\documentstyle{acmconf}

% JAR changes 10-22-90:
%  Deleted occurrences of ``perfect'' and ``perfectly''
%  Fixed ...*5 problem in discriminant example
%  Reworded to avoid ``she''
%  Flushed ``seem to''
%  capture of free variable *references*
\arraycolsep 0.2em

\title{Macros That Work}

\author{William Clinger\\
        Department of Computer Science \\
        University of Oregon 
 \and   Jonathan Rees \\
        Artificial Intelligence Laboratory \\
        Massachusetts Institute of Technology
}
\sloppy
\renewcommand{\textfraction}{.1}
\renewcommand{\topfraction}{.9}
\renewcommand{\floatpagefraction}{.8}
\renewcommand{\dbltopfraction}{.9}
\renewcommand{\dblfloatpagefraction}{.8}

% Here's how we did inference rules in 6.821.  It's simpler than I
% remember it being.  This is LaTeX, not TeX.

% The first argument is the IF part of the rule, the second is the
% THEN part.
\newcommand{\malign}[1]{\begin{array}{rcl}#1\end{array}}
\newcommand{\infrule}[2]{\malign{#1} \over \malign{#2}}
\newcommand{\mword}[1] {\hbox {\sl #1\/}}
\newcommand{\rwlabel}[1]{[\mword{#1}]}
\newcommand{\rwaxiom}[2]{$$#2\eqno{\rwlabel{#1}}$$}
\newcommand{\rwrule}[3]{$$\infrule{#2}{#3}\eqno{\rwlabel{#1}}$$}
\newcommand{\rwabove}[2]{{\displaystyle #1}\atop{\displaystyle #2}}

% The \rwrule macro wants three arguments: antecendent, consequent, and
% a name for the rule, which appears as a slanted-font [name] to the
% right of the rule.  Use \rwabove for multiple antecedents.  \infrule
% is the same except that there's no name; also perhaps it needs to be
% inside math display mode, but I can't tell.  I guess we'll have to
% experiment.  Since all of these arguments were in math mode, we did a
% lot of (macroized) \hbox\{tt ...\}'s to get back into horizontal mode
% code font.

% The \infrule, \rwlabel, and \rwabove commands need to be inside
% math display mode; the \rwaxiom and \rwrule commands do not.
% Go figure.

\def\code#1{{\hbox{\tt #1}}}
\def\meta#1{{\hbox{\rm\bf #1}}}
\def\domain#1{{\hbox{\rm #1}}}
\def\function#1{{\hbox{\it #1\,}}}
\def\constant#1{{\hbox{\it #1}}}

\def\justifies{\vdash}
\def\expandsto{\rightarrow}

\def\lookup{\function{lookup}}
\def\bind{\function{bind}}
\def\divert{\function{divert}}
\def\transcribe{\function{transcribe}}
\def\match{\function{match}}
\def\rewrite{\function{rewrite}}

\newcommand{\pair}[2]{\langle#1,#2\rangle}

%\newenvironment{scheme}{\begin{verbatim}}{\end{verbatim}}

\def\referto#1{\cite{#1}}


\begin{document}

\maketitle

\begin{abstract}

This paper describes a modified form of Kohlbecker's algorithm for
reliably hygienic (capture-free) macro expansion in block-structured
languages,
where macros are source-to-source transformations specified using a
high-level pattern language.  Unlike previous
algorithms, the modified algorithm runs in linear instead of quadratic
time, copies few constants, does not assume that syntactic
keywords (e.g.\ \code{if}) are reserved words, and allows local
(scoped) macros to refer to lexical variables in a referentially
transparent manner.

Syntactic closures have been advanced as an alternative to
hygienic macro expansion.  The problem with syntactic closures
is that they are inherently low-level and therefore difficult
to use correctly, especially when syntactic keywords are not
reserved.
% Furthermore
It is impossible to construct a
pattern-based, automatically hygienic macro system on top of
syntactic closures because the pattern interpreter must be able
to determine the syntactic role of an identifier (in order to
close it in the correct syntactic environment) before macro
expansion has made that role apparent.

Kohlbecker's algorithm may be viewed as a book-keeping technique
for deferring such decisions until macro expansion is locally
complete.  Building on that insight, this paper unifies and
extends the competing paradigms of hygienic macro expansion
and syntactic closures to obtain an algorithm that combines
the benefits of both.

Several prototypes of a complete macro system for Scheme have
been based on the algorithm presented here.

\end{abstract}


\section{Introduction}

A macro is a source-to-source program transformation specified
by programmers using a high-level pattern language.  Macros add
a useful degree of syntactic extensibility to a programming
language, and provide a convenient way to abbreviate common
programming idioms.

Macros are a prominent component of several popular programming
languages, including C \referto{assemblylanguage}
and Common Lisp \referto{CLtL}.  The macro systems
provided by these languages suffer from various problems that make
it difficult and in many cases impossible to write macros that work
correctly regardless of the context in which the macros are used.
It is widely believed that these problems result from the very
nature of macro processing, so that macros are an inherently
unreliable feature of programming languages \referto{brown}.

That is not so.  A macro system based upon the algorithm described in
this paper allows reliable macros to be written, and is simple to use.
The algorithm is nearly as fast as algorithms in current use.
% used for macro processing in current programming languages.

%Where did it come from?
%Block-structured languages
%fully block-structured most useful
%FOR example

This introduction illustrates several problems
common to existing macro systems, using examples written in
C and Scheme \referto{scheme}.
With one exception, all of these problems are solved
automatically and reliably by the algorithm presented in this paper.

The original preprocessor for C allowed the body of a macro
definition to be an arbitrary sequence of
characters.  It was therefore possible for a macro to expand into
part of a token.  For example,
\begin{verbatim}
  #define foo "salad
  printf(foo bar");
\end{verbatim}
would expand into \code{printf("salad bar");}.  We may say that
this macro processor {\em failed to respect the integrity of
lexical tokens}.
This behavior caused so many problems that it has been banished
from ANSI C except when special operators are used for the
specific purpose of violating the integrity of lexical tokens.

Similar problems arise in macro systems that allow the body
of a macro to expand into an arbitrary sequence of tokens.
For example,
\begin{verbatim}
  #define discriminant(a,b,c) b*b-4*a*c
    2*discriminant(x-y,x+y,x-y)*5
\end{verbatim}
expands into \code{2*x+y*x+y-4*x-y*x-y*5}, which is then parsed
as 
\begin{verbatim}
  (2*x)+(y*x)+y-(4*x)-(y*x)-(y*5)
\end{verbatim}
instead of the more plausible
\begin{verbatim}
  2*(x+y)*(x+y)-4*(x-y)*(x-y)*5.
\end{verbatim}
We may say that systems such as the ANSI C preprocessor
{\em fail to respect the structure of expressions}.
Experienced C programmers know they must defend against this
problem by placing parentheses around the macro body and
around all uses of macro parameters, as in
\begin{verbatim}
  #define discriminant(a,b,c) ((b)*(b)-4*(a)*(c))
\end{verbatim}
This convention is not enforced by the C language, however, so
the author of a macro who neglects this precaution is likely to
create subtle bugs in programs that use the macro.

Another problem with the \code{discriminant} macro occurs when
the actual parameter for \code{b} is an expression that has a
side effect, as in \code{discriminant(3,x--,2)}.  Of the problems
listed in this introduction, the inappropriate duplication of
side effects is the only one that is not solved automatically
by
% a macro system based on
our algorithm.

One can argue that actual parameter expressions
should not have side effects, but this argument runs counter to
the C culture.  In a fully block-structured language such as
Scheme, the author of a macro can defend against actual parameters
with side effects by introducing a local variable that is
initialized to the value obtained by referencing the macro parameter.
In the syntax we adopt for this paper, which differs slightly from
syntax that has been proposed
for Scheme \referto{r4rs}, a correct
version of the \code{discriminant} macro can be defined by
\begin{verbatim}
  (define-syntax discriminant
    (syntax-rules
      ((discriminant ?a ?b ?c)
       => (let ((temp ?b))
            (- (* temp temp) (* 4 ?a ?c))))))
\end{verbatim}
Unfortunately there is no equivalent to this macro in C, since
blocks are not permitted as expressions.

From the above example we see that macros must be able to
introduce local variables.  Local variables, however, make
macros vulnerable to accidental conflicts of names, as in
\begin{verbatim}
  #define swap(v,w) {int temp=(v); \
       (v) = (w); (w) = temp;}
    int temp = thermometer();
    if (temp < lo_temp) swap(temp, lo_temp);
\end{verbatim}
Here the \code{if} statement {\it never} exchanges the values of
\code{temp} and \code{lo\_temp}, because of an accidental name clash.
The macro writer's usual defense is to use an obscure name and
{\it hope} that it will not be used by a client of the macro:
\begin{verbatim}
 #define swap(v,w) {int __temp_obscure_name=(v); \
      (v) = (w); (w) = __temp_obscure_name;}
\end{verbatim}
Even if the macro writer is careful to choose an obscure name, this
defense is less than reliable.  For example, the macro
may be used within some other use of a macro whose author happened
to choose the same obscure name.  This problem can be especially
perplexing to authors of recursive macros.

The most troublesome name clashes arise not from variables local
to a macro, but from the very common case of a macro that needs
to refer to a global variable or procedure:
\begin{verbatim}
  #define complain(msg) print_error(msg);
    if (printer_broken()) {
        char *print_error = "The printer is broken";
        complain(print_error);
        }
\end{verbatim}
Here the name given to the error message conflicts with the name
of the procedure that prints the message.  In this example the
compiler will report a type error, but programmers are not
always so lucky.

In most macro systems there is no good way to work around this
problem.  Programs would become less readable if obscure names
were chosen for global variables and procedures, and the author
of a macro probably does not have the right to choose those names
anyway.  Requiring the client of each macro to be aware of the
names that occur free in the macro would defeat the purpose of
macros as syntactic abstractions.

The examples above show that at least two classes
of inadvertent name conflicts can be created by macro processors
that
{\em fail to respect the correlation between bindings and
uses of names}.  One class involves macros that introduce
bound (local) variables.  Another class involves macros that
contain free references to variables or procedures.

{\em Hygienic macro expansion} \referto{kohlbecker} is a
technology that maintains the correlation between bindings
and uses of names, while respecting the structure of tokens
and expressions.
The main problem with hygienic macro expansion has been that
the algorithms have required
$O(n^2)$ time, where $n$ is the time required by naive macro
expansion as in C or Common Lisp.  Although this is the worst
case, it sometimes occurs in practice.

The purpose of this paper is to build on Kohlbecker's algorithm
for hygienic macro expansion by incorporating ideas developed
within the framework of syntactic closures \referto{bawden}.
Our result is an efficient and more complete solution to the
problems of macro processing.  Our algorithm runs in $O(n)$
time and solves several additional problems associated with
local (scoped) macros that had not been addressed by hygienic
macro expansion.  In particular, our algorithm supports
referentially transparent local macros as described below.

If macros can be declared within the scope of lexical variables,
as in Common Lisp, then a seemingly new set of problems arises.
We would
like for free variables that occur on the right hand side of a
rewriting rule for a macro to be resolved in the lexical
environment of the macro definition instead of being resolved
in the lexical environment of the use of the macro.  Using
\code{let-syntax} to declare local macros, for example,
it would be nice if
\begin{verbatim}
  (let-syntax ((first
                (syntax-rules
                  ((first ?x) => (car ?x))))
               (second
                (syntax-rules
                  ((second ?x) => (car (cdr ?x))))))
    (let ((car "duesenberg"))
      (let-syntax ((classic
                    (syntax-rules
                      ((classic) => car))))
        (let ((car "yugo"))
          (let-syntax ((affordable
                        (syntax-rules
                          ((affordable) => car))))
            (let ((cars (list (classic)
                              (affordable))))
              (list (second cars)
                    (first cars))))))))
\end{verbatim}
could be made to evaluate to \code{("yugo" "duesenberg")}.
This would be the case if the references to \code{car}
that are introduced by the \code{first}, \code{second},
\code{classic}, and \code{affordable} macros referred
in each case to the \code{car} variable within whose
scope the macro was defined.  In other words, this
example would evaluate to \code{("yugo" "duesenberg")}
if local macros were {\em referentially transparent}.

Our algorithm supports referentially transparent local macros.
We should note that these macros may not be referentially
transparent in the traditional sense because of side effects
and other problems caused by the programming language whose
syntax they extend, but we blame the language for this and
say that the macros themselves are referentially transparent.

Now consider the following Scheme code:
\begin{verbatim}
  (define-syntax push
    (syntax-rules
      ((push ?v ?x) => (set! ?x (cons ?v ?x)))))

  (let ((pros (list "cheap" "fast"))
        (cons (list)))
    (push "unreliable" cons))
\end{verbatim}
It is easy to see that
the \code{cons} procedure referred to within the macro
body is different from the \code{cons} variable within whose
scope the macro is used.
Through its reliance on the meaning of the syntactic keyword
\code{set!}, the \code{push} macro also
illustrates yet a third class of inadvertent name conflicts.
If syntactic keywords are not reserved, then the
\code{push} macro might be used within the scope of a local
variable or macro named \code{set!}.

We can now identify four classes of {\em capturing}
problems.  The first class involves inadvertent
capturing by bound variables introduced by a macro.  The
second class involves the inadvertent capture of free
variable references introduced by a macro.  The third is like the
first, but involves inadvertent capturing by bindings of
syntactic keywords (i.e.\ local macros)
introduced by a macro.  The fourth is like the second,
but involves the inadvertent capture of references
to syntactic keywords introduced by a macro.

% Maybe this stuff about syntactic closures should go into
% a separate section.

Syntactic closures \referto{bawden} have been advanced
as an alternative to hygienic macro expansion.  Syntactic
closures can be used to eliminate all four classes of
capturing problems, and can support referentially
transparent local macros as well.  Why then have we
bothered to develop a new algorithm for hygienic macro
expansion, when syntactic closures also run in linear
time and solve all the problems that are solved by our
algorithm?

The problem with syntactic closures is that they do not
permit macros to be defined using the kind of
high-level pattern language that is used in C and is
proposed for Scheme \referto{hanson}.  The difficulty is that a
pattern interpreter that uses syntactic closures must be
able to determine the syntactic role of an identifier (to
know whether to close over it, and if so to know the
correct syntactic environment) before macro expansion has
made that role apparent.  Consider a simplified form of
the \code{let} macro, which introduces local variables:
\begin{verbatim}
  (define-syntax let
    (syntax-rules
      ((let ((?name ?val)) ?body)
       => ((lambda (?name) ?body) ?val))))
\end{verbatim}
When this macro is used, the \code{?val} expression must
be closed in the syntactic environment of the use, but the
\code{?body} cannot simply be closed in the syntactic
environment of the use because its references to
\code{?name} must be left free.  The pattern interpreter
cannot make this distinction unaided until the lambda
expression is expanded, and even then it must somehow
remember that the bound variable of the lambda expression
came from the original source code and must therefore be
permitted to capture the references that occur in
\code{?body}.  Recall from the \code{swap} example that
a reliable macro system must {\it not} permit bound
variables introduced by macro expansion
to capture such references.

Kohlbecker's algorithm can be viewed as a book-keeping
technique for deferring all such decisions about the syntactic
roles of identifiers until macro expansion is locally
complete and has made those roles evident.  Our algorithm
is therefore based on Kohlbecker's but incorporates
the idea of syntactic environments, taken from the work
on syntactic closures, in order to achieve referentially
transparent local macros.

The question arises:  Don't the capturing problems occur
simply because we use names instead of pointers, and trees instead
of dags?  If we first parsed completely before doing macro
expansion, could we not replace all occurrences of names by
pointers to symbol table entries and thereby eliminate the
capturing problems?

The answer is no.  One of the most important uses of
macros is to provide syntactically convenient binding 
% and control 
abstractions.
% {\it }, by which we mean similar in
%form to the primitive binding and control abstractions of the
%language.
% We do not want to have to mark all binding
% occurrences {\em lexically} just so the macro
% processor can distinguish references from bindings.
The distinction between binding occurrences and other uses
of identifiers should be determined by a particular
syntactic abstraction, not predetermined by the parser.
Therefore, even if we were to parse actual parameters into expression
trees before macro expansion,
the macro processor still could not
reliably distinguish bindings from uses and correlate them
until macro expansion is performed.

\begin{figure}
%
% Syntactic environments.
%
\begin{eqnarray*}
\domain{env}        &=& \domain{identifier} \rightarrow \domain{denotation}\\
\domain{denotation} &=& \domain{special} + \domain{macro} + \domain{identifier}\\
\domain{special}    &=& \left\{ \constant{lambda}, \constant{let-syntax} \right\}\\
\domain{macro}      &=& (\domain{pattern} \times \domain{rewrite})^+
                        \times \domain{env}
\end{eqnarray*}
%
\begin{eqnarray*}
\constant{ident}     &\in& \domain{env}\\
\constant{lookup} &\in& \domain{env} \times \domain{identifier}
                        \rightarrow \domain{denotation}\\
\constant{bind}   &\in& \domain{env} \times \domain{identifier} \times
                        \domain{denotation} \rightarrow \domain{env}\\
\constant{divert} &\in& \domain{env} \times \domain{env}
                        \rightarrow \domain{env}
\end{eqnarray*}
%
\begin{eqnarray*}
\lookup(\constant{ident}, x) &=& x\\
\lookup(\bind(e, x, v), x) &=& v\\
\lookup(\bind(e, x, v), y) &=& \lookup(e, y)
    \quad\quad \hbox{if $x \not= y$}\\
\divert(e, \constant{ident}) &=& e\\
\divert(e, \bind(e^\prime, x, v)) &=& \bind(\divert(e, e^\prime), x, v)
\end{eqnarray*}
%\vskip 8pt
\caption{Syntactic environments.\label{environments}}
\end{figure}

Consider an analogy from lambda calculus.  In reducing an
expression to normal form by textual substitution, it is
sometimes necessary to rename variables as part of a beta
reduction.  It doesn't work to perform all the (naive) beta
reductions first, without renaming, and then to perform all
the necessary alpha conversions; by then it is too late.
Nor does it work to do all the alpha conversions first, because
beta reductions introduce new opportunities for name clashes.
The renamings must be {\it interleaved} with the (naive)
beta reductions, which is the reason why the notion
of substitution required by the non-naive beta rule is so
complicated.

\begin{figure*}
%
% Inference rules for modified Kohlbecker algorithm
%

\rwrule{variable references}
{\lookup(e, \meta{x}) \in \domain{identifier}}
{e \justifies \meta{x} \expandsto \lookup(e, \meta{x})}

\rwrule{procedure abstractions}
{\rwabove{\lookup(e, \meta{k}_0) = \constant{lambda}}
         {\bind(e, \meta{x}, \meta{x}^\prime) \justifies \meta{E}
                   \expandsto \meta{E}^\prime \;
                   \hbox{(where $\meta{x}^\prime$ is a fresh identifier)}}}
{e \justifies \code{($\meta{k}_0$ (\meta{x}) \meta{E})} \expandsto
 \code{(lambda ($\meta{x}^\prime$) $\meta{E}^\prime$)}}

%\hskip 144pt(where $\meta{x}^\prime$ is a fresh identifier)

\rwrule{procedure calls}
{e \justifies \meta{E}_0 \expandsto \meta{E}_0^\prime, \;\;
 e \justifies \meta{E}_1 \expandsto \meta{E}_1^\prime}
{e \justifies \code{($\meta{E}_0$ $\meta{E}_1$)} \expandsto
 \code{($\meta{E}_0^\prime$ $\meta{E}_1^\prime$)}}

\rwrule{macro abstractions}
{\rwabove{\lookup(e, \meta{k}_0) = \constant{let-syntax}}
         {\bind(e, \meta{k}, \pair{\tau}{e}) \justifies
          \meta{E} \expandsto \meta{E}^\prime}}
{e \justifies \code{($\meta{k}_0$ ((\meta{k} $\tau$)) \meta{E})}
 \expandsto \meta{E}^\prime}

% \code{(\meta{k} \meta{E} $\ldots$)}

\rwrule{macro calls}
{\rwabove{\lookup(e, \meta{k}) = \pair{\tau}{e^\prime}}
 {\rwabove{\transcribe(\code{(\meta{k} $\ldots$)}, \tau, e, e^\prime) =
  \pair{\meta{E}}{e^{\prime\prime}}}
  {e^{\prime\prime} \justifies \meta{E} \expandsto \meta{E}^\prime}}}
{e \justifies \code{(\meta{k} $\ldots$)} \expandsto \meta{E}^\prime}
%\vskip 12pt
\caption{The modified Kohlbecker algorithm.\label{algorithm}}
\end{figure*}

% End of inference rules for modified Kohlbecker algorithm.

\begin{figure*}
\vspace*{6ex}
%
% Definition of transcribe.
%

% \meta{E} -> \code{(\meta{k} \meta{A} $\ldots$)}
%          or \code{( \meta{A} $\ldots$)}

$$\infrule
{\rwabove
 {\match(\meta{E}, \pi, e_{{\it use}}, e_{{\it def}}) = \constant{nomatch}}
 {\transcribe(\meta{E}, \tau^\prime, e_{{\it use}}, e_{{\it def}}) =
  \pair{\meta{E}^\prime}{e^\prime}}}
{\transcribe(\meta{E}, \pair{\langle \pi}{\rho}, \tau^\prime \rangle,
 e_{{\it use}}, e_{{\it def}}) = \pair{\meta{E}^\prime}{e^\prime}}$$

$$\infrule
{\rwabove
 {\match(\meta{E}, \pi, e_{{\it use}}, e_{{\it def}}) = \sigma}
 {\rewrite(\rho, \sigma, e_{{\it def}}) = \pair{\meta{E}^\prime}{
  e_{{\it new}}}}}
{\transcribe(\meta{E}, \pair{\pair{\pi}{\rho}}{\tau^\prime},
 e_{{\it use}}, e_{{\it def}}) =
 \pair{\meta{E}^\prime}{\divert(e_{{\it use}}, e_{{\it new}})}}$$

\vskip 2ex

\begin{center}
$\transcribe(\meta{E}, \langle \; \rangle, e_{{\it use}}, e_{{\it def}})$
is an error.
%\\
%See text for an explanation of
%$\match(\meta{E}, \pi, e_{{\it use}}, e_{\it def})$
%and $\rewrite(\rho, \sigma, e_{\it def})$.
\end{center}

\caption{Definition of $\transcribe(\meta{E}, \tau,
e_{{\it use}}, e_{{\it def}})$.\label{transcribe}}
\end{figure*}

% End of definition of transcribe.


The same situation holds for macro expansions.  It does not work to
simply expand all macro calls and then rename variables, nor can
% *&^*&^*&^*&^
the renamings be performed before expansion.
% One must carefully interleave
The two processes
must be interleaved
in an appropriate manner.
A correct and efficient realization of this interleaving
% Getting this right and fast
is our primary contribution.



\section{The algorithm}

Our algorithm avoids inadvertent captures by guaranteeing
the following {\em hygiene condition}:

\begin{enumerate}
\item  It is impossible to write a high-level macro that inserts
      a binding that can capture references other than those
      inserted by the macro.
\item  It is impossible to write a high-level macro that inserts
      a reference that can be captured by bindings other than
      those inserted by the macro.
\end{enumerate}

These two properties can be taken as the defining properties
of hygienic macro expansion.  The hygiene condition is quite
strong, and it is sometimes necessary to write non-hygienic
macros; for example, the \code{while} construct in C
implicitly binds \code{break}, so if \code{while} were
implemented as a macro then it would have to be allowed to
capture references to \code{break} that it did not insert.
We here ignore the occasional need to escape from hygiene;
we have implemented a compatible low-level macro system in which
non-hygienic macros can be written.

The reason that previous algorithms for hygienic macro expansion
are quadratic in time is that they expand each use of a macro by
performing a naive expansion followed by an extra scan of the
expanded code to find and paint (i.e. rename, or time-stamp)
the newly introduced identifiers.  If macros expand into
uses of still other macros with more or less the same actual
parameters, which often happens, then large fragments of code
may be scanned anew each time a macro is expanded.
Naive macro expansion would scan each fragment of code only
once, when the fragment is itself expanded.

Our algorithm runs in linear time because it finds the newly
introduced identifiers by scanning the rewrite rules, and
paints these identifiers as they are introduced during macro
expansion.  The algorithm therefore scans the
expanded code but once, for the purpose of completing the
recursive expansion of the code tree, just as in the naive
macro expansion algorithm.
The newly introduced identifiers can in fact be determined
by scanning the rewrite rules at macro definition time, but
this does not affect the asymptotic complexity of the algorithm.

The more fundamental difference between our algorithm and
previous algorithms lies in the book-keeping needed to support
referentially transparent local macros.  The syntactic
environments manipulated by this book-keeping are shown in
Figure~\ref{environments}.  These are essentially
the same as the environments used by syntactic closures, but
the book-keeping performed by our algorithm allows it to
defer decisions that involve the syntactic roles of identifiers.

%The algorithm works by allocating a new color for every macro
%expansion, and by painting every new identifier introduced by
%that macro expansion with the new color.  It also keeps track
%of the bindings between the newly painted identifiers and the
%unpainted identifiers that they will eventually be seen to
%refer to, provided no intervening bindings surface to break
%the connection.  As the algorithm traverses the program
%recursively, it will eventually scan each identifier after macro
%expansion is (locally) complete.  At that time it uses the
%environments that it has constructed to replace the identifier
%by the identifier that it refers to.  The ultimate result is a
%completely alpha-converted and macro-expanded source program
%with no inadvertent captures of bound variables.


The overall structure of the algorithm is shown formally
in Figure~\ref{algorithm} for the lambda calculus subset of Scheme,
extended by macro calls and a restricted form of
\code{let-syntax}.  The notation
``$\,e \justifies \meta{E} \expandsto \meta{E}^\prime\>$''
indicates that $\meta{E}^\prime$ is the completely
macro-expanded
expression that results from expanding $\meta{E}$ in the
syntactic environment $e$.  For this simple language
the initial syntactic environment $e_{\it init}$ is
$$\bind(\bind(\constant{ident}, \code{lambda}, \constant{lambda}),
        \code{let-syntax}, \constant{let-syntax}).$$

The variables bound by a procedure abstraction are renamed
to avoid shadowing outer variables.  
Identifiers that denote variable references must therefore
be renamed as well.
Procedure calls are straightforward (but would be less so
if expressions were allowed to expand into syntactic
keywords; we have implemented this both ways).
The rule for macro abstractions is also straightforward:
the body is macro-expanded in a syntactic environment in
which the syntactic keyword bound by the abstraction
denotes the macro obtained from the transformation function
$\tau$ (a set of rewrite rules) by closing $\tau$ in the
syntactic environment of the macro definition.

The rule for macro calls is subtle.  The macro call is
transcribed using the transformation function $\tau$
obtained from the macro being called, the syntactic
environment of the call, and the syntactic environment
in which the macro was defined.  This transcription
yields not only a new expression $\meta{E}$ but a new
syntactic environment $e^{\prime\prime}$ in which to
complete the macro expansion.  The key fact about
algorithms for hygienic macro expansion is that any
identifiers introduced by the
macro are renamed, so the macro can only introduce
fresh identifiers.  The new syntactic environment
binds these fresh identifiers to the denotations of
the corresponding original identifiers in the syntactic
environment of the macro definition.  These will be
the ultimate denotations of the fresh identifiers
unless subsequent macro expansion exposes
an intervening procedure abstraction that
binds them.  Since the identifiers were fresh, any
such binding must have been introduced by the same
macro call that introduced the references.  Hence the
hygiene condition will be satisfied.

Figure~\ref{transcribe} defines the $\constant{transcribe}$ function
in terms of $\constant{match}$ and $\constant{rewrite}$.
The $\constant{transcribe}$ function simply loops through
each rewrite rule $\pi$ \code{=>} $\rho$ until it finds
one whose pattern $\pi$ matches the macro call.  It
then rewrites the macro call according to $\rho$ and
adds new bindings for any identifiers introduced by
the rewrite to the syntactic environment of the use.

Actually, rather than matching the entire macro call to the pattern,
it is sufficient to match only the tail (or ``actual parameters'') of the
call against the tail (``formal parameters'') of the pattern.  This
complication is not reflected in Figure~\ref{transcribe}.

The
$\constant{match}$ function (Figure~\ref{match})
delivers a substitution $\sigma$ mapping pattern variables
to components of the input expression.
It is quite conventional except for one important
wrinkle:  Matching an identifier $x$ in the macro use
against a literal identifier $y$ in the pattern
succeeds if and only if $\lookup(e_{{\it use}}, x)
= \lookup(e_{{\it def}}, y)$.
This implies that identifiers in patterns are lexically
scoped: bindings that intervene between the definition and use of a
macro may cause match failure.

For simplicity, the definition of \constant{match} in
Figure~\ref{match} assumes that no pattern variable is duplicated.

% A detail about match: it is necessary to
% strip off the head from the expression and pattern.
% This is not reflected in figure mumble.

The $\constant{rewrite}$ function (Figure~\ref{rewrite}) rewrites the
macro call using the substitution $\sigma$ generated by the matcher.
It is also responsible for choosing the fresh identifiers that replace
those that appear in the output pattern and establishing their proper
denotations.  $\constant{transcribe}$ uses $\constant{divert}$ to add
these new bindings to the environment in which the macro output is
expanded.

%It is defined as follows.  Let
%$\left\{ x_1, \ldots, x_n \right\}$ be the set of
%identifiers (as opposed to pattern variables)
%that occur in the rewrite template $\rho$, let
%$d_i = \lookup(e_{{\it def}}, x_i)$ for $i=1\dots n$,
%and let
%$\left\{ x_1', \ldots, x_n' \right\}$ be a
%set of fresh identifiers.  Then
%$$\rewrite(\rho, \sigma, e_{{\it def}}) =
%  \pair{\meta{E}^\prime}{
%  \bind(\ldots \bind(\constant{ident}, x_1', d_1)
%   \ldots, x_n', d_n)}$$
%where $\meta{E}^\prime$ is $\rho$ rewritten according
%to the substitution
%$$\sigma \cup
%  \left\{ x_1 \mapsto x_1', \ldots, x_n \mapsto x_n' \right\}.$$

Given constant-time operations on environments, this algorithm
takes $O(n)$ time, where $n$ is the time required by naive
macro expansion.

\begin{figure}
%
% Definition of match.
%

$$
\match(\meta{E}, \code{?}\meta{v}, e_{\it use}, e_{\it def})
  = \{\code{?}\meta{v} \mapsto \meta{E}\}$$

$$\infrule
{\lookup(e_{\it def}, \meta{x}') = \lookup(e_{\it use}, \meta{x})}
{\match(\meta{x}, \meta{x}', e_{\it use}, e_{\it def}) = \{\}}
$$

$$\infrule
{\rwabove
 {\match(\meta{E}_i, \pi_i, e_{\it use}, e_{\it def}) = \sigma_i,
    \; i = 1, \ldots, n}
 {\sigma_i \not= \constant{nomatch},
    \; i = 1, \ldots, n}}
{\match(\code{(}\meta{E}_1 \ldots \meta{E}_n\code{)},
        \code{(}\pi_1 \ldots \pi_n\code{)},
        e_{\it use}, e_{\it def})
   = \sigma_1 \cup \ldots \cup \sigma_n}$$

$$
{\rwabove
 {\match(\meta{E}, \pi, e_{\it use}, e_{\it def})
     = \constant{nomatch},}
 {\hbox{\hspace*{4em}\rm if the other rules are not applicable}}}
$$

\caption{Definition of $\match(\meta{E}, \pi, e_{\it use}, e_{\it def})$.\label{match}}

\end{figure}

\begin{figure}
%
% Definition of rewrite.
%
\vspace*{8ex}
\topsep 0pt

$$\rewrite(\rho, \sigma, e_{\it def})
     = \pair{rewrite'(\rho, \sigma')}{e_{\it new}},$$
where
\begin{quote}  % kludge for indentation and spacing
 $\sigma' = \sigma \cup \{x_1 \mapsto x_1', \ldots, x_n \mapsto x_n'\}$,\\
 $x_1, \ldots, x_n$ are all the identifiers that occur in $\rho$,\\
 $x_1', \ldots x_n'$ are fresh identifiers,\\
 $e_{\it new} = \bind(\ldots \bind(\constant{ident}, x_1', d_1)\ldots,
                          x_n', d_n)$, \\
 and $d_i = lookup(e_{\it def}, x_i)$ for $i = 1, \ldots, n$.
\end{quote}

$$\rewrite'(\code{?}\meta{v}, \sigma) = \sigma(\code{?}\meta{v})$$

$$\rewrite'(\meta{x}, \sigma) = \sigma(\meta{x})$$

$$\rewrite'(\code{(}\pi_1 \ldots \pi_n\code{)}, \sigma)
   = \code{(}\meta{E}_1' \ldots \meta{E}_n'\code{)},$$
where $\meta{E}_i' = rewrite'(\pi_i, \sigma),\> i = 1, \ldots, n$.

\caption{Definition of $\rewrite(\rho, \sigma, e_{\it def})$.\label{rewrite}}

\end{figure}

\section{Examples}
\newcommand{\example}[1]{\medskip\noindent{\em Example #1}.}

To make the examples easier to follow, we'll assume that \code{let} is
understood primitively by the expansion algorithm, in a manner similar
to \code{lambda}.  The initial environment $e_{\it init}$ thus has
a nontrivial binding for the identifier \code{let} in addition to
\code{lambda} and \code{let-syntax}.

\example{1}
Consider the problem of expanding the following
expression in the initial syntactic environment:
%
\begin{verbatim}
  (let-syntax ((push (syntax-rules
                       ((push ?v ?x)
                        => (set! ?x (cons ?v ?x))))))
    (let ((pros (list "cheap" "fast"))
          (cons (list)))
      (push "unreliable" cons)))
\end{verbatim}
%
% Other cons:  cramped, inefficient, unecomonical, unsafe, ...
%
The rule for macro abstractions applies, because
$$\lookup(e_{\it init}, \code{let-syntax}) = \constant{let-syntax}.$$
The next step is to
expand the body of the \code{let-syntax} expression in an augmented syntactic
environment
$$
  e_1 = bind(e_{\it init}, \code{push}, \pair{\tau}{e_{\it init}})
$$
where
$$
  \tau = \langle \pair{\code{( ?v ?x)}}{\code{(set!\ ?x (cons ?v ?x))}} \rangle
$$
The pattern is \code{( ?v ?x)}, rather than \code{(push ?v ?x)}, because the
rule will only be examined when the fact that the head of the form
denotes the \code{push} macro is already apparent.  Thus there is
never a need to match the head of the pattern with the head of the
expression to be expanded.

The initializers in the \code{let} expression expand to themselves,
because $e_1 \justifies \code{list} \expandsto \code{list}$.
(Recall that $e_{\it init}$, and therefore $e_1$ as well, is based on the
identity environment $\constant{ident}$.)

Next we expand the body of the \code{let} expression in the augmented
environment 
$$
  e_2 = \bind(\bind(e_1, \code{cons}, \code{cons.1}), \code{pros}, \code{pros.1})
$$
where \code{pros.1} and \code{cons.1} are fresh identifiers.  In $e_2$, the
identifier \code{push} denotes the macro $\pair{\tau}{e_{\it init}}$, so the rule for macro
calls applies to the \code{push} expression.  We now compute
$$
  \transcribe( \code{(push "unreliable" cons)}, \tau, e_2, e_{\it init})
$$
$\tau$ consists of only one rule, which matches the input:
$$\begin{array}{l}
  \match( \code{( "unreliable" cons)}, \code{( ?v ?x)}, e_2, e_{\it init})\\
\quad = \{\code{?v} \mapsto \code{"unreliable"},\>
           \code{?x} \mapsto \code{cons}\}
\end{array}$$
Note that $\match$ made no use of its two environment arguments, because
the pattern \code{( ?v ?x)} didn't contain any identifiers.  The \code{cond}
example below gives a situation in which these environments are
used.

Now we compute the replacement expression:
{\arraycolsep 0pt
$$\begin{array}{rl}
  \rewrite( &\code{(set!\ ?x (cons ?v ?x))}, \\
            &\{\code{?v} \mapsto \code{"unreliable"},\>
               \code{?x} \mapsto \code{cons}\}, \\
            &e_{\it init}) \\
 \multicolumn{2}{r}{
   \quad = \pair{\code{(set!.2 cons (cons.2 "unreliable" cons))}}{e_3}  }
\end{array}$$
}
where
$$
  e_3 = \bind(\bind(\constant{ident}, \code{set!.2}, \code{set}!), \code{cons.2}, \code{cons})
$$
and \code{set!.2} and \code{cons.2} are fresh identifiers.  
$\constant{transcribe}$ now delivers the rewritten expression
together with an environment
$$\begin{array}{rcl}
 e_4 &=& \divert(e_2, e_3) \\
     &=&\bind(\bind(e_2, \code{set!.2}, \code{set}!), \code{cons.2}, \code{cons})
\end{array}$$
that gives bindings to use in expanding the replacement expression.
The environment $e_4$ takes \code{set!.2} to \code{set!}, \code{cons.2} to \code{cons}, and
\code{cons} to \code{cons.1}, so
$$\begin{array}{rcl}
   e_4 &\justifies& \code{(set!.2 cons (cons.2 "unreliable" cons))} \\
       &&\quad \expandsto \code{(set!\ cons.1 (cons "unreliable" cons.1))}
\end{array}$$
The final result is
\begin{verbatim}
  (let ((pros.1 (list "cheap" "fast"))
        (cons.1 (list)))
    (set! cons.1 (cons "unreliable" cons.1)))
\end{verbatim}

\example{2}
This example illustrates reliable reference to local variables
that are in scope where the macro is defined.
\begin{verbatim}
  (let ((x "outer"))
    (let-syntax ((m (syntax-rules
                      ((m) => x))))
      (let ((x "inner"))
        (m))))
\end{verbatim}
To expand this expression in $e_{\it init}$,
a fresh identifier \code{x.1} is chosen to replace the outer \code{x},
and the \code{let-syntax} expression is expanded in the syntactic
environment
$$
  e_1 = \bind(e_{\it init}, \code{x}, \code{x.1})
$$
This leads to expanding the inner \code{let} expression
in the syntactic environment
$$
  e_2 = \bind(e_1, \code{m},
              \pair{\langle\pair{\code{( )}}{\code{x}}\rangle}{e_1})
$$
Finally a fresh identifer \code{x.2} is chosen to replace the inner \code{x},
and \code{(m)} is expanded in the syntactic
environment
$$
  e_3 = \bind(e_2, \code{x}, \code{x.2})
$$
Now
$$
  \transcribe(\code{(m)},
              \langle\pair{\langle\code{( )}\rangle}{\code{x}}\rangle,
              e_3, e_1)
    = \pair{\code{x.3}}{\bind(e_3, \code{x.3}, \code{x.1})}
$$
where \code{x.3} is a fresh identifer introduced for the right-hand
side of the rewrite rule for the macro \code{m}.  The denotation of
\code{x.3} is the denotation of \code{x} in the environment of
\code{m}'s definition, which is \code{x.1}.
The final expansion is
\begin{verbatim}
  (let ((x.1 "outer"))
    (let ((x.2 "inner"))
      x.1))
\end{verbatim}

% ------------------------------------------------------------
%      ((cond (?test => ?result) ?clause ...)
%       => (let ((temp ?test))
%            (if temp
%                (?result temp)
%                (cond ?clause ...))))

\example{3}
This example illustrates lexical scoping of constant identifiers that
occur in the left-hand side of rewrite rules.  Following
\referto{kohlbeckerphd}, we adopt the use of an ellipsis token
\code{...} as part of the syntax of patterns, not as a meta-notation
indicating that something has been elided from this example.
\begin{verbatim}
  (define-syntax cond
    (syntax-rules
      ((cond) => #f)
      ((cond (else ?result ...) ?clause ...)
       => (begin ?result ...))
      ((cond (?test) ?clause ...)
       => (or ?test (cond ?clause ...)))
      ((cond (?test ?result ...) ?clause ...)
       => (if ?test
              (begin ?result ...)
              (cond ?clause ...)))))
\end{verbatim}
The second pattern for this macro contains a fixed identifier
\code{else}.  This will only match a given identifer $x$ in a use of
\code{cond}
if the denotation of $x$ in the environment of use matches the denotation of
\code{else} in the environment of \code{cond}'s definition.
Typically $x$ is \code{else} and is self-denoting in
both environments.  However, consider the following:
\begin{verbatim}
  (let ((else #f))
    (cond (#f 3)
          (else 4)
          (#t 5)))
\end{verbatim}
Expanding this expression requires calculating
$\match(\code{else}, \code{else}, e_{\it use}, e_{\it def})$
where
\begin{eqnarray*}
   \lookup(e_{\it use}, \code{else}) &=& \code{else.1},\\
   \lookup(e_{\it def}, \code{else}) &=& \code{else}.
\end{eqnarray*}
Thus
$$
  \match(\code{else}, \code{else}, e_{\it use}, e_{\it def})
    = \constant{nomatch}
$$
and the final expansion is
\begin{verbatim}
  (let ((else.1 #f))
    (if #f (begin 3)
        (if else.1 (begin 4)
            (if #t (begin 5) #f))))
\end{verbatim}
%as opposed to
%\begin{verbatim}
%  (let ((else.1 #f))
%    (if #f (begin 3)
%        (begin 4)))
%\end{verbatim}


%%%%%% Remove -- it is no longer in the introduction. %%%%%
%
%\example{4}
%[The other example from the main part of the paper ---]
%\begin{verbatim}
%  (let ((temp (- (* b b) (* 4 a c))))
%    (or (negative? temp)
%        (positive? temp)))
%\end{verbatim}
%expands to
%\begin{verbatim}
%  (let ((temp.1 (- (* b b) (* 4 a c))))
%    (let ((temp.2.3 (negative? temp.1)))
%      (if temp.2.3 temp.2.3 (positive? temp.1))))
%\end{verbatim}


\section{Integration issues}

% Scheme particularly good because
% 1. Lists, 2. Full parenthesization, 3. Block structure, 4. Single namespace.

We emphasize that our algorithm is suitable for use
with any block-structured language, and does not depend
on the representation of programs as lists in Scheme.
Scheme's representation is especially convenient, however.
This section explains how the algorithm can be made to
work with less convenient representations.

The simplicity of the $\match$ function defined in Figure 4
results from the regularity of a Cambridge Polish syntax.
For Algol-like syntaxes the matcher could be much more
complicated.  To avoid such complications, a macro system
may eschew complex patterns and may specify a fixed syntax
for macro calls.

Our algorithm must understand the structure of the source
program, so Algol-like syntaxes require that the
algorithm be integrated with a parser.  If the macro
language is sufficiently restricted, then it may be
possible to parse the input program completely before
macro expansion is performed.  If the actual parameters
of a macro call need to be transmitted to the macro in
unparsed form, however, then parsing will have to be
interleaved with the macro expansion algorithm.

For the algorithm to work at all, the parser must be
able to locate the end of any macro definition or macro
use.  If parentheses are used to surround the actual
parameters of a macro call, for example, then mismatched
parentheses within an actual parameter cannot be
tolerated unless they are somehow marked as such,
perhaps by an escape character.  This is a fundamental
limitation on the generality of the syntactic
transformations that can be described using a macro
system based on our algorithm.

This is not a particularly burdensome limitation.  For
example, it is possible to design a hygienic macro system
for C that allows the \code{for} construct to be described
as a macro.

Experience with macros in Lisp and related languages has
shown that macros are most useful when local variables
can be introduced in any statement or expression context.
Most Algol-like languages are not fully block-structured
in this sense.  C, for example, does not admit blocks as
expressions, while Pascal and Modula-2 do not even admit
blocks as statements.  Fortunately this particular
shortcoming can usually be overcome by the macro processor.
Macros can be written as though the language admits
blocks in all sensible contexts, and the macro processor
itself can be responsible for replacing these blocks by
their bodies while lifting all local declarations
to the head of the procedure body within which the
declarations appear.

In our algorithm, the matcher compares an identifier in
the pattern against an identifier in the input by comparing
their denotations.  This makes it difficult to use such
a sophisticated matcher in languages such as Common Lisp,
where an identifier may denote many different things at once,
and where the overloading is resolved by syntactic context.
The problem is that the matcher cannot reliably determine
the syntactic context in which the identifier will
ultimately appear.  One solution is to ban identifiers
from patterns.  Another is to resolve the overloading
by relying on declarations provided by the author of
the macro.


\section{Previous work, current status, future work}

The problems with naive macro expansion have been recognized
for many years, as have the traditional work-arounds \referto{brown}.
The capturing problems that afflict macro systems for
block-structured languages
were first solved by Kohlbecker's work on hygienic macro
expansion.  Bawden and Rees then proposed syntactic
closures \referto{bawden} as a more general and efficient
but lower-level solution.
Our algorithm unifies and extends this recent research,
most of which has been directed toward the goal of developing
a reliable macro system for Scheme.

At the 1988 meeting of the Scheme Report authors at Snowbird, Utah, a macro
committee was charged with developing a hygienic macro facility akin
to \code{extend-syntax} \referto{dybvig} but based on syntactic
closures.  Chris Hanson implemented a prototype and discovered 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 \referto{hanson}.
Clinger observed that Kohlbecker's algorithm
amounts to a technique for delaying this determination, and proposed a
linear-time version of Kohlbecker's algorithm.  Rees married syntactic
closures to the modified Kohlbecker's algorithm and implemented it
all, twice.  Bob Hieb found some %serious
bugs in the first
implementation and proposed fixes.

A high-level macro system similar to that described here is
currently implemented on top of a compatible low-level system
that is not described in this paper.
Bob Hieb and Kent Dybvig have redesigned this low-level
system to make it more abstract and easier to use, and
have constructed yet another implementation.  It
is expected that both the high-level and low-level macro
facilities
% (but not the algorithms used to implement them)
will be described in a future report on Scheme \referto{r4rs}.

% Conclusion and future work ?
% ``we have done grumble''

Some problems remain.  The algorithm we have described treats
identifiers uniformly, but identifiers in Scheme are lexically
indistinguishable from symbols that appear in constants.  Consequently
any symbols introduced by a macro will be renamed just as if they were
identifiers, and must therefore be reverted after macro expansion has
revealed that they are part of a constant.  This means that constants
introduced by a macro may have to be copied.  In this respect our
algorithm improves upon Kohlbecker's, which copied {\it all} constants,
but is still not ideal.

More significantly, the pattern variables used to define macros might
be lexically indistinguishable from identifiers and symbols.  In order
for macros that define other macros to remain referentially
transparent, pattern variables must not be reverted to their original
names even though they are represented as symbols in our existing
implementation.  We are not completely certain that this refinement
eliminates all problems with macros that define other macros.

One project we intend to pursue is to integrate
%the modified Kohlbecker
our
algorithm with a module system for Scheme such as that
described in \referto{curtis}.  For example, it should be possible for
a module to export a macro without also having to export bindings
needed by the macro's expansions.
% A word on modules from Jonathan's thesis?

An obvious application for this research is to develop better
macro facilities for other block-structured languages such
as Modula-2.
%We emphasize that our algorithm does not depend
%on the representation of programs as lists, though we
%enjoy the convenience of that representation.  It is
%probably more important that the programming language treat
%identifiers in a reasonably uniform manner, and so we offer
%the
%surprising
%conjecture that it will be easier to apply this research to C than to
%Common Lisp.


\section*{Acknowledgements}

The authors thank an anonymous member of the program committee who
helped us to write the introduction.  Jim O'Toole and Mark Sheldon
provided helpful comments on drafts of the paper.

%This report describes research done at the Artificial Intelligence
%Laboratory of the Massachusetts Institute of Technology.  Support for
%the laboratory's artificial intelligence research is provided in part
%by the Advanced Research Projects Agency of The Department of Defense
%under the Office of Naval Research contract N00014-89-J-3202.

\begin{thebibliography}{99}

\bibitem{bawden}    Alan Bawden and Jonathan Rees. \\
                    Syntactic closures. \\
                    {\em 1988 ACM Conference on
                      Lisp and Functional Programming,} pages 86--95.

\bibitem{brown}     P.~J.~Brown. \\
                    {\em Macro Processors and Techniques for Portable
                      Software.} \\
                    Wiley, 1974.

\bibitem{r4rs}      William Clinger and Jonathan Rees, editors. \\
                    Revised$^4$ report on the algorithmic language
                      Scheme. \\
                    University of Oregon Technical Report CIS-TR-90-02,
                      to appear.

\bibitem{curtis}    Pavel Curtis and James Rauen. \\
                    A module system for Scheme. \\
                    {\em 1990 ACM Conference on Lisp and Functional
                      Programming,} pages 13--19.

\bibitem{dybvig}    R.~Kent Dybvig. \\
                    {\em The Scheme Programming Language.} \\
                    Prentice-Hall, 1987.

\bibitem{hanson}    Chris Hanson. \\
                    Personal communication.

\bibitem{assemblylanguage}
                    Samuel P.~Harbison and Guy L.~Steele Jr. \\
                    {\em C: A Reference Manual.} \\
                    Prentice-Hall, second edition 1987.

\bibitem{kohlbecker} Eugene Kohlbecker, Daniel P.~Friedman, Matthias
                      Felleisen, and Bruce Duba. \\
                    Hygienic macro expansion. \\
                    {\em 1986 ACM Conference on Lisp and Functional
                      Programming,} pages 151--159.

\bibitem{kohlbeckerphd}
                    Eugene E.~Kohlbecker Jr. \\
                    Syntactic extensions in the programming language
                      Lisp. \\
                    Technical report no.~199, Indiana University
                      Computer Science Department, 1986.

\bibitem{scheme}    Jonathan A.~Rees and William Clinger, editors. \\
                    Revised$^3$ report on the algorithmic language
                      Scheme. \\
                    {\em SIGPLAN Notices} 21(12), pages 37--79, 1986.

\bibitem{CLtL}      Guy L.~Steele Jr. \\
                    {\em Common Lisp: The Language.} \\
                    Digital Press, second edition 1990.

\end{thebibliography}

\end{document}

