Using a defined procedure as argument yields different result than using a lambda-expression as argument

Question

I'm trying to memoize a procedure in scheme. The code is from SICP

I have my procedure fib defined as

(define (fib n)
    (display "computing fib of ")
    (display n) (newline)
    (cond ((= n 0) 0)
        ((= n 1) 1)
        (else (+ (fib (- n 1))
                (fib (- n 2))))))

My memoization procedure is as following

(define (memoize f)
    (let ((table (make-table)))
        (lambda (x)
            (let ((previously-computed-result (lookup x table)))
                (or previously-computed-result
                    (let ((result (f x)))
                       (insert! x result table)
                       result))))))

Let's define two procedures

(define mem-fib (memoize fib))
(define mem-fib-lambda (memoize (lambda (n)
             (display "computing fib of ")
             (display n)
             (newline)
             (cond ((= n 0) 0)
               ((= n 1) 1)
                   (else (+ (memo-fib (- n 1))
                            (memo-fib (- n 2))))))))

As you see, in mem-fib, I use fib as argument, but in mem-fib-lambda, I use the lambda expression as argument, which is nearly identical.

Calling this procedures with 5 as argument yields different results where the first, mem-fib stores the last result in its table, whereas mem-fib-lambda stores every recursive calculation along the way.

(mem-fib 5)
->computing fib of 5
->computing fib of 4
->computing fib of 3
->computing fib of 2
->computing fib of 1
->computing fib of 0
->computing fib of 1
->computing fib of 2
->computing fib of 1
->computing fib of 0
->computing fib of 3
->computing fib of 2
->computing fib of 1
->computing fib of 0
->computing fib of 1
->5
(mem-fib 5)
->5

and

(mem-fib-lambda 5)
->computing fib of 5
->computing fib of 4
->computing fib of 3
->computing fib of 2
->computing fib of 1
->computing fib of 0
->5
(mem-fib-lambda 5)
->5 

My theory is that when I am calling mem-fib fib is being calculated in another environment, whereas mem-fib-lambda is calculating it in the enviroment it was called.

As a attempt to fix this, I tried to make a copy in the memoization procedure

(define (memoize proc)
  (define f proc) ;; Here
    (let ((table (make-table)))
        (lambda (x)
            (let ((previously-computed-result (lookup x table)))
                (or previously-computed-result
                    (let ((result (f x)))
                       (insert! x result table)
                       result))))))

That didn't work so I tried putting it in the let expression. To my knowledge, fib should be a part of the same frame as table

(define (memoize proc)
    (let ((table (make-table))
         (f proc)) ;; Here
        (lambda (x)
            (let ((previously-computed-result (lookup x table)))
                (or previously-computed-result
                    (let ((result (f x)))
                       (insert! x result table)
                       result))))))

That didn't do anything either.

What am I missing? Why is there a difference in behaviour? How can I get the result I am looking for?

Thank you

Answer 1

The problem is that, in your first function, you are calling the non-memoized version of fibonacci recursively, not the memoized version of fib. A way around this would be to define fib like this:

(define (fib n)
    (display "computing fib of ")
    (display n) (newline)
    (cond ((= n 0) 0)
        ((= n 1) 1)
        (else (+ (mem-fib (- n 1)) ;; Notice we're calling the memoized version here
                (mem-fib (- n 2))))))
(define mem-fib (memoize fib))

An arguably better way would be to do the following:

(define (fib n)
    (display "computing fib of ")
    (display n) (newline)
    (cond ((= n 0) 0)
        ((= n 1) 1)
        (else (+ (fib (- n 1)) ;; Notice we're calling the NON-memoized version here
                (fib (- n 2))))))
(set! fib (memoize fib)) ;; but we redefine fib to be memoized

This means we're only using one name and it's memoized. There is no good way to have both versions laying around, but if you want to, here is one way you would do it (if you want to compare performance or something):

(define (fib n)
    (display "computing fib of ")
    (display n) (newline)
    (cond ((= n 0) 0)
        ((= n 1) 1)
        (else (+ (mem-fib (- n 1)) ;; Notice we're calling the memoized version here
                (mem-fib (- n 2))))))
(define mem-fib (memoize fib))
(set! fib (lambda (n)
    (display "computing fib of ")
    (display n) (newline)
    (cond ((= n 0) 0)
        ((= n 1) 1)
        (else (+ (fib (- n 1)) ;; Notice we're calling the NON-memoized version here
                (fib (- n 2)))))))

Answer 2

Here is an alternative approach to this problem. This is in Racket, not Scheme, for which I apologise (it could be Scheme except I don't know how hashtables work in Scheme).

First of all, here is a Racket function to memoize a function of an arbitrary number of arguments on its first argument. It will be apparent why we need to allow extra arguments in a moment.

(define (memoize f (table (make-hasheqv)))
  ;; Memoize a function on its first argument.
  ;; table, if given, should be a mutable hashtable
  (λ (k . more)
    ;; hash-ref! looks up k in table, and if it is not there
    ;; sets it to be the result of calling the third argument (or
    ;; to the third argument if it's not callable).  thunk just makes
    ;; a function of no arguments.
    (hash-ref! table k
               (thunk (apply f k more)))))

Now here's the trick: rather than defining fib as a recursive function we define fib/c as a non-recursive function which knows how to do one-step of the Fibonacci series calculation and punts to another function to do the rest. It also tells you what it's doing as your function did.

(define (fib/c n c)
  ;; fib/c does one step of the fibonacci calculation,
  ;; calling c to do the remaining steps.
  (printf "fib of ~A~%" n)
  (if (<= n 2)
      1
      (+ (c (- n 1) c)
         (c (- n 2) c))))

Based on this we can very easily define fib/u, an unmemoized Fibonacci function which has the terrible performance you would expect, by just passing fib/c itself as its second argument:

(define (fib/u n)
  ;; unmemoized fib
  (fib/c n fib/c))

But now we can memoize it, and define a memoized version, fib/m (here's where you see why I needed memoize to allow more than one argument: we need to keep passing the memoized function down:

(define (fib/m n)
  ;; and here's a memoized fib
  (let ((fib/m (memoize fib/c)))
    (fib/m n fib/m)))

And now (4 is the first case where they differ):

> (fib/u 4)
fib of 4
fib of 3
fib of 2
fib of 1
fib of 2
3
> (fib/m 4)
fib of 4
fib of 3
fib of 2
fib of 1
3

And with the printing removed:

> (time (fib/u 40))
cpu time: 8025 real time: 7962 gc time: 26
102334155
> (time (fib/m 40))
cpu time: 1 real time: 1 gc time: 0
102334155

---

Note that this sort of approach, where you write a nonrecursive function & turn it into a recursive one, is closely-related to how the derivation of Y gets done (although these are normally very purist and insist on functions with only a single argument, so you end up with (λ (f) (λ (n) ... (f ...) ...)) rather than (λ (n c) ... (c ...) ...). It turns out that this is quite a useful trick.