mailto:srfi-72@srfi.schemers.org.
See instructions
here to subscribe to the list. You can access previous messages via
the
archive of the mailing list.
Existing hygienic macro systems work well for high-level macros, but tend to run into unintended variable capture problems with procedural macros. The proposal described here addresses a class of unintended capture problems that may occur in procedural macros.
A primitive is provided for writing hygiene-breaking macros that are composable and referentially transparent, correcting a known shortcoming of some existing macro systems.
The design provides a small number of primitives with simple semantics. More complex features, including pattern matching facilities and syntax-case, may be built on top of the current design and are available as libraries.
Both syntax-rules and syntax-case have been implemented as macros in the system described here and are available as libraries. In particular, one obtains a concise and portable implementation and semantics for syntax-case in terms of a simpler macro system.
The reference implementation documents an imperative hygiene algorithm that is eager, has linear complexity, and is very fast.
Source correlation information is not associated with syntax objects, but instead instead recorded separately during expansion. All intermediate expansion steps from the source to the object code are made available.
The implementation is small and tractable, written in mostly portable R5RS Scheme without using R5RS macros. It should run out of the box on most existing Schemes.
(define-syntax (swap! a b)
(quasisyntax
(let ((temp ,a))
(set! ,a ,b)
(set! ,b temp))))
This macro builds a syntax object using the quasisyntax primitive.
Identifiers appearing in the quoted part of the quasisyntax
expression are hygienically introduced. Syntax provided as part
of the input expression is inserted in the result using unquote
or unquote-splicing.
To test hygiene, we may evaluate:
(let ((temp 1)
(set! 2))
(swap! set! temp)
(values temp set!)) ;==> 2 1
The above macro may also be written as
(define-syntax swap!
(lambda form
(let ((a (cadr form))
(b (caddr form)))
(quasisyntax
(let ((temp ,a))
(set! ,a ,b)
(set! ,b temp))))))
This illustrates that syntax objects are s-expressions manipulable
with the usual Scheme primitives. Instead of symbols,
these s-expressions contain identifiers, which belong to a separate
data type.
For comparing identifiers, the primitives free-identifier=?, bound-identifier=? and literal-identifier=?, familiar from syntax-case [6, 7], are provided. For example, a simplified cond macro can be written as follows:
(define-syntax (my-cond clause . clauses)
(if (and (list? clause) (>= (length clause) 2))
(cond ((literal-identifier=? (car clause)
(syntax else)) (quasisyntax (begin ,@(cdr clause))))
((null? clauses) (quasisyntax (if ,(car clause) (begin ,@(cdr clause)))))
(else (quasisyntax (if ,(car clause)
(begin ,@(cdr clause))
(my-cond ,@clauses)))))
(syntax-error)))
(my-cond (#f 1) (else 2)) ==> 2
(let ((else #f)) (my-cond (else 2))) ==> unspecified
This concludes the lightning overview of the core proposal.
We mention that, while not part of the core design, a pattern matcher is available separately as a library, allowing the above macro to be written as:
(define-syntax my-cond
(lambda form
(match form
((_ ((syntax else) e1 e2 ...)) (quasisyntax (begin ,e1 ,,e2 ...)))
((_ (e0 e1 e2 ...)) (quasisyntax (if ,e0 (begin ,e1 ,,e2 ...))))
((_ (e0 e1 e2 ...) c1 c2 ...) (quasisyntax (if ,e0
(begin ,e1 ,,e2 ...)
(my-cond ,c1 ,,c2 ...))))
(_ (syntax-error)))))
Finally, both syntax-rules and syntax-case can be implemented
as macros in the system described here and are available as
libraries, so that we can write, for example.
(define-syntax my-cond
(lambda form
(syntax-case form (else)
((_ (else e1 e2 ...)) (syntax (begin e1 e2 ...)))
((_ (e0 e1 e2 ...)) (syntax (if e0 (begin e1 e2 ...))))
((_ (e0 e1 e2 ...) c1 c2 ...) (syntax (if e0
(begin e1 e2 ...)
(my-cond c1 c2 ...)))))))
These extensions are described at [1].
Our design differs from the syntax-case system in the way in which bound-identifier=? identifiers are introduced. Each evaluation of a quasisyntax expression occurs in a fresh hygienic context, so that identifiers introduced during separate evaluations of quasisyntax expressions are never bound-identifier=?, even if these occur during the same macro invocation.
(bound-identifier=? (quasisyntax x) (quasisyntax x)) ==> #fThis choice, inspired by [3, 4], makes it easier to avoid a class of unintentional variable capture problems that may occur in procedural macros, an issue that had been largely neglected in most existing designs.
To see the problem, consider converting the helper macro in the following
(define-syntax no-capture
(syntax-rules ()
((no-capture) (let ((temp 1)) (helper temp)))))
(define-syntax helper
(syntax-rules ()
((helper value) (let ((temp 2)) value))))
(no-capture) ==> 1
to a procedure. The naive syntax-case implementation
(define-syntax (capture stx)
(define (helper value)
(with-syntax ((value value))
(syntax (let ((temp 2)) value))))
(syntax-case stx ()
((capture)
(with-syntax ((nested (helper (syntax temp))))
(syntax (let ((temp 1))
nested))))))
(capture) ==> 2
gives the wrong answer.
The binding for temp introduced by
helper has captured the temp introduced in the syntax-case body,
which was not our intent.
In the system proposed here, the above macro is expressed as follows:
(define-syntax (no-more-capture)
(define (helper value)
(quasisyntax
(let ((temp 2)) ,value)))
(let ((temp (quasisyntax temp)))
(quasisyntax
(let ((,temp 1))
,(helper temp)))))
(no-more-capture) ==> 1
Since each quasisyntax evaluation occurs in a new hygienic
context, the two identifiers temp are distinct in the
sense of bound-identifier=?. As a result, no accidental
capture will take place, and we get the correct answer.
The unintentional capture problem becomes particularly insidious when code is generated recursively. Consider the following reasonable-looking syntax-case implementation of a let macro with guaranteed left to right evaluation:
(define-syntax let-ordered
(lambda (form)
(define (let-help form temps vars)
(syntax-case form ()
((_ () . body)
(with-syntax (((var ...) vars)
((temp ...) temps))
(syntax
(let ((var temp) ...) . body))))
((_ ((var exp) binding ...) . body)
(with-syntax ((rest (let-help (syntax (_ (binding ...) . body))
(cons (syntax temp) temps)
(cons (syntax var) vars))))
(syntax (let ((temp exp))
rest))))))
(let-help form '() '())))
(let-ordered ((x 1)
(y 2))
(+ x y)) ==> 4
The error occurs because all the identifiers temp, occurring in nested
bindings, are bound-identifier=?, so that an unintended variable capture
occurs. Note that, because of hygiene, this problem would not
have occurred if let-helper had been implemented as a macro instead of
a helper procedure.
In the MzScheme syntax-case extension, primitives make-syntax-introducer and syntax-local-introduce may be inserted in the appropriate places to obtain the correct behaviour in the above macros. However, correct usage of these primitives is nontrivial, and requires the programmer to be aware that the problem occurs in the first place. The default behaviour remains unsafe.
We see that, in these macro systems, the programmer has to keep track of the names of all identifiers introduced in the macro and all its helper procedures. This may be nontrivial if the macro is large or has various helpers, and is reminiscent of the difficulties one encounters in languages with dynamic scoping of variables. Avoiding name clashes is not enough, as the let-ordered macro shows. In general, it may be quite hard to verify whether accidental captures occur if code is generated recursively.
This issue clearly violates the spirit of lexical scoping and hygiene. It breaks the modularity and constrains the maintainability of complex macros such as pattern matchers.
With the proposal of this SRFI, the above macro can be expressed as follows:
(define-syntax (let-ordered bindings . body)
(define (let-help bindings temps variables)
(cond ((null? bindings) (quasisyntax
(let ,(map list variables temps) ,@body)))
((pair? bindings) (let ((temp (quasisyntax temp)))
(quasisyntax
(let ((,temp ,(cadar bindings)))
,(let-help (cdr bindings)
(cons temp temps)
(cons (caar bindings) variables))))))))
(let-help bindings '() '()))
(let-ordered ((x 1)
(y 2))
(+ x y)) ==> 3
We obtain the correct result, despite having used the same name
for the distinct temporaries, since each quasisyntax evaluation occurs
in its own hygienic context.
Notice that quasisyntax allows the following implementation of generate-temporaries:
(define (generate-temporaries lst)
(map (lambda (_) (quasisyntax temp))
lst))
To support macro-generating macros correctly, we have to keep the traditional
semantics for syntax. All
syntax evaluations occurring during a single macro invocation
occur in the same hygienic context:
(bound-identifier=? (syntax x) (syntax x)) ==> #tWe may then use the traditional Lisp techniques for splicing syntax into a generated macro, with quasisyntax in place of quasiquote and syntax in place of quote:
(define-syntax (macro-generate name id)
(quasisyntax
(define-syntax (,name)
(quasisyntax (let ((,(syntax ,id) 4)) ,(syntax ,id))))))
(macro-generate test z)
(test) ==> 4
As a bonus, this semantics makes it possible to define syntax-case
as a macro in our system.
We point out, though, that careless use of syntax
can lead to exactly the capture problems decribed above.
Indeed, if we had instead written (let ((temp (syntax temp))) ...in let-help, the macro would be wrong. This problem can be avoided by programmer discipline, restricting the use of syntax to the kind of essential splicing situations that occur in macro-generating macros.
(if-it 1 it 42) ==> 1We would also like to be able to compose unhygienic macros. In particular, we would like to be able to write macros when-it, if-flag-it and my-or in terms of if-it as follows:
(define-syntax (when-it condition consequent)
(quasisyntax
(if-it ,condition
,consequent
(if #f #f))))
(define-syntax (if-flag-it body else)
(quasisyntax
(if-it flag ,body ,else)))
(define-syntax (my-or expr1 expr2)
(quasisyntax
(if-it ,expr1 it ,expr2)))
We impose the following requirements on the semantics:
(when-it 42 it) ==> 42 (define flag 3) (if-flag-it it 'none) ==> 3 (my-or 2 it) ==> 2 (my-or #f it) ==> #fThe macro system described here has a primitive datum->syntax similar to that provided by syntax-case. However, as far as the author is aware, it is impossible to satisfy these four conditions using datum->syntax without code-walking. Furthermore, we wish to impose the following referential transparency conditions
(let ((it 1)) (if-it 42 it #f)) ==> 1 (let ((it 1)) (when-it 42 it)) ==> 1 (let ((it 1)) (my-or 2 it)) ==> 2 (note) (let ((it 1)) (my-or #f it)) ==> 1by analogy with the behaviour of
(let ((else #f)) (my-cond (else 2))) ==> unspecifiedTo satisfy these requirements, we provide a new primitive, make-capturing-identifier, that introduces an identifier which, when bound, will capture all free-identifier=? identifiers in its scope. With this primitive, the following implementation of if-it satisfies all the above requirements:
(define-syntax (if-it condition consequent alternative)
(let ((it (make-capturing-identifier (syntax here) 'it)))
(quasisyntax
(let ((,it ,condition))
(if ,it
,consequent
,alternative)))))
A similar idea has been proposed by Oleg Kiselyov in [2].
The denotation of the new identifier is determined by the syntactic environment of the first argument. This allows us fine control over what we mean by referential transparency. Compare for example the above with:
(define-syntax if-it
(lambda (_ condition consequent alternative)
(let ((it (make-capturing-identifier _ 'it)))
(quasisyntax
(let ((,it ,condition))
(if ,it
,consequent
,alternative))))))
(let ((it 1)) (if-it 42 it #f)) ==> 42
The primitive datum->syntax is still the appropriate primitive for introducing identifiers that should be captured by bound-identifier=? identifiers in surrounding binding forms. Comparing with the description of make-capturing-identifier above, we see that the one introduces identifiers that are the subject of capture, while the other introduces identifiers that should be the object of capture.
define-syntax
let-syntax
letrec-syntax
set-syntax!
syntax
quasisyntax
syntax-quote
identifier?
bound-identifier=?
free-identifier=?
literal-identifier=?
make-capturing-identifier
datum->syntax
syntax->datum
expand
syntax-debug
syntax-error
Syntax objects:
'() 1 #f '(1 2 3) (cons (syntax x) (vector 1 2 3 (syntax y))) (syntax (let ((x 1)) x)) (quasisyntax (let ((x 1)) ,(syntax x)))Symbols may not appear in syntax objects:
'(let ((x 1)) x) ==> not a syntax object
syntax: (DEFINE-SYNTAX var exp)
(DEFINE-SYNTAX (var . formals) exp1 exp ...)
The second variant is equivalent to
(DEFINE-SYNTAX var (lambda (dummy . formals) exp1 exp ...)).Exp may evaluate to a procedure, also called a transformer. When the expander encounters a macro invocation, the corresponding transformer is invoked on the input form as follows:
(apply transformer input-form)
Examples:
(define-syntax a #f)
(define-syntax my-let
(lambda form
(let ((bindings (cadr form))
(body (cddr form)))
(quasisyntax
((lambda ,(map car bindings) ,@body) ,@(map cadr bindings))))))
(define-syntax (my-let bindings . body)
(quasisyntax
((lambda ,(map car bindings) ,@body) ,@(map cadr bindings))))
syntax: (LET[REC]-SYNTAX ((var exp) ...) exp* ...)
(letrec-syntax
((my-or (lambda (_ . body)
(cond ((null? body) #f)
((null? (cdr body)) (car body))
(else
(quasisyntax
(let ((temp ,(car body)))
(if temp
temp
(my-or ,@(cdr body))))))))))
(let ((x #f)
(y 7)
(temp 8)
(let odd?)
(if even?))
(my-or x
(let temp)
(if y)
y))) ==> 7
(let ((x 'outer))
(let-syntax ((m (lambda (_) (syntax x))))
(let ((x 'inner))
(m)))) ==> outer
(let-syntax ((when (lambda (_ test . body)
(quasisyntax
(if ,test
(begin . ,body))))))
(let ((if #t))
(when if (set! if 'now))
if)) ==> now
The language for expanding further nested macros is incrementally
extended, as the following example shows:
(let ((x 1))
(let-syntax ((m (lambda (_) (syntax (syntax x)))))
(let-syntax ((n (lambda (_) (m))))
(n))))
==> 1
syntax: (SET-SYNTAX! var exp)
(define-syntax (test) (syntax (syntax 'a))) (set-syntax! test (lambda (_) (test))) (test) ==> a
syntax: (SYNTAX template)
During the course of a single macro invocation, syntax acts like a one-to-one mathematical function on identifiers: Two identifiers introduced via syntax expressions will be bound-identifier=? if and only if the syntax expressions were evaluated during the same macro invocation and the original identifiers in the templates were bound-identifier=?.
Identifiers that are bound-identifier=? are required to have the same denotation. Any attempt to break this invariant should cause an error to be signaled.
(cons (syntax x)
(let ((x 1)) (syntax x))) ==> error
Syntax differs from the identically named form in the syntax-case
system in that here we have no concept of pattern variable substitution.
Instead, existing syntax objects can be inserted in new syntax objects using
quasisyntax with unquote or
unquote-splicing, using cons, list,
vector, ...
Syntax-case can be implemented as a macro on top of the current system and is available as a library.
Examples:
(bound-identifier=? (syntax x) (syntax x)) ==> #t
(define-syntax (test)
(quasisyntax
(let ((,(syntax x) 1)) ,(syntax x))))
(test) ==> 1
In the following example, (m) expands to (syntax x), where
x denotes the outer binding. Although the expanded
(syntax x) occurs in the syntactic environment of the middle binding,
the fresh identifier resulting from evaluating it will denote the same thing as the
identifier x in the template. It will therefore also refer to the outer binding.
(let ((x 'outer))
(let-syntax ((m (lambda (_) (syntax (syntax x)))))
(let ((x 'middle))
(let-syntax ((n (lambda (_) (m))))
(let ((x 'inner))
(n)))))) ==> outer
The fact that syntax preserves bound-identifier=? equivalence
during the course of the macro invocation is useful for
writing macro-generating macros using the traditional Lisp techniques for
splicing syntax into a generated macro (with quasisyntax instead of
quasiquote and syntax in place of quote):
(define-syntax (macro-generate name id)
(quasisyntax
(define-syntax (,name)
(quasisyntax
(let ((,(syntax ,id) 4)) ,(syntax ,id))))))
(macro-generate test z)
(test) ==> 4
Note that syntax does not unify identifiers previously distinct in the sense
of bound-identifier=? occurring
in template even if they
have the same symbolic name:
(let ((x 1))
(let-syntax ((m (lambda (_) (syntax (syntax x)))))
(let ((x 2))
(let-syntax ((n (lambda (_)
(quasisyntax
(let-syntax ((o (lambda (_)
(,(syntax syntax)
(,(syntax list)
,(m)
,(syntax x))))))
(o))))))
(n))))) ==> (1 2)
syntax: (QUASISYNTAX template)
As in the case of syntax, identifiers appearing in the quoted part of the template are replaced by fresh identifiers bound to the denotations of the original identifiers in the syntactic environment in which the template occurred.
However, quasisyntax differs from syntax in that two identifiers introduced by quasisyntax will be bound-identifier=? only if they are introduced during the same evaluation of a quasisyntax expression, and the original identifiers in the template were bound-identifier=?.
Similarly to quasiquote, values may be inserted into the template using unquote and unquote-splicing. To make nested splicing behave in a more useful way, the R5RS-compatible extension described in appendix B of Bawden's paper [10] is recommended.
(bound-identifier=? (quasisyntax x) (quasisyntax x)) ==> #f
(define-syntax (test)
(quasisyntax
(let ((,(quasisyntax x) 1)) ,(quasisyntax x))))
(test) ==> reference to undefined identifier
syntax: (SYNTAX-QUOTE template)
(let-syntax ((m (lambda (_ x)
(quasisyntax
(let-syntax ((n (lambda (_ y)
(quasisyntax
(let ((,y 1))
,(syntax-quote ,x))))))
(n ,x))))))
(m z)) ==> 1
procedure: (IDENTIFIER? obj)
procedure: (BOUND-IDENTIFIER=? obj1 obj2)
(FREE-IDENTIFIER=? obj1 obj2)
(LITERAL-IDENTIFIER=? obj1 obj2)
Identifiers are literal-identifier=? if they are free-identifier=? or if they both refer to toplevel bindings and have the same symbolic name. This primitive should be used to reliably identify literals (such as else in cond) even if they occur in a different module from the macro definition.
Identifiers are bound-identifier=? if a binding of one would capture references to the other in the scope of the binding. Two identifiers are bound-identifier=? only if they are present in the same toplevel expression in the original program, if they were introduced by syntax during the same macro-invocation, or if they were introduced during a single evaluation of a quasisyntax expression. In addition, datum->syntax may create identifiers that are bound-identifier=? to previously introduced identifiers.
These procedures return #f if either argument is not an identifier.
procedure: (MAKE-CAPTURING-IDENTIFIER template-identifier symbol)
(define-syntax (if-it condition consequent alternative)
(let ((it (make-capturing-identifier (syntax here) 'it)))
(quasisyntax
(let ((,it ,condition))
(if ,it
,consequent
,alternative)))))
(if-it 42 it #f) ==> 42
(let ((it 1)) (if-it 42 it #f)) ==> 1
The following examples illustrate how the behaviour
of non-hygienic macros may be controlled by the template-identifier
argument.
(define-syntax if-it
(lambda (_ condition consequent alternative)
(let ((it (make-capturing-identifier _ 'it)))
(quasisyntax
(let ((,it ,condition))
(if ,it
,consequent
,alternative))))))
(let ((it 1)) (if-it 42 it #f)) ==> 42
(let ((y 'outer))
(let-syntax ((m (lambda (_) (make-capturing-identifier (syntax here) 'y))))
(let ((y 'inner))
(m)))) ==> outer
(let ((y 'outer))
(let-syntax ((m (lambda (_ . rest)
(let ((y (make-capturing-identifier (syntax here) 'y)))
(quasisyntax
(let ((,y 'inner)) . ,rest))))))
(m y)))
==> inner
(let ((y 'outer))
(let-syntax ((m (lambda (_ . rest)
(let ((y (make-capturing-identifier (syntax here) 'y)))
(quasisyntax
(let ((,y 'inner)) . ,rest))))))
(let ((y 'more))
(m y))))
==> more
procedure: (DATUM->SYNTAX template-identifier obj)
If template-identifier is a capturing identifier, the symbols in obj will also be converted to capturing identifiers.
This procedure has the same meaning as datum->syntax-object in the syntax-case system [6, 7].
procedure: (SYNTAX->DATUM syntax-object)
procedure: (EXPAND syntax-object)
(expand (syntax (let ((x 1)) x))) ==> ((lambda (@x5872) @x5872) 1)
procedure: (SYNTAX-DEBUG syntax-object)
(syntax-debug (syntax (let ((x 1)) y))) ==> (let ((x#top 1)) y#top)
procedure: (SYNTAX-ERROR obj ...)
Portability hooks are provided for Schemes that lack either of these additional primitives. For example, to run the code on Gambit, unquote the definition of gensym provided.
The implementation was strongly influenced by the explicit renaming system [8, 11].
We use an imperative hygiene algorithm that is eager, has linear complexity, and is very fast. This is achieved by having bound-identifier=? identifiers share a location, so that alpha substitutions can be done by a simple imperative update of an identifier and no additional work is required to propagate substitutions or environments to leaves. In addition, source-object correlation information is not stored in syntax objects, but tracked independently, which makes it possible to represent syntax objects as ordinary s-expressions.
During the draft period, the reference implementation will be available here.
[1] André van Tonder - Simple macros and simple modules
http://www.het.brown.edu/people/andre/macros/index.htm
[2] Oleg Kiselyov - Message on comp.lang.scheme:
http://groups-beta.google.com/group/comp.lang.scheme/msg/9c7da84c5496d1f3
[3] Marcin 'Qrczak' Kowalczyk - Message on comp.lang.scheme:
http://groups-beta.google.com/group/comp.lang.scheme/msg/b7075e4ca751dbdb
[4] Ben Rudiak-Gould - Message on comp.lang.scheme:
http://groups-beta.google.com/group/comp.lang.scheme/msg/180c7627853c288e
[5] Matthew Flatt - Composable and Compilable Macros You Want it When?
[6] R. Kent Dybvig - Schez Scheme user's guide:
http://www.scheme.com/csug/
[7] Robert Hieb, R. Kent Dybvig and Carl Bruggeman
- Syntactic Abstraction in Scheme.
http://library.readscheme.org/page3.html
[8] William D. Clinger - Hygienic macros through explicit renaming.
http://library.readscheme.org/page3.html
[9] Eugene E. Kohlbecker, Daniel P. Friedman, Matthias Felleisen and Bruce F. Duba
- Hygienic macro expansion
http://library.readscheme.org/page3.html
[10] Alan Bawden - Quasiquotation in Lisp
http://citeseer.ist.psu.edu/bawden99quasiquotation.html
[11] Richard Kelsey and Jonathan Rees - The Scheme 48 implementation
http://s48.org/
Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:
The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.