doc.texi

\input texinfo

@settitle JRM's Syntax-rules Primer for the Merely Eccentric

@dircategory The Algorithmic Language Scheme
@direntry
* joe-marshall-syntax-rules-primer: Joe R Marshall's Syntax-Rules Primer for the Merely Eccentric
@end direntry

@author Joe Marshall

@documentencoding UTF-8

@node Top

@ifinfo
@heading Joe R Marshall's Syntax-Rules Primer for the Merely Eccentric
@noindent
Unofficial Texinfo Format version.

@end ifinfo

@node Foreword, Very simple macros, Top

In learning to write Scheme macros, I have noticed that it is easy to find both trivial examples and extraordinarily complex examples, but there seem to be no intermediate ones.  I have discovered a few tricks in writing macros and perhaps some people will find them helpful.

The basic purpose of a macro is *syntactic* abstraction.  As functions allow you to extend the functionality of the underlying Scheme language, macros allow you to extend the syntax.  A well designed macro can greatly increase the readability of a program, but a poorly designed one can make a program completely unreadable.

Macros are also often used as a substitute for functions to improve performance.  In an ideal world this would be unnecessary, but compilers have limitations and a macro can often provide a workaround.  In these cases, the macro should be a `drop-in' replacement for the equivalent function, and the design goal is not to extend the syntax of the language but to mimic the existing syntax as much as possible.

@node Very simple macros, Debugging macros, Foreword

SYNTAX-RULES provides very powerful pattern-matching and destructuring facilities.  With very simple macros, however, most of this power is unused.  Here is an example:

@lisp
(define-syntax nth-value
  (syntax-rules ()
    ((nth-value n values-producing-form)
     (call-with-values
       (lambda () values-producing-form)
       (lambda all-values
         (list-ref all-values n))))))
@end lisp

When using functions that return multiple values, it is occasionally the case that you are interested in only one of the return values. The NTH-VALUE macro evaluates the VALUES-PRODUCING-FORM and extracts the Nth return value.

Before the macro has been evaluated, Scheme would treat a form that begins with NTH-VALUE as it would any other form:  it would look up the value of the variable NTH-VALUE in the current environment and apply it to the values produced by evaluating the arguments.

DEFINE-SYNTAX introduces a new special form to Scheme.  Forms that begin with NTH-VALUE are no longer simple procedure applications. When Scheme processes such a form, it uses the SYNTAX-RULES we provide to rewrite the form.  The resulting rewrite is then processed in place of the original form.

Forms are only rewritten if the operator position is an IDENTIFIER that has been DEFINE-SYNTAX'd.  Other uses of the identifier are not rewritten.

You cannot write an `infix' macro, nor can you write a macro in a `nested position', i.e., an expression like @code{((foo x) y z)} is always considered a procedure application.  (The subexpression @code{(foo x)} will be rewritten of course, but it will not be able to affect the processing of subexpressions @code{y} and @code{z}.)  This will be important later on.

SYNTAX-RULES is based on token-replacement.  SYNTAX-RULES defines a series of patterns and templates.  The form is matched against the pattern and the various pieces are transcribed into the template. This seems simple enough, but there is one important thing to always keep in mind.

THE SYNTAX-RULES SUBLANGUAGE IS NOT SCHEME!

This is a crucial point that is easy to forget.  In the example,

@lisp
(define-syntax nth-value
  (syntax-rules ()
    ((nth-value n values-producing-form)
     (call-with-values
       (lambda () values-producing-form)
       (lambda all-values
         (list-ref all-values n))))))
@end lisp

the pattern @code{(nth-value n values-producing-form)} looks like Scheme code
and the template

@lisp
(call-with-values
    (lambda () values-producing-form)
    (lambda all-values
        (list-ref all-values n)))
@end lisp

Really seems to be Scheme code, but when Scheme is applying the syntax-rules rewrite there is NO SEMANTIC MEANING attached to the tokens.  The meaning will be attached at a later point in the process, but not here.

One reason this is easy to forget is that in a large number of cases it doesn't make a difference, but when you write more complicated rules you may find unexpected expansions.  Keeping in mind that syntax-rules only manipulates patterns and templates will help avoid confusion.

This example makes good use of patterns and templates.  Consider the form @code{(nth-value 1 (let ((q (get-number))) (quotient/remainder q d)))} During the expansion of NTH-VALUE, the *entire* subform @code{(let ((q (get-number))) (quotient/remainder q d))} is bound to VALUES-PRODUCING-FORM and transcribed into the template at @code{(lambda () values-producing-form)} The example would not work if VALUES-PRODUCING-FORM could only be bound to a symbol or number.

A pattern consists of a symbol, a constant, a list (proper or improper) or vector of more patterns, or the special token "..."  (A series of three consecutive dots in this paper will *always* mean the literal token "..." and @b{never} be used for any other reason.)  It is not allowed to use the same symbol twice in a pattern. Since the pattern is matched against the form, and since the form @b{always} starts with the defined keyword, it does not participate in the match.

You may reserve some symbols as `literals' by placing them in the list that is the first argument to syntax-rules.  Essentially, they will be treated as if they were constants but there is some trickiness that ensures that users of the macro can still use those names as variables.  The trickiness `does the right thing' so I won't go into details.

You may find macros written using the token "_" rather than repeating the name of the macro:

@lisp
(define-syntax nth-value
    (syntax-rules ()
    ((_ n values-producing-form)
        (call-with-values
        (lambda () values-producing-form)
        (lambda all-values
            (list-ref all-values n))))))
@end lisp

I personally find this to be confusing and would rather duplicate the
macro name.

Here are the rules for pattern matching:

@itemize @minus
@item
A constant pattern will only match against an EQUAL? constant.
    We'll exploit this later on.
@item
A symbol that is one of the `literals' can only match against the exact same symbol in the form, and then only if the macro user hasn't shadowed it.
@item
A symbol that is *not* one of the literals can match against *any* complete form.  (Forgetting this can lead to surprising bugs.)

@item
A proper list of patterns can only match against a list form of the same length and only if the subpatterns match.

@item
An improper list of patterns can only match against a list form of the same or greater length and only if the subpatterns match.  The `dotted tail' of the pattern will be matched against the remaining elements of the form.  It rarely makes sense to use anything but a symbol in the dotted tail of the pattern.

@item
The ... token is special and will be discussed a bit later.
@end itemize

@node Debugging macros, N-ary macros, Very simple macros

As macros get more complicated, they become trickier to debug.  Most Scheme systems have a mechanism by which you can invoke the macro expansion system on a piece of list structure and get back the expanded form.  In MzScheme you could do this:

@lisp
(syntax-object->datum
    (expand '(nth-value 1 (let ((q (get-number)))
                            (quotient/remainder q d)))))
@end lisp

In MIT Scheme,

@lisp
(unsyntax (syntax '(nth-value 1 (let ((q (get-number)))
                                    (quotient/remainder q d)))
                    (nearest-repl/environment)))
@end lisp

Be prepared for some interesting output --- you may not realize how many forms are really macros and how much code is produced.  The macro system may recognize and optimize certain patterns of function usage as well.  It would not be unusual to see @code{(caddr x)} expand into @code{(car (cdr (cdr x)))} or into @code{(%general-car-cdr 6 x)}.

Be prepared, too, for some inexplicable constructs.  Some syntax objects may refer to bindings that are only lexically visible from within the expander.  Syntax objects may contain information that is lost when they are converted back into list structure.  You may encounter apparently illegal expansions like this:

@lisp
 (lambda (temp temp temp) (set! a temp) (set! b temp) (set! c temp))
@end lisp

There are three internal syntax objects that represent the three different parameters to the lambda expression, and each assignment referred to a unique one, but each individual syntax object had the same symbolic name, so their unique identity was lost when they were turned back into list structure.

Debugging trick

One very easy debugging trick is to wrap the template with a quote:

@lisp
(define-syntax nth-value
    (syntax-rules ()
    ((_ n values-producing-form)
        '(call-with-values                    ;; @r{Note the quote!}
        (lambda () values-producing-form)
        (lambda all-values
            (list-ref all-values n))))))
@end lisp

Now the macro returns the filled-in template as a quoted list:

@lisp
(nth-value (compute-n) (compute-values))
=> (call-with-values (lambda () (compute-values))
     (lambda all-values (list-ref all-values (compute-n))))
@end lisp

Sometimes it is difficult to understand why a pattern didn't match something you thought it should or why it did match something it shouldn't.  It is easy to write a pattern testing macro:

@lisp
(define-syntax test-pattern
  (syntax-rules ()
    ((test-pattern one two) "match 1")
    ((test-pattern one two three) "match 2")
    ((test-pattern . default) "fail")))
@end lisp

Debugging trick
A second trick is to write a debugging template:

@lisp
(define-syntax nth-value
   (syntax-rules ()
     ((_ n values-producing-form)
      '("Debugging template for nth-value"
        "n is" n
        "values-producing-form is" values-producing-form))))
@end lisp

@node N-ary macros, Syntax errors, Debugging macros

By using a dotted tail in the pattern we can write macros that take an arbitrary number of arguments.

@lisp
(define-syntax when
  (syntax-rules ()
    ((when condition . body) (if condition (begin . body) #f))))
@end lisp

An example usage is

@lisp
    (when (negative? x)
       (newline)
       (display "Bad number:  negative."))
@end lisp

The pattern matches as follows:

@example
   condition = (negative? x)

   body = ((newline) (display "Bad number:  negative."))
@end example

Since the pattern variable `body' is in the dotted tail position, it is matched against the list of remaining elements in the form.  This can lead to unusual errors.  Suppose I had written the macro this way:

@lisp
(define-syntax when
  (syntax-rules ()
    ((when condition . body) (if condition (begin body) #f))))
@end lisp

The pattern is matched against the list of remaining arguments, so in the template it will expand to a list:

@lisp
(when (negative? x)
    (newline)
    (display "Bad number:  negative."))
@end lisp

expands to

@lisp
(if (negative? x)
    (begin ((newline) (display "Bad number:  negative.")))
    #f)
@end lisp

But this @b{almost} works.  The consequence of the condition is evaluated as if it were a function call.  The `function' is the return value of the call to newline and the `argument' the return value from display.  Since the rules for evaluation are to evaluate the subforms and then apply the resulting procedure to the resulting arguments, this may actually print a newline and display the string "Bad number:  negative." before raising an error.  One could easily be fooled into thinking that the WHEN form succesfully ran to completion and it was the code *subsequent* to the WHEN that raised the error.

The original code had this in the template: @code{(begin . body)}

When the template is filled in, the body is placed in `the dotted tail'.  Since the body is a list of forms, the effect is as if you had used CONS rather than LIST to create the resultant form. Unfortunately, this trick does not generalize; you can only prefix things in this manner.

Macro `rest args' get bound to a list of forms, so remember to `unlist' them at some point.

There is another bug in the original form:

@lisp
(define-syntax when
  (syntax-rules ()
    ((when condition . body) (if condition (begin . body) #f))))
(when (< x 5))
@end lisp

expands into

@lisp
  (if (< x 5) (begin) #f)
@end lisp

Recall that pattern variables match anything, including the empty list.  The pattern variable BODY is bound to the empty list.  When the template form @code{(begin . body)} is filled in, the token BEGIN is consed to the empty list resulting in an illegal (BEGIN) form.

Since @code{(when (< x 5))} is unusual itself, one solution is to modify the macro like this:

@lisp
(define-syntax when
  (syntax-rules ()
    ((when condition form . forms)
    (if condition (begin form . forms) #f))))
@end lisp

Now the pattern will match only if the WHEN expression has at least one consequent form and the resulting BEGIN subform is guaranteed to contain at least one form.

This sort of macro --- one that takes an arbitrary number of subforms and evaluates them in an `implicit begin' --- is extremely common.  It is valuable to know this macro idiom:

Implicit Begin idiom

Use this idiom for a macro that allows an arbitrary number of subforms and processes them sequentially (possibly returning the value of the last subform).

The pattern should end in "FORM . FORMS)" to ensure a minimum of one subform.

The template has either @code{(begin form . forms)} or uses the implicit begin of another special form, e.g. @code{(lambda () form . forms)}


A strange and subtle bug

This section describes a bug in the syntax-rules expander for MzScheme v207.  A fix has been made to the sources, so versions later than this ought to work.  You can skip this section (about 1 page) if you wish.

Suppose you are a former INTERCAL hacker and you truly miss the language.  You wish to write a macro PLEASE that simply removes itself from the expansion:

@lisp
   (please display "foo")  =>  (display "foo")
@end lisp

Here is an attempt:

@lisp
   (define-syntax please
     (syntax-rules ()
       ((please . forms) forms)))
@end lisp

This works on some Scheme systems, but not on others and the reason is quite subtle.  In Scheme, function application is indicated syntactically by a list consisting of a function and zero or more arguments.  Above macro, although it returns such a list, creates that list as part of the pattern matching process.  When a macro is expanded careful attention is paid to ensure that subforms from the point of use continue to refer to the lexical environment at that point while subforms that are introduced by the template continue to refer to the lexical environment of the macro definition.  The list that is returned from the PLEASE macro, however, is a subform that was not created at either the macro use point *or* at the macro definition point, but rather in the environment of the pattern matcher.  In MzScheme, that environment does not have a syntactic mapping to interpret a list as a function call, so the following error results: @code {"compile: bad syntax; function application is not allowed, because no #%app syntax transformer is bound in: (display 33)"}

The fix is trivial:

@lisp
(define-syntax please
    (syntax-rules ()
    ((please function . arguments) (function . arguments))))
@end lisp

The resulting expansion is now a list constructed within the template of the macro rather than one constructed by the pattern matcher.  The template environment is used and the resulting list is therefore interpreted as a function call.

Again, this is an extremely subtle point, but it is easy to remember this rule of thumb:

Don't use macro `rest' arguments as an implicit function call. Use a template with an explicit (function . arguments) element.

END OF STRANGE AND SUBTLE BUG SECTION

Syntax rules allows for an arbitrary number of pattern/template pairs. When a form is to be rewritten, a match is attempted against the first pattern.  If the pattern cannot be matched, the next pattern is examined.  The template associated with the first matching pattern is the one used for the rewrite.  If no pattern matches, an error is raised.  We will exploit this heavily.

@node Syntax errors, `Accidental' matching, N-ary macros

The macro system will raise an error if no pattern matches the form, but it will become useful to us to write patterns that explicitly reject a form if the pattern *does* match.  This is easily accomplished by making the template for a pattern expand into poorly formed code, but the resulting error message is rather unhelpful:

@lisp
 (define-syntax prohibit-one-arg
   (syntax-rules ()
     ((prohibit-one-arg function argument) (if)) ;; @r{bogus expansion}
     ((prohibit-one-arg function . arguments)
      (function . arguments))))

 (prohibit-one-arg + 2 3) => 5

 (prohibit-one-arg display 'foo)
  @r{if: bad syntax (has 0 parts after keyword) in: (if)}
@end lisp

To make a more helpful error message, and to indicate in the macro definition that the bogus expansion is intentional, we'll define a macro designed to raise a syntax error.  (There is, no doubt a procedural way of doing this, but we wish to raise this error during macro expansion and the pattern language provides no way to do this directly.  A more complicated macro system could be used, but this is nice, easy, and portable.)

@lisp
 (define-syntax syntax-error
   (syntax-rules ()
     ((syntax-error) (syntax-error "Bad use of syntax error!"))))
@end lisp

We can now write macros that expand into `calls' to syntax error.  If the call contains any arguments, the pattern will not match and an error will be raised.  Most scheme macro systems display the form that failed to match, so we can put our debugging messages there.

@lisp
(define-syntax prohibit-one-arg
  (syntax-rules ()
    ((prohibit-one-arg function argument)
    (syntax-error
    "Prohibit-one-arg cannot be used with one argument."
    function argument))
    ((prohibit-one-arg function . arguments)
    (function . arguments))))

(prohibit-one-arg display 3)
=> syntax-error: bad syntax in: (syntax-error "Prohibit-one-arg cannot
be used with one argument." display 3)
@end lisp

Write a syntax-error macro.

Write `rejection' patterns by expanding into a call to syntax-error.

@node `Accidental' matching, Recursive expansion, Syntax errors

The pattern roughly resembles what it matches, but this can be a source of confusion.  A pattern like this:

@lisp
   (my-named-let name (binding . more-bindings) . body)
@end lisp

will match this form:

@lisp
   (my-named-let ((x 22)
                  (y "computing square root"))
      (display y)
      (display (sqrt x)))
@end lisp

as follows:

@example
   name  =   ((x 22) (y "computing square root"))

   binding = display
   more-bindings = (y)

   body = ((display (sqrt x)))
@end example

Nested list structure in the pattern will match similar nested list structure in the form, but symbols in the pattern will match *anything*.

In this example we want to prohibit matching NAME with a list.  We do this by `guarding' the intended pattern with patterns that should not be allowed.

@lisp
(define-syntax my-named-let
  (syntax-rules ()

    ((my-named-let () . ignore)
     (syntax-error "NAME must not be the empty list."))

    ((my-named-let (car . cdr) . ignore)
     (syntax-error "NAME must be a symbol." (car . cdr)))

    ((my-named-let name bindings form . forms) ;; implicit begin
     (let name bindings form . forms))))
@end lisp

Protect against accidental pattern matching by writing guard patterns that match the bad syntax.

@node Recursive expansion, List Recursion Idiom, `Accidental' matching

Our syntax-error macro can expand into a syntax-error form.  If the result of a macro expansion is itself a macro form, that resulting macro form will be expanded.  This process continues until either the resulting form is not a macro call or the resulting form fails to match a pattern.  The syntax-error macro is designed to fail to match anything but a no-argument call.  A no-argument call to syntax-error expands into a one-argument call to syntax-error which fails to match.

The template for a macro can expand to a form that embeds a call to the same macro within it.  The embedded code will be expanded normally if the surrounding code treats it as a normal form.  The embedded call will normally contain fewer forms than the original call so that the expansion eventually terminates with a trivial expansion.

Note, however, that the recursive macro will not be expanded unless the intermediate code uses it as a macro call.  This is why the debugging trick of quoting the template works: the macro form is expanded to a quote form.  The quote form just treats its argument as data so no further expansion is done.

Recursive expansion always produces a nested result. This is used to good effect in this example:

@lisp
 (define-syntax bind-variables
   (syntax-rules ()
     ((bind-variables () form . forms)
      (begin form . forms))

     ((bind-variables ((variable value0 value1 . more) . more-bindings) form . forms)
      (syntax-error "bind-variables illegal binding" (variable value0 value1 . more)))

     ((bind-variables ((variable value) . more-bindings) form . forms)
      (let ((variable value)) (bind-variables more-bindings form . forms)))

     ((bind-variables ((variable) . more-bindings) form . forms)
      (let ((variable #f)) (bind-variables more-bindings form . forms)))

     ((bind-variables (variable . more-bindings) form . forms)
      (let ((variable #f)) (bind-variables more-bindings form . forms)))

     ((bind-variables bindings form . forms)
      (syntax-error "Bindings must be a list." bindings))))
@end lisp

@code{BIND-VARIABLES} is much like @code{LET*}, but you are allowed to omit the
value in the binding list.  If you omit the value, the variable will
be bound to #F.  You can also omit the parenthesis around the variable
name.

@lisp
(bind-variables ((a 1)        ;; @r{a will be 1}
                 (b)          ;; @r{b will be #F}
                 c            ;; @r{so will c}
                 (d (+ a 3))) ;; @r{a is visible in this scope.}
    (list a b c d))
@end lisp

When bind-variables is processed, its immediate expansion is this:

@lisp
  (let ((a 1))
    (bind-variables ((b)
                     c
                     (d (+ a 3)))
      (list a b c d)))
@end lisp

The LET form is now processed and as part of that processing the body
of the LET will be expanded.

@lisp
(bind-variables ((b)
                    c
                    (d (+ a 3)))
    (list a b c d))
@end lisp

This expands into another LET form:

@lisp
(let ((b #f))
    (bind-variables (c
                    (d (+ a 3)))
    (list a b c d)))
@end lisp

The process terminates when the binding list is the empty list.  At this point each level of expansion is placed back in its surrounding context to yield this nested structure:

@lisp
(let ((a 1))
  (let ((b #f))
    (let ((c #f))
      (let ((d (+ a 3)))
        (list a b c d)))))
@end lisp

There are several things to note here:

@enumerate

@item
The macro uses the implicit begin idiom.

@item
There is a `guard' patterns to match bindings with more than one value form.

@item
In each expansion, the first binding will be removed.  The remaining bindings appear in the binding position at the recursive call, thus the macro is inductive over the list of bindings.

@item
There is a base case of the induction that matches the empty binding list.

@item
On each iteration a match is attempted on first binding against these patterns in order:

@itemize @minus

@item
@code{(variable value0 value1 . more)} a list of more than two elements

@item
@code{(variable value)} a list of exactly two elements

@item
@code{(variable)} a list of one element

@item
variable  not a list

@end itemize

@end enumerate

This order is used because the last pattern will match anything and would prevent the previous matches from being matched.

This macro idiom is also extremely common.

@node List Recursion Idiom, Ellipses, Recursive expansion

This idiom is used to recursively process a list of macro subforms.

The macro has a parenthesised list of items in a fixed position.

This list may be empty (), but it may not be omitted.

A pattern that matches the empty list at that position preceeds the other matches. The template for this pattern does not include another use of this macro.

One or more patterns that have dotted tails in the list position are present.  The patterns are ordered from most-specific to most-general to ensure that the later matches do not `shadow' the earlier ones.  The associated templates are either syntax-errors or contain another use of this macro.  The list position in the recursive call will contain the dotted tail component.

A minimal list recursion looks like this:

@lisp
 (define-syntax mli
   (syntax-rules ()

     ((mli ()) (base-case))

     ((mli (item . remaining)) (f item (mli remaining)))

     ((mli non-list) (syntax-error "not a list")))))
@end lisp

Note that the recursive call in the second clause uses the pattern variable REMAINING and that it is NOT dotted.  Each recursive call therefore contains a shorter list of forms at the same point.

At this point, things are starting to get complicated.  We can no longer look upon macros as `simple rewrites'.  We are starting to write macros whose purpose is to control the actions of the macro processing engine.  We will be writing macros whose purpose is not to produce code but rather to perform computation.

A macro is a compiler.  It takes source code written in one language, i.e. Scheme with some syntactic extension, and it generates object code written in another language, i.e. Scheme *without* that syntactic extension.  The language in which we will be writing these compilers is NOT Scheme.  It is the pattern and template language of syntax-rules.

A compiler consists of three basic phases:  a parser that reads the source language, a transformation and translation process that maps the source language semantics into constructs in the target language, and a generator that turns the resulting target constructs into code. Our macros will have these three identifiable parts.  The parser phase will use pattern language to extract code fragments from the source code. The translator will operate on these code fragments and use them to construct and manipulate Scheme code fragments.  The generator phase will assemble the resulting Scheme fragments of Scheme code with a template that will be the final result.

The pattern and template language of syntax-rules is an unusual implementation language.  The pattern-driven rule model makes it easy to write powerful parsers.  The template-driven output model makes code generation a snap.  The automatic hygiene tracks the context of the code fragments and essentially allows us to manipulate the intermediate code fragments as elements in an abstract syntax tree. There is just one problem:  the model of computation is non-procedural.  Simple standard programming abstractions such as subroutines, named variables, structured data, and conditionals are not only different from Scheme, they don't exist in a recognizable form!

But if we look carefully, we will find our familiar programming abstractions haven't disappeared at all --- they have been destructured, taken apart, and re-formed into strange shapes.  We will be writing some strange-looking code.  This code will be written in the form of a macro transformer, but it will not be a macro in the traditional sense.


When a macro is expanded the original form is rewritten into a new form.  If the result of macro expansion is a new macro form, the expander then expands that result.  So if the macro expands into another call to itself, we have written a tail-recursive loop.  We made a minimal use of this above with the syntax-error macro, but now we will be doing this as a standard practice.

We encountered the list recursion idiom above.  We can create an analagous list iteration:

@lisp
 (define-syntax bind-variables1
   (syntax-rules ()
     ((bind-variables1 () form . forms)
      (begin form . forms))

     ((bind-variables1 ((variable value0 value1 . more) . more-bindings) form . forms)
      (syntax-error "bind-variables illegal binding" (variable value0 value1 . more)))

     ((bind-variables1 ((variable value) . more-bindings) form . forms)
      (bind-variables1 more-bindings (let ((variable value)) form . forms)))

     ((bind-variables1 ((variable) . more-bindings) form . forms)
      (bind-variables1 more-bindings (let ((variable value)) form . forms)))

     ((bind-variables1 (variable . more-bindings) form . forms)
      (bind-variables1 more-bindings (let ((variable #f)) form . forms)))

     ((bind-variables1 bindings form . forms)
      (syntax-error "Bindings must be a list." bindings))))
@end lisp

Because we process the leftmost variable first, the resulting form will be nested in the reverse order from the recursive version.  We will deal with this issue later and just write the bindings list backwards for now.

@lisp
(bind-variables1 ((d (+ a 3))  ;; @r{a is visible in this scope.}
                  c            ;; @r{c will be bound to #f}
                  (b)          ;; @r{so will b}
                  (a 1))       ;; @r{a will be 1}
    (list a b c d))
@end lisp

This macro first expands into this:

@lisp
(bind-variables1 (c
                  (b)
                  (a 1))
  (let ((d (+ a 3)))
    (list a b c d)))
@end lisp

But since this form is a macro, the expander is run again.  This
second expansion results in this:

@lisp
(bind-variables1 ((b)
                  (a 1))
  (let ((c #f))
    (let ((d (+ a 3)))
      (list a b c d))))
@end lisp

The expander is run once again to produce this:

@lisp
(bind-variables1 ((a 1))
  (let ((b #f))
    (let ((c #f))
      (let ((d (+ a 3)))
        (list a b c d)))))
@end lisp

Another iteration produces this:

@lisp
(bind-variables1 ()
  (let ((a 1))
    (let ((b #f))
      (let ((c #f))
        (let ((d (+ a 3)))
          (list a b c d))))))
@end lisp

The next expansion does not contain a call to the macro:

@lisp
(begin
  (let ((a 1))
    (let ((b #f))
      (let ((c #f))
        (let ((d (+ a 3)))
          (list a b c d))))))
@end lisp

We could call this the `List Iteration Idiom', but let's take this in a completely different direction.

Notice that the template for most of the rules begins with the macro name itself in order to cause the macro expander to immediately re-expand the result.  But let's ignore the expander and pretend that  *the template form is a tail-recursive function call*.

By removing the error checking and the multiple formats for argument bindings, we can see the essence of what is going on:

@lisp
 (define-syntax bind-variables1
   (syntax-rules ()
     ((bind-variables1 () . forms)
      (begin . forms))

     ((bind-variables1 ((variable value) . more-bindings) . forms)
      (bind-variables1 more-bindings (let ((variable value)) . forms)))))
@end lisp

BIND-VARIABLES1 is tail-recursive function.  SYNTAX-RULES functions as a COND expression.  The arguments to bind-variables1 are unnamed, but by placing patterns in the appropriate positions, we can destructure the values passed into named variables.

Let us demonstrate this insight through a simple example.

We want to mimic the Common Lisp macro MULTIPLE-VALUE-SETQ.  This form takes a list of variables and form that returns multiple values.  The form is invoked and the variables are SET! to the respective return values.  A putative expansion might be this:

@lisp
 (multiple-value-set! (a b c) (generate-values))
  =>  (call-with-values (lambda () (generate-values))
        (lambda (temp-a temp-b temp-c)
          (set! a temp-a)
          (set! b temp-b)
          (set! c temp-c)))
@end lisp

For the sake of clarity, we'll start out with no error checking. Since our macros are tail-recursive, we can write separate subroutines for each part of the expansion.

First, we write the `entry-point' macro.  This macro is the one that would be exported to the user.  This macro will call the one that creates the temporaries and the necessary assignment expressions.  It passes in empty lists as the initial values for these expressions.

@lisp
(define-syntax multiple-value-set!
  (syntax-rules ()
    ((multiple-value-set! variables values-form)

     (gen-temps-and-sets
         variables
         ()  ;; initial value of temps
         ()  ;; initial value of assignments
         values-form))))
@end lisp

Assuming that gen-temps-and-sets does the right thing, we will want to emit the resulting code.  The code is obvious:
@lisp
(define-syntax emit-cwv-form
  (syntax-rules ()

    ((emit-cwv-form temps assignments values-form)
     (call-with-values (lambda () values-form)
       (lambda temps . assignments)))))
@end lisp

The temps and assignments are just pasted into the right spots.

Now we need to write the routine that generates a temporary and an assignment for each variable.  We'll again use induction on the list of variables.  When that list is empty, we'll call EMIT-CMV-FORM with the collected results.  On each iteration we'll remove one variable, generate the temporary and assignment for that variable, and collect them with the other temporaries and assignments.

@lisp
(define-syntax gen-temps-and-sets
  (syntax-rules ()

    ((gen-temps-and-sets () temps assignments values-form)
     (emit-cwv-form temps assignments values-form))

    ((gen-temps-and-sets (variable . more) temps assignments values-form)
     (gen-temps-and-sets
        more
       (temp . temps)
       ((set! variable temp) . assignments)
       values-form))))
@end lisp

Before we develop this further, though, there are some important points about this macro that should not be overlooked.

@quotation
Did I ever tell you that Mrs. McCave
Had twenty-three sons, and she named them all Dave?
-- Dr. Seuss
@end quotation

Our MULTIPLE-VALUE-SET! macro generates a temporary variable for each of the variables that will be assigned (this is in the second clause of GEN-TEMPS-AND-SETS).  Unfortunately, all the temporary variables are named `TEMP'.  We can see this if we print the expanded code:

@lisp
(call-with-values (lambda () (generate-values))
    (lambda (temp temp temp)
    (set! c temp)
    (set! b temp)
    (set! a temp)))
@end lisp

@quotation
Well, she did. And that wasn't a smart thing to do.
You see, when she wants one, and calls out "Yoo-Hoo!
Come into the house, Dave!" she doesn't get one.
All twenty-three Daves of hers come on the run!
-- Ibid
@end quotation

The importance of unique identifiers to avoid name collisions is taught at a very young age.

The funny thing is, though, the code works.  There are actually three different syntactic objects (all named temp) that will be bound by the LAMBDA form, and each SET! refers to the appropriate one.  But there are six identifiers here with the name TEMP.  Why did the macro expander decide to create three pairs of associated syntax objects rather than six individual ones or two triplets?  The answer lies in this template:

@lisp
(gen-temps-and-sets
    more
    (temp . temps)
    ((set! variable temp) . assignments)
    values-form)
@end lisp

The variable TEMP that is being prepended to the list of temps and the variable TEMP in the newly created (SET! VARIABLE TEMP) form will refer to the *same* syntactic object because they are created during the same expansion step.  It will be a *different* syntactic object than any created during any other expansion step.

Since we run the expansion step three times, one for each variable to be assigned, we get three variables named temp.  They are paired up properly because we generated all references to them at the same time.

@enumerate
@item
Introduce associated code fragments in a single expansion step.
@item
Introduce duplicated, but unassociated fragments in different expansion steps.
@end enumerate

Let's explore two variants of this program.  We will separate the genaration of the temps and the assignments into two different functions, GEN-TEMPS and GEN-SETS.

Because both GEN-TEMPS and GEN-SETS iterate over the list of variables as they operate, we modify MULTIPLE-VALUE-SET! to pass the list twice.  GEN-TEMPS will do induction over one copy, GEN-SETS will work with the other.

@lisp
(define-syntax multiple-value-set!
  (syntax-rules ()
    ((multiple-value-set! variables values-form)

     (gen-temps
         variables ;; provided for GEN-TEMPS
         ()  ;; initial value of temps
         variables ;; provided for GEN-SETS
         values-form))))
@end lisp

GEN-TEMPS does induction over the first list of variables and creates a list of temp variables.

@lisp
(define-syntax gen-temps
  (syntax-rules ()

    ((gen-temps () temps vars-for-gen-set values-form)
     (gen-sets temps
               vars-for-gen-set
               () ;; @r{initial set of assignments}
               values-form))

    ((gen-temps (variable . more) temps vars-for-gen-set values-form)
     (gen-temps
       more
       (temp . temps)
       vars-for-gen-set
       values-form))))
@end lisp

GEN-SETS also does induction over the list of variables and creates a list of assignment forms.

@lisp
(define-syntax gen-sets
  (syntax-rules ()

    ((gen-sets temps () assignments values-form)
     (emit-cwv-form temps assignments values-form))

    ((gen-sets temps (variable . more) assignments values-form)
     (gen-sets
       temps
       more
       ((set! variable temp) . assignments)
       values-form))))
@end lisp

Although the result of expansion looks similar, this version of the macro does not work.  The name TEMP that is generated in the GEN-TEMPS expansion is different from the name TEMP generated in the GEN-SETS expansion.  The expansion will contain six unrelated identifiers (all named TEMP).

But we can fix this.  Notice that GEN-SETS carries around the list of temps generated by GEN-TEMPS.  Instead of generating a new variable named TEMP, we can extract the previously generated TEMP from the list and use that.

First, we arrange for GEN-TEMPS to pass the temps twice.  We need to destructure one of the lists to do the iteration, but we need the whole list for the final expansion.

@lisp
(define-syntax gen-temps
  (syntax-rules ()

    ((gen-temps () temps vars-for-gen-set values-form)
     (gen-sets temps
               temps ;; @r{another copy for gen-sets}
               vars-for-gen-set
               () ;; @r{initial set of assignments}
               values-form))

    ((gen-temps (variable . more) temps vars-for-gen-set values-form)
     (gen-temps
       more
       (temp . temps)
       vars-for-gen-set
       values-form))))
@end lisp

GEN-SETS again uses list induction, but on two parallel lists rather than a single list (the lists are the same length).  Each time around the loop we bind TEMP to a previously generated temporary.

@lisp
(define-syntax gen-sets
  (syntax-rules ()

    ((gen-sets temps () () assignments values-form)
     (emit-cwv-form temps assignments values-form))

    ((gen-sets temps (temp . more-temps) (variable . more-vars) assignments values-form)
     (gen-sets
       temps
       more-temps
       more-vars
       ((set! variable temp) . assignments)
       values-form))))
@end lisp

Now we aren't generating new temps in GEN-SETS, we are re-using the
old ones generated by GEN-SETS.

@node Ellipses, , List Recursion Idiom

Ellipses are not really that difficult to understand, but they have three serious problems that make them seem mysterious when you first encounter them.

@itemize @minus

@item
The ... operator is very strange looking.  It isn't a `normal' token and it has a prior established meaning in the English language that is somewhat at odds with what it does.  Macros that use ellipses look like `sound bites' from movie reviews.

@item
The ... token is a reserved word in the macro language.  Unlike all other tokens, it cannot be re-bound or quoted.  In the macro language, ... acts like a syntactic mark of the same nature as a double-quote, dotted tail, or parenthesis.  (It is nonsensical to try to use an open-parenthesis as a variable name!  The same is true for ... in the macro language.)  But in standard scheme, ... is an indetifier token and could conceivably be used as a variable.

@item
Out of every form in Scheme, the ... operator is the *only* one that is POSTFIX!  The ... operator modifies how the PREVIOUS form is interpreted by the macro language.  This one exception is probably responsible for most of the confusion.  (Of course, if you were to use ... as a function in normal scheme, it is a prefix operator.)

@end itemize

In a macro pattern, ellipses can only appear as the last token in a LIST or VECTOR pattern.  There must be a pattern immediately before it (because it is a postfix operator), so ellipses cannot appear right after an unmatched open-paren.  In a pattern, the ellipses cause the pattern immediately before it to be able to match repeated occurrances of itself in the tail of the enclosing list or vector pattern.  Here is an example.

Suppose our pattern were this: @code{(foo var #t ((a . b) c) ...)}

This pattern would match: @code{(foo (* tax x) #t ((moe larry curly) stooges))} because var matches anything, @var{#t} matches @var{#t}, and one occurrance of @code{((a . b) c)} would match . a would match moe, b would match the tail @code{(larry curly)} and c would match stooges.

This pattern would match:

@lisp
(foo 11 #t ((moe larry curly) stooges)
            ((carthago delendum est) cato)
            ((egad) (mild oath)))
@end lisp

because var matches anything, #t matches #t, and three occurrances of the @code{((a . b) c)} pattern would each match the three remaining elements.  Note that the third element matches with a being egad, b being empty and the pattern c matching the entire list @code{(mild oath)}.

This pattern would *not* match:

@lisp
(foo 11 #t ((moe larry curly) stooges)
            ((carthago delendum est) cato)
            ((egad) mild oath))
@end lisp

The reason is that the final element @code{((egad) mild oath)} cannot match @code{((a . b) c)} because it the pattern is a list of two elements and we supplied a list of three elements.

This pattern *would* match: @code{(foo #f #t)} because var matches anything, #t matches #t, and zero occurrances of the @code{((a . b) c)} pattern would match the empty tail.

@enumerate
@item
Ellipses must be last in a list or vector pattern.  The list or vector must have at least one initial pattern.

@item
Ellipses is a postfix operator that operates on the pattern before it.

@item
Ellipses allows the containing list or vector pattern to match provided that the head elements of the pattern match the head elements of the list or vector up to (but not including) the pattern before the ellipses, *and* zero or more copies of that pattern match *each and all* of the remaining elements.

@item
Remember that zero occurrance of the pattern can `match'.

When a pattern has an ellipses, the pattern variables within the clause prior to the ellipses work differently from normal.  When you use one of these pattern variables in the template, it must be suffixed with an ellipses, or it must be contained in a template subform that is suffixed with an ellipses.  In the template, anything suffixed with an ellipses will be repeated as many times as the enclosed pattern variables matched.
@end enumerate

Suppose our pattern is @code{(foo var #t ((a . b) c) ...)} and it is matched against

@lisp
   (foo 11 #t ((moe larry curly) stooges)
              ((carthago delendum est) cato)
              ((egad) (mild oath)))
@end lisp

These are example templates and the forms produced:

@lisp
 ((a ...) (b ...) var (c ...))

=> ((moe carthago egad)
    ((larry curly) (delendum est) ())
    11
    (stooges cato (mild-oath)))

  ((a b c) ... var)

=>  ((moe (larry curly) stooges)
     (carthago (delendum est) cato)
     (egad () (mild oath)) 11)

((c . b) ... a ...)

=>  ((stooges larry curly)
     (cato delendum est)
     ((mild oath))
     moe carthago egad)

 (let ((c 'b) ...) (a 'x var c) ...)

=>  (let ((stooges '(larry curly))
          (cato '(delendum est))
          ((mild oath) '()))

       (moe 'x 11 stooges)
       (carthago 'x 11 cato)
       (egad 'x 11 (mild-oath)))
@end lisp

There can be several unrelated ellipses forms in the pattern: The different subpatterns patterns need not have the same length in order for the entire pattern to match.

@code{(foo (pattern1 ...) ((pattern2) ...) ((pattern3) ...))} will match against @code{(foo (a b) ((b) (c) (d) (e)) ())}.

When a template is replicated, it is replicated as many times as the embedded pattern variable matched, so if you use variables from different subpatterns, the subpatterns must be the same length.  (The pattern matching will work if the subpatterns are different lengths, but the template transcription will break if a subpattern uses two different lengths.)

You may have come to the conclusion that ellipses are too complicated to think about, and in the general case they can be very complex, but there are a couple of very common usage patterns that are easy to understand.  Let's demonstrate an example.

We wish to write a macro TRACE-SUBFORMS that given an expression rewrites it so that some information is printed when each subform is evaluated.  Let's start by using our list induction pattern.

@lisp
(define-syntax trace-subforms
  (syntax-rules ()
    ((trace-subforms traced-form)
     (trace-expand traced-form
                   ())))) ;; initialize the traced element list

(define-syntax trace-expand
  (syntax-rules ()

    ;; when no more subforms, emit the traced code.
    ((trace-expand () traced)
     (trace-emit . traced))

    ;; Otherwise, wrap some code around the form and CONS it to
    ;; the traced forms list.
    ((trace-expand (form . more-forms) traced)
     (trace-expand more-forms
       ((begin (newline)
               (display "Evaluating ")
               (display 'form)
               (flush-output)
               (let ((result form))
                 (display " => ")
                 (display result)
                 (flush-output)
                 result))
         . traced)))))

(define-syntax trace-emit
  (syntax-rules ()
    ((trace-emit function . arguments)
     (begin (newline)
            (let ((f function)
                  (a (list . arguments)))
            (newline)
            (display "Now applying function.")
            (flush-output)
            (apply f a))))))
@end lisp

Now let's try it:
@lisp
(trace-subforms (+ 2 3))
@end lisp

@example
Evaluating 3 => 3
Evaluating 2 => 2
Evaluating + => #<primitive:+>
Now applying function.
apply: expects type <procedure> as 1st argument,
    given: 3; other arguments were: (2 #<primitive:+>)
@end example

It evaluated the subforms backwards and tried to use the final argument as the function.  The error, of course, is that as we worked from left to right on the list of subforms, the results were prepended to the list so they ended up in reverse order.  We *could* interpose a list-reversing macro between trace-expand and trace-emit, but we can use ellipses here to good effect:

@lisp
(define-syntax trace-subforms
  (syntax-rules ()

    ((trace-subforms (form ...))
     (trace-emit (begin
                   (newline)
                   (display "Evaluating ")
                   (display 'form)
                   (flush-output)
                   (let ((result form))
                     (display " => ")
                     (display result)
                     (flush-output)
                     result)) ...))))
@end lisp

The tracing code will be replicated as many times FORM is matched so the subforms will be handed to trace-emit in the correct order.  The output is now

@example
Evaluating + => #<primitive:+>
Evaluating 2 => 2
Evaluating 3 => 3
Now applying function.5
@end example

You may have noticed in our MULTIPLE-VALUE-SET! form that the assignments were happening in reverse order of the variable list. This didn't really matter because performing one assignment didn'taffect the others.  But let's print something out before each assignment and let's make the assignments happen in the correct order. We'll rewrite our MULTIPLE-VALUE-SET! macro using ellipses.

@lisp
(define-syntax multiple-value-set!
  (syntax-rules ()
    ((multiple-value-set! variables values-form)

     (gen-temps-and-sets
         variables
         values-form))))

(define-syntax gen-temps-and-sets
  (syntax-rules ()

    ((gen-temps-and-sets (variable ...) values-form)
     (emit-cwv-form
         (temp)                          ;; ****
         ((begin
            (newline)
            (display "Now assigning ")
            (display 'variable)
            (display " to value ")
            (display temp)
            (force-output)
            (set! variable temp)) ...)
         values-form))))
@end lisp

We have a problem.  We need as many temps as variables, but the form that generates the temporaries (marked with the asterisks) isn't replicated because it doesn't contain a pattern.  We'll fix this by putting the variable in with the temps and stripping it back out in EMIT-CWV-FORM.

@lisp
(define-syntax gen-temps-and-sets
  (syntax-rules ()

    ((gen-temps-and-sets (variable ...) values-form)
     (emit-cwv-form
         ((temp variable) ...)
         ((set! variable temp) ...)
         values-form))))

(define-syntax emit-cwv-form
  (syntax-rules ()

    ((emit-cwv-form ((temp variable) ...) assignments values-form)
     (call-with-values (lambda () values-form)
       (lambda (temp ...)
           . assignments)))))
@end lisp

We have another problem.  This doesn't work.  Recall that when we introduce new variables that we need to introduce unrelated copies in different expansions. Even though we create a list of temps, they are all created in a single expansion, so they will all be the same identifier in the resulting code.  You cannot use the same identifier twice in a lambda argument list.

We will need to return to the list induction form, but the problem is that it generates the assignments in reverse order.  We therefore use ellipses not to iterate over the variables, but to simulate APPEND:

@lisp
(define-syntax multiple-value-set!
  (syntax-rules ()
    ((multiple-value-set! variables values-form)

     (gen-temps-and-sets
         variables
         ()  ;; initial value of temps
         ()  ;; initial value of assignments
         values-form))))

(define-syntax gen-temps-and-sets
  (syntax-rules ()

    ((gen-temps-and-sets () temps assignments values-form)
     (emit-cwv-form temps assignments values-form))

    ((gen-temps-and-sets (variable . more) (temps ...) (assignments ...) values-form)
     (gen-temps-and-sets
        more
       (temps ... temp)
       (assignments ... (begin
                          (newline)
                          (display "Now assigning value ")
                          (display temp)
                          (display " to variable ")
                          (display 'variable)
                          (flush-output)
                          (set! variable temp)))
       values-form))))

(define-syntax emit-cwv-form
  (syntax-rules ()

    ((emit-cwv-form temps assignments values-form)
     (call-with-values (lambda () values-form)
       (lambda temps . assignments)))))

(multiple-value-set! (a b c) (values 1 2 3))
@end lisp

@example
Now assigning value 1 to variable a
Now assigning value 2 to variable b
Now assigning value 3 to variable c
@end example

When we use the ellipsis subpattern @code{(temps ...)} in the pattern, and the ellipses subtemplate @code{(temps ... temp)} in the template, this is analagous to writing @code{(append temps (list temp))}.  This is a common idiom for extending a list ``from the right hand end''.  While appending to the right-hand end is a terrible idiom to use in normal Scheme, it is commonly used in macro expansion because expansion time is less important than runtime.

We can now see how to `splice' sublists when generating code.  Suppose the pattern were this:

@lisp
(foo (f1 ...) (f2 ...) . body-forms)
@end lisp

and we matched against this:

@lisp
(foo (a b c d) (1 2 3 4) moe larry curly)
@end lisp

Then we can `flatten' the output by using this template:

@lisp
  (f1 ... f2 ... . body-forms) =>
  (a b c d 1 2 3 4 moe larry curly)
@end lisp

Use ellipses to extend lists while retaining the order.

Use ellipses to `flatten' output.

It isn't always convenient to write a separate auxiliary macro for each step of a complex macro.  There is a trick that can be used to put `labels' on patterns.  Since a string will only match another string if they are EQUAL, we can place a string in our patterns.  A template that wishes to transfer to a particular pattern simply mentions the string.  We can combine the @code{gen-sets}, @code{gen-temps}, and @code{emit-cwv-form} with this trick:

@lisp
(define-syntax multiple-value-set!
  (syntax-rules ()
    ((multiple-value-set! (variable . variables) values-form)
     (mvs-aux "entry" variables values-form))

(define-syntax mvs-aux
  (syntax-rules ()
    ((mvs-aux "entry" variables values-form)
     (mvs-aux "gen-code" variables () () values-form))

    ((mvs-aux "gen-code" () temps sets values-form)
     (mvs-aux "emit" temps sets values-form))

    ((mvs-aux "gen-code" (var . vars) (temps ...) (sets ...) values-form)
     (mvs-aux "gen-code" vars
                         (temps ... temp)
                         (sets ... (set! var temp))
                         values-form))

    ((mvs-aux "emit" temps sets values-form)
     (call-with-values (lambda () values-form)
       (lambda temps . sets)))))
@end lisp

Let's compare this form of the macro @code{GEN-TEMPS-AND-SETS}

@lisp
(define-syntax gen-temps-and-sets
  (syntax-rules ()

    ((gen-temps-and-sets () temps assignments values-form)
     (emit-cwv-form temps assignments values-form))

    ((gen-temps-and-sets (variable . more) temps assignments values-form)
     (gen-temps-and-sets
        more
       (temp . temps)
       ((set! variable temp) . assignments)
       values-form))))
@end lisp

with some Scheme code that iterates over a list and constructs a collection of s-expressions.  This code is not a macro but it performs a superficially similar calculation:

@lisp
(define (gen-temps-and-sets variables temps assignments values-form)
   (cond

      ((null? variables)
       (emit-cwv-form temps assignments values-form))

      ((pair? variables) (let ((variable (car variables))
                               (more     (cdr variables)))

                           (gen-temps-and-sets
                              more
                              `(temp ,@ temps)
                              `((set! ,variable temp) ,@ assignments)
                               values-form)))))
@end lisp

The similarity is striking:

@itemize @minus
@item
SYNTAX-RULES is a COND
@item
The pattern language is a hybrid of predicate (null? and pair?) and list destructuring code.  A dotted pair in the pattern takes the CAR and CDR of the list provided it is a PAIR?   ( . )
@item
The list structure in the template is QUASIQUOTE (sans punctuation) and is equivalent to the appropriate CONS and LIST forms.  The quoting is implicit:  everything is quoted except those identifiers that were matched in the pattern.
@item
Ellipses does a mapcar/append sort of thing.
@end itemize

In our macro language we've identified conditionals, variables, tail-recursive calls, and list and pair data structures, and primitives such as CAR, CDR, CONS, APPEND, and even a weird mapping mechanism.  What about non-tail-recursive function calls, data structure abstractions, and first-class functions?  Unfortunately, these constructs are a bit more complex.

The macro language appears to be a variant of Scheme, but as seen through the looking glass, where things are not always as they appear.  How can we characterize the language?

The most important difference between a form in Scheme and a form in the macro language is in the meaning of parenthesis.  In Scheme, a parenthesized form is either a special form or a function call.  In the macro language it is either a destructuring predicate or a constructor.  But if we are using parenthesis for that purpose, we can't use them for function calls anymore.

@itemize @minus
@item
a template in the macro language with a macro name in the function position is a macro function call
@item
like Scheme, the value of variable is passed to the called procedure, not the name of the variable.

@item
like Scheme, arguments are positional

@item
unlike Scheme, the arguments are unnamed.  Patterns must be positionally tested.

@item
unlike Scheme, subexpressions in the pattern can only indirectly invoke list manipulation functions like @code{CAR}, @code{CDR}, @code{PAIR?} and @code{EQUAL?} through a pattern matching mechanism.
@item
unlike Scheme, subexpressions in the template can only indirectly invoke list manipulation functions like CONS or APPEND through a quasiquote-like mechanism.

@end itemize

If we are missing the ability to call arbitrary functions from a subexpression, we are restricted to a linear calling sequence.  For the macros written so far this is sufficient, but we will need something better for more complicated macros.

How do we write a macro subroutine? Our macro calls so far have been tail recursive --- each routine transfered control to another until the emit code was finally called.  A subroutine, however, needs a continuation to determine what macro to return to.  We will explicitly pass the macro continuation to the macro subroutine.  The subroutine will `return' by invoking the macro continuation on the values it has produced.

So let's use this technique to deeply reverse a list.  The `continuation' is represented by a list of a string tag and whatever values the continuation may need to use (we don't yet have closures, so we carry the data along).  To return a value, we destructure the continuation to obtain the tag and re-invoke sreverse.

@lisp
(define-syntax sreverse
   (syntax-rules ()
     ((sreverse thing) (sreverse "top" thing ("done")))

     ((sreverse "top" () (tag . more))
      (sreverse tag () . more))

     ((sreverse "top" ((headcar . headcdr) . tail) kont)
      (sreverse "top" tail ("after-tail" (headcar . headcdr) kont)))

     ((sreverse "after-tail" new-tail head kont)
      (sreverse "top" head ("after-head" new-tail kont)))

     ((sreverse "after-head" () new-tail (tag . more))
      (sreverse tag new-tail . more))

     ((sreverse "after-head" new-head (new-tail ...) (tag . more))
      (sreverse tag (new-tail ... new-head) . more))

     ((sreverse "top" (head . tail) kont)
      (sreverse "top" tail ("after-tail2" head kont)))

     ((sreverse "after-tail2" () head (tag . more))
      (sreverse tag (head) . more))

     ((sreverse "after-tail2" (new-tail ...) head (tag . more))
      (sreverse tag (new-tail ... head) . more))

     ((sreverse "done" value)
      'value)))
@end lisp

Let's closely examine a simple call and return.

This clause recursively invokes sreverse on the head of the expression.  It creates a new continuation by creating the list @code{("after-head" new-tail kont)}.

@lisp
((sreverse "after-tail" new-tail head kont)
 (sreverse "top" head ("after-head" new-tail kont)))
@end lisp

This is where we will end up when that continuation is invoked.  We expect the `return value' as the first `argument' after the tag.  The remaining arguments after the tag are the remaining list elements of the continuation we made.  As you can see here, "after-head" is itself going to invoke a continuation --- the continuation saved within the continuation constructed above.

@lisp
     ((sreverse "after-head" () new-tail (tag . more))
      (sreverse tag new-tail . more))

     ((sreverse "after-head" new-head (new-tail ...) (tag . more))
      (sreverse tag (new-tail ... new-head) . more))
@end lisp

Something very interesting is going on here.  Let's add a rule to our macro that causes the macro to halt when the list we wish to reverse is the element 'HALT.

@lisp
(define-syntax sreverse
   (syntax-rules (halt)
     ((sreverse thing) (sreverse "top" thing ("done")))

     ((sreverse "top" () (tag . more))
      (sreverse tag () . more))

     ((sreverse "top" ((headcar . headcdr) . tail) kont)
      (sreverse "top" tail ("after-tail" (headcar . headcdr) kont)))

     ((sreverse "after-tail" new-tail head kont)
      (sreverse "top" head ("after-head" new-tail kont)))

     ((sreverse "after-head" () new-tail (tag . more))
      (sreverse tag new-tail . more))

     ((sreverse "after-head" new-head (new-tail ...) (tag . more))
      (sreverse tag (new-tail ... new-head) . more))

     ((sreverse "top" (halt . tail) kont)
      '(sreverse "top" (halt . tail) kont))

     ((sreverse "top" (head . tail) kont)
      (sreverse "top" tail ("after-tail2" head kont)))

     ((sreverse "after-tail2" () head (tag . more))
      (sreverse tag (head) . more))

     ((sreverse "after-tail2" (new-tail ...) head (tag . more))
      (sreverse tag (new-tail ... head) . more))

     ((sreverse "done" value)
      'value)))

(sreverse (1 (2 3) (4 (halt)) 6 7))
=>
  (sreverse "top" (halt)
    ("after-head" ()
      ("after-tail2" 4
        ("after-head" (7 6)
          ("after-tail" (2 3)
            ("after-tail2" 1
              ("done")))))))
@end lisp

Notice how each continuation to sreverse contains the saved state for that continuation in addition to its `parent' continuation.

Let's take a huge leap of imagination:

The intermediate form is a last-in, first-out stack.  The topmost element on the stack is the current function, the next few elements are the arguments, and this is followed by the return address and the remaining dynamic context.  We have a stack of call frames.

I like to refer to this as `stack-machine style'.

We can exploit the analogy between the macro processor and a stack machine more fully by re-arranging the patterns and templates to place the continuation in a fixed spot.  The logical spot in the first position rather than the last. In addition, if we change the way the continuation is constructed, i.e., change the format of the stack frame, we can arrange for the return value to be delivered to any desired location.  Rather than place the return value immediately after the tag, we'll place the tag and the first few values of the frame in a list and upon returning we'll spread the list and put the value after the last element.  This can all be done with an auxiliary macro:

@lisp
(define-syntax return
  (syntax-rules ()

    ;; @r{Continuation goes first.  Location of return value is indicated}
    ;; @r{by end of first list.}
    ((return ((kbefore ...) . kafter) value)
     (kbefore ... value . kafter))

    ;; @r{Special case to just return value from the null continuation.}
    ((return () value) value)))
@end lisp

Constructing a continuation of the correct form is tedious, if we are computing something of the form @code{(f a b (g x) c d)}, we have to write it something like this: @code{(g ((f a b) c d) x)} in order to compute G and get the result placed into @code{(f a b <result> c d)}.  We can write a helper macro for that.  It will take 3 arguments, the current continuation, the saved elements to come before the return value, the call to the subroutine, and the saved elements after the return value.  So if we want to express a nested function call like this, @code{(f a b (g x) c d)} we can write

@lisp
(macro-subproblem (f a b) (g x) c d)
@end lisp

We are still limited to exactly one subproblem, though.

To facilitate calls with tags, we allow G to be a list that is spread at the head, so

@lisp
(macro-subproblem (f a b) ((g "tag") x) c d)
@end lisp

becomes
@lisp
(g "tag" ((f a b) (c d)) x)
@end lisp

@lisp
(define-syntax macro-subproblem
  (syntax-rules ()
    ((macro-subproblem before ((macro-function ...) . args) . after)
     (macro-function ... (before . after) . args))

    ((macro-subproblem before (macro-function . args) . after)
     (macro-function (before . after) . args))))
@end lisp

@code{SREVERSE} now becomes this:

@lisp
(define-syntax sreverse
   (syntax-rules (halt)
     ((sreverse thing)
        (macro-subproblem
          (sreverse "done" ()) ((sreverse "top") thing)))

     ((sreverse "top" k ())
      (return k ()))

     ((sreverse "top" k ((headcar . headcdr) . tail))
      (macro-subproblem
        (sreverse "after-tail" k) ((sreverse "top") tail) (headcar . headcdr)))

     ((sreverse "after-tail" k new-tail head)
      (macro-subproblem
        (sreverse "after-head" k) ((sreverse "top") head) new-tail))

     ((sreverse "after-head" k () new-tail)
      (return k new-tail))

     ((sreverse "after-head" k new-head (new-tail ...))
      (return k (new-tail ... new-head)))

     ((sreverse "top" k (halt . tail))
      '(sreverse "top" k (halt . tail)))

     ((sreverse "top" k (head . tail))
      (macro-subproblem
        (sreverse "after-tail2" k) ((sreverse "top") tail) head))

     ((sreverse "after-tail2" k () head)
      (return k (head)))

     ((sreverse "after-tail2" k (new-tail ...) head)
      (return k (new-tail ... head)))

     ((sreverse "done" k value)
      (return k 'value))))
@end lisp

Although the calling syntax is still rather cumbersome, we have made it easy to write macro subroutines.  Here is NULL?, CAR, PAIR? and LIST? written as macro subroutines:

@lisp
(define-syntax macro-null?
  (syntax-rules ()
    ((macro-null? k ())        (return k #t))
    ((macro-null? k otherwise) (return k #f))))

(define-syntax macro-car
  (syntax-rules ()
    ((macro-car k (car . cdr)) (return k car))
    ((macro-car k otherwise)   (syntax-error "Not a list"))))

(define-syntax macro-pair?
  (syntax-rules ()
    ((macro-car k (a . b))   (return k #t))
    ((macro-car k otherwise) (return k #f))))

(define-syntax macro-list?
  (syntax-rules ()
    ((macro-car k (elements ...)) (return k #t))
    ((macro-car k otherwise)      (return k #f))))
@end lisp

The macro analog of IF suggests itself.  We just tail call the pred after inserting IF-DECIDE into the continuation chain.

@lisp
(define-syntax macro-if
  (syntax-rules ()
    ((macro-if (pred . args) if-true if-false)
     (pred ((if-decide) if-true if-false) . args))))

(define-syntax if-decide
  (syntax-rules ()
    ((if-decide #t if-true if-false) if-true)
    ((if-decide #f if-true if-false) if-false)))
@end lisp

An example use would be:

@lisp
(define-syntax whatis
  (syntax-rules ()
    ((whatis object) (whatis1 () object))))

(define-syntax whatis1
  (syntax-rules ()
    ((whatis1 k object)
     (macro-if (macro-null? object)
       (return k 'null)
       (macro-if (macro-list? object)
         (macro-subproblem
           (whatis1 "after car" k proper) (macro-car object))
         (macro-if (macro-pair? object)
           (macro-subproblem
             (whatis1 "after car" k improper) (macro-car object))
           (return k 'something-else)))))

    ((whatis1 "after car" k type c)
     (return k '(a type list whose car is c)))))
@end lisp

The first obvious drawback to these stack-machine style macros is the clumsy calling sequence.  We can only call compute one subproblem at a time and we need to have a label to return to for each subproblem.  As you might imagine, this, too, can be solved by a macro function.

However, there is a bit of a problem.  If take the obvious approach and scan the macro call for parenthesized subexpressions, we have destroyed our ability to use templates as templates.  We will need to be able to determine which parenthesis are not meant as function calls but are meant as list templates.  Although we could re-introduce a quoting syntax, we would be losing most of the power of templates and we would be burying our code in a pile of quote and unquote forms.

Instead, let us place marks within the template to indicate what subexpressions are meant as subproblems.

@lisp
(define-syntax macro-call
  (syntax-rules (!)
    ((macro-call k (! ((function ...) . arguments)))
     (function ... k . arguments))

    ((macro-call k (! (function . arguments)))
     (macro-call ((macro-apply k function)) arguments))

    ((macro-call k (a . b))
     (macro-call ((macro-descend-right k) b) a))

    ((macro-call k whatever) (return k whatever))))

(define-syntax macro-apply
  (syntax-rules ()
    ((macro-apply k function arguments)
     (function k . arguments))))

(define-syntax macro-descend-right
  (syntax-rules ()
    ((macro-descend-right k evaled b)
     (macro-call ((macro-cons k evaled)) b))))

(define-syntax macro-cons
   (syntax-rules ()
     ((macro-cons k ca cd) (return k (ca . cd)))))
@end lisp

So if we expand this form:

@lisp
(macro-call ()
  (this is a (! (macro-cdr (a b (! (macro-null? ())) c d))) test))
@end lisp

The expansion is @code{(this is a (b #t c d) test)}

Let's write a macro similar to LET.  Since let-like binding lists are a common macro feature, we'd like to have a subroutine to parse them. We'd also like a subroutine to tell us if the first argument to our LET is a name or a binding list.

@lisp
(define-syntax my-let
  (syntax-rules ()
    ((my-let first-subform . other-subforms)
     (macro-if (is-symbol? first-subform)
       (expand-named-let () first-subform other-subforms)
       (expand-standard-let () first-subform other-subforms)))))
@end lisp

To test if something is a symbol, we first test to see if it is a list or vector.  If it matches, we simply return if-no.  If it doesn't match, then we know it is atomic, but we don't know if it is a symbol. Recall that symbols in macros match anything, but other atoms only match things equal? to themselves.  Oleg Kiselyov suggests this nasty trick: we build a syntax-rule using it and see if the rule matches a list.

@lisp
(define-syntax is-symbol?
  (syntax-rules ()

    ((is-symbol? k (form ...))  (return k #f))
    ((is-symbol? k #(form ...)) (return k #f))

    ((is-symbol? k atom)
     (letrec-syntax ((test-yes (syntax-rules () ((test-yes) (return k #t))))
                     (test-no  (syntax-rules () ((test-no)  (return k #f))))
                     (test-rule
                       (syntax-rules ()
                         ((test-rule atom) (test-yes))
                         ((test-rule . whatever) (test-no)))))
            (test-rule (#f))))))
@end lisp

We need to use LETREC-SYNTAX here because we do not want our continuation forms to be in the template of the test-rule; if the test rule matches, the atom we just tested would be rewritten!

Parsing a binding-list list is easy to do with an ellipses:

@lisp
(define-syntax parse-bindings
  (syntax-rules ()
    ((parse-bindings k ((name value) ...))
     (return k ((name ...) (value ...))))))

(define-syntax expand-named-let
  (syntax-rules ()
    ((expand-named-let k name (bindings . body))
      (macro-call k
        (! (emit-named-let name (! (parse-bindings bindings)) body))))))

(define-syntax expand-standard-let
  (syntax-rules ()
    ((expand-standard-let k bindings body)
     (macro-call k
        (! (emit-standard-let (! (parse-bindings bindings)) body))))))

(define-syntax emit-named-let
  (syntax-rules ()
    ((emit-named-let k name (args values) body)
     (return k (((lambda (name)
                   (set! name (lambda args . body))
                    name) #f) . values)))))
@end lisp

The obligatory hack.

The following is a small scheme interpreter written as a syntax-rules macro.  It is incredibly slow.

@lisp
(define-syntax macro-cdr
  (syntax-rules ()
    ((macro-cdr k (car . cdr)) (return k cdr))
    ((macro-cdr k otherwise)   (syntax-error "Not a list"))))

(define-syntax macro-append
   (syntax-rules ()
     ((macro-append k (e1 ...) (e2 ...)) (return k (e1 ... e2 ...)))))

(define-syntax initial-environment
  (syntax-rules ()
    ((initial-environment k)
     (return k ((cdr . macro-cdr)
                (null? . macro-null?)
                (append . macro-append)
                )))))

(define-syntax scheme-eval
  (syntax-rules ()
    ((scheme-eval expression)
     (macro-call ((quote))
       (! (meval expression (! (initial-environment))))))))

(define-syntax meval
  (syntax-rules (if lambda quote)
    ((meval k () env)  (return k ()))

    ((meval k (if pred cons alt) env)
     (macro-if (meval pred env)
       (meval k cons env)
       (meval k alt env)))

    ((meval k (lambda names body) env)
     (return k (closure names body env)))

    ((meval k (quote object) env) (return k object))

    ((meval k (operator . operands) env)
     (meval-list ((mapply k)) () (operator . operands) env))

    ((meval k whatever env)
     (macro-if (is-symbol? whatever)
       (mlookup k whatever env)
       (return k whatever)))))

(define-syntax mlookup
  (syntax-rules ()
    ((mlookup k symbol ())
     '(variable not found))
    ((mlookup k symbol ((var . val) . env))
     (macro-if (is-eqv? symbol var)
       (return k val)
       (mlookup k symbol env)))))

(define-syntax meval-list
  (syntax-rules ()
    ((meval-list k evaled () env)
     (return k evaled))

    ((meval-list k (evaled ...) (to-eval . more) env)
     (macro-call k
       (! (meval-list (evaled ... (! (meval to-eval env))) more env))))))

(define-syntax mapply
  (syntax-rules (closure)
    ((mapply k ((closure names body env) . operands))
     (macro-call k
       (! (meval body (! (extend-environment env names operands))))))

    ((mapply k (operator . operands))
     (macro-if (is-symbol? operator)
       (operator k . operands)
       '(non-symbol application)))))

(define-syntax extend-environment
  (syntax-rules ()
    ((extend-environment k env () ())
     (return k env))

   ((extend-environment k env names ())
    '(too-few-arguments))

   ((extend-environment k env () args)
    '(too-many-arguments))

   ((extend-environment k env (name . names) (arg . args))
    (extend-environment k ((name . arg) . env) names args))))
@end lisp