This appendix describes an extension to Scheme that allows programs to define and use new derived expression types. A derived expression type that has been defined using this extension is called a macro.
Derived expression types introduced using this extension have the syntax
(<keyword> <datum>*)
where <keyword> is an identifier that uniquely determines the expression type. This identifier is called the syntactic keyword, or simply keyword, of the macro. The number of the <datum>s, and their syntax, depends on the expression type.
Each instance of a macro is called a use of the macro. The set of rules, or more generally the procedure, that specifies how a use of a macro is transcribed into a more primitive expression is called the transformer of the macro.
The extension described here consists of three parts:
With this extension, there are no reserved identifiers. The syntactic keyword of a macro may shadow variable bindings, and local variable bindings may shadow keyword bindings. All macros defined using the pattern language are "hygienic" and "referentially transparent":
This appendix is divided into three major sections. The first section describes the expressions and definitions used to introduce macros, i.e. to bind identifiers to macro transformers.
The second section describes the pattern language. This pattern language is sufficient to specify most macro transformers, including those for all the derived expression types from section 4.2 Derived expression types. The primary limitation of the pattern language is that it is thoroughly hygienic, and thus cannot express macros that bind identifiers implicitly.
The third section describes a low-level macro facility that could be used to implement the pattern language described in the second section. This low-level facility is also capable of expressing non-hygienic macros and other macros whose transformers cannot be described by the pattern language, and is important as an example of a more powerful facility that can co-exist with the high-level pattern language.
The particular low-level facility described in the third section is but one of several low-level facilities that have been designed and implemented to complement the pattern language described in the second section. The design of such low-level macro facilities remains an active area of research, and descriptions of alternative low-level facilities will be published in subsequent documents.
`Define-syntax', `let-syntax', and `letrec-syntax' are analogous to `define', `let', and `letrec', but they bind syntactic keywords to macro transformers instead of binding variables to locations that contain values. Furthermore, there is no `define-syntax' analogue of the internal definitions described in section 5.2.2 Internal definitions.
Rationale: As discussed below, the syntax and scope rules for definitions give rise to syntactic ambiguities when syntactic keywords are not reserved. Further ambiguities would arise if `define-syntax' were permitted at the beginning of a <body>, with scope rules analogous to those for internal definitions.
These new expression types and the pattern language described in section Pattern language are added to Scheme by augmenting the BNF in section 7.1 Formal syntax with the following new productions. Note that the identifier `...' used in some of these productions is not a metasymbol.
<expression> --> <macro use>
| <macro block>
<macro use> --> (<keyword> <datum>*)
<keyword> --> <identifier>
<macro block> -->
(let-syntax (<syntax spec>*) <body>)
| (letrec-syntax (<syntax spec>*) <body>)
<syntax spec> --> (<keyword> <transformer spec>)
<transformer spec> -->
(syntax-rules (<identifier>*) <syntax rule>*)
<syntax rule> --> (<pattern> <template>)
<pattern> --> <pattern identifier>
| (<pattern>*)
| (<pattern>+ . <pattern>)
| (<pattern>* <pattern> <ellipsis>)
| <pattern datum>
<pattern datum> --> <vector>
| <string>
| <character>
| <boolean>
| <number>
<template> --> <pattern identifier>
| (<template element>*)
| (<template element>+ . <template>)
| <template datum>
<template element> --> <template>
| <template> <ellipsis>
<template datum> --> <pattern datum>
<pattern identifier> --> <any identifier except `...'>
<ellipsis> --> <the identifier `...'>
<command or definition> --> <syntax definition>
<syntax definition> -->
(define-syntax <keyword> <transformer spec>)
| (begin <syntax definition>*)
Although macros may expand into definitions in any context that permits definitions, it is an error for a definition to shadow a syntactic keyword whose meaning is needed to determine whether some definition in the group of top-level or internal definitions that contains the shadowing definition is in fact a definition, or is needed to determine the boundary between the group and the expressions that follow the group. For example, the following are errors:
(define define 3)
(begin (define begin list))
(let-syntax
((foo (syntax-rules ()
((foo (proc args ...) body ...)
(define proc
(lambda (args ...)
body ...))))))
(let ((x 3))
(foo (plus x y) (+ x y))
(define foo x)
(plus foo x)))
Syntax: <Bindings> should have the form
((<keyword> <transformer spec>) ...)
Each <keyword> is an identifier, each <transformer spec> is an instance of `syntax-rules', and <body> should be a sequence of one or more expressions. It is an error for a <keyword> to appear more than once in the list of keywords being bound.
Semantics: The <body> is expanded in the syntactic environment obtained by extending the syntactic environment of the `let-syntax' expression with macros whose keywords are the <keyword>s, bound to the specified transformers. Each binding of a <keyword> has <body> as its region.
(let-syntax ((when (syntax-rules ()
((when test stmt1 stmt2 ...)
(if test
(begin stmt1
stmt2 ...))))))
(let ((if #t))
(when if (set! if 'now))
if)) ==> now
(let ((x 'outer))
(let-syntax ((m (syntax-rules () ((m) x))))
(let ((x 'inner))
(m)))) ==> outer
Syntax: Same as for `let-syntax'.
Semantics: The <body> is expanded in the syntactic environment obtained by extending the syntactic environment of the `letrec-syntax' expression with macros whose keywords are the <keyword>s, bound to the specified transformers. Each binding of a <keyword> has the <bindings> as well as the <body> within its region, so the transformers can transcribe expressions into uses of the macros introduced by the `letrec-syntax' expression.
(letrec-syntax
((or (syntax-rules ()
((or) #f)
((or e) e)
((or e1 e2 ...)
(let ((temp e1))
(if temp
temp
(or e2 ...)))))))
(let ((x #f)
(y 7)
(temp 8)
(let odd?)
(if even?))
(or x
(let temp)
(if y)
y))) ==> 7
Syntax: The <keyword> is an identifier, and the <transformer spec> should be an instance of `syntax-rules'.
Semantics: The top-level syntactic environment is extended by binding the <keyword> to the specified transformer.
(define-syntax let*
(syntax-rules ()
((let* () body1 body2 ...)
(let () body1 body2 ...))
((let* ((name1 val1) (name2 val2) ...)
body1 body2 ...)
(let ((name1 val1))
(let* ((name2 val2) ...)
body1 body2 ...)))))
Syntax: <Literals> is a list of identifiers, and each <syntax rule> should be of the form
(<pattern> <template>)
where the <pattern> and <template> are as in the grammar above.
Semantics: An instance of `syntax-rules' produces a new macro transformer by specifying a sequence of hygienic rewrite rules. A use of a macro whose keyword is associated with a transformer specified by `syntax-rules' is matched against the patterns contained in the <syntax rule>s, beginning with the leftmost <syntax rule>. When a match is found, the macro use is transcribed hygienically according to the template.
Each pattern begins with the keyword for the macro. This keyword is not involved in the matching and is not considered a pattern variable or literal identifier.
Rationale: The scope of the keyword is determined by the expression or syntax definition that binds it to the associated macro transformer. If the keyword were a pattern variable or literal identifier, then the template that follows the pattern would be within its scope regardless of whether the keyword were bound by `let-syntax' or by `letrec-syntax'.
An identifier that appears in the pattern of a <syntax rule> is a pattern variable, unless it is the keyword that begins the pattern, is listed in <literals>, or is the identifier "`...'". Pattern variables match arbitrary input elements and are used to refer to elements of the input in the template. It is an error for the same pattern variable to appear more than once in a <pattern>.
Identifiers that appear in <literals> are interpreted as literal identifiers to be matched against corresponding subforms of the input. A subform in the input matches a literal identifier if and only if it is an identifier and either both its occurrence in the macro expression and its occurrence in the macro definition have the same lexical binding, or the two identifiers are equal and both have no lexical binding.
A subpattern followed by `...' can match zero or more elements of the input. It is an error for `...' to appear in <literals>. Within a pattern the identifier `...' must follow the last element of a nonempty sequence of subpatterns.
More formally, an input form F matches a pattern P if and only if:
It is an error to use a macro keyword, within the scope of its binding, in an expression that does not match any of the patterns.
When a macro use is transcribed according to the template of the matching <syntax rule>, pattern variables that occur in the template are replaced by the subforms they match in the input. Pattern variables that occur in subpatterns followed by one or more instances of the identifier `...' are allowed only in subtemplates that are followed by as many instances of `...'. They are replaced in the output by all of the subforms they match in the input, distributed as indicated. It is an error if the output cannot be built up as specified.
Identifiers that appear in the template but are not pattern variables or the identifier `...' are inserted into the output as literal identifiers. If a literal identifier is inserted as a free identifier then it refers to the binding of that identifier within whose scope the instance of `syntax-rules' appears. If a literal identifier is inserted as a bound identifier then it is in effect renamed to prevent inadvertent captures of free identifiers.
(define-syntax let
(syntax-rules ()
((let ((name val) ...) body1 body2 ...)
((lambda (name ...) body1 body2 ...)
val ...))
((let tag ((name val) ...) body1 body2 ...)
((letrec ((tag (lambda (name ...)
body1 body2 ...)))
tag)
val ...))))
(define-syntax cond
(syntax-rules (else =>)
((cond (else result1 result2 ...))
(begin result1 result2 ...))
((cond (test => result))
(let ((temp test))
(if temp (result temp))))
((cond (test => result) clause1 clause2 ...)
(let ((temp test))
(if temp
(result temp)
(cond clause1 clause2 ...))))
((cond (test)) test)
((cond (test) clause1 clause2 ...)
(or test (cond clause1 clause2 ...)))
((cond (test result1 result2 ...))
(if test (begin result1 result2 ...)))
((cond (test result1 result2 ...)
clause1 clause2 ...)
(if test
(begin result1 result2 ...)
(cond clause1 clause2 ...)))))
(let ((=> #f))
(cond (#t => 'ok))) ==> ok
The last example is not an error because the local variable `=>' is renamed in effect, so that its use is distinct from uses of the top level identifier `=>' that the transformer for `cond' looks for. Thus, rather than expanding into
(let ((=> #f))
(let ((temp #t))
(if temp ('ok temp))))
which would result in an invalid procedure call, it expands instead into
(let ((=> #f)) (if #t (begin => 'ok)))
Although the pattern language provided by `syntax-rules' is the preferred way to specify macro transformers, other low-level facilities may be provided to specify more complex macro transformers. In fact, `syntax-rules' can itself be defined as a macro using the low-level facilities described in this section.
The low-level macro facility described here introduces `syntax' as a new syntactic keyword analogous to `quote', and allows a <transformer spec> to be any expression. This is accomplished by adding the following two productions to the productions in section 7.1 Formal syntax and in section Binding syntactic keywords above.
<expression> --> (syntax <datum>) <transformer spec> --> <expression>
The low-level macro system also adds the following procedures:
unwrap-syntax identifier->symbol identifier? generate-identifier free-identifier=? construct-identifier bound-identifier=?
Evaluation of a program proceeds in two logical steps. First the program is converted into an intermediate language via macro-expansion, and then the result of macro expansion is evaluated. When it is necessary to distinguish the second stage of this process from the full evaluation process, it is referred to as "execution."
Syntax definitions, either lexical or global, cause an identifier to be treated as a keyword within the scope of the binding. The keyword is associated with a transformer, which may be created implicitly using the pattern language of `syntax-rules' or explicitly using the low-level facilities described below.
Since a transformer spec must be fully evaluated during the course of expansion, it is necessary to specify the environment in which this evaluation takes place. A transformer spec is expanded in the same environment as that in which the program is being expanded, but is executed in an environment that is distinct from the environment in which the program is executed. This execution environment distinction is important only for the resolution of global variable references and assignments. In what follows, the environment in which transformers are executed is called the standard transformer environment and is assumed to be a standard Scheme environment.
Since part of the task of hygienic macro expansion is to resolve identifier references, the fact that transformers are expanded in the same environment as the program means that identifier bindings in the program can shadow identifier uses within transformers. Since variable bindings in the program are not available at the time the transformer is executed, it is an error for a transformer to reference or assign them. However, since keyword bindings are available during expansion, lexically visible keyword bindings from the program may be used in macro uses in a transformer.
When a macro use is encountered, the macro transformer associated with the macro keyword is applied to a representation of the macro expression. The result returned by the macro transformer replaces the original expression and is expanded once again. Thus macro expansions may themselves be or contain macro uses.
The syntactic representation passed to a macro transformer encapsulates information about the structure of the represented form and the bindings of the identifiers it contains. These syntax objects can be traversed and examined using the procedures described below. The output of a transformer may be built up using the usual Scheme list constructors, combining pieces of the input with new syntactic structures.
Syntax: The <datum> may be any external representation of a Scheme object.
Semantics: `Syntax' is the syntactic analogue of `quote'. It creates a syntactic representation of <datum> that, like an argument to a transformer, contains information about the bindings for identifiers contained in <datum>. The binding for an identifier introduced by `syntax' is the closest lexically visible binding. All variables and keywords introduced by transformers must be created by `syntax'. It is an error to insert a symbol in the output of a transformation procedure unless it is to be part of a quoted datum.
(symbol? (syntax x)) ==> #f
(let-syntax ((car (lambda (x) (syntax car))))
((car) '(0))) ==> 0
(let-syntax
((quote-quote
(lambda (x) (list (syntax quote) 'quote))))
(quote-quote)) ==> quote
(let-syntax
((quote-quote
(lambda (x) (list 'quote 'quote))))
(quote-quote)) ==> error
The second `quote-quote' example results in an error because two raw symbols are being inserted in the output. The quoted `quote' in the first `quote-quote' example does not cause an error because it will be a quoted datum.
(let-syntax ((quote-me
(lambda (x)
(list (syntax quote) x))))
(quote-me please)) ==> (quote-me please)
(let ((x 0))
(let-syntax ((alpha (lambda (e) (syntax x))))
(alpha))) ==> 0
(let ((x 0))
(let-syntax ((alpha (lambda (x) (syntax x))))
(alpha))) ==> error
(let-syntax ((alpha
(let-syntax ((beta
(syntax-rules ()
((beta) 0))))
(lambda (x) (syntax (beta))))))
(alpha)) ==> error
The last two examples are errors because in both cases a lexically bound identifier is placed outside of the scope of its binding. In the first case, the variable `x' is placed outside its scope. In the second case, the keyword `beta' is placed outside its scope.
(let-syntax ((alpha (syntax-rules ()
((alpha) 0))))
(let-syntax ((beta (lambda (x) (alpha))))
(beta))) ==> 0
(let ((list 0))
(let-syntax ((alpha (lambda (x) (list 0))))
(alpha))) ==> error
The last example is an error because the reference to `list' in the transformer is shadowed by the lexical binding for `list'. Since the expansion process is distinct from the execution of the program, transformers cannot reference program variables. On the other hand, the previous example is not an error because definitions for keywords in the program do exist at expansion time.
Note: It has been suggested that `#'<datum>' and `#`<datum>' would be felicitous abbreviations for `(syntax <datum>)' and `(quasisyntax <datum>)', respectively, where `quasisyntax', which is not described in this appendix, would bear the same relationship to `syntax' that `quasiquote' bears to `quote'.
Returns #t if syntax-object represents an identifier, otherwise returns #f.
(identifier? (syntax x)) ==> #t (identifier? (quote x)) ==> #f (identifier? 3) ==> #f
If syntax-object is an identifier, then it is returned unchanged. Otherwise `unwrap-syntax' converts the outermost structure of syntax-object into a data object whose external representation is the same as that of syntax-object. The result is either an identifier, a pair whose car and cdr are syntax objects, a vector whose elements are syntax objects, an empty list, a string, a boolean, a character, or a number.
(identifier? (unwrap-syntax (syntax x)))
==> #t
(identifier? (car (unwrap-syntax (syntax (x)))))
==> #t
(unwrap-syntax (cdr (unwrap-syntax (syntax (x)))))
==> ()
Returns #t if the original occurrences of id1 and id2 have the same binding, otherwise returns #f. `free-identifier=?' is used to look for a literal identifier in the argument to a transformer, such as `else' in a `cond' clause. A macro definition for `syntax-rules' would use `free-identifier=?' to look for literals in the input.
(free-identifier=? (syntax x) (syntax x))
==> #t
(free-identifier=? (syntax x) (syntax y))
==> #f
(let ((x (syntax x)))
(free-identifier=? x (syntax x)))
==> #f
(let-syntax
((alpha
(lambda (x)
(free-identifier=? (car (unwrap-syntax x))
(syntax alpha)))))
(alpha)) ==> #f
(letrec-syntax
((alpha
(lambda (x)
(free-identifier=? (car (unwrap-syntax x))
(syntax alpha)))))
(alpha)) ==> #t
Returns #t if a binding for one of the two identifiers id1 and id2 would shadow free references to the other, otherwise returns #f. Two identifiers can be `free-identifier=?' without being `bound-identifier=?' if they were introduced at different stages in the expansion process. `Bound-identifier=?' can be used, for example, to detect duplicate identifiers in bound-variable lists. A macro definition of `syntax-rules' would use `bound-identifier=?' to look for pattern variables from the input pattern in the output template.
(bound-identifier=? (syntax x) (syntax x))
==> #t
(letrec-syntax
((alpha
(lambda (x)
(bound-identifier=? (car (unwrap-syntax x))
(syntax alpha)))))
(alpha)) ==> #f
Returns a symbol representing the original name of id. `Identifier->symbol' is used to examine identifiers that appear in literal contexts, i.e., identifiers that will appear in quoted structures.
(symbol? (identifier->symbol (syntax x)))
==> #t
(identifier->symbol (syntax x))
==> x
Returns a new identifier. The optional argument to `generate-identifier' specifies the symbolic name of the resulting identifier. If no argument is supplied the name is unspecified.
`Generate-identifier' is used to introduce bound identifiers into the output of a transformer. Since introduced bound identifiers are automatically renamed, `generate-identifier' is necessary only for distinguishing introduced identifiers when an indefinite number of them must be generated by a macro.
The optional argument to `generate-identifier' specifies the symbolic name of the resulting identifier. If no argument is supplied the name is unspecified. The procedure `identifier->symbol' reveals the symbolic name of an identifier.
(identifier->symbol (generate-identifier 'x))
==> x
(bound-identifier=? (generate-identifier 'x)
(generate-identifier 'x))
==> #f
(define-syntax set*!
; (set*! (<identifier> <expression>) ...)
(lambda (x)
(letrec
((unwrap-exp
(lambda (x)
(let ((x (unwrap-syntax x)))
(if (pair? x)
(cons (car x)
(unwrap-exp (cdr x)))
x)))))
(let ((sets (map unwrap-exp
(cdr (unwrap-exp x)))))
(let ((ids (map car sets))
(vals (map cadr sets))
(temps (map (lambda (x)
(generate-identifier))
sets)))
`(,(syntax let) ,(map list temps vals)
,@(map (lambda (id temp)
`(,(syntax set!) ,id ,temp))
ids
temps)
#f))))))
Creates and returns an identifier named by symbol that behaves as if it had been introduced where the identifier id was introduced.
`Construct-identifier' is used to circumvent hygiene by creating an identifier that behaves as though it had been implicitly present in some expression. For example, the transformer for a structure definition macro might construct the name of a field accessor that does not explicitly appear in a use of the macro, but can be constructed from the names of the structure and the field. If a binding for the field accessor were introduced by a hygienic transformer, then it would be renamed automatically, so that the introduced binding would fail to capture any references to the field accessor that were present in the input and were intended to be within the scope of the introduced binding.
Another example is a macro that implicitly binds `exit':
(define-syntax loop-until-exit
(lambda (x)
(let ((exit (construct-identifier
(car (unwrap-syntax x))
'exit))
(body (car (unwrap-syntax
(cdr (unwrap-syntax x))))))
`(,(syntax call-with-current-continuation)
(,(syntax lambda)
(,exit)
(,(syntax letrec)
((,(syntax loop)
(,(syntax lambda) ()
,body
(,(syntax loop)))))
(,(syntax loop))))))))
(let ((x 0) (y 1000))
(loop-until-exit
(if (positive? y)
(begin (set! x (+ x 3))
(set! y (- y 1)))
(exit x)))) => 3000
The extension described in this appendix is the most sophisticated macro facility that has ever been proposed for a block-structured programming language. The main ideas come from Eugene Kohlbecker's PhD thesis on hygienic macro expansion [Kohlbecker86], written under the direction of Dan Friedman [hygienic], and from the work by Alan Bawden and Jonathan Rees on syntactic closures [Bawden88]. Pattern-directed macro facilities were popularized by Kent Dybvig's non-hygienic implementation of `extend-syntax' [Dybvig87].
At the 1988 meeting of this report's authors at Snowbird, a macro committee consisting of Bawden, Rees, Dybvig, and Bob Hieb was charged with developing a hygienic macro facility akin to `extend-syntax' but based on syntactic closures. Chris Hanson implemented a prototype and wrote a paper on his experience, pointing out that an implementation based on syntactic closures must determine the syntactic roles of some identifiers before macro expansion based on textual pattern matching can make those roles apparent. William Clinger observed that Kohlbecker's algorithm amounts to a technique for delaying this determination, and proposed a more efficient version of Kohlbecker's algorithm. Pavel Curtis spoke up for referentially transparent local macros. Rees merged syntactic environments with the modified Kohlbecker's algorithm and implemented it all, twice [macrosthatwork].
Dybvig and Hieb designed and implemented the low-level macro facility described above. Recently Hanson and Bawden have extended syntactic closures to obtain an alternative low-level macro facility. The macro committee has not endorsed any particular low-level facility, but does endorse the general concept of a low-level facility that is compatible with the high-level pattern language described in this appendix.
Several other people have contributed by working on macros over the years. Hal Abelson contributed by holding this report hostage to the appendix on macros.