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)))))))