Go to the previous, next section.

# 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.

## 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)).

## 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.

## 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 (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.

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` (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
```

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.

Setter: list-ref

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
((eq? key (caar table))
(let ( (value (cdar table)) )
(set! table (cdr table))
value)
)
(else
(let loop ( (last table) (this (cdr table)) )
(cond
((null? this)
((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)
)
) ) )
```

## 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.

## 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.

## 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"
=> ("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")
```

## 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}"

```

## Macroless Object System

`(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.

### 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 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 self (make-instance-object society))
(make-method! self name (lambda (self) %name))
(make-method! self who (lambda (self) (name self)))
(make-method! self instantiate
(lambda (self)
(make-person (string-append (name self) "-son-of")
(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
```

## 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.

## 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.

## Records

`(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.

Function: record? obj

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.

## Base Table

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.

Function: sync-base lldb

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.

Function: close-base lldb

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.

Constant: catalog-id

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.

Function: present? handle key

Returns a non-`#f` value if there is a row associated with key in the table opened in handle and `#f` otherwise.

Function: delete handle key

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`
Scheme exact integer.
`symbol`
Scheme symbol.
`boolean`
`#t` or `#f`.
`base-id`
Objects suitable for passing as the base-id parameter to `open-table`. The value of catalog-id must be an acceptable `base-id`.

## Relational Database

`(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.

### Motivations

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:

• Tables, fields, domains, and types can be dealt with by name in programs.
• The underlying database implementation can be changed (for performance or other reasons) by changing a single line of code.
• The formats of tables can be easily extended or changed without altering code.
• Consistency checks are specified as part of the table descriptions. Changes in checks need only occur in one place.
• All the configuration information which the developer wishes to group together is easily grouped, without needing to change programs aware of only some of these tables.
• Generalized report generators, interactive entry programs, and other database utilities can be part of a shared library. The burden of adding configurability to a program is greatly reduced.
• Scheme is the "comprehensive language" for these databases. Scripting for configuration no longer needs to be in a separate language with additional documentation.
• Scheme's latent types mesh well with the strict typing and logical requirements of the relational model.
• Portable formats allow easy interchange of data. The included table descriptions help prevent misinterpretation of format.

### Creating and Opening Relational Databases

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 `require`ing 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.

### Relational Database Operations

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))
```

Function: close-database

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?.

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`.

Function: create-view ??

Function: project-table ??

Function: restrict-table ??

Function: cart-prod-tables ??

Not yet implemented.

### Table Operations

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.

Function: get key1 key2 ...

Returns the value for the specified column of the row associated with primary keys key1, key2 ... if it exists, or `#f` otherwise.

Function: get*

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.

Function: row:retrieve*

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.

Function: row:remove*

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.

Function: row:delete*

Deletes all rows in this table. The value returned is unspecified. The descriptor table and catalog entry for this table are not affected.

Function: row:update row

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.

Function: row:update* rows

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.

Function: row:insert row

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.

Function: row:insert* rows

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.

Function: for-each-row proc

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.

Function: close-table

Subsequent operations to this table will signal an error.

Constant: column-names

Constant: column-foreigns

Constant: column-domains

Constant: column-types

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.

### Catalog Representation

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>
```

### Unresolved Issues

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:

Process scope
The actions captured by a transaction should be only for the process which invoked the start of transaction. Although standard Scheme does not provide process primitives as such, `dynamic-wind` would provide a workable hook into process switching for many implementations.
Shared utilities with state
Some shared utilities have state which should not be part of a transaction. An example would be calling a pseudo-random number generator. If the success of a transaction depended on the pseudo-random number and failed, the state of the generator would be set back. Subsequent calls would keep returning the same number and keep failing.

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.

## Red-Black Trees

`(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:

left-rotation-field-maintainer
right-rotation-field-maintainer
Invoked in rotations to maintain augmented fields. Args are X and Y. If you have no augmented fields that depend explicitly on the structure of the tree, make these null.

insertion-field-maintainer
Invoked in insertion to maintain fields. Invoked once, on node inserted after insertion is performed, but before rotations are performed to balance tree. May also be invoked in one case of deletion.

deletion-field-maintainer
Invoked in deletion to maintain fields. Invoked once, on node deleted after deletion is performed, but before rotations are performed to balance the tree. May be invoked on non-garbage nodes during deletion, where node is spliced out of one place and into another. The tree is always guaranteed connected from parent up.

prior?
prior? should be a binary predicate used for totally ordering the data fields of nodes. The name prior? is just a mnemonic aid; it means that if the predicate is successful the first arg should go to the left of the second arg, where left is in tree fields.

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.

Function: make-rb-node data

Makes a node (suitable for insertion with `rb-insert!`) with datum data.

## Structures

`(require 'struct)` for defmacros. `(require 'structure)` for syntax-case macros.

`defmacro`s 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.