Source code for Exercise 4.29.
We know that recursive procedures benefit greatly from memoisation and so our old friend
fib would be a good candidate to show the benefits of a memoised
(display-line "Defining the fib procedure") (collect-garbage) (time (run-interpreter '(define (fib n) (cond ((= n 0) 0) ((= n 1) 1) (else (+ (fib (- n 1)) (fib (- n 2)))))))) (display-line "Calling fib 3 times") (let loop ((i 3)) (cond ((zero? i) 'done) (else (collect-garbage) (time (run-interpreter '(fib 17))) (loop (- i 1)))))
The non-memoised results.
Defining the fib procedure cpu time: 3 real time: 1 gc time: 0 'ok Calling fib 3 times cpu time: 1463 real time: 1464 gc time: 0 cpu time: 1473 real time: 1473 gc time: 0 cpu time: 1456 real time: 1457 gc time: 0
The memoised results.
Defining the fib procedure cpu time: 0 real time: 2 gc time: 0 'ok Calling fib 3 times cpu time: 364 real time: 363 gc time: 0 cpu time: 380 real time: 384 gc time: 0 cpu time: 380 real time: 380 gc time: 0
Note that there is no garbage collection taking place in the timings and so this is a fairly good indication of the difference memoisation makes. But in a real world program, memoisation would cause the creation of far more data, causing more space to be used. It’s very likely that this would cause a lot more garbage collection to take place as space is more limited for storing data.
For the non-memoised version of
square the value of
count is 2, but for the memoised version the value of
count is 1.
The reason is that within
square, the argument
(id 10) is bound to x as a thunk and when evaluating
(* x x), the thunk is evaluated twice, once for each reference to x. In the memoising evaluator
(id 10) is also bound to x as a thunk, but the first time it is referenced in the expression
(* x x) it’s value is calculated and memoised. The second reference simply returns it’s value and so doesn’t evaluate the body of
(id 10) a second time.