caching previous return values of procedures in scheme

Question

In Chapter 16 of "The Seasoned Schemer", the authors define a recursive procedure "depth", which returns 'pizza nested in n lists, e.g (depth 3) is (((pizza))). They then improve it as "depthM", which caches its return values using set! in the lists Ns and Rs, which together form a lookup-table, so you don't have to recurse all the way down if you reach a return value you've seen before. E.g. If I've already computed (depthM 8), when I later compute (depthM 9), I just lookup the return value of (depthM 8) and cons it onto null, instead of recursing all the way down to (depthM 0).

But then they move the Ns and Rs inside the procedure, and initialize them to null with "let". Why doesn't this completely defeat the point of caching the return values? From a bit of experimentation, it appears that the Ns and Rs are being reinitialized on every call to "depthM".

Am I misunderstanding their point?

I guess my question is really this: Is there a way in Scheme to have lexically-scoped variables preserve their values in between calls to a procedure, like you can do in Perl 5.10 with "state" variables?

Answer 1

Duh. Not having read the Seasoned Schemer, I cannot comment on the memoization issue, unless you give some source code here. However, regarding the question of whether there is a way to have lexically scoped variables keep their state between function calls... This is a feature of the Scheme language called "closures". Consider the following example:

(define counter 
  (let ((number 0))
    (lambda () 
      (let ((result number))
        (set! number (+ number 1))
        result)))

This piece of code defines a function called counter, which uses a lexical variable (number) to keep track of its state. Each time you call the function, you will get a different number in return:

> (counter)
0
> (counter)
1

and so on. The important point here is, that the function generated by the execution of the lambda expression "closes over" all lexically visible variables from enclosing scopes (in this case only number.) This means, that those variables remain valid places to read values from or write new values to.