Memoization during delayed evaluation

Question

The book Structure and Interpretation of Computer Programs introduces a memoizing procedure 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))))

while suggesting the definition of delayed execution, (delay <exp>) be (memo-proc (lambda () <exp>)). A delayed object can be forced using the following procedure:

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

In the chapter which gives these definitions, computations are done using streams. Each stream is a pair with a head, and a delayed tail.

However, I don't see how memoization is achieved without using a lookup table, or some other kind of data structure which accumulates the previous calls.

The chapter which includes these definitions are here.

A lookup table would be useful when we are memoizing a single procedure with various arguments. Then, we would put arguments as keys and the result of the procedure as values. In this case, we have nullary procedures hence we don't need a lookup table. All we need would be a set of delayed objects we have created so far. However, closures are used here.

According to the definition of memo-proc above, each delayed object actually is a closure with values already-run? and result, which are both initialised to false. However, since each delayed object inside the call proc would have their own closures with their own local already-run? and result, modifying them wouldn't change the other ones in the call tree. Hence, I'm feeling like a memoized value won't ever be read by any other procedures again.

So my question is, what am I thinking wrong or what is the correct explanation of how everything works?

Handyman

Answer 1

Each delayed object stores its own value after the first time it's forced; the value is stored in the result variable. It works because memo-proc creates a closure over both proc - the promise (a no-arg procedure waiting to be evaluated) and the result variable.

After the first time the object is forced the stored result is returned, and never again is recalculated. So the promise becomes the value itself.

I don't see how memoization is achieved without using a lookup table, or some other kind of data structure which accumulates the previous calls.

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

Hence, I'm feeling like a memoized value won't ever be read by any other procedures again

Yes, it'll be read each and every time that force is called on the promise object.

Brae

Thank you. I understand that the closures are created around each promise. But each time (memoize proc) is invoked, doesn't it create a new lambda from scratch, where result is nil? So, what is stopping the value of result being nil in an inner call to the same memoized procedure? – Handyman

If you call again (memo-proc proc) you're creating a new value, and obviously this won't be memoized yet. It doesn't matter if it's a value that was created previously somewhere else - this is a new value, memoization as defined in SICP works on a per-value level, it's not global - and it can't be, unless we restrict the language to a purely functional subset, otherwise mutation operations will wreak havoc on precalculated values that are reused in several parts of the program – Sidestep

So, every instance of a delayed expression is actually a call to (memo-proc proc) and a new already-run? variable is created. Where is the memoization then? – Handyman

No, every time you create a new delayed expression you call memo-proc. If you keep forcing an already created delayed expression, you'll get the memoized value. For example: if you define a stream called integers and all the rest of your program uses that stream, then after the first time a value is forced from the stream it will never be evaluated again, it just returns the memoized value. Of course, if you create a new stream called integers2 then all of its values wiill need to be calculated again and memoized again, because it's a different object that has not been memoized yet – Sidestep

If you've done any object oriented programming you might find it easier to think of (memo-proc proc) as a constructor that returns an instance of an object. Then you use this instance of the closure object as you would a normal function. – Tuff

Oh, I see now. So, we're not memoizing anything while reading from the stream ones the first time (I thought we did because the same stream contained many occurrences of the same value). However, once we access to the, say 8th element of ones, whenever we want to access the same element from elsewhere, we get the memoized value. Is this correct? – Handyman