1 (define
false #f)
2 (define
true #t)
3
4 (define (make-
table)
5 (let ((local-table (list
'*table*)))
6
7 (define (assoc key records)
8 (cond ((
null? records)
false)
9 ((equal?
(caar records) key) (car records))
10 (
else (assoc key (cdr records)))))
11
12 (define (lookup keys)
13 (define (lookup-
helper keys table)
14 (let ((subtable (assoc (car keys) (cdr table))))
15 (
if subtable
16 (
if (
null?
(cdr keys))
17 (cdr subtable)
18 (lookup-
helper (cdr keys) subtable))
19 false)))
20 (lookup-helper keys local-
table))
21
22 (define (insert!
keys value)
23 (define (insert-helper!
keys table)
24 (
if (
null?
table)
25 (
if (
null?
(cdr keys))
26 (cons (car keys) value)
27 (list (car keys) (insert-helper! (cdr keys)
'())))
28 (let ((sub (assoc (car keys) (cdr table))))
29 (
if sub
30 (
if (
null?
(cdr keys))
31 (
set-cdr!
sub value)
32 (insert-helper!
(cdr keys) sub))
33 (
if (
null?
(cdr keys))
34 (
set-cdr!
table (cons (cons (car keys) value) (cdr table)))
35 (
set-cdr!
table (cons
36 (list (car keys)(insert-helper! (cdr keys)
'()))
37 ;;可以直接用（insert-helper! keys
'()）
38 (cdr table))))))))
39 (insert-helper! keys local-
table)
40 'ok)
41
42 (define (dispatch m)
43 (cond ((eq? m
'lookup-proc) lookup)
44 ((eq? m
'insert-proc) insert!)
45 (
else (error
"Unknow operation --TABLE" m))))
46
47 dispatch))
48
49 (define (lookup x table)
50 (let ((keys (list x)))
51 ((table
'lookup-proc) keys)))
52
53 (define (insert!
x result table)
54 (let ((keys (list x)))
55 ((table
'insert-proc) keys result)))
56
57 ;;;;;;;;;;;;;;;;;;;;;;;;;;;;
58
59 (define (memoize f)
60 (let ((table (make-
table)))
61 (lambda (x)
62 (let ((previously-computed-
result (lookup x table)))
63 (or previously-computed-
result
64 (let ((result (f x)))
65 (insert!
x result table)
66 result))))))
67
68
69 (define memo-
fib
70 (memoize (lambda (n)
71 (cond ((= n
0)
0)
72 ((= n
1)
1)
73 (
else (+ (memo-fib (- n
1))
74 (memo-fib (- n
2))))))))
75
76
77 (memo-fib
0)
简单的定义为
（memoize fib）
能工作，但这样并没有意义，因为这样定义在处理 fib（n-2）和fib（n-1）时就是普通fib函数了
步数：
在计算fib（n）时 需要fib（n-1）和fib（n-2）而fib（n-1）的值需要fib（n-2）的值，如使用记忆法，则fib（n-2），fib（n-3）已事先存在表中。所以事先
要计算fib（n-2），一直到达n=0 和 n=1时整个表都被填满，总的来看就是求一遍fib（2）到fib（n-1）所以需要O(n)步来计算fib（n）。
转载于:https://www.cnblogs.com/tclan126/p/6833377.html
相关资源：sicp_but_clojure：Clojure中的SICP示例和练习-源码
