syntax-rules (idea)

Hygienic macros, or syntax-rules macros, are an extremely cool feature of the programming language Scheme. call-with-current-continuation gets all the attention, but I think that once you start writing larger programs, a good macro system is at least as important.

Macros in the Lisp family of languages aren't quite the same thing as the dangerous and notoriously stupid #define of the C preprocessor. They're "macros" because, just like the C preprocessor, they operate by rewriting the source code before its interpretation or compilation. But, because Lisp languages have very simple concrete syntax, the rewriting can occur not at the lexeme level as in C, but at the syntactic level, that is s-expressions. This in turn allows Lisp implementors to build more sophisticated macro transformations, since more is known about the context of their application.

A simple example is the let construct of Scheme. let creates a local lexical scope with new bindings for some identifiers:

(let ((x 3) (y 2))
  (+ (* x y) (/ x y))) => 15/2

As you know if you've learned a little Scheme, a let expression is just shorthand for a lambda expression whose formal parameters are the identifiers bound, whose procedure body is the body of the let, and whose arguments are the values to be bound to the identifiers: the let above is equivalent to

((lambda (x y)
   (+ (* x y) (/ x y)))
 3 2)

Since the passage from let to lambda is a regular transformation on the expression syntax, we could write it as a macro.

Older Scheme standards (R4RS and IEEE Scheme) specified a macro system similar to that found in Common Lisp. The principle is that a macro is a lambda expression which evaluates to the list of symbols that is the syntax of the desired code. So you might write let as

(define-macro let
  (lambda (bindings . body)
    (cons
      (cons 'lambda
        (cons (map car bindings)
              body))         ;; this builds the procedure
      (map cadr bindings)))) ;; here are its arguments

This is a little confusing because, although cons and/or list are needed to build the desired syntax, they don't appear in the result; so the macro body doesn't look much like the expression it evaluates to. To get around this, we express the macro body as a template using quasiquote `, unquote ,, and unquote-splicing ,@. Quasiquote is like the ordinary quote ', except that you can "escape" out of it with unquote, which indicates that the following expression is to be evaluated. Unquote-splicing does the same thing, then deletes the outermost set of parentheses. Now our let macro looks like:

(define-macro let
  (lambda (bindings . body)
    `((lambda ,(map car bindings)
        ,@body)
      ,@(map cadr bindings))))

This is closer to expressing our intent, and indeed most Common Lisp macros are written as this kind of template.

There are still two problems with the template macro.

• The exact syntactic form of the defined expression is only expressed indirectly. The 'bindings' section of a let expression has the form

  ((var1 val1) (var2 val2) ...)
  

  but you have to puzzle that out from the fact that our macro uses the car of each binding to get the variables, and the cadr to get the bound values.

• define-macro macros aren't hygienic: if an identifier which occurs as a free variable in the arguments of an application of the macro is given a binding in the macro definition, the intended binding of that identifier (the one lexically visible at the point of use) will be shadowed by the binding appearing in the expanded macro text. This problem doesn't occur in our let example above, but suppose you wanted to write a let expression in a macro body; you would either have to reserve a group of identifiers for "variables defined in macros" (which is unsafe), or else make explicit use of a mechanism (usually called gensym) for generating fresh (previously unused) symbols.

The syntax-rules macro mechanism defined in the R5RS Scheme standard addresses both these problems and provides a flexible, transparent way to express macros with multiple syntactic patterns and recursive transformations. You specify a macro by a pattern matching, giving a list of patterns and corresponding rewrite rules. Explicit list-construction and/or recursion is avoided by patterns of the form "x ..." which denote zero or more occurrences of x. Renaming of symbols bound within the macro body happens automatically and transparently.

Our let example above would be written

(define-syntax let
  (syntax-rules ()
    ((_ ((x v) ...) e1 e2 ...) ;; the syntactic pattern
     ((lambda (x ...)          ;; the desired expansion
        e1 e2 ...)
      v ...))))

Here the underscore stands for "the keyword we're defining". We wrote "e1 e2 ..." but "((x v) ...)" because let specifies that the body must contain at least one expression, but the binding list may be empty. Notice that the macro body looks almost exactly like the definition of let you'd see in a book; this is one of the principal benefits of syntax-rules macros.

We could extend this macro to handle "named let", which gives a name to the lambda expression it creates so that it can be called within the body for recursion:

(define-syntax let
  (syntax-rules ()
    ((_ ((x v) ...) e1 e2 ...)
     ((lambda (x ...)
        e1 e2 ...)
      v ...))
    ((_ f ((x v) ...) e1 e2 ...) ;; second pattern
     (letrec ((f
               (lambda (x ...) e1 e2 ...)))
       (f v ...)))))

The two patterns don't conflict because in the first one, a list (list of bindings) appears after the defined keyword, and in the second one, a symbol appears there.

A written-out syntax-rules macro is shockingly simple, and the system is very powerful. These macro systems are the biggest reason why Scheme has no standardized record or object types; Schemers familiar with macros tend to consider "write an object system" to be a medium-easy exercise. (Of course the absence of a standard is unfortunate; see the SRFIs for more information.)

syntax-rules macros are provided by the SLIB portable Scheme library, and thus available on most Scheme implementations including SCM and Guile. MzScheme has its own implementation which slightly limits the forms you can use in a macro expansion, but works fine. For more information see R5RS, the Revised^5 Report on the Algorithmic Language Scheme, or the Schemers home page, http://www.schemers.org/ .