1 (define (lookup key table)
2   (let ((record (assoc key (cdr table))))
3     (if record
4         (cdr record)
5         false)))
6 (define (assoc key records)
7   (cond ((null? records) false)
8         ((equal? key (caar records)) (car records))
9         (else (assoc key (cdr records)))))
10 (define (insert! key value table)
11   (let ((record (assoc key (cdr table))))
12     (if record
13         (set-cdr! record value)
14         (set-cdr! table
15                   (cons (cons key value) (cdr table)))))
16   'ok)
17 (define (make-table)
18   (list '*table*))
19 
20 (define (fib n)
21   (cond ((= n 0) 0)
22 	((= n 1) 1)
23 	(else (+ (fib (- n 1))
24 		 (fib (- n 2))))))
25 
26 (define (memoize f)
27   (let ((local-table (make-table)))
28     (lambda (x)
29       (or (lookup x local-table)
30 	  (let ((result (f x)))
31 	    (insert! x result local-table)
32 	    result)))))
33 
34 (define memo-fib
35   (memoize
36    (lambda (n)
37      (cond ((= n 0) 0)
38 	   ((= n 1) 1)
39 	   (else (+ (memo-fib (- n 1))
40 		    (memo-fib (- n 2))))))))
41 
42 (memo-fib 5000)
43 ;;(fib 100)
44   
45 ;; Draw an environment diagram to analyze the computation of (memo-fib 3). Explain why memo-fib computes the nth Fibonacci number in a number of steps proportional to n. Would the scheme still work if we had simply defined memo-fib to be (memoize fib)? 
46 
47 ;; each fibonacci number is only calculated once because the argument and resulting value is stored in the table and looked up whenever possible
48 ;; No, the scheme would not work if we had defined memo-fib to be (memoize fib). This is because, while (memo-fib 3) looks up values in the table and attempts to record its calculations in the table, when it is discovered that the 3rd fibonacci number is not in the table, (fib 2) and (fib 1) are calculated. fib has, as its enclosing environment, the global environment. So, it cannot look up nor add entries to the table (the procedure for fib also never uses the table).