Representing Tables

When we studied various ways of representing sets in chapter 2, we mentioned in section the task of maintaining a table of records indexed by identifying keys. In the implementation of data-directed programming in section , we made extensive use of two-dimensional tables, in which information is stored and retrieved using two keys. Here we see how to build tables as mutable list structures.

We first consider a one-dimensional table, in which each value is
stored under a single key. We implement the table as a list of
records, each of which is implemented as a pair consisting of a key
and the associated value. The records are glued together to form a
list by pairs whose `car`s point to successive records. These
gluing pairs are called the
*backbone* of the table. In order to
have a place that we can change when we add a new record to the table,
we build the table as a
*headed list*. A headed list has a
special backbone pair at the beginning, which holds a dummy
``record''--in this case the arbitrarily chosen symbol `*table*`.
Figure shows the box-and-pointer diagram for the table

a: 1 b: 2 c: 3

To extract information from a table we use the `lookup`
procedure, which takes a key as argument and returns the associated
value (or false if there is no value stored under that key).
`Lookup` is defined in terms of the `assoc` operation, which
expects a key and a list of records as arguments. Note that `
assoc` never sees the dummy record. `Assoc` returns the record
that has the given key as its `car`.^{}
`Lookup` then
checks to see that the resulting record returned by `assoc` is not
false, and returns the value (the `cdr`) of the record.

(define (lookup key table) (let ((record (assoc key (cdr table)))) (if record (cdr record) false))) (define (assoc key records) (cond ((null? records) false) ((equal? key (caar records)) (car records)) (else (assoc key (cdr records)))))

To insert a value in a table under a specified key, we first use `
assoc` to see if there is already a record in the table with this key.
If not, we form a new record by `cons`ing the key with the value,
and insert this at the head of the table's list of records, after the
dummy record. If there already is a record with this key, we set the
`cdr` of this record to the designated new value. The header of
the table provides us with a fixed location to modify in order to
insert the new record.^{}

(define (insert! key value table) (let ((record (assoc key (cdr table)))) (if record (set-cdr! record value) (set-cdr! table (cons (cons key value) (cdr table))))) 'ok)

To construct a new table, we simply create a list containing the
symbol `*table*`:

(define (make-table) (list '*table*))

Two-dimensional tables

In a two-dimensional table, each value is indexed by two keys. We can construct such a table as a one-dimensional table in which each key identifies a subtable. Figure shows the box-and-pointer diagram for the table

math: +: 43 -: 45 *: 42 letters: a: 97 b: 98which has two subtables. (The subtables don't need a special header symbol, since the key that identifies the subtable serves this purpose.)

When we look up an item, we use the first key to identify the correct subtable. Then we use the second key to identify the record within the subtable.

(define (lookup key-1 key-2 table) (let ((subtable (assoc key-1 (cdr table)))) (if subtable (let ((record (assoc key-2 (cdr subtable)))) (if record (cdr record) false)) false)))

To insert a new item under a pair of keys, we use `assoc` to see if
there is a subtable stored under the first key. If not, we build a
new subtable containing the single record (`key-2`, `value`)
and insert it into the table under the first key. If a subtable
already exists for the first key, we insert the new record into this
subtable, using the insertion method for one-dimensional tables
described above:

(define (insert! key-1 key-2 value table) (let ((subtable (assoc key-1 (cdr table)))) (if subtable (let ((record (assoc key-2 (cdr subtable)))) (if record (set-cdr! record value) (set-cdr! subtable (cons (cons key-2 value) (cdr subtable))))) (set-cdr! table (cons (list key-1 (cons key-2 value)) (cdr table))))) 'ok)

Creating local tables

The `lookup` and `insert!` operations defined above take the
table as an argument. This enables us to use programs that access
more than one table. Another way to deal with multiple tables is to
have separate `lookup` and `insert!` procedures for each
table. We can do this by representing a table procedurally, as an
object that maintains an internal table as part of its local state.
When sent an appropriate message, this ``table object'' supplies the
procedure with which to operate on the internal table. Here is a
generator for two-dimensional tables represented in this fashion:

(define (make-table) (let ((local-table (list '*table*))) (define (lookup key-1 key-2) (let ((subtable (assoc key-1 (cdr local-table)))) (if subtable (let ((record (assoc key-2 (cdr subtable)))) (if record (cdr record) false)) false))) (define (insert! key-1 key-2 value) (let ((subtable (assoc key-1 (cdr local-table)))) (if subtable (let ((record (assoc key-2 (cdr subtable)))) (if record (set-cdr! record value) (set-cdr! subtable (cons (cons key-2 value) (cdr subtable))))) (set-cdr! local-table (cons (list key-1 (cons key-2 value)) (cdr local-table))))) 'ok) (define (dispatch m) (cond ((eq? m 'lookup-proc) lookup) ((eq? m 'insert-proc!) insert!) (else (error "Unknown operation - TABLE" m)))) dispatch))

Using `make-table`, we could implement the `get` and `put`
operations used in section for data-directed
programming, as follows:

(define operation-table (make-table)) (define get (operation-table 'lookup-proc)) (define put (operation-table 'insert-proc!))

**Exercise.**
In the table implementations above, the keys are tested for equality
using `equal?` (called by `assoc`). This is not always the appropriate test. For
instance, we might have a table with numeric keys in which we don't
need an exact match to the number we're looking up,
but only a number within some tolerance of it.
Design a table constructor `
make-table` that takes as an argument a `same-key?` procedure
that will be used to test ``equality'' of keys. `Make-table` should
return a `dispatch` procedure that can be used to access
appropriate `lookup` and `insert!` procedures for a local
table.

**Exercise.**
Generalizing one- and two-dimensional tables, show how to implement a
table in which values are stored under an arbitrary number of keys and
different values may be stored under different numbers of keys. The
`lookup` and `insert!` procedures should take as input a list
of keys used to access the table.

**Exercise.**
To search a table as implemented above, one needs to scan through the
list of records. This is basically the unordered list representation of
section . For large tables, it may be more
efficient to structure the table in a different manner. Describe a
table implementation where the (key, value) records are organized
using a binary tree, assuming that keys can be ordered in some way
(e.g., numerically or alphabetically). (Compare
exercise of chapter 2.)

**Exercise.**
*Memoization* (also called *tabulation*) is a technique that
enables a procedure to record, in a local table, values that have
previously been computed. This technique can make a vast difference
in the performance of a program. A memoized procedure maintains a
table in which values of previous calls are stored
using as keys the arguments that produced the values. When the
memoized procedure is asked to compute a value, it first checks the
table to see if the value is already there and, if so, just returns
that value. Otherwise, it computes the new value in the ordinary way
and stores this in the table. As an example of memoization, recall
from section the exponential process for
computing Fibonacci numbers:

(define (fib n) (cond ((= n 0) 0) ((= n 1) 1) (else (+ (fib (- n 1)) (fib (- n 2))))))The memoized version of the same procedure is

(define memo-fib (memoize (lambda (n) (cond ((= n 0) 0) ((= n 1) 1) (else (+ (memo-fib (- n 1)) (memo-fib (- n 2))))))))where the memoizer is defined as

(define (memoize f) (let ((table (make-table))) (lambda (x) (let ((previously-computed-result (lookup x table))) (or previously-computed-result (let ((result (f x))) (insert! x result table) result))))))Draw an environment diagram to analyze the computation of