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

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.”