diff options
Diffstat (limited to 'slib.info-1')
| -rw-r--r-- | slib.info-1 | 1306 |
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. + |