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

Regular-expression procedures
-----------------------------

   Procedures that perform regular-expression match and search accept
standardized arguments.  REGEXP is the regular expression; it is a
string.  STRING is the string being matched or searched.  Procedures
that operate on substrings also accept START and END index arguments
with the usual meaning.  The optional argument CASE-FOLD? says whether
the match/search is case-sensitive; if CASE-FOLD? is `#f', it is
case-sensitive, otherwise it is case-insensitive.  The optional
argument SYNTAX-TABLE is a character syntax table that defines the
character syntax, such as which characters are legal word constituents.
This feature is primarily for Edwin, so character syntax tables will
not be documented here.  Supplying `#f' for (or omitting) SYNTAX-TABLE
will select the default character syntax, equivalent to Edwin's
`fundamental' mode.

 - procedure: re-string-match regexp string [case-fold? [syntax-table]]
 - procedure: re-substring-match regexp string start end [case-fold?
          [syntax-table]]
     These procedures match REGEXP against the respective string or
     substring, returning `#f' for no match, or a set of match registers
     (see below) if the match succeeds.  Here is an example showing how
     to extract the matched substring:

          (let ((r (re-substring-match REGEXP STRING START END)))
            (and r
                 (substring STRING START (re-match-end-index 0 r))))

 - procedure: re-string-search-forward regexp string [case-fold?
          [syntax-table]]
 - procedure: re-substring-search-forward regexp string start end
          [case-fold? [syntax-table]]
     Searches STRING for the leftmost substring matching REGEXP.
     Returns a set of match registers (see below) if the search is
     successful, or `#f' if it is unsuccessful.

     `re-substring-search-forward' limits its search to the specified
     substring of STRING; `re-string-search-forward' searches all of
     STRING.

 - procedure: re-string-search-backward regexp string [case-fold?
          [syntax-table]]
 - procedure: re-substring-search-backward regexp string start end
          [case-fold? [syntax-table]]
     Searches STRING for the rightmost substring matching REGEXP.
     Returns a set of match registers (see below) if the search is
     successful, or `#f' if it is unsuccessful.

     `re-substring-search-backward' limits its search to the specified
     substring of STRING; `re-string-search-backward' searches all of
     STRING.

   When a successful match or search occurs, the above procedures
return a set of "match registers".  The match registers are a set of
index registers that record indexes into the matched string.  Each index
register corresponds to an instance of the regular-expression grouping
operator `\(', and records the start index (inclusive) and end index
(exclusive) of the matched group.  These registers are numbered from
`1' to `9', corresponding left-to-right to the grouping operators in
the expression.  Additionally, register `0' corresponds to the entire
substring matching the regular expression.

 - procedure: re-match-start-index n registers
 - procedure: re-match-end-index n registers
     N must be an exact integer between `0' and `9' inclusive.
     REGISTERS must be a match-registers object as returned by one of
     the regular-expression match or search procedures above.
     `re-match-start-index' returns the start index of the corresponding
     regular-expression register, and `re-match-end-index' returns the
     corresponding end index.

 - procedure: re-match-extract string registers n
     REGISTERS must be a match-registers object as returned by one of
     the regular-expression match or search procedures above.  STRING
     must be the string that was passed as an argument to the procedure
     that returned REGISTERS.  N must be an exact integer between `0'
     and `9' inclusive.  If the matched regular expression contained M
     grouping operators, then the value of this procedure is undefined
     for N strictly greater than M.

     This procedure extracts the substring corresponding to the match
     register specified by REGISTERS and N.  This is equivalent to the
     following expression:

          (substring STRING
                     (re-match-start-index N REGISTERS)
                     (re-match-end-index N REGISTERS))

 - procedure: regexp-group alternative ...
     Each ALTERNATIVE must be a regular expression.  The returned value
     is a new regular expression that consists of the ALTERNATIVEs
     combined by a grouping operator.  For example:

          (regexp-group "foo" "bar" "baz")
            => "\\(foo\\|bar\\|baz\\)"

REXP abstraction
----------------

   In addition to providing standard regular-expression support, MIT
Scheme also provides the REXP abstraction.  This is an alternative way
to write regular expressions that is easier to read and understand than
the standard notation.  Regular expressions written in this notation
can be translated into the standard notation.

   The REXP abstraction is a set of combinators that are composed into
a complete regular expression.  Each combinator directly corresponds to
a particular piece of regular-expression notation.  For example, the
expression `(rexp-any-char)' corresponds to the `.' character in
standard regular-expression notation, while `(rexp* REXP)' corresponds
to the `*' character.

   The primary advantages of REXP are that it makes the nesting
structure of regular expressions explicit, and that it simplifies the
description of complex regular expressions by allowing them to be built
up using straightforward combinators.

 - procedure: rexp? object
     Returns `#t' if OBJECT is a REXP expression, or `#f' otherwise.  A
     REXP is one of: a string, which represents the pattern matching
     that string; a character set, which represents the pattern
     matching a character in that set; or an object returned by calling
     one of the procedures defined here.

 - procedure: rexp->regexp rexp
     Converts REXP to standard regular-expression notation, returning a
     newly-allocated string.

 - procedure: rexp-compile rexp
     Converts REXP to standard regular-expression notation, then
     compiles it and returns the compiled result.  Equivalent to

          (re-compile-pattern (rexp->regexp REXP) #f)

 - procedure: rexp-any-char
     Returns a REXP that matches any single character except a newline.
     This is equivalent to the `.' construct.

 - procedure: rexp-line-start
     Returns a REXP that matches the start of a line.  This is
     equivalent to the `^' construct.

 - procedure: rexp-line-end
     Returns a REXP that matches the end of a line.  This is equivalent
     to the `$' construct.

 - procedure: rexp-string-start
     Returns a REXP that matches the start of the text being matched.
     This is equivalent to the `\`' construct.

 - procedure: rexp-string-end
     Returns a REXP that matches the end of the text being matched.
     This is equivalent to the `\'' construct.

 - procedure: rexp-word-edge
     Returns a REXP that matches the start or end of a word.  This is
     equivalent to the `\b' construct.

 - procedure: rexp-not-word-edge
     Returns a REXP that matches anywhere that is not the start or end
     of a word.  This is equivalent to the `\B' construct.

 - procedure: rexp-word-start
     Returns a REXP that matches the start of a word.  This is
     equivalent to the `\<' construct.

 - procedure: rexp-word-end
     Returns a REXP that matches the end of a word.  This is equivalent
     to the `\>' construct.

 - procedure: rexp-word-char
     Returns a REXP that matches any word-constituent character.  This
     is equivalent to the `\w' construct.

 - procedure: rexp-not-word-char
     Returns a REXP that matches any character that isn't a word
     constituent.  This is equivalent to the `\W' construct.

   The next two procedures accept a SYNTAX-TYPE argument specifying the
syntax class to be matched against.  This argument is a symbol selected
from the following list.  Each symbol is followed by the equivalent
character used in standard regular-expression notation.  `whitespace'
(space character), `punctuation' (`.'), `word' (`w'), `symbol' (`_'),
`open' (`('), `close' (`)'), `quote' (`''), `string-delimiter' (`"'),
`math-delimiter' (`$'), `escape' (`\'), `char-quote' (`/'),
`comment-start' (`<'), `comment-end' (`>').

 - procedure: rexp-syntax-char syntax-type
     Returns a REXP that matches any character of type SYNTAX-TYPE.
     This is equivalent to the `\s' construct.

 - procedure: rexp-not-syntax-char syntax-type
     Returns a REXP that matches any character not of type SYNTAX-TYPE.
     This is equivalent to the `\S' construct.

 - procedure: rexp-sequence rexp ...
     Returns a REXP that matches each REXP argument in sequence.  If no
     REXP argument is supplied, the result matches the null string.
     This is equivalent to concatenating the regular expressions
     corresponding to each REXP argument.

 - procedure: rexp-alternatives rexp ...
     Returns a REXP that matches any of the REXP arguments.  This is
     equivalent to concatenating the regular expressions corresponding
     to each REXP argument, separating them by the `\|' construct.

 - procedure: rexp-group rexp ...
     `rexp-group' is like `rexp-sequence', except that the result is
     marked as a match group.  This is equivalent to the `\(' ... `\)'
     construct.

   The next three procedures in principal accept a single REXP
argument.  For convenience, they accept multiple arguments, which are
converted into a single argument by `rexp-group'.  Note, however, that
if only one REXP argument is supplied, and it's very simple, no
grouping occurs.

 - procedure: rexp* rexp ...
     Returns a REXP that matches zero or more instances of the pattern
     matched by the REXP arguments.  This is equivalent to the `*'
     construct.

 - procedure: rexp+ rexp ...
     Returns a REXP that matches one or more instances of the pattern
     matched by the REXP arguments.  This is equivalent to the `+'
     construct.

 - procedure: rexp-optional rexp ...
     Returns a REXP that matches zero or one instances of the pattern
     matched by the REXP arguments.  This is equivalent to the `?'
     construct.

 - procedure: rexp-case-fold rexp
     Returns a REXP that matches the same pattern as REXP, but is
     insensitive to character case.  This has no equivalent in standard
     regular-expression notation.

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

 - procedure: string-replace string char1 char2
 - procedure: substring-replace string start end char1 char2
 - procedure: string-replace! string char1 char2
 - procedure: substring-replace! string start end char1 char2
     These procedures replace all occurrences of CHAR1 with CHAR2 in
     the original string (substring).  `string-replace' and
     `substring-replace' return a newly allocated string containing the
     result.  `string-replace!' and `substring-replace!' destructively
     modify STRING and return an unspecified value.

          (define str "a few words")              =>  unspecified
          (string-replace str #\space #\-)        =>  "a-few-words"
          (substring-replace str 2 9 #\space #\-) =>  "a few-words"
          str                                     =>  "a few words"
          (string-replace! str #\space #\-)       =>  unspecified
          str                                     =>  "a-few-words"

 - procedure: string-fill! string char
     Stores CHAR in every element of STRING and returns an unspecified
     value.

 - procedure: substring-fill! string start end char
     Stores CHAR in elements START (inclusive) to END (exclusive) of
     STRING and returns an unspecified value.

          (define s (make-string 10 #\space))     =>  unspecified
          (substring-fill! s 2 8 #\*)             =>  unspecified
          s                                       =>  "  ******  "

 - procedure: substring-move-left! string1 start1 end1 string2 start2
 - procedure: substring-move-right! string1 start1 end1 string2 start2
     Copies the characters from START1 to END1 of STRING1 into STRING2
     at the START2-th position.  The characters are copied as follows
     (note that this is only important when STRING1 and STRING2 are
     `eqv?'):

    `substring-move-left!'
          The copy starts at the left end and moves toward the right
          (from smaller indices to larger).  Thus if STRING1 and
          STRING2 are the same, this procedure moves the characters
          toward the left inside the string.

    `substring-move-right!'
          The copy starts at the right end and moves toward the left
          (from larger indices to smaller).  Thus if STRING1 and
          STRING2 are the same, this procedure moves the characters
          toward the right inside the string.

     The following example shows how these procedures can be used to
     build up a string (it would have been easier to use
     `string-append'):
          (define answer (make-string 9 #\*))         =>  unspecified
          answer                                      =>  "*********"
          (substring-move-left! "start" 0 5 answer 0) =>  unspecified
          answer                                      =>  "start****"
          (substring-move-left! "-end" 0 4 answer 5)  =>  unspecified
          answer                                      =>  "start-end"

 - procedure: reverse-string string
 - procedure: reverse-substring string start end
 - procedure: reverse-string! string
 - procedure: reverse-substring! string start end
     Reverses the order of the characters in the given string or
     substring.  `reverse-string' and `reverse-substring' return newly
     allocated strings; `reverse-string!' and `reverse-substring!'
     modify their argument strings and return an unspecified value.

          (reverse-string "foo bar baz")          => "zab rab oof"
          (reverse-substring "foo bar baz" 4 7)   => "rab"
          (let ((foo "foo bar baz"))
            (reverse-string! foo)
            foo)                                  => "zab rab oof"
          (let ((foo "foo bar baz"))
            (reverse-substring! foo 4 7)
            foo)                                  => "foo rab baz"

Variable-Length Strings
=======================

   MIT Scheme allows the length of a string to be dynamically adjusted
in a limited way.  When a new string is allocated, by whatever method,
it has a specific length.  At the time of allocation, it is also given a
"maximum length", which is guaranteed to be at least as large as the
string's length.  (Sometimes the maximum length will be slightly larger
than the length, but it is a bad idea to count on this.  Programs should
assume that the maximum length is the same as the length at the time of
the string's allocation.)  After the string is allocated, the operation
`set-string-length!' can be used to alter the string's length to any
value between 0 and the string's maximum length, inclusive.

 - procedure: string-maximum-length string
     Returns the maximum length of STRING.  The following is guaranteed:

          (<= (string-length string)
              (string-maximum-length string))     =>  #t

     The maximum length of a string never changes.

 - procedure: set-string-length! string k
     Alters the length of STRING to be K, and returns an unspecified
     value.  K must be less than or equal to the maximum length of
     STRING.  `set-string-length!' does not change the maximum length
     of STRING.

Byte Vectors
============

   MIT Scheme implements strings as packed vectors of 8-bit ISO-8859-1
bytes.  Most of the string operations, such as `string-ref', coerce
these 8-bit codes into character objects.  However, some lower-level
operations are made available for use.

 - procedure: vector-8b-ref string k
     Returns character K of STRING as an ISO-8859-1 code.  K must be a
     valid index of STRING.

          (vector-8b-ref "abcde" 2)               =>  99 ;c

 - procedure: vector-8b-set! string k code
     Stores CODE in element K of STRING and returns an unspecified
     value.  K must be a valid index of STRING, and CODE must be a
     valid ISO-8859-1 code.

 - procedure: vector-8b-fill! string start end code
     Stores CODE in elements START (inclusive) to END (exclusive) of
     STRING and returns an unspecified value.  CODE must be a valid
     ISO-8859-1 code.

 - procedure: vector-8b-find-next-char string start end code
 - procedure: vector-8b-find-next-char-ci string start end code
     Returns the index of the first occurrence of CODE in the given
     substring; returns `#f' if CODE does not appear.  The index
     returned is relative to the entire string, not just the substring.
     CODE must be a valid ISO-8859-1 code.

     `vector-8b-find-next-char-ci' doesn't distinguish uppercase and
     lowercase letters.

 - procedure: vector-8b-find-previous-char string start end code
 - procedure: vector-8b-find-previous-char-ci string start end code
     Returns the index of the last occurrence of CODE in the given
     substring; returns `#f' if CODE does not appear.  The index
     returned is relative to the entire string, not just the substring.
     CODE must be a valid ISO-8859-1 code.

     `vector-8b-find-previous-char-ci' doesn't distinguish uppercase and
     lowercase letters.

Lists
*****

   A "pair" (sometimes called a "dotted pair") is a data 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.(1)

   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, the following are
equivalent notations for a list of symbols:

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

   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? y)                               =>  #f

   A chain of pairs that doesn't end 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, as
the following equivalent notations show:

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

   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.  Among
other things, this permits the use of the `read' procedure to parse
Scheme programs.

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

   (1) The above definitions imply that all lists have finite length
and are terminated by the empty list.

Pairs
=====

   This section describes the simple operations that are available for
constructing and manipulating arbitrary graphs constructed from pairs.

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

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

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

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

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

 - procedure: set-car! pair object
     Stores OBJECT 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--> Illegal datum

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

 - procedure: caar pair
 - procedure: cadr pair
 - procedure: cdar pair
 - procedure: cddr pair
 - procedure: caaar pair
 - procedure: caadr pair
 - procedure: cadar pair
 - procedure: caddr pair
 - procedure: cdaar pair
 - procedure: cdadr pair
 - procedure: cddar pair
 - procedure: cdddr pair
 - procedure: caaaar pair
 - procedure: caaadr pair
 - procedure: caadar pair
 - procedure: caaddr pair
 - procedure: cadaar pair
 - procedure: cadadr pair
 - procedure: caddar pair
 - procedure: cadddr pair
 - procedure: cdaaar pair
 - procedure: cdaadr pair
 - procedure: cdadar pair
 - procedure: cdaddr pair
 - procedure: cddaar pair
 - procedure: cddadr pair
 - procedure: cdddar pair
 - procedure: cddddr pair
     These procedures are compositions of `car' and `cdr'; for example,
     `caddr' could be defined by

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

 - procedure: general-car-cdr object path
     This procedure is a generalization of `car' and `cdr'.  PATH
     encodes a particular sequence of `car' and `cdr' operations, which
     `general-car-cdr' executes on OBJECT.  PATH is an exact
     non-negative integer that encodes the operations in a bitwise
     fashion: a zero bit represents a `cdr' operation, and a one bit
     represents a `car'.  The bits are executed LSB to MSB, and the
     most significant one bit, rather than being interpreted as an
     operation, signals the end of the sequence.(1)

     For example, the following are equivalent:
          (general-car-cdr OBJECT #b1011)
          (cdr (car (car OBJECT)))

     Here is a partial table of path/operation equivalents:

          #b10    cdr
          #b11    car
          #b100   cddr
          #b101   cdar
          #b110   cadr
          #b111   caar
          #b1000  cdddr

 - procedure: tree-copy tree
     This copies an arbitrary TREE constructed from pairs, copying both
     the car and cdr elements of every pair.  This could have been
     defined by

          (define (tree-copy tree)
            (let loop ((tree tree))
              (if (pair? tree)
                  (cons (loop (car tree)) (loop (cdr tree)))
                  tree)))

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

   (1) Note that PATH is restricted to a machine-dependent range,
usually the size of a machine word.  On many machines, this means that
the maximum length of PATH will be 30 operations (32 bits, less the
sign bit and the "end-of-sequence" bit).

Construction of Lists
=====================

 - procedure: list object ...
     Returns a list of its arguments.

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

     These expressions are equivalent:

          (list OBJ1 OBJ2 ... OBJN)
          (cons OBJ1 (cons OBJ2 ... (cons OBJN '()) ...))

 - procedure: make-list k [element]
     This procedure returns a newly allocated list of length K, whose
     elements are all ELEMENT.  If ELEMENT is not supplied, it defaults
     to the empty list.

 - procedure: cons* object object ...
     `cons*' is similar to `list', except that `cons*' conses together
     the last two arguments rather than consing the last argument with
     the empty list.  If the last argument is not a list the result is
     an improper list.  If the last argument is a list, the result is a
     list consisting of the initial arguments and all of the items in
     the final argument.  If there is only one argument, the result is
     the argument.

          (cons* 'a 'b 'c)                        =>  (a b . c)
          (cons* 'a 'b '(c d))                    =>  (a b c d)
          (cons* 'a)                              =>  a

     These expressions are equivalent:

          (cons* OBJ1 OBJ2 ... OBJN-1 OBJN)
          (cons OBJ1 (cons OBJ2 ... (cons OBJN-1 OBJN) ...))

 - procedure: list-copy list
     Returns a newly allocated copy of LIST.  This copies each of the
     pairs comprising LIST.  This could have been defined by

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

 - procedure: vector->list vector
 - procedure: subvector->list vector start end
     `vector->list' returns a newly allocated list of the elements of
     VECTOR.
     `subvector->list' returns a newly allocated list of the elements
     of the given subvector.  The inverse of `vector->list' is
     `list->vector'.

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

 - procedure: string->list string
 - procedure: substring->list string start end
     `string->list' returns a newly allocated list of the character
     elements of STRING.
     `substring->list' returns a newly allocated list of the character
     elements of the given substring.  The inverse of `string->list' is
     `list->string'.

          (string->list "abcd")                   =>  (#\a #\b #\c #\d)
          (substring->list "abcdef" 1 3)          =>  (#\b #\c)

Selecting List Components
=========================

 - procedure: list? object
     Returns `#t' if OBJECT is a list, otherwise returns `#f'.  By
     definition, all lists have finite length and are terminated by the
     empty list.  This procedure returns an answer even for circular
     structures.

     Any OBJECT satisfying this predicate will also satisfy exactly one
     of `pair?' or `null?'.

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

 - procedure: length list
     Returns the length of LIST.  Signals an error if LIST isn't a
     proper list.

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

 - procedure: null? object
     Returns `#t' if OBJECT is the empty list; otherwise returns `#f'
     (but True and False).

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

 - procedure: list-ref list k
     Returns the Kth element of LIST, using zero-origin indexing.  The
     "valid indexes" of a list are the exact non-negative integers less
     than the length of the list.  The first element of a list has index
     `0', the second has index `1', and so on.

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

     `(list-ref LIST K)' is equivalent to `(car (list-tail LIST K))'.

 - procedure: first list
 - procedure: second list
 - procedure: third list
 - procedure: fourth list
 - procedure: fifth list
 - procedure: sixth list
 - procedure: seventh list
 - procedure: eighth list
 - procedure: ninth list
 - procedure: tenth list
     Returns the specified element of LIST.  It is an error if LIST is
     not long enough to contain the specified element (for example, if
     the argument to `seventh' is a list that contains only six
     elements).

Cutting and Pasting Lists
=========================

 - procedure: sublist list start end
     START and END must be exact integers satisfying

          0 <= START <= END <= (length LIST)

     `sublist' returns a newly allocated list formed from the elements
     of LIST beginning at index START (inclusive) and ending at END
     (exclusive).

 - procedure: list-head list k
     Returns a newly allocated list consisting of the first K elements
     of LIST.  K must not be greater than the length of LIST.

     We could have defined `list-head' this way:

          (define (list-head list k)
            (sublist list 0 k))

 - procedure: list-tail list k
     Returns the sublist of LIST obtained by omitting the first K
     elements.  The result, if it is not the empty list, shares
     structure with LIST.  K must not be greater than the length of
     LIST.

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

     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

 - procedure: append! list ...
     Returns a list that is the argument LISTs concatenated together.
     The arguments are changed rather than copied.  (Compare this with
     `append', which copies arguments rather than destroying them.)  For
     example:

          (define x '(a b c))
          (define y '(d e f))
          (define z '(g h))
          (append! x y z)                         =>  (a b c d e f g h)
          x                                       =>  (a b c d e f g h)
          y                                       =>  (d e f g h)
          z                                       =>  (g h)

 - procedure: last-pair list
     Returns the last pair in LIST, which may be an improper list.
     `last-pair' could have been defined this way:

          (define last-pair
            (lambda (x)
              (if (pair? (cdr x))
                  (last-pair (cdr x))
                  x)))

 - procedure: except-last-pair list
 - procedure: except-last-pair! list
     These procedures remove the last pair from LIST.  LIST may be an
     improper list, except that it must consist of at least one pair.
     `except-last-pair' returns a newly allocated copy of LIST that
     omits the last pair.  `except-last-pair!' destructively removes
     the last pair from LIST and returns LIST.  If the cdr of LIST is
     not a pair, the empty list is returned by either procedure.

Filtering Lists
===============

 - procedure: keep-matching-items list predicate
 - procedure: delete-matching-items list predicate
     These procedures return a newly allocated copy of LIST containing
     only the elements for which PREDICATE is (respectively) true or
     false.  PREDICATE must be a procedure of one argument.

          (keep-matching-items '(1 2 3 4 5) odd?) => (1 3 5)
          (delete-matching-items '(1 2 3 4 5) odd?) => (2 4)

     For compatibility, the procedure `list-transform-positive' is an
     alias for `keep-matching-items', and `list-transform-negative' is
     an alias for `delete-matching-items'.

 - procedure: keep-matching-items! list predicate
 - procedure: delete-matching-items! list predicate
     These procedures are exactly like `keep-matching-items' and
     `delete-matching-items', respectively, except that they
     destructively modify the LIST argument rather than allocating a
     new result.

 - procedure: delq element list
 - procedure: delv element list
 - procedure: delete element list
     Returns a newly allocated copy of LIST with all entries equal to
     ELEMENT removed.  `delq' uses `eq?' to compare ELEMENT with the
     entries in LIST, `delv' uses `eqv?', and `delete' uses `equal?'.

 - procedure: delq! element list
 - procedure: delv! element list
 - procedure: delete! element list
     Returns a list consisting of the top-level elements of LIST with
     all entries equal to ELEMENT removed.  These procedures are like
     `delq', `delv', and `delete' except that they destructively modify
     LIST.  `delq!' uses `eq?' to compare element with the entries in
     LIST, `delv!' uses `eqv?', and `delete!' uses `equal?'.  Because
     the result may not be `eq?' to LIST, it is desirable to do
     something like `(set! x (delete! x))'.

          (define x '(a b c b))
          (delete 'b x)                           =>  (a c)
          x                                       =>  (a b c b)

          (define x '(a b c b))
          (delete! 'b x)                          =>  (a c)
          x                                       =>  (a c)
          ;; Returns correct result:
          (delete! 'a x)                          =>  (c)

          ;; Didn't modify what x points to:
          x                                       =>  (a c)

 - procedure: delete-member-procedure deletor predicate
     Returns a deletion procedure similar to `delv' or `delete!'.
     DELETOR should be one of the procedures `list-deletor' or
     `list-deletor!'.  PREDICATE must be an equivalence predicate.  The
     returned procedure accepts exactly two arguments: first, an object
     to be deleted, and second, a list of objects from which it is to be
     deleted.  If DELETOR is `list-deletor', the procedure returns a
     newly allocated copy of the given list in which all entries equal
     to the given object have been removed.  If DELETOR is
     `list-deletor!', the procedure returns a list consisting of the
     top-level elements of the given list with all entries equal to the
     given object removed; the given list is destructively modified to
     produce the result.  In either case PREDICATE is used to compare
     the given object to the elements of the given list.

     Here are some examples that demonstrate how
     `delete-member-procedure' could have been used to implement `delv'
     and `delete!':

          (define delv
            (delete-member-procedure list-deletor eqv?))
          (define delete!
            (delete-member-procedure list-deletor! equal?))

 - procedure: list-deletor predicate
 - procedure: list-deletor! predicate
     These procedures each return a procedure that deletes elements from
     lists.  PREDICATE must be a procedure of one argument.  The
     returned procedure accepts exactly one argument, which must be a
     proper list, and applies PREDICATE to each of the elements of the
     argument, deleting those for which it is true.

     The procedure returned by `list-deletor' deletes elements
     non-destructively, by returning a newly allocated copy of the
     argument with the appropriate elements removed.  The procedure
     returned by `list-deletor!' performs a destructive deletion.

Searching Lists
===============

 - procedure: find-matching-item list predicate
     Returns the first element in LIST for which PREDICATE is true;
     returns `#f' if it doesn't find such an element.  (This means that
     if PREDICATE is true for `#f', it may be impossible to distinguish
     a successful result from an unsuccessful one.)  PREDICATE must be
     a procedure of one argument.

     For compatibility, `list-search-positive' is an alias for
     `find-matching-item'.  `list-search-negative' is similar but the
     sense of the predicate is reversed.

 - procedure: memq object list
 - procedure: memv object list
 - procedure: member object list
     These procedures return the first pair of LIST whose car is
     OBJECT; the returned pair is always one from which LIST is
     composed.  If OBJECT does not occur in LIST, `#f' (n.b.: not the
     empty list) is returned.  `memq' uses `eq?' to compare OBJECT with
     the elements of LIST, while `memv' uses `eqv?' and `member' uses
     `equal?'.(1)

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

 - procedure: member-procedure predicate
     Returns a procedure similar to `memq', except that PREDICATE,
     which must be an equivalence predicate, is used instead of `eq?'.
     This could be used to define `memv' as follows:

          (define memv (member-procedure eqv?))

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

   (1) Although they are often used as predicates, `memq', `memv', and
`member' do not have question marks in their names because they return
useful values rather than just `#t' or `#f'.

Mapping of Lists
================

 - procedure: map procedure list list ...
     PROCEDURE must be a procedure taking as many arguments as there
     are LISTs.  If more than one LIST is given, then they must all be
     the same length.  `map' applies PROCEDURE element-wise to the
     elements of the LISTs and returns a list of the results, in order
     from left to right.  The dynamic order in which PROCEDURE is
     applied to the elements of the LISTs is unspecified; use
     `for-each' to sequence side effects.

          (map cadr '((a b) (d e) (g h)))           =>  (b e h)
          (map (lambda (n) (expt n n)) '(1 2 3 4))  =>  (1 4 27 256)
          (map + '(1 2 3) '(4 5 6))                 =>  (5 7 9)
          (let ((count 0))
            (map (lambda (ignored)
                   (set! count (+ count 1))
                   count)
                 '(a b c)))                         =>  unspecified

 - procedure: map* initial-value procedure list1 list2 ...
     Similar to `map', except that the resulting list is terminated by
     INITIAL-VALUE rather than the empty list.  The following are
     equivalent:

          (map PROCEDURE LIST LIST ...)
          (map* '() PROCEDURE LIST LIST ...)

 - procedure: append-map procedure list list ...
 - procedure: append-map* initial-value procedure list list ...
     Similar to `map' and `map*', respectively, except that the results
     of applying PROCEDURE to the elements of LISTs are concatenated
     together by `append' rather than by `cons'.  The following are
     equivalent, except that the former is more efficient:

          (append-map PROCEDURE LIST LIST ...)
          (apply append (map PROCEDURE LIST LIST ...))

 - procedure: append-map! procedure list list ...
 - procedure: append-map*! initial-value procedure list list ...
     Similar to `map' and `map*', respectively, except that the results
     of applying PROCEDURE to the elements of LISTs are concatenated
     together by `append!' rather than by `cons'.  The following are
     equivalent, except that the former is more efficient:

          (append-map! PROCEDURE LIST LIST ...)
          (apply append! (map PROCEDURE LIST LIST ...))

 - procedure: for-each procedure list list ...
     The arguments to `for-each' are like the arguments to `map', but
     `for-each' calls PROCEDURE for its side effects rather than for
     its values.  Unlike `map', `for-each' is guaranteed to call
     PROCEDURE on the elements of the LISTs in order from the first
     element to the last, and the value returned by `for-each' is
     unspecified.

          (let ((v (make-vector 5)))
            (for-each (lambda (i)
                        (vector-set! v i (* i i)))
                      '(0 1 2 3 4))
            v)                            =>  #(0 1 4 9 16)

Reduction of Lists
==================

 - procedure: reduce procedure initial list
     Combines all the elements of LIST using the binary operation
     PROCEDURE.  For example, using `+' one can add up all the elements:

          (reduce + 0 list-of-numbers)

     The argument INITIAL is used only if LIST is empty; in this case
     INITIAL is the result of the call to `reduce'.  If LIST has a
     single argument, it is returned.  Otherwise, the arguments are
     reduced in a left-associative fashion.  For example:

          (reduce + 0 '(1 2 3 4))                 =>  10
          (reduce + 0 '(1 2))                     =>  3
          (reduce + 0 '(1))                       =>  1
          (reduce + 0 '())                        =>  0
          (reduce + 0 '(foo))                     =>  foo
          (reduce list '() '(1 2 3 4))            =>  (((1 2) 3) 4)

 - procedure: reduce-right procedure initial list
     Like `reduce' except that it is right-associative.

          (reduce-right list '() '(1 2 3 4))      =>  (1 (2 (3 4)))

 - procedure: fold-right procedure initial list
     Combines all of the elements of LIST using the binary operation
     PROCEDURE.  Unlike `reduce' and `reduce-right', INITIAL is always
     used:

          (fold-right + 0 '(1 2 3 4))             =>  10
          (fold-right + 0 '(foo))                 error--> Illegal datum
          (fold-right list '() '(1 2 3 4))        =>  (1 (2 (3 (4 ()))))

     `Fold-right' has interesting properties because it establishes a
     homomorphism between (`cons', `()') and (PROCEDURE, INITIAL).  It
     can be thought of as replacing the pairs in the spine of the list
     with PROCEDURE and replacing the `()' at the end with INITIAL.
     Many of the classical list-processing procedures can be expressed
     in terms of `fold-right', at least for the simple versions that
     take a fixed number of arguments:

          (define (copy-list list)
            (fold-right cons '() list))

          (define (append list1 list2)
            (fold-right cons list2 list1))

          (define (map p list)
            (fold-right (lambda (x r) (cons (p x) r)) '() list))

          (define (reverse items)
            (fold-right (lambda (x r) (append r (list x))) '() items))

 - procedure: fold-left procedure initial list
     Combines all the elements of LIST using the binary operation
     PROCEDURE.  Elements are combined starting with INITIAL and then
     the elements of LIST from left to right.  Whereas `fold-right' is
     recursive in nature, capturing the essence of `cdr'-ing down a
     list and then computing a result, FOLD-LEFT is iterative in
     nature, combining the elements as the list is traversed.

          (fold-left list '() '(1 2 3 4))         =>  ((((() 1) 2) 3) 4)

          (define (length list)
            (fold-left (lambda (sum element) (+ sum 1)) 0 list))

          (define (reverse items)
            (fold-left (lambda (x y) (cons y x)) () items))

 - procedure: there-exists? list predicate
     PREDICATE must be a procedure of one argument.  Applies PREDICATE
     to each element of LIST, in order from left to right.  If
     PREDICATE is true for any element of LIST, the value yielded by
     PREDICATE is immediately returned as the value of `there-exists?';
     PREDICATE will not be applied to the remaining elements of LIST.
     If PREDICATE returns `#f' for all of the elements of LIST, then
     `#f' is returned.

 - procedure: for-all? list predicate
     PREDICATE must be a procedure of one argument.  Applies PREDICATE
     to each element of LIST, in order from left to right.  If
     PREDICATE returns `#f' for any element of LIST, `#f' is
     immediately returned as the value of `for-all?'; PREDICATE will
     not be applied to the remaining elements of LIST.  If PREDICATE is
     true for all of the elements of LIST, then `#t' is returned.