3.3.3 · Representing mutable tables

A table mutates records while lookup keeps the representation private.

An association list behind lookup and insert! changes a record in place, links a missing record into the table, and nests a subtable for a new key.

Guiding question

Which links must change when a table updates one record or creates a new nested key path?

Use assoc to locate a mutable record behind a table header
Update an existing record with set-cdr!
Insert a new record by changing the table tail
Represent a two-key table as subtables containing records
Distinguish lookup failure from a stored value

The one-key table is a mutable list whose first element is a private header. lookup searches only the records after that header. insert! mutates the cdr of an existing key-value pair when the key is present; otherwise it changes the table header pair so a new record becomes part of the association list. Client code does not depend on insertion order or pair layout.

The two-key table stores a first-key record whose cdr is itself an association list. Inserting a new second key mutates that subtable, while a new first key links an entire subtable into the outer table. Updating arithmetic from 10 to 11 changes the existing innermost record rather than creating a duplicate. These examples use #f as the missing result, so storing #f would require a richer lookup protocol.

SICP code621 of 1,048,576 UTF-8 bytes

(begin
  (define (make-table) (list '*table*))
  (define (lookup key table)
    (let ((record (assoc key (cdr table))))
      (if record (cdr record) #f)))
  (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)
  (define table (make-table))
  (insert! 'alpha 4 table)
  (insert! 'beta 5 table)
  (insert! 'alpha 9 table)
  (list (lookup 'alpha table)
        (lookup 'beta table)
        (lookup 'gamma table)
        table))

Examples

Result—

Output: —
Value: —
Diagnostic: —

Execution trace0 / 0 events

Expected result

The first program returns (9 5 #f (*table* (beta . 5) (alpha . 9))). The second returns (11 20 30 #f (*table* (language (scheme . 30)) (math (algebra . 20) (arithmetic . 11)))).

Trace focus

Compare assoc traversals that find alpha with the gamma traversal that reaches the end. Distinguish set-cdr! on an existing record from set-cdr! on the table or subtable header that links a new record. In the nested run, follow the outer key before the inner key and verify that the arithmetic update changes one existing pair.

Try it yourself

Change the program and compare the result.

Add physics under math, update scheme to 31, and add a second language record. Predict the outer and inner record order before running, then explain which updates mutate records and which mutate table tails.

Show hint

A present key changes the cdr of its record. A missing key creates a new pair and links it at the front of the relevant association list.

Complete this lesson

0 of 21 lessons complete in this chapter0%