Import Upstream version 2a6upstream/2a6

1 files changed, 1306 insertions, 0 deletions

diff --git a/slib.info-1 b/slib.info-1
new file mode 100644
index 0000000..89c4fce
--- /dev/null
+++ b/slib.info-1
@@ -0,0 +1,1306 @@
+This is Info file slib.info, produced by Makeinfo-1.64 from the input
+file slib.texi.
+
+  This file documents SLIB, the portable Scheme library.
+
+  Copyright (C) 1993 Todd R. Eigenschink Copyright (C) 1993, 1994, 1995
+Aubrey Jaffer
+
+  Permission is granted to make and distribute verbatim copies of this
+manual provided the copyright notice and this permission notice are
+preserved on all copies.
+
+  Permission is granted to copy and distribute modified versions of this
+manual under the conditions for verbatim copying, provided that the
+entire resulting derived work is distributed under the terms of a
+permission notice identical to this one.
+
+  Permission is granted to copy and distribute translations of this
+manual into another language, under the above conditions for modified
+versions, except that this permission notice may be stated in a
+translation approved by the author.
+
+
+File: slib.info,  Node: Top,  Next: Overview,  Prev: (dir),  Up: (dir)
+
+  This file documents SLIB, the portable Scheme library.
+
+Good Engineering is 1% inspiration and 99% documentation.
+=========================================================
+
+  Herein lies the good part.  Many thanks to Todd Eigenschink
+<eigenstr@CS.Rose-Hulman.Edu> (who thanks Dave Love <D.Love@dl.ac.uk>)
+for creating `slib.texi'.  I have learned much from their example.
+
+  Aubrey Jaffer jaffer@ai.mit.edu
+
+* Menu:
+
+* Overview::                    What is SLIB?
+
+* Data Structures::             Various data structures.
+* Macros::                      Extensions to Scheme syntax.
+* Numerics::
+* Procedures::                  Miscellaneous utility procedures.
+* Standards Support::           Support for Scheme Standards.
+* Session Support::             Debugging, Pathnames, Require, etc.
+
+* Optional SLIB Packages::
+* Procedure and Macro Index::
+* Variable Index::
+
+
+File: slib.info,  Node: Overview,  Next: Data Structures,  Prev: Top,  Up: Top
+
+Overview
+********
+
+  SLIB is a portable Scheme library meant to provide compatibility and
+utility functions for all standard Scheme implementations, and fixes
+several implementations which are non-conforming.  SLIB conforms to
+`Revised^4 Report on the Algorithmic Language Scheme' and the IEEE
+P1178 specification.  SLIB supports Unix and similar systems, VMS, and
+MS-DOS.
+
+  For a summary of what each file contains, see the file `README'.  For
+a list of the features that have changed since the last SLIB release,
+see the file `ANNOUNCE'.  For a list of the features that have changed
+over time, see the file `ChangeLog'.
+
+  The maintainer can be reached as `jaffer@ai.mit.edu'.
+
+* Menu:
+
+* Installation::                How to install SLIB on your system.
+* Porting::                     SLIB to new platforms
+* Coding Standards::            How to write modules for SLIB.
+* Copyrights::                  Intellectual propery issues.
+* Manual Conventions::          Conventions used in this manual.
+
+
+File: slib.info,  Node: Installation,  Next: Porting,  Prev: Overview,  Up: Overview
+
+Installation
+============
+
+  Check the manifest in `README' to find a configuration file for your
+Scheme implementation.  Initialization files for most IEEE P1178
+compliant Scheme Implementations are included with this distribution.
+
+  If the Scheme implementation supports `getenv', then the value of the
+shell environment variable SCHEME_LIBRARY_PATH will be used for
+`(library-vicinity)' if it is defined.  Currently, Chez, Elk,
+MITScheme, scheme->c, VSCM, and SCM support `getenv'.
+
+  You should check the definitions of `software-type',
+`scheme-implementation-version', `implementation-vicinity', and
+`library-vicinity' in the initialization file.  There are comments in
+the file for how to configure it.
+
+  Once this is done you can modify the startup file for your Scheme
+implementation to `load' this initialization file.  SLIB is then
+installed.
+
+  Multiple implementations of Scheme can all use the same SLIB
+directory.  Simply configure each implementation's initialization file
+as outlined above.
+
+  The SCM implementation does not require any initialization file as
+SLIB support is already built in to SCM.  See the documentation with
+SCM for installation instructions.
+
+  SLIB includes methods to create heap images for the VSCM and Scheme48
+implementations.  The instructions for creating a VSCM image are in
+comments in `vscm.init'.  To make a Scheme48 image, `cd' to the SLIB
+directory and type `make slib48'.  This will also create a shell script
+with the name `slib48' which will invoke the saved image.
+
+
+File: slib.info,  Node: Porting,  Next: Coding Standards,  Prev: Installation,  Up: Overview
+
+Porting
+=======
+
+  If there is no initialization file for your Scheme implementation, you
+will have to create one.  Your Scheme implementation must be largely
+compliant with `IEEE Std 1178-1990' or `Revised^4 Report on the
+Algorithmic Language Scheme' to support SLIB.
+
+  `Template.scm' is an example configuration file.  The comments inside
+will direct you on how to customize it to reflect your system.  Give
+your new initialization file the implementation's name with `.init'
+appended.  For instance, if you were porting `foo-scheme' then the
+initialization file might be called `foo.init'.
+
+  Your customized version should then be loaded as part of your scheme
+implementation's initialization.  It will load `require.scm' (*Note
+Require::) from the library; this will allow the use of `provide',
+`provided?', and `require' along with the "vicinity" functions
+(`vicinity' functions are documented in the section on Require.  *Note
+Require::).  The rest of the library will then be accessible in a
+system independent fashion.
+
+  Please mail new working configuration files to `jaffer@ai.mit.edu' so
+that they can be included in the SLIB distribution.
+
+
+File: slib.info,  Node: Coding Standards,  Next: Copyrights,  Prev: Porting,  Up: Overview
+
+Coding Standards
+================
+
+  All library packages are written in IEEE P1178 Scheme and assume that
+a configuration file and `require.scm' package have already been
+loaded.  Other versions of Scheme can be supported in library packages
+as well by using, for example, `(provided? 'rev3-report)' or `(require
+'rev3-report)' (*Note Require::).
+
+  `require.scm' defines `*catalog*', an association list of module
+names and filenames.  When a new package is added to the library, an
+entry should be added to `require.scm'.  Local packages can also be
+added to `*catalog*' and even shadow entries already in the table.
+
+  The module name and `:' should prefix each symbol defined in the
+package.  Definitions for external use should then be exported by having
+`(define foo module-name:foo)'.
+
+  Submitted code should not duplicate routines which are already in SLIB
+files.  Use `require' to force those features to be supported in your
+package.  Care should be taken that there are no circularities in the
+`require's and `load's between the library packages.
+
+  Documentation should be provided in Emacs Texinfo format if possible,
+But documentation must be provided.
+
+  Your package will be released sooner with SLIB if you send me a file
+which tests your code.  Please run this test *before* you send me the
+code!
+
+Modifications
+-------------
+
+  Please document your changes.  A line or two for `ChangeLog' is
+sufficient for simple fixes or extensions.  Look at the format of
+`ChangeLog' to see what information is desired.  Please send me `diff'
+files from the latest SLIB distribution (remember to send `diff's of
+`slib.texi' and `ChangeLog').  This makes for less email traffic and
+makes it easier for me to integrate when more than one person is
+changing a file (this happens a lot with `slib.texi' and `*.init'
+files).
+
+  If someone else wrote a package you want to significantly modify,
+please try to contact the author, who may be working on a new version.
+This will insure against wasting effort on obsolete versions.
+
+  Please *do not* reformat the source code with your favorite
+beautifier, make 10 fixes, and send me the resulting source code.  I do
+not have the time to fish through 10000 diffs to find your 10 real
+fixes.
+
+
+File: slib.info,  Node: Copyrights,  Next: Manual Conventions,  Prev: Coding Standards,  Up: Overview
+
+Copyrights
+==========
+
+  This section has instructions for SLIB authors regarding copyrights.
+
+  Each package in SLIB must either be in the public domain, or come
+with a statement of terms permitting users to copy, redistribute and
+modify it.  The comments at the beginning of `require.scm' and
+`macwork.scm' illustrate copyright and appropriate terms.
+
+  If your code or changes amount to less than about 10 lines, you do not
+need to add your copyright or send a disclaimer.
+
+Putting code into the Public Domain
+-----------------------------------
+
+  In order to put code in the public domain you should sign a copyright
+disclaimer and send it to the SLIB maintainer.  Contact
+jaffer@ai.mit.edu for the address to mail the disclaimer to.
+
+     I, NAME, hereby affirm that I have placed the software package
+     NAME in the public domain.
+
+     I affirm that I am the sole author and sole copyright holder for
+     the software package, that I have the right to place this software
+     package in the public domain, and that I will do nothing to
+     undermine this status in the future.
+
+                                                     SIGNATURE AND DATE
+
+  This wording assumes that you are the sole author.  If you are not the
+sole author, the wording needs to be different.  If you don't want to be
+bothered with sending a letter every time you release or modify a
+module, make your letter say that it also applies to your future
+revisions of that module.
+
+  Make sure no employer has any claim to the copyright on the work you
+are submitting.  If there is any doubt, create a copyright disclaimer
+and have your employer sign it.  Mail the signed disclaimer to the SLIB
+maintainer.  Contact jaffer@ai.mit.edu for the address to mail the
+disclaimer to.  An example disclaimer follows.
+
+Explicit copying terms
+----------------------
+
+If you submit more than about 10 lines of code which you are not placing
+into the Public Domain (by sending me a disclaimer) you need to:
+
+   * Arrange that your name appears in a copyright line for the
+     appropriate year.   Multiple copyright lines are acceptable.
+
+   * With your copyright line, specify any terms you require to be
+     different from those already in the file.
+
+   * Make sure no employer has any claim to the copyright on the work
+     you are submitting.  If there is any doubt, create a copyright
+     disclaimer and have your employer sign it.  Mail the signed
+     disclaim to the SLIB maintainer.  Contact jaffer@ai.mit.edu for
+     the address to mail the disclaimer to.
+
+Example: Company Copyright Disclaimer
+-------------------------------------
+
+  This disclaimer should be signed by a vice president or general
+manager of the company.  If you can't get at them, anyone else
+authorized to license out software produced there will do.  Here is a
+sample wording:
+
+     EMPLOYER Corporation hereby disclaims all copyright interest in
+     the program PROGRAM written by NAME.
+
+     EMPLOYER Corporation affirms that it has no other intellectual
+     property interest that would undermine this release, and will do
+     nothing to undermine it in the future.
+
+     SIGNATURE AND DATE,
+     NAME, TITLE, EMPLOYER Corporation
+
+
+File: slib.info,  Node: Manual Conventions,  Prev: Copyrights,  Up: Overview
+
+Manual Conventions
+==================
+
+  Things that are labeled as Functions are called for their return
+values.  Things that are labeled as Procedures are called primarily for
+their side effects.
+
+  All examples throughout this text were produced using the `scm'
+Scheme implementation.
+
+  At the beginning of each section, there is a line that looks something
+like
+
+  `(require 'feature)'.
+
+This means that, in order to use `feature', you must include the line
+`(require 'feature)' somewhere in your code prior to the use of that
+feature.  `require' will make sure that the feature is loaded.
+
+
+File: slib.info,  Node: Data Structures,  Next: Macros,  Prev: Overview,  Up: Top
+
+Data Structures
+***************
+
+* Menu:
+
+* Arrays::                      'array
+* Array Mapping::               'array-for-each
+* Association Lists::           'alist
+* Collections::                 'collect
+* Dynamic Data Type::           'dynamic
+* Hash Tables::                 'hash-table
+* Hashing::                     'hash, 'sierpinski, 'soundex
+* Chapter Ordering::            'chapter-order
+* Object::                      'object
+* Parameter lists::             'parameters
+* Priority Queues::             'priority-queue
+* Queues::                      'queue
+* Records::                     'record
+* Base Table::
+* Relational Database::         'relational-database
+* Weight-Balanced Trees::       'wt-tree
+* Structures::                  'struct, 'structure
+
+
+File: slib.info,  Node: Arrays,  Next: Array Mapping,  Prev: Data Structures,  Up: Data Structures
+
+Arrays
+======
+
+  `(require 'array)'
+
+ - Function: array? OBJ
+     Returns `#t' if the OBJ is an array, and `#f' if not.
+
+ - Function: make-array INITIAL-VALUE BOUND1 BOUND2 ...
+     Creates and returns an array that has as many dimensins as there
+     are BOUNDs and fills it with INITIAL-VALUE.
+
+  When constructing an array, BOUND is either an inclusive range of
+indices expressed as a two element list, or an upper bound expressed as
+a single integer.  So
+     (make-array 'foo 3 3) == (make-array 'foo '(0 2) '(0 2))
+
+ - Function: make-shared-array ARRAY MAPPER BOUND1 BOUND2 ...
+     `make-shared-array' can be used to create shared subarrays of other
+     arrays.  The MAPPER is a function that translates coordinates in
+     the new array into coordinates in the old array.  A MAPPER must be
+     linear, and its range must stay within the bounds of the old
+     array, but it can be otherwise arbitrary.  A simple example:
+          (define fred (make-array #f 8 8))
+          (define freds-diagonal
+            (make-shared-array fred (lambda (i) (list i i)) 8))
+          (array-set! freds-diagonal 'foo 3)
+          (array-ref fred 3 3)
+             => FOO
+          (define freds-center
+            (make-shared-array fred (lambda (i j) (list (+ 3 i) (+ 3 j)))
+                               2 2))
+          (array-ref freds-center 0 0)
+             => FOO
+
+ - Function: array-rank OBJ
+     Returns the number of dimensions of OBJ.  If OBJ is not an array,
+     0 is returned.
+
+ - Function: array-shape ARRAY
+     `array-shape' returns a list of inclusive bounds.  So:
+          (array-shape (make-array 'foo 3 5))
+             => ((0 2) (0 4))
+
+ - Function: array-dimensions ARRAY
+     `array-dimensions' is similar to `array-shape' but replaces
+     elements with a 0 minimum with one greater than the maximum. So:
+          (array-dimensions (make-array 'foo 3 5))
+             => (3 5)
+
+ - Procedure: array-in-bounds? ARRAY INDEX1 INDEX2 ...
+     Returns `#t' if its arguments would be acceptable to `array-ref'.
+
+ - Function: array-ref ARRAY INDEX1 INDEX2 ...
+     Returns the element at the `(INDEX1, INDEX2)' element in ARRAY.
+
+ - Procedure: array-set! ARRAY NEW-VALUE INDEX1 INDEX2 ...
+
+ - Function: array-1d-ref ARRAY INDEX
+ - Function: array-2d-ref ARRAY INDEX INDEX
+ - Function: array-3d-ref ARRAY INDEX INDEX INDEX
+
+ - Procedure: array-1d-set! ARRAY NEW-VALUE INDEX
+ - Procedure: array-2d-set! ARRAY NEW-VALUE INDEX INDEX
+ - Procedure: array-3d-set! ARRAY NEW-VALUE INDEX INDEX INDEX
+
+  The functions are just fast versions of `array-ref' and `array-set!'
+that take a fixed number of arguments, and perform no bounds checking.
+
+  If you comment out the bounds checking code, this is about as
+efficient as you could ask for without help from the compiler.
+
+  An exercise left to the reader: implement the rest of APL.
+
+
+File: slib.info,  Node: Array Mapping,  Next: Association Lists,  Prev: Arrays,  Up: Data Structures
+
+Array Mapping
+=============
+
+  `(require 'array-for-each)'
+
+ - Function: array-map! ARRAY0 PROC ARRAY1 ...
+     ARRAY1, ... must have the same number of dimensions as ARRAY0 and
+     have a range for each index which includes the range for the
+     corresponding index in ARRAY0.  PROC is applied to each tuple of
+     elements of ARRAY1 ... and the result is stored as the
+     corresponding element in ARRAY0.  The value returned is
+     unspecified.  The order of application is unspecified.
+
+ - Function: array-for-each PROC ARRAY0 ...
+     PROC is applied to each tuple of elements of ARRAY0 ...  in
+     row-major order.  The value returned is unspecified.
+
+ - Function: array-indexes ARRAY
+     Returns an array of lists of indexes for ARRAY such that, if LI is
+     a list of indexes for which ARRAY is defined, (equal?  LI (apply
+     array-ref (array-indexes ARRAY) LI)).
+
+ - Function: array-copy! SOURCE DESTINATION
+     Copies every element from vector or array SOURCE to the
+     corresponding element of DESTINATION.  DESTINATION must have the
+     same rank as SOURCE, and be at least as large in each dimension.
+     The order of copying is unspecified.
+
+
+File: slib.info,  Node: Association Lists,  Next: Collections,  Prev: Array Mapping,  Up: Data Structures
+
+Association Lists
+=================
+
+  `(require 'alist)'
+
+  Alist functions provide utilities for treating a list of key-value
+pairs as an associative database.  These functions take an equality
+predicate, PRED, as an argument.  This predicate should be repeatable,
+symmetric, and transitive.
+
+  Alist functions can be used with a secondary index method such as hash
+tables for improved performance.
+
+ - Function: predicate->asso PRED
+     Returns an "association function" (like `assq', `assv', or
+     `assoc') corresponding to PRED.  The returned function returns a
+     key-value pair whose key is `pred'-equal to its first argument or
+     `#f' if no key in the alist is PRED-equal to the first argument.
+
+ - Function: alist-inquirer PRED
+     Returns a procedure of 2 arguments, ALIST and KEY, which returns
+     the value associated with KEY in ALIST or `#f' if KEY does not
+     appear in ALIST.
+
+ - Function: alist-associator PRED
+     Returns a procedure of 3 arguments, ALIST, KEY, and VALUE, which
+     returns an alist with KEY and VALUE associated.  Any previous
+     value associated with KEY will be lost.  This returned procedure
+     may or may not have side effects on its ALIST argument.  An
+     example of correct usage is:
+          (define put (alist-associator string-ci=?))
+          (define alist '())
+          (set! alist (put alist "Foo" 9))
+
+ - Function: alist-remover PRED
+     Returns a procedure of 2 arguments, ALIST and KEY, which returns
+     an alist with an association whose KEY is key removed.  This
+     returned procedure may or may not have side effects on its ALIST
+     argument.  An example of correct usage is:
+          (define rem (alist-remover string-ci=?))
+          (set! alist (rem alist "foo"))
+
+ - Function: alist-map PROC ALIST
+     Returns a new association list formed by mapping PROC over the
+     keys and values of ALIST.   PROC must be a function of 2 arguments
+     which returns the new value part.
+
+ - Function: alist-for-each PROC ALIST
+     Applies PROC to each pair of keys and values of ALIST.  PROC must
+     be a function of 2 arguments.  The returned value is unspecified.
+
+
+File: slib.info,  Node: Collections,  Next: Dynamic Data Type,  Prev: Association Lists,  Up: Data Structures
+
+Collections
+===========
+
+  `(require 'collect)'
+
+  Routines for managing collections.  Collections are aggregate data
+structures supporting iteration over their elements, similar to the
+Dylan(TM) language, but with a different interface.  They have
+"elements" indexed by corresponding "keys", although the keys may be
+implicit (as with lists).
+
+  New types of collections may be defined as YASOS objects (*Note
+Yasos::).  They must support the following operations:
+   * `(collection? SELF)' (always returns `#t');
+
+   * `(size SELF)' returns the number of elements in the collection;
+
+   * `(print SELF PORT)' is a specialized print operation for the
+     collection which prints a suitable representation on the given
+     PORT or returns it as a string if PORT is `#t';
+
+   * `(gen-elts SELF)' returns a thunk which on successive invocations
+     yields elements of SELF in order or gives an error if it is
+     invoked more than `(size SELF)' times;
+
+   * `(gen-keys SELF)' is like `gen-elts', but yields the collection's
+     keys in order.
+
+  They might support specialized `for-each-key' and `for-each-elt'
+operations.
+
+ - Function: collection? OBJ
+     A predicate, true initially of lists, vectors and strings.  New
+     sorts of collections must answer `#t' to `collection?'.
+
+ - Procedure: map-elts PROC . COLLECTIONS
+ - Procedure: do-elts PROC . COLLECTIONS
+     PROC is a procedure taking as many arguments as there are
+     COLLECTIONS (at least one).  The COLLECTIONS are iterated over in
+     their natural order and PROC is applied to the elements yielded by
+     each iteration in turn.  The order in which the arguments are
+     supplied corresponds to te order in which the COLLECTIONS appear.
+     `do-elts' is used when only side-effects of PROC are of interest
+     and its return value is unspecified.  `map-elts' returns a
+     collection (actually a vector) of the results of the applications
+     of PROC.
+
+     Example:
+          (map-elts + (list 1 2 3) (vector 1 2 3))
+             => #(2 4 6)
+
+ - Procedure: map-keys PROC . COLLECTIONS
+ - Procedure: do-keys PROC . COLLECTIONS
+     These are analogous to `map-elts' and `do-elts', but each
+     iteration is over the COLLECTIONS' *keys* rather than their
+     elements.
+
+     Example:
+          (map-keys + (list 1 2 3) (vector 1 2 3))
+             => #(0 2 4)
+
+ - Procedure: for-each-key COLLECTION PROC
+ - Procedure: for-each-elt COLLECTION PROC
+     These are like `do-keys' and `do-elts' but only for a single
+     collection; they are potentially more efficient.
+
+ - Function: reduce PROC SEED . COLLECTIONS
+     A generalization of the list-based `comlist:reduce-init' (*Note
+     Lists as sequences::) to collections which will shadow the
+     list-based version if `(require 'collect)' follows `(require
+     'common-list-functions)' (*Note Common List Functions::).
+
+     Examples:
+          (reduce + 0 (vector 1 2 3))
+             => 6
+          (reduce union '() '((a b c) (b c d) (d a)))
+             => (c b d a).
+
+ - Function: any? PRED . COLLECTIONS
+     A generalization of the list-based `some' (*Note Lists as
+     sequences::) to collections.
+
+     Example:
+          (any? odd? (list 2 3 4 5))
+             => #t
+
+ - Function: every? PRED . COLLECTIONS
+     A generalization of the list-based `every' (*Note Lists as
+     sequences::) to collections.
+
+     Example:
+          (every? collection? '((1 2) #(1 2)))
+             => #t
+
+ - Function: empty? COLLECTION
+     Returns `#t' iff there are no elements in COLLECTION.
+
+     `(empty? COLLECTION) == (zero? (size COLLECTION))'
+
+ - Function: size COLLECTION
+     Returns the number of elements in COLLECTION.
+
+ - Function: Setter LIST-REF
+     See *Note Setters:: for a definition of "setter".  N.B.  `(setter
+     list-ref)' doesn't work properly for element 0 of a list.
+
+  Here is a sample collection: `simple-table' which is also a `table'.
+     (define-predicate TABLE?)
+     (define-operation (LOOKUP table key failure-object))
+     (define-operation (ASSOCIATE! table key value)) ;; returns key
+     (define-operation (REMOVE! table key))          ;; returns value
+     
+     (define (MAKE-SIMPLE-TABLE)
+       (let ( (table (list)) )
+         (object
+          ;; table behaviors
+          ((TABLE? self) #t)
+          ((SIZE self) (size table))
+          ((PRINT self port) (format port "#<SIMPLE-TABLE>"))
+          ((LOOKUP self key failure-object)
+           (cond
+            ((assq key table) => cdr)
+            (else failure-object)
+            ))
+          ((ASSOCIATE! self key value)
+           (cond
+            ((assq key table)
+             => (lambda (bucket) (set-cdr! bucket value) key))
+            (else
+             (set! table (cons (cons key value) table))
+             key)
+            ))
+          ((REMOVE! self key);; returns old value
+           (cond
+            ((null? table) (slib:error "TABLE:REMOVE! Key not found: " key))
+            ((eq? key (caar table))
+             (let ( (value (cdar table)) )
+               (set! table (cdr table))
+               value)
+             )
+            (else
+             (let loop ( (last table) (this (cdr table)) )
+               (cond
+                ((null? this)
+                 (slib:error "TABLE:REMOVE! Key not found: " key))
+                ((eq? key (caar this))
+                 (let ( (value (cdar this)) )
+                   (set-cdr! last (cdr this))
+                   value)
+                 )
+                (else
+                 (loop (cdr last) (cdr this)))
+                ) ) )
+            ))
+          ;; collection behaviors
+          ((COLLECTION? self) #t)
+          ((GEN-KEYS self) (collect:list-gen-elts (map car table)))
+          ((GEN-ELTS self) (collect:list-gen-elts (map cdr table)))
+          ((FOR-EACH-KEY self proc)
+           (for-each (lambda (bucket) (proc (car bucket))) table)
+           )
+          ((FOR-EACH-ELT self proc)
+           (for-each (lambda (bucket) (proc (cdr bucket))) table)
+           )
+          ) ) )
+
+
+File: slib.info,  Node: Dynamic Data Type,  Next: Hash Tables,  Prev: Collections,  Up: Data Structures
+
+Dynamic Data Type
+=================
+
+  `(require 'dynamic)'
+
+ - Function: make-dynamic OBJ
+     Create and returns a new "dynamic" whose global value is OBJ.
+
+ - Function: dynamic? OBJ
+     Returns true if and only if OBJ is a dynamic.  No object
+     satisfying `dynamic?' satisfies any of the other standard type
+     predicates.
+
+ - Function: dynamic-ref DYN
+     Return the value of the given dynamic in the current dynamic
+     environment.
+
+ - Procedure: dynamic-set! DYN OBJ
+     Change the value of the given dynamic to OBJ in the current
+     dynamic environment.  The returned value is unspecified.
+
+ - Function: call-with-dynamic-binding DYN OBJ THUNK
+     Invoke and return the value of the given thunk in a new, nested
+     dynamic environment in which the given dynamic has been bound to a
+     new location whose initial contents are the value OBJ.  This
+     dynamic environment has precisely the same extent as the
+     invocation of the thunk and is thus captured by continuations
+     created within that invocation and re-established by those
+     continuations when they are invoked.
+
+  The `dynamic-bind' macro is not implemented.
+
+
+File: slib.info,  Node: Hash Tables,  Next: Hashing,  Prev: Dynamic Data Type,  Up: Data Structures
+
+Hash Tables
+===========
+
+  `(require 'hash-table)'
+
+ - Function: predicate->hash PRED
+     Returns a hash function (like `hashq', `hashv', or `hash')
+     corresponding to the equality predicate PRED.  PRED should be
+     `eq?', `eqv?', `equal?', `=', `char=?', `char-ci=?', `string=?', or
+     `string-ci=?'.
+
+  A hash table is a vector of association lists.
+
+ - Function: make-hash-table K
+     Returns a vector of K empty (association) lists.
+
+  Hash table functions provide utilities for an associative database.
+These functions take an equality predicate, PRED, as an argument.  PRED
+should be `eq?', `eqv?', `equal?', `=', `char=?', `char-ci=?',
+`string=?', or `string-ci=?'.
+
+ - Function: predicate->hash-asso PRED
+     Returns a hash association function of 2 arguments, KEY and
+     HASHTAB, corresponding to PRED.  The returned function returns a
+     key-value pair whose key is PRED-equal to its first argument or
+     `#f' if no key in HASHTAB is PRED-equal to the first argument.
+
+ - Function: hash-inquirer PRED
+     Returns a procedure of 3 arguments, `hashtab' and `key', which
+     returns the value associated with `key' in `hashtab' or `#f' if
+     key does not appear in `hashtab'.
+
+ - Function: hash-associator PRED
+     Returns a procedure of 3 arguments, HASHTAB, KEY, and VALUE, which
+     modifies HASHTAB so that KEY and VALUE associated.  Any previous
+     value associated with KEY will be lost.
+
+ - Function: hash-remover PRED
+     Returns a procedure of 2 arguments, HASHTAB and KEY, which
+     modifies HASHTAB so that the association whose key is KEY is
+     removed.
+
+ - Function: hash-map PROC HASH-TABLE
+     Returns a new hash table formed by mapping PROC over the keys and
+     values of HASH-TABLE.  PROC must be a function of 2 arguments
+     which returns the new value part.
+
+ - Function: hash-for-each PROC HASH-TABLE
+     Applies PROC to each pair of keys and values of HASH-TABLE.  PROC
+     must be a function of 2 arguments.  The returned value is
+     unspecified.
+
+
+File: slib.info,  Node: Hashing,  Next: Chapter Ordering,  Prev: Hash Tables,  Up: Data Structures
+
+Hashing
+=======
+
+  `(require 'hash)'
+
+  These hashing functions are for use in quickly classifying objects.
+Hash tables use these functions.
+
+ - Function: hashq OBJ K
+ - Function: hashv OBJ K
+ - Function: hash OBJ K
+     Returns an exact non-negative integer less than K.  For each
+     non-negative integer less than K there are arguments OBJ for which
+     the hashing functions applied to OBJ and K returns that integer.
+
+     For `hashq', `(eq? obj1 obj2)' implies `(= (hashq obj1 k) (hashq
+     obj2))'.
+
+     For `hashv', `(eqv? obj1 obj2)' implies `(= (hashv obj1 k) (hashv
+     obj2))'.
+
+     For `hash', `(equal? obj1 obj2)' implies `(= (hash obj1 k) (hash
+     obj2))'.
+
+     `hash', `hashv', and `hashq' return in time bounded by a constant.
+     Notice that items having the same `hash' implies the items have
+     the same `hashv' implies the items have the same `hashq'.
+
+  `(require 'sierpinski)'
+
+ - Function: make-sierpinski-indexer MAX-COORDINATE
+     Returns a procedure (eg hash-function) of 2 numeric arguments which
+     preserves *nearness* in its mapping from NxN to N.
+
+     MAX-COORDINATE is the maximum coordinate (a positive integer) of a
+     population of points.  The returned procedures is a function that
+     takes the x and y coordinates of a point, (non-negative integers)
+     and returns an integer corresponding to the relative position of
+     that point along a Sierpinski curve.  (You can think of this as
+     computing a (pseudo-) inverse of the Sierpinski spacefilling
+     curve.)
+
+     Example use: Make an indexer (hash-function) for integer points
+     lying in square of integer grid points [0,99]x[0,99]:
+          (define space-key (make-sierpinski-indexer 100))
+     Now let's compute the index of some points:
+          (space-key 24 78)               => 9206
+          (space-key 23 80)               => 9172
+
+     Note that locations (24, 78) and (23, 80) are near in index and
+     therefore, because the Sierpinski spacefilling curve is
+     continuous, we know they must also be near in the plane.  Nearness
+     in the plane does not, however, necessarily correspond to nearness
+     in index, although it *tends* to be so.
+
+     Example applications:
+
+          Sort points by Sierpinski index to get heuristic solution to
+          *travelling salesman problem*.  For details of performance,
+          see L. Platzman and J. Bartholdi, "Spacefilling curves and the
+          Euclidean travelling salesman problem", JACM 36(4):719-737
+          (October 1989) and references therein.
+
+
+          Use Sierpinski index as key by which to store 2-dimensional
+          data in a 1-dimensional data structure (such as a table).
+          Then locations that are near each other in 2-d space will
+          tend to be near each other in 1-d data structure; and
+          locations that are near in 1-d data structure will be near in
+          2-d space.  This can significantly speed retrieval from
+          secondary storage because contiguous regions in the plane
+          will tend to correspond to contiguous regions in secondary
+          storage.  (This is a standard technique for managing CAD/CAM
+          or geographic data.)
+
+
+  `(require 'soundex)'
+
+ - Function: soundex NAME
+     Computes the *soundex* hash of NAME.  Returns a string of an
+     initial letter and up to three digits between 0 and 6.  Soundex
+     supposedly has the property that names that sound similar in normal
+     English pronunciation tend to map to the same key.
+
+     Soundex was a classic algorithm used for manual filing of personal
+     records before the advent of computers.  It performs adequately for
+     English names but has trouble with other nationalities.
+
+     See Knuth, Vol. 3 `Sorting and searching', pp 391-2
+
+     To manage unusual inputs, `soundex' omits all non-alphabetic
+     characters.  Consequently, in this implementation:
+
+          (soundex <string of blanks>)    => ""
+          (soundex "")                    => ""
+
+     Examples from Knuth:
+
+          (map soundex '("Euler" "Gauss" "Hilbert" "Knuth"
+                                 "Lloyd" "Lukasiewicz"))
+                  => ("E460" "G200" "H416" "K530" "L300" "L222")
+          
+          (map soundex '("Ellery" "Ghosh" "Heilbronn" "Kant"
+                                  "Ladd" "Lissajous"))
+                  => ("E460" "G200" "H416" "K530" "L300" "L222")
+
+     Some cases in which the algorithm fails (Knuth):
+
+          (map soundex '("Rogers" "Rodgers"))     => ("R262" "R326")
+          
+          (map soundex '("Sinclair" "St. Clair")) => ("S524" "S324")
+          
+          (map soundex '("Tchebysheff" "Chebyshev")) => ("T212" "C121")
+
+
+File: slib.info,  Node: Chapter Ordering,  Next: Object,  Prev: Hashing,  Up: Data Structures
+
+Chapter Ordering
+================
+
+  `(require 'chapter-order)'
+
+  The `chap:' functions deal with strings which are ordered like
+chapter numbers (or letters) in a book.  Each section of the string
+consists of consecutive numeric or consecutive aphabetic characters of
+like case.
+
+ - Function: chap:string<? STRING1 STRING2
+     Returns #t if the first non-matching run of alphabetic upper-case
+     or the first non-matching run of alphabetic lower-case or the first
+     non-matching run of numeric characters of STRING1 is `string<?'
+     than the corresponding non-matching run of characters of STRING2.
+
+          (chap:string<? "a.9" "a.10")                    => #t
+          (chap:string<? "4c" "4aa")                      => #t
+          (chap:string<? "Revised^{3.99}" "Revised^{4}")  => #t
+
+ - Function: chap:string>? STRING1 STRING2
+ - Function: chap:string<=? STRING1 STRING2
+ - Function: chap:string>=? STRING1 STRING2
+     Implement the corresponding chapter-order predicates.
+
+ - Function: chap:next-string STRING
+     Returns the next string in the *chapter order*.  If STRING has no
+     alphabetic or numeric characters, `(string-append STRING "0")' is
+     returnd.  The argument to chap:next-string will always be
+     `chap:string<?' than the result.
+
+          (chap:next-string "a.9")                => "a.10"
+          (chap:next-string "4c")                 => "4d"
+          (chap:next-string "4z")                 => "4aa"
+          (chap:next-string "Revised^{4}")        => "Revised^{5}"
+
+
+File: slib.info,  Node: Object,  Next: Parameter lists,  Prev: Chapter Ordering,  Up: Data Structures
+
+Macroless Object System
+=======================
+
+  `(require 'object)'
+
+  This is the Macroless Object System written by Wade Humeniuk
+(whumeniu@datap.ca).  Conceptual Tributes: *Note Yasos::, MacScheme's
+%object, CLOS, Lack of R4RS macros.
+
+Concepts
+--------
+
+OBJECT
+     An object is an ordered association-list (by `eq?') of methods
+     (procedures).  Methods can be added (`make-method!'), deleted
+     (`unmake-method!') and retrieved (`get-method').  Objects may
+     inherit methods from other objects.  The object binds to the
+     environment it was created in, allowing closures to be used to
+     hide private procedures and data.
+
+GENERIC-METHOD
+     A generic-method associates (in terms of `eq?') object's method.
+     This allows scheme function style to be used for objects.  The
+     calling scheme for using a generic method is `(generic-method
+     object param1 param2 ...)'.
+
+METHOD
+     A method is a procedure that exists in the object.  To use a method
+     get-method must be called to look-up the method.  Generic methods
+     implement the get-method functionality.  Methods may be added to an
+     object associated with any scheme obj in terms of eq?
+
+GENERIC-PREDICATE
+     A generic method that returns a boolean value for any scheme obj.
+
+PREDICATE
+     A object's method asscociated with a generic-predicate. Returns
+     `#t'.
+
+Procedures
+----------
+
+ - Function: make-object ANCESTOR ...
+     Returns an object.  Current object implementation is a tagged
+     vector.  ANCESTORs are optional and must be objects in terms of
+     object?.  ANCESTORs methods are included in the object.  Multiple
+     ANCESTORs might associate the same generic-method with a method.
+     In this case the method of the ANCESTOR first appearing in the
+     list is the one returned by `get-method'.
+
+ - Function: object? OBJ
+     Returns boolean value whether OBJ was created by make-object.
+
+ - Function: make-generic-method EXCEPTION-PROCEDURE
+     Returns a procedure which be associated with an object's methods.
+     If EXCEPTION-PROCEDURE is specified then it is used to process
+     non-objects.
+
+ - Function: make-generic-predicate
+     Returns a boolean procedure for any scheme object.
+
+ - Function: make-method! OBJECT GENERIC-METHOD METHOD
+     Associates METHOD to the GENERIC-METHOD in the object.  The METHOD
+     overrides any previous association with the GENERIC-METHOD within
+     the object.  Using `unmake-method!' will restore the object's
+     previous association with the GENERIC-METHOD.  METHOD must be a
+     procedure.
+
+ - Function: make-predicate! OBJECT GENERIC-PRECIATE
+     Makes a predicate method associated with the GENERIC-PREDICATE.
+
+ - Function: unmake-method! OBJECT GENERIC-METHOD
+     Removes an object's association with a GENERIC-METHOD .
+
+ - Function: get-method OBJECT GENERIC-METHOD
+     Returns the object's method associated (if any) with the
+     GENERIC-METHOD.  If no associated method exists an error is
+     flagged.
+
+Examples
+--------
+
+     (require 'object)
+     
+     (define instantiate (make-generic-method))
+     
+     (define (make-instance-object . ancestors)
+       (define self (apply make-object
+                           (map (lambda (obj) (instantiate obj)) ancestors)))
+       (make-method! self instantiate (lambda (self) self))
+       self)
+     
+     (define who (make-generic-method))
+     (define imigrate! (make-generic-method))
+     (define emigrate! (make-generic-method))
+     (define describe (make-generic-method))
+     (define name (make-generic-method))
+     (define address (make-generic-method))
+     (define members (make-generic-method))
+     
+     (define society
+       (let ()
+         (define self (make-instance-object))
+         (define population '())
+         (make-method! self imigrate!
+                       (lambda (new-person)
+                         (if (not (eq? new-person self))
+                             (set! population (cons new-person population)))))
+         (make-method! self emigrate!
+                       (lambda (person)
+                         (if (not (eq? person self))
+                             (set! population
+                                   (comlist:remove-if (lambda (member)
+                                                        (eq? member person))
+                                                      population)))))
+         (make-method! self describe
+                       (lambda (self)
+                         (map (lambda (person) (describe person)) population)))
+         (make-method! self who
+                       (lambda (self) (map (lambda (person) (name person))
+                                           population)))
+         (make-method! self members (lambda (self) population))
+         self))
+     
+     (define (make-person %name %address)
+       (define self (make-instance-object society))
+       (make-method! self name (lambda (self) %name))
+       (make-method! self address (lambda (self) %address))
+       (make-method! self who (lambda (self) (name self)))
+       (make-method! self instantiate
+                     (lambda (self)
+                       (make-person (string-append (name self) "-son-of")
+                                    %address)))
+       (make-method! self describe
+                     (lambda (self) (list (name self) (address self))))
+       (imigrate! self)
+       self)
+
+Inverter Documentation
+......................
+
+  Inheritance:
+             <inverter>::(<number> <description>)
+  Generic-methods
+             <inverter>::value      => <number>::value
+             <inverter>::set-value! => <number>::set-value!
+             <inverter>::describe   => <description>::describe
+             <inverter>::help
+             <inverter>::invert
+             <inverter>::inverter?
+
+Number Documention
+..................
+
+  Inheritance
+             <number>::()
+  Slots
+             <number>::<x>
+  Generic Methods
+             <number>::value
+             <number>::set-value!
+
+Inverter code
+.............
+
+     (require 'object)
+     
+     (define value (make-generic-method (lambda (val) val)))
+     (define set-value! (make-generic-method))
+     (define invert (make-generic-method
+                     (lambda (val)
+                       (if (number? val)
+                           (/ 1 val)
+                           (error "Method not supported:" val)))))
+     (define noop (make-generic-method))
+     (define inverter? (make-generic-predicate))
+     (define describe (make-generic-method))
+     (define help (make-generic-method))
+     
+     (define (make-number x)
+       (define self (make-object))
+       (make-method! self value (lambda (this) x))
+       (make-method! self set-value!
+                     (lambda (this new-value) (set! x new-value)))
+       self)
+     
+     (define (make-description str)
+       (define self (make-object))
+       (make-method! self describe (lambda (this) str))
+       (make-method! self help (lambda (this) "Help not available"))
+       self)
+     
+     (define (make-inverter)
+       (define self (make-object
+                     (make-number 1)
+                     (make-description "A number which can be inverted")))
+       (define <value> (get-method self value))
+       (make-method! self invert (lambda (self) (/ 1 (<value> self))))
+       (make-predicate! self inverter?)
+       (unmake-method! self help)
+       (make-method! self help
+                     (lambda (self)
+                       (display "Inverter Methods:") (newline)
+                       (display "  (value inverter) ==> n") (newline)))
+       self)
+     
+     ;;;; Try it out
+     
+     (define invert! (make-generic-method))
+     
+     (define x (make-inverter))
+     
+     (make-method! x invert! (lambda () (set-value! x (/ 1 (value x)))))
+     
+     (value x)                       => 1
+     (set-value! x 33)               => undefined
+     (invert! x)                     => undefined
+     (value x)                       => 1/33
+     
+     (unmake-method! x invert!)      => undefined
+     
+     (invert! x)                     error-->  ERROR: Method not supported: x
+
+
+File: slib.info,  Node: Parameter lists,  Next: Priority Queues,  Prev: Object,  Up: Data Structures
+
+Parameter lists
+===============
+
+  `(require 'parameters)'
+
+Arguments to procedures in scheme are distinguished from each other by
+their position in the procedure call.  This can be confusing when a
+procedure takes many arguments, many of which are not often used.
+
+A "parameter-list" is a way of passing named information to a
+procedure.  Procedures are also defined to set unused parameters to
+default values, check parameters, and combine parameter lists.
+
+A PARAMETER has the form `(parameter-name value1 ...)'.  This format
+allows for more than one value per parameter-name.
+
+A PARAMETER-LIST is a list of PARAMETERs, each with a different
+PARAMETER-NAME.
+
+ - Function: make-parameter-list PARAMETER-NAMES
+     Returns an empty parameter-list with slots for PARAMETER-NAMES.
+
+ - Function: parameter-list-ref PARAMETER-LIST PARAMETER-NAME
+     PARAMETER-NAME must name a valid slot of PARAMETER-LIST.
+     `parameter-list-ref' returns the value of parameter PARAMETER-NAME
+     of PARAMETER-LIST.
+
+ - Procedure: adjoin-parameters! PARAMETER-LIST PARAMETER1 ...
+     Returns PARAMETER-LIST with PARAMETER1 ... merged in.
+
+ - Procedure: parameter-list-expand EXPANDERS PARAMETER-LIST
+     EXPANDERS is a list of procedures whose order matches the order of
+     the PARAMETER-NAMEs in the call to `make-parameter-list' which
+     created PARAMETER-LIST.  For each non-false element of EXPANDERS
+     that procedure is mapped over the corresponding parameter value
+     and the returned parameter lists are merged into PARAMETER-LIST.
+
+     This process is repeated until PARAMETER-LIST stops growing.  The
+     value returned from `parameter-list-expand' is unspecified.
+
+ - Function: fill-empty-parameters DEFAULTS PARAMETER-LIST
+     DEFAULTS is a list of lists whose order matches the order of the
+     PARAMETER-NAMEs in the call to `make-parameter-list' which created
+     PARAMETER-LIST.  `fill-empty-parameters' returns a new
+     parameter-list with each empty parameter filled with the
+     corresponding DEFAULT.
+
+ - Function: check-parameters CHECKS PARAMETER-LIST
+     CHECKS is a list of procedures whose order matches the order of
+     the PARAMETER-NAMEs in the call to `make-parameter-list' which
+     created PARAMETER-LIST.
+
+     `check-parameters' returns PARAMETER-LIST if each CHECK of the
+     corresponding PARAMETER-LIST returns non-false.  If some CHECK
+     returns `#f' an error is signaled.
+
+In the following procedures ARITIES is a list of symbols.  The elements
+of `arities' can be:
+
+`single'
+     Requires a single parameter.
+
+`optional'
+     A single parameter or no parameter is acceptable.
+
+`boolean'
+     A single boolean parameter or zero parameters is acceptable.
+
+`nary'
+     Any number of parameters are acceptable.
+
+`nary1'
+     One or more of parameters are acceptable.
+
+ - Function: parameter-list->arglist POSITIONS ARITIES TYPES
+          PARAMETER-LIST
+     Returns PARAMETER-LIST converted to an argument list.  Parameters
+     of ARITY type `single' and `boolean' are converted to the single
+     value associated with them.  The other ARITY types are converted
+     to lists of the value(s) of type TYPES.
+
+     POSITIONS is a list of positive integers whose order matches the
+     order of the PARAMETER-NAMEs in the call to `make-parameter-list'
+     which created PARAMETER-LIST.  The integers specify in which
+     argument position the corresponding parameter should appear.
+
+ - Function: getopt->parameter-list ARGC ARGV OPTNAMES ARITIES TYPES
+          ALIASES
+     Returns ARGV converted to a parameter-list.  OPTNAMES are the
+     parameter-names.  ALIASES is a list of lists of strings and
+     elements of OPTNAMES.  Each of these strings which have length of
+     1 will be treated as a single - option by `getopt'.  Longer
+     strings will be treated as long-named options (*note getopt-:
+     Getopt.).
+
+ - Function: getopt->arglist ARGC ARGV OPTNAMES POSITIONS ARITIES TYPES
+          DEFAULTS CHECKS ALIASES
+     Like `getopt->parameter-list', but converts ARGV to an
+     argument-list as specified by OPTNAMES, POSITIONS, ARITIES, TYPES,
+     DEFAULTS, CHECKS, and ALIASES.
+
+  These `getopt' functions can be used with SLIB relational databases.
+For an example, *Note make-command-server: Database Utilities.
+
+
+File: slib.info,  Node: Priority Queues,  Next: Queues,  Prev: Parameter lists,  Up: Data Structures
+
+Priority Queues
+===============
+
+  `(require 'priority-queue)'
+
+ - Function: make-heap PRED<?
+     Returns a binary heap suitable which can be used for priority queue
+     operations.
+
+ - Function: heap-length HEAP
+     Returns the number of elements in HEAP.
+
+ - Procedure: heap-insert! HEAP ITEM
+     Inserts ITEM into HEAP.  ITEM can be inserted multiple times.  The
+     value returned is unspecified.
+
+ - Function: heap-extract-max! HEAP
+     Returns the item which is larger than all others according to the
+     PRED<? argument to `make-heap'.  If there are no items in HEAP, an
+     error is signaled.
+
+  The algorithm for priority queues was taken from `Introduction to
+Algorithms' by T. Cormen, C. Leiserson, R. Rivest.  1989 MIT Press.
+
+
+File: slib.info,  Node: Queues,  Next: Records,  Prev: Priority Queues,  Up: Data Structures
+
+Queues
+======
+
+  `(require 'queue)'
+
+  A "queue" is a list where elements can be added to both the front and
+rear, and removed from the front (i.e., they are what are often called
+"dequeues").  A queue may also be used like a stack.
+
+ - Function: make-queue
+     Returns a new, empty queue.
+
+ - Function: queue? OBJ
+     Returns `#t' if OBJ is a queue.
+
+ - Function: queue-empty? Q
+     Returns `#t' if the queue Q is empty.
+
+ - Procedure: queue-push! Q DATUM
+     Adds DATUM to the front of queue Q.
+
+ - Procedure: enquque! Q DATUM
+     Adds DATUM to the rear of queue Q.
+
+  All of the following functions raise an error if the queue Q is empty.
+
+ - Function: queue-front Q
+     Returns the datum at the front of the queue Q.
+
+ - Function: queue-rear Q
+     Returns the datum at the rear of the queue Q.
+
+ - Prcoedure: queue-pop! Q
+ - Procedure: dequeue! Q
+     Both of these procedures remove and return the datum at the front
+     of the queue.  `queue-pop!' is used to suggest that the queue is
+     being used like a stack.
+