   This file documents the MIT Scheme system.

   Copyright (C) 1988-2002 Massachusetts Institute of Technology

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

Miscellaneous List Operations
=============================

 - procedure: circular-list object ...
 - procedure: make-circular-list k [element]
     These procedures are like `list' and `make-list', respectively,
     except that the returned lists are circular.  `circular-list'
     could have been defined like this:

          (define (circular-list . objects)
            (append! objects objects))

 - procedure: reverse list
     Returns a newly allocated list consisting of the top-level
     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: reverse! list
     Returns a list consisting of the top-level elements of LIST in
     reverse order.  `reverse!' is like `reverse', except that it
     destructively modifies LIST.  Because the result may not be `eqv?'
     to LIST, it is desirable to do something like `(set! x (reverse!
     x))'.

 - procedure: sort sequence procedure
 - procedure: merge-sort sequence procedure
 - procedure: quick-sort sequence procedure
     SEQUENCE must be either a list or a vector.  PROCEDURE must be a
     procedure of two arguments that defines a "total ordering" on the
     elements of SEQUENCE.  In other words, if X and Y are two distinct
     elements of SEQUENCE, then it must be the case that

          (and (PROCEDURE X Y)
               (PROCEDURE Y X))
               =>  #f

     If SEQUENCE is a list (vector), `sort' returns a newly allocated
     list (vector) whose elements are those of SEQUENCE, except that
     they are rearranged to be sorted in the order defined by
     PROCEDURE.  So, for example, if the elements of SEQUENCE are
     numbers, and PROCEDURE is `<', then the resulting elements are
     sorted in monotonically nondecreasing order.  Likewise, if
     PROCEDURE is `>', the resulting elements are sorted in
     monotonically nonincreasing order.  To be precise, if X and Y are
     any two adjacent elements in the result, where X precedes Y, it is
     the case that

          (PROCEDURE Y X)
               =>  #f

     Two sorting algorithms are implemented: `merge-sort' and
     `quick-sort'.  The procedure `sort' is an alias for `merge-sort'.

     See also the definition of `sort!'.

Vectors
*******

   "Vectors" are heterogenous structures whose elements are indexed by
exact non-negative integers.  A vector typically occupies less space
than a list of the same length, and the average time required to access
a randomly chosen element is typically less for the vector than for the
list.

   The "length" of a vector is the number of elements that it contains.
This number is an exact non-negative integer that is fixed when the
vector is created.  The "valid indexes" of a vector are the exact
non-negative integers less than the length of the vector.  The first
element in a vector is indexed by zero, and the last element is indexed
by one less than the length of the vector.

   Vectors are written using the notation `#(OBJECT ...)'.  For
example, a vector of length 3 containing the number zero in element 0,
the list `(2 2 2 2)' in element 1, and the string `"Anna"' in element 2
can be written as

     #(0 (2 2 2 2) "Anna")

Note that this is the external representation of a vector, not an
expression evaluating to a vector.  Like list constants, vector
constants must be quoted:

     '#(0 (2 2 2 2) "Anna")          =>  #(0 (2 2 2 2) "Anna")

   A number of the vector procedures operate on subvectors.  A
"subvector" is a segment of a vector that is specified by two exact
non-negative integers, START and END.  START is the index of the first
element that is included in the subvector, and END is one greater than
the index of the last element that is included in the subvector.  Thus
if START and END are the same, they refer to a null subvector, and if
START is zero and END is the length of the vector, they refer to the
entire vector.  The "valid indexes" of a subvector are the exact
integers between START inclusive and END exclusive.

Construction of Vectors
=======================

 - procedure: make-vector k [object]
     Returns a newly allocated vector of K elements.  If OBJECT is
     specified, `make-vector' initializes each element of the vector to
     OBJECT.  Otherwise the initial elements of the result are
     unspecified.

 - procedure: vector object ...
     Returns a newly allocated vector whose elements are the given
     arguments.  `vector' is analogous to `list'.

          (vector 'a 'b 'c)                       =>  #(a b c)

 - procedure: vector-copy vector
     Returns a newly allocated vector that is a copy of VECTOR.

 - procedure: list->vector list
     Returns a newly allocated vector initialized to the elements of
     LIST.  The inverse of `list->vector' is `vector->list'.

          (list->vector '(dididit dah))           =>  #(dididit dah)

 - procedure: make-initialized-vector k initialization
     Similar to `make-vector', except that the elements of the result
     are determined by calling the procedure INITIALIZATION on the
     indices.  For example:

          (make-initialized-vector 5 (lambda (x) (* x x)))
               =>  #(0 1 4 9 16)

 - procedure: vector-grow vector k
     K must be greater than or equal to the length of VECTOR.  Returns
     a newly allocated vector of length K.  The first `(vector-length
     VECTOR)' elements of the result are initialized from the
     corresponding elements of VECTOR.  The remaining elements of the
     result are unspecified.

 - procedure: vector-map procedure vector
     PROCEDURE must be a procedure of one argument.  `vector-map'
     applies PROCEDURE element-wise to the elements of VECTOR and
     returns a newly allocated vector of the results, in order from
     left to right.  The dynamic order in which PROCEDURE is applied to
     the elements of VECTOR is unspecified.

          (vector-map cadr '#((a b) (d e) (g h)))     =>  #(b e h)
          (vector-map (lambda (n) (expt n n)) '#(1 2 3 4))
                                                      =>  #(1 4 27 256)
          (vector-map + '#(5 7 9))                    =>  #(5 7 9)

Selecting Vector Components
===========================

 - procedure: vector? object
     Returns `#t' if OBJECT is a vector; otherwise returns `#f'.

 - procedure: vector-length vector
     Returns the number of elements in VECTOR.

 - procedure: vector-ref vector k
     Returns the contents of element K of VECTOR.  K must be a valid
     index of VECTOR.

          (vector-ref '#(1 1 2 3 5 8 13 21) 5)    =>  8

 - procedure: vector-set! vector k object
     Stores OBJECT in element K of VECTOR and returns an unspecified
     value.  K must be a valid index of VECTOR.

          (let ((vec (vector 0 '(2 2 2 2) "Anna")))
            (vector-set! vec 1 '("Sue" "Sue"))
            vec)
               =>  #(0 ("Sue" "Sue") "Anna")

 - procedure: vector-first vector
 - procedure: vector-second vector
 - procedure: vector-third vector
 - procedure: vector-fourth vector
 - procedure: vector-fifth vector
 - procedure: vector-sixth vector
 - procedure: vector-seventh vector
 - procedure: vector-eighth vector
     These procedures access the first several elements of VECTOR in
     the obvious way.  It is an error if the implicit index of one of
     these procedurs is not a valid index of VECTOR.

 - procedure: vector-binary-search vector key<? unwrap-key key
     Searches VECTOR for an element with a key matching KEY, returning
     the element if one is found or `#f' if none.  The search operation
     takes time proportional to the logarithm of the length of VECTOR.
     UNWRAP-KEY must be a procedure that maps each element of VECTOR to
     a key.  KEY<? must be a procedure that implements a total ordering
     on the keys of the elements.

          (define (translate number)
            (vector-binary-search '#((1 . i)
                                     (2 . ii)
                                     (3 . iii)
                                     (6 . vi))
                                  < car number))
          (translate 2)  =>  (2 . ii)
          (translate 4)  =>  #F

Cutting Vectors
===============

 - procedure: subvector vector start end
     Returns a newly allocated vector that contains the elements of
     VECTOR between index START (inclusive) and END (exclusive).

 - procedure: vector-head vector end
     Equivalent to

          (subvector VECTOR 0 END)

 - procedure: vector-tail vector start
     Equivalent to

          (subvector VECTOR START (vector-length VECTOR))

Modifying Vectors
=================

 - procedure: vector-fill! vector object
 - procedure: subvector-fill! vector start end object
     Stores OBJECT in every element of the vector (subvector) and
     returns an unspecified value.

 - procedure: subvector-move-left! vector1 start1 end1 vector2 start2
 - procedure: subvector-move-right! vector1 start1 end1 vector2 start2
     Destructively copies the elements of VECTOR1, starting with index
     START1 (inclusive) and ending with END1 (exclusive), into VECTOR2
     starting at index START2 (inclusive).  VECTOR1, START1, and END1
     must specify a valid subvector, and START2 must be a valid index
     for VECTOR2.  The length of the source subvector must not exceed
     the length of VECTOR2 minus the index START2.

     The elements are copied as follows (note that this is only
     important when VECTOR1 and VECTOR2 are `eqv?'):

    `subvector-move-left!'
          The copy starts at the left end and moves toward the right
          (from smaller indices to larger).  Thus if VECTOR1 and
          VECTOR2 are the same, this procedure moves the elements
          toward the left inside the vector.

    `subvector-move-right!'
          The copy starts at the right end and moves toward the left
          (from larger indices to smaller).  Thus if VECTOR1 and
          VECTOR2 are the same, this procedure moves the elements
          toward the right inside the vector.

 - procedure: sort! vector procedure
 - procedure: merge-sort! vector procedure
 - procedure: quick-sort! vector procedure
     PROCEDURE must be a procedure of two arguments that defines a
     "total ordering" on the elements of VECTOR.  The elements of
     VECTOR are rearranged so that they are sorted in the order defined
     by PROCEDURE.  The elements are rearranged in place, that is,
     VECTOR is destructively modified so that its elements are in the
     new order.

     `sort!' returns VECTOR as its value.

     Two sorting algorithms are implemented: `merge-sort!' and
     `quick-sort!'.  The procedure `sort!' is an alias for
     `merge-sort!'.

     See also the definition of `sort'.

Bit Strings
***********

   A "bit string" is a sequence of bits.  Bit strings can be used to
represent sets or to manipulate binary data.  The elements of a bit
string are numbered from zero up to the number of bits in the string
less one, in _right to left order_, (the rightmost bit is numbered
zero).  When you convert from a bit string to an integer, the zero-th
bit is associated with the zero-th power of two, the first bit is
associated with the first power, and so on.

   Bit strings are encoded very densely in memory.  Each bit occupies
exactly one bit of storage, and the overhead for the entire bit string
is bounded by a small constant.  However, accessing a bit in a bit
string is slow compared to accessing an element of a vector or character
string.  If performance is of overriding concern, it is better to use
character strings to store sets of boolean values even though they
occupy more space.

   The "length" of a bit string is the number of bits that it contains.
This number is an exact non-negative integer that is fixed when the bit
string is created.  The "valid indexes" of a bit string are the exact
non-negative integers less than the length of the bit string.

   Bit strings may contain zero or more bits.  They are not limited by
the length of a machine word.  In the printed representation of a bit
string, the contents of the bit string are preceded by `#*'.  The
contents are printed starting with the most significant bit (highest
index).

   Note that the external representation of bit strings uses a bit
ordering that is the reverse of the representation for bit strings in
Common Lisp.  It is likely that MIT Scheme's representation will be
changed in the future, to be compatible with Common Lisp.  For the time
being this representation should be considered a convenience for viewing
bit strings rather than a means of entering them as data.

     #*11111
     #*1010
     #*00000000
     #*

   All of the bit-string procedures are MIT Scheme extensions.

Construction of Bit Strings
===========================

 - procedure: make-bit-string k initialization
     Returns a newly allocated bit string of length K.  If
     INITIALIZATION is `#f', the bit string is filled with 0 bits;
     otherwise, the bit string is filled with 1 bits.

          (make-bit-string 7 #f)                  =>  #*0000000

 - procedure: bit-string-allocate k
     Returns a newly allocated bit string of length K, but does not
     initialize it.

 - procedure: bit-string-copy bit-string
     Returns a newly allocated copy of BIT-STRING.

Selecting Bit String Components
===============================

 - procedure: bit-string? object
     Returns `#t' if OBJECT is a bit string; otherwise returns `#f'.

 - procedure: bit-string-length bit-string
     Returns the length of BIT-STRING.

 - procedure: bit-string-ref bit-string k
     Returns `#t' if the Kth bit is 1; otherwise returns `#f'.  K must
     be a valid index of BIT-STRING.

 - procedure: bit-string-set! bit-string k
     Sets the Kth bit in BIT-STRING to 1 and returns an unspecified
     value.  K must be a valid index of BIT-STRING.

 - procedure: bit-string-clear! bit-string k
     Sets the Kth bit in BIT-STRING to 0 and returns an unspecified
     value.  K must be a valid index of BIT-STRING.

 - procedure: bit-substring-find-next-set-bit bit-string start end
     Returns the index of the first occurrence of a set bit in the
     substring of BIT-STRING from START (inclusive) to END (exclusive).
     If none of the bits in the substring are set `#f' is returned.
     The index returned is relative to the whole bit string, not
     substring.

     The following procedure uses `bit-substring-find-next-set-bit' to
     find all the set bits and display their indexes:

          (define (scan-bitstring bs)
            (let ((end (bit-string-length bs)))
              (let loop ((start 0))
                (let ((next
                       (bit-substring-find-next-set-bit bs start end)))
                  (if next
                      (begin
                        (write-line next)
                        (if (< next end)
                            (loop (+ next 1)))))))))

Cutting and Pasting Bit Strings
===============================

 - procedure: bit-string-append bit-string-1 bit-string-2
     Appends the two bit string arguments, returning a newly allocated
     bit string as its result.  In the result, the bits copied from
     BIT-STRING-1 are less significant (smaller indices) than those
     copied from BIT-STRING-2.

 - procedure: bit-substring bit-string start end
     Returns a newly allocated bit string whose bits are copied from
     BIT-STRING, starting at index START (inclusive) and ending at END
     (exclusive).

Bitwise Operations on Bit Strings
=================================

 - procedure: bit-string-zero? bit-string
     Returns `#t' if BIT-STRING contains only 0 bits; otherwise returns
     `#f'.

 - procedure: bit-string=? bit-string-1 bit-string-2
     Compares the two bit string arguments and returns `#t' if they are
     the same length and contain the same bits; otherwise returns `#f'.

 - procedure: bit-string-not bit-string
     Returns a newly allocated bit string that is the bitwise-logical
     negation of BIT-STRING.

 - procedure: bit-string-movec! target-bit-string bit-string
     The destructive version of `bit-string-not'.  The arguments
     TARGET-BIT-STRING and BIT-STRING must be bit strings of the same
     length.  The bitwise-logical negation of BIT-STRING is computed
     and the result placed in TARGET-BIT-STRING.  The value of this
     procedure is unspecified.

 - procedure: bit-string-and bit-string-1 bit-string-2
     Returns a newly allocated bit string that is the bitwise-logical
     "and" of the arguments.  The arguments must be bit strings of
     identical length.

 - procedure: bit-string-andc bit-string-1 bit-string-2
     Returns a newly allocated bit string that is the bitwise-logical
     "and" of BIT-STRING-1 with the bitwise-logical negation of
     BIT-STRING-2.  The arguments must be bit strings of identical
     length.

 - procedure: bit-string-or bit-string-1 bit-string-2
     Returns a newly allocated bit string that is the bitwise-logical
     "inclusive or" of the arguments.  The arguments must be bit
     strings of identical length.

 - procedure: bit-string-xor bit-string-1 bit-string-2
     Returns a newly allocated bit string that is the bitwise-logical
     "exclusive or" of the arguments.  The arguments must be bit
     strings of identical length.

 - procedure: bit-string-and! target-bit-string bit-string
 - procedure: bit-string-or! target-bit-string bit-string
 - procedure: bit-string-xor! target-bit-string bit-string
 - procedure: bit-string-andc! target-bit-string bit-string
     These are destructive versions of the above operations.  The
     arguments TARGET-BIT-STRING and BIT-STRING must be bit strings of
     the same length.  Each of these procedures performs the
     corresponding bitwise-logical operation on its arguments, places
     the result into TARGET-BIT-STRING, and returns an unspecified
     result.

Modification of Bit Strings
===========================

 - procedure: bit-string-fill! bit-string initialization
     Fills BIT-STRING with zeroes if INITIALIZATION is `#f'; otherwise
     fills BIT-STRING with ones.  Returns an unspecified value.

 - procedure: bit-string-move! target-bit-string bit-string
     Moves the contents of BIT-STRING into TARGET-BIT-STRING.  Both
     arguments must be bit strings of the same length.  The results of
     the operation are undefined if the arguments are the same bit
     string.

 - procedure: bit-substring-move-right! bit-string-1 start1 end1
          bit-string-2 start2
     Destructively copies the bits of BIT-STRING-1, starting at index
     START1 (inclusive) and ending at END1 (exclusive), into
     BIT-STRING-2 starting at index START2 (inclusive).  START1 and
     END1 must be valid substring indices for BIT-STRING-1, and START2
     must be a valid index for BIT-STRING-2.  The length of the source
     substring must not exceed the length of BIT-STRING-2 minus the
     index START2.

     The bits are copied starting from the MSB and working towards the
     LSB; the direction of copying only matters when BIT-STRING-1 and
     BIT-STRING-2 are `eqv?'.

Integer Conversions of Bit Strings
==================================

 - procedure: unsigned-integer->bit-string length integer
     Both LENGTH and INTEGER must be exact non-negative integers.
     Converts INTEGER into a newly allocated bit string of LENGTH bits.
     Signals an error of type `condition-type:bad-range-argument' if
     INTEGER is too large to be represented in LENGTH bits.

 - procedure: signed-integer->bit-string length integer
     LENGTH must be an exact non-negative integer, and INTEGER may be
     any exact integer.  Converts INTEGER into a newly allocated bit
     string of LENGTH bits, using two's complement encoding for
     negative numbers.  Signals an error of type
     `condition-type:bad-range-argument' if INTEGER is too large to be
     represented in LENGTH bits.

 - procedure: bit-string->unsigned-integer bit-string
 - procedure: bit-string->signed-integer bit-string
     Converts BIT-STRING into an exact integer.
     `bit-string->signed-integer' regards BIT-STRING as a two's
     complement representation of a signed integer, and produces an
     integer of like sign and absolute value.
     `bit-string->unsigned-integer' regards BIT-STRING as an unsigned
     quantity and converts to an integer accordingly.

Miscellaneous Datatypes
***********************

Booleans
========

   The "boolean objects" are "true" and "false".  The boolean constant
true is written as `#t', and the boolean constant false is written as
`#f'.

   The primary use for boolean objects is in the conditional expressions
`if', `cond', `and', and `or'; the behavior of these expressions is
determined by whether objects are true or false.  These expressions
count only `#f' as false.  They count everything else, including `#t',
pairs, symbols, numbers, strings, vectors, and procedures as true (but
True and False).

   Programmers accustomed to other dialects of Lisp should note that
Scheme distinguishes `#f' and the empty list from the symbol `nil'.
Similarly, `#t' is distinguished from the symbol `t'.  In fact, the
boolean objects (and the empty list) are not symbols at all.

   Boolean constants evaluate to themselves, so you don't need to quote
them.

     #t                                      =>  #t
     #f                                      =>  #f
     '#f                                     =>  #f
     t                                       error--> Unbound variable

 - variable: false
 - variable: true
     These variables are bound to the objects `#f' and `#t'
     respectively.  The compiler, given the `usual-integrations'
     declaration, replaces references to these variables with their
     respective values.

     Note that the symbol `true' is not equivalent to `#t', and the
     symbol `false' is not equivalent to `#f'.

 - procedure: boolean? object
     Returns `#t' if OBJECT is either `#t' or `#f'; otherwise returns
     `#f'.

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

 - procedure: not object
 - procedure: false? object
     These procedures return `#t' if OBJECT is false; otherwise they
     return `#f'.  In other words they _invert_ boolean values.  These
     two procedures have identical semantics; their names are different
     to give different connotations to the test.

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

 - procedure: boolean=? obj1 obj2
     This predicate is true iff OBJ1 and OBJ2 are either both true or
     both false.

 - procedure: boolean/and object ...
     This procedure returns `#t' if none of its arguments are `#f'.
     Otherwise it returns `#f'.

 - procedure: boolean/or object ...
     This procedure returns `#f' if all of its arguments are `#f'.
     Otherwise it returns `#t'.

Symbols
=======

   MIT Scheme provides two types of symbols: "interned" and
"uninterned".  Interned symbols are far more common than uninterned
symbols, and there are more ways to create them.  Interned symbols have
an external representation that is recognized by the procedure `read';
uninterned symbols do not.(1)

   Interned symbols have an extremely useful property: any two interned
symbols whose names are the same, in the sense of `string=?', are the
same object (i.e. they are `eq?' to one another).  The term "interned"
refers to the process of "interning" by which this is accomplished.
Uninterned symbols do not share this property.

   The names of interned symbols are not distinguished by their
alphabetic case.  Because of this, MIT Scheme converts all alphabetic
characters in the name of an interned symbol to a specific case (lower
case) when the symbol is created.  When the name of an interned symbol
is referenced (using `symbol->string') or written (using `write') it
appears in this case.  It is a bad idea to depend on the name being
lower case.  In fact, it is preferable to take this one step further:
don't depend on the name of a symbol being in a uniform case.

   The rules for writing an interned symbol are the same as the rules
for writing an identifier (see Identifiers).  Any interned 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
`eq?').

   Usually it is also true that reading in an interned symbol that was
previously written out produces the same symbol.  An exception are
symbols created by the procedures `string->symbol' and `intern'; they
can create symbols for which this write/read invariance may not hold
because the symbols' names contain special characters or letters in the
non-standard case.(2)

   The external representation for uninterned symbols is special, to
distinguish them from interned symbols and prevent them from being
recognized by the `read' procedure:

     (string->uninterned-symbol "foo")
          =>  #[uninterned-symbol 30 foo]

   In this section, the procedures that return symbols as values will
either always return interned symbols, or always return uninterned
symbols.  The procedures that accept symbols as arguments will always
accept either interned or uninterned symbols, and do not distinguish the
two.

 - procedure: symbol? object
     Returns `#t' if OBJECT is a symbol, otherwise returns `#f'.

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

 - procedure: symbol->string symbol
     Returns the name of SYMBOL as a string.  If SYMBOL was returned by
     `string->symbol', the value of this procedure will be identical
     (in the sense of `string=?') to the string that was passed to
     `string->symbol'.  It is an error to apply mutation procedures
     such as `string-set!' to strings returned by this procedure.

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

     Note that two distinct uninterned symbols can have the same name.

 - procedure: intern string
     Returns the interned symbol whose name is STRING.  Converts STRING
     to the standard alphabetic case before generating the symbol.
     This is the preferred way to create interned symbols, as it
     guarantees the following independent of which case the
     implementation uses for symbols' names:

          (eq? 'bitBlt (intern "bitBlt")) =>     #t

     The user should take care that STRING obeys the rules for
     identifiers (see Identifiers), otherwise the resulting symbol
     cannot be read as itself.

 - procedure: intern-soft string
     Returns the interned symbol whose name is STRING.  Converts STRING
     to the standard alphabetic case before generating the symbol.  If
     no such interned symbol exists, returns `#f'.

     This is exactly like `intern', except that it will not create an
     interned symbol, but only returns symbols that already exist.

 - procedure: string->symbol string
     Returns the interned symbol whose name is STRING.  Although you
     can use this procedure to create symbols with names containing
     special characters or lowercase letters, it's usually a bad idea
     to create such symbols because they cannot be read as themselves.
     See `symbol->string'.

          (eq? 'mISSISSIppi 'mississippi)         =>  #t
          (string->symbol "mISSISSIppi")
               =>  the symbol with the 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

 - procedure: string->uninterned-symbol string
     Returns a newly allocated uninterned symbol whose name is STRING.
     It is unimportant what case or characters are used in STRING.

     Note: this is the fastest way to make a symbol.

 - procedure: generate-uninterned-symbol [object]
     Returns a newly allocated uninterned symbol that is guaranteed to
     be different from any other object.  The symbol's name consists of
     a prefix string followed by the (exact non-negative integer) value
     of an internal counter.  The counter is initially zero, and is
     incremented after each call to this procedure.

     The optional argument OBJECT is used to control how the symbol is
     generated.  It may take one of the following values:

        * If OBJECT is omitted or `#f', the prefix is `"G"'.

        * If OBJECT is an exact non-negative integer, the internal
          counter is set to that integer prior to generating the result.

        * If OBJECT is a string, it is used as the prefix.

        * If OBJECT is a symbol, its name is used as the prefix.

          (generate-uninterned-symbol)
               =>  #[uninterned-symbol 31 G0]
          (generate-uninterned-symbol)
               =>  #[uninterned-symbol 32 G1]
          (generate-uninterned-symbol 'this)
               =>  #[uninterned-symbol 33 this2]
          (generate-uninterned-symbol)
               =>  #[uninterned-symbol 34 G3]
          (generate-uninterned-symbol 100)
               =>  #[uninterned-symbol 35 G100]
          (generate-uninterned-symbol)
               =>  #[uninterned-symbol 36 G101]

 - procedure: symbol-append symbol ...
     Returns the interned symbol whose name is formed by concatenating
     the names of the given symbols.  This procedure preserves the case
     of the names of its arguments, so if one or more of the arguments'
     names has non-standard case, the result will also have
     non-standard case.

          (symbol-append 'foo- 'bar)              =>  foo-bar
          ;; the arguments may be uninterned:
          (symbol-append 'foo- (string->uninterned-symbol "baz"))
                                                  =>  foo-baz
          ;; the result has the same case as the arguments:
          (symbol-append 'foo- (string->symbol "BAZ"))    =>  foo-BAZ

 - procedure: symbol-hash symbol
     Returns a hash number for SYMBOL, which is computed by calling
     `string-hash' on SYMBOL's name.  The hash number is an exact
     non-negative integer.

 - procedure: symbol-hash-mod symbol modulus
     MODULUS must be an exact positive integer.  Equivalent to

          (modulo (symbol-hash SYMBOL) MODULUS)

     This procedure is provided for convenience in constructing hash
     tables.  However, it is normally preferable to use
     `make-eq-hash-table' to build hash tables keyed by symbols,
     because `eq?' hash tables are much faster.

 - procedure: symbol<? symbol1 symbol2
     This procedure computes a total order on symbols.  It is
     equivalent to

          (string<? (symbol->string SYMBOL1)
                    (symbol->string SYMBOL2))

   ---------- Footnotes ----------

   (1) In older dialects of Lisp, uninterned symbols were fairly
important.  This was true because symbols were complicated data
structures: in addition to having value cells (and sometimes, function
cells), these structures contained "property lists".  Because of this,
uninterned symbols were often used merely for their property lists --
sometimes an uninterned symbol used this way was referred to as a
"disembodied property list".  In MIT Scheme, symbols do not have
property lists, or any other components besides their names.  There is
a different data structure similar to disembodied property lists:
one-dimensional tables (see 1D Tables).  For these reasons,
uninterned symbols are not very useful in MIT Scheme.  In fact, their
primary purpose is to simplify the generation of unique variable names
in programs that generate Scheme code.

   (2) MIT Scheme reserves a specific set of interned symbols for its
own use.  If you use these reserved symbols it is possible that you
could break specific pieces of software that depend on them.  The
reserved symbols all have names beginning with the characters `#[' and
ending with the character `]'; thus none of these symbols can be read
by the procedure `read' and hence are not likely to be used by accident.
For example, `(intern "#[unnamed-procedure]")' produces a reserved
symbol.

Cells
=====

   "Cells" are data structures similar to pairs except that they have
only one element.  They are useful for managing state.

 - procedure: cell? object
     Returns `#t' if OBJECT is a cell; otherwise returns `#f'.

 - procedure: make-cell object
     Returns a newly allocated cell whose contents is OBJECT.

 - procedure: cell-contents cell
     Returns the current contents of CELL.

 - procedure: set-cell-contents! cell object
     Alters the contents of CELL to be OBJECT.  Returns an unspecified
     value.

 - procedure: bind-cell-contents! cell object thunk
     Alters the contents of CELL to be OBJECT, calls THUNK with no
     arguments, then restores the original contents of CELL and returns
     the value returned by THUNK.  This is completely equivalent to
     dynamic binding of a variable, including the behavior when
     continuations are used (see Dynamic Binding).

Records
=======

   MIT Scheme provides a "record" abstraction, which is a simple and
flexible mechanism for building structures with named components.
Records can be defined and accessed using the procedures defined in this
section.  A less flexible but more concise way to manipulate records is
to use the `define-structure' special form (see Structure Definitions).

 - procedure: make-record-type type-name field-names
     Returns a "record-type descriptor", a value representing a new data
     type, disjoint from all others.  The TYPE-NAME argument must be a
     string, but is only used for debugging purposes (such as the
     printed representation of a record of the new type).  The
     FIELD-NAMES argument is a list of symbols naming the "fields" of a
     record of the new type.  It is an error if the list contains any
     duplicates.  It is unspecified how record-type descriptors are
     represented.

 - procedure: record-constructor record-type [field-names]
     Returns a procedure for constructing new members of the type
     represented by RECORD-TYPE.  The returned procedure accepts
     exactly as many arguments as there are symbols in the given list,
     FIELD-NAMES; these are used, in order, as the initial values of
     those fields in a new record, which is returned by the constructor
     procedure.  The values of any fields not named in the list of
     FIELD-NAMES are unspecified.  The FIELD-NAMES argument defaults to
     the list of field-names in the call to `make-record-type' that
     created the type represented by RECORD-TYPE; if the FIELD-NAMES
     argument is provided, it is an error if it contains any duplicates
     or any symbols not in the default list.

 - procedure: record-predicate record-type
     Returns a procedure for testing membership in the type represented
     by RECORD-TYPE.  The returned procedure accepts exactly one
     argument and returns `#t' if the argument is a member of the
     indicated record type; it returns `#f' otherwise.

 - procedure: record-accessor record-type field-name
     Returns a procedure for reading the value of a particular field of
     a member of the type represented by RECORD-TYPE.  The returned
     procedure accepts exactly one argument which must be a record of
     the appropriate type; it returns the current value of the field
     named by the symbol FIELD-NAME in that record.  The symbol
     FIELD-NAME must be a member of the list of field names in the call
     to `make-record-type' that created the type represented by
     RECORD-TYPE.

 - procedure: record-modifier record-type field-name
     Returns a procedure for writing the value of a particular field of
     a member of the type represented by RECORD-TYPE.  The returned
     procedure accepts exactly two arguments: first, a record of the
     appropriate type, and second, an arbitrary Scheme value; it
     modifies the field named by the symbol FIELD-NAME in that record
     to contain the given value.  The returned value of the modifier
     procedure is unspecified.  The symbol FIELD-NAME must be a member
     of the list of field names in the call to `make-record-type' that
     created the type represented by RECORD-TYPE.

 - procedure: record? object
     Returns `#t' if OBJECT is a record of any type and `#f' otherwise.
     Note that `record?' may be true of any Scheme value; of course,
     if it returns `#t' for some particular value, then
     `record-type-descriptor' is applicable to that value and returns an
     appropriate descriptor.

 - procedure: record-type-descriptor record
     Returns the record-type descriptor representing the type of
     RECORD.  That is, for example, if the returned descriptor were
     passed to `record-predicate', the resulting predicate would return
     `#t' when passed RECORD.  Note that it is not necessarily the case
     that the returned descriptor is the one that was passed to
     `record-constructor' in the call that created the constructor
     procedure that created RECORD.

 - procedure: record-type? object
     Returns `#t' if OBJECT is a record-type descriptor; otherwise
     returns `#f'.

 - procedure: record-type-name record-type
     Returns the type name associated with the type represented by
     RECORD-TYPE.  The returned value is `eqv?' to the TYPE-NAME
     argument given in the call to `make-record-type' that created the
     type represented by RECORD-TYPE.

 - procedure: record-type-field-names record-type
     Returns a list of the symbols naming the fields in members of the
     type represented by RECORD-TYPE.  The returned value is `equal?'
     to the FIELD-NAMES argument given in the call to
     `make-record-type' that created the type represented by
     RECORD-TYPE.(1)

   ---------- Footnotes ----------

   (1) In MIT Scheme, the returned list is always newly allocated.

Promises
========

 - special form: 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.

 - procedure: force promise
     Forces the value of _promise_.  If no value has been computed for
     the promise, then a value is computed and returned.  The value of
     the promise is cached (or "memoized") so that if it is forced a
     second time, the previously computed value is returned without any
     recomputation.

          (force (delay (+ 1 2)))                 =>  3

          (let ((p (delay (+ 1 2))))
            (list (force p) (force p)))           =>  (3 3)

          (define head car)

          (define tail
            (lambda (stream)
              (force (cdr stream))))

          (define a-stream
            (letrec ((next
                      (lambda (n)
                        (cons n (delay (next (+ n 1)))))))
              (next 0)))

          (head (tail (tail a-stream)))           =>  2

 - procedure: promise? object
     Returns `#t' if OBJECT is a promise; otherwise returns `#f'.

 - procedure: promise-forced? promise
     Returns `#t' if PROMISE has been forced and its value cached;
     otherwise returns `#f'.

 - procedure: promise-value promise
     If PROMISE has been forced and its value cached, this procedure
     returns the cached value.  Otherwise, an error is signalled.

   `force' and `delay' are mainly intended for programs written in
functional style.  The following examples should not be considered to
illustrate good programming style, but they illustrate the property that
the value of a promise is computed at most once.

     (define count 0)

     (define p
       (delay
        (begin
          (set! count (+ count 1))
          (* x 3))))

     (define x 5)

     count                                   =>  0
     p                                       =>  #[promise 54]
     (force p)                               =>  15
     p                                       =>  #[promise 54]
     count                                   =>  1
     (force p)                               =>  15
     count                                   =>  1

   Here is a possible implementation of `delay' and `force'.  We define
the expression

     (delay EXPRESSION)

to have the same meaning as the procedure call

     (make-promise (lambda () EXPRESSION))

where `make-promise' is defined as follows:

     (define make-promise
       (lambda (proc)
         (let ((already-run? #f)
               (result #f))
           (lambda ()
             (cond ((not already-run?)
                    (set! result (proc))
                    (set! already-run? #t)))
             result))))

   Promises are implemented here as procedures of no arguments, and
`force' simply calls its argument.

     (define force
       (lambda (promise)
         (promise)))

   Various extensions to this semantics of `delay' and `force' are
supported in some implementations (none of these are currently
supported in MIT Scheme):

   * Calling `force' on an object that is not a promise may simply
     return the object.

   * It may be the case that there is no means by which a promise can be
     operationally distinguished from its forced value.  That is,
     expressions like the following may evaluate to either `#t' or `#f',
     depending on the implementation:

          (eqv? (delay 1) 1)              =>  unspecified
          (pair? (delay (cons 1 2)))      =>  unspecified

   * Some implementations will implement "implicit forcing", where the
     value of a promise is forced by primitive procedures like `car' and
     `+':

          (+ (delay (* 3 7)) 13)          =>  34

Streams
=======

   In addition to promises, MIT Scheme supports a higher-level
abstraction called "streams".  Streams are similar to lists, except
that the tail of a stream is not computed until it is referred to.
This allows streams to be used to represent infinitely long lists.

 - procedure: stream object ...
     Returns a newly allocated stream whose elements are the arguments.
     Note that the expression `(stream)' returns the empty stream, or
     end-of-stream marker.

 - procedure: list->stream list
     Returns a newly allocated stream whose elements are the elements of
     LIST.  Equivalent to `(apply stream LIST)'.

 - procedure: stream->list stream
     Returns a newly allocated list whose elements are the elements of
     STREAM.  If STREAM has infinite length this procedure will not
     terminate.  This could have been defined by

          (define (stream->list stream)
            (if (stream-null? stream)
                '()
                (cons (stream-car stream)
                      (stream->list (stream-cdr stream)))))

 - special form: cons-stream object expression
     Returns a newly allocated stream pair.  Equivalent to `(cons
     OBJECT (delay EXPRESSION))'.

 - procedure: stream-pair? object
     Returns `#t' if OBJECT is a pair whose cdr contains a promise.
     Otherwise returns `#f'.  This could have been defined by

          (define (stream-pair? object)
            (and (pair? object)
                 (promise? (cdr object))))

 - procedure: stream-car stream
 - procedure: stream-first stream
     Returns the first element in STREAM.  `stream-car' is equivalent
     to `car'.  `stream-first' is a synonym for `stream-car'.

 - procedure: stream-cdr stream
 - procedure: stream-rest stream
     Returns the first tail of STREAM.  Equivalent to `(force (cdr
     STREAM))'.  `stream-rest' is a synonym for `stream-cdr'.

 - procedure: stream-null? stream
     Returns `#t' if STREAM is the end-of-stream marker; otherwise
     returns `#f'.  This is equivalent to `null?', but should be used
     whenever testing for the end of a stream.

 - procedure: stream-length stream
     Returns the number of elements in STREAM.  If STREAM has an
     infinite number of elements this procedure will not terminate.
     Note that this procedure forces all of the promises that comprise
     STREAM.

 - procedure: stream-ref stream k
     Returns the element of STREAM that is indexed by K; that is, the
     Kth element.  K must be an exact non-negative integer strictly
     less than the length of STREAM.

 - procedure: stream-head stream k
     Returns the first K elements of STREAM as a list.  K must be an
     exact non-negative integer strictly less than the length of STREAM.

 - procedure: stream-tail stream k
     Returns the tail of STREAM that is indexed by K; that is, the Kth
     tail.  This is equivalent to performing `stream-cdr' K times.  K
     must be an exact non-negative integer strictly less than the
     length of STREAM.

 - procedure: stream-map procedure stream stream ...
     Returns a newly allocated stream, each element being the result of
     invoking PROCEDURE with the corresponding elements of the STREAMs
     as its arguments.