20 February 1998

Conditionals
------------

 - library syntax: cond <clause1> <clause2> ...,
     _Syntax:_ Each <clause> should be of the form

     (<test> <expression1> ...,)

     where <test> is any expression.  Alternatively, a <clause> may be
     of the form

     (<test> => <expression>)

     The last <clause> may be an "else clause," which has the form

     (else <expression1> <expression2> ...,).

     _Semantics:_ A `cond' expression is evaluated by evaluating the
     <test> expressions of successive <clause>s in order until one of
     them evaluates to a true value (see section Booleans).
     When a <test> evaluates to a true value, then the remaining
     <expression>s in its <clause> are evaluated in order, and the
     result(s) of the last <expression> in the <clause> is(are)
     returned as the result(s) of the entire `cond' expression.  If the
     selected <clause> contains only the <test> and no <expression>s,
     then the value of the <test> is returned as the result.  If the
     selected <clause> uses the `=>' alternate form, then the
     <expression> is evaluated.  Its value must be a procedure that
     accepts one argument; this procedure is then called on the value
     of the <test> and the value(s) returned by this procedure is(are)
     returned by the `cond' expression.  If all <test>s evaluate to
     false values, and there is no else clause, then the result of the
     conditional expression is unspecified; if there is an else clause,
     then its <expression>s are evaluated, and the value(s) of the last
     one is(are) returned.

     (cond ((> 3 2) 'greater)
           ((< 3 2) 'less))                 ==>  greater

     (cond ((> 3 3) 'greater)
           ((< 3 3) 'less)
           (else 'equal))                   ==>  equal

     (cond ((assv 'b '((a 1) (b 2))) => cadr)
           (else #f))                       ==>  2

 - library syntax: case <key> <clause1> <clause2> ...,
     _Syntax:_ <Key> may be any expression.  Each <clause> should have
     the form

     ((<datum1> ...,) <expression1> <expression2> ...,),

     where each <datum> is an external representation of some object.
     All the <datum>s must be distinct.  The last <clause> may be an
     "else clause," which has the form

     (else <expression1> <expression2> ...,).

     _Semantics:_ A `case' expression is evaluated as follows.  <Key> is
     evaluated and its result is compared against each <datum>.  If the
     result of evaluating <key> is equivalent (in the sense of `eqv?';
     see section Equivalence predicates) to a <datum>, then the
     expressions in the corresponding <clause> are evaluated from left
     to right and the result(s) of the last expression in the <clause>
     is(are) returned as the result(s) of the `case' expression.  If
     the result of evaluating <key> is different from every <datum>,
     then if there is an else clause its expressions are evaluated and
     the result(s) of the last is(are) the result(s) of the `case'
     expression; otherwise the result of the `case' expression is
     unspecified.

     (case (* 2 3)
       ((2 3 5 7) 'prime)
       ((1 4 6 8 9) 'composite))            ==>  composite
     (case (car '(c d))
       ((a) 'a)
       ((b) 'b))                            ==>  _unspecified_
     (case (car '(c d))
       ((a e i o u) 'vowel)
       ((w y) 'semivowel)
       (else 'consonant))                   ==>  consonant

 - library syntax: and <test1> ...,
     The <test> expressions are evaluated from left to right, and the
     value of the first expression that evaluates to a false value (see
     section Booleans) is returned.  Any remaining expressions
     are not evaluated.  If all the expressions evaluate to true
     values, the value of the last expression is returned.  If there
     are no expressions then #t is returned.

     (and (= 2 2) (> 2 1))                  ==>  #t
     (and (= 2 2) (< 2 1))                  ==>  #f
     (and 1 2 'c '(f g))                    ==>  (f g)
     (and)                                  ==>  #t

 - library syntax: or <test1> ...,
     The <test> expressions are evaluated from left to right, and the
     value of the first expression that evaluates to a true value (see
     section Booleans) is returned.  Any remaining expressions
     are not evaluated.  If all expressions evaluate to false values,
     the value of the last expression is returned.  If there are no
     expressions then #f is returned.

     (or (= 2 2) (> 2 1))                   ==>  #t
     (or (= 2 2) (< 2 1))                   ==>  #t
     (or #f #f #f)                          ==>  #f
     (or (memq 'b '(a b c))
         (/ 3 0))                           ==>  (b c)

Binding constructs
------------------

The three binding constructs `let', `let*', and `letrec' give Scheme a
block structure, like Algol 60.  The syntax of the three constructs is
identical, but they differ in the regions they establish for their
variable bindings.  In a `let' expression, the initial values are
computed before any of the variables become bound; in a `let*'
expression, the bindings and evaluations are performed sequentially;
while in a `letrec' expression, all the bindings are in effect while
their initial values are being computed, thus allowing mutually
recursive definitions.

 - library syntax: let <bindings> <body>
     _Syntax:_ <Bindings> should have the form

     ((<variable1> <init1>) ...,),

     where each <init> is an expression, and <body> should be a
     sequence of one or more expressions.  It is an error for a
     <variable> to appear more than once in the list of variables being
     bound.

     _Semantics:_ The <init>s are evaluated in the current environment
     (in some unspecified order), the <variable>s are bound to fresh
     locations holding the results, the <body> is evaluated in the
     extended environment, and the value(s) of the last expression of
     <body> is(are) returned.  Each binding of a <variable> has <body>
     as its region.

     (let ((x 2) (y 3))
       (* x y))                             ==>  6

     (let ((x 2) (y 3))
       (let ((x 7)
             (z (+ x y)))
         (* z x)))                          ==>  35

     See also named `let', section Iteration.

 - library syntax: let* <bindings> <body>
     _Syntax:_ <Bindings> should have the form

     ((<variable1> <init1>) ...,),

     and <body> should be a sequence of one or more expressions.

     _Semantics:_ `Let*' is similar to `let', but the bindings are
     performed sequentially from left to right, and the region of a
     binding indicated by `(<variable> <init>)' is that part of the
     `let*' expression to the right of the binding.  Thus the second
     binding is done in an environment in which the first binding is
     visible, and so on.

     (let ((x 2) (y 3))
       (let* ((x 7)
              (z (+ x y)))
         (* z x)))                          ==>  70

 - library syntax: letrec <bindings> <body>
     _Syntax:_ <Bindings> should have the form

     ((<variable1> <init1>) ...,),

     and <body> should be a sequence of one or more expressions. It is
     an error for a <variable> to appear more than once in the list of
     variables being bound.

     _Semantics:_ The <variable>s are bound to fresh locations holding
     undefined values, the <init>s are evaluated in the resulting
     environment (in some unspecified order), each <variable> is
     assigned to the result of the corresponding <init>, the <body> is
     evaluated in the resulting environment, and the value(s) of the
     last expression in <body> is(are) returned.  Each binding of a
     <variable> has the entire `letrec' expression as its region,
     making it possible to define mutually recursive procedures.

     (letrec ((even?
               (lambda (n)
                 (if (zero? n)
                     #t
                     (odd? (- n 1)))))
              (odd?
               (lambda (n)
                 (if (zero? n)
                     #f
                     (even? (- n 1))))))
       (even? 88))
                                            ==>  #t

     One restriction on `letrec' is very important: it must be possible
     to evaluate each <init> without assigning or referring to the
     value of any <variable>.  If this restriction is violated, then it
     is an error.  The restriction is necessary because Scheme passes
     arguments by value rather than by name.  In the most common uses
     of `letrec', all the <init>s are lambda expressions and the
     restriction is satisfied automatically.

Sequencing
----------

 - library syntax: begin <expression1> <expression2> ...,
     The <expression>s are evaluated sequentially from left to right,
     and the value(s) of the last <expression> is(are) returned.  This
     expression type is used to sequence side effects such as input and
     output.

     (define x 0)

     (begin (set! x 5)
            (+ x 1))                        ==>  6

     (begin (display "4 plus 1 equals ")
            (display (+ 4 1)))              ==>  _unspecified_
               _and prints_  4 plus 1 equals 5

Iteration
---------

 - library syntax: do ((<variable1> <init1> <step1>) ...) (<test>
          <expression> ...) <command> ...
     `Do' is an iteration construct.  It specifies a set of variables to
     be bound, how they are to be initialized at the start, and how
     they are to be updated on each iteration.  When a termination
     condition is met, the loop exits after evaluating the
     <expression>s.

     `Do' expressions are evaluated as follows: The <init> expressions
     are evaluated (in some unspecified order), the <variable>s are
     bound to fresh locations, the results of the <init> expressions
     are stored in the bindings of the <variable>s, and then the
     iteration phase begins.

     Each iteration begins by evaluating <test>; if the result is false
     (see section Booleans), then the <command> expressions are
     evaluated in order for effect, the <step> expressions are
     evaluated in some unspecified order, the <variable>s are bound to
     fresh locations, the results of the <step>s are stored in the
     bindings of the <variable>s, and the next iteration begins.

     If <test> evaluates to a true value, then the <expression>s are
     evaluated from left to right and the value(s) of the last
     <expression> is(are) returned.  If no <expression>s are present,
     then the value of the `do' expression is unspecified.

     The region of the binding of a <variable> consists of the entire
     `do' expression except for the <init>s.  It is an error for a
     <variable> to appear more than once in the list of `do' variables.

     A <step> may be omitted, in which case the effect is the same as
     if `(<variable> <init> <variable>)' had been written instead of
     `(<variable> <init>)'.

     (do ((vec (make-vector 5))
          (i 0 (+ i 1)))
         ((= i 5) vec)
       (vector-set! vec i i))               ==>  #(0 1 2 3 4)

     (let ((x '(1 3 5 7 9)))
       (do ((x x (cdr x))
            (sum 0 (+ sum (car x))))
           ((null? x) sum)))                ==>  25

 - library syntax: let <variable> <bindings> <body>
     "Named `let'" is a variant on the syntax of `let' which provides a
     more general looping construct than `do' and may also be used to
     express recursions.  It has the same syntax and semantics as
     ordinary `let' except that <variable> is bound within <body> to a
     procedure whose formal arguments are the bound variables and whose
     body is <body>.  Thus the execution of <body> may be repeated by
     invoking the procedure named by <variable>.

     (let loop ((numbers '(3 -2 1 6 -5))
                (nonneg '())
                (neg '()))
       (cond ((null? numbers) (list nonneg neg))
             ((>= (car numbers) 0)
              (loop (cdr numbers)
                    (cons (car numbers) nonneg)
                    neg))
             ((< (car numbers) 0)
              (loop (cdr numbers)
                    nonneg
                    (cons (car numbers) neg)))))
               ==>  ((6 1 3) (-5 -2))

Delayed evaluation
------------------

 - library syntax: delay <expression>
     The `delay' construct is used together with the procedure `force'
     to implement "lazy evaluation" or "call by need".  (delay
     <expression>) returns an object called a "promise" which at some
     point in the future may be asked (by the `force' procedure)  to
     evaluate <expression>, and deliver the resulting value.  The
     effect of <expression> returning multiple values is unspecified.

     See the description of `force' (section Control features)
     for a more complete description of `delay'.

Quasiquotation
--------------

 - syntax: quasiquote <qq template>
 - syntax: `<qq template>
     "Backquote" or "quasiquote" expressions are useful for
     constructing a list or vector structure when most but not all of
     the desired structure is known in advance.  If no commas appear
     within the <qq template>, the result of evaluating `<qq template>
     is equivalent to the result of evaluating '<qq template>.  If a
     comma appears within the <qq template>, however, the expression
     following the comma is evaluated ("unquoted") and its result is
     inserted into the structure instead of the comma and the
     expression.  If a comma appears followed immediately by an at-sign
     (@), then the following expression must evaluate to a list; the
     opening and closing parentheses of the list are then "stripped
     away" and the elements of the list are inserted in place of the
     comma at-sign expression sequence.  A comma at-sign should only
     appear within a list or vector <qq template>.

     `(list ,(+ 1 2) 4)                     ==>  (list 3 4)
     (let ((name 'a)) `(list ,name ',name))
               ==>  (list a (quote a))
     `(a ,(+ 1 2) ,@(map abs '(4 -5 6)) b)
               ==>  (a 3 4 5 6 b)
     `((`foo' ,(- 10 3)) ,@(cdr '(c)) . ,(car '(cons)))
               ==>  ((foo 7) . cons)
     `#(10 5 ,(sqrt 4) ,@(map sqrt '(16 9)) 8)
               ==>  #(10 5 2 4 3 8)

     Quasiquote forms may be nested.  Substitutions are made only for
     unquoted components appearing at the same nesting level as the
     outermost backquote.  The nesting level increases by one inside
     each successive quasiquotation, and decreases by one inside each
     unquotation.

     `(a `(b ,(+ 1 2) ,(foo ,(+ 1 3) d) e) f)
               ==>  (a `(b ,(+ 1 2) ,(foo 4 d) e) f)
     (let ((name1 'x)
           (name2 'y))
       `(a `(b ,,name1 ,',name2 d) e))
               ==>  (a `(b ,x ,'y d) e)

     The two notations  `<qq template> and (quasiquote <qq template>)
     are identical in all respects.   `,<expression>' is identical to
     `(unquote <expression>)',  and  `,@<expression>' is identical to
     `(unquote-splicing <expression>)'.  The external syntax generated
     by `write' for two-element lists whose car is one of these symbols
     may vary between implementations.

     (quasiquote (list (unquote (+ 1 2)) 4))
               ==>  (list 3 4)
     '(quasiquote (list (unquote (+ 1 2)) 4))
               ==>  `(list ,(+ 1 2) 4)
          __i.e., (quasiquote (list (unquote (+ 1 2)) 4))

     Unpredictable behavior can result if any of the symbols
     `quasiquote', `unquote', or `unquote-splicing' appear in positions
     within a <qq template> otherwise than as described above.

Macros
======

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 <datum>s, 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.

The macro definition facility consists of two 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, and

   * a pattern language for specifying macro transformers.

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 [Kohlbecker86],
[ hygienic], [Bawden88], [macrosthatwork], [syntacticabstraction]:

   * 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.
     Note that a `define' at top level may or may not introduce a
     binding; see section Definitions.

   * 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' and `letrec-syntax' are analogous to `let' and `letrec',
but they bind syntactic keywords to macro transformers instead of
binding variables to locations that contain values.  Syntactic keywords
may also be bound at top level; see section Syntax definitions.

 - syntax: let-syntax <bindings> <body>
     _Syntax:_ <Bindings> should have the form

     ((<keyword> <transformer spec>) ...,)

     Each <keyword> is an identifier, each <transformer spec> is an
     instance of `syntax-rules', and <body> should be 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.

     _Semantics:_ The <body> is expanded in the syntactic environment
     obtained by extending the syntactic environment of the
     `let-syntax' expression with macros whose keywords are the
     <keyword>s, bound to the specified transformers.  Each binding of
     a <keyword> has <body> 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

 - syntax: letrec-syntax <bindings> <body>
     _Syntax:_ Same as for `let-syntax'.

     _Semantics:_  The <body> is expanded in the syntactic environment
     obtained by extending the syntactic environment of the
     `letrec-syntax' expression with macros whose keywords are the
     <keyword>s, bound to the specified transformers.  Each binding of
     a <keyword> has the <bindings> as well as the <body> 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

Pattern language
----------------

A <transformer spec> has the following form:

 - : syntax-rules <literals> <syntax rule> ...,
     _Syntax:_ <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>)
     #(<pattern> ...)
     #(<pattern> ... <pattern> <ellipsis>)

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

     (<element> ...)
     (<element> <element> ... . <template>)
     #(<element> ...)

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

     _Semantics:_ 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 rule>s, 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.

          _Rationale:_ The scope of the keyword is determined by the
          expression or syntax definition that binds it to the
          associated macro transformer.  If the keyword were a pattern
          variable or literal identifier, then the template that
          follows the pattern would be within its scope regardless of
          whether the keyword were bound by `let-syntax' or by
          `letrec-syntax'.

     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 vector of the form `#(P_1 ... P_n)' and F is a vector
          of n forms that match P_1 through P_n; or

        * P is of the form `#(P_1 ... P_n P_n+1 <ellipsis>)' where
          <ellipsis> is the identifier `...' and F is a vector of n or
          more 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.

     As an example, if `let' and `cond' are defined as in section
     Derived expression type then they are hygienic (as required) and
     the following is not an error.

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

Program structure
*****************

Programs
========

A Scheme program consists of a sequence of expressions, definitions,
and syntax definitions.  Expressions are described in chapter
Expressions; definitions and syntax definitions are the subject of
the rest of the present chapter.

Programs are typically stored in files or entered interactively to a
running Scheme system, although other paradigms are possible; questions
of user interface lie outside the scope of this report.  (Indeed,
Scheme would still be useful as a notation for expressing computational
methods even in the absence of a mechanical implementation.)

Definitions and syntax definitions occurring at the top level of a
program can be interpreted declaratively.  They cause bindings to be
created in the top level environment or modify the value of existing
top-level bindings.  Expressions occurring at the top level of a
program are interpreted imperatively; they are executed in order when
the program is invoked or loaded, and typically perform some kind of
initialization.

At the top level of a program (begin <form1> ...,) is equivalent to the
sequence of expressions, definitions, and syntax definitions that form
the body of the `begin'.

Definitions
===========

Definitions are valid in some, but not all, contexts where expressions
are allowed.  They are valid only at the top level of a <program> and
at the beginning of a <body>.

A definition should have one of the following forms:

   * (define <variable> <expression>)

   * (define (<variable> <formals>) <body>)

     <Formals> should be either a sequence of zero or more variables,
     or a sequence of one or more variables followed by a
     space-delimited period and another variable (as in a lambda
     expression).  This form is equivalent to

          (define <variable>
            (lambda (<formals>) <body>)).

   * (define (<variable> . <formal>) <body>)

     <Formal> should be a single variable.  This form is equivalent to

          (define <variable>
            (lambda <formal> <body>)).

Top level definitions
---------------------

At the top level of a program, a definition

     (define <variable> <expression>)

has essentially the same effect as the assignment expression

     (set! <variable> <expression>)

if <variable> is bound.  If <variable> is not bound, however, then the
definition will bind <variable> to a new location before performing the
assignment, whereas it would be an error to perform a `set!' on an
unbound variable.

     (define add3
       (lambda (x) (+ x 3)))
     (add3 3)                               ==>  6
     (define first car)
     (first '(1 2))                         ==>  1

Some implementations of Scheme use an initial environment in which all
possible variables are bound to locations, most of which contain
undefined values.  Top level definitions in such an implementation are
truly equivalent to assignments.

Internal definitions
--------------------

Definitions may occur at the beginning of a <body> (that is, the body
of a `lambda', `let', `let*', `letrec', `let-syntax', or `letrec-syntax'
expression or that of a definition of an appropriate form).  Such
definitions are known as _internal definitions_  as opposed to the top
level definitions described above.  The variable defined by an internal
definition is local to the <body>.  That is, <variable> is bound rather
than assigned, and the region of the binding is the entire <body>.  For
example,

     (let ((x 5))
       (define foo (lambda (y) (bar x y)))
       (define bar (lambda (a b) (+ (* a b) a)))
       (foo (+ x 3)))                       ==>  45

A <body> containing internal definitions can always be converted into a
completely equivalent `letrec' expression.  For example, the `let'
expression in the above example is equivalent to

     (let ((x 5))
       (letrec ((foo (lambda (y) (bar x y)))
                (bar (lambda (a b) (+ (* a b) a))))
         (foo (+ x 3))))

Just as for the equivalent `letrec' expression, it must be possible to
evaluate each <expression> of every internal definition in a <body>
without assigning or referring to the value of any <variable> being
defined.

Wherever an internal definition may occur (begin <definition1> ...,) is
equivalent to the sequence of definitions that form the body of the
`begin'.

Syntax definitions
==================

Syntax definitions are valid only at the top level of a <program>.

They have the following form:

(define-syntax <keyword> <transformer spec>)

<Keyword> is an identifier, and the <transformer spec> should be an
instance of `syntax-rules'.  The top-level syntactic environment is
extended by binding the <keyword> to the specified transformer.

There is no `define-syntax' analogue of internal definitions.

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

Standard procedures
*******************

This chapter describes Scheme's built-in procedures.  The initial (or
"top level") Scheme environment starts out with a number of variables
bound to locations containing useful values, most of which are primitive
procedures that manipulate data.  For example, the variable `abs' is
bound to (a location initially containing) a procedure of one argument
that computes the absolute value of a number, and the variable `+' is
bound to a procedure that computes sums.  Built-in procedures that can
easily be written in terms of other built-in procedures are identified
as "library procedures".

A program may use a top-level definition to bind any variable.  It may
subsequently alter any such binding by an assignment (see
Assignments).  These operations do not modify the behavior of
Scheme's built-in procedures.  Altering any top-level binding that has
not been introduced by a definition has an unspecified effect on the
behavior of the built-in procedures.

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.  This relation is left slightly
     open to interpretation, but the following partial specification of
     `eqv?' holds for all implementations of Scheme.

     The `eqv?' procedure returns #t if:

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

        * OBJ1 and OBJ2 are both symbols and

          (string=? (symbol->string obj1)
                    (symbol->string obj2))
                                            ==>  #t

               _Note:_ This assumes that neither OBJ1 nor OBJ2 is an
               "uninterned symbol" as alluded to in section
               Symbols.  This report does not presume to specify the
               behavior of `eqv?' on implementation-dependent
               extensions.

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

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

        * both OBJ1 and OBJ2 are the empty list.

        * OBJ1 and OBJ2 are pairs, vectors, or strings that denote the
          same locations in the store (section Storage model).

        * OBJ1 and OBJ2 are procedures whose location tags are equal
          (section Procedures).

     The `eqv?' procedure returns #f if:

        * OBJ1 and OBJ2 are of different types (section
          Disjointness of 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 pairs, vectors, or strings that denote
          distinct locations.

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

     (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

     Since it is an error to modify constant objects (those returned by
     literal expressions), implementations are permitted, though not
     required, to share structure between constants where appropriate.
     Thus the value of `eqv?' on constants is sometimes
     implementation-dependent.

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

          _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, procedures, 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?'.

 - library procedure: equal? obj1 obj2
     `Equal?' recursively compares the contents of pairs, vectors, and
     strings, applying `eqv?' on other objects such as numbers and
     symbols.  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
=======

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 [Pitman83] 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.

Numerical types
---------------

Mathematically, numbers may be arranged into a tower of subtypes in
which each level is a subset of the level above it:

         number
          complex
          real
          rational
          integer

For example, 3 is an integer.  Therefore 3 is also a rational, a real,
and a complex.  The same is true of the Scheme numbers that model 3.
For Scheme numbers, these types are defined by the predicates
`number?', `complex?', `real?', `rational?', and `integer?'.

There is no simple relationship between a number's type and its
representation inside a computer.  Although most implementations of
Scheme will offer at least two different representations of 3, these
different representations denote the same integer.

Scheme's numerical operations treat numbers as abstract data, as
independent of their representation as possible.  Although an
implementation of Scheme may use fixnum, flonum, and perhaps other
representations for numbers, this should not be apparent to a casual
programmer writing simple programs.

It is necessary, however, to distinguish between numbers that are
represented exactly and those that may not be.  For example, indexes
into data structures must be known exactly, as must some polynomial
coefficients in a symbolic algebra system.  On the other hand, the
results of measurements are inherently inexact, and irrational numbers
may be approximated by rational and therefore inexact approximations.
In order to catch uses of inexact numbers where exact numbers are
required, Scheme explicitly distinguishes exact from inexact numbers.
This distinction is orthogonal to the dimension of type.

Exactness
---------

Scheme numbers are either exact or inexact.  A number is exact if it
was written as an exact constant or was derived from exact numbers
using only exact operations.  A number is inexact if it was written as
an inexact constant, if it was derived using inexact ingredients, or if
it was derived using inexact operations. Thus inexactness is a
contagious property of a number.

If two implementations produce exact results for a computation that did
not involve inexact intermediate results, the two ultimate results will
be mathematically equivalent.  This is generally not true of
computations involving inexact numbers since approximate methods such
as floating point arithmetic may be used, but it is the duty of each
implementation to make the result as close as practical to the
mathematically ideal result.

Rational operations such as `+' should always produce exact results
when given exact arguments.  If the operation is unable to produce an
exact result, then it may either report the violation of an
implementation restriction or it may silently coerce its result to an
inexact value.  See section Implementation restrictions.

With the exception of `inexact->exact', the operations described in
this section must generally return inexact results when given any
inexact arguments.  An operation may, however, return an exact result
if it can prove that the value of the result is unaffected by the
inexactness of its arguments.  For example, multiplication of any
number by an exact zero may produce an exact zero result, even if the
other argument is inexact.