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

Weak Pairs
==========

   "Weak pairs" are a mechanism for building data structures that point
at objects without protecting them from garbage collection.  The car of
a weak pair holds its pointer weakly, while the cdr holds its pointer in
the normal way.  If the object in the car of a weak pair is not held
normally by any other data structure, it will be garbage-collected.

   Note: weak pairs are _not_ pairs; that is, they do not satisfy the
predicate `pair?'.

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

 - procedure: weak-cons car cdr
     Allocates and returns a new weak pair, with components CAR and
     CDR.  The CAR component is held weakly.

 - procedure: weak-pair/car? weak-pair
     This predicate returns `#f' if the car of WEAK-PAIR has been
     garbage-collected; otherwise returns `#t'.  In other words, it is
     true if WEAK-PAIR has a valid car component.

 - procedure: weak-car weak-pair
     Returns the car component of WEAK-PAIR.  If the car component has
     been garbage-collected, this operation returns `#f', but it can
     also return `#f' if that is the value that was stored in the car.

   Normally, `weak-pair/car?' is used to determine if `weak-car' would
return a valid value.  An obvious way of doing this would be:

     (if (weak-pair/car? x)
         (weak-car x)
         ...)

However, since a garbage collection could occur between the call to
`weak-pair/car?' and `weak-car', this would not always work correctly.
Instead, the following should be used, which always works:

     (or (weak-car x)
         (and (not (weak-pair/car? x))
              ...))

   The reason that the latter expression works is that `weak-car'
returns `#f' in just two instances: when the car component is `#f', and
when the car component has been garbage-collected.  In the former case,
if a garbage collection happens between the two calls, it won't matter,
because `#f' will never be garbage-collected.  And in the latter case,
it also won't matter, because the car component no longer exists and
cannot be affected by the garbage collector.

 - procedure: weak-set-car! weak-pair object
     Sets the car component of WEAK-PAIR to OBJECT and returns an
     unspecified result.

 - procedure: weak-cdr weak-pair
     Returns the cdr component of WEAK-CDR.

 - procedure: weak-set-cdr! weak-pair object
     Sets the cdr component of WEAK-PAIR to OBJECT and returns an
     unspecified result.

Associations
************

   MIT Scheme provides several mechanisms for associating objects with
one another.  Each of these mechanisms creates a link between one or
more objects, called "keys", and some other object, called a "datum".
Beyond this common idea, however, each of the mechanisms has various
different properties that make it appropriate in different situations:

   * "Association lists" are one of Lisp's oldest association
     mechanisms.  Because they are made from ordinary pairs, they are
     easy to build and manipulate, and very flexible in use.  However,
     the average lookup time for an association list is linear in the
     number of associations.

   * "1D tables" have a very simple interface, making them easy to use,
     and offer the feature that they do not prevent their keys from
     being reclaimed by the garbage collector.  Like association lists,
     their average lookup time is linear in the number of associations;
     but 1D tables aren't as flexible.

   * "The association table" is MIT Scheme's equivalent to the
     "property lists" of Lisp.  It has the advantages that the keys may
     be any type of object and that it does not prevent the keys from
     being reclaimed by the garbage collector.  However, two
     linear-time lookups must be performed, one for each key, whereas
     for traditional property lists only one lookup is required for
     both keys.

   * "Hash tables" are a powerful mechanism with constant-time access to
     large amounts of data.  Hash tables are not as flexible as
     association lists, but because their access times are independent
     of the number of associations in the table, for most applications
     they are the mechanism of choice.

   * "Balanced binary trees" are another association mechanism that is
     useful for applications in which the keys are ordered.  Binary
     trees have access times that are proportional to the logarithm of
     the number of associations in the tree.  While they aren't as fast
     as hash tables, they offer the advantage that the contents of the
     tree can be converted to a sorted alist in linear time.
     Additionally, two trees can be compared for equality in worst-case
     linear time.

   * "Red-Black trees" are a kind of balanced binary tree.  The
     implementation supports destructive insertion and deletion
     operations with a good constant factor.

   * "Weight-Balanced trees" are a kind of balanced binary tree.  The
     implementation provides non-destructive operations.  There is a
     comprehensive set of operations, including: a constant-time size
     operation; many high-level operations such as the set operations
     union, intersection and difference; and indexing of elements by
     position.

Association Lists
=================

   An "association list", or "alist", is a data structure used very
frequently in Scheme.  An alist is a list of pairs, each of which is
called an "association".  The car of an association is called the "key".

   An advantage of the alist representation is that an alist can be
incrementally augmented simply by adding new entries to the front.
Moreover, because the searching procedures `assv' et al. search the
alist in order, new entries can "shadow" old entries.  If an alist is
viewed as a mapping from keys to data, then the mapping can be not only
augmented but also altered in a non-destructive manner by adding new
entries to the front of the alist.(1)

 - procedure: alist? object
     Returns `#t' if OBJECT is an association list (including the empty
     list); otherwise returns `#f'.  Any OBJECT satisfying this
     predicate also satisfies `list?'.

 - procedure: assq object alist
 - procedure: assv object alist
 - procedure: assoc object alist
     These procedures find the first pair in ALIST whose car field is
     OBJECT, and return that pair; the returned pair is always an
     _element_ of ALIST, _not_ one of the pairs from which ALIST is
     composed.  If no pair in ALIST has OBJECT as its car, `#f' (n.b.:
     not the empty list) is returned.  `assq' uses `eq?' to compare
     OBJECT with the car fields of the pairs in ALIST, while `assv'
     uses `eqv?' and `assoc' uses `equal?'.(2)

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

 - procedure: association-procedure predicate selector
     Returns an association procedure that is similar to `assv', except
     that SELECTOR (a procedure of one argument) is used to select the
     key from the association, and PREDICATE (an equivalence predicate)
     is used to compare the key to the given item.  This can be used to
     make association lists whose elements are, say, vectors instead of
     pairs (also Searching Lists).

     For example, here is how `assv' could be implemented:

          (define assv (association-procedure eqv? car))

     Another example is a "reverse association" procedure:

          (define rassv (association-procedure eqv? cdr))

 - procedure: del-assq object alist
 - procedure: del-assv object alist
 - procedure: del-assoc object alist
     These procedures return a newly allocated copy of ALIST in which
     all associations with keys equal to OBJECT have been removed.
     Note that while the returned copy is a newly allocated list, the
     association pairs that are the elements of the list are shared with
     ALIST, not copied.  `del-assq' uses `eq?' to compare OBJECT with
     the keys, while `del-assv' uses `eqv?' and `del-assoc' uses
     `equal?'.

          (define a
            '((butcher . "231 e22nd St.")
              (baker . "515 w23rd St.")
              (hardware . "988 Lexington Ave.")))

          (del-assq 'baker a)
               =>
               ((butcher . "231 e22nd St.")
                (hardware . "988 Lexington Ave."))

 - procedure: del-assq! object alist
 - procedure: del-assv! object alist
 - procedure: del-assoc! object alist
     These procedures remove from ALIST all associations with keys
     equal to OBJECT.  They return the resulting list.  `del-assq!'
     uses `eq?' to compare OBJECT with the keys, while `del-assv!' uses
     `eqv?' and `del-assoc!' uses `equal?'.  These procedures are like
     `del-assq', `del-assv', and `del-assoc', respectively, except that
     they destructively modify ALIST.

 - procedure: delete-association-procedure deletor predicate selector
     This returns a deletion procedure similar to `del-assv' or
     `del-assq!'.  The PREDICATE and SELECTOR arguments are the same as
     those for `association-procedure', while the DELETOR argument
     should be either the procedure `list-deletor' (for non-destructive
     deletions), or the procedure `list-deletor!' (for destructive
     deletions).

     For example, here is a possible implementation of `del-assv':

          (define del-assv
            (delete-association-procedure list-deletor eqv? car))

 - procedure: alist-copy alist
     Returns a newly allocated copy of ALIST.  This is similar to
     `list-copy' except that the "association" pairs, i.e. the elements
     of the list ALIST, are also copied.  `alist-copy' could have been
     implemented like this:

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

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

   (1) This introduction is taken from `Common Lisp, The Language',
second edition, p. 431.

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

1D Tables
=========

   "1D tables" ("one-dimensional" tables) are similar to association
lists.  In a 1D table, unlike an association list, the keys of the table
are held "weakly": if a key is garbage-collected, its associated value
in the table is removed.  1D tables compare their keys for equality
using `eq?'.

   1D tables can often be used as a higher-performance alternative to
the two-dimensional association table (see The Association Table).
If one of the keys being associated is a compound object such as a
vector, a 1D table can be stored in one of the vector's slots.  Under
these circumstances, accessing items in a 1D table will be comparable in
performance to using a property list in a conventional Lisp.

 - procedure: make-1d-table
     Returns a newly allocated empty 1D table.

 - procedure: 1d-table? object
     Returns `#t' if OBJECT is a 1D table, otherwise returns `#f'.  Any
     object that satisfies this predicate also satisfies `list?'.

 - procedure: 1d-table/put! 1d-table key datum
     Creates an association between KEY and DATUM in 1D-TABLE.  Returns
     an unspecified value.

 - procedure: 1d-table/remove! 1d-table key
     Removes any association for KEY in 1D-TABLE and returns an
     unspecified value.

 - procedure: 1d-table/get 1d-table key default
     Returns the DATUM associated with KEY in 1D-TABLE.  If there is no
     association for KEY, DEFAULT is returned.

 - procedure: 1d-table/lookup 1d-table key if-found if-not-found
     IF-FOUND must be a procedure of one argument, and IF-NOT-FOUND
     must be a procedure of no arguments.  If 1D-TABLE contains an
     association for KEY, IF-FOUND is invoked on the DATUM of the
     association.  Otherwise, IF-NOT-FOUND is invoked with no
     arguments.  In either case, the result of the invoked procedure is
     returned as the result of `1d-table/lookup'.

 - procedure: 1d-table/alist 1d-table
     Returns a newly allocated association list that contains the same
     information as 1D-TABLE.

The Association Table
=====================

   MIT Scheme provides a generalization of the property-list mechanism
found in most other implementations of Lisp: a global two-dimensional
"association table".  This table is indexed by two keys, called X-KEY
and Y-KEY in the following procedure descriptions.  These keys and the
datum associated with them can be arbitrary objects.  `eq?' is used to
discriminate keys.

   Think of the association table as a matrix: a single datum can be
accessed using both keys, a column using X-KEY only, and a row using
Y-KEY only.

 - procedure: 2d-put! x-key y-key datum
     Makes an entry in the association table that associates DATUM with
     X-KEY and Y-KEY.  Returns an unspecified result.

 - procedure: 2d-remove! x-key y-key
     If the association table has an entry for X-KEY and Y-KEY, it is
     removed.  Returns an unspecified result.

 - procedure: 2d-get x-key y-key
     Returns the DATUM associated with X-KEY and Y-KEY.  Returns `#f'
     if no such association exists.

 - procedure: 2d-get-alist-x x-key
     Returns an association list of all entries in the association
     table that are associated with X-KEY.  The result is a list of
     `(Y-KEY . DATUM)' pairs.  Returns the empty list if no entries for
     X-KEY exist.

          (2d-put! 'foo 'bar 5)
          (2d-put! 'foo 'baz 6)
          (2d-get-alist-x 'foo)           =>  ((baz . 6) (bar . 5))

 - procedure: 2d-get-alist-y y-key
     Returns an association list of all entries in the association
     table that are associated with Y-KEY.  The result is a list of
     `(X-KEY . DATUM)' pairs.  Returns the empty list if no entries for
     Y-KEY exist.

          (2d-put! 'bar 'foo 5)
          (2d-put! 'baz 'foo 6)
          (2d-get-alist-y 'foo)           =>  ((baz . 6) (bar . 5))

Hash Tables
===========

   Hash tables are a fast, powerful mechanism for storing large numbers
of associations.  MIT Scheme's hash tables feature automatic resizing,
customizable growth parameters, and customizable hash procedures.

   The average times for the insertion, deletion, and lookup operations
on a hash table are bounded by a constant.  The space required by the
table is proportional to the number of associations in the table; the
constant of proportionality is described below (see Resizing of Hash Tables).

   (Previously, the hash-table implementation was a run-time-loadable
option, but as of release 7.7.0 it is loaded by default.  It's no longer
necessary to call `load-option' prior to using hash tables.)

Construction of Hash Tables
---------------------------

   The next few procedures are hash-table constructors.  All hash table
constructors are procedures that accept one optional argument,
INITIAL-SIZE, and return a newly allocated hash table.  If INITIAL-SIZE
is given, it must be an exact non-negative integer or `#f'.  The
meaning of INITIAL-SIZE is discussed below (see Resizing of Hash Tables).

   Hash tables are normally characterized by two things: the equivalence
predicate that is used to compare keys, and whether or not the table
allows its keys to be reclaimed by the garbage collector.  If a table
prevents its keys from being reclaimed by the garbage collector, it is
said to hold its keys "strongly"; otherwise it holds its keys "weakly"
(see Weak Pairs).

 - procedure: make-eq-hash-table [initial-size]
     Returns a newly allocated hash table that accepts arbitrary
     objects as keys, and compares those keys with `eq?'.  The keys are
     held weakly.  These are the fastest of the standard hash tables.

 - procedure: make-eqv-hash-table [initial-size]
     Returns a newly allocated hash table that accepts arbitrary
     objects as keys, and compares those keys with `eqv?'.  The keys
     are held weakly, except that booleans, characters, and numbers are
     held strongly.  These hash tables are a little slower than those
     made by `make-eq-hash-table'.

 - procedure: make-equal-hash-table [initial-size]
     Returns a newly allocated hash table that accepts arbitrary
     objects as keys, and compares those keys with `equal?'.  The keys
     are held strongly.  These hash tables are quite a bit slower than
     those made by `make-eq-hash-table'.

 - procedure: make-string-hash-table [initial-size]
     Returns a newly allocated hash table that accepts character
     strings as keys, and compares them with `string=?'.  The keys are
     held strongly.

   The next two procedures are used to create new hash-table
constructors.  All of the above hash table constructors, with the
exception of `make-eqv-hash-table', could have been created by calls to
these "constructor-constructors"; see the examples below.

 - procedure: strong-hash-table/constructor key-hash key=?
          [rehash-after-gc?]
 - procedure: weak-hash-table/constructor key-hash key=?
          [rehash-after-gc?]
     Each of these procedures accepts two arguments and returns a
     hash-table constructor.  The KEY=? argument is an equivalence
     predicate for the keys of the hash table.  The KEY-HASH argument
     is a procedure that computes a hash number.  Specifically,
     KEY-HASH accepts two arguments, a key and an exact positive
     integer (the "modulus"), and returns an exact non-negative integer
     that is less than the modulus.

     The optional argument REHASH-AFTER-GC?, if true, says that the
     values returned by KEY-HASH might change after a garbage
     collection.  If so, the hash-table implementation arranges for the
     table to be rehashed when necessary.  (see Address Hashing, for
     information about hash procedures that have this property.)
     Otherwise, it is assumed that KEY-HASH always returns the same
     value for the same arguments.  The default value of this argument
     is `#f'.

     The constructors returned by `strong-hash-table/constructor' make
     hash tables that hold their keys strongly.  The constructors
     returned by `weak-hash-table/constructor' make hash tables that
     hold their keys weakly.

   Some examples showing how some standard hash-table constructors
could have been defined:

     (define make-eq-hash-table
       (weak-hash-table/constructor eq-hash-mod eq? #t))

     (define make-equal-hash-table
       (strong-hash-table/constructor equal-hash-mod equal? #t))

     (define make-string-hash-table
       (strong-hash-table/constructor string-hash-mod string=? #f))

   The following procedure is sometimes useful in conjunction with weak
hash tables.  Normally it is not needed, because such hash tables clean
themselves automatically as they are used.

 - procedure: hash-table/clean! hash-table
     If HASH-TABLE is a type of hash table that holds its KEYs weakly,
     this procedure recovers any space that was being used to record
     associations for objects that have been reclaimed by the garbage
     collector.  Otherwise, this procedure does nothing.  In either
     case, it returns an unspecified result.

Basic Hash Table Operations
---------------------------

   The procedures described in this section are the basic operations on
hash tables.  They provide the functionality most often needed by
programmers.  Subsequent sections describe other operations that provide
additional functionality needed by some applications.

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

 - procedure: hash-table/put! hash-table key datum
     Associates DATUM with KEY in HASH-TABLE and returns an unspecified
     result.  The average time required by this operation is bounded by
     a constant.

 - procedure: hash-table/get hash-table key default
     Returns the datum associated with KEY in HASH-TABLE.  If there is
     no association for KEY, DEFAULT is returned.  The average time
     required by this operation is bounded by a constant.

 - procedure: hash-table/remove! hash-table key
     If HASH-TABLE has an association for KEY, removes it.  Returns an
     unspecified result.  The average time required by this operation
     is bounded by a constant.

 - procedure: hash-table/clear! hash-table
     Removes all associations in HASH-TABLE and returns an unspecified
     result.  The average and worst-case times required by this
     operation are bounded by a constant.

 - procedure: hash-table/count hash-table
     Returns the number of associations in HASH-TABLE as an exact
     non-negative integer.  If HASH-TABLE holds its keys weakly, this
     is a conservative upper bound that may count some associations
     whose keys have recently been reclaimed by the garbage collector.
     The average and worst-case times required by this operation are
     bounded by a constant.

 - procedure: hash-table->alist hash-table
     Returns the contents of HASH-TABLE as a newly allocated alist.
     Each element of the alist is a pair `(KEY . DATUM)' where KEY is
     one of the keys of HASH-TABLE, and DATUM is its associated datum.
     The average and worst-case times required by this operation are
     linear in the number of associations in the table.

 - procedure: hash-table/key-list hash-table
     Returns a newly allocated list of the keys in HASH-TABLE.  The
     average and worst-case times required by this operation are linear
     in the number of associations in the table.

 - procedure: hash-table/datum-list hash-table
     Returns a newly allocated list of the datums in HASH-TABLE.  Each
     element of the list corresponds to one of the associations in
     HASH-TABLE; if the table contains multiple associations with the
     same datum, so will this list.  The average and worst-case times
     required by this operation are linear in the number of
     associations in the table.

 - procedure: hash-table/for-each hash-table procedure
     PROCEDURE must be a procedure of two arguments.  Invokes PROCEDURE
     once for each association in HASH-TABLE, passing the association's
     KEY and DATUM as arguments, in that order.  Returns an unspecified
     result.  PROCEDURE must not modify HASH-TABLE, with one exception:
     it is permitted to call `hash-table/remove!' to remove the
     association being processed.

   The following procedure is an alternate form of `hash-table/get'
that is useful in some situations.  Usually, `hash-table/get' is
preferable because it is faster.

 - procedure: hash-table/lookup hash-table key if-found if-not-found
     IF-FOUND must be a procedure of one argument, and IF-NOT-FOUND
     must be a procedure of no arguments.  If HASH-TABLE contains an
     association for KEY, IF-FOUND is invoked on the datum of the
     association.  Otherwise, IF-NOT-FOUND is invoked with no
     arguments.  In either case, the result yielded by the invoked
     procedure is returned as the result of `hash-table/lookup'
     (`hash-table/lookup' _reduces_ into the invoked procedure, i.e.
     calls it tail-recursively).  The average time required by this
     operation is bounded by a constant.

Resizing of Hash Tables
-----------------------

   Normally, hash tables automatically resize themselves according to
need.  Because of this, the programmer need not be concerned with
management of the table's size.  However, some limited control over the
table's size is provided, which will be discussed below.  This
discussion involves two concepts, "usable size" and "physical size",
which we will now define.

   The "usable size" of a hash table is the number of associations that
the table can hold at a given time.  If the number of associations in
the table exceeds the usable size, the table will automatically grow,
increasing the usable size to a new value that is sufficient to hold the
associations.

   The "physical size" is an abstract measure of a hash table that
specifies how much space is allocated to hold the associations of the
table.  The physical size is always greater than or equal to the usable
size.  The physical size is not interesting in itself; it is interesting
only for its effect on the performance of the hash table.  While the
average performance of a hash-table lookup is bounded by a constant, the
worst-case performance is not.  For a table containing a given number of
associations, increasing the physical size of the table decreases the
probability that worse-than-average performance will occur.

   The physical size of a hash table is statistically related to the
number of associations.  However, it is possible to place bounds on the
physical size, and from this to estimate the amount of space used by the
table:

     (define (hash-table-space-bounds count rehash-size rehash-threshold)
       (let ((tf (/ 1 rehash-threshold)))
         (values (if (exact-integer? rehash-size)
                     (- (* count (+ 4 tf))
                        (* tf (+ rehash-size rehash-size)))
                     (* count (+ 4 (/ tf (* rehash-size rehash-size)))))
                 (* count (+ 4 tf)))))

What this formula shows is that, for a "normal" rehash size (that is,
not an exact integer), the amount of space used by the hash table is
proportional to the number of associations in the table.  The constant
of proportionality varies statistically, with the low bound being

     (+ 4 (/ (/ 1 rehash-threshold) (* rehash-size rehash-size)))

and the high bound being

     (+ 4 (/ 1 rehash-threshold))

which, for the default values of these parameters, are `4.25' and `5',
respectively.  Reducing the rehash size will tighten these bounds, but
increases the amount of time spent resizing, so you can see that the
rehash size gives some control over the time-space tradeoff of the
table.

   The programmer can control the size of a hash table by means of three
parameters:

   * Each table's INITIAL-SIZE may be specified when the table is
     created.

   * Each table has a "rehash size" that specifies how the size of the
     table is changed when it is necessary to grow or shrink the table.

   * Each table has a "rehash threshold" that specifies the relationship
     of the table's physical size to its usable size.

   If the programmer knows that the table will initially contain a
specific number of items, INITIAL-SIZE can be given when the table is
created.  If INITIAL-SIZE is an exact non-negative integer, it
specifies the initial usable size of the hash table; the table will not
change size until the number of items in the table exceeds
INITIAL-SIZE, after which automatic resizing is enabled and
INITIAL-SIZE no longer has any effect.  Otherwise, if INITIAL-SIZE is
not given or is `#f', the table is initialized to an unspecified size
and automatic resizing is immediately enabled.

   The "rehash size" specifies how much to increase the usable size of
the hash table when it becomes full.  It is either an exact positive
integer, or a real number greater than one.  If it is an integer, the
new size is the sum of the old size and the rehash size.  Otherwise, it
is a real number, and the new size is the product of the old size and
the rehash size.  Increasing the rehash size decreases the average cost
of an insertion, but increases the average amount of space used by the
table.  The rehash size of a table may be altered dynamically by the
application in order to optimize the resizing of the table; for example,
if the table will grow quickly for a known period and afterwards will
not change size, performance might be improved by using a large rehash
size during the growth phase and a small one during the static phase.
The default rehash size of a newly constructed hash table is `2.0'.

   *Warning*: The use of an exact positive integer for a rehash size is
almost always undesirable; this option is provided solely for
compatibility with the Common Lisp hash-table mechanism.  The reason for
this has to do with the time penalty for resizing the hash table.  The
time needed to resize a hash table is proportional to the number of
associations in the table.  This resizing cost is "amortized" across
the insertions required to fill the table to the point where it needs
to grow again.  If the table grows by an amount proportional to the
number of associations, then the cost of resizing and the increase in
size are both proportional to the number of associations, so the
"amortized cost" of an insertion operation is still bounded by a
constant.  However, if the table grows by a constant amount, this is
not true: the amortized cost of an insertion is not bounded by a
constant.  Thus, using a constant rehash size means that the average
cost of an insertion increases proportionally to the number of
associations in the hash table.

   The "rehash threshold" is a real number, between zero exclusive and
one inclusive, that specifies the ratio between a hash table's usable
size and its physical size.  Decreasing the rehash threshold decreases
the probability of worse-than-average insertion, deletion, and lookup
times, but increases the physical size of the table for a given usable
size.  The default rehash threshold of a newly constructed hash table is
`1'.

 - procedure: hash-table/size hash-table
     Returns the usable size of HASH-TABLE as an exact positive
     integer.  This is the number of associations that HASH-TABLE can
     hold before it will grow.

 - procedure: hash-table/rehash-size hash-table
     Returns the rehash size of HASH-TABLE.

 - procedure: set-hash-table/rehash-size! hash-table x
     X must be either an exact positive integer, or a real number that
     is greater than one.  Sets the rehash size of HASH-TABLE to X and
     returns an unspecified result.  This operation adjusts the "shrink
     threshold" of the table; the table might shrink if the number of
     associations is less than the new threshold.

 - procedure: hash-table/rehash-threshold hash-table
     Returns the rehash threshold of HASH-TABLE.

 - procedure: set-hash-table/rehash-threshold! hash-table x
     X must be a real number between zero exclusive and one inclusive.
     Sets the rehash threshold of HASH-TABLE to X and returns an
     unspecified result.  This operation does not change the usable
     size of the table, but it usually changes the physical size of the
     table, which causes the table to be rehashed.

Address Hashing
---------------

   The procedures described in this section may be used to make very
efficient key-hashing procedures for arbitrary objects.  All of these
procedures are based on "address hashing", which uses the address of an
object as its hash number.  The great advantage of address hashing is
that converting an arbitrary object to a hash number is extremely fast
and takes the same amount of time for any object.

   The disadvantage of address hashing is that the garbage collector
changes the addresses of most objects.  The hash-table implementation
compensates for this disadvantage by automatically rehashing tables that
use address hashing when garbage collections occur.  Thus, in order to
use these procedures for key hashing, it is necessary to tell the
hash-table implementation (by means of the REHASH-AFTER-GC?  argument
to the "constructor-constructor" procedure) that the hash numbers
computed by your key-hashing procedure must be recomputed after a
garbage collection.

 - procedure: eq-hash object
 - procedure: eqv-hash object
 - procedure: equal-hash object
     These procedures return a hash number for OBJECT.  The result is
     always a non-negative integer, and in the case of `eq-hash', a
     non-negative fixnum.  Two objects that are equivalent according to
     `eq?', `eqv?', or `equal?', respectively, will produce the same
     hash number when passed as arguments to these procedures, provided
     that the garbage collector does not run during or between the two
     calls.

   The following procedures are the key-hashing procedures used by the
standard address-hash-based hash tables.

 - procedure: eq-hash-mod object modulus
     This procedure is the key-hashing procedure used by
     `make-eq-hash-table'.

 - procedure: eqv-hash-mod object modulus
     This procedure is the key-hashing procedure used by
     `make-eqv-hash-table'.

 - procedure: equal-hash-mod object modulus
     This procedure is the key-hashing procedure used by
     `make-equal-hash-table'.

Low-Level Hash Table Operations
-------------------------------

   The procedures in this section allow the programmer to control some
of the internal structure of a hash table.  Normally, hash tables
maintain associations between keys and datums using pairs or weak
pairs.  These procedures allow the programmer to specify the use of
some other data structure to maintain the association.  In this
section, the data structure that represents an association in a hash
table is called an "entry".

 - procedure: hash-table/constructor key-hash key=? make-entry
          entry-valid? entry-key entry-datum set-entry-datum!
          [rehash-after-gc?]
     Creates and returns a hash-table constructor procedure (see
     Construction of Hash Tables).  The arguments define the
     characteristics of the hash table as follows:

    KEY-HASH
          The hashing procedure.  A procedure that accepts two
          arguments, a key and an exact positive integer (the
          "modulus"), and returns an exact non-negative integer that is
          less than the modulus.

    KEY=?
          A equivalence predicate that accepts two keys and is true iff
          they are the same key.  If this predicate is true of two
          keys, then KEY-HASH must return the same value for each of
          these keys (given the same modulus in both cases).

    MAKE-ENTRY
          A procedure that accepts a key and a datum as arguments and
          returns a newly allocated entry.

    ENTRY-VALID?
          A procedure that accepts an entry and returns `#f' iff the
          entry's key has been reclaimed by the garbage collector.
          Instead of a procedure, this may be `#t', which is equivalent
          to `(lambda (entry) #t)'.

    ENTRY-KEY
          A procedure that accepts an entry as an argument and returns
          the entry's key.

    ENTRY-DATUM
          A procedure that accepts an entry as an argument and returns
          the entry's datum.

    SET-ENTRY-DATUM!
          A procedure that accepts an entry and an object as arguments,
          modifies the entry's datum to be the object, and returns an
          unspecified result.

    REHASH-AFTER-GC?
          An optional argument that, if true, says the values returned
          by KEY-HASH might change after a garbage collection.  If so,
          the hash-table implementation arranges for the table to be
          rehashed when necessary.  (see Address Hashing, for
          information about hash procedures that have this property.)
          Otherwise, it is assumed that KEY-HASH always returns the
          same value for the same arguments.  The default value of this
          argument is `#f'.

For example, here is how the constructors for ordinary hash tables could
be defined:

     (define (strong-hash-table/constructor key-hash key=?
                                            #!optional rehash-after-gc?)
       (hash-table/constructor key-hash key=?
                               cons #t car cdr set-cdr!
                               (if (default-object? rehash-after-gc?)
                                   #f
                                   rehash-after-gc?)))

     (define (weak-hash-table/constructor key-hash key=?
                                          #!optional rehash-after-gc?)
       (hash-table/constructor key-hash key=? weak-cons weak-pair/car?
                               weak-car weak-cdr weak-set-cdr!
                               (if (default-object? rehash-after-gc?)
                                   #f
                                   rehash-after-gc?)))

 - procedure: hash-table/key-hash hash-table
 - procedure: hash-table/key=? hash-table
 - procedure: hash-table/make-entry hash-table
 - procedure: hash-table/entry-valid? hash-table
 - procedure: hash-table/entry-key hash-table
 - procedure: hash-table/entry-datum hash-table
 - procedure: hash-table/set-entry-datum! hash-table
     Each procedure returns the value of the corresponding argument
     that was used to construct HASH-TABLE.

   The following procedures return the contents of a hash table as a
collection of entries.  While the data structure holding the entries is
newly allocated, the entries themselves are not copied.  Since hash
table operations can modify these entries, the entries should be copied
if it is desired to keep them while continuing to modify the table.

 - procedure: hash-table/entries-list hash-table
     Returns a newly allocated list of the entries in HASH-TABLE.

 - procedure: hash-table/entries-vector hash-table
     Returns a newly allocated vector of the entries in HASH-TABLE.
     Equivalent to

          (list->vector (hash-table/entries-list HASH-TABLE))

Object Hashing
==============

   The MIT Scheme object-hashing facility provides a mechanism for
generating a unique hash number for an arbitrary object.  This hash
number, unlike an object's address, is unchanged by garbage collection.
The object-hashing facility is useful in conjunction with hash tables,
but it may be used for other things as well.  In particular, it is used
in the generation of the written representation for many objects (see
Custom Output).

   All of these procedures accept an optional argument called TABLE;
this table contains the object-integer associations.  If given, this
argument must be an object-hash table as constructed by
`hash-table/make' (see below).  If not given, a default table is used.

 - procedure: hash object [table]
     `hash' associates an exact non-negative integer with OBJECT and
     returns that integer.  If `hash' was previously called with OBJECT
     as its argument, the integer returned is the same as was returned
     by the previous call.  `hash' guarantees that distinct objects (in
     the sense of `eq?') are associated with distinct integers.

 - procedure: unhash k [table]
     `unhash' takes an exact non-negative integer K and returns the
     object associated with that integer.  If there is no object
     associated with K, or if the object previously associated with K
     has been reclaimed by the garbage collector, an error of type
     `condition-type:bad-range-argument' is signalled.  In other words,
     if `hash' previously returned K for some object, and that object
     has not been reclaimed, it is the value of the call to `unhash'.

   An object that is passed to `hash' as an argument is not protected
from being reclaimed by the garbage collector.  If all other references
to that object are eliminated, the object will be reclaimed.
Subsequently calling `unhash' with the hash number of the (now
reclaimed) object will signal an error.

     (define x (cons 0 0))           =>  unspecified
     (hash x)                        =>  77
     (eqv? (hash x) (hash x))        =>  #t
     (define x 0)                    =>  unspecified
     (gc-flip)                       ;force a garbage collection
     (unhash 77)                     error-->

 - procedure: object-hashed? object [table]
     This predicate is true if OBJECT has an associated hash number.
     Otherwise it is false.

 - procedure: valid-hash-number? k [table]
     This predicate is true if K is the hash number associated with
     some object.  Otherwise it is false.

   The following two procedures provide a lower-level interface to the
object-hashing mechanism.

 - procedure: object-hash object [table [insert?]]
     `object-hash' is like `hash', except that it accepts an additional
     optional argument, INSERT?.  If INSERT? is supplied and is `#f',
     `object-hash' will return an integer for OBJECT only if there is
     already an association in the table; otherwise, it will return
     `#f'.  If INSERT? is not supplied, or is not `#f', `object-hash'
     always returns an integer, creating an association in the table if
     necessary.

     `object-hash' additionally treats `#f' differently than does
     `hash'.  Calling `object-hash' with `#f' as its argument will
     return an integer that, when passed to `unhash', will signal an
     error rather than returning `#f'.  Likewise, `valid-hash-number?'
     will return `#f' for this integer.

 - procedure: object-unhash k [table]
     `object-unhash' is like `unhash', except that when K is not
     associated with any object or was previously associated with an
     object that has been reclaimed, `object-unhash' returns `#f'.
     This means that there is an ambiguity in the value returned by
     `object-unhash': if `#f' is returned, there is no way to tell if K
     is associated with `#f' or is not associated with any object at
     all.

   Finally, this procedure makes new object-hash tables:

 - procedure: hash-table/make
     This procedure creates and returns a new, empty object-hash table
     that is suitable for use as the optional TABLE argument to the
     above procedures.  The returned table contains no associations.