2 November 1991

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.

 - essential 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 of the last expression of
     <body> is 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.

 - 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

 - essential 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 of the last
     expression in <body> is 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
----------

 - essential syntax: begin <EXPRESSION1> <EXPRESSION2> ...,
     The <expression>s are evaluated sequentially from left to right,
     and the value of the last <expression> is 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

          *Note:* [SICP] uses the keyword `sequence' instead of `begin'.

Iteration
---------

 - 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 with a specified result value.

     `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 of the last
     <expression> is returned as the value of the `do' expression.  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

 - syntax: let <variable> <bindings> <body>
     Some implementations of Scheme permit a variant on the syntax of
     `let' called "named `let'" which provides a more general looping
     construct than `do', and may also be used to express recursions.

     Named `let' 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
------------------

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

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

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

 - essential syntax: quasiquote <template>
 - essential syntax: `<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 <template>, the result of evaluating `<template> is
     equivalent to the result of evaluating '<template>.  If a comma
     appears within the <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.

     `(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 notations  `<template> and (quasiquote <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 <template> otherwise than as described above.

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

Programs
========

A Scheme program consists of a sequence of expressions and definitions.
Expressions are described in chapter Expressions; 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 occurring at the top level of a program can be interpreted
declaratively.  They cause bindings to be created in the top level
environment.  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.

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,
in some implementations, at the beginning of a <body>.

A definition should have one of the following forms:

   * (define <variable> <expression>)

     This syntax is essential.

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

     This syntax is not essential.  <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>)

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

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

   * (begin <definition1> ...,)

     This syntax is essential.  This form is equivalent to the set of
     definitions that form the body of the `begin'.

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

All Scheme implementations must support top level definitions.

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

Some implementations of Scheme permit definitions to occur at the
beginning of a <body> (that is, the body of a `lambda', `let', `let*',
`letrec', or `define' expression).  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.

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.

Booleans
========

The standard boolean objects for true and false are written as #t and
#f.  What really matters, though, are the objects that the Scheme
conditional expressions (`if', `cond', `and', `or', `do') treat as true
or false.  The phrase "a true value" (or sometimes just "true") means
any object treated as true by the conditional expressions, and the
phrase "a false value" (or "false") means any object treated as false
by the conditional expressions.

Of all the standard Scheme values, only #f counts as false in
conditional expressions.  Except for #f, all standard Scheme values,
including #t, pairs, the empty list, symbols, numbers, strings,
vectors, and procedures, count as true.

     *Note:* In some implementations the empty list counts as false,
     contrary to the above.  Nonetheless a few examples in this report
     assume that the empty list counts as true, as in [IEEEScheme].

     *Note:* Programmers accustomed to other dialects of Lisp should be
     aware that Scheme distinguishes both #f and the empty list from
     the symbol `nil'.

Boolean constants evaluate to themselves, so they don't need to be
quoted in programs.

     #t                                     ==>  #t
     #f                                     ==>  #f
     '#f                                    ==>  #f

 - essential procedure: not OBJ
     `Not' returns #t if OBJ is false, and returns #f otherwise.

     (not #t)                               ==>  #f
     (not 3)                                ==>  #f
     (not (list 3))                         ==>  #f
     (not #f)                               ==>  #t
     (not '())                              ==>  #f
     (not (list))                           ==>  #f
     (not 'nil)                             ==>  #f

 - essential procedure: boolean? OBJ
     `Boolean?' returns #t if OBJ is either #t or #f and returns #f
     otherwise.

     (boolean? #f)                          ==>  #t
     (boolean? 0)                           ==>  #f
     (boolean? '())                         ==>  #f

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?'.

 - essential 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 lambda expressions.).

     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 a different value 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.

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

 - essential 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*

Pairs and lists
===============

A "pair" (sometimes called a "dotted pair") is a record structure with
two fields called the car and cdr fields (for historical reasons).
Pairs are created by the procedure `cons'.  The car and cdr fields are
accessed by the procedures `car' and `cdr'.  The car and cdr fields are
assigned by the procedures `set-car!' and `set-cdr!'.

Pairs are used primarily to represent lists.  A list can be defined
recursively as either the empty list or a pair whose cdr is a list.
More precisely, the set of lists is defined as the smallest set X such
that

   * The empty list is in X.

   * If LIST is in X, then any pair whose cdr field contains LIST is
     also in X.

The objects in the car fields of successive pairs of a list are the
elements of the list.  For example, a two-element list is a pair whose
car is the first element and whose cdr is a pair whose car is the
second element and whose cdr is the empty list.  The length of a list
is the number of elements, which is the same as the number of pairs.

The empty list is a special object of its own type (it is not a pair);
it has no elements and its length is zero.

     *Note:* The above definitions imply that all lists have finite
     length and are terminated by the empty list.

The most general notation (external representation) for Scheme pairs is
the "dotted" notation `(C1 . C2)' where C1 is the value of the car
field and C2 is the value of the cdr field.  For example `(4 . 5)' is a
pair whose car is 4 and whose cdr is 5.  Note that `(4 . 5)' is the
external representation of a pair, not an expression that evaluates to
a pair.

A more streamlined notation can be used for lists: the elements of the
list are simply enclosed in parentheses and separated by spaces.  The
empty list is written () .  For example,

     (a b c d e)

and

     (a . (b . (c . (d . (e . ())))))

are equivalent notations for a list of symbols.

A chain of pairs not ending in the empty list is called an "improper
list".  Note that an improper list is not a list.  The list and dotted
notations can be combined to represent improper lists:

     (a b c . d)

is equivalent to

     (a . (b . (c . d)))

Whether a given pair is a list depends upon what is stored in the cdr
field.  When the `set-cdr!' procedure is used, an object can be a list
one moment and not the next:

     (define x (list 'a 'b 'c))
     (define y x)
     y                                      ==>  (a b c)
     (list? y)                              ==>  #t
     (set-cdr! x 4)                         ==>  *unspecified*
     x                                      ==>  (a . 4)
     (eqv? x y)                             ==>  #t
     y                                      ==>  (a . 4)
     (list? y)                              ==>  #f
     (set-cdr! x x)                         ==>  *unspecified*
     (list? x)                              ==>  #f

Within literal expressions and representations of objects read by the
`read' procedure, the forms '<datum>, `<datum>, ,<datum>, and ,@<datum>
denote two-element lists whose first elements are the symbols `quote',
`quasiquote', `unquote', and `unquote-splicing', respectively.  The
second element in each case is <datum>.  This convention is supported
so that arbitrary Scheme programs may be represented as lists.   That
is, according to Scheme's grammar, every <expression> is also a <datum>
(see section External representation.).  Among other things,
this permits the use of the `read' procedure to parse Scheme programs.
See section External representations.

 - essential procedure: pair? OBJ
     `Pair?' returns #t if OBJ is a pair, and otherwise returns #f.

     (pair? '(a . b))                       ==>  #t
     (pair? '(a b c))                       ==>  #t
     (pair? '())                            ==>  #f
     (pair? '#(a b))                        ==>  #f

 - essential procedure: cons OBJ1 OBJ2
     Returns a newly allocated pair whose car is OBJ1 and whose cdr is
     OBJ2.  The pair is guaranteed to be different (in the sense of
     `eqv?') from every existing object.

     (cons 'a '())                          ==>  (a)
     (cons '(a) '(b c d))                   ==>  ((a) b c d)
     (cons "a" '(b c))                      ==>  ("a" b c)
     (cons 'a 3)                            ==>  (a . 3)
     (cons '(a b) 'c)                       ==>  ((a b) . c)

 - essential procedure: car PAIR
     Returns the contents of the car field of PAIR.  Note that it is an
     error to take the car of the empty list.

     (car '(a b c))                         ==>  a
     (car '((a) b c d))                     ==>  (a)
     (car '(1 . 2))                         ==>  1
     (car '())                              ==>  *error*

 - essential procedure: cdr PAIR
     Returns the contents of the cdr field of PAIR.  Note that it is an
     error to take the cdr of the empty list.

     (cdr '((a) b c d))                     ==>  (b c d)
     (cdr '(1 . 2))                         ==>  2
     (cdr '())                              ==>  *error*

 - essential procedure: set-car! PAIR OBJ
     Stores OBJ in the car field of PAIR.  The value returned by
     `set-car!' is unspecified.

     (define (f) (list 'not-a-constant-list))
     (define (g) '(constant-list))
     (set-car! (f) 3)                       ==>  *unspecified*
     (set-car! (g) 3)                       ==>  *error*

 - essential procedure: set-cdr! PAIR OBJ
     Stores OBJ in the cdr field of PAIR.  The value returned by
     `set-cdr!' is unspecified.

 - essential procedure: caar PAIR
 - essential procedure: cadr PAIR
 -  :          ...
 - essential procedure: cdddar PAIR
 - essential procedure: cddddr PAIR
     These procedures are compositions of `car' and `cdr', where for
     example `caddr' could be defined by

     (define caddr (lambda (x) (car (cdr (cdr x))))).

     Arbitrary compositions, up to four deep, are provided.  There are
     twenty-eight of these procedures in all.

 - essential procedure: null? OBJ
     Returns #t if OBJ is the empty list, otherwise returns #f.

 - essential procedure: list? OBJ
     Returns #t if OBJ is a list, otherwise returns #f.  By definition,
     all lists have finite length and are terminated by the empty list.

             (list? '(a b c))               ==>  #t
             (list? '())                    ==>  #t
             (list? '(a . b))               ==>  #f
             (let ((x (list 'a)))
               (set-cdr! x x)
               (list? x))                   ==>  #f

 - essential procedure: list OBJ ...,
     Returns a newly allocated list of its arguments.

     (list 'a (+ 3 4) 'c)                   ==>  (a 7 c)
     (list)                                 ==>  ()

 - essential procedure: length LIST
     Returns the length of LIST.

     (length '(a b c))                      ==>  3
     (length '(a (b) (c d e)))              ==>  3
     (length '())                           ==>  0

 - essential procedure: append LIST ...,
     Returns a list consisting of the elements of the first LIST
     followed by the elements of the other LISTs.

     (append '(x) '(y))                     ==>  (x y)
     (append '(a) '(b c d))                 ==>  (a b c d)
     (append '(a (b)) '((c)))               ==>  (a (b) (c))

     The resulting list is always newly allocated, except that it shares
     structure with the last LIST argument.  The last argument may
     actually be any object; an improper list results if the last
     argument is not a proper list.

     (append '(a b) '(c . d))               ==>  (a b c . d)
     (append '() 'a)                        ==>  a

 - essential procedure: reverse LIST
     Returns a newly allocated list consisting of the elements of LIST
     in reverse order.

     (reverse '(a b c))                     ==>  (c b a)
     (reverse '(a (b c) d (e (f))))
               ==>  ((e (f)) d (b c) a)

 - procedure: list-tail LIST K
     Returns the sublist of LIST obtained by omitting the first K
     elements.  `List-tail' could be defined by

     (define list-tail
       (lambda (x k)
         (if (zero? k)
             x
             (list-tail (cdr x) (- k 1)))))

 - essential procedure: list-ref LIST K
     Returns the Kth element of LIST.  (This is the same as the car of
     (list-tail LIST K).)

     (list-ref '(a b c d) 2)                 ==>  c
     (list-ref '(a b c d)
               (inexact->exact (round 1.8)))
               ==>  c

 - essential procedure: memq OBJ LIST
 - essential procedure: memv OBJ LIST
 - essential procedure: member OBJ LIST
     These procedures return the first sublist of LIST whose car is
     OBJ, where the sublists of LIST are the non-empty lists returned
     by (list-tail LIST K) for K less than the length of LIST.  If OBJ
     does not occur in LIST, then #f (not the empty list) is returned.
     `Memq' uses `eq?' to compare OBJ with the elements of LIST, while
     `memv' uses `eqv?' and `member' uses `equal?'.

     (memq 'a '(a b c))                     ==>  (a b c)
     (memq 'b '(a b c))                     ==>  (b c)
     (memq 'a '(b c d))                     ==>  #f
     (memq (list 'a) '(b (a) c))            ==>  #f
     (member (list 'a)
             '(b (a) c))                    ==>  ((a) c)
     (memq 101 '(100 101 102))              ==>  *unspecified*
     (memv 101 '(100 101 102))              ==>  (101 102)

 - essential procedure: assq OBJ ALIST
 - essential procedure: assv OBJ ALIST
 - essential procedure: assoc OBJ ALIST
     ALIST (for "association list") must be a list of pairs.  These
     procedures find the first pair in ALIST whose car field is OBJ,
     and returns that pair.  If no pair in ALIST has OBJ as its car,
     then #f (not the empty list) is returned.  `Assq' uses `eq?' to
     compare OBJ with the car fields of the pairs in ALIST, while
     `assv' uses `eqv?' and `assoc' uses `equal?'.

     (define e '((a 1) (b 2) (c 3)))
     (assq 'a e)                            ==>  (a 1)
     (assq 'b e)                            ==>  (b 2)
     (assq 'd e)                            ==>  #f
     (assq (list 'a) '(((a)) ((b)) ((c))))
                                            ==>  #f
     (assoc (list 'a) '(((a)) ((b)) ((c))))
                                            ==>  ((a))
     (assq 5 '((2 3) (5 7) (11 13)))
                                            ==>  *unspecified*
     (assv 5 '((2 3) (5 7) (11 13)))
                                            ==>  (5 7)

          *Rationale:* Although they are ordinarily used as predicates,
          `memq', `memv', `member', `assq', `assv', and `assoc' do not
          have question marks in their names because they return useful
          values rather than just #t or #f.

Symbols
=======

Symbols are objects whose usefulness rests on the fact that two symbols
are identical (in the sense of `eqv?') if and only if their names are
spelled the same way.  This is exactly the property needed to represent
identifiers in programs, and so most implementations of Scheme use them
internally for that purpose.  Symbols are useful for many other
applications; for instance, they may be used the way enumerated values
are used in Pascal.

The rules for writing a symbol are exactly the same as the rules for
writing an identifier; see sections Identifiers and
Lexical structure.

It is guaranteed that any symbol that has been returned as part of a
literal expression, or read using the `read' procedure, and
subsequently written out using the `write' procedure, will read back in
as the identical symbol (in the sense of `eqv?').  The `string->symbol'
procedure, however, can create symbols for which this write/read
invariance may not hold because their names contain special characters
or letters in the non-standard case.

     *Note:* Some implementations of Scheme have a feature known as
     "slashification" in order to guarantee write/read invariance for
     all symbols, but historically the most important use of this
     feature has been to compensate for the lack of a string data type.

     Some implementations also have "uninterned symbols", which defeat
     write/read invariance even in implementations with slashification,
     and also generate exceptions to the rule that two symbols are the
     same if and only if their names are spelled the same.

 - essential procedure: symbol? OBJ
     Returns #t if OBJ is a symbol, otherwise returns #f.

     (symbol? 'foo)                         ==>  #t
     (symbol? (car '(a b)))                 ==>  #t
     (symbol? "bar")                        ==>  #f
     (symbol? 'nil)                         ==>  #t
     (symbol? '())                          ==>  #f
     (symbol? #f)                           ==>  #f

 - essential procedure: symbol->string SYMBOL
     Returns the name of SYMBOL as a string.  If the symbol was part of
     an object returned as the value of a literal expression (section
     Literal expressions.) or by a call to the `read' procedure,
     and its name contains alphabetic characters, then the string
     returned will contain characters in the implementation's preferred
     standard case--some implementations will prefer upper case, others
     lower case.  If the symbol was returned by `string->symbol', the
     case of characters in the string returned will be the same as the
     case in the string that was passed to `string->symbol'.  It is an
     error to apply mutation procedures like `string-set!' to strings
     returned by this procedure.

     The following examples assume that the implementation's standard
     case is lower case:

     (symbol->string 'flying-fish)
                                            ==>  "flying-fish"
     (symbol->string 'Martin)               ==>  "martin"
     (symbol->string
        (string->symbol "Malvina"))
                                            ==>  "Malvina"

 - essential procedure: string->symbol STRING
     Returns the symbol whose name is STRING.  This procedure can
     create symbols with names containing special characters or letters
     in the non-standard case, but it is usually a bad idea to create
     such symbols because in some implementations of Scheme they cannot
     be read as themselves.  See `symbol->string'.

     The following examples assume that the implementation's standard
     case is lower case:

     (eq? 'mISSISSIppi 'mississippi)
               ==>  #t
     (string->symbol "mISSISSIppi")
               ==>
       the symbol with name "mISSISSIppi"
     (eq? 'bitBlt (string->symbol "bitBlt"))
               ==>  #f
     (eq? 'JollyWog
          (string->symbol
            (symbol->string 'JollyWog)))
               ==>  #t
     (string=? "K. Harper, M.D."
               (symbol->string
                 (string->symbol "K. Harper, M.D.")))
               ==>  #t

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.