summaryrefslogtreecommitdiffstats
path: root/slib.info-1
diff options
context:
space:
mode:
authorJim Pick <jim@jimpick.com>1998-03-08 23:05:22 -0800
committerBryan Newbold <bnewbold@robocracy.org>2017-02-20 00:05:27 -0800
commitb21cac3362022718634f7086964208b2eed8e897 (patch)
tree16f4b2e70645c0e8e2202023170b5a94baa967e3 /slib.info-1
parent3796d2595035e192ed4bf1c9a6bfdb13c3c9d261 (diff)
parentf24b9140d6f74804d5599ec225717d38ca443813 (diff)
downloadslib-b21cac3362022718634f7086964208b2eed8e897.tar.gz
slib-b21cac3362022718634f7086964208b2eed8e897.zip
Import Debian changes 2c0-3debian/2c0-3
slib (2c0-3) unstable; urgency=low * New maintainer. * slibconfig script to automatically configure guile. * Fix type in description, closes: Bug#18996 slib (2c0-2) unstable; urgency=low * Minor fix for debian/rules targets slib (2c0-1) unstable; urgency=low * New upstream source * New maintainer
Diffstat (limited to 'slib.info-1')
-rw-r--r--slib.info-11306
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.
-