Rabbit: A Compiler for Scheme/Chapter 6
[Page 38]
28 6. The Use of Macros An important characteristic of the SCHEME language is that its set of primitive constructs is quite small. This set is not always convenient for expressing programs, however, and so a macro facility is provided for extending the expressive power of the language. A macro is best thought of as a syntax rewrite rule. As a simple example, suppose we have a primitive GCD which takes only two arguments, and we wish to be able to write an invocation of a GCD function with any number of arguments. We might then define (in a 'production-rule" style) the conditional rule:
(XGCD) => 0 (XGCD x) => x (XGCD x _ rest) => (GCD x (XGCD . rest)) (Notice the use of LISP dots to refer to the rest of a list.) This is not considered to be a definition of a function XGCD, but a purely syntactic transformation. In principle all such transformations could be performed before executing-the program. In fact, RABBIT does exactly this, although the SCHEME interpreter naturally does it incrementally, as each macro call is encountered.
Rather than use a separate production-rule/pattern-matching language, in practice SCHEME macros are defined as transformation functions from macro-call expressions to resulting S-expressions, just as they are in MacLISP. (Here, however, we shall continue to use production rules for purposes of exposition.) It is important to note that macros need not be written in the language for which they express rewrite rules; rather, they should be considered an adjunct to the interpreter, and written in the same language as the interpreter (or the compiler). To see this more clearly, consider a version of SCHEME which does not have S~expressions in its data domain. If programs in this language are
[Page 39]
Z9 represented as S-expressions, then the interpreter for that language cannot be written in that language, but in another metalanguage which does deal with S-expressions. Macros, which transform one S-expression (representing a macro call) to another (the replacement form, or the interpretation of the call), clearly should be expressed in this metalanguage also. The fact that in most LISP systems the language and the metalanguage appear to coincide is a source of both power and confusion.
K In the PDP-10 MacLISP implementation of SCHEME, four separate macro mechanisms are used in practice. One is the MacLISP read-macro mechanism [Moon], which performs transformations such as 'FOO => (QUOTE FOO) when an expression is read from a file. The other three are as described earlier, processed by the interpreter or compiler, and differ only in that one kind is recognized by the MacLISP interpreter as well while the other two are used only by SCHEME, and that of the latter two one kind is written in MacLISP and the other kind in SCHEME itself.
There is a growing library of SCHEME macros which express a variety of traditional programming constructs in terms of other, more primitive constructs, and eventually in terms of the small set of primitives. A number of these are catalogued in [Imperative] and [Revised Report]. Others were invented in the course of writing RABBIT. We shall give some examples here.
The BLOCK macro is similar to the MacLISP PROGN; it evaluates all. its arguments and returns the value of the last one. One critical characteristic is that the last argument is evaluated 'tail-recursively' (I use horror quotes because normally we speak of invocation, not evaluation, as being tail-recursive). An expansion rule is given for this in [Imperative] equivalent to:
(BLOCK x) => x (BLOCK x . rest) => ((LAMBDA (DUMMY) (BLOCK . rest)) x)
[Page 40]
30 This definition exploits the fact that SCHEME is evaluated in applicative order, and so will evaluate all arguments before applying a function to them. Thus, in the second subrule, x must be evaluated, and then the block of all the rest is.
It is then clear from the first subrule that the last argument is evaluated "tail-recursively".
One problem with this definition is the occurrence of the variable DUMMY, which must be chosen so as not to conflict with any variable used by the user.
This we refer to as the "GENSYM problem", in honor of the traditional LISP function which creates a "fresh" symbol. It would be nicer to write the macro in such a way that no conflict could arise no matter what names were used by the user. There is indeed a way, which ALGOL programmers will recognize as equivalent to the use of "thunks", or call-by-name parameters:
(BLOCK x) => x (BLOCK x _ rest) => ((LAMBDA (A B) (B)) (LAMBDA () (BLOCK . rest))) Consider carefully the meaning of the right-hand side of the second subrule.
First the expression x and the (LAMBDA () ...) must be evaluated (it doesn't matter in which order!); the result of the latter is a function (that is, a closure), which is later invoked in order to evaluate the rest of the arguments.
There can be no naming conflicts here, because the scope of the variables A and B (which is lexical) does not contain any of the arguments to BLOCK written by the user. (we .should note that we have been sloppy in speaking of the "arguments" to BLOCK, when BLOCK is properly speaking not a function at all, but merely a syntactic keyword used to recognize a situation where a syntactic rewriting rule is applicable. we would do better to speak of 'argument expressions' or 'macro
[Page 41]
31 arguments", but we shall continue to be sloppy where no confusion should arise.) This is a technique which should be understood quite thoroughly, since it is the key to writing correct macro rules without any possibility of conflicts between names used by the user and those needed by the macro. As another example, let us consider the AND and OR constructs as used by most LISP systems.
OR evaluates its arguments one by one, in order, returning the first non-NIL value obtained (without evaluating any of the following arguments), or NIL if all arguments produce NIL. AND is the dual to this; it returns NIL if any argument does, and otherwise the value of the last argument. A simpleminded approach to OR would be:
(OR) => 'NIL (OR x . rest) => (IF x x (OR . rest)) There is an objection to this, which is that the code for x is duplicated. Not only does this consume extra space, but it can execute erroneously if x has any side-effects. We must arrange to evaluate x only once, and then test its value:
(OR) => 'NIL (OR x . rest) => ((LAMBDA (V) (IF V V (OR . rest))) x) This certainly evaluates x only once, but admits a possible naming conflict between the variable V and any variables used by rest. This is avoided by the same technique used for BLOCK:
(OR) => 'NIL (OR x _ rest) => ((LAMBDA (V R) (IF V V (R))) x (LAMBDA () (OR . rest))) Similarly, we can express AND as follows:
[Page 42]
32 (AND) => 'T (AND x) => x (AND x . rest) => ((LAMBDA (V R) (IF V (R) 'NIL)) (LAMBDA () (AND . rest))) (The macro rules are not precise duals because of the non-duality between NIL-ness and non-NIL-ness, and the requirement that a successful AND return the actual value of the last argument and not just T.) {Note Tail-Recursive OR) As yet another example, consider a modification to BLOCK to allow a limited form of assignment statement: if (v := x) appears as a statement in a block, it "assigns" a value to the variable v whose scope is the remainder of the block. Let us assume that such a statement cannot occur as the last statement of a block (it would be useless to have one in that position, as the variable would have a null scope). we can write the rule:
(BLOCK x) => X (BLOCK (v := x) . rest) => ((LAMBDA (v) (BLOCK . rest)) x) (BLOCK x . rest) => ((LAHBDA (A B) (B)) x (LAMBDA () (BLOCK . rest))) The second subrule states that an 'assignment' causes x to be evaluated and then bound to v, and that the variable v is visible to the rest of the block.
We may think of := as a "sub-macro keyword' which is used to mark an expression as suitable for transformation, but only in the context of a certain larger transformation. This idea is easily extended to allow other constructions, such as "simultaneous assignments' of the form ((varl var2 ... varn) := value] valueZ ... valuen) which first compute all the values and then assign to all the variables, and "exchange assignments" of the form (X :=: Y), as follows:
[Page 43]
33 (BLOCK x) => x (BLOCK (v := x) _ rest) => ((LAMBDA (v) (BLOCK . rest)) x) (BLOCK (vars := . values) . rest) => ((LAMBDA vars (BLOCK . rest)) . values) (BLOCK (x :=: y) _ rest) => ((LAMBDA (x y) (BLOCK . rest)) y x) (BLOCK x . rest) => ((LAMBDA (A B) (B)) x (LAMBDA () (BLOCK . rest))) Let us now consider a rule for the more complicated COND construct:
(COND) => 'NIL (COND (x) _ rest) => (OR x (COND . rest)) (COND (x . r) _ rest) => (IF x (BLOCK _ r) (COND . rest)) This defines the "extended" COND of modern LISP systems, which produces NIL if no clauses succeed, which returns the value of the predicate in the case of a singleton clause, and which allows more than one consequent in a clause. An important point here is that one can write these rules in terms of other macro constructs such as OR and BLOCK; moreover, any extensions to BLOCK, such as the limited assignment feature described above, are automatically inherited by COND.
Thus with the above definition one could write (COND ((NUMBERP X) (Y := (SORT X)) (+ Y (SORT Y))) (T (HACK X))) where the scope of the variable Y is the remainder of the first COND clause.
SCHEME also provides macros for such constructs as DO and PROG, all of which expand into similar kinds of code using LAMBDA, IF, and LABELS (see below).
In particular, PROG permits the use of GO and RETURN in the usual manner. In this manner all the traditional imperative constructs are expressed in an applicative manner. (Note ASET' Is Imperative) None of this is particularly new; theoreticians have modelled imperative
[Page 44]
34 constructs in these terms for years. What is new, we think, is the serious proposal that a practical interpreter and compiler can be designed for a language in which such models serve as the sole definitions of these imperative constructs. (Note Dijkstra's Opinion) This approach has both advantages and disadvantages.
One advantage is that the base language is small. A simpleminded interpreter or compiler can be written in a few hours. (We have reimplemented the SCHEME interpreter from scratch a dozen times or more to test various representation strategies; this was practical only because of the small size of the language. Similarly, the CHEAPY compiler is fewer than ten pages of code, and could be rewritten in a day or less.) Once the basic interpreter is written, the macro definitions for all the complex constructs can be used without revision. Moreover, the same macro definitions can be used by both interpreter and compiler (or by several versions of interpreter and compiler!). Excepting the very few primitives such as LAMBDA and IF, it is not necessary to "implement a construct twice", once each in interpreter and compiler.
Another advantage is that new macros are very easy to write (using facilities provided in SCHEME). One can easily invent a new kind of DO loop, for example, and implement it in SCHEME for both interpreter and all compilers in less than five minutes. (In practice such new control constructs, such as the ITERATE loop described in [Revised Report], are indeed installed within five to ten minutes of conception, in a routine manner.) I A third advantage is that the attention of the compiler can be focused on the basic constructs. Rather than having specialized code for two dozen different constructs, the compiler can have much deeper knowledge about each of a few basic constructs. One might object that this "deeper knowledge' consists of recognizing the two dozen special cases represented by the separate constructs of
[Page 45]
35 the former case. This is true to some extent. It is also true, however, that in the latter case such deep knowledge will carry over to any new constructs which are invented and represented as macros.
Among the disadvantages of the macro approach are lack of speed and the discarding of information. Many people have objected that macros are of necessity slower than, say, the FSUBR implementation used by most LISP systems.
This is true in many current interpretive implementations, but need not be true of compilers or more cleverly designed interpreters. Moreover, the FSUBR implementation is not general; it is very hard for a user to write a meaningful FSUBR and then describe to the compiler the best way to compile it. The macro approach handles this difficulty automatically. We do not object to the use of the FSUBR mechanism as a special-case "speed hack" to improve the performance of an interpreter, but we insist on recognizing the fact that it is not as generally useful as the macro approach.
Another objection relating to speed is that the macros produce convoluted code involving the temporary creation and subsequent invocation of many closures. we feel, first of all, that the macro writer should concern himself more with producing correct code than fast code. Furthermore, convolutedness can be eliminated by a few simple optimization techniques in the compiler, to be discussed below. Finally, function calls need not be as expensive as is popularly supposed. [Steele] Information is discarded by macros in the situation, for example, where a DO macro expands into a large mess that is not obviously a simple loop; later compiler analysis must recover this information. This is indeed a problem. We feel that the compiler is probably better off having to recover the information anyway, since a deep analysis allows it to catch other loops which the user did not use DO to express for one reason or another. Another is the possibility that
[Page 46]
36 DO could leave clues around in the form of declarations if desired.
Another difficulty with the discarding of information is the issuing of meaningful diagnostic messages. The user would prefer to see diagnostics mention the originally-written source constructs, rather than the constructs into which the macros expanded. (An example of this problem from another LISP compiler is that it may convert (MEMQ X '(A B C)) into (OR (EQ X 'A) (EQ X 'B) (EQ X 'C)); when by the same rule it converts (MEMQ X '(A)) (a piece of code generated by a macro) into (OR (EQ X 'A)), it later issues a warning that an OR had only one subform.) This problem can be partially circumvented if the responsibility for syntax-checking is placed on the macro definition at each level of expansion.