SICP: A note about Exercise 3.27

This exercise in Section 3.3.3 demonstrates a concept called “memoization,” where values that are created during the run of a function are stored, so that when requests for certain computations repeat, the previously computed values can just be retrieved, rather than redone. It’s a caching technique.

I got really frustrated trying to do this exercise, because of the way the make-table function was portrayed. The exercise text doesn’t say anything about it. The code that was given for the exercise just uses it. In the past, exercises would use code that had already been introduced and discussed in the section/chapter. There is a set of functions that implement a single-dimension table (all that would be needed for this exercise) that is discussed earlier in the section. When I brought what I thought were the appropriate functions together, what I saw was this:

(define (make-table)
   (list '*table*))

(define memo-fib
   (memoize (lambda (n)
               (cond ((= n 0) 0)
                     ((= n 1) 1)
                     (else (+ (memo-fib (- n 1))
                              (memo-fib (- n 2))))))))

(define (memoize f)
   (let ((table (make-table)))
      (lambda (x) ...

Even the two-dimensional versions of make-table that were presented initialized their local table the same way. I’m used to paying attention to details in code, and so I tried to make sense of this. Every time memo-fib got called, the table got reinitialized, wiping out everything that had been added to it! This made no sense for this exercise, since the whole idea was to store values in the table, and then retrieve them later.

By looking at what other people had done with this exercise, I realized that I needed to use “wishful thinking,” and ignore any prior implementations of make-table. Just assume that make-table initializes its table structure on the first call, and returns a reference to its table (or a reference to a dispatch function) on subsequent calls to it. Assume that it does not reinitialize its internal structure, leaving anything that was previously added intact. Once I made these assumptions, the exercise made more sense.

What I saw other people do as well was assume that the insert! and lookup functions operated in constant time, taking them out as a factor in the number of steps. I do not know what assumptions are “supposed” to be made about the insert! and lookup functions. If you are doing this exercise for a grade, take these assumptions at your own risk. To me, it made sense, but perhaps your professor has a different idea in mind for how these functions are supposed to be considered in your analysis.

One thought on “SICP: A note about Exercise 3.27

  1. Mark, I was confused by this exercise as well, but rest assured this version of insert! is the same procedure introduced in the previous exercises in this chapter. The thing that makes this tricky is that memo-fib is NOT defined as a procedure.

    defining a procedure: (define (identifier arg1 arg2 …) …)

    defining a variable: (define identifier )

    where expression could be a primitive like ‘value or the application of a function (+ 2 3) where the value of memo-fib stays a consistent 5 and is never recalculated.

    rather a variable whose value is the result of applying memoize to the lambda expression that looks exactly like fib except the recursive steps are memo-fib and not fib.

    If we wrote this in javascript it would look like this:

    memo-fib = memoize((n) => {
    if (n = 0) return 0;
    if (n = 1) return 1;
    return memo-fib (n-1) + memo-fib (n-2);

    memo-fib = memoize((f) => {
    let table = make-table();
    x => {
    let previously-computed-result = lookup(x, table);
    if (previously-computed-result)
    return previously-computed-result;
    let result = f(x);
    insert!(x, result, table);
    return result;
    })((n) => {
    if (n = 0) return 0;
    if (n = 1) return 1;
    return memo-fib (n-1) + memo-fib (n-2);

    I think seeing this in an imperative form makes it easier to see that memo-fib becomes the procedure returned by memoize and stays that same functions for all the recursive calls that updates it’s local table and that the recursive step is calling this same memo-fib defined in the global environment.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s