Set! on memoize and define something to memoize, difference?

user_15970133 0
Viewed 74

I have made this memoize function bellow and I am experimenting with it.

(define (make-table)
  (list '*table*))

(define (lookup key table)
  (let ((record (assoc key (cdr table)))) 
    (and record (cdr record))))

(define (insert! key value table)
  (let ((record (assoc key (cdr table))))
    (if record
        (set-cdr! record value)
        (set-cdr! table
                 (cons (cons key value) (cdr table))))))

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

(define (memoize message f)

  (define (dispatch message)
    (cond 
      ((eq? message 'memoize) memo)
      ((eq? message 'unmemoize) fibe)))

  (define memo 
    (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)
               )))))

  (dispatch message) )

You can ignore the 'unmemoize) fibee part.

What I have a hard time understanding is why these two lines of codes bellow don't act in the same way.

(set! fib(memoize 'memoize  fib))

and

(define mm (memoize 'memoize fib))

fib here is this function:

(define (fib n)
(cond ((= n 0) 0)
      ((= n 1) 1)
      (else (+ (fib (- n 1))
               (fib (- n 2))))))

Calling these functions bellow gives me different results and I don't understand why

(fib 3)
(fib 3)
(mm 3)
(mm 3)

Result:

calling (fib 3) twice: enter image description here

calling (mm 3 ) twice and (mm 2) once enter image description here

As you can see (mm 3) and (fib 3) act differently, and when I run (mm 2) I don't see why we don't just get the number 1 as return but new computation

r5rs racket scheme
1 Answers

The problem is that when you do (define mm (memoize 'memoize fib)), mm calls a memoized version of fib, but fib itself is defined to recursively call itself, and fib is not memoized. That is, when mm is called, only the initial call to fib is subject to memoization.

This can be seen by using a trace functionality. It appears that the posted code is not Racket, but instead #lang r5rs, which allows access to Racket's trace procedure with (#%require racket/trace). We can use this to see the calls to fib as they unfold. Note that I commented out the display calls in OP definition of fib to remove some noise in the output:

bad-memo.rkt> (#%require racket/trace)
bad-memo.rkt> (trace fib)
bad-memo.rkt> (fib 5)
>(fib 5)
> (fib 4)
> >(fib 3)
> > (fib 2)
> > >(fib 1)
< < <1
> > >(fib 0)
< < <0
< < 1
> > (fib 1)
< < 1
< <2
> >(fib 2)
> > (fib 1)
< < 1
> > (fib 0)
< < 0
< <1
< 3
> (fib 3)
> >(fib 2)
> > (fib 1)
< < 1
> > (fib 0)
< < 0
< <1
> >(fib 1)
< <1
< 2
<5
5

This produces exactly the same trace, which I will omit here to save space:

bad-memo.rkt> (define mm (memoize 'memoize fib))
bad-memo.rkt> (mm 5)
;; --> same output as `(fib 5)` above

When mm is called the memoized version of fib is called once, and then the unmemoized fib is called many times.

With (set! fib (memoize 'memoize fib)) things are different. This time memoize returns a memoized version of fib, and the symbol fib is mutated so that it refers to this memoized version! Now whenever fib is called, it is the memoized version that is called, and this includes recursive calls:

bad-memo.rkt> (set! fib (memoize 'memoize fib))
bad-memo.rkt> (fib 5)
>(fib 5)
> (fib 4)
> >(fib 3)
> > (fib 2)
> > >(fib 1)
< < <1
> > >(fib 0)
< < <0
< < 1
< <2
< 3
<5
5

Here you can see the difference by comparing the trace for fib before and after setting it to the memoized version.

For some further reading, here is a related answer that I wrote some time ago.

user_68798260
Related