When we studied various ways of representing sets in chapter 2, we
mentioned in section 2.3.3 the task of
maintaining a table of records
indexed by identifying keys. In the
implementation of data-directed programming in
section 2.4.3, 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
carsheads
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*.string "*table*".
Figure 3.43
Figure 3.44
shows the box-and-pointer diagram for the table
To extract information from a table we use the
lookupprocedure,function,
which takes a key as argument and returns the associated value (or
falseundefined
if
there is no value stored under that key).
LookupThe function 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.
AssocThe function assoc
returns the record that has the given key as its
carhead.[1]LookupThe function lookup
then checks to see that the resulting record returned by
assoc is not
false,undefined,
and returns the value (the
cdr)tail)
of the record.
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
consingpairing
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
cdrtail
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.[2]
Original
JavaScript
(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)
function insert(key, value, table) {
const record = assoc(key, tail(table));
if (is_undefined(record)) {
set_tail(table,
pair(pair(key, value), tail(table)));
} else {
set_tail(record, value);
}
return "ok";
}
To construct a new table, we simply create a list containing
the symbol *table*:
just the string "*table*":
Original
JavaScript
(define (make-table)
(list '*table*))
function make_table() {
return 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 3.45
Figure 3.46
shows the box-and-pointer diagram for the table
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,(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:
The lookup and
insert!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!insertproceduresfunctions
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
procedurefunction
with which to operate on the internal table. Here is a generator for
two-dimensional tables represented in this fashion:
function make_table() {
const local_table = list("*table*");
function lookup(key_1, key_2) {
const subtable = assoc(key_1, tail(local_table));
if (is_undefined(subtable)) {
return undefined;
} else {
const record = assoc(key_2, tail(subtable));
return is_undefined(record)
? undefined
: tail(record);
}
}
function insert(key_1, key_2, value) {
const subtable = assoc(key_1, tail(local_table));
if (is_undefined(subtable)) {
set_tail(local_table,
pair(list(key_1, pair(key_2, value)),
tail(local_table)));
} else {
const record = assoc(key_2, tail(subtable));
if (is_undefined(record)) {
set_tail(subtable,
pair(pair(key_2, value), tail(subtable)));
} else {
set_tail(record, value);
}
}
}
function dispatch(m) {
return m === "lookup"
? lookup
: m === "insert"
? insert
: error(m, "unknown operation -- table");
}
return dispatch;
}
Using
make-table,make_table,
we could
implement the get and
put operations used in
section 2.4.3 for data-directed
programming, as follows:
Original
JavaScript
(define operation-table (make-table))
(define get (operation-table 'lookup-proc))
(define put (operation-table 'insert-proc!))
const operation_table = make_table();
const get = operation_table("lookup");
const put = operation_table("insert");
GetThe function get
takes as arguments two keys, and put takes
as arguments two keys and a value. Both operations access the same
local table, which is encapsulated within the object created by the
call to
make-table.make_table.
Exercise 3.24
In the table implementations above, the keys are
tested for equality using
equal?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-tablemake_table
that takes as an argument a
same-key?same_keyprocedurefunction
that will be used to test equality of keys.
Make-tableThe function make_table
should return a dispatchprocedurefunction
that can be used to access appropriate
lookup and
insert!insertproceduresfunctions
for a local table.
// Solution by GitHub user clean99
function make_table(same_key) {
const local_table = list("*table*");
function assoc(key, records) {
return is_null(records)
? undefined
: same_key(key, head(head(records)))
? head(records)
: assoc(key, tail(records));
}
function lookup(key) {
const record = assoc(key, tail(local_table));
return is_undefined(record)
? undefined
: tail(record);
}
function insert(key, value) {
const record = assoc(key, tail(local_table));
if (is_undefined(record)) {
set_tail(local_table,
pair(pair(key, value), tail(local_table)));
} else {
set_tail(record, value);
}
return "ok";
}
function dispatch(m) {
return m === "lookup"
? lookup
: m === "insert"
? insert
: error(m, "unknow operation -- table");
}
return dispatch;
}
const operation_table = make_table((a, b) => a === b);
const get = operation_table("lookup");
const put = operation_table("insert");
Exercise 3.25
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!insertproceduresfunctions
should take as input a list of keys used to access the table.
// contributed by GitHub user tttinkl
function assoc(key, records, same_key) {
return is_null(records)
? undefined
: same_key(key, head(head(records)))
? head(records)
: assoc(key, tail(records), same_key);
}
function make_table(same_key) {
const local_table = list("*table");
const get_value = tail;
function is_table(t) {
return is_pair(t) && head(t) === "*table";
}
function lookup(keys) {
function lookup_generic(keys, table) {
if (is_null(keys)) {
return table;
}
const key_1 = head(keys);
const key_rest = tail(keys);
const record = assoc(key_1, tail(table), same_key);
if (is_undefined(record)) {
return undefined;
}
if (is_null(key_rest)) {
return get_value(record);
} else if (is_table(get_value(record))) {
return lookup_generic(key_rest, get_value(record));
} else {
error('invalid key');
}
}
return lookup_generic(keys, local_table);
}
function insert(keys, value) {
function insert_generic(keys, value, table) {
const key_1 = head(keys);
const key_rest = tail(keys);
const record = assoc(key_1, tail(table), same_key);
if (is_undefined(record)) {
if (is_null(key_rest)) {
set_tail(
table,
pair(pair(key_1, value), tail(table)));
} else {
const new_subtable = list("*table");
set_tail(
table,
pair(pair(key_1, new_subtable), tail(table))
);
insert_generic(key_rest, value, new_subtable);
}
} else {
if (is_null(key_rest)) {
set_tail(record, value);
} else {
if (is_table(get_value(record))) {
insert_generic(key_rest, value, get_value(record));
} else {
const new_subtable = list("*table");
set_tail(record, new_subtable);
insert_generic(key_rest, value, new_subtable);
}
}
}
}
insert_generic(keys, value, local_table);
}
function dispatch(m) {
return m === "lookup"
? lookup
: m === "insert"
? insert
: m === "show"
? () => {
display(local_table);
return local_table;
}
: error(m, "unknow operation -- table");
}
return dispatch;
}
const table = make_table(equal);
const get = table('lookup');
const put = table('insert');
const show = table('show');
Exercise 3.26
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 2.3.3. 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 2.70 of chapter 2.)
// provided by GitHub user devinryu
function entry(tree) { return head(tree); }
function left_branch(tree) { return head(tail(tree)); }
function right_branch(tree) { return head(tail(tail(tree))); }
function make_tree(entry, left, right) {
return list(entry, left, right);
}
// kv is list(key, value)
function adjoin_set(kv, set) {
return is_null(set)
? make_tree(kv, null, null)
: head(kv) === head(entry(set))
? set
: head(kv) < head(entry(set))
? make_tree(entry(set),
adjoin_set(kv, left_branch(set)),
right_branch(set))
: make_tree(entry(set),
left_branch(set),
adjoin_set(kv, right_branch(set)));
}
function make_table() {
let local_table = null;
function lookup(given_key, tree_of_records) {
if (is_null(tree_of_records)) {
return null;
} else {
const this_entry = entry(tree_of_records);
const this_key = head(this_entry);
return given_key === this_key
? this_entry
: given_key < this_key
? lookup(given_key,
left_branch(tree_of_records))
: lookup(given_key,
right_branch(tree_of_records));
}
}
function insert(k, v) {
let record = lookup(k, local_table);
if(is_null(record)) {
local_table = adjoin_set(list(k, v), local_table);
} else {
// do nothing
}
}
function get(k) {
return head(tail(lookup(k, local_table)));
}
function print() {
return display(local_table);
}
function dispatch(m) {
return m === "lookup"
? get
: m === "insert"
? insert
: m === "print"
? print
: error(m, "error");
}
return dispatch;
}
Exercise 3.27 Memoization
(also called tabulation) is a technique that
enables a
procedurefunction
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
procedurefunction
maintains a table in which values of previous calls are stored
using as keys the arguments that produced the values. When the
memoized
procedurefunction
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 1.2.2 the exponential process for
computing Fibonacci numbers:
Original
JavaScript
(define (fib n)
(cond ((= n 0) 0)
((= n 1) 1)
(else (+ (fib (- n 1))
(fib (- n 2))))))
function fib(n) {
return n === 0
? 0
: n === 1
? 1
: fib(n - 1) + fib(n - 2);
}
The memoized version of the same
procedurefunction
is
Original
JavaScript
(define memo-fib
(memoize (lambda (n)
(cond ((= n 0) 0)
((= n 1) 1)
(else (+ (memo-fib (- n 1))
(memo-fib (- n 2))))))))
(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))))))
function memoize(f) {
const table = make_table();
return x => {
const previously_computed_result =
lookup(x, table);
if (is_undefined(previously_computed_result)) {
const result = f(x);
insert(x, result, table);
return result;
} else {
return previously_computed_result;
}
};
}
Draw an environment diagram to analyze the computation of
(memo-fib 3).memo_fib(3).
Explain why
memo-fibmemo_fib
computes the $n$th Fibonacci number in a number
of steps proportional to $n$. Would the scheme
still work if we had simply defined
memo-fibmemo_fib
to be
(memoize fib)?memoize(fib)?
There is currently no solution available for this exercise. This textbook adaptation is a community effort. Do consider contributing by providing a solution for this exercise, using a Pull Request in Github.
Because
assoc uses
equal?, it can recognize keys that are
symbols, numbers, or list structure.
Because assoc uses
equal, it can recognize keys that
are strings, numbers, or list structure.
[2]
Thus, the first backbone pair is the object that represents
the table itself; that is, a pointer to the table is a
pointer to this pair. This same backbone pair always starts the table.
If we did not arrange things in this way,
insert!insert
would have to return a new value for the start of the table
when it added a new record.
