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.45
Figure 3.46
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
falseNone
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,None,
and returns the value (the
cdr)tail)
of the record.
def lookup(key, table):
record = assoc(key, tail(table))
return (None
if is_none(record)
else tail(record))
def assoc(key, records):
return (None
if is_none(records)
else head(records)
if key == head(head(records))
else assoc(key, tail(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
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
Python
(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)
def insert(key, value, table):
record = assoc(key, tail(table))
if is_none(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
Python
(define (make-table)
(list '*table*))
def make_table():
return llist('*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.47
Figure 3.48
shows the box-and-pointer diagram for the table
def lookup(key_1, key_2, table):
subtable = assoc(key_1, tail(table))
if is_none(subtable):
return None
else:
record = assoc(key_2, tail(subtable))
return (None
if is_none(record)
else tail(record))
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:
def make_table():
local_table = llist('*table*')
def lookup(key_1, key_2):
subtable = assoc(key_1, tail(local_table))
if is_none(subtable):
return None
else:
record = assoc(key_2, tail(subtable))
return (None
if is_none(record)
else tail(record))
def insert(key_1, key_2, value):
subtable = assoc(key_1, tail(local_table))
if is_none(subtable):
set_tail(local_table,
pair(llist(key_1, pair(key_2, value)),
tail(local_table)))
else:
record = assoc(key_2, tail(subtable))
if is_none(record):
set_tail(subtable,
pair(pair(key_2, value), tail(subtable)))
else:
set_tail(record, value)
def dispatch(m):
return (lookup if m == 'lookup'
else insert if m == 'insert'
else error('unknown operation -- table', m))
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
Python
(define operation-table (make-table))
(define get (operation-table 'lookup-proc))
(define put (operation-table 'insert-proc!))
operation_table = make_table()
get = operation_table('lookup')
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?==
(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
def make_table(same_key):
local_table = llist('*table*')
def assoc(key, records):
return (None if is_none(records)
else head(records) if same_key(key, head(head(records)))
else assoc(key, tail(records)))
def lookup(key):
record = assoc(key, tail(local_table))
return (None if is_none(record)
else tail(record))
def insert(key, value):
record = assoc(key, tail(local_table))
if is_none(record):
set_tail(local_table,
pair(pair(key, value), tail(local_table)))
else:
set_tail(record, value)
return 'ok'
def dispatch(m):
return (lookup if m == 'lookup'
else insert if m == 'insert'
else error('unknown operation -- table', m))
return dispatch
operation_table = make_table(lambda a, b: a == b)
get = operation_table('lookup')
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
def assoc(key, records, same_key):
return (None if is_none(records)
else head(records) if same_key(key, head(head(records)))
else assoc(key, tail(records), same_key))
def make_table(same_key):
local_table = llist('*table')
get_value = tail
def is_table(t):
return is_pair(t) and head(t) == '*table'
def lookup(keys):
def lookup_generic(keys, table):
if is_none(keys):
return table
key_1 = head(keys)
key_rest = tail(keys)
record = assoc(key_1, tail(table), same_key)
if is_none(record):
return None
if is_none(key_rest):
return get_value(record)
elif is_table(get_value(record)):
return lookup_generic(key_rest, get_value(record))
else:
error('invalid key')
return lookup_generic(keys, local_table)
def insert(keys, value):
def insert_generic(keys, value, table):
key_1 = head(keys)
key_rest = tail(keys)
record = assoc(key_1, tail(table), same_key)
if is_none(record):
if is_none(key_rest):
set_tail(
table,
pair(pair(key_1, value), tail(table)))
else:
new_subtable = llist('*table')
set_tail(
table,
pair(pair(key_1, new_subtable), tail(table))
)
insert_generic(key_rest, value, new_subtable)
else:
if is_none(key_rest):
set_tail(record, value)
else:
if is_table(get_value(record)):
insert_generic(key_rest, value, get_value(record))
else:
new_subtable = llist('*table')
set_tail(record, new_subtable)
insert_generic(key_rest, value, new_subtable)
insert_generic(keys, value, local_table)
def dispatch(m):
return (lookup if m == 'lookup'
else insert if m == 'insert'
else (lambda: print(local_table)) if m == 'show'
else error('unknown operation -- table', m))
return dispatch
table = make_table(lambda a, b: a == b)
get = table('lookup')
put = table('insert')
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.66 of chapter 2.)
# provided by GitHub user devinryu
def entry(tree):
return head(tree)
def left_branch(tree):
return head(tail(tree))
def right_branch(tree):
return head(tail(tail(tree)))
def make_tree(entry, left, right):
return llist(entry, left, right)
# kv is llist(key, value)
def adjoin_set(kv, set):
return (make_tree(kv, None, None) if is_none(set)
else set if head(kv) == head(entry(set))
else make_tree(entry(set),
adjoin_set(kv, left_branch(set)),
right_branch(set))
if head(kv) < head(entry(set))
else make_tree(entry(set),
left_branch(set),
adjoin_set(kv, right_branch(set))))
def make_table():
local_table = None
def lookup(given_key, tree_of_records):
if is_none(tree_of_records):
return None
else:
this_entry = entry(tree_of_records)
this_key = head(this_entry)
return (this_entry if given_key == this_key
else lookup(given_key,
left_branch(tree_of_records))
if given_key < this_key
else lookup(given_key,
right_branch(tree_of_records)))
def insert(k, v):
nonlocal local_table
record = lookup(k, local_table)
if is_none(record):
local_table = adjoin_set(llist(k, v), local_table)
else:
set_tail(record, llist(v))
def get(k):
return head(tail(lookup(k, local_table)))
def show_table():
return print(local_table)
def dispatch(m):
return (get if m == 'lookup'
else insert if m == 'insert'
else show_table if m == 'print'
else error('unknown operation -- table', m))
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
Python
(define (fib n)
(cond ((= n 0) 0)
((= n 1) 1)
(else (+ (fib (- n 1))
(fib (- n 2))))))
def fib(n):
return (0 if n == 0
else 1 if n == 1
else fib(n - 1) + fib(n - 2))
The memoized version of the same
procedurefunction
is
Original
Python
(define memo-fib
(memoize (lambda (n)
(cond ((= n 0) 0)
((= n 1) 1)
(else (+ (memo-fib (- n 1))
(memo-fib (- n 2))))))))
memo_fib = memoize(lambda n: (0
if n == 0
else 1
if n == 1
else memo_fib(n - 1) +
memo_fib(n - 2)))
where the memoizer is defined as
Original
Python
(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))))))
def memoize(f):
table = make_table()
def memoized(x):
previously_computed_result = lookup(x, table)
if is_none(previously_computed_result):
result = f(x)
insert(x, result, table)
return result
else:
return previously_computed_result
return memoized
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
==, 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.
