Chapter 3

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.

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 \(1.2 .2\) the exponential process for computing Fibonacci numbers: \(\begin{aligned}(\text { define }(f i b ~ n)& \\\\(\text { cond }((=\mathrm{n})&0) \\ &((=\mathrm{n} 1)&1) \\ &(e l s e(+(f i b(-\mathrm{n} 1))\\\ & &(f i b(-\mathrm{n}&2))))) \end{aligned}\) The memoized version of the same procedure is \(\begin{aligned}&\text { (define memo-fib } \\\&\text { (memoize (lambda ( } \mathrm{n} \text { ) } \\\&\begin{array}{rll}\text { (cond } & ((=\mathrm{n} & 0) & 0) \\ & ((=\mathrm{n} & 1) & 1)\end{array} \\\& & (\text { else (+ (memo-fib (-n 1)) } \\\& & \end{aligned}\) 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 (memo-fib 3 ). Explain why 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 to be (memoize fib)?

Another way to construct an or-gate is as a compound digital logic device, built from and-gates and inverters. Define a procedure or-gate that accomplishes this. What is the delay time of the or-gate in terms of and-gate- delay and inverter-delay?

Using primitive multiplier, adder, and constant constraints, define a procedure averager that takes three connectors \(\mathrm{a}, \mathrm{b}\), and \(\mathrm{c}\) as inputs and establishes the constraint that the value of \(c\) is the average of the values of a and \(b\).

The procedures to be run during each time segment of the agenda are kept in a queue. Thus, the procedures for each segment are called in the order in which they were added to the agenda (first in, first out). Explain why this order must be used. In particular, trace the behavior of an and-gate whose inputs change from 0,1 to 1,0 in the same segment and say how the behavior would differ if we stored a segment's procedures in an ordinary list, adding and removing procedures only at the front (last in, first out).

Write a procedure triples that takes three infinite streams, \(S, T\), and \(U\), and produces the stream of triples \(\left(S_{i}, T_{j}, U_{k}\right)\) such that \(i \leq j \leq k\). Use triples to generate the stream of all Pythagorean triples of positive integers, i.e., the triples \((i, j, k)\) such that \(i \leq j\) and \(i^{2}+j^{2}=k^{2}\).

Louis Reasoner wants to build a squarer, a constraint device with two terminals such that the value of connector b on the second terminal will always be the square of the value a on the first terminal. He proposes the following simple device made from a multiplier: (define (squarer a b) (multiplier a a b)) There is a serious flaw in this idea. Explain.

Alyssa P. Hacker is designing a system to process signals coming from physical sensors. One important feature she wishes to produce is a signal that describes the zero crossings of the input signal. That is, the resulting signal should be \(+1\) whenever the input signal changes from negative to positive, \(-1\) whenever the input signal changes from positive to negative, and 0 otherwise. (Assume that the sign of a 0 input is positive.) For example, a typical input signal with its associated zero-crossing signal would be $$ \begin{array}{lllllllllllllll} \ldots & 1 & 2 & 1.5 & 1 & 0.5 & -0.1 & -2 & -3 & -2 & -0.5 & 0.2 & 3 & 4 & \ldots \\ \ldots & 0 & 0 & 0 & 0 & 0 & -1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & \ldots \end{array} $$ In Alyssa's system, the signal from the sensor is represented as a stream sensedata and the stream zero-crossings is the corresponding stream of zero crossings. Alyssa first writes a procedure sign-change-detector that takes two values as arguments and compares the signs of the values to produce an appropriate 0,1 , or \(-1\). She then constructs her zero-crossing stream as follows: (define (make-zero-crossings input-stream last-value) (cons-stream (sign-change-detector (stream-car input-stream) last-value) (make-zero-crossings (stream-cdr input-stream) (stream-car input-stream)))) (define zero-crossings (make-zero-crossings sense-data 0 )) Alyssa's boss, Eva Lu Ator, walks by and suggests that this program is approximately equivalent to the following one, which uses the generalized version of stream-map from exercise 3.50: (define zero-crossings (stream-map sign-change-detector sense-data (expression))) Complete the program by supplying the indicated \langleexpression \(\rangle .\)