7. Other Packages

7.1 Data Structures

7.1.1 Arrays

(require 'array)

Function: array? obj

Returns #t if the obj is an array, and #f if not.

(define (strict-array? obj)
  (and (array? obj) (not (string? obj)) (not (vector? obj))))

Function: array=? array1 array2

Returns #t if array1 and array2 have the same rank and shape and the corresponding elements of array1 and array2 are equal?.

(array=? (create-array '#(foo) 3 3) (create-array '#(foo) '(0 2) '(0 2))) => #t

Function: create-array prototype bound1 bound2 ...

Creates and returns an array of type prototype with dimensions bound1, bound2, ... and filled with elements from prototype. prototype must be an array, vector, or string. The implementation-dependent type of the returned array will be the same as the type of prototype; except if that would be a vector or string with non-zero origin, in which case some variety of array will be returned.

If the prototype has no elements, then the initial contents of the returned array are unspecified. Otherwise, the returned array will be filled with the element at the origin of prototype.

Function: ac64 z

Function: ac64

Returns a high-precision complex uniform-array prototype.

Function: ac32 z

Function: ac32

Returns a complex uniform-array prototype.

Function: ar64 x

Function: ar64

Returns a high-precision real uniform-array prototype.

Function: ar32 x

Function: ar32

Returns a real uniform-array prototype.

Function: as64 n

Function: as64

Returns an exact signed integer uniform-array prototype with at least 64 bits of precision.

Function: as32 n

Function: as32

Returns an exact signed integer uniform-array prototype with at least 32 bits of precision.

Function: as16 n

Function: as16

Returns an exact signed integer uniform-array prototype with at least 16 bits of precision.

Function: as8 n

Function: as8

Returns an exact signed integer uniform-array prototype with at least 8 bits of precision.

Function: au64 k

Function: au64

Returns an exact non-negative integer uniform-array prototype with at least 64 bits of precision.

Function: au32 k

Function: au32

Returns an exact non-negative integer uniform-array prototype with at least 32 bits of precision.

Function: au16 k

Function: au16

Returns an exact non-negative integer uniform-array prototype with at least 16 bits of precision.

Function: au8 k

Function: au8

Returns an exact non-negative integer uniform-array prototype with at least 8 bits of precision.

Function: at1 bool

Function: at1

Returns a boolean uniform-array prototype.

(create-array '#(foo) 3 3) == (create-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 (create-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

Returns a list of inclusive bounds.

(array-shape (create-array '#() 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.

(array-dimensions (create-array '#() 3 5)) => (3 5)

Function: 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 (index1, index2, ...) element of array.

Procedure: array-set! array obj index1 index2 ...

Stores obj in the (index1, index2, ...) element of array. The value returned by array-set! is unspecified.

7.1.2 Subarrays

(require 'subarray)

Function: subarray array select ...

selects a subset of an array. For array of rank n, there must be at least n selects arguments. For 0 <= j < n, selectsj is either an integer, a list of two integers within the range for the jth index, or #f.

When selectsj is a list of two integers, then the jth index is restricted to that subrange in the returned array.

When selectsj is #f, then the full range of the jth index is accessible in the returned array. An elided argument is equivalent to #f.

When selectsj is an integer, then the rank of the returned array is less than array, and only elements whose jth index equals selectsj are shared.

> (define ra '#2A((a b c) (d e f))) #<unspecified> > (subarray ra 0 #f) #1A(a b c) > (subarray ra 1 #f) #1A(d e f) > (subarray ra #f 1) #1A(b e) > (subarray ra '(0 1) #f) #2A((a b c) (d e f)) > (subarray ra #f '(0 1)) #2A((a b) (d e)) > (subarray ra #f '(1 2)) #2A((b c) (e f))

Function: subarray0 array select ...

Behaves like subarray, but aligns the returned array origin to 0 ....

Function: array-align array coord ...

Returns an array shared with array but with a different origin. The coords are the exact integer coordinates of the new origin. Indexes corresponding to missing or #f coordinates are not realigned.

For example:

(define ra2 (create-array '#(5) '(5 9) '(-4 0))) (array-shape ra2) => ((5 9) (-4 0)) (array-shape (array-align ra2 0 0)) => ((0 4) (0 4)) (array-shape (array-align ra2 0)) => ((0 4) (-4 0)) (array-shape (array-align ra2)) => ((5 9) (-4 0)) (array-shape (array-align ra2 0 #f)) => ((0 4) (-4 0)) (array-shape (array-align ra2 #f 0)) => ((5 9) (0 4))

Function: array-trim array trim ...

Returns a subarray sharing contents with array except for slices removed from either side of each dimension. Each of the trims is an exact integer indicating how much to trim. A positive s trims the data from the lower end and reduces the upper bound of the result; a negative s trims from the upper end and increases the lower bound.

For example:

(array-trim '#(0 1 2 3 4) 1) => #1A(1 2 3 4) ;; shape is ((0 3)) (array-trim '#(0 1 2 3 4) -1) => #1A(0 1 2 3) ;; shape is ((1 4)) (require 'array-for-each) (define (centered-difference ra) (array-map - (array-trim ra 1) (array-trim ra -1))) (define (forward-difference ra) (array-map - (array-trim ra 1) ra)) (define (backward-difference ra) (array-map - ra (array-trim ra -1))) (centered-difference '#(0 1 3 5 9 22)) => #1A(3 4 6 17) ;;shape is ((1 4)) (backward-difference '#(0 1 3 5 9 22)) => #1A(1 2 2 4 13) ;; shape is ((1 5)) (forward-difference '#(0 1 3 5 9 22)) => #(1 2 2 4 13) ;; shape is ((0 4))

7.1.3 Array Mapping

(require 'array-for-each)

Procedure: 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-map prototype proc array1 array2 ...

array2, ... must have the same number of dimensions as array1 and have a range for each index which includes the range for the corresponding index in array1. proc is applied to each tuple of elements of array1, array2, ... and the result is stored as the corresponding element in a new array of type prototype. The new array is returned. 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)).

Procedure: 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 create-array '#() (array-shape array)))) (array-index-map! ra (lambda x x)) ra))

Another example:

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

Procedure: 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.

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

7.1.5 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 nonnegative integer. byte-set! stores byte in element k of bytes and returns an unspecified value.

Function: make-bytes k byte

Function: make-bytes k

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: bytes byte ...

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

Function: bytes->list bytes

bytes->list returns a newly allocated list of the bytes that make up the given byte-array.

Function: list->bytes bytes

list->bytes returns a newly allocated byte-array formed from the small nonnegative integers in the list bytes.

Function: bytes-copy bytes

Returns a newly allocated copy of the given bytes.

Procedure: bytes-reverse! bytes

Reverses the order of byte-array bytes.

Function: bytes-reverse bytes

Returns a newly allocated bytes-array consisting of the elements of bytes in reverse order.

Function: write-byte byte port

Function: write-byte byte

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.

Function: read-byte port

Function: read-byte

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.

Once read in, SLIB treats byte sequences as big-endian. The multi-byte sequences produced and used by number conversion routines see section 7.1.6 Byte/Number Conversions are always big-endian.

Function: read-bytes n port

Function: read-bytes n

read-bytes returns a newly allocated bytes-array filled with (abs n) bytes read from port. If n is positive, then the first byte read is stored at index 0; otherwise the last byte read is stored at index 0. Note that the length of the returned string will be less than (abs n) if port reaches end-of-file.

port may be omitted, in which case it defaults to the value returned by current-input-port.

Function: write-bytes bytes n port

Function: write-bytes bytes n

write-bytes writes (abs n) bytes to output-port port. If n is positive, then the first byte written is index 0 of bytes; otherwise the last byte written is index 0 of bytes. write-bytes returns an unspecified value.

port may be omitted, in which case it defaults to the value returned by current-output-port.

Procedure: substring-read! string start end port

Procedure: substring-read! string start end

Fills string with up to (abs (- start end)) bytes read from port. The first byte read is stored at index string. substring-read! returns the number of bytes read.

port may be omitted, in which case it defaults to the value returned by current-input-port.

Function: substring-write string start end port

Function: substring-write string start end

substring-write writes (abs (- start end)) bytes to output-port port. The first byte written is index start of string. substring-write returns the number of bytes written.

port may be omitted, in which case it defaults to the value returned by current-output-port.

7.1.6 Byte/Number Conversions

(require 'byte-number)

The multi-byte sequences produced and used by numeric conversion routines are always big-endian. Endianness can be changed during reading and writing bytes using read-bytes and write-bytes See section read-bytes.

The sign of the length argument to bytes/integer conversion procedures determines the signedness of the number.

Function: bytes->integer bytes n

Converts the first (abs n) bytes of big-endian bytes array to an integer. If n is negative then the integer coded by the bytes are treated as two's-complement (can be negative).

(bytes->integer (bytes 0 0 0 15) -4) => 15 (bytes->integer (bytes 0 0 0 15) 4) => 15 (bytes->integer (bytes 255 255 255 255) -4) => -1 (bytes->integer (bytes 255 255 255 255) 4) => 4294967295 (bytes->integer (bytes 128 0 0 0) -4) => -2147483648 (bytes->integer (bytes 128 0 0 0) 4) => 2147483648

Function: integer->bytes n len

Converts the integer n to a byte-array of (abs n) bytes. If n and len are both negative, then the bytes in the returned array are coded two's-complement.

(bytes->list (integer->bytes 15 -4)) => (0 0 0 15) (bytes->list (integer->bytes 15 4)) => (0 0 0 15) (bytes->list (integer->bytes -1 -4)) => (255 255 255 255) (bytes->list (integer->bytes 4294967295 4)) => (255 255 255 255) (bytes->list (integer->bytes -2147483648 -4)) => (128 0 0 0) (bytes->list (integer->bytes 2147483648 4)) => (128 0 0 0)

Function: bytes->ieee-float bytes

bytes must be a 4-element byte-array. bytes->ieee-float calculates and returns the value of bytes interpreted as a big-endian IEEE 4-byte (32-bit) number.

(bytes->ieee-float (bytes #x40    0 0 0))  =>  2.0
(bytes->ieee-float (bytes #x40 #xd0 0 0))  =>  6.5
(bytes->ieee-float (bytes #xc0 #xd0 0 0))  => -6.5

(bytes->ieee-float (bytes    0 #x80 0 0))  => 11.754943508222875e-39
(bytes->ieee-float (bytes    0 #x40 0 0))  =>  5.877471754111437e-39
(bytes->ieee-float (bytes    0    0 0 1))  =>  1.401298464324817e-45

(bytes->ieee-float (bytes #xff #x80 0 0))  => -1/0
(bytes->ieee-float (bytes #x7f #x80 0 0))  =>  1/0
(bytes->ieee-float (bytes #x7f #x80 0 1))  =>  0/0

Function: bytes->ieee-double bytes

bytes must be a 8-element byte-array. bytes->ieee-double calculates and returns the value of bytes interpreted as a big-endian IEEE 8-byte (64-bit) number.

(bytes->ieee-double (bytes    0    0 0 0 0 0 0 0))  =>  0.0
(bytes->ieee-double (bytes #x40    0 0 0 0 0 0 0))  =>  2
(bytes->ieee-double (bytes #x40 #x1A 0 0 0 0 0 0))  =>  6.5
(bytes->ieee-double (bytes #xC0 #x1A 0 0 0 0 0 0))  => -6.5

(bytes->ieee-double (bytes 0 8 0 0 0 0 0 0)) => 11.125369292536006e-309
(bytes->ieee-double (bytes 0 4 0 0 0 0 0 0)) =>  5.562684646268003e-309
(bytes->ieee-double (bytes 0 0 0 0 0 0 0 1)) =>  4.0e-324

(bytes->ieee-double (bytes #xFF #xF0 0 0 0 0 0 0))  => -1/0
(bytes->ieee-double (bytes #x7F #xF0 0 0 0 0 0 0))  =>  1/0
(bytes->ieee-double (bytes #x7F #xF8 0 0 0 0 0 0))  =>  0/0

Function: ieee-float->bytes x

Returns a 4-element byte-array encoding the IEEE single-precision floating-point of x.

(bytes->list (ieee-float->bytes  2.0))                    => (64    0 0 0)
(bytes->list (ieee-float->bytes  6.5))                    => (64  208 0 0)
(bytes->list (ieee-float->bytes -6.5))                    => (192 208 0 0)

(bytes->list (ieee-float->bytes 11.754943508222875e-39))  => (  0 128 0 0)
(bytes->list (ieee-float->bytes  5.877471754111438e-39))  => (  0  64 0 0)
(bytes->list (ieee-float->bytes  1.401298464324817e-45))  => (  0   0 0 1)

(bytes->list (ieee-float->bytes -1/0))                    => (255 128 0 0)
(bytes->list (ieee-float->bytes  1/0))                    => (127 128 0 0)
(bytes->list (ieee-float->bytes  0/0))                    => (127 128 0 1)

Function: ieee-double->bytes x

Returns a 8-element byte-array encoding the IEEE double-precision floating-point of x.

(bytes->list (ieee-double->bytes  2.0)) => (64    0 0 0 0 0 0 0)
(bytes->list (ieee-double->bytes  6.5)) => (64   26 0 0 0 0 0 0)
(bytes->list (ieee-double->bytes -6.5)) => (192  26 0 0 0 0 0 0)

(bytes->list (ieee-double->bytes 11.125369292536006e-309))
                                        => (  0   8 0 0 0 0 0 0)
(bytes->list (ieee-double->bytes  5.562684646268003e-309))
                                        => (  0   4 0 0 0 0 0 0)
(bytes->list (ieee-double->bytes  4.0e-324))
                                        => (  0   0 0 0 0 0 0 1)

(bytes->list (ieee-double->bytes -1/0)) => (255 240 0 0 0 0 0 0)
(bytes->list (ieee-double->bytes  1/0)) => (127 240 0 0 0 0 0 0)
(bytes->list (ieee-double->bytes  0/0)) => (127 248 0 0 0 0 0 0)

Byte Collation Order

The string<? ordering of big-endian byte-array representations of fixed and IEEE floating-point numbers agrees with the numerical ordering only when those numbers are non-negative.

Straighforward modification of these formats can extend the byte-collating order to work for their entire ranges. This agreement enables the full range of numbers as keys in indexed-sequential-access-method databases.

Procedure: integer-byte-collate! byte-vector

Modifies sign bit of byte-vector so that string<? ordering of two's-complement byte-vectors matches numerical order. integer-byte-collate! returns byte-vector and is its own functional inverse.

Function: integer-byte-collate byte-vector

Returns copy of byte-vector with sign bit modified so that string<? ordering of two's-complement byte-vectors matches numerical order. integer-byte-collate is its own functional inverse.

Procedure: ieee-byte-collate! byte-vector

Modifies byte-vector so that string<? ordering of IEEE floating-point byte-vectors matches numerical order. ieee-byte-collate! returns byte-vector.

Procedure: ieee-byte-decollate! byte-vector

Given byte-vector modified by IEEE-byte-collate!, reverses the byte-vector modifications.

Function: ieee-byte-collate byte-vector

Returns copy of byte-vector encoded so that string<? ordering of IEEE floating-point byte-vectors matches numerical order.

Function: ieee-byte-decollate byte-vector

Given byte-vector returned by IEEE-byte-collate, reverses the byte-vector modifications.

7.1.7 MAT-File Format

(require 'matfile)

http://www.mathworks.com/access/helpdesk/help/pdf_doc/matlab/matfile_format.pdf

This package reads MAT-File Format version 4 (MATLAB) binary data files. MAT-files written from big-endian or little-endian computers having IEEE format numbers are currently supported. Support for files written from VAX or Cray machines could also be added.

The numeric and text matrix types handled; support for sparse matrices awaits a sample file.

Function: matfile:read filename

filename should be a string naming an existing file containing a MATLAB Version 4 MAT-File. The matfile:read procedure reads matrices from the file and returns a list of the results; a list of the name string and array for each matrix.

Function: matfile:load filename

filename should be a string naming an existing file containing a MATLAB Version 4 MAT-File. The matfile:load procedure reads matrices from the file and defines the string-ci->symbol for each matrix to its corresponding array. matfile:load returns a list of the symbols defined.

7.1.8 Portable Image Files

(require 'pnm)

Function: pnm:type-dimensions path

The string path must name a portable bitmap graphics file. pnm:type-dimensions returns a list of 4 items:

1. A symbol describing the type of the file named by path.
2. The image width in pixels.
3. The image height in pixels.
4. The maximum value of pixels assume in the file.

The current set of file-type symbols is:

pbm

pbm-raw

Black-and-White image; pixel values are 0 or 1.

pgm

pgm-raw

Gray (monochrome) image; pixel values are from 0 to maxval specified in file header.

ppm

ppm-raw

RGB (full color) image; red, green, and blue interleaved pixel values are from 0 to maxval

Function: pnm:image-file->array path array

Reads the portable bitmap graphics file named by path into array. array must be the correct size and type for path. array is returned.

Function: pnm:image-file->array path

pnm:image-file->array creates and returns an array with the portable bitmap graphics file named by path read into it.

Function: pnm:array-write type array maxval path comment ...

Writes the contents of array to a type image file named path. The file will have pixel values between 0 and maxval, which must be compatible with type. For `pbm' files, maxval must be `1'. comments are included in the file header.

7.1.9 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 3.8 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 collection1 ...

Procedure: do-elts proc collection1 ...

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

Procedure: do-keys proc collection1 ...

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

A generalization of the list-based reduce-init (see section 7.2.1.3 Lists as sequences) to collections which will shadow the list-based version if (require 'collect) follows (require 'common-list-functions) (see section 7.2.1 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 collection1 ...

A generalization of the list-based some (see section 7.2.1.3 Lists as sequences) to collections.

Example:

(any? odd? (list 2 3 4 5)) => #t

Function: every? pred collection1 ...

A generalization of the list-based every (see section 7.2.1.3 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 3.8.3 Setters for a definition of setter. N.B. (setter list-ref) doesn't work properly for element 0 of a list.

Here is a sample collection: simple-table which is also a table.

(define-predicate TABLE?)
(define-operation (LOOKUP table key failure-object))
(define-operation (ASSOCIATE! table key value)) ;; returns key
(define-operation (REMOVE! table key))          ;; returns value

(define (MAKE-SIMPLE-TABLE)
  (let ( (table (list)) )
    (object
     ;; table behaviors
     ((TABLE? self) #t)
     ((SIZE self) (size table))
     ((PRINT self port) (format port "#<SIMPLE-TABLE>"))
     ((LOOKUP self key failure-object)
      (cond
       ((assq key table) => cdr)
       (else failure-object)
       ))
     ((ASSOCIATE! self key value)
      (cond
       ((assq key table)
        => (lambda (bucket) (set-cdr! bucket value) key))
       (else
        (set! table (cons (cons key value) table))
        key)
       ))
     ((REMOVE! self key);; returns old value
      (cond
       ((null? table) (slib:error "TABLE:REMOVE! Key not found: " key))
       ((eq? key (caar table))
        (let ( (value (cdar table)) )
          (set! table (cdr table))
          value)
        )
       (else
        (let loop ( (last table) (this (cdr table)) )
          (cond
           ((null? this)
            (slib:error "TABLE:REMOVE! Key not found: " key))
           ((eq? key (caar this))
            (let ( (value (cdar this)) )
              (set-cdr! last (cdr this))
              value)
            )
           (else
            (loop (cdr last) (cdr this)))
           ) ) )
       ))
     ;; collection behaviors
     ((COLLECTION? self) #t)
     ((GEN-KEYS self) (collect:list-gen-elts (map car table)))
     ((GEN-ELTS self) (collect:list-gen-elts (map cdr table)))
     ((FOR-EACH-KEY self proc)
      (for-each (lambda (bucket) (proc (car bucket))) table)
      )
     ((FOR-EACH-ELT self proc)
      (for-each (lambda (bucket) (proc (cdr bucket))) table)
      ) ) ) )

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

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

Function: make-hash-table k

Returns a vector of k empty (association) lists.

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

Function: hash-rehasher pred

hash-rehasher accepts a hash table predicate and returns a function of two arguments hashtab and new-k which is specialized for that predicate.

This function is used for nondestrutively resizing a hash table. hashtab should be an existing hash-table using pred, new-k is the size of a new hash table to be returned. The new hash table will have all of the associations of the old hash table.

7.1.12 Macroless Object System

(require 'object)

This is the Macroless Object System written by Wade Humeniuk (whumeniu@datap.ca). Conceptual Tributes: 3.8 Yasos, MacScheme's %object, CLOS, Lack of R4RS macros.

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

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

7.1.15 Examples

(require 'object)

(define instantiate (make-generic-method))

(define (make-instance-object . ancestors)
  (define self (apply make-object
                      (map (lambda (obj) (instantiate obj)) ancestors)))
  (make-method! self instantiate (lambda (self) self))
  self)

(define who (make-generic-method))
(define imigrate! (make-generic-method))
(define emigrate! (make-generic-method))
(define describe (make-generic-method))
(define name (make-generic-method))
(define address (make-generic-method))
(define members (make-generic-method))

(define society
  (let ()
    (define self (make-instance-object))
    (define population '())
    (make-method! self imigrate!
                  (lambda (new-person)
                    (if (not (eq? new-person self))
                        (set! population (cons new-person population)))))
    (make-method! self emigrate!
                  (lambda (person)
                    (if (not (eq? person self))
                        (set! population
                              (comlist:remove-if (lambda (member)
                                                   (eq? member person))
                                                 population)))))
    (make-method! self describe
                  (lambda (self)
                    (map (lambda (person) (describe person)) population)))
    (make-method! self who
                  (lambda (self) (map (lambda (person) (name person))
                                      population)))
    (make-method! self members (lambda (self) population))
    self))

(define (make-person %name %address)
  (define self (make-instance-object society))
  (make-method! self name (lambda (self) %name))
  (make-method! self address (lambda (self) %address))
  (make-method! self who (lambda (self) (name self)))
  (make-method! self instantiate
                (lambda (self)
                  (make-person (string-append (name self) "-son-of")
                               %address)))
  (make-method! self describe
                (lambda (self) (list (name self) (address self))))
  (imigrate! self)
  self)

7.1.15.1 Inverter Documentation

        <inverter>::(<number> <description>)

        <inverter>::value      => <number>::value
        <inverter>::set-value! => <number>::set-value!
        <inverter>::describe   => <description>::describe
        <inverter>::help
        <inverter>::invert
        <inverter>::inverter?

7.1.15.2 Number Documention

        <number>::()

        <number>::<x>

        <number>::value
        <number>::set-value!

7.1.15.3 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)
  (let* ((self (make-object
                (make-number 1)
                (make-description "A number which can be inverted")))
         (<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 (x) (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

7.1.16 Priority Queues

(require 'priority-queue)

This algorithm for priority queues is due to Introduction to Algorithms by T. Cormen, C. Leiserson, R. Rivest. 1989 MIT Press.

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.

Procedure: 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.

7.1.17 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: enqueue! q datum

Adds datum to the rear of queue q.

Procedure: dequeue! q

Procedure: queue-pop! 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.

Procedure: dequeue-all! q

Removes and returns (the list) of all contents of queue q.

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.

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

7.2 Sorting and Searching

7.2.1 Common List Functions

(require 'common-list-functions)

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

7.2.1.1 List construction

Function: make-list k

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* obj1 obj2 ...

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

7.2.1.2 Lists as sets

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

Function: adjoin e l

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) (adjoin 'foo '(bar baz bang)) => (foo bar baz bang)

Function: union l1 l2

union returns a list of all elements that are in l1 or 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)) => (1 2 3 4 5 6 7 8) (union '(0 1 2 3 4) '(3 4 5 6)) => (5 6 0 1 2 3 4)

Function: intersection l1 l2

intersection returns a list of 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 a list 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: subset? list1 list2

Returns #t if every element of list1 is eqv? an element of list2; otherwise returns #f.

Example:

(subset? '(1 2 3 4) '(3 4 5 6)) => #f (subset? '(1 2 3 4) '(6 5 4 3 2 1 0)) => #t

Function: member-if pred lst

member-if returns the list headed by the first element of lst to satisfy (pred element). Member-if returns #f if pred returns #f for every element in lst.

Example:

(member-if vector? '(a 2 b 4)) => #f (member-if number? '(a 2 b 4)) => (2 b 4)

Function: some pred lst1 lst2 ...

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 > '(1 3) '(2 4)) => #f

Function: every pred lst1 lst2 ...

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

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

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: list-of?? predicate

Returns a predicate which returns true if its argument is a list every element of which satisfies predicate.

Function: list-of?? predicate low-bound high-bound

low-bound and high-bound are non-negative integers. list-of?? returns a predicate which returns true if its argument is a list of length between low-bound and high-bound (inclusive); every element of which satisfies predicate.

Function: list-of?? predicate bound

bound is an integer. If bound is negative, list-of?? returns a predicate which returns true if its argument is a list of length greater than (- bound); every element of which satisfies predicate. Otherwise, list-of?? returns a predicate which returns true if its argument is a list of length less than or equal to bound; every element of which satisfies predicate.

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)) => (1 2 3 4) (remove-duplicates '(2 4 3 4)) => (2 4 3)

7.2.1.3 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 7.1.9 Collections) provides a version of collect generalized to collections.

Example:

(reduce + '(1 2 3 4)) => 10 (define (bad-sum . l) (reduce + l)) (bad-sum 1 2 3 4) == (reduce + (1 2 3 4)) == (+ (+ (+ 1 2) 3) 4) => 10 (bad-sum) == (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)

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 cdrs 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)) => (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)

7.2.1.4 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 7.4.4 Rev2 Procedures).

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

(define (subsets set) (if (null? set) '(()) (append (map (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 cdrs 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 (list 'foo 'bar 'baz 'bang)) (delete 'foo lst) => (bar baz bang) lst => (foo bar baz bang) (define lst (list 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 don't 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.

7.2.1.5 Non-List functions

Function: and? arg1 ...

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

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

7.2.2 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

Function: subst new old tree equ?

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. If subst is called with a fourth argument, equ? is the equality predicate.

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

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

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

(sort list predicate)

(sort! list/vector predicate?)

(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 not a list, vector, or string.

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, vector, or string; 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 or string, the sorted elements are put back in the same vector or string.

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

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

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

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

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

7.2.7 Space-Filling Curves

7.2.7.1 Peano-Hilbert Space-Filling Curve

(require 'hilbert-fill)

The Peano-Hilbert Space-Filling Curve is a one-to-one mapping between a unit line segment and an n-dimensional unit cube.

The integer procedures map the non-negative integers to an arbitrarily large n-dimensional cube with its corner at the origin and all coordinates are non-negative.

For any exact nonnegative integers scalar and rank,

(= scalar (hilbert-coordinates->integer
           (integer->hilbert-coordinates scalar rank)))
                                       => #t

Function: integer->hilbert-coordinates scalar rank

Returns a list of rank integer coordinates corresponding to exact non-negative integer scalar. The lists returned by integer->hilbert-coordinates for scalar arguments 0 and 1 will differ in the first element.

Function: hilbert-coordinates->integer coords

Returns an exact non-negative integer corresponding to coords, a list of non-negative integer coordinates.

7.2.7.2 Sierpinski Curve

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

7.2.8 Soundex

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

See Knuth, Vol. 3 Sorting and searching, pp 391--2

To manage unusual inputs, soundex omits all non-alphabetic characters. Consequently, in this implementation:

(soundex <string of blanks>) => "" (soundex "") => ""

Examples from Knuth:

(map soundex '("Euler" "Gauss" "Hilbert" "Knuth" "Lloyd" "Lukasiewicz")) => ("E460" "G200" "H416" "K530" "L300" "L222") (map soundex '("Ellery" "Ghosh" "Heilbronn" "Kant" "Ladd" "Lissajous")) => ("E460" "G200" "H416" "K530" "L300" "L222")

Some cases in which the algorithm fails (Knuth):

(map soundex '("Rogers" "Rodgers")) => ("R262" "R326") (map soundex '("Sinclair" "St. Clair")) => ("S524" "S324") (map soundex '("Tchebysheff" "Chebyshev")) => ("T212" "C121")

7.2.9 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; then old2 replaced with new2 .... Matches are found from the left. Matches do not overlap.

Function: count-newlines str

Returns the number of `#\newline' characters in string str.

7.2.10 Sequence Comparison

(require 'diff)

diff:edit-length implements the algorithm:

S. Wu, E. Myers, U. Manber, and W. Miller,
   "An O(NP) Sequence Comparison Algorithm,"
   Information Processing Letters 35, 6 (1990), 317-323.
   http://www.cs.arizona.edu/people/gene/vita.html

The values returned by diff:edit-length can be used to gauge the degree of match between two sequences.

Surprisingly, "An O(NP) Sequence Comparison Algorithm" does not derive the edit sequence; only the sequence length. Developing this linear-space sub-quadratic-time algorithm for computing the edit sequence required hundreds of hours of work. I have submitted a paper describing the algorithm to the Journal of Computational Biology.

If the items being sequenced are text lines, then the computed edit-list is equivalent to the output of the diff utility program. If the items being sequenced are words, then it is like the lesser known spiff program.

Function: diff:longest-common-subsequence array1 array2 =? p-lim

Function: diff:longest-common-subsequence array1 array2 =?

array1 and array2 are one-dimensional arrays. The procedure =? is used to compare sequence tokens for equality.

The non-negative integer p-lim, if provided, is maximum number of deletions of the shorter sequence to allow. diff:longest-common-subsequence will return #f if more deletions would be necessary.

diff:longest-common-subsequence returns a one-dimensional array of length (quotient (- (+ len1 len2) (diff:edit-length array1 array2)) 2) holding the longest sequence common to both arrays.

Function: diff:edits array1 array2 =? p-lim

Function: diff:edits array1 array2 =?

array1 and array2 are one-dimensional arrays. The procedure =? is used to compare sequence tokens for equality.

The non-negative integer p-lim, if provided, is maximum number of deletions of the shorter sequence to allow. diff:edits will return #f if more deletions would be necessary.

diff:edits returns a vector of length (diff:edit-length array1 array2) composed of a shortest sequence of edits transformaing array1 to array2.

Each edit is an integer:

k > 0

Inserts (array-ref array1 (+ -1 j)) into the sequence.

k < 0

Deletes (array-ref array2 (- -1 k)) from the sequence.

Function: diff:edit-length array1 array2 =? p-lim

Function: diff:edit-length array1 array2 =?

array1 and array2 are one-dimensional arrays. The procedure =? is used to compare sequence tokens for equality.

The non-negative integer p-lim, if provided, is maximum number of deletions of the shorter sequence to allow. diff:edit-length will return #f if more deletions would be necessary.

diff:edit-length returns the length of the shortest sequence of edits transformaing array1 to array2.

(diff:longest-common-subsequence "fghiejcklm" "fgehijkpqrlm" eqv?)
=> "fghijklm"

(diff:edit-length "fghiejcklm" "fgehijkpqrlm" eqv?)
=> 6

(diff:edits "fghiejcklm" "fgehijkpqrlm" eqv?)
=> #As32(3 -5 -7 8 9 10)
       ; e  c  h p q  r

7.3 Procedures

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

7.3.1 Type Coercion

Function: type-of obj

Returns a symbol name for the type of obj.

Function: coerce obj result-type

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

7.3.2 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-capitalize! 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.

Function: symbol-append obj1 ...

Converts obj1 ... to strings, appends them, and converts to a symbol which is returned. Strings and numbers are converted to read's symbol case; the case of symbol characters is not changed. #f is converted to the empty string (symbol).

Function: StudlyCapsExpand str delimiter

Function: StudlyCapsExpand str

delimiter must be a string or character. If absent, delimiter defaults to `-'. StudlyCapsExpand returns a copy of str where delimiter is inserted between each lower-case character immediately followed by an upper-case character; and between two upper-case characters immediately followed by a lower-case character.

(StudlyCapsExpand "aX" " ") => "a X" (StudlyCapsExpand "aX" "..") => "a..X" (StudlyCapsExpand "AX") => "AX" (StudlyCapsExpand "Ax") => "Ax" (StudlyCapsExpand "AXLE") => "AXLE" (StudlyCapsExpand "aAXACz") => "a-AXA-Cz" (StudlyCapsExpand "AaXACz") => "Aa-XA-Cz" (StudlyCapsExpand "AAaXACz") => "A-Aa-XA-Cz" (StudlyCapsExpand "AAaXAC") => "A-Aa-XAC"

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

7.3.4 Line I/O

(require 'line-i/o)

Function: read-line

Function: read-line port

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.

Procedure: read-line! string

Procedure: read-line! string port

Fills string 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 string

Function: write-line string port

Writes string followed by a newline 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-input-port.

Function: system->line command tmp

Function: system->line command

command must be a string. The string tmp, if supplied, is a path to use as a temporary file. system->line calls system with command as argument, redirecting stdout to file tmp. system->line returns a string containing the first line of output from tmp.

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

Procedure: add-process! proc

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

7.3.6 Metric Units

(require 'metric-units)

http://swissnet.ai.mit.edu/~jaffer/MIXF.html

Metric Interchange Format is a character string encoding for numerical values and units which:

• is unambiguous in all locales;

• uses only [TOG] "Portable Character Set" characters matching "Basic Latin" characters in Plane 0 of the Universal Character Set [UCS];

• is transparent to [UTF-7] and [UTF-8] UCS transformation formats;

• is human readable and writable;

• is machine readable and writable;

• incorporates SI prefixes and units;

• incorporates [ISO 6093] numbers; and

• incorporates [IEC 60027-2] binary prefixes.

In the expression for the value of a quantity, the unit symbol is placed after the numerical value. A dot (PERIOD, `.') is placed between the numerical value and the unit symbol.

Within a compound unit, each of the base and derived symbols can optionally have an attached SI prefix.

Unit symbols formed from other unit symbols by multiplication are indicated by means of a dot (PERIOD, `.') placed between them.

Unit symbols formed from other unit symbols by division are indicated by means of a SOLIDUS (`/') or negative exponents. The SOLIDUS must not be repeated in the same compound unit unless contained within a parenthesized subexpression.

The grouping formed by a prefix symbol attached to a unit symbol constitutes a new inseparable symbol (forming a multiple or submultiple of the unit concerned) which can be raised to a positive or negative power and which can be combined with other unit symbols to form compound unit symbols.

The grouping formed by surrounding compound unit symbols with parentheses (`(' and `)') constitutes a new inseparable symbol which can be raised to a positive or negative power and which can be combined with other unit symbols to form compound unit symbols.

Compound prefix symbols, that is, prefix symbols formed by the juxtaposition of two or more prefix symbols, are not permitted.

Prefix symbols are not used with the time-related unit symbols min (minute), h (hour), d (day). No prefix symbol may be used with dB (decibel). Only submultiple prefix symbols may be used with the unit symbols L (liter), Np (neper), o (degree), oC (degree Celsius), rad (radian), and sr (steradian). Submultiple prefix symbols may not be used with the unit symbols t (metric ton), r (revolution), or Bd (baud).

A unit exponent follows the unit, separated by a CIRCUMFLEX (`^'). Exponents may be positive or negative. Fractional exponents must be parenthesized.

7.3.6.1 SI Prefixes

       Factor     Name    Symbol  |  Factor     Name    Symbol
       ======     ====    ======  |  ======     ====    ======
        1e24      yotta      Y    |   1e-1      deci       d
        1e21      zetta      Z    |   1e-2      centi      c
        1e18      exa        E    |   1e-3      milli      m
        1e15      peta       P    |   1e-6      micro      u
        1e12      tera       T    |   1e-9      nano       n
        1e9       giga       G    |   1e-12     pico       p
        1e6       mega       M    |   1e-15     femto      f
        1e3       kilo       k    |   1e-18     atto       a
        1e2       hecto      h    |   1e-21     zepto      z
        1e1       deka       da   |   1e-24     yocto      y

7.3.6.2 Binary Prefixes

These binary prefixes are valid only with the units B (byte) and bit. However, decimal prefixes can also be used with bit; and decimal multiple (not submultiple) prefixes can also be used with B (byte).

                Factor       (power-of-2)  Name  Symbol
                ======       ============  ====  ======
       1.152921504606846976e18  (2^60)     exbi    Ei
          1.125899906842624e15  (2^50)     pebi    Pi
             1.099511627776e12  (2^40)     tebi    Ti
                1.073741824e9   (2^30)     gibi    Gi
                   1.048576e6   (2^20)     mebi    Mi
                      1.024e3   (2^10)     kibi    Ki

7.3.6.3 Unit Symbols

    Type of Quantity      Name          Symbol   Equivalent
    ================      ====          ======   ==========
time                      second           s
time                      minute           min = 60.s
time                      hour             h   = 60.min
time                      day              d   = 24.h
frequency                 hertz            Hz    s^-1
signaling rate            baud             Bd    s^-1
length                    meter            m
volume                    liter            L     dm^3
plane angle               radian           rad
solid angle               steradian        sr    rad^2
plane angle               revolution     * r   = 6.283185307179586.rad
plane angle               degree         * o   = 2.777777777777778e-3.r
information capacity      bit              bit
information capacity      byte, octet      B   = 8.bit
mass                      gram             g
mass                      ton              t     Mg
mass              unified atomic mass unit u   = 1.66053873e-27.kg
amount of substance       mole             mol
catalytic activity        katal            kat   mol/s
thermodynamic temperature kelvin           K
centigrade temperature    degree Celsius   oC
luminous intensity        candela          cd
luminous flux             lumen            lm    cd.sr
illuminance               lux              lx    lm/m^2
force                     newton           N     m.kg.s^-2
pressure, stress          pascal           Pa    N/m^2
energy, work, heat        joule            J     N.m
energy                    electronvolt     eV  = 1.602176462e-19.J
power, radiant flux       watt             W     J/s
logarithm of power ratio  neper            Np
logarithm of power ratio  decibel        * dB  = 0.1151293.Np
electric current          ampere           A
electric charge           coulomb          C     s.A
electric potential, EMF   volt             V     W/A
capacitance               farad            F     C/V
electric resistance       ohm              Ohm   V/A
electric conductance      siemens          S     A/V
magnetic flux             weber            Wb    V.s
magnetic flux density     tesla            T     Wb/m^2
inductance                henry            H     Wb/A
radionuclide activity     becquerel        Bq    s^-1
absorbed dose energy      gray             Gy    m^2.s^-2
dose equivalent           sievert          Sv    m^2.s^-2

* The formulas are:

• r/rad = 8 * atan(1)
• o/r = 1 / 360
• db/Np = ln(10) / 20

Function: si:conversion-factor to-unit from-unit

If the strings from-unit and to-unit express valid unit expressions for quantities of the same unit-dimensions, then the value returned by si:conversion-factor will be such that multiplying a numerical value expressed in from-units by the returned conversion factor yields the numerical value expressed in to-units.

Otherwise, si:conversion-factor returns:

-3

if neither from-unit nor to-unit is a syntactically valid unit.

-2

if from-unit is not a syntactically valid unit.

-1

if to-unit is not a syntactically valid unit.

0

if linear conversion (by a factor) is not possible.

(si:conversion-factor "km/s" "m/s" ) => 0.001     
(si:conversion-factor "N"    "m/s" ) => 0         
(si:conversion-factor "moC"  "oC"  ) => 1000      
(si:conversion-factor "mK"   "oC"  ) => 0         
(si:conversion-factor "rad"  "o"   ) => 0.0174533 
(si:conversion-factor "K"    "o"   ) => 0         
(si:conversion-factor "K"    "K"   ) => 1         
(si:conversion-factor "oK"   "oK"  ) => -3        
(si:conversion-factor ""     "s/s" ) => 1         
(si:conversion-factor "km/h" "mph" ) => -2        

7.4 Standards Support

7.4.1 RnRS

The r2rs, r3rs, r4rs, and r5rs features attempt to provide procedures and macros to bring a Scheme implementation to the desired version of Scheme.

Feature: r2rs

Requires features implementing procedures and optional procedures specified by Revised^2 Report on the Algorithmic Language Scheme; namely rev3-procedures and rev2-procedures.

Feature: r3rs

Requires features implementing procedures and optional procedures specified by Revised^3 Report on the Algorithmic Language Scheme; namely rev3-procedures.

Note: SLIB already mandates the r3rs procedures which can be portably implemented in r4rs implementations.

Feature: r4rs

Requires features implementing procedures and optional procedures specified by Revised^4 Report on the Algorithmic Language Scheme; namely rev4-optional-procedures.

Feature: r5rs

Requires features implementing procedures and optional procedures specified by Revised^5 Report on the Algorithmic Language Scheme; namely values, macro, and eval.

7.4.2 With-File

(require 'with-file)

Function: with-input-from-file file thunk

Function: with-output-to-file file thunk

Description found in R4RS.

7.4.3 Transcripts

(require 'transcript)

Function: transcript-on filename

Function: transcript-off filename

Redefines read-char, read, write-char, write, display, and newline.

7.4.4 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, chokes 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! pair1 ...

Destructively appends its arguments. Equivalent to nconc.

Function: 1+ n

Adds 1 to 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 `?'.

7.4.5 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

7.4.6 Multi-argument / and -

(require 'multiarg/and-)

For the specification of these optional forms, See section `Numerical operations' in Revised(4) Scheme.

Function: / dividend divisor1 ...

Function: - minuend subtrahend1 ...

7.4.7 Multi-argument Apply

(require 'multiarg-apply)

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

Function: apply proc arg1 ...

7.4.8 Rationalize

(require 'rationalize)

Function: rationalize x e

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.

Function: find-ratio x e

find-ratio returns the list of the simplest numerator and denominator whose quotient differs from x by no more than e.

(find-ratio 3/97 .0001) => (3 97) (find-ratio 3/97 .001) => (1 32)

Function: find-ratio-between x y

find-ratio-between returns the list of the simplest numerator and denominator between x and y.

(find-ratio-between 2/7 3/5) => (1 2) (find-ratio-between -3/5 -2/7) => (-1 2)

7.4.9 Promises

(require 'promise)

Function: make-promise proc

Function: force promise

(require 'delay) provides force and delay:

Macro: delay obj

Change occurrences of (delay expression) to

(make-promise (lambda () expression))

(see section `Control features' in Revised(4) Scheme).

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

7.4.11 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

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

7.4.13 SRFI

(require 'srfi)

Implements Scheme Request For Implementation (SRFI) as described at http://srfi.schemers.org/

The Copyright terms of each SRFI states:

"However, this document itself may not be modified in any way, ..."

Therefore, the specification of SRFI constructs must not be quoted without including the complete SRFI document containing discussion and a sample implementation program.

Macro: cond-expand <clause1> <clause2> ...

Syntax: Each <clause> should be of the form

(<feature> <expression1> ...)

where <feature> is a boolean expression composed of symbols and `and', `or', and `not' of boolean expressions. The last <clause> may be an "else clause," which has the form

(else <expression1> <expression2> ...).

The first clause whose feature expression is satisfied is expanded. If no feature expression is satisfied and there is no else clause, an error is signaled.

SLIB cond-expand is an extension of SRFI-0, http://srfi.schemers.org/srfi-0/srfi-0.html.

7.4.13.1 SRFI-1

(require 'srfi-1)

Implements the SRFI-1 list-processing library as described at http://srfi.schemers.org/srfi-1/srfi-1.html

Constructors

Function: xcons d a

(define (xcons d a) (cons a d)).

Function: list-tabulate len proc

Returns a list of length len. Element i is (proc i) for 0 <= i < len.

Function: cons* obj1 obj2

Function: list-copy flist

Function: iota count start step

Function: iota count start

Function: iota count

Returns a list of count numbers: (start, start+step, ..., start+(count-1)*step).

Function: circular-list obj1 obj2 ...

Returns a circular list of obj1, obj2, ....

Predicates

Function: proper-list? obj

Function: circular-list? x

Function: dotted-list? obj

Function: null-list? obj

Function: not-pair? obj

Function: list= =pred list ...

Selectors

Function: first pair

Function: second pair

Function: third pair

Function: fourth pair

Function: fifth pair

Function: sixth obj

Function: seventh obj

Function: eighth obj

Function: ninth obj

Function: tenth obj

Function: car+cdr pair

Function: drop lst k

Function: take lst k

Procedure: take! lst k

Function: take-right lst k

Function: drop-right lst k

Procedure: drop-right! lst k

Function: split-at lst k

Procedure: split-at! lst k

Function: last lst

(car (last-pair lst))

Miscellaneous

Function: length+ obj

Function: concatenate lists

Function: concatenate! lists

Procedure: reverse! lst

Function: append-reverse rev-head tail

Function: append-reverse! rev-head tail

Function: zip list1 list2 ...

Function: unzip1 lst

Function: unzip2 lst

Function: unzip3 lst

Function: unzip4 lst

Function: unzip5 lst

Function: count pred list1 list2 ...

Fold and Unfold

Procedure: map! f list1 clist2 ...

Function: pair-for-each f clist1 clist2 ...

Filtering and Partitioning

Function: filter pred lis

Procedure: filter! pred l

Function: partition pred list

Searching

Function: find pred list

Function: find-tail pred list

Function: remove pred l

Procedure: remove! pred l

Function: any pred clist1 clist2 ...

Function: list-index pred clist1 clist2 ...

Function: span pred list

Function: member obj list pred

Function: member obj list

member returns the first sublist of list whose car is obj, where the sublists of list are the non-empty lists returned by (list-tail list k) for k less than the length of list. If obj does not occur in list, then #f (not the empty list) is returned. The procedure pred is used for testing equality. If pred is not provided, `equal?' is used.

Deleting

Association lists

Function: assoc obj alist pred

Function: assoc obj alist

alist (for "association list") must be a list of pairs. These procedures find the first pair in alist whose car field is obj, and returns that pair. If no pair in alist has obj as its car, then #f (not the empty list) is returned. The procedure pred is used for testing equality. If pred is not provided, `equal?' is used.

Set operations

7.4.13.2 SRFI-2

(require 'srfi-2)

Macro: and-let* claws body ...

http://srfi.schemers.org/srfi-2/srfi-2.html

7.4.13.3 SRFI-8

(require 'srfi-8)

Special Form: receive formals expression body ...

http://srfi.schemers.org/srfi-8/srfi-8.html

7.4.13.4 SRFI-9

(require 'srfi-9)

http://srfi.schemers.org/srfi-9/srfi-9.html

Special Form: define-record-type <type-name> (<constructor-name> <field-tag> ...) <predicate-name> <field spec> ...

Where

<field-spec> == (<field-tag> <accessor-name>) == (<field-tag> <accessor-name> <modifier-name>)

define-record-type is a syntax wrapper for the SLIB record module.

7.5 Session Support

7.5.1 Repl

(require 'repl)

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

Procedure: repl:top-level repl:eval

reads, repl:evals and writes 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)

7.5.2 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 4.2 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.