sicp-ex-3.27

meteorgan



   The (memo-fib) never computes the same result twice. the call tree is a linear list. 
   If define memo-fib to be (memorize fib), the procedure won't work. because fib calls itself to compute (fib n) before applies memorize.

sam

 (define memo-fib (memoize fib))

willl not work because when evaluating code for (memoize fib); (fib x) will be evaluated whose enclosing envrionment is the global environment and thus memoization is lost.

Manu Halvagal

 (define memo-fib (memoize fib))

will actually work but not very well. For example, the call (memo-fib 3) would memoize fib(3), but not fib(1) or fib(2) because these are recursive calls to the unmemoized version of the function. The proper implementation memoizes even the recursive calls.

John-Gaines

Instead of recoding fib into memo-fib as shown in SICP (which seems like a very error-prone way of adding memoize to an existing function). The following works in DrRacket using #lang racket

 (set! fib (memoize fib))

It sets fib in the global environment to (memoize fib) which also causes the recursive calls within fib to call the redefined version.

sam

This will not work under the environment model for evaluation as described in the book. This is because f in memoize will be bound to procedure object that was created via lambda expression for fib; and this procedure object still has global envrionment as the enclosing environment. (note, all procedures can be created only via lambda expressions).

ericwen229

This WILL work as the fib in global environment HAS CHANGED. When f in memoize gets invoked and searches for fib it will find the redefined version of fib (in global environment as its enclosing environment), which is decorated by memoize.