Memorization during deferred evaluation

Question

In the book Structure and interpretation of computer programs, the memoizing procedure is introduced as follows:

(define (memo-proc proc) (let ((already-run? false) (result false)) (lambda () (if (not already-run?) (begin (set! result (proc)) (set! already-run? true) result) result)))) 

offering a definition of deferred execution, (delay <exp>) be (memo-proc (lambda () <exp>)) . You can force a delayed object using the following procedure:

 (define (force delayed-object) (delayed-object)) 

In the chapter that gives these definitions, calculations are performed using threads. Each thread is a pair with a head and tail delay.

However, I do not see how memoization is achieved without using a lookup table or some other data structure that accumulates previous calls.

The chapter that includes these definitions is here .

A lookup table will be useful when we remember one procedure with different arguments. Then we put the arguments as keys and the result of the procedure as values. In this case, we have zero procedures, so we do not need a lookup table. All we need is a set of pending objects that we have created so far. However, closures are used here.

According to the definition of memo-proc above, each delayed object is actually a closure with already-run? values already-run? and result , which are both initialized to false . However, since each delayed object inside the proc call will have its own closures with its own local already-run? and result , changing them will not change others in the call tree. Therefore, I feel that remembering the meaning will never again be read by any other procedures.

So my question is: what am I thinking wrong or how to correctly explain how everything works?

Answer 1

Each delayed object retains its own value after the first forced one; the value is stored in the result variable. It works because memo-proc creates a closure on proc — a promise (a procedure with no argument, waiting to be evaluated) and a result variable.

After the first launch of the object, the object is saved result and is never recalculated. Thus, the promise becomes value itself.

I do not see how memorization is performed without using a lookup table or any other data structure that accumulates previous calls.

The data structure is a closure created around each promise, it accumulates the value of the first call in the result variable, returning it for all subsequent calls.

Therefore, I feel that the memoized value will never be read by any other procedures again

Yes, it will be read every time force is called on the promise object.