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

Red-Black Trees
===============

   Balanced binary trees are a useful data structure for maintaining
large sets of associations whose keys are ordered.  While most
applications involving large association sets should use hash tables,
some applications can benefit from the use of binary trees.  Binary
trees have two advantages over hash tables:

   * The contents of a binary tree can be converted to an alist, sorted
     by key, in time proportional to the number of associations in the
     tree.  A hash table can be converted into an unsorted alist in
     linear time; sorting it requires additional time.

   * Two binary trees can be compared for equality in linear time.  Hash
     tables, on the other hand, cannot be compared at all; they must be
     converted to alists before comparison can be done, and alist
     comparison is quadratic unless the alists are sorted.

   MIT Scheme provides an implementation of "red-black" trees.  The
red-black tree-balancing algorithm provides generally good performance
because it doesn't try to keep the tree very closely balanced.  At any
given node in the tree, one side of the node can be twice as high as the
other in the worst case.  With typical data the tree will remain fairly
well balanced anyway.

   A red-black tree takes space that is proportional to the number of
associations in the tree.  For the current implementation, the constant
of proportionality is eight words per association.

   Red-black trees hold their keys "strongly".  In other words, if a
red-black tree contains an association for a given key, that key cannot
be reclaimed by the garbage collector.

   The red-black tree implementation is a run-time-loadable option.  To
use red-black trees, execute

     (load-option 'rb-tree)

once before calling any of the procedures defined here.

 - procedure: make-rb-tree key=? key<?
     This procedure creates and returns a newly allocated red-black
     tree.  The tree contains no associations.  KEY=? and KEY<? are
     predicates that compare two keys and determine whether they are
     equal to or less than one another, respectively.  For any two
     keys, at most one of these predicates is true.

 - procedure: rb-tree? object
     Returns `#t' if OBJECT is a red-black tree, otherwise returns `#f'.

 - procedure: rb-tree/insert! rb-tree key datum
     Associates DATUM with KEY in RB-TREE and returns an unspecified
     value.  If RB-TREE already has an association for KEY, that
     association is replaced.  The average and worst-case times
     required by this operation are proportional to the logarithm of
     the number of assocations in RB-TREE.

 - procedure: rb-tree/lookup rb-tree key default
     Returns the datum associated with KEY in RB-TREE.  If RB-TREE
     doesn't contain an association for KEY, DEFAULT is returned.  The
     average and worst-case times required by this operation are
     proportional to the logarithm of the number of assocations in
     RB-TREE.

 - procedure: rb-tree/delete! rb-tree key
     If RB-TREE contains an association for KEY, removes it.  Returns
     an unspecified value.  The average and worst-case times required
     by this operation are proportional to the logarithm of the number
     of assocations in RB-TREE.

 - procedure: rb-tree->alist rb-tree
     Returns the contents of RB-TREE as a newly allocated alist.  Each
     element of the alist is a pair `(KEY . DATUM)' where KEY is one of
     the keys of RB-TREE, and DATUM is its associated datum.  The alist
     is sorted by key according to the KEY<? argument used to construct
     RB-TREE.  The time required by this operation is proportional to
     the number of associations in the tree.

 - procedure: rb-tree/key-list rb-tree
     Returns a newly allocated list of the keys in RB-TREE.  The list
     is sorted by key according to the KEY<? argument used to construct
     RB-TREE.  The time required by this operation is proportional to
     the number of associations in the tree.

 - procedure: rb-tree/datum-list rb-tree
     Returns a newly allocated list of the datums in RB-TREE.  Each
     element of the list corresponds to one of the associations in
     RB-TREE, so if the tree contains multiple associations with the
     same datum, so will this list.  The list is sorted by the keys of
     the associations, even though they do not appear in the result.
     The time required by this operation is proportional to the number
     of associations in the tree.

     This procedure is equivalent to:

          (lambda (rb-tree) (map cdr (rb-tree->alist rb-tree)))

 - procedure: rb-tree/equal? rb-tree-1 rb-tree-2 datum=?
     Compares RB-TREE-1 and RB-TREE-2 for equality, returning `#t' iff
     they are equal and `#f' otherwise.  The trees must have been
     constructed with the same equality and order predicates (same in
     the sense of `eq?').  The keys of the trees are compared using the
     KEY=? predicate used to build the trees, while the datums of the
     trees are compared using the equivalence predicate DATUM=?.  The
     worst-case time required by this operation is proportional to the
     number of associations in the tree.

 - procedure: rb-tree/empty? rb-tree
     Returns `#t' iff RB-TREE contains no associations.  Otherwise
     returns `#f'.

 - procedure: rb-tree/size rb-tree
     Returns the number of associations in RB-TREE, an exact
     non-negative integer.  The average and worst-case times required
     by this operation are proportional to the number of associations
     in the tree.

 - procedure: rb-tree/height rb-tree
     Returns the height of RB-TREE, an exact non-negative integer.
     This is the length of the longest path from a leaf of the tree to
     the root.  The average and worst-case times required by this
     operation are proportional to the number of associations in the
     tree.

     The returned value satisfies the following:

          (lambda (rb-tree)
            (let ((size (rb-tree/size rb-tree))
                  (lg (lambda (x) (/ (log x) (log 2)))))
              (<= (lg size)
                  (rb-tree/height rb-tree)
                  (* 2 (lg (+ size 1))))))

 - procedure: rb-tree/copy rb-tree
     Returns a newly allocated copy of RB-TREE.  The copy is identical
     to RB-TREE in all respects, except that changes to RB-TREE do not
     affect the copy, and vice versa.  The time required by this
     operation is proportional to the number of associations in the
     tree.

 - procedure: alist->rb-tree alist key=? key<?
     Returns a newly allocated red-black tree that contains the same
     associations as ALIST.  This procedure is equivalent to:

          (lambda (alist key=? key<?)
            (let ((tree (make-rb-tree key=? key<?)))
              (for-each (lambda (association)
                          (rb-tree/insert! tree
                                           (car association)
                                           (cdr association)))
                        alist)
              tree))

   The following operations provide access to the smallest and largest
members in a red/black tree.  They are useful for implementing priority
queues.

 - procedure: rb-tree/min rb-tree default
     Returns the smallest key in RB-TREE, or DEFAULT if the tree is
     empty.

 - procedure: rb-tree/min-datum rb-tree default
     Returns the datum associated with the smallest key in RB-TREE, or
     DEFAULT if the tree is empty.

 - procedure: rb-tree/min-pair rb-tree
     Finds the smallest key in RB-TREE and returns a pair containing
     that key and its associated datum.  If the tree is empty, returns
     `#f'.

 - procedure: rb-tree/max rb-tree default
     Returns the largest key in RB-TREE, or DEFAULT if the tree is
     empty.

 - procedure: rb-tree/max-datum rb-tree default
     Returns the datum associated with the largest key in RB-TREE, or
     DEFAULT if the tree is empty.

 - procedure: rb-tree/max-pair rb-tree
     Finds the largest key in RB-TREE and returns a pair containing
     that key and its associated datum.  If the tree is empty, returns
     `#f'.

 - procedure: rb-tree/delete-min! rb-tree default
 - procedure: rb-tree/delete-min-datum! rb-tree default
 - procedure: rb-tree/delete-min-pair! rb-tree
 - procedure: rb-tree/delete-max! rb-tree default
 - procedure: rb-tree/delete-max-datum! rb-tree default
 - procedure: rb-tree/delete-max-pair! rb-tree
     These operations are exactly like the accessors above, in that they
     return information associated with the smallest or largest key,
     except that they simultaneously delete that key.

Weight-Balanced Trees
=====================

   Balanced binary trees are a useful data structure for maintaining
large sets of ordered objects or sets of associations whose keys are
ordered.  MIT Scheme has a comprehensive implementation of
weight-balanced binary trees which has several advantages over the
other data structures for large aggregates:

   * In addition to the usual element-level operations like insertion,
     deletion and lookup, there is a full complement of collection-level
     operations, like set intersection, set union and subset test, all
     of which are implemented with good orders of growth in time and
     space.  This makes weight-balanced trees ideal for rapid
     prototyping of functionally derived specifications.

   * An element in a tree may be indexed by its position under the
     ordering of the keys, and the ordinal position of an element may
     be determined, both with reasonable efficiency.

   * Operations to find and remove minimum element make weight-balanced
     trees simple to use for priority queues.

   * The implementation is _functional_ rather than _imperative_.  This
     means that operations like `inserting' an association in a tree do
     not destroy the old tree, in much the same way that `(+ 1 x)'
     modifies neither the constant 1 nor the value bound to `x'.  The
     trees are referentially transparent thus the programmer need not
     worry about copying the trees.  Referential transparency allows
     space efficiency to be achieved by sharing subtrees.

   These features make weight-balanced trees suitable for a wide range
of applications, especially those that require large numbers of sets or
discrete maps.  Applications that have a few global databases and/or
concentrate on element-level operations like insertion and lookup are
probably better off using hash tables or red-black trees.

   The _size_ of a tree is the number of associations that it contains.
Weight-balanced binary trees are balanced to keep the sizes of the
subtrees of each node within a constant factor of each other.  This
ensures logarithmic times for single-path operations (like lookup and
insertion).  A weight-balanced tree takes space that is proportional to
the number of associations in the tree.  For the current
implementation, the constant of proportionality is six words per
association.

   Weight-balanced trees can be used as an implementation for either
discrete sets or discrete maps (associations).  Sets are implemented by
ignoring the datum that is associated with the key.  Under this scheme
if an association exists in the tree this indicates that the key of the
association is a member of the set.  Typically a value such as `()',
`#t' or `#f' is associated with the key.

   Many operations can be viewed as computing a result that, depending
on whether the tree arguments are thought of as sets or maps, is known
by two different names.  An example is `wt-tree/member?', which, when
regarding the tree argument as a set, computes the set membership
operation, but, when regarding the tree as a discrete map,
`wt-tree/member?' is the predicate testing if the map is defined at an
element in its domain.  Most names in this package have been chosen
based on interpreting the trees as sets, hence the name
`wt-tree/member?' rather than `wt-tree/defined-at?'.

   The weight-balanced tree implementation is a run-time-loadable
option.  To use weight-balanced trees, execute

     (load-option 'wt-tree)

once before calling any of the procedures defined here.

Construction of Weight-Balanced Trees
-------------------------------------

   Binary trees require there to be a total order on the keys used to
arrange the elements in the tree.  Weight-balanced trees are organized
by _types_, where the type is an object encapsulating the ordering
relation.  Creating a tree is a two-stage process.  First a tree type
must be created from the predicate that gives the ordering.  The tree
type is then used for making trees, either empty or singleton trees or
trees from other aggregate structures like association lists.  Once
created, a tree `knows' its type and the type is used to test
compatibility between trees in operations taking two trees.  Usually a
small number of tree types are created at the beginning of a program
and used many times throughout the program's execution.

 - procedure: make-wt-tree-type key<?
     This procedure creates and returns a new tree type based on the
     ordering predicate KEY<?.  KEY<? must be a total ordering, having
     the property that for all key values `a', `b' and `c':

          (key<? a a)                         => #f
          (and (key<? a b) (key<? b a))       => #f
          (if (and (key<? a b) (key<? b c))
              (key<? a c)
              #t)                             => #t

     Two key values are assumed to be equal if neither is less than the
     other by KEY<?.

     Each call to `make-wt-tree-type' returns a distinct value, and
     trees are only compatible if their tree types are `eq?'.  A
     consequence is that trees that are intended to be used in
     binary-tree operations must all be created with a tree type
     originating from the same call to `make-wt-tree-type'.

 - variable: number-wt-type
     A standard tree type for trees with numeric keys.  `Number-wt-type'
     could have been defined by

          (define number-wt-type (make-wt-tree-type  <))

 - variable: string-wt-type
     A standard tree type for trees with string keys.  `String-wt-type'
     could have been defined by

          (define string-wt-type (make-wt-tree-type  string<?))

 - procedure: make-wt-tree wt-tree-type
     This procedure creates and returns a newly allocated
     weight-balanced tree.  The tree is empty, i.e. it contains no
     associations.  WT-TREE-TYPE is a weight-balanced tree type
     obtained by calling `make-wt-tree-type'; the returned tree has
     this type.

 - procedure: singleton-wt-tree wt-tree-type key datum
     This procedure creates and returns a newly allocated
     weight-balanced tree.  The tree contains a single association,
     that of DATUM with KEY.  WT-TREE-TYPE is a weight-balanced tree
     type obtained by calling `make-wt-tree-type'; the returned tree
     has this type.

 - procedure: alist->wt-tree tree-type alist
     Returns a newly allocated weight-balanced tree that contains the
     same associations as ALIST.  This procedure is equivalent to:

          (lambda (type alist)
            (let ((tree (make-wt-tree type)))
              (for-each (lambda (association)
                          (wt-tree/add! tree
                                        (car association)
                                        (cdr association)))
                        alist)
              tree))

Basic Operations on Weight-Balanced Trees
-----------------------------------------

   This section describes the basic tree operations on weight-balanced
trees.  These operations are the usual tree operations for insertion,
deletion and lookup, some predicates and a procedure for determining the
number of associations in a tree.

 - procedure: wt-tree? object
     Returns `#t' if OBJECT is a weight-balanced tree, otherwise
     returns `#f'.

 - procedure: wt-tree/empty? wt-tree
     Returns `#t' if WT-TREE contains no associations, otherwise
     returns `#f'.

 - procedure: wt-tree/size wt-tree
     Returns the number of associations in WT-TREE, an exact
     non-negative integer.  This operation takes constant time.

 - procedure: wt-tree/add wt-tree key datum
     Returns a new tree containing all the associations in WT-TREE and
     the association of DATUM with KEY.  If WT-TREE already had an
     association for KEY, the new association overrides the old.  The
     average and worst-case times required by this operation are
     proportional to the logarithm of the number of associations in
     WT-TREE.

 - procedure: wt-tree/add! wt-tree key datum
     Associates DATUM with KEY in WT-TREE and returns an unspecified
     value.  If WT-TREE already has an association for KEY, that
     association is replaced.  The average and worst-case times
     required by this operation are proportional to the logarithm of
     the number of associations in WT-TREE.

 - procedure: wt-tree/member? key wt-tree
     Returns `#t' if WT-TREE contains an association for KEY, otherwise
     returns `#f'.  The average and worst-case times required by this
     operation are proportional to the logarithm of the number of
     associations in WT-TREE.

 - procedure: wt-tree/lookup wt-tree key default
     Returns the datum associated with KEY in WT-TREE.  If WT-TREE
     doesn't contain an association for KEY, DEFAULT is returned.  The
     average and worst-case times required by this operation are
     proportional to the logarithm of the number of associations in
     WT-TREE.

 - procedure: wt-tree/delete wt-tree key
     Returns a new tree containing all the associations in WT-TREE,
     except that if WT-TREE contains an association for KEY, it is
     removed from the result.  The average and worst-case times required
     by this operation are proportional to the logarithm of the number
     of associations in WT-TREE.

 - procedure: wt-tree/delete! wt-tree key
     If WT-TREE contains an association for KEY the association is
     removed.  Returns an unspecified value.  The average and worst-case
     times required by this operation are proportional to the logarithm
     of the number of associations in WT-TREE.

Advanced Operations on Weight-Balanced Trees
--------------------------------------------

   In the following the _size_ of a tree is the number of associations
that the tree contains, and a _smaller_ tree contains fewer
associations.

 - procedure: wt-tree/split< wt-tree bound
     Returns a new tree containing all and only the associations in
     WT-TREE that have a key that is less than BOUND in the ordering
     relation of the tree type of WT-TREE.  The average and worst-case
     times required by this operation are proportional to the logarithm
     of the size of WT-TREE.

 - procedure: wt-tree/split> wt-tree bound
     Returns a new tree containing all and only the associations in
     WT-TREE that have a key that is greater than BOUND in the ordering
     relation of the tree type of WT-TREE.  The average and worst-case
     times required by this operation are proportional to the logarithm
     of the size of WT-TREE.

 - procedure: wt-tree/union wt-tree-1 wt-tree-2
     Returns a new tree containing all the associations from both trees.
     This operation is asymmetric: when both trees have an association
     for the same key, the returned tree associates the datum from
     WT-TREE-2 with the key.  Thus if the trees are viewed as discrete
     maps then `wt-tree/union' computes the map override of WT-TREE-1 by
     WT-TREE-2.  If the trees are viewed as sets the result is the set
     union of the arguments.  The worst-case time required by this
     operation is proportional to the sum of the sizes of both trees.
     If the minimum key of one tree is greater than the maximum key of
     the other tree then the worst-case time required is proportional to
     the logarithm of the size of the larger tree.

 - procedure: wt-tree/intersection wt-tree-1 wt-tree-2
     Returns a new tree containing all and only those associations from
     WT-TREE-1 that have keys appearing as the key of an association in
     WT-TREE-2.  Thus the associated data in the result are those from
     WT-TREE-1.  If the trees are being used as sets the result is the
     set intersection of the arguments.  As a discrete map operation,
     `wt-tree/intersection' computes the domain restriction of
     WT-TREE-1 to (the domain of) WT-TREE-2.  The worst-case time
     required by this operation is proportional to the sum of the sizes
     of the trees.

 - procedure: wt-tree/difference wt-tree-1 wt-tree-2
     Returns a new tree containing all and only those associations from
     WT-TREE-1 that have keys that _do not_ appear as the key of an
     association in WT-TREE-2.  If the trees are viewed as sets the
     result is the asymmetric set difference of the arguments.  As a
     discrete map operation, it computes the domain restriction of
     WT-TREE-1 to the complement of (the domain of) WT-TREE-2.  The
     worst-case time required by this operation is proportional to the
     sum of the sizes of the trees.

 - procedure: wt-tree/subset? wt-tree-1 wt-tree-2
     Returns `#t' iff the key of each association in WT-TREE-1 is the
     key of some association in WT-TREE-2, otherwise returns `#f'.
     Viewed as a set operation, `wt-tree/subset?' is the improper subset
     predicate.  A proper subset predicate can be constructed:

          (define (proper-subset? s1 s2)
            (and (wt-tree/subset? s1 s2)
                 (< (wt-tree/size s1) (wt-tree/size s2))))

     As a discrete map operation, `wt-tree/subset?' is the subset test
     on the domain(s) of the map(s).  In the worst-case the time
     required by this operation is proportional to the size of
     WT-TREE-1.

 - procedure: wt-tree/set-equal? wt-tree-1 wt-tree-2
     Returns `#t' iff for every association in WT-TREE-1 there is an
     association in WT-TREE-2 that has the same key, and _vice versa_.

     Viewing the arguments as sets, `wt-tree/set-equal?' is the set
     equality predicate.  As a map operation it determines if two maps
     are defined on the same domain.

     This procedure is equivalent to

          (lambda (wt-tree-1 wt-tree-2)
            (and (wt-tree/subset? wt-tree-1 wt-tree-2
                 (wt-tree/subset? wt-tree-2 wt-tree-1)))

     In the worst case the time required by this operation is
     proportional to the size of the smaller tree.

 - procedure: wt-tree/fold combiner initial wt-tree
     This procedure reduces WT-TREE by combining all the associations,
     using an reverse in-order traversal, so the associations are
     visited in reverse order.  COMBINER is a procedure of three
     arguments: a key, a datum and the accumulated result so far.
     Provided COMBINER takes time bounded by a constant, `wt-tree/fold'
     takes time proportional to the size of WT-TREE.

     A sorted association list can be derived simply:

          (wt-tree/fold (lambda (key datum list)
                          (cons (cons key datum) list))
                        '()
                        WT-TREE))

     The data in the associations can be summed like this:

          (wt-tree/fold (lambda (key datum sum) (+ sum datum))
                        0
                        WT-TREE)

 - procedure: wt-tree/for-each action wt-tree
     This procedure traverses WT-TREE in order, applying ACTION to each
     association.  The associations are processed in increasing order
     of their keys.  ACTION is a procedure of two arguments that takes
     the key and datum respectively of the association.  Provided
     ACTION takes time bounded by a constant, `wt-tree/for-each' takes
     time proportional to the size of WT-TREE.  The example prints the
     tree:

          (wt-tree/for-each (lambda (key value)
                              (display (list key value)))
                            WT-TREE))

 - procedure: wt-tree/union-merge wt-tree-1 wt-tree-2 merge
     Returns a new tree containing all the associations from both
     trees.  If both trees have an association for the same key, the
     datum associated with that key in the result tree is computed by
     applying the procedure MERGE to the key, the value from WT-TREE-1
     and the value from WT-TREE-2.  MERGE is of the form

          (lambda (KEY DATUM-1 DATUM-2) ...)

     If some key occurs only in one tree, that association will appear
     in the result tree without being processed by MERGE, so for this
     operation to make sense, either MERGE must have both a right and
     left identity that correspond to the association being absent in
     one of the trees, or some guarantee must be made, for example, all
     the keys in one tree are known to occur in the other.

     These are all reasonable procedures for MERGE

          (lambda (key val1 val2) (+ val1 val2))
          (lambda (key val1 val2) (append val1 val2))
          (lambda (key val1 val2) (wt-tree/union val1 val2))

     However, a procedure like

          (lambda (key val1 val2) (- val1 val2))

     would result in a subtraction of the data for all associations
     with keys occuring in both trees but associations with keys
     occuring in only the second tree would be copied, not negated, as
     is presumably be intent.  The programmer might ensure that this
     never happens.

     This procedure has the same time behavior as `wt-tree/union' but
     with a slightly worse constant factor.  Indeed, `wt-tree/union'
     might have been defined like this:

          (define (wt-tree/union tree1 tree2)
            (wt-tree/union-merge tree1 tree2
                                 (lambda (key val1 val2) val2)))

   The MERGE procedure takes the KEY as a parameter in case the data
are not independent of the key.

Indexing Operations on Weight-Balanced Trees
--------------------------------------------

   Weight-balanced trees support operations that view the tree as sorted
sequence of associations.  Elements of the sequence can be accessed by
position, and the position of an element in the sequence can be
determined, both in logarthmic time.

 - procedure: wt-tree/index wt-tree index
 - procedure: wt-tree/index-datum wt-tree index
 - procedure: wt-tree/index-pair wt-tree index
     Returns the 0-based INDEXth association of WT-TREE in the sorted
     sequence under the tree's ordering relation on the keys.
     `wt-tree/index' returns the INDEXth key, `wt-tree/index-datum'
     returns the datum associated with the INDEXth key and
     `wt-tree/index-pair' returns a new pair `(KEY . DATUM)' which is
     the `cons' of the INDEXth key and its datum.  The average and
     worst-case times required by this operation are proportional to
     the logarithm of the number of associations in the tree.

     These operations signal a condition of type
     `condition-type:bad-range-argument' if INDEX`<0' or if INDEX is
     greater than or equal to the number of associations in the tree.
     If the tree is empty, they signal an anonymous error.

     Indexing can be used to find the median and maximum keys in the
     tree as follows:

          median:   (wt-tree/index WT-TREE
                                   (quotient (wt-tree/size WT-TREE)
                                             2))
          maximum:  (wt-tree/index WT-TREE
                                   (- (wt-tree/size WT-TREE)
                                      1))

 - procedure: wt-tree/rank wt-tree key
     Determines the 0-based position of KEY in the sorted sequence of
     the keys under the tree's ordering relation, or `#f' if the tree
     has no association with for KEY.  This procedure returns either an
     exact non-negative integer or `#f'.  The average and worst-case
     times required by this operation are proportional to the logarithm
     of the number of associations in the tree.

 - procedure: wt-tree/min wt-tree
 - procedure: wt-tree/min-datum wt-tree
 - procedure: wt-tree/min-pair wt-tree
     Returns the association of WT-TREE that has the least key under
     the tree's ordering relation.  `wt-tree/min' returns the least key,
     `wt-tree/min-datum' returns the datum associated with the least
     key and `wt-tree/min-pair' returns a new pair `(key . datum)'
     which is the `cons' of the minimum key and its datum.  The average
     and worst-case times required by this operation are proportional
     to the logarithm of the number of associations in the tree.

     These operations signal an error if the tree is empty.  They could
     have been written

          (define (wt-tree/min tree)
            (wt-tree/index tree 0))
          (define (wt-tree/min-datum tree)
            (wt-tree/index-datum tree 0))
          (define (wt-tree/min-pair tree)
            (wt-tree/index-pair tree 0))

 - procedure: wt-tree/delete-min wt-tree
     Returns a new tree containing all of the associations in WT-TREE
     except the association with the least key under the WT-TREE's
     ordering relation.  An error is signalled if the tree is empty.
     The average and worst-case times required by this operation are
     proportional to the logarithm of the number of associations in the
     tree.  This operation is equivalent to

          (wt-tree/delete WT-TREE (wt-tree/min WT-TREE))

 - procedure: wt-tree/delete-min! wt-tree
     Removes the association with the least key under the WT-TREE's
     ordering relation.  An error is signalled if the tree is empty.
     The average and worst-case times required by this operation are
     proportional to the logarithm of the number of associations in the
     tree.  This operation is equivalent to

          (wt-tree/delete! WT-TREE (wt-tree/min WT-TREE))

Procedures
**********

   Procedures are created by evaluating `lambda' expressions (see
Lambda Expressions); the `lambda' may either be explicit or may be
implicit as in a "procedure `define'" (see Definitions).  Also
there are special built-in procedures, called "primitive procedures",
such as `car'; these procedures are not written in Scheme but in the
language used to implement the Scheme system.  MIT Scheme also provides
"application hooks", which support the construction of data structures
that act like procedures.

   In MIT Scheme, the written representation of a procedure tells you
the type of the procedure (compiled, interpreted, or primitive):

     pp
          =>  #[compiled-procedure 56 ("pp" #x2) #x10 #x307578]
     (lambda (x) x)
          =>  #[compound-procedure 57]
     (define (foo x) x)
     foo
          =>  #[compound-procedure 58 foo]
     car
          =>  #[primitive-procedure car]
     (call-with-current-continuation (lambda (x) x))
          =>  #[continuation 59]

Note that interpreted procedures are called "compound" procedures
(strictly speaking, compiled procedures are also compound procedures).
The written representation makes this distinction for historical
reasons, and may eventually change.

Procedure Operations
====================

 - procedure: apply procedure object object ...
     Calls PROCEDURE with the elements of the following list as
     arguments:

          (cons* OBJECT OBJECT ...)

     The initial OBJECTs may be any objects, but the last OBJECT (there
     must be at least one OBJECT) must be a list.

          (apply + (list 3 4 5 6))                =>  18
          (apply + 3 4 '(5 6))                    =>  18

          (define compose
            (lambda (f g)
              (lambda args
                (f (apply g args)))))
          ((compose sqrt *) 12 75)                =>  30

 - procedure: procedure? object
     Returns `#t' if OBJECT is a procedure; otherwise returns `#f'.  If
     `#t' is returned, exactly one of the following predicates is
     satisfied by OBJECT: `compiled-procedure?', `compound-procedure?',
     or `primitive-procedure?'.

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

 - procedure: compound-procedure? object
     Returns `#t' if OBJECT is a compound (i.e. interpreted) procedure;
     otherwise returns `#f'.

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

   The following two procedures test the "arity" of a procedure, that
is, the number of arguments that the procedure accepts.  The results of
the test may be less restrictive than the effect of calling the
procedure.  In other words, these procedures may indicate that the
procedure will accept a given number of arguments, but if you call the
procedure it may signal a `condition-type:wrong-number-of-arguments'
error.  This is because these procedures examine the apparent arity of
a procedure.  For example, here is a procedure that appears to accept
any number of arguments, but when called will signal an error if the
number of arguments is not one:

     (lambda arguments (apply car arguments))

 - procedure: procedure-arity-valid? procedure k
     Returns `#t' if PROCEDURE accepts K arguments; otherwise returns
     `#f'.

 - procedure: procedure-arity procedure
     Returns a description of the number of arguments that PROCEDURE
     accepts.  The result is a newly allocated pair whose car field is
     the minimum number of arguments, and whose cdr field is the maximum
     number of arguments.  The minimum is an exact non-negative
     integer.  The maximum is either an exact non-negative integer, or
     `#f' meaning that the procedure has no maximum number of arguments.

          (procedure-arity (lambda () 3))         =>  (0 . 0)
          (procedure-arity (lambda (x) x))        =>  (1 . 1)
          (procedure-arity car)                   =>  (1 . 1)
          (procedure-arity (lambda x x))          =>  (0 . #f)
          (procedure-arity (lambda (x . y) x))    =>  (1 . #f)
          (procedure-arity (lambda (x #!optional y) x))
                                                  =>  (1 . 2)

 - procedure: procedure-environment procedure
     Returns the closing environment of PROCEDURE.  Signals an error if
     PROCEDURE is a primitive procedure, or if PROCEDURE is a compiled
     procedure for which the debugging information is unavailable.

Primitive Procedures
====================

 - procedure: make-primitive-procedure name [arity]
     NAME must be a symbol.  ARITY must be an exact non-negative
     integer, `-1', `#f', or `#t'; if not supplied it defaults to `#f'.
     Returns the primitive procedure called NAME.  May perform further
     actions depending on ARITY:

    `#f'
          If the primitive procedure is not implemented, signals an
          error.

    `#t'
          If the primitive procedure is not implemented, returns `#f'.

    integer
          If the primitive procedure is implemented, signals an error
          if its arity is not equal to ARITY.  If the primitive
          procedure is not implemented, returns an unimplemented
          primitive procedure object that accepts ARITY arguments.  An
          ARITY of `-1' means it accepts any number of arguments.

 - procedure: primitive-procedure-name primitive-procedure
     Returns the name of PRIMITIVE-PROCEDURE, a symbol.

          (primitive-procedure-name car)          =>  car

 - procedure: implemented-primitive-procedure? primitive-procedure
     Returns `#t' if PRIMITIVE-PROCEDURE is implemented; otherwise
     returns `#f'.  Useful because the code that implements a particular
     primitive procedure is not necessarily linked into the executable
     Scheme program.

Continuations
=============

 - procedure: call-with-current-continuation procedure
     PROCEDURE must be a procedure of one argument.  Packages up the
     current continuation (see below) as an "escape procedure" and
     passes it as an argument to PROCEDURE.  The escape procedure is a
     Scheme procedure of one argument that, if it is later passed a
     value, will ignore whatever continuation is in effect at that
     later time and will give the value instead to the continuation
     that was in effect when the escape procedure was created.  The
     escape procedure created by `call-with-current-continuation' has
     unlimited extent just like any other procedure in Scheme.  It may
     be stored in variables or data structures and may be called as
     many times as desired.

     The following examples show only the most common uses of this
     procedure.  If all real programs were as simple as these examples,
     there would be no need for a procedure with the power of
     `call-with-current-continuation'.

          (call-with-current-continuation
            (lambda (exit)
              (for-each (lambda (x)
                          (if (negative? x)
                              (exit x)))
                        '(54 0 37 -3 245 19))
              #t))                                =>  -3

          (define list-length
            (lambda (obj)
              (call-with-current-continuation
                (lambda (return)
                  (letrec ((r
                            (lambda (obj)
                              (cond ((null? obj) 0)
                                    ((pair? obj) (+ (r (cdr obj)) 1))
                                    (else (return #f))))))
                    (r obj))))))
          (list-length '(1 2 3 4))                =>  4
          (list-length '(a b . c))                =>  #f

     A common use of `call-with-current-continuation' is for structured,
     non-local exits from loops or procedure bodies, but in fact
     `call-with-current-continuation' is quite useful for implementing a
     wide variety of advanced control structures.

     Whenever a Scheme expression is evaluated a continuation exists
     that wants the result of the expression.  The continuation
     represents an entire (default) future for the computation.  If the
     expression is evaluated at top level, for example, the
     continuation will take the result, print it on the screen, prompt
     for the next input, evaluate it, and so on forever.  Most of the
     time the continuation includes actions specified by user code, as
     in a continuation that will take the result, multiply it by the
     value stored in a local variable, add seven, and give the answer
     to the top-level continuation to be printed.  Normally these
     ubiquitous continuations are hidden behind the scenes and
     programmers don't think much about them.  On the rare occasions
     that you may need to deal explicitly with continuations,
     `call-with-current-continuation' lets you do so by creating a
     procedure that acts just like the current continuation.

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

 - procedure: within-continuation continuation thunk
     THUNK must be a procedure of no arguments.  Conceptually,
     `within-continuation' invokes CONTINUATION on the result of
     invoking THUNK, but THUNK is executed in the dynamic context of
     CONTINUATION.  In other words, the "current" continuation is
     abandoned before THUNK is invoked.

 - procedure: dynamic-wind before thunk after
     Calls THUNK without arguments, returning the result(s) of this
     call.  BEFORE and AFTER are called, also without arguments, as
     required by the following rules (note that in the absence of calls
     to continuations captured using `call-with-current-continuation'
     the three arguments are called once each, in order).  BEFORE is
     called whenever execution enters the dynamic extent of the call to
     THUNK and AFTER is called whenever it exits that dynamic extent.
     The dynamic extent of a procedure call is the period between when
     the call is initiated and when it returns.  In Scheme, because of
     `call-with-current-continuation', the dynamic extent of a call may
     not be a single, connected time period.  It is defined as follows:

        * The dynamic extent is entered when execution of the body of
          the called procedure begins.

        * The dynamic extent is also entered when execution is not
          within the dynamic extent and a continuation is invoked that
          was captured (using `call-with-current-continuation') during
          the dynamic extent.

        * It is exited when the called procedure returns.

        * It is also exited when execution is within the dynamic extent
          and a continuation is invoked that was captured while not
          within the dynamic extent.

     If a second call to `dynamic-wind' occurs within the dynamic extent
     of the call to THUNK and then a continuation is invoked in such a
     way that the AFTERs from these two invocations of `dynamic-wind'
     are both to be called, then the AFTER associated with the second
     (inner) call to `dynamic-wind' is called first.

     If a second call to `dynamic-wind' occurs within the dynamic extent
     of the call to THUNK and then a continuation is invoked in such a
     way that the BEFOREs from these two invocations of `dynamic-wind'
     are both to be called, then the BEFORE associated with the first
     (outer) call to `dynamic-wind' is called first.

     If invoking a continuation requires calling the BEFORE from one
     call to `dynamic-wind' and the AFTER from another, then the AFTER
     is called first.

     The effect of using a captured continuation to enter or exit the
     dynamic extent of a call to BEFORE or AFTER is undefined.

          (let ((path '())
                (c #f))
            (let ((add (lambda (s)
                         (set! path (cons s path)))))
              (dynamic-wind
                (lambda () (add 'connect))
                (lambda ()
                  (add (call-with-current-continuation
                         (lambda (c0)
                           (set! c c0)
                           'talk1))))
                (lambda () (add 'disconnect)))
              (if (< (length path) 4)
                  (c 'talk2)
                  (reverse path))))

          => (connect talk1 disconnect connect talk2 disconnect)

   The following two procedures support multiple values.

 - procedure: call-with-values thunk procedure
     THUNK must be a procedure of no arguments, and PROCEDURE must be a
     procedure.  THUNK is invoked with a continuation that expects to
     receive multiple values; specifically, the continuation expects to
     receive the same number of values that PROCEDURE accepts as
     arguments.  THUNK must return multiple values using the `values'
     procedure.  Then PROCEDURE is called with the multiple values as
     its arguments.  The result yielded by PROCEDURE is returned as the
     result of `call-with-values'.

 - procedure: values object ...
     Returns multiple values.  The continuation in effect when this
     procedure is called must be a multiple-value continuation that was
     created by `call-with-values'.  Furthermore it must accept as many
     values as there are OBJECTs.

Application Hooks
=================

   "Application hooks" are objects that can be applied like procedures.
Each application hook has two parts: a "procedure" that specifies what
to do when the application hook is applied, and an arbitrary object,
called "extra".  Often the procedure uses the extra object to determine
what to do.

   There are two kinds of application hooks, which differ in what
arguments are passed to the procedure.  When an "apply hook" is
applied, the procedure is passed exactly the same arguments that were
passed to the apply hook.  When an "entity" is applied, the entity
itself is passed as the first argument, followed by the other arguments
that were passed to the entity.

   Both apply hooks and entities satisfy the predicate `procedure?'.
Each satisfies either `compiled-procedure?', `compound-procedure?', or
`primitive-procedure?', depending on its procedure component.  An apply
hook is considered to accept the same number of arguments as its
procedure, while an entity is considered to accept one less argument
than its procedure.

 - procedure: make-apply-hook procedure object
     Returns a newly allocated apply hook with a procedure component of
     PROCEDURE and an extra component of OBJECT.

 - procedure: apply-hook? object
     Returns `#t' if OBJECT is an apply hook; otherwise returns `#f'.

 - procedure: apply-hook-procedure apply-hook
     Returns the procedure component of APPLY-HOOK.

 - procedure: set-apply-hook-procedure! apply-hook procedure
     Changes the procedure component of APPLY-HOOK to be PROCEDURE.
     Returns an unspecified value.

 - procedure: apply-hook-extra apply-hook
     Returns the extra component of APPLY-HOOK.

 - procedure: set-apply-hook-extra! apply-hook object
     Changes the extra component of APPLY-HOOK to be OBJECT.  Returns
     an unspecified value.

 - procedure: make-entity procedure object
     Returns a newly allocated entity with a procedure component of
     PROCEDURE and an extra component of OBJECT.

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

 - procedure: entity-procedure entity
     Returns the procedure component of ENTITY.

 - procedure: set-entity-procedure! entity procedure
     Changes the procedure component of ENTITY to be PROCEDURE.
     Returns an unspecified value.

 - procedure: entity-extra entity
     Returns the extra component of ENTITY.

 - procedure: set-entity-extra! entity object
     Changes the extra component of ENTITY to be OBJECT.  Returns an
     unspecified value.

Environments
************