\documentstyle{article}


\def\schtrue{\hbox{{\tt \#t}}}
\def\schfalse{\hbox{{\tt \#f}}}
\def\ide#1{\hbox{{\tt #1}}}


\newcommand{\meta}[1]{{\noindent\hbox{\rm$\langle$#1$\rangle$}}}
\let\hyper=\meta
\newcommand{\hyperi}[1]{\hyper{#1$_1$}}
\newcommand{\hyperii}[1]{\hyper{#1$_2$}}
\newcommand{\hyperj}[1]{\hyper{#1$_i$}}
\newcommand{\hypern}[1]{\hyper{#1$_n$}}
\newcommand{\var}[1]{\noindent\hbox{\it{}#1\/}}  % Careful, is \/ always the right thing?
\newcommand{\vari}[1]{\var{#1$_1$}}
\newcommand{\varii}[1]{\var{#1$_2$}}
\newcommand{\variii}[1]{\var{#1$_3$}}
\newcommand{\variv}[1]{\var{#1$_4$}}
\newcommand{\varj}[1]{\var{#1$_j$}}
\newcommand{\varn}[1]{\var{#1$_n$}}


\newcommand{\vr}[1]{{\noindent\hbox{$#1$\/}}}  % Careful, is \/ always the right thing?
\newcommand{\vri}[1]{\vr{#1_1}}
\newcommand{\vrii}[1]{\vr{#1_2}}
\newcommand{\vriii}[1]{\vr{#1_3}}
\newcommand{\vriv}[1]{\vr{#1_4}}
\newcommand{\vrj}[1]{\vr{#1_j}}
\newcommand{\vrn}[1]{\vr{#1_n}}


% \frobq will make quote and backquote look nicer.
\def\frobqcats{%\catcode`\'=13
\catcode`\`=13{}}
{\frobqcats
\gdef\frobqdefs{%\def'{\singlequote}
\def`{\backquote}}}
\def\frobq{\frobqcats\frobqdefs}


% \cf = code font
% Unfortunately, \cf \cf won't work at all, so don't even attempt to
% next constructions which use them...
\newcommand{\cf}{\frenchspacing\frobq\tt}


% Same as \obeycr, but doesn't do a \@gobblecr.
{\catcode`\^^M=13 \gdef\myobeycr{\catcode`\^^M=13 \def^^M{\\}}%
\gdef\restorecr{\catcode`\^^M=5 }}


{\catcode`\^^I=13 \gdef\obeytabs{\catcode`\^^I=13 \def^^I{\hbox{\hskip 4em}}}}


{\obeyspaces\gdef {\hbox{\hskip0.5em}}}


\gdef\gobblecr{\@gobblecr}


\def\setupcode{\@makeother\^}


\newenvironment{grammar}{
  \def\:{\goesto{}}
  \def\|{$\vert$}
  \cf \myobeycr
  \begin{tabbing}
    %\qquad\quad \= 
    \qquad \= $\vert$ \= \kill
  }{\unskip\end{tabbing}}


% Commands for grammars
\newcommand{\arbno}[1]{#1\hbox{\rm*}}  
\newcommand{\atleastone}[1]{#1\hbox{$^+$}}


\newcommand{\goesto}{$\longrightarrow$}








\begin{document}


\centerline{{\Large Hygienic Macros Through Explicit Renaming}}


\vskip 24pt


\centerline{William Clinger}


\vskip 72pt


This paper describes an alternative to the low-level macro
facility described in the {\em Revised$^4$ Report on the
Algorithmic Language Scheme} [1].
The facility described here is based on explicit renaming
of identifiers, and was developed for the first implementation of the hygienic
macro expansion algorithm described in [2]. It was the first
low-level macro facility to be designed for compatibility with a high-level
hygienic macro system, and it remains one of the easiest to understand.


Whereas the low-level macro facility described in the
Revised$^4$ Report renames identifiers automatically,
so that hygienic macros are obtained by default, the
facility described here requires that identifiers be
renamed explicitly in order to maintain hygiene.


Another difference is that, as originally implemented
and as described here, there is no way to define certain
hygienic macros that define other hygienic macros.
The problem is that the transformation procedure for the
defined macro may need to compare pieces of its
first argument with the denotation of an identifier,
but the only way for the defining macro to pass that
denotation along to the defined macro is as part of
the code for the defined macro.
This problem can be solved by introducing \ide{syntax}
expressions as in the Revised$^4$ Report.  \ide{Syntax}
is like \ide{quote}, except that the denotation of an
identifier quoted by \ide{syntax} is preserved as part
of the quoted value.


As with the low-level macro facility based on syntactic
closures [3], the explicit renaming facility adds a new
production for \meta{transformer spec}:
\begin{grammar}
    \meta{transformer} \: (transformer \meta{expression})%
\end{grammar}


The \meta{expression} is expanded in the syntactic
environment of the \ide{transformer} expression, and the
expanded expression is evaluated in the standard transformer
environment to yield a {\em transformation procedure}.
The transformation procedure takes an expression and two
other arguments and returns a transformed expression.
For example, the transformation
procedure for a \ide{call} macro such that
\ide{(call \var{proc} \var{arg} ...)} expands
into \ide{(\var{proc} \var{arg} ...)} can be written as
\begin{verbatim}
     (lambda (exp rename compare)
       (cdr exp))
\end{verbatim}
\noindent
Expressions are represented as lists in the traditional manner,
except that identifiers may be represented by objects other than
symbols.
Transformation procedures may use the predicate
\ide{identifier?} to determine whether an object is the
representation of an identifier.


The second argument to a transformation procedure is a renaming procedure that
takes the representation of an identifier as its argument and returns the
representation of a fresh identifier that occurs nowhere else in the
program.  For example, the transformation procedure for a simplified
version of the \ide{let} macro might be written as
\begin{verbatim}
     (lambda (exp rename compare)
       (let ((vars (map car (cadr exp)))
             (inits (map cadr (cadr exp)))
             (body (cddr exp)))
         `((lambda ,vars ,@body)
           ,@inits)))
\end{verbatim}


\noindent
This would not be hygienic, however.  A
hygienic \ide{let} macro must rename the identifier \ide{lambda} to protect it
from being captured by a local binding.  The renaming effectively
creates an fresh alias for \ide{lambda}, one that cannot be captured by
any subsequent binding:
\begin{verbatim}
     (lambda (exp rename compare)
       (let ((vars (map car (cadr exp)))
             (inits (map cadr (cadr exp)))
             (body (cddr exp)))
         `((,(rename 'lambda) ,vars ,@body)
           ,@inits)))
\end{verbatim}


   The expression returned by the transformation procedure will be
expanded in the syntactic environment obtained from the syntactic
environment of the macro application by binding any fresh identifiers
generated by the renaming procedure to the denotations of the original
identifiers in the syntactic environment in which the macro was
defined.  This means that a renamed identifier will denote the same
thing as the original identifier unless the transformation procedure
that renamed the identifier placed an occurrence of it in a binding
position.


   The renaming procedure acts as a mathematical function in the sense
that the identifiers obtained from any two calls with the same
argument will be the same in the sense of \ide{eqv?}.  It is an error if
the renaming procedure is called after the transformation procedure
has returned.


   The third argument to a transformation procedure is a comparison
predicate that takes the representations of two identifiers as its
arguments and returns true if and only if they denote the same thing
in the syntactic environment that will be used to expand the
transformed macro application.  For example, the transformation
procedure for a simplified version of the \ide{cond} macro can be written
as
\begin{verbatim}
     (lambda (exp rename compare)
       (let ((clauses (cdr exp)))
         (if (null? clauses)
             `(,(rename 'quote) unspecified)
             (let* ((first (car clauses))
                    (rest (cdr clauses))
                    (test (car first)))
               (cond ((and (identifier? test)
                           (compare test (rename 'else)))
                      `(,(rename 'begin) ,@(cdr first)))
                     (else `(,(rename 'if)
                             ,test
                              (,(rename 'begin) ,@(cdr first))
                              (cond ,@rest))))))))
\end{verbatim}
\noindent
In this example the identifier \ide{else} is renamed before being passed
to the comparison predicate, so the comparison will be true if and
only if the test expression is an identifier that denotes the same
thing in the syntactic environment of the expression being transformed
as \ide{else} denotes in the syntactic environment in which the \ide{cond}
macro was defined.  If \ide{else} were not renamed before being passed to
the comparison predicate, then it would match a local variable that
happened to be named \ide{else}, and the macro would not be hygienic.


   Some macros are non-hygienic by design.  For example, the
following defines a \ide{loop} macro that implicitly binds \ide{exit} to an
escape procedure.  The binding of \ide{exit} is intended to capture free
references to \ide{exit} in the body of the loop, so \ide{exit} is not
renamed.
\begin{verbatim}
     (define-syntax loop
       (transformer
        (lambda (x r c)
          (let ((body (cdr x)))
            `(,(r 'call-with-current-continuation)
              (,(r 'lambda) (exit)
               (,(r 'let) ,(r 'f) () ,@body (,(r 'f)))))))))
\end{verbatim}


Suppose a \ide{while} macro is implemented using \ide{loop}, with the intent
that \ide{exit} may be used to escape from the \ide{while} loop.  The \ide{while}
macro cannot be written as
\begin{verbatim}
     (define-syntax while
       (syntax-rules ()
         ((while test body ...)
          (loop (if (not test) (exit #f))
                body ...))))
\end{verbatim}
\noindent
because the reference to \ide{exit} that is inserted by the \ide{while} macro
is intended to be captured by the binding of \ide{exit} that will be
inserted by the \ide{loop} macro.  In other words, this \ide{while} macro is
not hygienic.  Like \ide{loop}, it must be written using the \ide{transformer}
syntax:
\begin{verbatim}
     (define-syntax while
       (transformer
        (lambda (x r c)
          (let ((test (cadr x))
                (body (cddr x)))
            `(,(r 'loop)
              (,(r 'if) (,(r 'not) ,test) (exit #f))
              ,@body)))))
\end{verbatim}


\begin{thebibliography}{99}


\bibitem{rrrs}      William Clinger and Jonathan Rees, editors. \\
                    Revised$^4$ report on the algorithmic language
                      Scheme. \\
                    To appear in the previous issue of {\em Lisp Pointers}.


\bibitem{macrosthatwork}    William Clinger and Jonathan Rees. \\
                    Macros that work. \\
                    {\em 1991 ACM Conference on
                      Principles of Programming Languages}.


\bibitem{hanson}    Chris Hanson. \\
                    A syntactic closures macro facility. \\
                    To appear in this issue of {\em Lisp Pointers}.
\end{thebibliography}




\end{document}
