1 665c255d 2023-08-04 jrmu (define (lookup key table)
 2 665c255d 2023-08-04 jrmu   (let ((record (assoc key (cdr table))))
 3 665c255d 2023-08-04 jrmu     (if record
 4 665c255d 2023-08-04 jrmu         (cdr record)
 5 665c255d 2023-08-04 jrmu         false)))
 6 665c255d 2023-08-04 jrmu (define (assoc key records)
 7 665c255d 2023-08-04 jrmu   (cond ((null? records) false)
 8 665c255d 2023-08-04 jrmu         ((equal? key (caar records)) (car records))
 9 665c255d 2023-08-04 jrmu         (else (assoc key (cdr records)))))
10 665c255d 2023-08-04 jrmu (define (insert! key value table)
11 665c255d 2023-08-04 jrmu   (let ((record (assoc key (cdr table))))
12 665c255d 2023-08-04 jrmu     (if record
13 665c255d 2023-08-04 jrmu         (set-cdr! record value)
14 665c255d 2023-08-04 jrmu         (set-cdr! table
15 665c255d 2023-08-04 jrmu                   (cons (cons key value) (cdr table)))))
16 665c255d 2023-08-04 jrmu   'ok)
17 665c255d 2023-08-04 jrmu (define (make-table)
18 665c255d 2023-08-04 jrmu   (list '*table*))
19 665c255d 2023-08-04 jrmu 
20 665c255d 2023-08-04 jrmu (define (fib n)
21 665c255d 2023-08-04 jrmu   (cond ((= n 0) 0)
22 665c255d 2023-08-04 jrmu 	((= n 1) 1)
23 665c255d 2023-08-04 jrmu 	(else (+ (fib (- n 1))
24 665c255d 2023-08-04 jrmu 		 (fib (- n 2))))))
25 665c255d 2023-08-04 jrmu 
26 665c255d 2023-08-04 jrmu (define (memoize f)
27 665c255d 2023-08-04 jrmu   (let ((local-table (make-table)))
28 665c255d 2023-08-04 jrmu     (lambda (x)
29 665c255d 2023-08-04 jrmu       (or (lookup x local-table)
30 665c255d 2023-08-04 jrmu 	  (let ((result (f x)))
31 665c255d 2023-08-04 jrmu 	    (insert! x result local-table)
32 665c255d 2023-08-04 jrmu 	    result)))))
33 665c255d 2023-08-04 jrmu 
34 665c255d 2023-08-04 jrmu (define memo-fib
35 665c255d 2023-08-04 jrmu   (memoize
36 665c255d 2023-08-04 jrmu    (lambda (n)
37 665c255d 2023-08-04 jrmu      (cond ((= n 0) 0)
38 665c255d 2023-08-04 jrmu 	   ((= n 1) 1)
39 665c255d 2023-08-04 jrmu 	   (else (+ (memo-fib (- n 1))
40 665c255d 2023-08-04 jrmu 		    (memo-fib (- n 2))))))))
41 665c255d 2023-08-04 jrmu 
42 665c255d 2023-08-04 jrmu (memo-fib 5000)
43 665c255d 2023-08-04 jrmu ;;(fib 100)
44 665c255d 2023-08-04 jrmu   
45 665c255d 2023-08-04 jrmu ;; 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 665c255d 2023-08-04 jrmu 
47 665c255d 2023-08-04 jrmu ;; each fibonacci number is only calculated once because the argument and resulting value is stored in the table and looked up whenever possible
48 665c255d 2023-08-04 jrmu ;; 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).