Names, definitions, and the global environment in Scheme (SICP)

” A critical aspect of a programming language is the means it provides for using names to refer to computational objects. We say that the name identifies a variable whose value is the object.

In the Scheme dialect of Lisp, we name things with define. Typing

(define size 2)

causes the interpreter to associate the value 2 with the name size. Once the name size has been associated with the number 2, we can refer to the value 2 by name:

size
2

(* 5 size)
10

Here are further examples of the use of define:

(define pi 3.14159)
(define radius 10)
(* pi (* radius radius))
314.159

(define circumference (* 2 pi radius))
circumference
62.8318

define is our language’s simplest means of abstraction, for it allows us to use simple names to refer to the results of compound operations, such as the circumference computed above. In general, computational objects may have very complex structures, and it would be extremely inconvenient to have to remember and repeat their details each time we want to use them. Indeed, complex programs are constructed by building, step by step, computational objects of increasing complexity. The interpreter makes this step-by-step program construction particularly convenient because name-object associations can be created incrementally in successive interactions. This feature encourages the incremental development and testing of programs and is largely responsible for the fact that a Lisp program usually consists of a large number of relatively simple procedures.

It should be clear that the possibility of associating values with symbols and later retrieving them means that the interpreter must maintain some sort of memory that keeps track of the name-object pairs. This memory is called the environment (more precisely the global environment, since we will see later that a computation may involve a number of different environments).”

Structure and Interpretation of Computer Programs (SICP), ‘1.1.2 Naming and the Environment

Simple expressions, combinations & evaluation in Scheme (SICP)

” […] Imagine that you are sitting at a computer terminal. You type an expression, and the interpreter responds by displaying the result of its evaluating that expression. One kind of primitive expression you might type is a number. […]

Expressions representing numbers may be combined with an expression representing a primitive procedure (such as + or *) to form a compound expression that represents the application of the procedure to those numbers. For example:

(+ 137 349)
486

(- 1000 334)
666

(* 5 99)
495

[...]

Expressions such as these, formed by delimiting a list of expressions within parentheses in order to denote procedure application, are called combinations. The leftmost element in the list is called the operator, and the other elements are called operands.

The value of a combination is obtained by applying the procedure specified by the operator to the arguments that are the values of the operands.”

Structure and Interpretation of Computer Programs (SICP), ‘1.1  The Elements of Programming

Why Scheme makes a good teaching language (SICP)

“In teaching our material we use a dialect of the programming language Lisp. We never formally teach the language, because we don’t have to. We just use it, and students pick it up in a few days. This is one great advantage of Lisp-like languages: They have very few ways of forming compound expressions, and almost no syntactic structure. All of the formal properties can be covered in an hour, like the rules of chess. After a short time we forget about syntactic details of the language (because there are none) and get on with the real issues — figuring out what we want to compute, how we will decompose problems into manageable parts, and how we will work on the parts. Another advantage of Lisp is that it supports (but does not enforce) more of the large-scale strategies for modular decomposition of programs than any other language we know. We can make procedural and data abstractions, we can use higher-order functions to capture common patterns of usage, we can model local state using assignment and data mutation, we can link parts of a program with streams and delayed evaluation, and we can easily implement embedded languages. All of this is embedded in an interactive environment with excellent support for incremental program design, construction, testing, and debugging. We thank all the generations of Lisp wizards, starting with John McCarthy, who have fashioned a fine tool of unprecedented power and elegance.

Scheme, the dialect of Lisp that we use, is an attempt to bring together the power and elegance of Lisp and Algol. From Lisp we take the metalinguistic power that derives from the simple syntax, the uniform representation of programs as data objects, and the garbage-collected heap-allocated data. From Algol we take lexical scoping and block structure, which are gifts from the pioneers of programming-language design who were on the Algol committee.”

Structure and Interpretation of Computer Programs, ‘1.1  The Elements of Programming

The development of Lisp as a symbol-manipulation language (SICP)

“Despite its inception as a mathematical formalism, Lisp is a practical programming language. A Lisp interpreter is a machine that carries out processes described in the Lisp language. The first Lisp interpreter was implemented by McCarthy with the help of colleagues and students in the Artificial Intelligence Group of the MIT Research Laboratory of Electronics and in the MIT Computation Center. Lisp, whose name is an acronym for LISt Processing, was designed to provide symbol-manipulating capabilities for attacking programming problems such as the symbolic differentiation and integration of algebraic expressions. It included for this purpose new data objects known as atoms and lists, which most strikingly set it apart from all other languages of the period.

Lisp was not the product of a concerted design effort. Instead, it evolved informally in an experimental manner in response to users’ needs and to pragmatic implementation considerations. Lisp’s informal evolution has continued through the years, and the community of Lisp users has traditionally resisted attempts to promulgate any “official” definition of the language. This evolution, together with the flexibility and elegance of the initial conception, has enabled Lisp, which is the second oldest language in widespread use today (only  Fortran is older), to continually adapt to encompass the most modern ideas about program design. Thus, Lisp is by now a family of dialects, which, while sharing most of the original features, may differ from one another in significant ways.”

Structure and Interpretation of Computer Programs, ‘Chapter 1: Building Abstractions with Procedures

Computer programs as developing models / Design to handle complexity (SICP)

“Every computer program is a model, hatched in the mind, of a real or mental process. These processes, arising from human experience and thought, are huge in number, intricate in detail, and at any time only partially understood. They are modeled to our permanent satisfaction rarely by our computer programs. Thus even though our programs are carefully handcrafted discrete collections of symbols, mosaics of interlocking functions, they continually evolve: we change them as our perception of the model deepens, enlarges, generalizes until the model ultimately attains a metastable place within still another model with which we struggle. The source of the exhilaration associated with computer programming is the continual unfolding within the mind and on the computer of mechanisms expressed as programs and the explosion of perception they generate. […]

For all its power, the computer is a harsh taskmaster. Its programs must be correct, and what we wish to say must be said accurately in every detail. As in every other symbolic activity, we become convinced of program truth through argument. Lisp itself can be assigned a semantics (another model, by the way), and if a program’s function can be specified, say, in the predicate calculus, the proof methods of logic can be used to make an acceptable correctness argument. Unfortunately, as programs get large and complicated, as they almost always do, the adequacy, consistency, and correctness of the specifications themselves become open to doubt, so that complete formal arguments of correctness seldom accompany large programs. Since large programs grow from small ones, it is crucial that we develop an arsenal of standard program structures of whose correctness we have become sure — we call them idioms — and learn to combine them into larger structures using organizational techniques of proven value. […] More than anything else, the uncovering and mastery of powerful organizational techniques accelerates our ability to create large, significant programs. Conversely, since writing large programs is very taxing, we are stimulated to invent new methods of reducing the mass of function and detail to be fitted into large programs.

— Alan J. Perlis, Structure and Interpretation of Computer Programs (2nd ed), ‘Foreword

Functional programming in Python and Lisp

I’ve been trying to learn more about functional programming – specifically, looking at functional programming patterns in Python and Lisp/Scheme code. While reading about Python’s “functional” features (first-class functions, generators, list comprehensions, etc) I ran across many articles/books on functional programming in Haskell, Lisp, Scheme etc.

Years ago I had picked up a few books on Common Lisp and Scheme, but was unable to grok it due to some fundamental conceptual pieces I was missing at the time. But over the past few weeks as I have started exploring Lisp-like languages again, my mind has been blown.

The single biggest problem that I’ve had with programming languages I’ve used (C/Perl/Java/Python) is rigid and complicated syntax being forced upon me, the programmer. Constantly, this syntax is getting in the way of me clearly expressing what I want the computer to do, and is instead forcing me to contort my ideas into a form that fits into the languages’ strict and inflexible syntax rules.

The two things that have intrigued me most about Lisp are:

1) the ability to write beautiful, readable code with a simple/minimal yet highly expressive syntax (s-expressions and function application / evaluation)

2) the ability to define your own syntax using macros. If a language feature is getting in the way, you simply change it by writing macros that define customized syntax that clearly expresses concepts in a particular context / problem domain …

I am excited to explore these features more in the coming months – specifically by working with tools for Lisp/Python interaction (sharing code/data between programs written in each) … I’ll be posting writeups periodically to describe what I’ve learned.

List-eating functions in Lisp

“Since the Lisp philosophy strongly emphasizes the use of lists to store and manipulate information, it will come as no surprise that the design of Common Lisp favors behaviors that make it easy to slice and dice such lists. The most profound design decision made in Common Lisp, with regard to lists, is that it automatically treats an empty list as a false value when evaluating a condition […]  when we pass the empty list () into an if form, it evaluates as a false value, whereas a list that contains an item evaluates as true.

Because we can easily detect an empty list, we can process lists using recursion. With this technique, we can take items from the front of a list and send the rest of the list back to the same function until the list is empty. (It’s a good thing that detecting empty lists is so easy, because so many functions in Lisp end up being list-eaters.)

Let’s look at a common list-eating function, which calculates the length of a list:

> (defun my-length (list)
     (if list
         (1+ (my-length (cdr list)))
         0))

> (my-length '(list with four symbols))
   4

This function is written in classic Lisp style. It calls itself recursively as it chomps items off the front of the list. Calling yourself in this way is not only allowed in Lisp, but is often strongly encouraged. Lists in Lisp are recursive (conses of conses of conses . . .), so the act of consuming a list maps naturally onto functions that are recursive.”

— Conrad Barski, The Land of Lisp: Learn to Program in Lisp, One Game at a Time (No Starch Press, 2011)

Common Lisp / Scheme macros

Here is a collection of snippets I’ve found helpful for understanding Common Lisp and Scheme macros …

 

“Macros are the single greatest advantage that Lisp has as a programming language and the single greatest advantage of any programming language. With them you can do things that you simply cannot do in other languages. Because macros can be used to transform lisp into other programming languages and back, programmers who gain experience with them discover that all other languages are just skins on top of lisp. This is the big deal. Lisp is special because programming with it is actually programing at a higher level. Where most languages invent and enforce syntactic and semantic rules, lisp is general and malleable. With lisp, you make the rules. […]

[…] macros are still not used to the fullest possible extent by most lisp programmers and are not used at all by all other programmers. This has always been a conundrum for advanced lispers. Since macros are so great, why doesn’t everybody use them all the time? While it’s true that the smartest, most determined programmers always end up at lisp macros, few start their programming careers there. Understanding why macros are so great requires understanding what lisp has that other languages don’t. It requires an understanding of other, less powerful languages. Sadly, most programmers lose the will to learn after they have mastered a few other languages and never make it close to understanding what a macro is or how to take advantage of one. But the top percentile of programmers in any language are always forced to learn some sort of way to write programs that write programs: macros. Because it is the best language for writing macros, the smartest and most determined and most curious programmers always end up at lisp.

Although the top-percentile of programmers is necessarily a small number, as the overall programming population grows so does the number of top-percentile programmers. The programming world sees few examples of the power of macros and understands far fewer, but this is changing. Because of the productivity multiplication that can be achieved through macros, the age of the macro is coming, whether the world is ready or not. […] Be prepared.

The conventional wisdom surrounding macros is to use them only when necessary because they can be difficult to understand, contain extremely subtle bugs, and limit you in possibly surprising ways if you think of everything as functions. These aren’t defects in the lisp macro system itself but instead are traits of macro programming in general. As with any technology, the more powerful the tool, the more ways there are to misuse it. And, as far as programming constructs go, lisp macros are the most powerful tool.

An interesting parallel to learning macros in lisp is that of learning pointers in the C programming language. Most beginning C programmers are able to quickly pick up most of the language. Functions, types, variables, arithmetic expressions: all have parallels in previous intellectual experiences beginners might have had, from elementary school maths to experimenting with simpler programming languages. But most novice C programmers hit a brick wall when they encounter pointers.

Pointers are second nature to experienced C programmers, most of whom consider their complete understanding necessary for the proper use of C. Because pointers are so fundamental, most experienced C programmers would not advise limits on their use for stylistic or learning purposes. Despite this, many C novices feel pointers are an unnecessary complication and avoid their use, resulting in the FORTRAN in any language symptom where valuable language features are neglected. The disease is ignorance of the language’s features, not poor programming style. Once the features are fully understood, the correct styles are obvious. An auxiliary theme […] is that in programming, style is not something to pursue directly. Style is necessary only where understanding is missing1.

Like C pointers, the macro is a feature of lisp that is often poorly understood, the wisdom on its proper use being very distributed and idealised. If when considering macros you find yourself relying on stylistic aphorisms like

Macros change the syntax of lisp code.

Macros work on the parse tree of your program.

Only use macros when a function won’t do.

you are probably missing the big picture when it comes to macro programming.”

— Doug Hoyte, Let Over Lambda: 50 Years of Lisp (Introduction)


“When writing computer programs, certain patterns arise over and over again. For example, programs must often loop through the elements of arrays, increment or decrement the values of variables, and perform multi-way conditionals based on numeric or character values. Programming language designers typically acknowledge this fact by including special-purpose syntactic constructs that handle the most common patterns.  C, for instance, provides multiple looping constructs, multiple conditional constructs, and multiple constructs for incrementing or otherwise updating the value of a variable.

Some patterns are less common but can occur frequently in a certain class of programs or perhaps just within a single program. These patterns might not even be anticipated by a language’s designers, who in any case would typically choose not to incorporate syntactic constructs to handle such patterns in the language core. Yet, recognizing that such patterns do arise and that special-purpose syntactic constructs can make programs both simpler and easier to read, language designers sometimes include a mechanism for syntactic abstraction , such as C’s preprocessor macros or Common Lisp macros.[…]

Syntactic abstraction facilities differ in several significant ways. C’s preprocessor macros are essentially token-based, allowing the replacement of a macro call with a sequence of tokens with text from the macro call substituted for the macro’s formal parameters, if any. Lisp macros are expression-based, allowing the replacement of a single expression with another expression, computed in Lisp itself and based on the subforms of the macro call, if any.”

— R. Kent Dybvig, Syntactic Abstraction: The syntax-case expander


“A Lisp macro is like a function that takes Lisp forms or objects as input, and typically generates code to be then compiled and executed. This happens before runtime, in a phase called macroexpansion time. Macros can perform arbitrary computation during expansion, using the full Lisp language.

One use of macros is transforming input representing arbitrary source code into a version specified in terms of known definitions. In other words, macros can add new syntax to the original language (this is known as syntactic abstraction).

This enables easily embedding domain-specific languages, since specialized syntax can be added before runtime.

The chief benefit of macros is that they add power by letting the programmer express intent clearly and with less code. Particularly, one can add new features to the language that appear as if they were builtin. In addition, when used to pre-emptively compute data or initialize state, macros may aid in performance optimisation.”

— Abhishek Reddy, Features of Common Lisp

 


“An important principle of macro design is top-down programming. When designing a lisp macro, you want to start with the abstraction first. You want to write programs that use the macro long before you write the macro itself. Somewhat paradoxically, you need to know how to program in a language before you can write a concise definition/implementation for that language.

So the first step in serious macro construction is always to write use cases of the macro, even though there is no way you can test or use them. If the programs written in the new language are comprehensive enough, a good idea of what will be required to implement a compiler or interpreter for the language will follow.”

— Doug Hoyte, Let Over Lambda: 50 Years of Lisp (Chapter 5: Programs that Program)

 

+++

+++


 

“In Common Lisp, the rule is simple. If the first symbol of a form is defined as a macro, the macroexpander is called with the unevaluated arguments of the form, and then the return value is recursively macroexpanded. Since everything’s an S-expression, you don’t need any more than this. Any macro you create will have the same syntax as normal Lisp forms.”

— Random stranger @ C2-Wiki …


///

“Macros can leverage a technique called implicit context. In code that is used frequently, or absolutely must be concise and lacking any surrounding book-keeping cruft, we sometimes choose to implicitly add lisp code around portions of an expression so we don’t have to write it every time we make use of an abstraction. We’ve talked before about implicit contexts and it should be clear that even when not programming macros they are a fundamental part of lisp programming: let and lambda forms have an implicit progn because they evaluate, in sequence, the forms in their body and return the last result.”

— Doug Hoyte, Let Over Lambda: 50 Years of Lisp (Chapter 5: Programs that Program)


“In essence, hygienic macro expansion implements lexical scoping with respect to the source code, whereas unhygienic expansion implements lexical scoping with respect to the code after expansion.”