CS386L Advanced Programming Languages Paul Wilson, U. of Texas, Austin (wilson@cs.utexas.edu) Notes on inline procedures, macros, scoping, and hygeine --- Copyright 1994 Paul R. Wilson Until 1998, you may use these notes freely for noncommercial purposes, as long as this notice is preserved in all copies. After January 1, 1998, you must obtain permission from the author to copy or redistribute. -------------------------------------------------------------------- INLINE PROCEDURES In many modern languages, it is possible to declare a procedure to be "inlinable", meaning that the compiler can replace calls to that procedure with the code for the procedure, "in line". (A normal procedure call is "out of line", because it branches away and comes back.) This is often a good idea for small procedures (e.g., eq?), where the procedure calling overhead is a significant fraction of the cost of the work done by the procedure. (In the case of eq?, it's an excellent idea because the procedure calling overhead may be several times greater than the actual work done in eq?) There is also an advantage for optimizing compilers, in that inlining allows them to "see into" code that otherwise would be hidden from them by a procedure call---they can eliminate common subexpressions between the call site and the called procedure, because they can see the (copy of the) procedure body as part of the code for the caller. The main advantage of inline procedures is that they have the semantics of a procedure call with the efficiency of writing out the operation explicitly. It's a way of getting procedural abstraction without paying a runtime cost. One problem with inline procedures in interactive programming languages is that if you change the definition of an inline procedure, all of the code compiled with the old definition inline becomes obsolete. Most systems do not keep track of which procedures have been inlined into which other procedures, so they don't automatically recompile the calling procedures when the inlined callees are redefined. (There are a few systems that do, however---if you inline a procedure and the definition is changed, the old code is recompiled. Actually, the code is invalidated and will be recompiled "lazily", i.e., when and if it is needed again.) In systems which don't keep track of this sort of thing, inlined procedures are not first class in quite the same sense as normal procedures---there is no lookup via a pointer expression to find the right procedure at every call. Notice, though, that an inlinable procedure may still be first class in the sense that it can be passed as an argument (e.g., to map). When an inline procedure is compiled, the compiler may really create two versions: one normal, fully compiled, first-class procedure, and one partly-compiled representation of the procedure that can be used for inlining it into other procedures. --------------------------------------------------------------------- MACROS Macros are SYNTACTIC EXTENSIONS of a programming language, expressed as a rewriting of expressions. By writing a macro, what you're really doing is extending the functionality of the compiler or interpreter---you're telling it how to compile a new construct, by telling it how to rewrite that construct into something it already knows how to compile or interpret. The process of rewriting a macro use into lower-level constructs is called MACROEXPANSION, despite the fact that the resulting expression may not be bigger than the original expression. Macroexpansion can be recursive, because macros can use macros. Macros are powerful, and hence dangerous when used casually. Be aware that when you write a macro, you can change the syntax of your programming language, and that can be a bad thing---you and others may no longer be able to easily understand what the program does. Used judiciously, however, such syntactic extensions are often just what you nead to simplify your programs. We will talk about a simple butvery powerful macro system first; this kind of macro system is hard to use safely. Then we will talk about some more advanced macro systems that are easier to use in safe ways. ULTRA-SIMPLE LISPish MACROS The classic macro system is the LISP macro system, which allows the user to define an arbitrary LISP procedure to rewrite a new construct. (Most dialects of Lisp, e.g., Common Lisp, have a macro facility of the same general kind, called DEFMACRO.) We'll talk for a moment about a simplified version of Lisp-style macros. Suppose, for example, you have a Lisp system which gives you things like LET and IF, but not OR. You want an OR construct (rather like the one built into Scheme). Can take a pair of arguments, evaluates the first one and returns the result if it's a true value, otherwise it evaluates the second one and returns that result. Suppose also that we have a macro system that we can use to tell the interpreter or compiler that when it sees an expression that's a list starting with a particular symbol, it should call a particular routine to rewrite that expression, and use the rewritten version in its place. For the OR example, we want to tell the compiler that if it sees an expression of the form (or first-arg second-arg), it should rewrite that into an expression of the form (if first-arg first-arg second-arg) That is, test first-arg, and return first-arg if it's not eq? to #f. That's not really quite right though, because this if statement evaluates first-arg twice: once to test it, and once to return it. We really only want to evaluate a once---if first-arg is an expression with side effects, evaluating it twice could make the program incorrect as well as inefficient. So we'll evaluate first-arg once to get the value, and store that value in a temporary variable so that we can return it without evaluating it again: (let ((temp first-arg)) (if temp temp second-arg)) (Actually, there's still a lurking bug here, but we're going to ignore it for now.) So now we want to tell the compiler how to rewrite expressions like that. Since LISP expressions are represented as lists, we can use normal list operations to examine the expression and generate the new expression. Let's assume our system has a special form called define-rewriter that lets us specify a procedure of one argument to write a particular kind of expression. (define-rewriter (or expr) ; tell compiler how to rewrite (or ...) (let ((first-arg (cadr expr)) (second-arg (caddr expr))) (cons 'let ; make LET (cons (list (list 'temp first-arg))) ; make let binding (append '(if temp temp) ; make IF expr (list second-arg)) Now when the interpreter or compiler is about to evaluate a list expression, it will check to see if it starts with or. If so, it will pass the expression to the above rewriter procedure, and interpret or compile the resulting list instead. (Actually, macroexpansion doesn't have to happen just before interpreting or compiling a particular expression. The system might rewrite all of the macro calls in a whole procedure, or a whole program, before feeding the procedure or program to the normal part of the compiler. It's easier to understand macros if they're interleaved with expression evaluation or compilation, though---it's just an extra case in the main dispatch of your interpreter or compiler.) The above system works, but it has several awkwardnesses. First, the user has to write annoying little expressions to destructure the expression being rewritten. ("Destructure" means take apart to get at the components---in this case, subexpressions.) It would be nice if the macro facility allowed you to declare the argument pattern to the macro, and automatically destructured it for you. Most Lisp systems have a special form called DEFMACRO that does this for you. For consistency with Scheme naming conventions, we'll call our equivalent DEFINE-MACRO. (define-macro (or first-arg second-arg) (cons 'let ; make LET (cons (list (list 'temp first-arg))) ; make let binding (append '(if temp temp) ; make IF expr (list second-arg)) This is still annoyingly tedious to use, however. We know the form of the expression we want to generate, which just has a couple of holes in it that we want filled. Scheme and most Lisp systems have a facility called QUASIQUOTE (or sometimes BACKQUOTE) that can help with this. Quasiquoting is like quoting, except that you can specify which substructures of a complex structure should be un-quoted, i.e., filled in with something that's not a literal. For un-quoting, you use COMMA. There's a little bit of magic in the reader routine that allows you to use the backquote character "`" for the special form QUASIQUOTE, and the comma character "," for the UNQUOTE operation: (define-macro (or first-arg second-arg) `(let ((temp ,first-arg)) (if temp temp ,second-arg)) Backquote means that we want literally the backquoted expression, except that the expressions following the commas SHOULD be evaluated (in this case, the values of the variables first-arg and second-arg should be looked up) and spliced into the expression as though those values had occurred there as literals. The combination of argument destructuring and the use of backquote lets us write macros that look pretty much like procedures. In the above example, the entire body of the macro are backquoted, because the whole body of the macro is the template for the code it will generate. --- QUASIQUOTE is not just for macros---it's useful in a lot of situations where you want an almost-literal value with a few holes filled in. In fact, Scheme had quasiquote from the start, but macros were added to the standard several years later. Quasiquote is very handy for expressing the construction of s-expressions that are mostly boilerplate, whether those lists are expressions to be evaluated or just data structures that need to be built. Besides UNQUOTE, Scheme provides UNQUOTE-SPLICING, which lets you splice a list into a mostly-quoted list, rather than inserting it as a sublist. You can use a comma followed by an at sign ",@" for unquote-splicing. Examples: Scheme> (define name-of-next-sucker 'Jones) name-of-next-sucker Scheme> (display `(Dear Mr/Ms ,name-of-next-sucker)) (Dear Mr/Ms Jones) Scheme> (define phrase-of-the-day '(the Lord helps those who take a big helping for themselves)) Scheme> (display `(And remember that ,@phrase-of-the-day)) (And remember that the Lord helps those who take a big helping for themselves) Notice that in the second example, if we'd used plain old unquote rather than unquote-splicing, this is what would've happened: Scheme> (display `And remember that ,phrase-of-the-day)) (And remember that (the Lord helps those who take a big helping for themselves)) --- GOOD, BAD, AND UGLY USES OF MACROS Historically, macros have been used for a lot of things: 1. getting the effect of inline procedures 2. implementing portable abstractions via conditional compilation 3. defining new special forms 4. implementing optimizations outside the main compiler, by source-to-source transformations. FAKING INLINE PROCEDURES Historically, macros have often been used to get the effect of inline procedures. This works, sort of, and made sense when compilers didn't support inline procedures, but it's not as good as actually having inline procedures. For one thing, it's easy to make mistakes about argument evaluation. A compiler that implements inline procedures guarantees that the argument expressions will be evaluated just once, before the code for the procedure is executed---just as with a normal procedure. When people use macros instead of inline procedures, they must be very careful that the argument expressions are used exactly once in the body of the macro, just as we did for the OR macro by wrapping the if in a let. As we will see later, this approach is difficult for programmers to get right, because of scoping problems. In general, using macros like inline procedures is a bad idea. Macros are powerful, and its easy to do various things by accident when all you wanted was an inline procedure. If you find yourself writing lots of macros just for the speed gain of inline procedures, you're probably using a lousy language or compiler and should move up to something more modern. Unfortunately, standard Scheme does not have inline procedures; that's because Scheme is not really oriented toward being an extremely high-speed standardized language for developing huge applications---it's more oriented toward being an elegant, simple, easily usable and powerful language. (Eventually Scheme may have more features like inline procedures to make it suitable for performance-critical application development. Meantime, there are high-performance implementations of Scheme that use nonstandard extensions for inlining, and the standardized-but-optional "high-level" macro facility is easier to use safely than conventional macros.) CONDITIONAL COMPILATION FOR CONFIGURABILITY AND PORTABILITY A very common use of macros in C is for conditional compilation, meaning that a program can be configured differently for different uses or to run on different platforms. For example, you may want to be able to compile one version of a program that has certain features, and compile another version that does not. For example, in the implementation of RScheme, which is partly implemented in C, certain parts of the code say something like #ifdef VIBRANT_GRAPHICS #else #endif The programmer can set the flag VIBRANT_GRAPHICS at compile time, and compile a version with graphics capabilities. If the flag is not set, then a version without graphics is compiled. (This can be an advantage if the RScheme system is going to be used for textual interaction only, and it is not necessary to include all of the code for the graphics subsystem. The resulting program will be smaller, and start up more quickly.) Another use of conditional compilation is to mask differences between platforms (hardware/OS/compiler combinations) so that most of the code can be written without regard to those differences. The graphics system of RScheme will not work on all platforms (In particular, any system that does not have one of the following underlying graphics systems: Microsoft Windows, X Windows, or the Macintosh windowing system.) The graphics subsystem itself uses conditional compilation to generate different code for different window systems---e.g., a different call to the underlying system to create a window or a menu. Another example of using conditional compilation for portability is that C compilers for different platforms may have different default sizes for integers, and it may be desirable to have a way of specifying an integer of a particular size, no matter what compiler is being used. Conditional compilation makes it possible to set up a program with different code for different platforms, to hide the differences between different platforms. We can come up with our own word for a 32-bit signed integer, and generate a different type name for different underlying compilers, e.g., #ifdef GNU_C_ON_LINUX #define int32 long int #elsif DEC_C_ON_ALPHA #define int32 int #endif This conditionally defines the meaning of the string "int32" to be replaced by the string "long int" on one platform and by "int" on another. Once the appropriate mappings for each platform have been established in this way, programmers can freely use "int32" to mean 32-bit integer on all platforms. DEFINING NEW SPECIAL FORMS Another important use of macros is to define useful new special forms that are not provided directly by the underlying language. (The "or" example is an example of this, albeit a very simple one.) Another example of this is the widely-used Common Lisp "loop" macro. The loop macro defines a loop construct with a large number of possible options and cominations of options. It can include "while" and "unless" conditions, and a variety of special clauses to collect the results of iterations into lists, and so on. This macro is itself written in Common Lisp. It examines the combination of clauses used in a particular loop and generates appropriate code (which may be rather complex) in the simpler base language of Common Lisp, which only has a few built-in loop types. IMPLEMENTING OPTIMIZATIONS AS SOURCE-TO-SOURCE TRANSFORMATIONS When the code for a macro transformation is written in a powerful language like Lisp, it is possible for the transformation code to do important analyses, and generate very different kinds of code depending on the interactions between the various options used. The Common Lisp loop macro does this---the code it generates for one loop may look very little like the code generated for another, because the macro doesn't simply leave out parts that aren't used. It analyzes the combination of expressions, and notices which possible interactions can't occur in a particular case because some options are not used. It can therefore generate much more efficient code than if it simply filled in a template, and left out unused parts. This takes advantage of the fact that Lisp is a very powerful language for analyzing and constructing programs. It is much harder to do in weaker macro systems (like C' language's macro preprocessor), which don't give you the full power of a normal programming language. The nice thing about this is that the macro writer doesn't really need to know a lot about the underlying compiler---the optimizations performed by the macro are "high-level" optimizations, and the macro writer doesn't need to understand how a particular compiler represents control flow and data flow information. This is often a convenient division of labor---macros can be used to write optimizations that are easy to express in the language being compiled, and the normal compiler can do the low-level work of detailed control flow and data flow analysis to generate good machine code. --- NICE THINGS ABOUT MACROS IN LISP Standard Lisp-style macros have some very nice features. The main one is that macroexpansion happens AFTER reading in expressions as a list, and the representation used for expressions is the same as for common data structures in the language. This makes it easy to understand what a macro is doing, because the transformations of program expressions are expressed the same way as transformations of data structures. There's not a different syntax and language that the macro-writer has to learn in order to express the desired transformation. (Quasiquote, unquote, and unquote-splicing are very different kinds of things (with a very unusual syntax based on single characters), but they turn out to be easy enough to learn, and useful outside the context of macros as well.) Another nice thing about Lisp is that its prefix syntax and use of parentheses makes it easy to nest expressions that will be evaluated at different times. --- BAD THINGS ABOUT MACROS IN LISP Lisp macros have two major drawbacks that make them easy to misuse. One problem is that when an expression is transformed, strange things may happen because macro transformations don't respect the normal scope rules of the language---they're transformations of uninterpreted data structures, not of program fragments with well-defined meanings. It's very easy to put together expressions that don't mean what you think they do. The other major drawback is that when a programmer uses the Lisp language itself as the language for expressing transformations, it's unclear when those transformations will take place, and (more fundamentally) in what environment that transforming code will be executed. SCOPING PROBLEMS Earlier we alluded to a lurking bug in our macro definition for OR. Suppose we use the OR macro this way---we check to see if someone is employed as either a permanent or temporary employee, and generate a w2 tax form if either of those is true. (let ((temp (member x temporary-employees)) (perm (member x permanent-employees))) (if (or temp perm) (generate-w2 x))) The expansion of this is: (let ((temp (member x temporary-employees)) (perm (member x permanent-employees))) (if (let ((temp temp)) (if temp temp temp))) ;BUG! (should refer to outer temp, not inner) (generate-w2 x))) The problem here is that we happened to use the same name, temp, at both the call site and inside the macro definition. The reference to temp in (or temp perm) gets "captured" by the binding of temp introduced in the macro. This occurs because a normal macro facility does not understand issues of name binding---the variable temp refers to one thing at the call site, and another at the site of its use inside the macro, and the macroexpander doesn't know the difference. To the macroexpansion mechanism, the symbol temp is just a symbol, not a name of anything in particular, i.e., a particular program variable. There are two ways to get around this problem. One is for the macro-writer to be very careful to use names that are very unlikely to conflict with other names. This makes code very ugly, because of the unnatural names given to variables, but more importantly, it's harder to get right than it may seem. The other way around the problem is to get a much smarter macro facility, like the new optional high-level macro facility from the 4th revised version of the Scheme report. --- UGLY HACKS AROUND NAME CONFLICTS One way to avoid name conflicts is to pick names for variables used inside macros in such a way that they're unlikely to conflict with names that users of the macros might pick, e.g., (define-macro (or first-arg second-arg) `(let ((temp!in!or!macro ,first-arg) (if temp!in!or!macro temp!in!or!macro ,second-arg))) It's unlikely that anyone will name a different variable temp!in!or!macro someplace else, so the problem is solved, right? Not necessarily. Besides the fact that this is incredibly tacky, there's still a situation where this kind of solution is LIKELY to fail---when people nest calls to the same macro. Each nested call will use the same name for different variables, and things can go nuts. (Food for thought: is this true of the OR macro above? Does it nest properly? It's common in macros that define looping constructs using letrec.) The standard hack around that problem is to have each USE of the macro use a different name for each local variable that might get captured. This requires some extra machinery from the underlying system---there has to be a procedure that generates new, unique symbols, and which can be called by the macro code each time the macro is expanded, e.g.,: (define-macro (or first-arg second-arg) (let ((temp-name (generate-symbol))) `(let ((,temp-name ,first-arg) (if ,temp-name ,temp-name ,second-arg))) Notice that the outer let is outside the backquote---it will be executed when the macro is used (i.e., once each time an OR expression is rewritten; the quasiquoted part is the code to be interpreted or compiled after the holes are filled in. So the let will generate a new symbol, and then quasiquote will fill in the holes for the new symbol. (Be sure to get your metalevels right here: temp-name is the NAME OF the actual name that will be used for the variable.) Isn't this ugly? To some degree, Lisp macros are nice because you can use the same language (Lisp) in macros as you can in normal code. But due to these funky scoping issues, you effectively end up having to learn a new language---one with lots of generate-symbol calls and commas. On the other hand, maybe it builds character and abstract reasoning abilities, because you have to think a lot about names of names and things like that. Fun, maybe, but not for the faint of heart. --- TIME OF MACROEXPANSION AND ENVIRONMENTS FOR MACROEXPANSION The other big problem with Lisp macros is that while you can execute arbitrary code to expand a macro, it's not necessarily clear when that code will get executed, or in what environment. For example, in an interpreter, a macro call may be expanded every time that point in the program is reached. A macroexpander for the interpreter will thus run at normal program run-time, interleaved with the actions of the program. The macroexpansion code may be executed in a top-level runtime environment that is the same as the toplevel environments normal programs start running in. On the other hand, a compiler is likely to expand all macro calls just once, during the compilation of the procedures containing those calls. It might make a pass over all of the code in a procedure or file and expand all of the macros (recursively, if necessary) or expand each macro as it is encountered by the normal compiler, interleaved with normal compilation. In either kind of compile-time macro expansion, the macro code may be executed in the environment that the COMPILER runs in, rather than the environment that the compiled code will run in. Unfortunately, expanding calls "just once" is hard to do in practice, in an interactive program development system---it really means expanding all of the calls in a procedure every time that procedure is (re-) compiled. If the macro writer wants to build data structures and use side-effects during macro expansion, she must be willing to write code that works when it is executed several times, in strange orders relative to other code. A carelessly-coded macro may work when a whole program is compiled just once, but not if parts are recompiled separately during debugging. --- LEXICALLY SCOPED SYNTACTIC EXTENSIONS and HYGEINIC MACROEXPANSION The scoping problems of macroexpansion have been addressed in recent "hygeinic" macroexpansion systems, most of them developed for dialects of Scheme. (Scheme is often used for this because it's a nice language to work with, but the same technology could be applied to more conventional progamming languages.) Hygeinic macro systems automatically avoid the common problems of name capture, and restore lexical scope to systems that use macros. Just as programmers can use "gensyms" to ensure that names don't conflict and cause unintional capturing, a macro system can automatically rename variables used in macros and relieve the programmer of this burden. The programmer can write a macro in the obvious way, e.g., (define-syntax (or first-expr second-expr) (let ((temp first-expr)) (if first-expr first-expr second-expr))) and the macro system will ensure that a unique name is used for "temp" for every usage of the macro. NOTE: here we use DEFINE-SYNTAX rather than DEFINE-MACRO, to indicate that we're using a high-level syntax definition facility. Rather than using define-macro and backquote to achieve template filling, we assume that the high-level macro system does this by default, i.e., we assume we don't need a backquote around the body of the macro, because it's implicit in define-syntax. This renaming of variable during macro definition and expansion is known as "hygeinic macro expansion", because it eliminates some of the "unclean" and unsafe properties of normal macros. It is important to realize that what's going on with this renaming is that the renaming is a particular IMPLEMENTATION TECHNIQUE that is achieving the language-level goal of allowing LEXICALLY-SCOPED SYNTAX EXTENSIONS. That is, at the language level the programmer is defining new syntax (and a mapping from those syntactic constructs onto the base language) and the implementation must ensure that name conflicts don't break the usual lexical scope rules. (Unfortunately, lexically-scoped syntactic extensions are often called "hygeinic macros", even though I think that's really an abuse of terminology, because lexically scoped syntactic extensions can be implemented with other mechanisms.) --- DIFFICULTIES IN LEXICALLY-SCOPED SYNTAX EXTENSION In many common cases, it is straightforward to preserve lexical scope when defining a macro---a knowledgeable programmer can do it by being very careful, or a relatively straightforward macroexpansions system can do it automatically. There are cases where things are more difficult however, and they arise when defining constructs that themselves do interesting things with scope---namely constructs which themselves bind variables at the language level. An example of this harder case is FOR loops, which themselves bind loop-control variables at the langauage level. EASY CASES: CALL-BY-NAME INLINE PROCEDURES Before explaining the difficult cases, it will be useful to get a deeper understanding of the easy ones. When we define a macro like or, the effect that we want is of a CALL-BY-NAME inline procedure. What that means is that the arguments to the expression have their meaning fixed at the point where they're used. OR is an example of this. When we see (let ((x ...) (y ...)) (let ((z ...)) (or z (> x y)) It's clear that the arguments to the or refer to variables in the environment where the or is used---the usual lexical scope rules apply to the arguments (> x y) and z, just as though they were arguments to a normal function. What's different from a normal function call is that the arguments should be passed unevaluated to the macro, and only evaluated where they're used inside the macro. In the parlance of programming language design, we want OR to act like a CALL-BY-NAME PROCEDURE. We want to package up the meaning of the argument expressions in the environment of call, but let the procedure IF evaluate them any number of times. One way of achieving such a result by hand would be to create closures that capture the meaning of the argument expressions, and pass those as argument values, e.g., replace (or z (> x y)) with (or (lambda () z) (lambda () (> x y)) to ensure that the meanings of the variables would not change inside the macro---they would be closed in the environment of call. We would also have to ensure that the resulting zero-argument closures (called "thunks") were called inside the macro code to get the resulting values, rather than just using the arguments directly. For this straightforward kind of macro, then, the advantage of macros over call-by-name procedures is that they are INLINED. The macro body itself is substituted into the macro user's code, rather than doing a call to a procedure at runtime. The uses of the argument are also inlined, rather than requiring runtime procedure calls to the thunks to get the values of the expressions that they package up. So, in cases like this, we can see a macro as an optimized form of call-by-name procedures, where we make the macro "procedure" second class for efficiency---we can inline the procedure itself, and the argument expressions as well. The job of a lexically-scoped syntactic extension facility (such as hygeinic macroexpansion) is just to preserve the lexically-scoped semantics of call-by-name procedures. A HARD CASE: USER-DEFINED BINDING CONSTRUCTS The problem with the above view is that not all uses of macros are really the equivalent of call-by-name procedures. It is common to write macros that intentionally create new binding environments, and intentionally evaluate their arguments in the new environment, rather than the environment where the macro is called. The most common example of this is looping constructs such as FOR, which create control variables which must be accessible inside the loop, e.g., (for (i 0 9) (set! total (+ total (vector-ref foo i)))) in this loop, which sums the elements of the first 10 elements of the vector foo, when i is used as an index, it must refer to the loop variable, not the binding of i in some outside environment. When we see how the loop is written as a macro, it is apparent what the programmer intends, yet treating FOR as a call-by-name procedure will fix the meaning of i at the point of call, before it is bound inside the macro. (define-syntax (for (?var ?initval ?endval) ?body) (let loop ((?var ?initval)) (if (<= ?var ?endval) (begin ?body (loop (+ var 1)))))) Actually, we've got two complications here: the simple one is that the syntax of the for loop is not simply one of having a pair of arguments---we want to have the first argument have a particular structure, and we want the macro facility to destructure it into three variables: the loop variable name, the initial value expression, and the end value expression. This is actually fairly straightforward to do, so we'll ignore that part: just pretend that we pass 4 arguments to a FOR loop, and the first 3 happen to be wrapped up in a list. (Here we've used macro argument variable names that begin with a question mark for clarity---that's just a convention to make things clearer, not anything enforced by a macro facility.) (Notice that in the above example, we're translating a for loop into a named let; named LET is Scheme's general-purpose built-in iteration construct which allows binding loop variables, and iterating by tail-calling a hidden procedure whose name is the name used in the let. In this case, the name of the procedure is "loop", and we iterate by tail-calling this procedure.) But back to the hard part. When we see the macro, we can tell that the argument ?var (the loop variable) from the call site is INTENTIONALLY being rebound by the let---it's no accident of naming, because the pattern variable ?var is explicitly being used in a let and rebound. It's also clear that the ?body argument to the macro is supposed to be evaluated in this environment---the programmer has chosen to put it inside the named let, rather than somewhere else. To get this right, a macroexpander must be careful to note that the macro-writer rebound an argument variable AND then put another argument inside that environment. This should tip off the macroexpander that the programmer does not mean for the ?body expression to be closed in the environment of call, but instead in the new environment. Unfortunately, it's not quite that simple, either, because the macro-writer might have bound other variables inside the macro, and the body expression should NOT see those bindings. It is only the binding of ?var that should be taken from inside the macro, and any other variables in the ?body expression should still refer to whatever they refer to at the point of call, e.g., (define-syntax (for (?var ?initval ?endval) (letrec ((loop (lambda (?var) (if (<= ?var ?endval) (begin ?body (loop (+ var 1))))))) (loop ?initval))) (Here, instead of using named LET, we've hand-coded a LETREC and LAMBDA that let us achieve iteration by tail-calling; named LET is just syntactic sugar for this kind of construct, and might itself be implemented as a macro that expands into something like this.) Here, the letrec introduces a binding of the variable "loop", so that its value---a tail-recursive procedure---can be called by name. (It is called once from the body of the letrec to begin the first iteration, and conditionally tail-calls itself for subsequent iterations.) If there is an occurrence of the variable name "loop" in the body of a for loop, we do not want it to capture this name. So what we want is for the body expression to be evaluated in the environment of call, except for those symbols which have been intentionally rebound inside the macro (and had the expression substituted in their scope). Modern "hygeinic" macroexpansion systems make this come out right. --- HIGH-LEVEL vs. LOW-LEVEL macros Macro facilities can be high-level, meaning that the macrowriter basically just specifies a template that the macroexpander fills in with the arguments to the macro, or they may be low-level, meaning that the macro writer supplies a procedure which may perform arbitrary computations to rewrite macro expressions. HIGH-LEVEL MACROS, PATTERN MATCHING, ETC. The macros we have discussed so far depend on a particular, simple form of PATTERN MATCHING. When the interpreter or compiler encounters an expression of the form ( ...), it dispatches to the macroexpander to rewrite the expression before interpreting or compiling it. If the full power of low-level macros is not needed, it is generally preferable to use a high-level macro facility; this avoids the tedium of writing argument destructuring and template-filling by hand. Some high-level macro systems (like the optional Scheme high level macro system in the appendix to the R4RS) provide fancier pattern matching than just recognizing expressions starting with the name of a macro. With Scheme macros, you can specify several different patterns that will be recognized and get different rewritings. So, for example, you might write an OR macro that works with zero, one, or two arguments by specifying each of those three patterns and, for each one, a template to fill in when rewriting patterns of that form. (define-syntax or (syntax-rules ((or) ; if or is used with no arguments, just substitute #f) ; the false literal in place of the or expression ((or arg) ; if or is used with one argument arg) ; just use that expression in place of the or ((or arg1 arg2) (let ((temp arg1)) (if temp temp arg2))))) In effect, this kind of pattern matching system lets you easily express the fact that there are several cases; it's a lot like writing a case statement in a low-level rewriter to recognize special cases, but it's more declarative and easier to get right---you just type in the obvious syntactic construct, rather than a bunch of list manipulation expressions to detect the cases yourself. The high-level macro facility also performs argument destructuring along with the pattern matching. A high-level pattern-matching facility may also support recursion; with Scheme's high-level macros, for example, you can define patterns which match on parts of an expression, and then leave it to recursive macro expansion to rewrite the rest. This is particularly useful for writing macros that can take any number of arguments. Here we write OR so that it can take any number of arguments. (define-syntax or (syntax-rules ((or #f) ((or arg) arg) ((or arg1 ...) (let ((temp arg1)) (if temp temp (or ...)))))) For an occurrence of OR with more than one argument, the first argument will be matched in the normal way, and the remainder will be matched by the special "..." symbol. (This is the compile-time analogue of a rest list.) Each time the macro matches, an argument will be peeled off of the list and used to generate a let and an if, with a new OR (with one less argument) nested inside. Eventually the recursion in the macro rewriting process will bottom out with a match against the second pattern. LOW-LEVEL MACROS The big advantage of Lisp-style low-level macros is that you can perform code analysis during the rewriting of the macro---since you have the full power of a programming language, and the expressions are represented as data structures, you can do many things that are difficult to express in a high-level pattern-matching-and-template-filling framework. The big disadvantage of Lisp-style low-level macros is that the program representation is TOO low-level for many purposes---S expressions don't really encode scoping issues in an obvious way, and subsituting one expression into another can have very surprising consequences due to naming conflicts. A high-level lexically-scoped macro facility must represent scope information, and not just simple S-expressions, so that it can get scope right. In that way, it must do some of the job that a compiler normally does---analysis of the binding contours of the program. The strength of Lisp macros is the fact that S-expressions are just lists that correspond closely to the textual representation of expressions---but now we see that it's also the big weakness of Lisp macros. S-expressions don't represent scope information, and it's not clear that there is a simple, easy-to-understand representation that makes scoping issues clear. (For example, the optional low-level, macro system in the appendix to the R4RS represents scope information, but it is close to incomprehensible, at least when compared to the high-level pattern-matching-and-template-filling facility.) --- DEEP PHILOSOPHICAL ISSUES IN MACRO SYSTEMS Macro systems are quite controversial, in ways that go to the heart of important issues in programming language design. Macros let you change the syntax of your language, defining new control constructs. Some people believe that this is the greatest thing since sliced bread, because it allows you to invent your own little language to solve the kind of problem you care about. You can extend Scheme (or Lisp) to be a domain-specific language (i.e., one that allows you to easily represent problems and solutions for a particular kind of "subject matter"); once that's done, actually coding the application program is much easier. This view is common at MIT, which is a hotbed of programming language libertarians. They believe in providing programmers with extremely powerful languages, and relying on the programmers' judgement and taste to avoid total chaos. The opposing view is that macros are the path to perdition. Some people believe that defining new syntax for your language will only lead to massive confusion in the long run---there will be lots and lots of variants of the same programming language, and nobody will be able to read anybody else's code, or use it in their programs. People who worry a lot about this are likely to be proponents of "bondage and discipline" languages, which don't let you do dangerous things because you're too likely to mess up. Fear of macros is often highly correlated with wanting strong type systems, which don't let you make certain kinds of type errors. Both are quite reasonable, if not taken so far as to crippel programmers. The challenge is to design systems that are both safe and very expressive. An intermediate view is that macros are useful in certain situations, but should not be overused. For example, if a programmer is frequently coding things that look like while loops, it may be less error-prone to invent a while loop macro. Its functioning may be easy to explain, and the code may be more readable to others because it's easy to explain what a while loop does. The rejoinder from the bondage-and-discipline camp is that if something is useful enough that you're extending the language in that way, and having to explain the language extension, then probably there's something wrong with your programming language---you left out "while", for example. They'd say that what you should do is get "while" added as a standard part of the language, so that everyone will have it and there won't be a bunch of incompatible variants of it. There is merit to both views: if used willy-nilly, macros can cause gratuitious incompatibility between lots of dialects of a language. On the other hand, they can be extremely useful when used judiciously. In some situations, it may also be worth the trouble to have a nonportable language. Consider a company that builds financial applications. It may be worth that company's time and money to develop a new programming language for the kinds of applications it makes money from. This could be a company-wide standard language, so that code can be shared (and understood) between various programmers in the company. In such a situation, it is very nice to be able to build the domain-specific language by writing macros and procedures in a portable base language, and thus extending it to be what's needed. There is no need to write a real compiler and port it to a bunch of different systems---the same library of macros and procedures can be used with different compilers for the base language, on a bunch of different platforms. In such a situation, it may be desirable to impose controls on language extensions: some programmers may be responsible for writing the macros and functions that extend the language, and others will simply write code in the resulting language. (You don't want your lowest-skilled bozo extending the language in audacious ways---they're likely to do something that's a bad idea in the first place, and implement it in a buggy way. Then you end up with a nonstandard language dialect AND a broken implementation.) In short, both the macros-are-great and macros-are-too-dangerous views have merit. As with many issues in programming language design, the right answer can't be based on a simplistic dogma. The argument that "extending the language is too dangerous" is clearly false if taken to an extreme: after all, simply defining procedures is extending the language, and almost everyone agrees procedural abstraction is a good thing. The real question is which kinds of language extension allow the most convenient expression of what needs to be expressed, with minimal conceptual overhead: is it easier to understand, modify, and maintain programs where some of the complexity is hidden by nonstandard syntactic abstractions, or where only standard syntactic abstractions are used and more of the complexity shows up in normal code? The answer depends crucially on human psychology---how hard is it for people to understand new special forms, compared to the difficulty of understanding code that's written awkwardly because those special forms aren't available? (In my view, macros are sometimes very valuable, and sometimes just a mess. I'd rather read code that's mostly in a standard language, but the introduction of a few useful special forms can sometimes make things much cleaner and more comprehensible.) --- SOCIAL ISSUES IN LANGUAGE EXTENSION AND LANGUAGE EVOLUTION Besides the issue of whether application programmers should be using macros much, there is a separate issue of whether macros are useful to programming language designers and implementors. Here macros seem more uncontroversially useful. Given a powerful macro facility built into a language, it is possible to implement various new constructs straightforwardly as portable sets of macros and procedures. Libraries implementing different functionality can be shared among various implementors, letting them try out experimental extensions to the base programming language. This allows for quick testing and refining of language features, so that when the language designers standardize on them, they are more likely to be well-designed. The Common Lisp Object System was prototyped in this way, beginning with a piece of software called Portable Common LOOPS developed at Xerox PARC (Palo Alto Research Center). Even if you believe that macros are too powerful (and error-prone) to be used freely by most programmers, they may be very useful in the hands of language designers and implementors. Some people are now more favorably disposed to macros, since lexically scoped macro facilities have become available and eliminate many common errors in macro writing. (Paradoxically, however, others may object just as strongly because if macros are easy to use, they will be used more---in a way, it may be better for macros to be hard to use, so that casual users will be scared away from extending languages in nonstandard ways.) ---------------------------------------------------------------------- IMPLEMENTING MACROS --- IMPLEMENTING QUASIQUOTE AND COMMA QUASIQUOTE is a special form that (like quote) has a very special syntax. Part of this syntax is recognized by the reader, rather than the compiler or interpreter proper; the rest of the work is done by the compiler or interpreter. A backquote character is interpreted very specially by the Scheme (or Lisp) reader, and backquoted expressions are converted into QUASIQUOTE expressions with a normal-looking nested-prefix-expression syntax. The expression `(a b c) is actually just shorthand for (quasiquote (a b c)), and. Similarly, comma'd expressions are converted, e.g. `(a ,b ,c) is read in as (quasiquote (a (unquote b) (unquote c))). Notice that as far as the reader is concerned, these are just lists---it is up to the compiler or interpreter to process them further, and the reader just preprocesses them into lists that the compiler or interpreter can deal with. The compiler or interpreter treats QUASIQUOTE forms specially, much as QUOTE does. The QUASIQUOTE special form may be built into the compiler or interpreter, but it can be implemented as a low-level macro. Here's a simplified version of quasiquote that only deals with commas at the top level of a list, e.g., (quasiquote (foo ,bar (baz x y))) but not (quasiquote (foo ,bar (baz ,x y))) Notice that (quasiquote (foo ,bar (baz x y))) should expand to something like (list 'foo bar '(baz x y)) We'll actually generate an expression that uses CONS instead of LIST, because we want to write BACKQUOTE so that it can take any number of arguments. Our recursive backquote macro will peel one argument off the list of arguments, and either quote it or not before using it in the resulting expression that is the rewritten version of the macro. (cons 'foo (cons bar (cons '(baz x y)) '()) Notice that what we've done is generate an expression to generate a list whose components are explicitly quoted where necessary, as opposed to the original backquoted list where things are quoted by default and explicitly unquoted. And since '... is just a shorthand for (quote ...), we'll really generate an ugly expression like (cons (quote foo) (cons bar (cons (quote baz x y) '()))) written as a straighforward low-level macro: [ NEED TO DEBUG THIS... PRW ] (define-macro (quasiquote expr) (quasiquote1 expr)) (defne (quasiquote1 expr) (if (not (pair? expr)) ; if quoted expr is not a list, it's just expr ; a literal ; else we'll grab a subexpression and cons it (appropriately ; quoted or not) onto the result of recursively quasiquoting ; the remaining arguments (let ((first-subexpr (car expr)) (rest-subexprs (cdr expr))) (if (and (pair? next-subexpr) (eq? (car first-subexpr) 'unquote))) (list 'cons first-subexpr ; gen expr to eval this subexpr (quasiquote1 rest-subexprs)) (list 'cons (list 'quote first-subexpr) ; quote this subexpr (quasiquote1 rest-subexprs))))) A full implementation of quasiquote is a bit trickier; each subexpression that is not unquoted must be traversed and treated similarly to the top-level list---i.e., rather than just using the subexpressions as literals and quoting them, an equivalent expression should be constructed to create a similarly-structured list with the unquoted holes filled in. Also, a full implementation should handle UNQUOTE-SPLICING as well as UNQUOTE. --- IMPLEMENTING DEFINE-MACRO Lisp-style DEFINE-MACRO is pretty simple to implement; it requires two things: 1. When the interpreter or compiler sees a define-macro expression, it records the name of the macro, the number of arguments, and the rewriter procedure to call with those arguments. 2. When the interpreter or compiler is about to evaluate (or compile) an expression that is a list, it checks to see if the car of the list is a symbol that's the name of a macro. If so, it calls the corresponding rewriter procedure, passing it the argument expressions as arguments to the rewriter. Then the resulting rewritten expression can then be evaluated (or compiled). The first step can be accomplished in several ways. When we record the definition of a macro, one possibility is to record it in a global table. This only allows us to have a single monolithic namespace of macros. A more refined technique is to store macro definitions in the normal lexically-scoped environment, so that lookups of macros obey the normal scope rules of the language. This allows us to have local macros in the same way we have local procedures. The second step can also be achieved in different ways. The obvious way is simply to add another case to the main dispatch of the interpreter or compiler, so that macro expansion is interleaved with normal expression evaluation, corresponding directly to the nesting of macro and nonmacro expressions. Another way (as mentioned before) is to do macro expansion in a separate pass, before interpreting or compiling. For an interpreter, this has the advantage that macros can be expanded once and for all when a procedure is defined, even though the procedure may be executed many times. This saves the overhead of macroexpansion at every call to a macro. In essence, the macroexpander is a kind of compiler, which compiles to a more easily-interpreted form. Having a separate macroexpansion phase also has the benefit that the macroexpander can be separate from the compiler or interpreter---there is no need to understand or modify the code of a particular compiler or interpreter. A separate-pass macroexpander can therefore be a portable piece of code used with several different underlying language processors. The disadvantage here is that it is more difficult to write a portable separate-pass macroexpander, because the macroexpander cannot take advantage of the analyses that are done by an interpreter or compiler. To be able to expand macros in a piece of code (e.g., some procedure), the macroexpander must descend through the expressions, taking into account binding information to tell whether a particular occurrence of a macro name is actually a call to the macro, rather than (for example) a literal embedded in a quoted list. --- IMPLEMENTING LEXICALLY-SCOPED "MACROS" [Need to fill this in with a long section about using environments to implement lexically-scoped syntactic extensions, rather than macroexpansion and coloring a la "hygeinic macro expansion"]