Re: macros again

[will@cs.uoregon.edu]

In response to Jeff Dalton's questions about the fate of syntactic
closures:

    It was decided to take two people from each side, and lock the four
    of them in a room, without any lunch, until they came to agreement.
    The expectation was, I think, that the result would look like
    extend-syntax on top and syntactic closures underneath.

In my opinion, the key to unifying EXTEND-SYNTAX with syntactic
closures was Kohlbecker's algorithm for hygienic macro expansion.
In my opinion, one of the reasons this has taken so long is that
the macro committee did not include any advocates of Kohlbecker's
algorithm.

    Finally, we heard some news.  Syntactic closures had been abandoned,
    and we were to get something else instead.

I regard the forthcoming proposal as a fusion of syntactic closures
with Kohlbecker's algorithm for hygienic macro expansion, accompanied
by a high-level syntax that resembles EXTEND-SYNTAX.  I therefore
would not say that syntactic closures have been abandoned.  The thing
that had to be abandoned is the idea that EXTEND-SYNTAX could easily
be layered on top of syntactic closures as they were described by
Bawden and Rees in the 1988 L&FP.

                                                It seemed that in some
    case (not described), it was impossible to figure out the status
    of some names at the right time (or something like that).

Consider the following definition of LET:

(define-syntax let
  (syntax-rules ()
    ((let ((?name ?val) ...) ?body)
     ((lambda (?name ...) ?body) ?val ...))))

If this high-level definition were compiled into syntactic closures,
then the ?val expressions would have to be closed in the syntactic
environment of a use of the macro, but the ?body must not be closed
in that same syntactic environment because its references to the
?names must be left free.  It is impossible to make such distinctions
reliably and automatically at macro definition time or when a use of
the macro is expanded into code that must be further macro-expanded.
(The proof is left to the reader.  Hint: assume that the pattern
language is powerful enough to have an undecidable halting problem.)

This doesn't mean we can't have a reliable and automatic macro
system while retaining a simple high-level syntax.  All it means
is that we're not going to get such a system by compiling high-level
macros to the particular semantics of syntactic closures that was
described by Bawden and Rees at the 1988 L&FP.  In other words, the
macro committee (actually Chris Hanson, who was not on the original
committee) found a bug in the expected implementation of its mission,
not a bug in the mission itself.

Jonathan Rees and I will be presenting a paper at POPL that describes
an algorithm that works.  The algorithm uses syntactic environments,
but it does not use syntactic closures as described by Bawden and
Rees because the fundamental problem is that we cannot reliably
construct the correct syntactic closure until macro expansion is
complete.  The algorithm reproduces the effect of syntactic closures,
however, by using a modified form of Kohlbecker's algorithm to defer
the choice of syntactic environment until macro expansion is locally
complete.

Other algorithms are possible.  For example, I have heard an
objection to our algorithm on the grounds that it relies on the
correctness of alpha conversion to express its result.  (Although
alpha conversion preserves the meanings of Scheme programs, it may
not preserve the meanings of programs written in some extensions
of Scheme.)  A few sentences in the draft of the macro proposal
that Dybvig referred to are indeed written as though the result
is expressed using alpha conversion, and Dybvig & Hieb's reference
implementation probably uses alpha conversion (I haven't studied
it yet), but I do not believe there is anything in the proposal
that would prevent its adoption by implementations that have
extended Scheme in ways that are incompatible with alpha
conversion.  In other words, the macro proposal specifies a
semantics but does not describe any particular way to implement
it.

    I was a bit puzzled by this....extend-syntax and syntactic closures
    had gone in on a fairly equal footing.  If they were incompatible,
    why was it that one got dropped and not the other?

If two things are truly incompatible, then the only alternative
to dropping one and not the other is to drop both.

I don't think syntactic closures were dropped so much as fixed.
EXTEND-SYNTAX could be saved by fixing syntactic closures.  We
saw no reasonable way to save the 1988 version of syntactic
closures by changing EXTEND-SYNTAX.

William Clinger
non-member, Scheme macro committee