diff options
Diffstat (limited to 'slib.info-1')
| -rw-r--r-- | slib.info-1 | 1306 |
1 files changed, 0 insertions, 1306 deletions
diff --git a/slib.info-1 b/slib.info-1 deleted file mode 100644 index 89c4fce..0000000 --- a/slib.info-1 +++ /dev/null @@ -1,1306 +0,0 @@ -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. - |