Go to the previous, next section.
(require 'array)
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
Returns the number of dimensions of obj. If obj is not an array, 0 is returned.
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.
(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.
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)).
(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.
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))
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.
(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 (See section 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.
for-each-key and
for-each-elt operations.
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
(See section Lists as sequences) to collections which will shadow the
list-based version if (require 'collect) follows (require
'common-list-functions) (See section 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 (See section 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 (See section Lists as sequences) to collections.
Example:
(every? collection? '((1 2) #(1 2))) => #t
Returns #t iff there are no elements in collection.
(empty? collection) == (zero? (size collection))
Returns the number of elements in collection.
See See section 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)
)
) ) )
(require 'dynamic)
Create and returns a new dynamic whose global value is obj.
Returns true if and only if obj is a dynamic. No object
satisfying dynamic? satisfies any of the other standard type
predicates.
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.
(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.
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.
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.
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.
(require 'hash)
These hashing functions are for use in quickly classifying objects. Hash tables use these functions.
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:
(require 'soundex)
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")
(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}"
(require 'object)
This is the Macroless Object System written by Wade Humeniuk (whumeniu@datap.ca). Conceptual Tributes: section Yasos, MacScheme's %object, CLOS, Lack of R4RS macros.
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.
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 ...).
#t.
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.
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.
(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>::(<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>::()
Slots
<number>::<x>
Generic Methods
<number>::value
<number>::set-value!
(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
(require 'priority-queue)
Returns a binary heap suitable which can be used for priority queue operations.
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.
(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.
Returns a new, empty queue.
Returns #t if obj is a queue.
Returns #t if the queue q is empty.
Procedure: queue-push! q datum
Adds datum to the front of queue q.
Adds datum to the rear of queue q.
All of the following functions raise an error if the queue q is empty.
Returns the datum at the front of the queue q.
Returns the datum at the rear of the queue 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.
(require 'record)
The Record package provides a facility for user to define their own record data types.
Function: make-record-type type-name field-names
Returns a record-type descriptor, a value representing a new data type disjoint from all others. The type-name argument must be a string, but is only used for debugging purposes (such as the printed representation of a record of the new type). The field-names argument is a list of symbols naming the fields of a record of the new type. It is an error if the list contains any duplicates. It is unspecified how record-type descriptors are represented.
Function: record-constructor rtd [field-names]
Returns a procedure for constructing new members of the type represented
by rtd. The returned procedure accepts exactly as many arguments
as there are symbols in the given list, field-names; these are
used, in order, as the initial values of those fields in a new record,
which is returned by the constructor procedure. The values of any
fields not named in that list are unspecified. The field-names
argument defaults to the list of field names in the call to
make-record-type that created the type represented by rtd;
if the field-names argument is provided, it is an error if it
contains any duplicates or any symbols not in the default list.
Function: record-predicate rtd
Returns a procedure for testing membership in the type represented by rtd. The returned procedure accepts exactly one argument and returns a true value if the argument is a member of the indicated record type; it returns a false value otherwise.
Function: record-accessor rtd field-name
Returns a procedure for reading the value of a particular field of a
member of the type represented by rtd. The returned procedure
accepts exactly one argument which must be a record of the appropriate
type; it returns the current value of the field named by the symbol
field-name in that record. The symbol field-name must be a
member of the list of field-names in the call to make-record-type
that created the type represented by rtd.
Function: record-modifier rtd field-name
Returns a procedure for writing the value of a particular field of a
member of the type represented by rtd. The returned procedure
accepts exactly two arguments: first, a record of the appropriate type,
and second, an arbitrary Scheme value; it modifies the field named by
the symbol field-name in that record to contain the given value.
The returned value of the modifier procedure is unspecified. The symbol
field-name must be a member of the list of field-names in the call
to make-record-type that created the type represented by
rtd.
Returns a true value if obj is a record of any type and a false
value otherwise. Note that record? may be true of any Scheme
value; of course, if it returns true for some particular value, then
record-type-descriptor is applicable to that value and returns an
appropriate descriptor.
Function: record-type-descriptor record
Returns a record-type descriptor representing the type of the given
record. That is, for example, if the returned descriptor were passed to
record-predicate, the resulting predicate would return a true
value when passed the given record. Note that it is not necessarily the
case that the returned descriptor is the one that was passed to
record-constructor in the call that created the constructor
procedure that created the given record.
Function: record-type-name rtd
Returns the type-name associated with the type represented by rtd. The
returned value is eqv? to the type-name argument given in
the call to make-record-type that created the type represented by
rtd.
Function: record-type-field-names rtd
Returns a list of the symbols naming the fields in members of the type
represented by rtd. The returned value is equal? to the
field-names argument given in the call to make-record-type that
created the type represented by rtd.
A base table implementation using Scheme association lists is available
as the value of the identifier alist-table after doing:
(require 'alist-table)
Association list base tables are suitable for small databases and support all Scheme types when temporary and readable/writeable Scheme types when saved. I hope support for other base table implementations will be added in the future.
This rest of this section documents the interface for a base table implementation from which the section Relational Database package constructs a Relational system. It will be of interest primarily to those wishing to port or write new base-table implementations.
All of these functions are accessed through a single procedure by
calling that procedure with the symbol name of the operation. A
procedure will be returned if that operation is supported and #f
otherwise. For example:
(require 'alist-table) (define open-base (alist-table 'make-base)) make-base => *a procedure* (define foo (alist-table 'foo)) foo => #f
Function: make-base filename key-dimension column-types
Returns a new, open, low-level database (collection of tables)
associated with filename. This returned database has an empty
table associated with catalog-id. The positive integer
key-dimension is the number of keys composed to make a
primary-key for the catalog table. The list of symbols
column-types describes the types of each column for that table.
If the database cannot be created as specified, #f is returned.
Calling the close-base method on this database and possibly other
operations will cause filename to be written to. If
filename is #f a temporary, non-disk based database will be
created if such can be supported by the base table implelentation.
Function: open-base filename mutable
Returns an open low-level database associated with filename. If
mutable? is #t, this database will have methods capable of
effecting change to the database. If mutable? is #f, only
methods for inquiring the database will be available. If the database
cannot be opened as specified #f is returned.
Calling the close-base (and possibly other) method on a
mutable? database will cause filename to be written to.
Function: write-base lldb filename
Causes the low-level database lldb to be written to
filename. If the write is successful, also causes lldb to
henceforth be associated with filename. Calling the
close-database (and possibly other) method on lldb may
cause filename to be written to. If filename is #f
this database will be changed to a temporary, non-disk based database if
such can be supported by the underlying base table implelentation. If
the operations completed successfully, #t is returned.
Otherwise, #f is returned.
Causes the file associated with the low-level database lldb to be
updated to reflect its current state. If the associated filename is
#f, no action is taken and #f is returned. If this
operation completes successfully, #t is returned. Otherwise,
#f is returned.
Causes the low-level database lldb to be written to its associated
file (if any). If the write is successful, subsequent operations to
lldb will signal an error. If the operations complete
successfully, #t is returned. Otherwise, #f is returned.
Function: make-table lldb key-dimension column-types
Returns the base-id for a new base table, otherwise returns
#f. The base table can then be opened using (open-table
lldb base-id). The positive integer key-dimension is
the number of keys composed to make a primary-key for this table.
The list of symbols column-types describes the types of each
column.
A constant base-id suitable for passing as a parameter to
open-table. catalog-id will be used as the base table for
the system catalog.
Function: open-table lldb base-id key-dimension column-types
Returns a handle for an existing base table in the low-level
database lldb if that table exists and can be opened in the mode
indicated by mutable?, otherwise returns #f.
As with make-table, the positive integer key-dimension is
the number of keys composed to make a primary-key for this table.
The list of symbols column-types describes the types of each
column.
Function: kill-table lldb base-id key-dimension column-types
Returns #t if the base table associated with base-id was
removed from the low level database lldb, and #f otherwise.
Function: make-keyifier-1 type
Returns a procedure which accepts a single argument which must be of type type. This returned procedure returns an object suitable for being a key argument in the functions whose descriptions follow.
Any 2 arguments of the supported type passed to the returned function
which are not equal? must result in returned values which are not
equal?.
Function: make-list-keyifier key-dimension types
The list of symbols types must have at least key-dimension elements. Returns a procedure which accepts a list of length key-dimension and whose types must corresopond to the types named by types. This returned procedure combines the elements of its list argument into an object suitable for being a key argument in the functions whose descriptions follow.
Any 2 lists of supported types (which must at least include symbols and
non-negative integers) passed to the returned function which are not
equal? must result in returned values which are not
equal?.
Function: make-key-extractor key-dimension types column-number
Returns a procedure which accepts objects produced by application of the
result of (make-list-keyifier key-dimension types).
This procedure returns a key which is equal? to the
column-numberth element of the list which was passed to create
combined-key. The list types must have at least
key-dimension elements.
Function: make-key->list key-dimension types
Returns a procedure which accepts objects produced by application of the
result of (make-list-keyifier key-dimension types).
This procedure returns a list of keys which are elementwise
equal? to the list which was passed to create combined-key.
In the following functions, the key argument can always be assumed to be the value returned by a call to a keyify routine.
Function: for-each-key handle procedure
Calls procedure once with each key in the table opened in handle in an unspecified order. An unspecified value is returned.
Function: map-key handle procedure
Returns a list of the values returned by calling procedure once with each key in the table opened in handle in an unspecified order.
Function: ordered-for-each-key handle procedure
Calls procedure once with each key in the table opened in handle in the natural order for the types of the primary key fields of that table. An unspecified value is returned.
Returns a non-#f value if there is a row associated with
key in the table opened in handle and #f otherwise.
Removes the row associated with key from the table opened in handle. An unspecified value is returned.
Function: make-getter key-dimension types
Returns a procedure which takes arguments handle and key.
This procedure returns a list of the non-primary values of the relation
(in the base table opened in handle) whose primary key is
key if it exists, and #f otherwise.
Function: make-putter key-dimension types
Returns a procedure which takes arguments handle and key and value-list. This procedure associates the primary key key with the values in value-list (in the base table opened in handle) and returns an unspecified value.
Function: supported-type? symbol
Returns #t if symbol names a type allowed as a column value
by the implementation, and #f otherwise. At a minimum, an
implementation must support the types integer, symbol,
string, boolean, and base-id.
Function: supported-key-type? symbol
Returns #t if symbol names a type allowed as a key value by
the implementation, and #f otherwise. At a minimum, an
implementation must support the types integer, and symbol.
integer
symbol
boolean
#t or #f.
base-id
open-table. The value of catalog-id must be an acceptable
base-id.
(require 'relational-database)
This package implements a database system inspired by the Relational Model (E. F. Codd, A Relational Model of Data for Large Shared Data Banks). An SLIB relational database implementation can be created from any section Base Table implementation.
Most nontrivial programs contain databases: Makefiles, configure scripts, file backup, calendars, editors, source revision control, CAD systems, display managers, menu GUIs, games, parsers, debuggers, profilers, and even error reporting are all rife with databases. Coding databases is such a common activity in programming that many may not be aware of how often they do it.
A database often starts as a dispatch in a program. The author, perhaps because of the need to make the dispatch configurable, the need for correlating dispatch in other routines, or because of changes or growth, devises a data structure to contain the information, a routine for interpreting that data structure, and perhaps routines for augmenting and modifying the stored data. The dispatch must be converted into this form and tested.
The programmer may need to devise an interactive program for enabling easy examination and modification of the information contained in this database. Often, in an attempt to foster modularity and avoid delays in release, intermediate file formats for the database information are devised. It often turns out that users prefer modifying these intermediate files with a text editor to using the interactive program in order to do operations (such as global changes) not forseen by the program's author.
In order to address this need, the concientous software engineer may even provide a scripting language to allow users to make repetitive database changes. Users will grumble that they need to read a large manual and learn yet another programming language (even if it almost has language "xyz" syntax) in order to do simple configuration.
All of these facilities need to be designed, coded, debugged, documented, and supported; often causing what was very simple in concept to become a major developement project.
This view of databases just outlined is somewhat the reverse of the view of the originators of the Relational Model of database abstraction. The relational model was devised to unify and allow interoperation of large multi-user databases running on diverse platforms. A fairly general purpose "Comprehensive Language" for database manipulations is mandated (but not specified) as part of the relational model for databases.
One aspect of the Relational Model of some importance is that the "Comprehensive Language" must be expressible in some form which can be stored in the database. This frees the programmer from having to make programs data-driven in order to use a database.
This package includes as one of its basic supported types Scheme
expressions. This type allows expressions as defined by the
Scheme standards to be stored in the database. The expressions are
evaluated (in the top-level environment) when retrieved. Scheme's
lambda facilitates closure of environments, modularity, etc. so
that procedures (which could not be stored directly) can be retrieved.
Since expressions are evaluated in the top-level environment, built-in
and user defined procedures can be easily accessed by name.
This package's purpose is to standardize (through a common interface) database creation and usage in Scheme programs. The relational model's provision for inclusion of language expressions as data as well as the description (in tables, of course) of all of its tables assures that relational databases are powerful enough to assume the roles currently played by thousands of ad-hoc routines and data formats.
Such standardization to a relational-like model brings many benefits:
Function: make-relational-system base-table-implementation
Returns a procedure implementing a relational database using the base-table-implementation.
All of the operations of a base table implementation are accessed
through a procedure defined by requireing that implementation.
Similarly, all of the operations of the relational database
implementation are accessed through the procedure returned by
make-relational-system. For instance, a new relational database
could be created from the procedure returned by
make-relational-system by:
(require 'alist-table)
(define relational-alist-system
(make-relational-system alist-table))
(define create-alist-database
(relational-alist-system 'create-database))
(define my-database
(create-alist-database "mydata.db"))
What follows are the descriptions of the methods available from
relational system returned by a call to make-relational-system.
Function: create-database filename
Returns an open, nearly empty relational database associated with
filename. The only tables defined are the system catalog and
domain table. Calling the close-database method on this database
and possibly other operations will cause filename to be written
to. If filename is #f a temporary, non-disk based database
will be created if such can be supported by the underlying base table
implelentation. If the database cannot be created as specified
#f is returned. For the fields and layout of descriptor tables,
See section Catalog Representation
Function: open-database filename mutable?
Returns an open relational database associated with filename. If
mutable? is #t, this database will have methods capable of
effecting change to the database. If mutable? is #f, only
methods for inquiring the database will be available. Calling the
close-database (and possibly other) method on a mutable?
database will cause filename to be written to. If the database
cannot be opened as specified #f is returned.
These are the descriptions of the methods available from an open relational database. A method is retrieved from a database by calling the database with the symbol name of the operation. For example:
(define my-database
(create-alist-database "mydata.db"))
(define telephone-table-desc
((my-database 'create-table) 'telephone-table-desc))
Causes the relational database to be written to its associated file (if
any). If the write is successful, subsequent operations to this
database will signal an error. If the operations completed
successfully, #t is returned. Otherwise, #f is returned.
Function: write-database filename
Causes the relational database to be written to filename. If the
write is successful, also causes the database to henceforth be
associated with filename. Calling the close-database (and
possibly other) method on this database will cause filename to be
written to. If filename is #f this database will be
changed to a temporary, non-disk based database if such can be supported
by the underlying base table implelentation. If the operations
completed successfully, #t is returned. Otherwise, #f is
returned.
Function: table-exists? table-name
Returns #t if table-name exists in the system catalog,
otherwise returns #f.
Function: open-table table-name mutable?
Returns a methods procedure for an existing relational table in
this database if it exists and can be opened in the mode indicated by
mutable?, otherwise returns #f.
These methods will be present only in databases which are mutable?.
Function: add-domain domain-row
Adds domain-row to the domains table if there is no row in
the domains table associated with key (car domain-row) and
returns #t. Otherwise returns #f.
For the fields and layout of the domain table, See section Catalog Representation
Function: delete-domain domain-name
Removes and returns the domain-name row from the domains table.
Function: delete-table table-name
Removes and returns the table-name row from the system catalog if
the table or view associated with table-name gets removed from the
database, and #f otherwise.
Function: create-table table-desc-name
Returns a methods procedure for a new (open) relational table for
describing the columns of a new base table in this database, otherwise
returns #f. For the fields and layout of descriptor tables,
See section Catalog Representation.
Function: create-table table-name table-desc-name
Returns a methods procedure for a new (open) relational table with
columns as described by table-desc-name, otherwise returns
#f.
Not yet implemented.
These are the descriptions of the methods available from an open relational table. A method is retrieved from a table by calling the table with the symbol name of the operation. For example:
(define telephone-table-desc
((my-database 'create-table) 'telephone-table-desc))
(require 'common-list-functions)
(define ndrp (telephone-table-desc 'row:insert))
(ndrp '(1 #t name #f string))
(ndrp '(2 #f telephone
(lambda (d)
(and (string? d) (> (string-length d) 2)
(every
(lambda (c)
(memv c '(#\0 #\1 #\2 #\3 #\4 #\5 #\6 #\7 #\8 #\9
#\+ #\( #\ #\) #\-)))
(string->list d))))
string))
Operations on a single column of a table are retrieved by giving the column name as the second argument to the methods procedure. For example:
(define column-ids ((telephone-table-desc 'get* 'column-number)))
Some operations described below require primary key arguments. Primary keys arguments are denoted key1 key2 .... It is an error to call an operation for a table which takes primary key arguments with the wrong number of primary keys for that table.
The term row used below refers to a Scheme list of values (one for
each column) in the order specified in the descriptor (table) for this
table. Missing values appear as #f. Primary keys may not
be missing.
Returns the value for the specified column of the row associated with
primary keys key1, key2 ... if it exists, or #f
otherwise.
Returns a list of the values for the specified column for all rows in this table.
Function: row:retrieve key1 key2 ...
Returns the row associated with primary keys key1, key2
... if it exists, or #f otherwise.
Returns a list of all rows in this table.
Function: row:remove key1 key2 ...
Removes and returns the row associated with primary keys key1,
key2 ... if it exists, or #f otherwise.
Removes and returns a list of all rows in this table.
Function: row:delete key1 key2 ...
Deletes the row associated with primary keys key1, key2 ... if it exists. The value returned is unspecified.
Deletes all rows in this table. The value returned is unspecified. The descriptor table and catalog entry for this table are not affected.
Adds the row, row, to this table. If a row for the primary key(s) specified by row already exists in this table, it will be overwritten. The value returned is unspecified.
Adds each row in the list rows, to this table. If a row for the primary key specified by an element of rows already exists in this table, it will be overwritten. The value returned is unspecified.
Adds the row row to this table. If a row for the primary key(s) specified by row already exists in this table an error is signaled. The value returned is unspecified.
Adds each row in the list rows, to this table. If a row for the primary key specified by an element of rows already exists in this table, an error is signaled. The value returned is unspecified.
Calls proc with each row in this table in the natural ordering for the primary key types. Real relational programmers would use some least-upper-bound join for every row to get them in order; But we don't have joins yet.
Subsequent operations to this table will signal an error.
Return a list of the column names, foreign-key table names, domain names, or type names respectively for this table. These 4 methods are different from the others in that the list is returned, rather than a procedure to obtain the list. Constant: primary-limit
Returns the number of primary keys fields in the relations in this table.
Each database (in an implementation) has a system catalog which describes all the user accessible tables in that database (including itself).
The system catalog base table has the following fields. PRI
indicates a primary key for that table.
PRI table-name
column-limit the highest column number
coltab-name descriptor table name
bastab-id data base table identifier
user-integrity-rule
view-procedure A scheme thunk which, when called,
produces a handle for the view. coltab
and bastab are specified if and only if
view-procedure is not.
Descriptors for base tables (not views) are tables (pointed to by system catalog). Descriptor (base) tables have the fields:
PRI column-number sequential integers from 1
primary-key? boolean TRUE for primary key components
column-name
column-integrity-rule
domain-name
A primary key is any column marked as primary-key? in the
corresponding descriptor table. All the primary-key? columns
must have lower column numbers than any non-primary-key? columns.
Every table must have at least one primary key. Primary keys must be
sufficient to distinguish all rows from each other in the table. All of
the system defined tables have a single primary key.
This package currently supports tables having from 1 to 4 primary keys if there are non-primary columns, and any (natural) number if all columns are primary keys. If you need more than 4 primary keys, I would like to hear what you are doing!
A domain is a category describing the allowable values to occur in a column. It is described by a (base) table with the fields:
PRI domain-name
foreign-table
domain-integrity-rule
type-id
type-param
The type-id field value is a symbol. This symbol may be used by the underlying base table implementation in storing that field.
If the foreign-table field is non-#f then that field names
a table from the catalog. The values for that domain must match a
primary key of the table referenced by the type-param (or
#f, if allowed). This package currently does not support
composite foreign-keys.
The types for which support is planned are:
atom
symbol
string [<length>]
number [<base>]
money <currency>
date-time
boolean
foreign-key <table-name>
expression
virtual <expression>
Although `rdms.scm' is not large I found it very difficult to write (six rewrites). I am not aware of any other examples of a generalized relational system (although there is little new in CS). I left out several aspects of the Relational model in order to simplify the job. The major features lacking (which might be addressed portably) are views, transaction boundaries, and protection.
Protection needs a model for specifying priveledges. Given how operations are accessed from handles it should not be difficult to restrict table accesses to those allowed for that user.
The system catalog has a field called view-procedure. This
should allow a purely functional implementation of views. This will
work but is unsatisfying for views resulting from a selection
(subset of rows); for whole table operations it will not be possible to
reduce the number of keys scanned over when the selection is specified
only by an opaque procedure.
Transaction boundaries present the most intriguing area. Transaction boundaries are actually a feature of the "Comprehensive Language" of the Relational database and not of the database. Scheme would seem to provide the opportunity for an extremely clean semantics for transaction boundaries since the builtin procedures with side effects are small in number and easily identified.
These side-effect builtin procedures might all be portably redefined to versions which properly handled transactions. Compiled library routines would need to be recompiled as well. Many system extensions (delete-file, system, etc.) would also need to be redefined.
There are 2 scope issues that must be resolved for multiprocess transaction boundaries:
dynamic-wind would
provide a workable hook into process switching for many implementations.
Pseudo-random number generators are not reentrant and so would require locks in order to operate properly in a multiprocess environment. Are all examples of utilities whose state should not part of transactions also non-reentrant? If so, perhaps suspending transaction capture for the duration of locks would fix it.
(require 'red-black-tree)
This is an implementation of Red-Black trees in Scheme.
Function: make-rb-tree left-rotation-field-maintainer right-rotation-field-maintainer insertion-field-maintainer deletion-field-maintainer prior?
Makes an empty Red-Black tree based on the arguments:
Procedure: rb-delete! tree node
Deletes node from tree. The node that is actually deleted may not be the one passed in, so if a resource is being maintained, what should be put back on the freelist is the node returned by this procedure.
Function: rb-node-successor node
Function: rb-node-predecessor node
Return the successor and predecessor (as determined by the
prior? argument to make-rb-tree) from the tree of which
node is a member.
Function: rb-node-maximum node
Function: rb-node-minimum node
Return the minimum and maximum nodes in the tree of which node is a member.
Function: rb-tree-maximum tree
Function: rb-tree-minimum tree
Return the minimum and maximum nodes in tree.
Procedure: rb-insert! tree node
Inserts node in tree. The value returned is unspecified.
Makes a node (suitable for insertion with rb-insert!) with datum
data.
(require 'struct) for defmacros.
(require 'structure) for syntax-case macros.
defmacros which implement records from the book
Essentials of Programming Languages by Daniel P. Friedman, M.
Wand and C.T. Haynes. Copyright 1992 Jeff Alexander, Shinnder Lee, and
Lewis Patterson
Macro: define-record tag (var1 var2 ...)
Defines several functions pertaining to record-name tag: make-tag, tag?, and tag->var1.
Macro: variant-case exp (tag (var1 var2 ...) body) ...
executes the following for the matching clause:
((lambda (var1 var ...) body) (tag->var1 exp) (tag->var2 exp) ...)
Go to the previous, next section.