   This file documents the MIT Scheme system.

   Copyright (C) 1988-2002 Massachusetts Institute of Technology

   Permission is granted to copy, distribute and/or modify this document
under the terms of the GNU Free Documentation License, Version 1.1 or
any later version published by the Free Software Foundation; with no
Invariant Sections, with no Front-Cover Texts, and with no Back-Cover
Texts.  A copy of the license is included in the section entitled "GNU
Free Documentation License".

Macros
======

   (This section is largely taken from the `Revised^4 Report on the
Algorithmic Language Scheme'.  The section on Syntactic Closures is
derived from a document written by Chris Hanson.  The section on
Explicit Renaming is derived from a document written by William
Clinger.)

   Scheme programs can define and use new derived expression types,
called "macros".  Program-defined expression types have the syntax

     (KEYWORD DATUM ...)

where KEYWORD is an identifier that uniquely determines the expression
type.  This identifier is called the "syntactic keyword", or simply
"keyword", of the macro.  The number of the DATUMs, and their syntax,
depends on the expression type.

   Each instance of a macro is called a "use" of the macro.  The set of
rules that specifies how a use of a macro is transcribed into a more
primitive expression is called the "transformer" of the macro.

   MIT Scheme also supports "anonymous syntactic keywords".  This means
that it's not necessary to binding a macro transformer to a syntactic
keyword before it is used.  Instead, any macro-transformer expression
can appear as the first element of a form, and the form will be expanded
by the transformer.

   The macro definition facility consists of these parts:

   * A set of expressions used to establish that certain identifiers are
     macro keywords, associate them with macro transformers, and
     control the scope within which a macro is defined.

   * A standard high-level pattern language for specifying macro
     transformers, introduced by the `syntax-rules' special form.

   * Two non-standard low-level languages for specifying macro
     transformers, "syntactic closures" and "explicit renaming".

   The syntactic keyword of a macro may shadow variable bindings, and
local variable bindings may shadow keyword bindings.  All macros
defined using the pattern language are "hygienic" and "referentially
transparent" and thus preserve Scheme's lexical scoping:

   * If a macro transformer inserts a binding for an identifier
     (variable or keyword), the identifier will in effect be renamed
     throughout its scope to avoid conflicts with other identifiers.

   * If a macro transformer inserts a free reference to an identifier,
     the reference refers to the binding that was visible where the
     transformer was specified, regardless of any local bindings that
     may surround the use of the macro.

Binding Constructs for Syntactic Keywords
-----------------------------------------

   `let-syntax', `letrec-syntax', `let*-syntax' and `define-syntax' are
analogous to `let', `letrec', `let*' and `define', but they bind
syntactic keywords to macro transformers instead of binding variables
to locations that contain values.

 - special form: let-syntax bindings expression expression ...
     BINDINGS should have the form

          ((KEYWORD TRANSFORMER-SPEC) ...)

     Each KEYWORD is an identifier, each TRANSFORMER-SPEC is a a
     macro-transformer expression, and the body is a sequence of one or
     more expressions.  It is an error for a KEYWORD to appear more
     than once in the list of keywords being bound.

     The EXPRESSIONs are expanded in the syntactic environment obtained
     by extending the syntactic environment of the `let-syntax'
     expression with macros whose keywords are the KEYWORDs, bound to
     the specified transformers.  Each binding of a KEYWORD has the
     EXPRESSIONs as its region.

          (let-syntax ((when (syntax-rules ()
                               ((when test stmt1 stmt2 ...)
                                (if test
                                    (begin stmt1
                                           stmt2 ...))))))
            (let ((if #t))
              (when if (set! if 'now))
              if))                           =>  now

          (let ((x 'outer))
            (let-syntax ((m (syntax-rules () ((m) x))))
              (let ((x 'inner))
                (m))))                       =>  outer

 - special form: letrec-syntax bindings expression expression ...
     The syntax of `letrec-syntax' is the same as for `let-syntax'.

     The EXPRESSIONs are expanded in the syntactic environment obtained
     by extending the syntactic environment of the `letrec-syntax'
     expression with macros whose keywords are the KEYWORDs, bound to
     the specified transformers.  Each binding of a KEYWORD has the
     BINDINGS as well as the EXPRESSIONs within its region, so the
     transformers can transcribe expressions into uses of the macros
     introduced by the `letrec-syntax' expression.

          (letrec-syntax
            ((my-or (syntax-rules ()
                      ((my-or) #f)
                      ((my-or e) e)
                      ((my-or e1 e2 ...)
                       (let ((temp e1))
                         (if temp
                             temp
                             (my-or e2 ...)))))))
            (let ((x #f)
                  (y 7)
                  (temp 8)
                  (let odd?)
                  (if even?))
              (my-or x
                     (let temp)
                     (if y)
                     y)))        =>  7

 - special form: let*-syntax bindings expression expression ...
     The syntax of `let*-syntax' is the same as for `let-syntax'.

     The EXPRESSIONs are expanded in the syntactic environment obtained
     by extending the syntactic environment of the `letrec-syntax'
     expression with macros whose keywords are the KEYWORDs, bound to
     the specified transformers.  Each binding of a KEYWORD has the
     subsequent BINDINGS as well as the EXPRESSIONs within its region.
     Thus

          (let*-syntax
             ((a (syntax-rules ...))
              (b (syntax-rules ...)))
            ...)

     is equivalent to

          (let-syntax ((a (syntax-rules ...)))
            (let-syntax ((b (syntax-rules ...)))
              ...))

 - special form: define-syntax keyword transformer-spec
     KEYWORD is an identifier, and TRANSFORMER-SPEC is a macro
     transformer expression.  The syntactic environment is extended by
     binding the KEYWORD to the specified transformer.

     The region of the binding introduced by `define-syntax' is the
     entire block in which it appears.  However, the KEYWORD may only
     be used after it has been defined.

     MIT Scheme permits `define-syntax' to appear both at top level and
     within `lambda' bodies.  The Revised^4 Report permits only
     top-level uses of `define-syntax'.

     When compiling a program, a top-level instance of `define-syntax'
     both defines the syntactic keyword and generates code that will
     redefine the keyword when the program is loaded.  This means that
     the same syntax can be used for defining macros that will be used
     during compilation and for defining macros to be used at run time.

     Although macros may expand into definitions and syntax definitions
     in any context that permits them, it is an error for a definition
     or syntax definition to shadow a syntactic keyword whose meaning
     is needed to determine whether some form in the group of forms
     that contains the shadowing definition is in fact a definition,
     or, for internal definitions, is needed to determine the boundary
     between the group and the expressions that follow the group.  For
     example, the following are errors:

          (define define 3)

          (begin (define begin list))

          (let-syntax
            ((foo (syntax-rules ()
                    ((foo (proc args ...) body ...)
                     (define proc
                       (lambda (args ...)
                         body ...))))))
            (let ((x 3))
              (foo (plus x y) (+ x y))
              (define foo x)
              (plus foo x)))

Pattern Language
----------------

   MIT Scheme supports a high-level pattern language for specifying
macro transformers.  This pattern language is defined by the Revised^4
Report and is portable to other conforming Scheme implementations.  To
use the pattern language, specify a TRANSFORMER-SPEC as a
`syntax-rules' form:

 - special form: syntax-rules literals syntax-rule ...
     LITERALS is a list of identifiers and each SYNTAX-RULE should be
     of the form

          (PATTERN TEMPLATE)

     The PATTERN in a SYNTAX-RULE is a list PATTERN that begins with
     the keyword for the macro.

     A PATTERN is either an identifier, a constant, or one of the
     following

          (PATTERN ...)
          (PATTERN PATTERN ... . PATTERN)
          (PATTERN ... PATTERN ELLIPSIS)

     and a template is either an identifier, a constant, or one of the
     following

          (ELEMENT ...)
          (ELEMENT ELEMENT ... . TEMPLATE)

     where an ELEMENT is a TEMPLATE optionally followed by an ELLIPSIS
     and an ELLIPSIS is the identifier `...' (which cannot be used as
     an identifier in either a template or a pattern).

     An instance of `syntax-rules' produces a new macro transformer by
     specifying a sequence of hygienic rewrite rules.  A use of a macro
     whose keyword is associated with a transformer specified by
     `syntax-rules' is matched against the patterns contained in the
     SYNTAX-RULEs, beginning with the leftmost SYNTAX-RULE.  When a
     match is found, the macro use is transcribed hygienically
     according to the template.

     An identifier that appears in the pattern of a SYNTAX-RULE is a
     "pattern-variable", unless it is the keyword that begins the
     pattern, is listed in LITERALS, or is the identifier `...'.
     Pattern variables match arbitrary input elements and are used to
     refer to elements of the input in the template.  It is an error
     for the same pattern variable to appear more than once in a
     PATTERN.

     The keyword at the beginning of the pattern in a SYNTAX-RULE is
     not involved in the matching and is not considered a pattern
     variable or literal identifier.

     Identifiers that appear in LITERALS are interpreted as literal
     identifiers to be matched against corresponding subforms of the
     input.  A subform in the input matches a literal identifier if and
     only if it is an identifier and either both its occurrence in the
     macro expression and its occurrence in the macro definition have
     the same lexical binding, or the two identifiers are equal and
     both have no lexical binding.

     A subpattern followed by `...' can match zero or more elements of
     the input.  It is an error for `...' to appear in LITERALS.
     Within a pattern the identifier `...' must follow the last element
     of a nonempty sequence of subpatterns.

     More formally, an input form F matches a pattern P if and only if:

        * P is a non-literal identifier; or

        * P is a literal identifier and F is an identifier with the
          same binding; or

        * P is a list `(P_1 ... P_N)' and F is a list of N forms that
          match P_1 through P_N, respectively; or

        * P is an improper list `(P_1 P_2 ... P_N . P_N+1)' and F is a
          list or improper list of N or more forms that match P_1
          through P_N, respectively, and whose Nth "cdr" matches P_N+1;
          or

        * P is of the form `(P_1 ... P_N P_N+1 ELLIPSIS)' where
          ELLIPSIS is the identifier `...' and F is a proper list of at
          least N forms, the first N of which match P_1 through P_N,
          respectively, and each remaining element of F matches P_N+1;
          or

        * P is a datum and F is equal to P in the sense of the `equal?'
          procedure.

     It is an error to use a macro keyword, within the scope of its
     binding, in an expression that does not match any of the patterns.

     When a macro use is transcribed according to the template of the
     matching SYNTAX RULE, pattern variables that occur in the template
     are replaced by the subforms they match in the input.  Pattern
     variables that occur in subpatterns followed by one or more
     instances of the identifier `...' are allowed only in subtemplates
     that are followed by as many instances of `...'.  They are
     replaced in the output by all of the subforms they match in the
     input, distributed as indicated.  It is an error if the output
     cannot be built up as specified.

     Identifiers that appear in the template but are not pattern
     variables or the identifier `...' are inserted into the output as
     literal identifiers.  If a literal identifier is inserted as a
     free identifier then it refers to the binding of that identifier
     within whose scope the instance of `syntax-rules' appears.  If a
     literal identifier is inserted as a bound identifier then it is in
     effect renamed to prevent inadvertent captures of free identifiers.

          (let ((=> #f))
            (cond (#t => 'ok)))           => ok

     The macro transformer for `cond' recognizes `=>' as a local
     variable, and hence an expression, and not as the top-level
     identifier `=>', which the macro transformer treats as a syntactic
     keyword.  Thus the example expands into

          (let ((=> #f))
            (if #t (begin => 'ok)))

     instead of

          (let ((=> #f))
            (let ((temp #t))
              (if temp
                  ('ok temp))))

     which would result in an invalid procedure call.

Syntactic Closures
------------------

   MIT Scheme's syntax-transformation engine is an implementation of
"syntactic closures", a mechanism invented by Alan Bawden and Jonathan
Rees.  The main feature of the syntactic-closures mechanism is its
simplicity and its close relationship to the environment models
commonly used with Scheme.  Using the mechanism to write macro
transformers is somewhat cumbersome and can be confusing for the newly
initiated, but it is easily mastered.

Syntax Terminology
..................

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

   * "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 `set!' special form is also a
     form.  Examples of forms:

          17
          #t
          car
          (+ x 4)
          (lambda (x) x)
          (define pi 3.14159)
          if
          define

   * An "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 `symbol?'.  Macro transformers rarely distinguish
     symbols from aliases, referring to both as "identifiers".  Another
     name for an alias is "synthetic identifier"; this document uses
     both names.

   * A "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.

   * A "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.

     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 `cond' special
     form.

     A syntactic closure appearing in a quoted structure is replaced by
     its form.

Transformer Definition
......................

   This section describes the special forms for defining
syntactic-closures macro transformers, and the associated procedures
for manipulating syntactic closures and syntactic environments.

 - special form: sc-macro-transformer expression
     The EXPRESSION is expanded in the syntactic environment of the
     `sc-macro-transformer' expression, and the expanded expression is
     evaluated in the 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 `transformer'
     expression appears (for example, `let-syntax').

     In the syntactic closures facility, a "macro transformer" is a
     procedure that takes two arguments, a form and a syntactic
     environment, and returns a new form.  The first argument, the
     "input form", is the form in which the macro keyword occurred.
     The second argument, the "usage environment", is the syntactic
     environment in which the input form occurred.  The result of the
     transformer, the "output form", is automatically closed in the
     "transformer environment", which is the syntactic environment in
     which the `transformer' expression occurred.

     For example, here is a definition of a `push' macro using
     `syntax-rules':

          (define-syntax push
            (syntax-rules ()
              ((push item list)
               (set! list (cons item list)))))

     Here is an equivalent definition using `sc-macro-transformer':

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

     In this example, the identifiers `set!' and `cons' are closed in
     the transformer environment, and thus will not be affected by the
     meanings of those identifiers in the usage environment `env'.

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

          (define-syntax loop
            (sc-macro-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))))))))

 - special form: rsc-macro-transformer expression
     This form is an alternative way to define a syntactic-closures
     macro transformer.  Its syntax and usage are identical to
     `sc-macro-transformer', except that the roles of the usage
     environment and transformer environment are reversed.  (Hence RSC
     stands for "Reversed Syntactic Closures".)  In other words, the
     procedure specified by EXPRESSION still accepts two arguments, but
     its second argument will be the transformer environment rather
     than the usage environment, and the returned expression is closed
     in the usage environment rather than the transformer environment.

     The advantage of this arrangement is that it allows a simpler
     definition style in some situations.  For example, here is the
     `push' macro from above, rewritten in this style:

          (define-syntax push
            (rsc-macro-transformer
             (lambda (exp env)
               `(,(make-syntactic-closure env '() 'SET!)
                 ,(caddr exp)
                 (,(make-syntactic-closure env '() 'CONS)
                  ,(cadr exp)
                  ,(caddr exp))))))

     In this style only the introduced keywords are closed, while
     everything else remains open.

     Note that `rsc-macro-transformer' and `sc-macro-transformer' are
     easily interchangeable.  Here is how to emulate
     `rsc-macro-transformer' using `sc-macro-transformer'.  (This
     technique can be used to effect the opposite emulation as well.)

          (define-syntax push
            (sc-macro-transformer
             (lambda (exp usage-env)
               (capture-syntactic-environment
                (lambda (env)
                  (make-syntactic-closure usage-env '()
                    `(,(make-syntactic-closure env '() 'SET!)
                      ,(caddr exp)
                      (,(make-syntactic-closure env '() 'CONS)
                       ,(cadr exp)
                       ,(caddr exp)))))))))

   To assign meanings to the identifiers in a form, use
`make-syntactic-closure' to close the form in a syntactic environment.

 - procedure: make-syntactic-closure environment free-names form
     ENVIRONMENT must be a syntactic environment, FREE-NAMES must be a
     list of identifiers, and FORM must be a form.
     `make-syntactic-closure' constructs and returns a syntactic
     closure of FORM in ENVIRONMENT, which can be used anywhere that
     FORM could have been used.  All the identifiers used in FORM,
     except those explicitly excepted by FREE-NAMES, obtain their
     meanings from ENVIRONMENT.

     Here is an example where FREE-NAMES is something other than the
     empty list.  It is instructive to compare the use of FREE-NAMES in
     this example with its use in the `loop' example above: the
     examples are similar except for the source of the identifier being
     left free.

          (define-syntax let1
            (sc-macro-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))))))

     `let1' is a simplified version of `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
     `let1' must be left free, so that it can be properly captured by
     the `lambda' in the output form.

   In most situations, the FREE-NAMES argument to
`make-syntactic-closure' is the empty list.  In those cases, the more
succinct `close-syntax' can be used:

 - procedure: close-syntax form environment
     ENVIRONMENT must be a syntactic environment and FORM must be a
     form.  Returns a new syntactic closure of FORM in ENVIRONMENT,
     with no free names.  Entirely equivalent to

          (make-syntactic-closure ENVIRONMENT '() FORM)

   To obtain a syntactic environment other than the usage environment,
use `capture-syntactic-environment'.

 - procedure: capture-syntactic-environment procedure
     `capture-syntactic-environment' returns a form that will, when
     transformed, call PROCEDURE on the current syntactic environment.
     PROCEDURE should compute and return a new form to be transformed,
     in that same syntactic environment, in place of the form.

     An example will make this clear.  Suppose we wanted to define a
     simple `loop-until' keyword equivalent to

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

     The following attempt at defining `loop-until' has a subtle bug:

          (define-syntax loop-until
            (sc-macro-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 '())))))))

     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 `id' identifier free in the `test', `return', and `step'
     expressions, so that it will be captured by the binding introduced
     by the `lambda' expression.  Unfortunately it uses the identifiers
     `if' and `loop' _within_ that `lambda' expression, so if the user
     of `loop-until' just happens to use, say, `if' for the identifier,
     it will be inadvertently captured.

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

          (define-syntax loop-until
            (sc-macro-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 '())))))))

     In this case, having captured the desired syntactic environment,
     it is convenient to construct syntactic closures of the
     identifiers `if' and the `loop' and use them in the body of the
     `lambda'.

     A common use of `capture-syntactic-environment' is to get the
     transformer environment of a macro transformer:

          (sc-macro-transformer
           (lambda (exp env)
             (capture-syntactic-environment
              (lambda (transformer-env)
                ...))))

Identifiers
...........

   This section describes the procedures that create and manipulate
identifiers.  The identifier data type extends the syntactic closures
facility to be compatible with the high-level `syntax-rules' facility.

   As discussed earlier, an identifier is either a symbol or an
"alias".  An alias is implemented as a syntactic closure whose FORM is
an identifier:

     (make-syntactic-closure env '() 'a) => an alias

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 `lambda' or
`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.

   Aliases are used in the implementation of the high-level facility
`syntax-rules'.  A macro transformer created by `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.

 - procedure: identifier? object
     Returns `#t' if OBJECT is an identifier, otherwise returns `#f'.
     Examples:

          (identifier? 'a)        => #t
          (identifier? (make-syntactic-closure env '() 'a))
                                  => #t

          (identifier? "a")       => #f
          (identifier? #\a)       => #f
          (identifier? 97)        => #f
          (identifier? #f)        => #f
          (identifier? '(a))      => #f
          (identifier? '#(a))     => #f

   The predicate `eq?' is used to determine if two identifers are "the
same".  Thus `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 `cond'
macro uses the symbol `else' to identify the final clause in the
conditional.  A macro transformer for `cond' cannot just look for the
symbol `else', because the `cond' form might be the output of another
macro transformer that replaced the symbol `else' with an alias.
Instead the transformer must look for an identifier that "means the
same thing" in the usage environment as the symbol `else' means in the
transformer environment.

 - procedure: identifier=? environment1 identifier1 environment2
          identifier2
     ENVIRONMENT1 and ENVIRONMENT2 must be syntactic environments, and
     IDENTIFIER1 and IDENTIFIER2 must be identifiers.  `identifier=?'
     returns `#t' if the meaning of IDENTIFIER1 in ENVIRONMENT1 is the
     same as that of IDENTIFIER2 in ENVIRONMENT2, otherwise it returns
     `#f'.  Examples:

          (let-syntax
              ((foo
                (sc-macro-transformer
                 (lambda (form env)
                   (capture-syntactic-environment
                    (lambda (transformer-env)
                      (identifier=? transformer-env 'x env 'x)))))))
            (list (foo)
                  (let ((x 3))
                    (foo))))
                                  => (#t #f)

          (let-syntax ((bar foo))
            (let-syntax
                ((foo
                  (sc-macro-transformer
                   (lambda (form env)
                     (capture-syntactic-environment
                      (lambda (transformer-env)
                        (identifier=? transformer-env 'foo
                                      env (cadr form))))))))
              (list (foo foo)
                    (foo bar))))
                                  => (#f #t)

   Sometimes it is useful to be able to introduce a new identifier that
is guaranteed to be different from any existing identifier, similarly to
the way that `generate-uninterned-symbol' is used.

 - procedure: make-synthetic-identifier identifier
     Creates and returns and new synthetic identifier (alias) that is
     guaranteed to be different from all existing identifiers.
     IDENTIFIER is any existing identifier, which is used in deriving
     the name of the new identifier.

     This is implemented by syntactically closing IDENTIFIER in a
     special empty environment.

Explicit Renaming
-----------------

   "Explicit renaming" is an alternative facility for defining macro
transformers.  In the MIT Scheme implementation, explicit-renaming
transformers are implemented as an abstraction layer on top of syntactic
closures.  An explicit-renaming macro transformer is defined by an
instance of the `er-macro-transformer' keyword:

 - special form: er-macro-transformer expression
     The EXPRESSION is expanded in the syntactic environment of the
     `er-macro-transformer' expression, and the expanded expression is
     evaluated in the 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 `transformer'
     expression appears (for example, `let-syntax').

     In the explicit-renaming facility, a "macro transformer" is a
     procedure that takes three arguments, a form, a renaming
     procedure, and a comparison predicate, and returns a new form.
     The first argument, the "input form", is the form in which the
     macro keyword occurred.

     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 `let'
     macro might be written as

          (lambda (exp rename compare)
            (let ((vars (map car (cadr exp)))
                  (inits (map cadr (cadr exp)))
                  (body (cddr exp)))
              `((lambda ,vars ,@body)
                ,@inits)))

     This would not be hygienic, however.  A hygienic `let' macro must
     rename the identifier `lambda' to protect it from being captured by
     a local binding.  The renaming effectively creates an fresh alias
     for `lambda', one that cannot be captured by any subsequent
     binding:

          (lambda (exp rename compare)
            (let ((vars (map car (cadr exp)))
                  (inits (map cadr (cadr exp)))
                  (body (cddr exp)))
              `((,(rename 'lambda) ,vars ,@body)
                ,@inits)))

     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 `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 `cond' macro can be
     written as

          (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))))))))))

     In this example the identifier `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 `else' denotes in the syntactic environment
     in which the `cond' macro was defined.  If `else' were not renamed
     before being passed to the comparison predicate, then it would
     match a local variable that happened to be named `else', and the
     macro would not be hygienic.

     Some macros are non-hygienic by design.  For example, the following
     defines a `loop' macro that implicitly binds `exit' to an escape
     procedure.  The binding of `exit' is intended to capture free
     references to `exit' in the body of the loop, so `exit' is not
     renamed.

          (define-syntax loop
            (er-macro-transformer
             (lambda (x r c)
               (let ((body (cdr x)))
                 `(,(r 'call-with-current-continuation)
                   (,(r 'lambda) (exit)
                    (,(r 'let) ,(r 'f) () ,@body (,(r 'f)))))))))

     Suppose a `while' macro is implemented using `loop', with the
     intent that `exit' may be used to escape from the `while' loop.
     The `while' macro cannot be written as

          (define-syntax while
            (syntax-rules ()
              ((while test body ...)
               (loop (if (not test) (exit #f))
                     body ...))))

     because the reference to `exit' that is inserted by the `while'
     macro is intended to be captured by the binding of `exit' that
     will be inserted by the `loop' macro.  In other words, this
     `while' macro is not hygienic.  Like `loop', it must be written
     using the `er-macro-transformer' syntax:

          (define-syntax while
            (er-macro-transformer
             (lambda (x r c)
               (let ((test (cadr x))
                     (body (cddr x)))
                 `(,(r 'loop)
                   (,(r 'if) (,(r 'not) ,test) (exit #f))
                   ,@body)))))

Equivalence Predicates
**********************

   A "predicate" is a procedure that always returns a boolean value
(`#t' or `#f').  An "equivalence predicate" is the computational
analogue of a mathematical equivalence relation (it is symmetric,
reflexive, and transitive).  Of the equivalence predicates described in
this section, `eq?' is the finest or most discriminating, and `equal?'
is the coarsest.  `eqv?' is slightly less discriminating than `eq?'.

 - procedure: eqv? obj1 obj2
     The `eqv?' procedure defines a useful equivalence relation on
     objects.  Briefly, it returns `#t' if OBJ1 and OBJ2 should
     normally be regarded as the same object.

     The `eqv?' procedure returns `#t' if:

        * OBJ1 and OBJ2 are both `#t' or both `#f'.

        * OBJ1 and OBJ2 are both interned symbols and

               (string=? (symbol->string OBJ1)
                         (symbol->string OBJ2))
                    => #t

        * OBJ1 and OBJ2 are both numbers, are numerically equal
          according to the `=' procedure, and are either both exact or
          both inexact (see Numbers).

        * OBJ1 and OBJ2 are both characters and are the same character
          according to the `char=?' procedure (see Characters).

        * both OBJ1 and OBJ2 are the empty list.

        * OBJ1 and OBJ2 are procedures whose location tags are equal.

        * OBJ1 and OBJ2 are pairs, vectors, strings, bit strings,
          records, cells, or weak pairs that denote the same locations
          in the store.

     The `eqv?' procedure returns `#f' if:

        * OBJ1 and OBJ2 are of different types.

        * one of OBJ1 and OBJ2 is `#t' but the other is `#f'.

        * OBJ1 and OBJ2 are symbols but

               (string=? (symbol->string OBJ1)
                         (symbol->string OBJ2))
                    => #f

        * one of OBJ1 and OBJ2 is an exact number but the other is an
          inexact number.

        * OBJ1 and OBJ2 are numbers for which the `=' procedure returns
          `#f'.

        * OBJ1 and OBJ2 are characters for which the `char=?' procedure
          returns `#f'.

        * one of OBJ1 and OBJ2 is the empty list but the other is not.

        * OBJ1 and OBJ2 are procedures that would behave differently
          (return a different value or have different side effects) for
          some arguments.

        * OBJ1 and OBJ2 are pairs, vectors, strings, bit strings,
          records, cells, or weak pairs that denote distinct locations.

     Some examples:

          (eqv? 'a 'a)                    =>  #t
          (eqv? 'a 'b)                    =>  #f
          (eqv? 2 2)                      =>  #t
          (eqv? '() '())                  =>  #t
          (eqv? 100000000 100000000)      =>  #t
          (eqv? (cons 1 2) (cons 1 2))    =>  #f
          (eqv? (lambda () 1)
                (lambda () 2))            =>  #f
          (eqv? #f 'nil)                  =>  #f
          (let ((p (lambda (x) x)))
            (eqv? p p))                   =>  #t

     The following examples illustrate cases in which the above rules
     do not fully specify the behavior of `eqv?'.  All that can be said
     about such cases is that the value returned by `eqv?' must be a
     boolean.

          (eqv? "" "")                    =>  unspecified
          (eqv? '#() '#())                =>  unspecified
          (eqv? (lambda (x) x)
                (lambda (x) x))           =>  unspecified
          (eqv? (lambda (x) x)
                (lambda (y) y))           =>  unspecified

     The next set of examples shows the use of `eqv?' with procedures
     that have local state.  `gen-counter' must return a distinct
     procedure every time, since each procedure has its own internal
     counter.  `gen-loser', however, returns equivalent procedures each
     time, since the local state does not affect the value or side
     effects of the procedures.

          (define gen-counter
            (lambda ()
              (let ((n 0))
                (lambda () (set! n (+ n 1)) n))))
          (let ((g (gen-counter)))
            (eqv? g g))                   =>  #t
          (eqv? (gen-counter) (gen-counter))
                                          =>  #f

          (define gen-loser
            (lambda ()
              (let ((n 0))
                (lambda () (set! n (+ n 1)) 27))))
          (let ((g (gen-loser)))
            (eqv? g g))                   =>  #t
          (eqv? (gen-loser) (gen-loser))
                                          =>  unspecified

          (letrec ((f (lambda () (if (eqv? f g) 'both 'f)))
                   (g (lambda () (if (eqv? f g) 'both 'g)))
            (eqv? f g))
                                          =>  unspecified

          (letrec ((f (lambda () (if (eqv? f g) 'f 'both)))
                   (g (lambda () (if (eqv? f g) 'g 'both)))
            (eqv? f g))
                                          =>  #f

     Objects of distinct types must never be regarded as the same
     object.

     Since it is an error to modify constant objects (those returned by
     literal expressions), the implementation may share structure
     between constants where appropriate.  Thus the value of `eqv?' on
     constants is sometimes unspecified.

          (let ((x '(a)))
            (eqv? x x))                    =>  #t
          (eqv? '(a) '(a))                 =>  unspecified
          (eqv? "a" "a")                   =>  unspecified
          (eqv? '(b) (cdr '(a b)))         =>  unspecified

     Rationale: The above definition of `eqv?' allows implementations
     latitude in their treatment of procedures and literals:
     implementations are free either to detect or to fail to detect
     that two procedures or two literals are equivalent to each other,
     and can decide whether or not to merge representations of
     equivalent objects by using the same pointer or bit pattern to
     represent both.

 - procedure: eq? obj1 obj2
     `eq?' is similar to `eqv?' except that in some cases it is capable
     of discerning distinctions finer than those detectable by `eqv?'.

     `eq?' and `eqv?' are guaranteed to have the same behavior on
     symbols, booleans, the empty list, pairs, records, and non-empty
     strings and vectors.  `eq?''s behavior on numbers and characters is
     implementation-dependent, but it will always return either true or
     false, and will return true only when `eqv?' would also return
     true.  `eq?' may also behave differently from `eqv?' on empty
     vectors and empty strings.

          (eq? 'a 'a)                     =>  #t
          (eq? '(a) '(a))                 =>  unspecified
          (eq? (list 'a) (list 'a))       =>  #f
          (eq? "a" "a")                   =>  unspecified
          (eq? "" "")                     =>  unspecified
          (eq? '() '())                   =>  #t
          (eq? 2 2)                       =>  unspecified
          (eq? #\A #\A)                   =>  unspecified
          (eq? car car)                   =>  #t
          (let ((n (+ 2 3)))
            (eq? n n))                    =>  unspecified
          (let ((x '(a)))
            (eq? x x))                    =>  #t
          (let ((x '#()))
            (eq? x x))                    =>  #t
          (let ((p (lambda (x) x)))
            (eq? p p))                    =>  #t

     Rationale: It will usually be possible to implement `eq?' much more
     efficiently than `eqv?', for example, as a simple pointer
     comparison instead of as some more complicated operation.  One
     reason is that it may not be possible to compute `eqv?' of two
     numbers in constant time, whereas `eq?' implemented as pointer
     comparison will always finish in constant time.  `eq?' may be used
     like `eqv?' in applications using procedures to implement objects
     with state since it obeys the same constraints as `eqv?'.

 - procedure: equal? obj1 obj2
     `equal?' recursively compares the contents of pairs, vectors, and
     strings, applying `eqv?' on other objects such as numbers, symbols,
     and records.  A rule of thumb is that objects are generally
     `equal?' if they print the same.  `equal?' may fail to terminate
     if its arguments are circular data structures.

          (equal? 'a 'a)                  =>  #t
          (equal? '(a) '(a))              =>  #t
          (equal? '(a (b) c)
                  '(a (b) c))             =>  #t
          (equal? "abc" "abc")            =>  #t
          (equal? 2 2)                    =>  #t
          (equal? (make-vector 5 'a)
                  (make-vector 5 'a))     =>  #t
          (equal? (lambda (x) x)
                  (lambda (y) y))         =>  unspecified

Numbers
*******

   (This section is largely taken from the `Revised^4 Report on the
Algorithmic Language Scheme'.)

   Numerical computation has traditionally been neglected by the Lisp
community.  Until Common Lisp there was no carefully thought out
strategy for organizing numerical computation, and with the exception of
the MacLisp system little effort was made to execute numerical code
efficiently.  This report recognizes the excellent work of the Common
Lisp committee and accepts many of their recommendations.  In some ways
this report simplifies and generalizes their proposals in a manner
consistent with the purposes of Scheme.

   It is important to distinguish between the mathematical numbers, the
Scheme numbers that attempt to model them, the machine representations
used to implement the Scheme numbers, and notations used to write
numbers.  This report uses the types _number_, _complex_, _real_,
_rational_, and _integer_ to refer to both mathematical numbers and
Scheme numbers.  Machine representations such as fixed point and
floating point are referred to by names such as _fixnum_ and _flonum_.