\input texinfo @c -*-texinfo-*-
@c %**start of header
@setfilename prop.info
@settitle A Syntactic Closures Macro Facility
@setchapternewpage off
@c %**end of header

@ifinfo
@node Top, Terminology, (dir), (dir)
@top A Syntactic Closures Macro Facility
@end ifinfo

@iftex
@finalout
@evenheading @thispage @| @| Revised^4 Scheme
@oddheading Syntactic Closures @| @| @thispage
@sp 4
@center @titlefont{A Syntactic Closures Macro Facility}
@sp 1
@center by Chris Hanson
@sp 1
@center 9 November 1991
@sp 4
@end iftex

This document describes @dfn{syntactic closures}, a low-level macro
facility for the Scheme programming language.  The facility is an
alternative to the low-level macro facility described in the
@cite{Revised^4 Report on Scheme}.  This document is an addendum to
that report.@refill

The syntactic closures facility extends the @sc{bnf} rule for
<transformer spec> to allow a new keyword that introduces a low-level
macro transformer:@refill

@lisp
@r{<transformer spec>} @expansion{} (transformer @r{<expression>})
@end lisp

@noindent
Additionally the following procedures are added:@refill

@lisp
make-syntactic-closure
capture-syntactic-environment
identifier?
identifier=?
@end lisp

The description of the facility is divided into three parts.  The first
part defines basic terminology.  The second part describes how macro
transformers are defined.  The third part describes the use of
@dfn{identifiers}, which extend the syntactic closure mechanism to be
compatible with @code{syntax-rules}.@refill

@menu
* Terminology::                 Terminology
* Transformer Definition::      Transformer Definition
* Identifiers::                 Identifiers
* Acknowledgments::             Acknowledgments
@end menu

@node Terminology, Transformer Definition, Top, Top
@heading Terminology

This section defines the concepts and data types used by the syntactic
closures facility.@refill

@itemize @bullet
@item
@cindex form
@dfn{Forms} are the syntactic entities out of which programs are
recursively constructed.  A form is any expression, any definition, any
syntactic keyword, or any syntactic closure.  The variable name that
appears in a @code{set!} special form is also a form.  Examples of
forms:@refill

@lisp
@group
17
#t
car
(+ x 4)
(lambda (x) x)
(define pi 3.14159)
if
define
@end group
@end lisp

@item
@cindex alias
@cindex identifier
An @dfn{alias} is an alternate name for a given symbol.  It can appear
anywhere in a form that the symbol could be used, and when quoted it is
replaced by the symbol; however, it does not satisfy the predicate
@code{symbol?}.  Macro transformers rarely distinguish symbols from
aliases, referring to both as @dfn{identifiers}.@refill

@item
@cindex syntactic environment
A @dfn{syntactic environment} maps identifiers to their meanings.  More
precisely, it determines whether an identifier is a syntactic keyword
or a variable.  If it is a keyword, the meaning is an interpretation
for the form in which that keyword appears.  If it is a variable, the
meaning identifies which binding of that variable is referenced.  In
short, syntactic environments contain all of the contextual information
necessary for interpreting the meaning of a particular form.@refill

@item
@cindex syntactic closure
A @dfn{syntactic closure} consists of a form, a syntactic environment,
and a list of identifiers.  All identifiers in the form take their
meaning from the syntactic environment, except those in the given list.
The identifiers in the list are to have their meanings determined
later.@refill

A syntactic closure may be used in any context in which its form could
have been used.  Since a syntactic closure is also a form, it may not
be used in contexts where a form would be illegal.  For example, a form
may not appear as a clause in the @code{cond} special form.@refill

A syntactic closure appearing in a quoted structure is replaced by its
form.@refill
@end itemize

@node Transformer Definition, Identifiers, Terminology, Top
@heading Transformer Definition

This section describes the @code{transformer} special form and the
procedures @code{make-syntactic-closure} and
@code{capture-syntactic-environment}.

@deffn syntax transformer expression
@i{Syntax:} It is an error if this syntax occurs except as a
<transformer spec>.@refill

@i{Semantics:} The @var{expression} is evaluated in the standard
transformer environment to yield a macro transformer as described
below.  This macro transformer is bound to a macro keyword by the
special form in which the @code{transformer} expression appears (for
example, @code{let-syntax}).@refill

@cindex macro transformer
@cindex input form
@cindex usage environment
@cindex output form
@cindex transformer environment
A @dfn{macro transformer} is a procedure that takes two arguments, a
form and a syntactic environment, and returns a new form.  The first
argument, the @dfn{input form}, is the form in which the macro keyword
occurred.  The second argument, the @dfn{usage environment}, is the
syntactic environment in which the input form occurred.  The result of
the transformer, the @dfn{output form}, is automatically closed in the
@dfn{transformer environment}, which is the syntactic environment in
which the @code{transformer} expression occurred.@refill

For example, here is a definition of a @code{push} macro using
@code{syntax-rules}:@refill

@lisp
@group
(define-syntax push
  (syntax-rules ()
    ((push item list)
     (set! list (cons item list)))))
@end group
@end lisp

@noindent
Here is an equivalent definition using @code{transformer}:@refill

@lisp
@group
(define-syntax push
  (transformer
   (lambda (exp env)
     (let ((item
            (make-syntactic-closure env '() (cadr exp)))
           (list
            (make-syntactic-closure env '() (caddr exp))))
       `(set! ,list (cons ,item ,list))))))
@end group
@end lisp

@noindent
In this example, the identifiers @code{set!} and @code{cons} are closed
in the transformer environment, and thus will not be affected by the
meanings of those identifiers in the usage environment
@code{env}.@refill

Some macros may be non-hygienic by design.  For example, the following
defines a @code{loop} macro that implicitly binds @code{exit} to an
escape procedure.  The binding of @code{exit} is intended to capture
free references to @code{exit} in the body of the loop, so @code{exit}
must be left free when the body is closed:@refill

@lisp
@group
(define-syntax loop
  (transformer
   (lambda (exp env)
     (let ((body (cdr exp)))
       `(call-with-current-continuation
         (lambda (exit)
           (let f ()
             ,@@(map (lambda (exp)
                      (make-syntactic-closure env '(exit)
                        exp))
                    body)
             (f))))))))
@end group
@end lisp
@end deffn

To assign meanings to the identifiers in a form, use
@code{make-syntactic-closure} to close the form in a syntactic
environment.@refill

@deffn procedure make-syntactic-closure environment free-names form
@var{Environment} must be a syntactic environment, @var{free-names}
must be a list of identifiers, and @var{form} must be a form.
@code{make-syntactic-closure} constructs and returns a syntactic
closure of @var{form} in @var{environment}, which can be used anywhere
that @var{form} could have been used.  All the identifiers used in
@var{form}, except those explicitly excepted by @var{free-names},
obtain their meanings from @var{environment}.@refill

Here is an example where @var{free-names} is something other than the
empty list.  It is instructive to compare the use of @var{free-names}
in this example with its use in the @code{loop} example above: the
examples are similar except for the source of the identifier being left
free.@refill

@lisp
@group
(define-syntax let1
  (transformer
   (lambda (exp env)
     (let ((id (cadr exp))
           (init (caddr exp))
           (exp (cadddr exp)))
       `((lambda (,id)
           ,(make-syntactic-closure env (list id) exp))
         ,(make-syntactic-closure env '() init))))))
@end group
@end lisp

@noindent
@code{let1} is a simplified version of @code{let} that only binds a
single identifier, and whose body consists of a single expression.
When the body expression is syntactically closed in its original
syntactic environment, the identifier that is to be bound by
@code{let1} must be left free, so that it can be properly captured by
the @code{lambda} in the output form.@refill
@end deffn

To obtain a syntactic environment other than the usage environment,
use @code{capture-syntactic-environment}.@refill

@deffn procedure capture-syntactic-environment procedure
@code{capture-syntactic-environment} returns a form that will, when
transformed, call @var{procedure} on the current syntactic environment.
@var{Procedure} should compute and return a new form to be transformed,
in that same syntactic environment, in place of the form.@refill

An example will make this clear.  Suppose we wanted to define a simple
@code{loop-until} keyword equivalent to@refill

@lisp
@group
(define-syntax loop-until
  (syntax-rules ()
    ((loop-until id init test return step)
     (letrec ((loop
               (lambda (id)
                 (if test return (loop step)))))
       (loop init)))))
@end group
@end lisp

@noindent
The following attempt at defining @code{loop-until} has a subtle
bug:@refill

@lisp
@group
(define-syntax loop-until
  (transformer
   (lambda (exp env)
     (let ((id (cadr exp))
           (init (caddr exp))
           (test (cadddr exp))
           (return (cadddr (cdr exp)))
           (step (cadddr (cddr exp)))
           (close
            (lambda (exp free)
              (make-syntactic-closure env free exp))))
       `(letrec ((loop
                  (lambda (,id)
                    (if ,(close test (list id))
                        ,(close return (list id))
                        (loop ,(close step (list id)))))))
          (loop ,(close init '())))))))
@end group
@end lisp

@noindent
This definition appears to take all of the proper precautions to
prevent unintended captures.  It carefully closes the subexpressions in
their original syntactic environment and it leaves the @code{id}
identifier free in the @code{test}, @code{return}, and @code{step}
expressions, so that it will be captured by the binding introduced by
the @code{lambda} expression.  Unfortunately it uses the identifiers
@code{if} and @code{loop} @emph{within} that @code{lambda} expression,
so if the user of @code{loop-until} just happens to use, say, @code{if}
for the identifier, it will be inadvertently captured.@refill

The syntactic environment that @code{if} and @code{loop} want to be
exposed to is the one just outside the @code{lambda} expression: before
the user's identifier is added to the syntactic environment, but after
the identifier @code{loop} has been added.
@code{capture-syntactic-environment} captures exactly that environment
as follows:@refill

@lisp
@group
(define-syntax loop-until
  (transformer
   (lambda (exp env)
     (let ((id (cadr exp))
           (init (caddr exp))
           (test (cadddr exp))
           (return (cadddr (cdr exp)))
           (step (cadddr (cddr exp)))
           (close
            (lambda (exp free)
              (make-syntactic-closure env free exp))))
       `(letrec ((loop
                  ,(capture-syntactic-environment
                    (lambda (env)
                      `(lambda (,id)
                         (,(make-syntactic-closure env '() `if)
                          ,(close test (list id))
                          ,(close return (list id))
                          (,(make-syntactic-closure env '() `loop)
                           ,(close step (list id)))))))))
          (loop ,(close init '())))))))
@end group
@end lisp

@noindent
In this case, having captured the desired syntactic environment, it is
convenient to construct syntactic closures of the identifiers @code{if}
and the @code{loop} and use them in the body of the
@code{lambda}.@refill

A common use of @code{capture-syntactic-environment} is to get the
transformer environment of a macro transformer:@refill

@lisp
@group
(transformer
 (lambda (exp env)
   (capture-syntactic-environment
    (lambda (transformer-env)
      @dots{}))))
@end group
@end lisp
@end deffn

@node Identifiers, Acknowledgments, Transformer Definition, Top
@heading Identifiers

This section describes the procedures that create and manipulate
identifiers.  Previous syntactic closure proposals did not have an
identifier data type---they just used symbols.  The identifier data
type extends the syntactic closures facility to be compatible with the
high-level @code{syntax-rules} facility.@refill

@cindex alias
As discussed earlier, an identifier is either a symbol or an
@dfn{alias}.  An alias is implemented as a syntactic closure whose
@var{form} is an identifier:@refill

@lisp
@group
(make-syntactic-closure env '() 'a) @result{} @r{an alias}
@end group
@end lisp

@noindent
Aliases are implemented as syntactic closures because they behave just
like syntactic closures most of the time.  The difference is that an
alias may be bound to a new value (for example by @code{lambda} or
@code{let-syntax}); other syntactic closures may not be used this way.
If an alias is bound, then within the scope of that binding it is
looked up in the syntactic environment just like any other
identifier.@refill

Aliases are used in the implementation of the high-level facility
@code{syntax-rules}.  A macro transformer created by
@code{syntax-rules} uses a template to generate its output form,
substituting subforms of the input form into the template.  In a
syntactic closures implementation, all of the symbols in the template
are replaced by aliases closed in the transformer environment, while
the output form itself is closed in the usage environment.  This
guarantees that the macro transformation is hygienic, without requiring
the transformer to know the syntactic roles of the substituted input
subforms.@refill

@deffn procedure identifier? object
Returns @code{#t} if @var{object} is an identifier, otherwise returns
@code{#f}.  Examples:@refill

@lisp
@group
(identifier? 'a)        @result{} #t
(identifier? (make-syntactic-closure env '() 'a))
                        @result{} #t

(identifier? "a")       @result{} #f
(identifier? #\a)       @result{} #f
(identifier? 97)        @result{} #f
(identifier? #f)        @result{} #f
(identifier? '(a))      @result{} #f
(identifier? '#(a))     @result{} #f
@end group
@end lisp
@end deffn

The predicate @code{eq?} is used to determine if two identifers are
``the same''.  Thus @code{eq?} can be used to compare identifiers
exactly as it would be used to compare symbols.  Often, though, it is
useful to know whether two identifiers ``mean the same thing''.  For
example, the @code{cond} macro uses the symbol @code{else} to identify
the final clause in the conditional.  A macro transformer for @code{cond}
cannot just look for the symbol @code{else}, because the @code{cond}
form might be the output of another macro transformer that replaced the
symbol @code{else} with an alias.  Instead the transformer must look for
an identifier that ``means the same thing'' in the usage
environment as the symbol @code{else} means in the transformer
environment.@refill

@deffn procedure identifier=? environment1 identifier1 environment2 identifier2
@var{Environment1} and @var{environment2} must be syntactic
environments, and @var{identifier1} and @var{identifier2} must be
identifiers.  @code{identifier=?} returns @code{#t} if the meaning of
@var{identifier1} in @var{environment1} is the same as that of
@var{identifier2} in @var{environment2}, otherwise it returns @code{#f}.
Examples:@refill

@lisp
@group
(let-syntax
    ((foo
      (transformer
       (lambda (form env)
         (capture-syntactic-environment
          (lambda (transformer-env)
            (identifier=? transformer-env 'x env 'x)))))))
  (list (foo)
        (let ((x 3))
          (foo))))
                        @result{} (#t #f)
@end group

@group
(let-syntax ((bar foo))
  (let-syntax
      ((foo
        (transformer
         (lambda (form env)
           (capture-syntactic-environment
            (lambda (transformer-env)
              (identifier=? transformer-env 'foo
                            env (cadr form))))))))
    (list (foo foo)
          (foo bar))))
                        @result{} (#f #t)
@end group
@end lisp
@end deffn

@node Acknowledgments, , Identifiers, Top
@heading Acknowledgments

The syntactic closures facility was invented by Alan Bawden and
Jonathan Rees.  The use of aliases to implement @code{syntax-rules} was
invented by Alan Bawden (who prefers to call them ``synthetic names'').
Much of this proposal is derived from an earlier proposal by Alan
Bawden.

@bye
