GV

GeezerVison

The World Wide Web, restored to 800 pixels of glory.

Home|About|Gaming cabinet|Archives|How it works|Starter sites

On this site

No menu could be recovered. Follow the blue links in the page.

This view

  • Original page
  • New address

GeezerVison is showing sicp.sourceacademy.org — 3.3.3 Representing Tables - SICP Comparison Edition

SICP — Scheme/JS Structure and Interpretation of Computer Programs — Comparison Edition
 
Foreword
Foreword to Structure and Interpretation of Computer Programs, 1984
Preface
Prefaces to Structure and Interpretation of Computer Programs, 1996 & 1984
Acknowledgments
➤ ▼ 1 Building Abstractions with Procedures Functions
➤ ▼ 1.1 The Elements of Programming
1.1.1 Expressions
1.1.2 Naming and the Environment
1.1.3 Evaluating Combinations Operator Combinations
1.1.4 Compound Procedures Functions
1.1.5 The Substitution Model for Procedure Function Application
1.1.6 Conditional Expressions and Predicates
1.1.7 Example: Square Roots by Newton's Method
1.1.8 Procedures Functions as Black-Box Abstractions
➤ ▼ 1.2 Procedures Functions and the Processes They Generate
1.2.1 Linear Recursion and Iteration
1.2.2 Tree Recursion
1.2.3 Orders of Growth
1.2.4 Exponentiation
1.2.5 Greatest Common Divisors
1.2.6 Example: Testing for Primality
➤ ▼ 1.3 Formulating Abstractions with Higher-Order Procedures Functions
1.3.1 Procedures Functions as Arguments
1.3.2 Constructing Procedures using Lambda Constructing Functions using Lambda Expressions
1.3.3 Procedures Functions as General Methods
1.3.4 Procedures Functions as Returned Values
➤ ▼ 2 Building Abstractions with Data
➤ ▼ 2.1 Introduction to Data Abstraction
2.1.1 Example: Arithmetic Operations for Rational Numbers
2.1.2 Abstraction Barriers
2.1.3 What Is Meant by Data?
2.1.4 Extended Exercise: Interval Arithmetic
➤ ▼ 2.2 Hierarchical Data and the Closure Property
2.2.1 Representing Sequences
2.2.2 Hierarchical Structures
2.2.3 Sequences as Conventional Interfaces
2.2.4 Example: A Picture Language
➤ ▼ 2.3 Symbolic Data
2.3.1 Quotation Strings
2.3.2 Example: Symbolic Differentiation
2.3.3 Example: Representing Sets
2.3.4 Example: Huffman Encoding Trees
➤ ▼ 2.4 Multiple Representations for Abstract Data
2.4.1 Representations for Complex Numbers
2.4.2 Tagged data
2.4.3 Data-Directed Programming and Additivity
➤ ▼ 2.5 Systems with Generic Operations
2.5.1 Generic Arithmetic Operations
2.5.2 Combining Data of Different Types
2.5.3 Example: Symbolic Algebra
➤ ▼ 3 Modularity, Objects, and State
➤ ▼ 3.1 Assignment and Local State
3.1.1 Local State Variables
3.1.2 The Benefits of Introducing Assignment
3.1.3 The Costs of Introducing Assignment
➤ ▼ 3.2 The Environment Model of Evaluation
3.2.1 The Rules for Evaluation
3.2.2 Applying Simple Procedures Functions
3.2.3 Frames as the Repository of Local State
3.2.4 Internal Definitions Declarations
3.2.5 CSE Machine
➤ ▼ 3.3 Modeling with Mutable Data
3.3.1 Mutable List Structure
3.3.2 Representing Queues
3.3.3 Representing Tables
3.3.4 A Simulator for Digital Circuits
3.3.5 Propagation of Constraints
➤ ▼ 3.4 Concurrency: Time Is of the Essence
3.4.1 The Nature of Time in Concurrent Systems
3.4.2 Mechanisms for Controlling Concurrency
➤ ▼ 3.5 Streams
3.5.1 Streams Are Delayed Lists
3.5.2 Infinite Streams
3.5.3 Exploiting the Stream Paradigm
3.5.4 Streams and Delayed Evaluation
3.5.5 Modularity of Functional Programs and Modularity of Objects
➤ ▼ 4 Metalinguistic Abstraction
➤ ▼ 4.1 The Metacircular Evaluator
4.1.1 The Core of the Evaluator
4.1.2 Representing Expressions Components
4.1.3 Evaluator Data Structures
4.1.4 Running the Evaluator as a Program
4.1.5 Data as Programs
4.1.6 Internal Definitions Declarations
4.1.7 Separating Syntactic Analysis from Execution
➤ ▼ 4.2 Variations on a Scheme: Lazy Evaluation
4.2.1 Normal Order and Applicative Order
4.2.2 An Interpreter with Lazy Evaluation
4.2.3 Streams as Lazy Lists
➤ ▼ 4.3 Variations on a Scheme: Nondeterministic Computing
4.3.1 Amb and Search Search and amb
4.3.2 Examples of Nondeterministic Programs
4.3.3 Implementing the Amb amb Evaluator
➤ ▼ 4.4 Logic Programming
4.4.1 Deductive Information Retrieval
4.4.2 How the Query System Works
4.4.3 Is Logic Programming Mathematical Logic?
4.4.4 Implementing the Query System
➤ ▼ 5 Computing with Register Machines
➤ ▼ 5.1 Designing Register Machines
5.1.1 A Language for Describing Register Machines
5.1.2 Abstraction in Machine Design
5.1.3 Subroutines
5.1.4 Using a Stack to Implement Recursion
5.1.5 Instruction Summary
➤ ▼ 5.2 A Register-Machine Simulator
5.2.1 The Machine Model
5.2.2 The Assembler
5.2.3 Generating Execution Procedures for Instructions Instructions and Their Execution Functions
5.2.4 Monitoring Machine Performance
➤ ▼ 5.3 Storage Allocation and Garbage Collection
5.3.1 Memory as Vectors
5.3.2 Maintaining the Illusion of Infinite Memory
➤ ▼ 5.4 The Explicit-Control Evaluator
5.4.1 The Core of the Explicit-Control Evaluator The Dispatcher and Basic Evaluation
5.4.2 Sequence Evaluation and Tail Recursion Evaluating Function Applications
5.4.3 Conditionals, Assignments and Definitions Blocks, Assignments, and Declarations
5.4.4 Running the Evaluator
➤ ▼ 5.5 Compilation
5.5.1 Structure of the Compiler
5.5.2 Compiling Expressions Components
5.5.3 Compiling Combinations Applications and Return Statements
5.5.4 Combining Instruction Sequences
5.5.5 An Example of Compiled Code
5.5.6 Lexical Addressing
5.5.7 Interfacing Compiled Code to the Evaluator
References
About the SICP JS Project
Permalink copied!
3.3.3 Representing Tables

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 cars heads 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

Original JavaScript
a: 1 b: 2 c: 3 a: 1 b: 2 c: 3
Original JavaScript
Figure 3.43 A table represented as a headed list.
Figure 3.44 A table represented as a headed list.

To extract information from a table we use the lookup procedure, function, which takes a key as argument and returns the associated value (or false undefined if there is no value stored under that key). Lookup The 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. Assoc The function assoc returns the record that has the given key as its carhead.[1] Lookup The 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.

Original JavaScript
(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))))) function lookup(key, table) { const record = assoc(key, tail(table)); return is_undefined(record) ? undefined : tail(record); } function assoc(key, records) { return is_null(records) ? undefined : equal(key, head(head(records))) ? head(records) : 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 consing pairing 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 tail 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

Original JavaScript
math: +: 43 -: 45 *: 42 letters: a: 97 b: 98 "math": "+": 43 "-": 45 "*": 42 "letters": "a": 97 "b": 98
which has two subtables. (The subtables don't need a special header symbol, string, since the key that identifies the subtable serves this purpose.)
Original JavaScript
Figure 3.45 A two-dimensional table.
Figure 3.46 A two-dimensional table.

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.

Original JavaScript
(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))) function lookup(key_1, key_2, table) { const subtable = assoc(key_1, tail(table)); if (is_undefined(subtable)) { return undefined; } else { const record = assoc(key_2, tail(subtable)); return is_undefined(record) ? undefined : 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:

Original JavaScript
(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) function insert(key_1, key_2, value, table) { const subtable = assoc(key_1, tail(table)); if (is_undefined(subtable)) { set_tail(table, pair(list(key_1, pair(key_2, value)), tail(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); } } return "ok"; }

Creating local tables

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! insert procedures functions 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 function with which to operate on the internal table. Here is a generator for two-dimensional tables represented in this fashion:

Original JavaScript
(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)) 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");
Get The 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-table make_table that takes as an argument a same-key? same_key procedure function that will be used to test equality of keys. Make-table The function make_table should return a dispatch procedure function that can be used to access appropriate lookup and insert! insert proceduresfunctions 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, "unknown 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! insert procedures functions 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, "unknown 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.66 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 { set_tail(record, list(v)); } } 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 procedure function 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 function maintains a table in which values of previous calls are stored using as keys the arguments that produced the values. When the memoized procedure function 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 procedure function 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)))))))) const memo_fib = memoize(n => n === 0 ? 0 : n === 1 ? 1 : memo_fib(n - 1) + memo_fib(n - 2) );
where the memoizer is defined as
Original JavaScript
(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-fib memo_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-fib memo_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.

[1]
Original JavaScript
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.
< Previous
Next >
3.3.3   Representing Tables
You are visitor 01402639 — GeezerVison does not store the pages you look up.
Best viewed with Netscape Navigator 4.7 or Internet Explorer 6 at 800×600. No cookies required.