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.


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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s