RE: lisp v. scheme macros

["Shriram Krishnamurthi" <sk@cs.brown.edu>]

Michael Vanier asked:

> As far as I know, virtually all scheme implementations support lisp style
> macros (with some minor name changes e.g. defmacro -> define-macro), but
> the only scheme implementation I know of that supports full hygienic R5RS
> scheme macros is Chez Scheme.  Mzscheme has nearly full support as an
> add-on library, and I believe a similar situation exists in
> Guile.  I don't
> think MIT scheme has R5RS macros at all.  This leads me to wonder if there
> is some major difficulty involved in their implementation, or else if
> people simply don't need hygienic macros for anything they can't do with
> traditional (non-hygienic macros).  Any thoughts on this from our local
> macro wizards?

There's a long and sordid history here.  Please note that everything
that follows is purely personal speculation.

In the 80s, back when people really cared about this stuff, there were
two major macro camps.  The MIT macrologists wanted to preserve as
much as possible of the Lisp world, with its free-form macro system
whose language was the same, powerful one as that target language --
namely, Lisp or Scheme itself.  This led to the invention (I'm
assuming a causality here that may not be strictly true, though it
seems quite likely) of quasiquote notation as a way of writing macros
"by example" ... except all the splicings spoiled the smooth harmony
of this scheme.  And it still left open the problem of accidental
variable capture.

The other camp, at Indiana, tackled both problems head-on.  Eugene
Kohlbecker and the rest of the IU cast addressed both the variable
capture problem (hygiene) and the pattern-matching problem (macro by
example, or MBE).  And they pasted them together into one harmonious
whole.  What's not to like?

As someone who *wasn't* at Indiana in the 80s, I see a few problems.

1. The original hygiene algorithm was quadratic in expression size.

2. The original presentation of hygiene was needlessly complex.

3. The original hygiene presentation didn't provide a clean way of
   performing intentional variable capture.

4. The original MBE proposal gave no clean way of escaping into a more
   powerful host language, computing phrases, and injecting them into
   the expression.  (We're still stuck with this legacy in
   SYNTAX-RULES; as a symptom, rather than a solution, see the paper
   by Hillsdale in last year's Scheme workshop.)

5. The two mechanisms -- variable capture and phrase injection weren't
   integrated at all smoothly.

The MIT folks, unhappy at the loss of a powerful Lisp-like language
for expressing transformations, rejected the entire Indiana stable.
They thought hard about name capture and came up with syntactic
closures.  They posited that syntactic closures, a mechanism they
claimed was easier to understand, could form a basis for (they
claimed) the harder-to-understand Indiana mechanisms.

Fortunately, this mess got resolved before macro research became truly
unpopular.  Hanson showed that syntactic closures couldn't express the
Indiana mechanisms.  Clinger and Rees (?) made the quadratic algorithm
linear.  And finally, Dybvig, Hieb and Bruggeman's SYNTAX-CASE
provided an excellent solution to the problem of computing and
injecting phrases into expansion.  Their solution is both powerful and
elegant: it keeps expressions and Scheme values in separate type
spaces, and provides injections and projections in the two directions.

To a sociologist of science, the 80s and early 90s macro papers make
for amusing reading.  You would be surprised at the number of papers
that claim "Xs proposal, while not without merit, is simply too hard
to understand", only to follow it up with an equally complex proposal
of its own.  Perhaps all the sniping wasted time; on the other hand,
maybe it got the creative juices flowing.  In the end, though, it did
result in some excellent mechanisms to solve what must have seemed
like a pretty intractable problem at the start.

Shriram