CS 151, Scheme48 extensions

CS 151 (Artificial Intelligence)
Scheme48 Extensions and Missing Features

The CS 151 class binary contains a variety of features not described in the R5RS Scheme Report, and a few R5RS features appear not to work (or work well, or work in obvious ways).

Missing features

Some of the complex number functions appear not to work in scheme48 and I don't know why. (I've tried loading the modules that seem relevant.)

Hash tables

(MAKE-TABLE) => <table> (MAKE-STRING-TABLE) => <string-table> (MAKE-INTEGER-TABLE) => <integer-table> (MAKE-SYMBOL-TABLE) => <symbol-table>: Make a new, empty table. MAKE-TABLE returns a table that uses EQ? for comparing keys and an ad-hoc hash function. The other three functions return tables that are correctly tuned for storing strings, integers, and symbols.
(MAKE-TABLE-MAKER <comparison-procedure> <hash-procedure>) => <procedure>: Returns a procedure of no arguments that makes tables that use the given comparison and hash procedures. (<comparison-procedure> <key1> <key2>) => <boolean> (<hash-procedure> <key>) => <non-negative-integer> See the definitions of functions such as make-integer-table (in big/general-table.scm) for examples of its use.
(TABLE? <x>) => <boolean>: True if <x> is a table.
(TABLE-REF <table> <key>) => <x>: Return the value for <key> in <table>, or #F if there is none. <key> should be of a type appropriate for <table>.
(TABLE-SET! <table> <key> <value>) => <undefined>: Make <value> be the value of <key> in <table>. <key> should be of a type appropriate for <table>.
(TABLE-WALK <procedure> <table>) => <undefined>: Apply <procedure>, which must accept two arguments, to every associated key and value in <table>.

Multiple values

Scheme provides some basic functions that allow a function to return multiple values: values and call-with-values (see the R5RS Report, p. 34). However, call-with-values is awkward to use. Here are some functions that are easier to use.

(MULTIPLE-SET! <list-of-identifiers> <expression>)

Evaluates <expression> and binds its return values to the identifiers in the list. <expression> should return as many values as there are identifiers in the list. Example:

    (define (baz x y) (values x y (+ x y)))
    (multiple-set! (a b c) (baz 2 3))

(MULTIPLE-DEFINE <list-of-identifiers> <expression>)

MULTIPLE-DEFINE is to MULTIPLE-SET! as DEFINE is to SET!.

(RECEIVE <list-of-identifiers> <expression> <body> ...)

Bind <identifiers> to the values returned by <exp>, and evaluate <body> in the resulting environment. Similar to LET for regular return values. <expression> should return as many values as there are identifiers in the list.

Output

(FORMAT <port-spec> <format-string> . <arguments>) => <string> or <undefined>

Prints the arguments to the port as directed by the string. <port-spec> should be either:

An output port.: The output is written directly to the port. The result of the call to FORMAT is undefined.
#T.: The output is written to the current output port. The result of the call to FORMAT is undefined.
#F.: The output is written to a string, which is then the value returned from the call to FORMAT.

Characters in <format-string> which are not preceded by a ~ are written directly to the output. Characters preceded by a ~ have the following meaning (case is irrelevant; ~a and ~A have the same meaning):

~~: prints a single ~
~A: prints the next argument using DISPLAY
~D: prints the next argument as a decimal number
~S: prints the next argument using WRITE
~%: prints a newline character
~&: prints a NEWLINE character if the previous printed character was not one (this is implemented using FRESH-LINE)
~?: performs a recursive call to FORMAT using the next two arguments as the string and the list of arguments

Example: (format #t "The output of foo is ~s~.%" (foo 2 7 9))

(FORCE-OUTPUT <port>)

Force buffered output to actually appear right now. Example: (force-output (current-output-port)).

(P <thing>) (P <thing> <output-port>)

Pretty-print <thing>. The current output port is used if no port is specified.

  Example:

    (p '(do ((foo 1)) (> x foo) (begin (+ foo 1) (* foo 2))))

  prints 

    (do ((foo 1))
        (> x foo)
      (begin (+ foo 1) (* foo 2)))

Records

"Record" is lisp-speak for "struct."

(DEFINE-RECORD-TYPE <tag> <type-name> (<constructor-name> <field-tag>*) <predicate-name> (<field-tag> <accessor-name> [<modifier-name>])*)

Defines a new type of record. Sets up a function (the constructor) for making objects of this type, a function (the predicate) to test whether an object is of this type, and functions to set and access the fields of the record (accessors and modifiers).

Example:

      (define-record-type pare :pare
        (kons x y)
	pare?
	(x kar set-kar!)
	(y kdr))

This defines KONS to be a constructor, KAR and KDR to be accessors, SET-KAR! to be a modifier, and PARE? to be a predicate for a new type of object. The type itself is named :PARE. PARE is a tag used in printing the new objects. The field tags X and Y are used in the inspector and to match constructor arguments with fields.

(DEFINE-RECORD-DISCLOSER <type> <print-function>)

By default, an object of record type :pare prints as #{Pare}. The print method can be modified using DEFINE-RECORD-DISCLOSER.

Example:
      (define-record-discloser :pare
        (lambda (p) `(pare ,(kar p) ,(kdr p))))

Sorting lists

(INSERT <item> <list> <comparison-function>): <list> is presumably sorted, using <comparison-function>. Inserts <item> into <list> in correct position.
(SORT-LIST <list> <a<b-procedure>) => <list> (SORT-LIST! <list> <a<b-procedure>) => <list>: Returns a sorted copy of <list>. The sorting algorithm is stable. (SORT-LIST '(6 5 1 3 2 4) <) => '(1 2 3 4 5 6). SORT-LIST! trashes its input. SORT-LIST leaves it input intact.

List utilities

(MEMQ? <element> <list>) => <boolean>: Returns true if <element> is in <list>, false otherwise.
(ANY? <predicate> <list>) => <boolean>: Returns true if <predicate> is true for any element of <list>.
(EVERY? <predicate> <list>) => <boolean>: Returns true if <predicate> is true for every element of <list>.
(ANY <predicate> <list>) (FIRST <predicate> <list>): ANY returns some element of <list> for which <predicate> is true, or #F if there are none. FIRST does the same except that it returns the first element for which is true.
(FILTER <predicate> <list>) (FILTER! <predicate> <list>): Returns a list containing all of the elements of <list> for which is true. The order of the elements is preserved. FILTER! may reuse the storage of <list>.
(FILTER-MAP <list>): The same as FILTER except the returned list contains the results of applying <procedure> instead of elements of <list>. (FILTER-MAP p l) is the same as (FILTER IDENTITY (MAP p l)).
(PARTITION-LIST <predicate> <list>) => <list> (PARTITION-LIST! <predicate> <list>) => <list> <list>: The first return value contains those elements for which <predicate> is true, the second contains the remaining elements. The order of the elements is preserved. PARTITION-LIST! may resuse the storage of the <list>.
(REMOVE-DUPLICATES <list>) => <list>: Returns its argument with all duplicate elements removed. The first instance of each element is preserved.
(DELQ <element> <list>) => <list> (DELQ! <element> <list>) => <list> (DELETE <predicate> <list>) => <list>: All three of these return <list> with some elements removed. DELQ removes all elements EQ? to <element>. DELQ! does the same and may reuse the storage of the list argument. DELETE removes all elements for which <predicate> is true.
(REVERSE! <list>) => <list>: Destructively reverses <list>.
(POSITION <item> <list>) (POSV <item> <list>) (POSQ <item> <list>): Returns the position of <item> in <list>. POSITION identifies the element using equal?, POSV with eqv?, and POSQ with eq?.
(LAST <list>): Returns the last element in the list.
(SUBLIST <list> <start> <end>): Returns the subsection of the list from <start> to <end>, including the item at position <start> but not that at position <end>.
(REDUCE <operator> <identity-value> <list>): Uses operator to combine all the elements in the list. The identity value is returned when the list is empty. For example, (reduce + 0 list) adds together all the elements in the list (a list, presumably, of numbers).

Miscellany

(ERROR <format-string> . format-args)

Triggers an error, printing the string.

  example:
      (error "this is my error message")
      (define symbol 'something)
      (error "this is error ~s" symbol)

(MAKE-RANDOM <seed>)

Random number generator. Unfortunately, there's no feature for providing it with a random seed.

Example:
        (define random (make-random <seed>))
	(random)  =>  a pseudo-random number between 0 and 2^28

(IDENTITY <any>) => <any> (NO-OP <any>) => <any>

These both just return their argument. NO-OP is guaranteed not to be compiled in-line, IDENTITY may be.

(CONCATENATE-SYMBOL . <components>)

Returns the symbol whose name is produced by concatenating the DISPLAYed representations of <components>. (CONCATENATE-SYMBOL 'abc "-" 4) => 'abc-4

Multi-dimensional Arrays

(MAKE-ARRAY <initial-value> <bound1> ..<boundk>)

Create a k-dimensional array, in which the ith dimension goes from zero to <boundi>.

(ARRAY-SHAPE <array>)

Return the list of bounds for the array.

(ARRAY-REF <array> <index1> ...) (ARRAY-SET! <array> <value> <index1> ...)

Set and retrieve values from an array location.

(MAKE-SHARED-ARRAY <array> <linear-map> <bound1> ...)

The <linear-map> argument to MAKE-SHARED-ARRAY is a linear function that maps indices into the shared array into a list of indices into the original array. The array returned by MAKE-SHARED-ARRAY shares storage with the original array.

Example: (array-ref (make-shared-array a f i1 i2 ... iN) j1 j2 ... jM)
         does the same thing as
         (apply array-ref a (f j1 j2 ... jM))

(COPY-ARRAY <array>)

Copy the array.

(ARRAY->VECTOR <array>)

ARRAY->VECTOR returns a vector containing the elements of an array in row-major order.

(ARRAY <bounds> . <elements>)

Create an array whose bounds are given by the list <bounds> and whose values are given by <elements>.

Example:
   (define yy (array '(2 3) 0 1 2 10 11 12))
   makes the 2 by 3 array
       0  1   2 
       10 11 12

This page is maintained by Margaret Fleck.

CS 151 (Artificial Intelligence) Scheme48 Extensions and Missing Features