summaryrefslogtreecommitdiffstats
path: root/slib.info-1
diff options
context:
space:
mode:
Diffstat (limited to 'slib.info-1')
-rw-r--r--slib.info-11306
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.
+