Other Packages

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 index1 index2
Function: array-3d-ref array index1 index2 index3

Procedure: array-1d-set! array new-value index
Procedure: array-2d-set! array new-value index1 index2
Procedure: array-3d-set! array new-value index1 index2 index3

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

Function: array-index-map! array proc
applies proc to the indices of each element of array in turn, storing the result in the corresponding element. The value returned and the order of application are unspecified.

One can implement array-indexes as

```(define (array-indexes array)
(let ((ra (apply make-array #f (array-shape array))))
(array-index-map! ra (lambda x x))
ra))
```

Another example:

```(define (apl:index-generator n)
(let ((v (make-uniform-vector n 1)))
(array-index-map! v (lambda (i) i))
v))
```

Function: array-copy! source destination
Copies every element from vector or array source to the corresponding element of destination. destination must have the same rank as source, and be at least as large in each dimension. The order of copying is unspecified.

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.

Byte

`(require 'byte)`

Some algorithms are expressed in terms of arrays of small integers. Using Scheme strings to implement these arrays is not portable vis-a-vis the correspondence between integers and characters and non-ascii character sets. These functions abstract the notion of a byte.

Function: byte-ref bytes k
k must be a valid index of bytes. `byte-ref` returns byte k of bytes using zero-origin indexing.

Procedure: byte-set! bytes k byte
k must be a valid index of bytes%, and byte must be a small integer. `Byte-set!` stores byte in element k of bytes and returns an unspecified value.

Function: make-bytes k
Function: make-bytes k byte

`Make-bytes` returns a newly allocated byte-array of length k. If byte is given, then all elements of the byte-array are initialized to byte, otherwise the contents of the byte-array are unspecified.

Function: bytes-length bytes

`bytes-length` returns length of byte-array bytes.

Function: write-byte byte
Function: write-byte byte port

Writes the byte byte (not an external representation of the byte) to the given port and returns an unspecified value. The port argument may be omitted, in which case it defaults to the value returned by `current-output-port`.

Returns the next byte available from the input port, updating the port to point to the following byte. If no more bytes are available, an end of file object is returned. Port may be omitted, in which case it defaults to the value returned by `current-input-port`.

Function: bytes byte ...

Returns a newly allocated byte-array composed of the arguments.

Function: bytes->list bytes
Function: list->bytes bytes

`Bytes->list` returns a newly allocated list of the bytes that make up the given byte-array. `List->bytes` returns a newly allocated byte-array formed from the small integers in the list bytes. `Bytes->list` and `list->bytes` are inverses so far as `equal?` is concerned.

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.

Function: 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")
```

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.

In May of 1996, as a product of discussion on the `rrrs-authors` mailing list, I rewrote `record.scm' to portably implement type disjointness for record data types.

As long as an implementation's procedures are opaque and the `record` code is loaded before other programs, this will give disjoint record types which are unforgeable and incorruptible by R4RS procedures.

As a consequence, the procedures `record?`, `record-type-descriptor`, `record-type-name`.and `record-type-field-names` are no longer supported.

Structures

`(require 'struct)` (uses defmacros)

`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

Matthew McDonald <mafm@cs.uwa.edu.au> added field setters.

Macro: define-record tag (var1 var2 ...)
Defines several functions pertaining to record-name tag:

Function: make-tag var1 var2 ...
Function: tag? obj
Function: tag->var1 obj
Function: tag->var2 obj
...
Function: set-tag-var1! obj val
Function: set-tag-var2! obj val
...

Here is an example of its use.

```(define-record term (operator left right))
=> #<unspecified>
(define foo (make-term 'plus  1 2))
=> foo
(term->left foo)
=> 1
(set-term-left! foo 2345)
=> #<unspecified>
(term->left foo)
=> 2345
```

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

Procedures

Anything that doesn't fall neatly into any of the other categories winds up here.

Common List Functions

`(require 'common-list-functions)`

The procedures below follow the Common LISP equivalents apart from optional arguments in some cases.

List construction

Function: make-list k . init
`make-list` creates and returns a list of k elements. If init is included, all elements in the list are initialized to init.

Example:

```(make-list 3)
=> (#<unspecified> #<unspecified> #<unspecified>)
(make-list 5 'foo)
=> (foo foo foo foo foo)
```

Function: list* x . y
Works like `list` except that the cdr of the last pair is the last argument unless there is only one argument, when the result is just that argument. Sometimes called `cons*`. E.g.:
```(list* 1)
=> 1
(list* 1 2 3)
=> (1 2 . 3)
(list* 1 2 '(3 4))
=> (1 2 3 4)
(list* args '())
== (list args)
```

Function: copy-list lst
`copy-list` makes a copy of lst using new pairs and returns it. Only the top level of the list is copied, i.e., pairs forming elements of the copied list remain `eq?` to the corresponding elements of the original; the copy is, however, not `eq?` to the original, but is `equal?` to it.

Example:

```(copy-list '(foo foo foo))
=> (foo foo foo)
(define q '(foo bar baz bang))
(define p q)
(eq? p q)
=> #t
(define r (copy-list q))
(eq? q r)
=> #f
(equal? q r)
=> #t
(define bar '(bar))
(eq? bar (car (copy-list (list bar 'foo))))
=> #t
@end lisp
```

Lists as sets

`eqv?` is used to test for membership by procedures which treat lists as sets.

`adjoin` returns the adjoint of the element e and the list l. That is, if e is in l, `adjoin` returns l, otherwise, it returns `(cons e l)`.

Example:

```(adjoin 'baz '(bar baz bang))
=> (bar baz bang)
=> (foo bar baz bang)
```

Function: union l1 l2
`union` returns the combination of l1 and l2. Duplicates between l1 and l2 are culled. Duplicates within l1 or within l2 may or may not be removed.

Example:

```(union '(1 2 3 4) '(5 6 7 8))
=> (4 3 2 1 5 6 7 8)
(union '(1 2 3 4) '(3 4 5 6))
=> (2 1 3 4 5 6)
```

Function: intersection l1 l2
`intersection` returns all elements that are in both l1 and l2.

Example:

```(intersection '(1 2 3 4) '(3 4 5 6))
=> (3 4)
(intersection '(1 2 3 4) '(5 6 7 8))
=> ()
```

Function: set-difference l1 l2
`set-difference` returns the union of all elements that are in l1 but not in l2.

Example:

```(set-difference '(1 2 3 4) '(3 4 5 6))
=> (1 2)
(set-difference '(1 2 3 4) '(1 2 3 4 5 6))
=> ()
```

Function: member-if pred lst
`member-if` returns lst if `(pred element)` is `#t` for any element in lst. Returns `#f` if pred does not apply to any element in lst.

Example:

```(member-if vector? '(1 2 3 4))
=> #f
(member-if number? '(1 2 3 4))
=> (1 2 3 4)
```

Function: some pred lst . more-lsts
pred is a boolean function of as many arguments as there are list arguments to `some` i.e., lst plus any optional arguments. pred is applied to successive elements of the list arguments in order. `some` returns `#t` as soon as one of these applications returns `#t`, and is `#f` if none returns `#t`. All the lists should have the same length.

Example:

```(some odd? '(1 2 3 4))
=> #t

(some odd? '(2 4 6 8))
=> #f

(some > '(2 3) '(1 4))
=> #f
```

Function: every pred lst . more-lsts
`every` is analogous to `some` except it returns `#t` if every application of pred is `#t` and `#f` otherwise.

Example:

```(every even? '(1 2 3 4))
=> #f

(every even? '(2 4 6 8))
=> #t

(every > '(2 3) '(1 4))
=> #f
```

Function: notany pred . lst
`notany` is analogous to `some` but returns `#t` if no application of pred returns `#t` or `#f` as soon as any one does.

Function: notevery pred . lst
`notevery` is analogous to `some` but returns `#t` as soon as an application of pred returns `#f`, and `#f` otherwise.

Example:

```(notevery even? '(1 2 3 4))
=> #t

(notevery even? '(2 4 6 8))
=> #f
```

Function: find-if pred lst
`find-if` searches for the first element in lst such that `(pred element)` returns `#t`. If it finds any such element in lst, element is returned. Otherwise, `#f` is returned.

Example:

```(find-if number? '(foo 1 bar 2))
=> 1

(find-if number? '(foo bar baz bang))
=> #f

(find-if symbol? '(1 2 foo bar))
=> foo
```

Function: remove elt lst
`remove` removes all occurrences of elt from lst using `eqv?` to test for equality and returns everything that's left. N.B.: other implementations (Chez, Scheme->C and T, at least) use `equal?` as the equality test.

Example:

```(remove 1 '(1 2 1 3 1 4 1 5))
=> (2 3 4 5)

(remove 'foo '(bar baz bang))
=> (bar baz bang)
```

Function: remove-if pred lst
`remove-if` removes all elements from lst where `(pred element)` is `#t` and returns everything that's left.

Example:

```(remove-if number? '(1 2 3 4))
=> ()

(remove-if even? '(1 2 3 4 5 6 7 8))
=> (1 3 5 7)
```

Function: remove-if-not pred lst
`remove-if-not` removes all elements from lst for which `(pred element)` is `#f` and returns everything that's left.

Example:

```(remove-if-not number? '(foo bar baz))
=> ()
(remove-if-not odd? '(1 2 3 4 5 6 7 8))
=> (1 3 5 7)
```

Function: has-duplicates? lst
returns `#t` if 2 members of lst are `equal?`, `#f` otherwise.

Example:

```(has-duplicates? '(1 2 3 4))
=> #f

(has-duplicates? '(2 4 3 4))
=> #t
```

The procedure `remove-duplicates` uses `member` (rather than `memv`).

Function: remove-duplicates lst
returns a copy of lst with its duplicate members removed. Elements are considered duplicate if they are `equal?`.

Example:

```(remove-duplicates '(1 2 3 4))
=> (4 3 2 1)

(remove-duplicates '(2 4 3 4))
=> (3 4 2)
```

Lists as sequences

Function: position obj lst
`position` returns the 0-based position of obj in lst, or `#f` if obj does not occur in lst.

Example:

```(position 'foo '(foo bar baz bang))
=> 0
(position 'baz '(foo bar baz bang))
=> 2
(position 'oops '(foo bar baz bang))
=> #f
```

Function: reduce p lst
`reduce` combines all the elements of a sequence using a binary operation (the combination is left-associative). For example, using `+`, one can add up all the elements. `reduce` allows you to apply a function which accepts only two arguments to more than 2 objects. Functional programmers usually refer to this as foldl. `collect:reduce` (See section Collections) provides a version of `collect` generalized to collections.

Example:

```(reduce + '(1 2 3 4))
=> 10
(define (bad-sum . l) (reduce + l))
== (reduce + (1 2 3 4))
== (+ (+ (+ 1 2) 3) 4)
=> 10
== (reduce + ())
=> ()
(reduce string-append '("hello" "cruel" "world"))
== (string-append (string-append "hello" "cruel") "world")
=> "hellocruelworld"
(reduce anything '())
=> ()
(reduce anything '(x))
=> x
```

What follows is a rather non-standard implementation of `reverse` in terms of `reduce` and a combinator elsewhere called C.

```;;; Contributed by Jussi Piitulainen (jpiitula@ling.helsinki.fi)

(define commute
(lambda (f)
(lambda (x y)
(f y x))))

(define reverse
(lambda (args)
(reduce-init (commute cons) '() args)))
```

Function: reduce-init p init lst
`reduce-init` is the same as reduce, except that it implicitly inserts init at the start of the list. `reduce-init` is preferred if you want to handle the null list, the one-element, and lists with two or more elements consistently. It is common to use the operator's idempotent as the initializer. Functional programmers usually call this foldl.

Example:

```(define (sum . l) (reduce-init + 0 l))
(sum 1 2 3 4)
== (reduce-init + 0 (1 2 3 4))
== (+ (+ (+ (+ 0 1) 2) 3) 4)
=> 10
(sum)
== (reduce-init + 0 '())
=> 0

(reduce-init string-append "@" '("hello" "cruel" "world"))
==
(string-append (string-append (string-append "@" "hello")
"cruel")
"world")
=> "@hellocruelworld"
```

Given a differentiation of 2 arguments, `diff`, the following will differentiate by any number of variables.

```(define (diff* exp . vars)
(reduce-init diff exp vars))
```

Example:

```;;; Real-world example:  Insertion sort using reduce-init.

(define (insert l item)
(if (null? l)
(list item)
(if (< (car l) item)
(cons (car l) (insert (cdr l) item))
(cons item l))))
(define (insertion-sort l) (reduce-init insert '() l))

(insertion-sort '(3 1 4 1 5)
== (reduce-init insert () (3 1 4 1 5))
== (insert (insert (insert (insert (insert () 3) 1) 4) 1) 5)
== (insert (insert (insert (insert (3)) 1) 4) 1) 5)
== (insert (insert (insert (1 3) 4) 1) 5)
== (insert (insert (1 3 4) 1) 5)
== (insert (1 1 3 4) 5)
=> (1 1 3 4 5)
@end lisp
```
Function: last lst n
`last` returns the last n elements of lst. n must be a non-negative integer. Example:
```(last '(foo bar baz bang) 2)
=> (baz bang)
(last '(1 2 3) 0)
=> 0
```
Function: butlast lst n
`butlast` returns all but the last n elements of lst. Example:
```(butlast '(a b c d) 3)
=> (a)
(butlast '(a b c d) 4)
=> ()
```
`last` and `butlast` split a list into two parts when given identical arugments.
```(last '(a b c d e) 2)
=> (d e)
(butlast '(a b c d e) 2)
=> (a b c)
```
Function: nthcdr n lst
`nthcdr` takes n `cdr`s of lst and returns the result. Thus `(nthcdr 3 lst)` == ```(cdddr lst)``` Example:
```(nthcdr 2 '(a b c d))
=> (c d)
(nthcdr 0 '(a b c d))
=> (a b c d)
```
Function: butnthcdr n lst
`butnthcdr` returns all but the nthcdr n elements of lst. Example:
```(butnthcdr 3 '(a b c d))
=> (a b c)
(butnthcdr 4 '(a b c d))
=> ()
```
`nthcdr` and `butnthcdr` split a list into two parts when given identical arugments.
```(nthcdr 2 '(a b c d e))
=> (c d e)
(butnthcdr 2 '(a b c d e))
=> (a b)
```

Destructive list operations

These procedures may mutate the list they operate on, but any such mutation is undefined.

Procedure: nconc args
`nconc` destructively concatenates its arguments. (Compare this with `append`, which copies arguments rather than destroying them.) Sometimes called `append!` (See section Rev2 Procedures).

Example: You want to find the subsets of a set. Here's the obvious way:

```(define (subsets set)
(if (null? set)
'(())
(append (mapcar (lambda (sub) (cons (car set) sub))
(subsets (cdr set)))
(subsets (cdr set)))))
```

But that does way more consing than you need. Instead, you could replace the `append` with `nconc`, since you don't have any need for all the intermediate results.

Example:

```(define x '(a b c))
(define y '(d e f))
(nconc x y)
=> (a b c d e f)
x
=> (a b c d e f)
```

`nconc` is the same as `append!` in `sc2.scm'.

Procedure: nreverse lst
`nreverse` reverses the order of elements in lst by mutating `cdr`s of the list. Sometimes called `reverse!`.

Example:

```(define foo '(a b c))
(nreverse foo)
=> (c b a)
foo
=> (a)
```

Some people have been confused about how to use `nreverse`, thinking that it doesn't return a value. It needs to be pointed out that

```(set! lst (nreverse lst))
```

is the proper usage, not

```(nreverse lst)
```

The example should suffice to show why this is the case.

Procedure: delete elt lst
Procedure: delete-if pred lst
Procedure: delete-if-not pred lst
Destructive versions of `remove` `remove-if`, and `remove-if-not`.

Example:

```(define lst '(foo bar baz bang))
(delete 'foo lst)
=> (bar baz bang)
lst
=> (foo bar baz bang)

(define lst '(1 2 3 4 5 6 7 8 9))
(delete-if odd? lst)
=> (2 4 6 8)
lst
=> (1 2 4 6 8)
```

Some people have been confused about how to use `delete`, `delete-if`, and `delete-if`, thinking that they dont' return a value. It needs to be pointed out that

```(set! lst (delete el lst))
```

is the proper usage, not

```(delete el lst)
```

The examples should suffice to show why this is the case.

Non-List functions

Function: and? . args
`and?` checks to see if all its arguments are true. If they are, `and?` returns `#t`, otherwise, `#f`. (In contrast to `and`, this is a function, so all arguments are always evaluated and in an unspecified order.)

Example:

```(and? 1 2 3)
=> #t
(and #f 1 2)
=> #f
```

Function: or? . args
`or?` checks to see if any of its arguments are true. If any is true, `or?` returns `#t`, and `#f` otherwise. (To `or` as `and?` is to `and`.)

Example:

```(or? 1 2 #f)
=> #t
(or? #f #f #f)
=> #f
```

Function: atom? object
Returns `#t` if object is not a pair and `#f` if it is pair. (Called `atom` in Common LISP.)
```(atom? 1)
=> #t
(atom? '(1 2))
=> #f
(atom? #(1 2))   ; dubious!
=> #t
```

Function: type-of object
Returns a symbol name for the type of object.

Function: coerce object result-type
Converts and returns object of type `char`, `number`, `string`, `symbol`, `list`, or `vector` to result-type (which must be one of these symbols).

Tree operations

`(require 'tree)`

These are operations that treat lists a representations of trees.

Function: subst new old tree
Function: substq new old tree
Function: substv new old tree
`subst` makes a copy of tree, substituting new for every subtree or leaf of tree which is `equal?` to old and returns a modified tree. The original tree is unchanged, but may share parts with the result.

`substq` and `substv` are similar, but test against old using `eq?` and `eqv?` respectively.

Examples:

```(substq 'tempest 'hurricane '(shakespeare wrote (the hurricane)))
=> (shakespeare wrote (the tempest))
(substq 'foo '() '(shakespeare wrote (twelfth night)))
=> (shakespeare wrote (twelfth night . foo) . foo)
(subst '(a . cons) '(old . pair)
'((old . spice) ((old . shoes) old . pair) (old . pair)))
=> ((old . spice) ((old . shoes) a . cons) (a . cons))
```

Function: copy-tree tree
Makes a copy of the nested list structure tree using new pairs and returns it. All levels are copied, so that none of the pairs in the tree are `eq?` to the original ones -- only the leaves are.

Example:

```(define bar '(bar))
(copy-tree (list bar 'foo))
=> ((bar) foo)
(eq? bar (car (copy-tree (list bar 'foo))))
=> #f
```

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

```

Sorting

`(require 'sort)`

Many Scheme systems provide some kind of sorting functions. They do not, however, always provide the same sorting functions, and those that I have had the opportunity to test provided inefficient ones (a common blunder is to use quicksort which does not perform well).

Because `sort` and `sort!` are not in the standard, there is very little agreement about what these functions look like. For example, Dybvig says that Chez Scheme provides

```(merge predicate list1 list2)
(merge! predicate list1 list2)
(sort predicate list)
(sort! predicate list)
```

while MIT Scheme 7.1, following Common LISP, offers unstable

```(sort list predicate)
```

TI PC Scheme offers

```(sort! list/vector predicate?)
```

and Elk offers

```(sort list/vector predicate?)
(sort! list/vector predicate?)
```

Here is a comprehensive catalogue of the variations I have found.

1. Both `sort` and `sort!` may be provided.
2. `sort` may be provided without `sort!`.
3. `sort!` may be provided without `sort`.
4. Neither may be provided.
5. The sequence argument may be either a list or a vector.
6. The sequence argument may only be a list.
7. The sequence argument may only be a vector.
8. The comparison function may be expected to behave like `<`.
9. The comparison function may be expected to behave like `<=`.
10. The interface may be `(sort predicate? sequence)`.
11. The interface may be `(sort sequence predicate?)`.
12. The interface may be `(sort sequence &optional (predicate? <))`.
13. The sort may be stable.
14. The sort may be unstable.

All of this variation really does not help anybody. A nice simple merge sort is both stable and fast (quite a lot faster than quick sort).

I am providing this source code with no restrictions at all on its use (but please retain D.H.D.Warren's credit for the original idea). You may have to rename some of these functions in order to use them in a system which already provides incompatible or inferior sorts. For each of the functions, only the top-level define needs to be edited to do that.

I could have given these functions names which would not clash with any Scheme that I know of, but I would like to encourage implementors to converge on a single interface, and this may serve as a hint. The argument order for all functions has been chosen to be as close to Common LISP as made sense, in order to avoid NIH-itis.

Each of the five functions has a required last parameter which is a comparison function. A comparison function `f` is a function of 2 arguments which acts like `<`. For example,

```(not (f x x))
(and (f x y) (f y z)) == (f x z)
```

The standard functions `<`, `>`, `char<?`, `char>?`, `char-ci<?`, `char-ci>?`, `string<?`, `string>?`, `string-ci<?`, and `string-ci>?` are suitable for use as comparison functions. Think of `(less? x y)` as saying when `x` must not precede `y`.

Function: sorted? sequence less?
Returns `#t` when the sequence argument is in non-decreasing order according to less? (that is, there is no adjacent pair ```... x y ...``` for which `(less? y x)`).

Returns `#f` when the sequence contains at least one out-of-order pair. It is an error if the sequence is neither a list nor a vector.

Function: merge list1 list2 less?
This merges two lists, producing a completely new list as result. I gave serious consideration to producing a Common-LISP-compatible version. However, Common LISP's `sort` is our `sort!` (well, in fact Common LISP's `stable-sort` is our `sort!`, merge sort is fast as well as stable!) so adapting CL code to Scheme takes a bit of work anyway. I did, however, appeal to CL to determine the order of the arguments.

Procedure: merge! list1 list2 less?
Merges two lists, re-using the pairs of list1 and list2 to build the result. If the code is compiled, and less? constructs no new pairs, no pairs at all will be allocated. The first pair of the result will be either the first pair of list1 or the first pair of list2, but you can't predict which.

The code of `merge` and `merge!` could have been quite a bit simpler, but they have been coded to reduce the amount of work done per iteration. (For example, we only have one `null?` test per iteration.)

Function: sort sequence less?
Accepts either a list or a vector, and returns a new sequence which is sorted. The new sequence is the same type as the input. Always `(sorted? (sort sequence less?) less?)`. The original sequence is not altered in any way. The new sequence shares its elements with the old one; no elements are copied.

Procedure: sort! sequence less?
Returns its sorted result in the original boxes. If the original sequence is a list, no new storage is allocated at all. If the original sequence is a vector, the sorted elements are put back in the same vector.

Some people have been confused about how to use `sort!`, thinking that it doesn't return a value. It needs to be pointed out that

```(set! slist (sort! slist <))
```

is the proper usage, not

```(sort! slist <)
```

Note that these functions do not accept a CL-style `:key' argument. A simple device for obtaining the same expressiveness is to define

```(define (keyed less? key)
(lambda (x y) (less? (key x) (key y))))
```

and then, when you would have written

```(sort a-sequence #'my-less :key #'my-key)
```

in Common LISP, just write

```(sort! a-sequence (keyed my-less? my-key))
```

in Scheme.

Topological Sort

`(require 'topological-sort)` or `(require 'tsort)`

The algorithm is inspired by Cormen, Leiserson and Rivest (1990) Introduction to Algorithms, chapter 23.

Function: tsort dag pred
Function: topological-sort dag pred
where
dag
is a list of sublists. The car of each sublist is a vertex. The cdr is the adjacency list of that vertex, i.e. a list of all vertices to which there exists an edge from the car vertex.
pred
is one of `eq?`, `eqv?`, `equal?`, `=`, `char=?`, `char-ci=?`, `string=?`, or `string-ci=?`.

Sort the directed acyclic graph dag so that for every edge from vertex u to v, u will come before v in the resulting list of vertices.

Time complexity: O (|V| + |E|)

Example (from Cormen):

Prof. Bumstead topologically sorts his clothing when getting dressed. The first argument to `tsort' describes which garments he needs to put on before others. (For example, Prof Bumstead needs to put on his shirt before he puts on his tie or his belt.) `tsort' gives the correct order of dressing:

```(require 'tsort)
(tsort '((shirt tie belt)
(tie jacket)
(belt jacket)
(watch)
(pants shoes belt)
(undershorts pants shoes)
(socks shoes))
eq?)
=>
(socks undershorts pants shoes watch shirt belt tie jacket)
```

String-Case

`(require 'string-case)`

Procedure: string-upcase str
Procedure: string-downcase str
Procedure: string-capitalize str
The obvious string conversion routines. These are non-destructive.

Function: string-upcase! str
Function: string-downcase! str
Function: string-captialize! str
The destructive versions of the functions above.

Function: string-ci->symbol str
Converts string str to a symbol having the same case as if the symbol had been `read`.

String Ports

`(require 'string-port)`

Procedure: call-with-output-string proc
proc must be a procedure of one argument. This procedure calls proc with one argument: a (newly created) output port. When the function returns, the string composed of the characters written into the port is returned.

Procedure: call-with-input-string string proc
proc must be a procedure of one argument. This procedure calls proc with one argument: an (newly created) input port from which string's contents may be read. When proc returns, the port is closed and the value yielded by the procedure proc is returned.

String Search

`(require 'string-search)`

Procedure: string-index string char
Procedure: string-index-ci string char
Returns the index of the first occurence of char within string, or `#f` if the string does not contain a character char.

Procedure: string-reverse-index string char
Procedure: string-reverse-index-ci string char
Returns the index of the last occurence of char within string, or `#f` if the string does not contain a character char.

procedure: substring? pattern string
procedure: substring-ci? pattern string
Searches string to see if some substring of string is equal to pattern. `substring?` returns the index of the first character of the first substring of string that is equal to pattern; or `#f` if string does not contain pattern.

```(substring? "rat" "pirate") =>  2
(substring? "rat" "outrage") =>  #f
(substring? "" any-string) =>  0
```

Procedure: find-string-from-port? str in-port max-no-chars
Looks for a string str within the first max-no-chars chars of the input port in-port.

Procedure: find-string-from-port? str in-port
When called with two arguments, the search span is limited by the end of the input stream.

Procedure: find-string-from-port? str in-port char
Searches up to the first occurrence of character char in str.

Procedure: find-string-from-port? str in-port proc
Searches up to the first occurrence of the procedure proc returning non-false when called with a character (from in-port) argument.

When the str is found, `find-string-from-port?` returns the number of characters it has read from the port, and the port is set to read the first char after that (that is, after the str) The function returns `#f` when the str isn't found.

`find-string-from-port?` reads the port strictly sequentially, and does not perform any buffering. So `find-string-from-port?` can be used even if the in-port is open to a pipe or other communication channel.

Function: string-subst txt old1 new1 ...
Returns a copy of string txt with all occurrences of string old1 in txt replaced with new1, old2 replaced with new2 ....

Line I/O

`(require 'line-i/o)`

Returns a string of the characters up to, but not including a newline or end of file, updating port to point to the character following the newline. If no characters are available, an end of file object is returned. The port argument may be omitted, in which case it defaults to the value returned by `current-input-port`.

Fills read-line! with characters up to, but not including a newline or end of file, updating the port to point to the last character read or following the newline if it was read. If no characters are available, an end of file object is returned. If a newline or end of file was found, the number of characters read is returned. Otherwise, `#f` is returned. The port argument may be omitted, in which case it defaults to the value returned by `current-input-port`.

Function: write-line write-line string

Function: write-line write-line string port
Writes write-line followed by a newline to the given port and returns an unspecified value. The Port argument may be omited, in which case it defaults to the value returned by `current-input-port`.

Function: display-file path

Function: display-file path port
Displays the contents of the file named by path to port. The port argument may be ommited, in which case it defaults to the value returned by `current-output-port`.

Multi-Processing

`(require 'process)`

This module implements asynchronous (non-polled) time-sliced multi-processing in the SCM Scheme implementation using procedures `alarm` and `alarm-interrupt`. Until this is ported to another implementation, consider it an example of writing schedulers in Scheme.

Adds proc, which must be a procedure (or continuation) capable of accepting accepting one argument, to the `process:queue`. The value returned is unspecified. The argument to proc should be ignored. If proc returns, the process is killed.

Procedure: process:schedule!
Saves the current process on `process:queue` and runs the next process from `process:queue`. The value returned is unspecified.

Procedure: kill-process!
Kills the current process and runs the next process from `process:queue`. If there are no more processes on `process:queue`, `(slib:exit)` is called (See section System).

Standards Support

With-File

`(require 'with-file)`

Function: with-input-from-file file thunk
Function: with-output-to-file file thunk
Description found in R4RS.

Transcripts

`(require 'transcript)`

Function: transcript-on filename
Function: transcript-off filename
Redefines `read-char`, `read`, `write-char`, `write`, `display`, and `newline`.

Rev2 Procedures

`(require 'rev2-procedures)`

The procedures below were specified in the Revised^2 Report on Scheme. N.B.: The symbols `1+` and `-1+` are not R4RS syntax. Scheme->C, for instance, barfs on this module.

Procedure: substring-move-left! string1 start1 end1 string2 start2
Procedure: substring-move-right! string1 start1 end1 string2 start2
string1 and string2 must be a strings, and start1, start2 and end1 must be exact integers satisfying

```0 <= start1 <= end1 <= (string-length string1)
0 <= start2 <= end1 - start1 + start2 <= (string-length string2)
```

`substring-move-left!` and `substring-move-right!` store characters of string1 beginning with index start1 (inclusive) and ending with index end1 (exclusive) into string2 beginning with index start2 (inclusive).

`substring-move-left!` stores characters in time order of increasing indices. `substring-move-right!` stores characters in time order of increasing indeces.

Procedure: substring-fill! string start end char
Fills the elements start--end of string with the character char.

Function: string-null? str
== `(= 0 (string-length str))`

Procedure: append! . pairs
Destructively appends its arguments. Equivalent to `nconc`.

Function: 1+ n

Function: -1+ n
Subtracts 1 from n.

Function: <?
Function: <=?
Function: =?
Function: >?
Function: >=?
These are equivalent to the procedures of the same name but without the trailing `?'.

Rev4 Optional Procedures

`(require 'rev4-optional-procedures)`

For the specification of these optional procedures, See section `Standard procedures' in Revised(4) Scheme.

Function: list-tail l p

Function: string->list s

Function: list->string l

Function: string-copy

Procedure: string-fill! s obj

Function: list->vector l

Function: vector->list s

Procedure: vector-fill! s obj

Multi-argument / and -

`(require 'mutliarg/and-)`

For the specification of these optional forms, See section `Numerical operations' in Revised(4) Scheme. The `two-arg:`* forms are only defined if the implementation does not support the many-argument forms.

Function: two-arg:/ n1 n2
The original two-argument version of `/`.

Function: / divident . divisors

Function: two-arg:- n1 n2
The original two-argument version of `-`.

Function: - minuend . subtrahends

Multi-argument Apply

`(require 'multiarg-apply)`

For the specification of this optional form, See section `Control features' in Revised(4) Scheme.

Function: two-arg:apply proc l
The implementation's native `apply`. Only defined for implementations which don't support the many-argument version.

Function: apply proc . args

Rationalize

`(require 'rationalize)`

The procedure rationalize is interesting because most programming languages do not provide anything analogous to it. For simplicity, we present an algorithm which computes the correct result for exact arguments (provided the implementation supports exact rational numbers of unlimited precision), and produces a reasonable answer for inexact arguments when inexact arithmetic is implemented using floating-point. We thank Alan Bawden for contributing this algorithm.

Function: rationalize x e

Promises

`(require 'promise)`

Function: make-promise proc

Change occurrences of `(delay expression)` to `(make-promise (lambda () expression))` and ```(define force promise:force)``` to implement promises if your implementation doesn't support them (see section `Control features' in Revised(4) Scheme).

Dynamic-Wind

`(require 'dynamic-wind)`

This facility is a generalization of Common LISP `unwind-protect`, designed to take into account the fact that continuations produced by `call-with-current-continuation` may be reentered.

Procedure: dynamic-wind thunk1 thunk2 thunk3
The arguments thunk1, thunk2, and thunk3 must all be procedures of no arguments (thunks).

`dynamic-wind` calls thunk1, thunk2, and then thunk3. The value returned by thunk2 is returned as the result of `dynamic-wind`. thunk3 is also called just before control leaves the dynamic context of thunk2 by calling a continuation created outside that context. Furthermore, thunk1 is called before reentering the dynamic context of thunk2 by calling a continuation created inside that context. (Control is inside the context of thunk2 if thunk2 is on the current return stack).

Warning: There is no provision for dealing with errors or interrupts. If an error or interrupt occurs while using `dynamic-wind`, the dynamic environment will be that in effect at the time of the error or interrupt.

Eval

`(require 'eval)`

Function: eval expression environment-specifier

Evaluates expression in the specified environment and returns its value. Expression must be a valid Scheme expression represented as data, and environment-specifier must be a value returned by one of the three procedures described below. Implementations may extend `eval` to allow non-expression programs (definitions) as the first argument and to allow other values as environments, with the restriction that `eval` is not allowed to create new bindings in the environments associated with `null-environment` or `scheme-report-environment`.

```(eval '(* 7 3) (scheme-report-environment 5))
=>  21

(let ((f (eval '(lambda (f x) (f x x))
(null-environment))))
(f + 10))
=>  20
```

Function: scheme-report-environment version
Function: null-environment version
Function: null-environment

Version must be an exact non-negative integer n corresponding to a version of one of the Revised^n Reports on Scheme. `Scheme-report-environment` returns a specifier for an environment that contains the set of bindings specified in the corresponding report that the implementation supports. `Null-environment` returns a specifier for an environment that contains only the (syntactic) bindings for all the syntactic keywords defined in the given version of the report.

Not all versions may be available in all implementations at all times. However, an implementation that conforms to version n of the Revised^n Reports on Scheme must accept version n. An error is signalled if the specified version is not available.

The effect of assigning (through the use of `eval`) a variable bound in a `scheme-report-environment` (for example `car`) is unspecified. Thus the environments specified by `scheme-report-environment` may be immutable.

Function: interaction-environment

This optional procedure returns a specifier for the environment that contains implementation-defined bindings, typically a superset of those listed in the report. The intent is that this procedure will return the environment in which the implementation would evaluate expressions dynamically typed by the user.

Here are some more `eval` examples:

```(require 'eval)
=> #<unspecified>
(define car 'volvo)
=> #<unspecified>
car
=> volvo
(eval 'car (interaction-environment))
=> volvo
(eval 'car (scheme-report-environment 5))
=> #<primitive-procedure car>
(eval '(eval 'car (interaction-environment))
(scheme-report-environment 5))
=> volvo
(eval '(eval '(set! car 'buick) (interaction-environment))
(scheme-report-environment 5))
=> #<unspecified>
car
=> buick
(eval 'car (scheme-report-environment 5))
=> #<primitive-procedure car>
(eval '(eval 'car (interaction-environment))
(scheme-report-environment 5))
=> buick
```

Values

`(require 'values)`

Function: values obj ...
`values` takes any number of arguments, and passes (returns) them to its continuation.

Function: call-with-values thunk proc
thunk must be a procedure of no arguments, and proc must be a procedure. `call-with-values` calls thunk with a continuation that, when passed some values, calls proc with those values as arguments.

Except for continuations created by the `call-with-values` procedure, all continuations take exactly one value, as now; the effect of passing no value or more than one value to continuations that were not created by the `call-with-values` procedure is unspecified.

Session Support

Repl

`(require 'repl)`

Here is a read-eval-print-loop which, given an eval, evaluates forms.

Procedure: repl:top-level repl:eval
`read`s, `repl:eval`s and `write`s expressions from `(current-input-port)` to `(current-output-port)` until an end-of-file is encountered. `load`, `slib:eval`, `slib:error`, and `repl:quit` dynamically bound during `repl:top-level`.

Procedure: repl:quit
Exits from the invocation of `repl:top-level`.

The `repl:` procedures establish, as much as is possible to do portably, a top level environment supporting macros. `repl:top-level` uses `dynamic-wind` to catch error conditions and interrupts. If your implementation supports this you are all set.

Otherwise, if there is some way your implementation can catch error conditions and interrupts, then have them call `slib:error`. It will display its arguments and reenter `repl:top-level`. `slib:error` dynamically bound by `repl:top-level`.

To have your top level loop always use macros, add any interrupt catching lines and the following lines to your Scheme init file:

```(require 'macro)
(require 'repl)
(repl:top-level macro:eval)
```

Quick Print

`(require 'qp)`

When displaying error messages and warnings, it is paramount that the output generated for circular lists and large data structures be limited. This section supplies a procedure to do this. It could be much improved.

Notice that the neccessity for truncating output eliminates Common-Lisp's See section Format (version 3.0) from consideration; even when variables `*print-level*` and `*print-level*` are set, huge strings and bit-vectors are not limited.

Procedure: qp arg1 ...
Procedure: qpn arg1 ...
Procedure: qpr arg1 ...
`qp` writes its arguments, separated by spaces, to `(current-output-port)`. `qp` compresses printing by substituting `...' for substructure it does not have sufficient room to print. `qpn` is like `qp` but outputs a newline before returning. `qpr` is like `qpn` except that it returns its last argument.

Variable: *qp-width*
`*qp-width*` is the largest number of characters that `qp` should use.

Debug

`(require 'debug)`

Requiring `debug` automatically requires `trace` and `break`.

An application with its own datatypes may want to substitute its own printer for `qp`. This example shows how to do this:

```(define qpn (lambda args) ...)
(provide 'qp)
(require 'debug)
```

Procedure: trace-all file
Traces (see section Tracing) all procedures `define`d at top-level in file `file'.

Procedure: break-all file
Breakpoints (see section Breakpoints) all procedures `define`d at top-level in file `file'.

Breakpoints

`(require 'break)`

Function: init-debug
If your Scheme implementation does not support `break` or `abort`, a message will appear when you `(require 'break)` or `(require 'debug)` telling you to type `(init-debug)`. This is in order to establish a top-level continuation. Typing `(init-debug)` at top level sets up a continuation for `break`.

Function: breakpoint arg1 ...
Returns from the top level continuation and pushes the continuation from which it was called on a continuation stack.

Function: continue
Pops the topmost continuation off of the continuation stack and returns an unspecified value to it.

Function: continue arg1 ...
Pops the topmost continuation off of the continuation stack and returns arg1 ... to it.

Macro: break proc1 ...
Redefines the top-level named procedures given as arguments so that `breakpoint` is called before calling proc1 ....
Macro: break
With no arguments, makes sure that all the currently broken identifiers are broken (even if those identifiers have been redefined) and returns a list of the broken identifiers.

Macro: unbreak proc1 ...
Turns breakpoints off for its arguments.
Macro: unbreak
With no arguments, unbreaks all currently broken identifiers and returns a list of these formerly broken identifiers.

The following routines are the procedures which actually do the tracing when this module is supplied by SLIB, rather than natively. If defmacros are not natively supported by your implementation, these might be more convenient to use.

Function: breakf proc
Function: breakf proc name
Function: debug:breakf proc
Function: debug:breakf proc name
To break, type
```(set! symbol (breakf symbol))
```

or

```(set! symbol (breakf symbol 'symbol))
```

or

```(define symbol (breakf function))
```

or

```(define symbol (breakf function 'symbol))
```

Function: unbreakf proc
Function: debug:unbreakf proc
To unbreak, type
```(set! symbol (unbreakf symbol))
```

Tracing

`(require 'trace)`

Macro: trace proc1 ...
Traces the top-level named procedures given as arguments.
Macro: trace
With no arguments, makes sure that all the currently traced identifiers are traced (even if those identifiers have been redefined) and returns a list of the traced identifiers.

Macro: untrace proc1 ...
Turns tracing off for its arguments.
Macro: untrace
With no arguments, untraces all currently traced identifiers and returns a list of these formerly traced identifiers.

The following routines are the procedures which actually do the tracing when this module is supplied by SLIB, rather than natively. If defmacros are not natively supported by your implementation, these might be more convenient to use.

Function: tracef proc
Function: tracef proc name
Function: debug:tracef proc
Function: debug:tracef proc name
To trace, type
```(set! symbol (tracef symbol))
```

or

```(set! symbol (tracef symbol 'symbol))
```

or

```(define symbol (tracef function))
```

or

```(define symbol (tracef function 'symbol))
```

Function: untracef proc
Function: debug:untracef proc
To untrace, type
```(set! symbol (untracef symbol))
```

System Interface

If `(provided? 'getenv)`:

Function: getenv name
Looks up name, a string, in the program environment. If name is found a string of its value is returned. Otherwise, `#f` is returned.

If `(provided? 'system)`:

Function: system command-string
Executes the command-string on the computer and returns the integer status code.

If `system` is provided by the Scheme implementation, the net-clients package provides interfaces to common network client programs like FTP, mail, and Netscape.

`(require 'net-clients)`

Function: call-with-tmpnam proc

Function: call-with-tmpnam proc k
Calls proc with k arguments, strings returned by successive calls to `tmpnam`. If proc returns, then any files named by the arguments to proc are deleted automatically and the value(s) yielded by the proc is(are) returned. k may be ommited, in which case it defaults to `1`.

`user-email-address` returns a string of the form `username@hostname'. If this e-mail address cannot be obtained, #f is returned.

If `user-email-address` cannot be supported by the platform, the value of `user-email-address` is #f.

Function: getcwd

`getcwd` returns a string containing the absolute file name representing the current working directory. If this string cannot be obtained, #f is returned.

If `getcwd` cannot be supported by the platform, the value of `getcwd` is #f.

Function: null-directory? file-name

Returns #t if changing directory to file-name makes the current working directory the same as it is before changing directory; otherwise returns #f.

Function: absolute-path? file-name

Returns #t if file-name is a fully specified pathname (does not depend on the current working directory); otherwise returns #f.

Function: path->url path

Returns a URL-string for path on the local host.

Returns a list of the decoded FTP url; or #f if indecipherable. FTP Uniform Resource Locator, ange-ftp, and getit formats are handled. The returned list has four elements which are strings or #f:

3. remote-site
4. remote-directory

Extra-SLIB Packages

Several Scheme packages have been written using SLIB. There are several reasons why a package might not be included in the SLIB distribution:

• Because it requires special hardware or software which is not universal.
• Because it is large and of limited interest to most Scheme users.
• Because it has copying terms different enough from the other SLIB packages that its inclusion would cause confusion.
• Because it is an application program, rather than a library module.
• Because I have been too busy to integrate it.

Once an optional package is installed (and an entry added to `*catalog*`, the `require` mechanism allows it to be called up and used as easily as any other SLIB package. Some optional packages (for which `*catalog*` already has entries) available from SLIB sites are:

SLIB-PSD is a portable debugger for Scheme (requires emacs editor).
```swissnet.ai.mit.edu:pub/scm/slib-psd1-3.tar.gz
prep.ai.mit.edu:pub/gnu/jacal/slib-psd1-3.tar.gz
ftp.maths.tcd.ie:pub/bosullvn/jacal/slib-psd1-3.tar.gz
ftp.cs.indiana.edu:/pub/scheme-repository/utl/slib-psd1-3.tar.gz
```
With PSD, you can run a Scheme program in an Emacs buffer, set breakpoints, single step evaluation and access and modify the program's variables. It works by instrumenting the original source code, so it should run with any R4RS compliant Scheme. It has been tested with SCM, Elk 1.5, and the sci interpreter in the Scheme->C system, but should work with other Schemes with a minimal amount of porting, if at all. Includes documentation and user's manual. Written by Pertti Kellom\"aki, pk@cs.tut.fi. The Lisp Pointers article describing PSD (Lisp Pointers VI(1):15-23, January-March 1993) is available as http://www.cs.tut.fi/staff/pk/scheme/psd/article/article.html
http://www.cs.rice.edu/CS/PLT/packages/schelog/