SICP CONCLUSION
目录
1. 构造过程抽象
2. 构造数据抽象
3. 模块化、对象和状态
4. 元语言抽象
5. 寄存器机器里的计算
Chapter 3
- 模块化、对象和状态
练习答案
流
流作为延时的表
(stream-car (cons-stream x y)) = x
(stream-cdr (cons-stream x y)) = y
(define (stream-ref s n)
(if (= n 0)
(stream-car s)
(stream-ref (stream-cdr s) (- n 1))))
(define (stream-map proc s)
(if (stream-null? s)
the-empty-stream
(cons-stream (proc (stream-car s))
(stream-map proc (stream-cdr s)))))
(define (stream-for-each proc s)
(if (stream-null? s)
'done
(begin (proc (stream-car s))
(stream-for-each proc (stream-cdr s)))))
(define (display-stream s)
(stream-for-each display-line s))
(define (display-line x)
(newline)
(display x))
流实现的行为方式
(cons-stream <a> <b>)
(cons <a> (delay <b>)) ;;可以看作是对未来求值的一个允诺
(define (stream-car stream) (car stream))
(define (stream-cdr stream) (force (cdr stream))) ;;
delay和force的实现
(delay <exp>)其实只是lambda的一层语法糖衣(lambda () <exp>)
(define (force delayed-object)
(delayed-object))
具有记忆的过程
(define (memo-proc proc)
(let ((already-run? false) (result false))
(lambda ()
(if (not already-run?)
(begin (set! result (proc))
(set! already-run? true)
result)
result))))
(delay <exp>) = (memo-proc (lambda () <exp>))
无穷流
厄拉多塞筛法，构造出素数的无穷流
(define (sieve stream)
(cons-stream
(stream-car stream)
(sieve (stream-filter
(lambda (x)
(not (divisible? x (stream-car stream))))
(stream-cdr stream)))))
(define primes (sieve (integers-starting-from 2)))
;: (stream-ref primes 50)
隐式定义流
(define ones (cons-stream 1 ones))
(define (add-streams s1 s2)
(stream-map + s1 s2))
(define integers2 (cons-stream 1 (add-streams ones integers2)))
流计算模式的使用
用流表示迭代过程，来不同赋值方法来更新状态变量
(define (sqrt-improve guess x)
(average guess (/ x guess)))
(define (sqrt-stream x)
(define guesses
(cons-stream 1.0
(stream-map (lambda (guess)
(sqrt-improve guess x))
guesses)))
guesses)
;: (display-stream (sqrt-stream 2))
(define (pi-summands n)
(cons-stream (/ 1.0 n)
(stream-map - (pi-summands (+ n 2)))))
;: (define pi-stream
;: (scale-stream (partial-sums (pi-summands 1)) 4))
;: (display-stream pi-stream)
序对的无穷流
(define (stream-append s1 s2)
(if (stream-null? s1)
s2
(cons-stream (stream-car s1)
(stream-append (stream-cdr s1) s2))))
;: (pairs integers integers)
(define (interleave s1 s2)
(if (stream-null? s1)
s2
(cons-stream (stream-car s1)
(interleave s2 (stream-cdr s1)))))
(define (pairs s t)
(cons-stream
(list (stream-car s) (stream-car t))
(interleave
(stream-map (lambda (x) (list (stream-car s) x))
(stream-cdr t))
(pairs (stream-cdr s) (stream-cdr t)))))
将流作为信号
可以采用流，以一种非常直接的方式为信号处理系统建模
- 函数式程序的模块化和对象的模块化
我们引进赋值的主要收益就是可以增加程序的模块化，把一个大系统的状态进行封装，或者说隐藏到局部变量中。流模型可以提供相应的模块化又不必使用赋值
随机数生成器
(define rand
(let ((x random-init))
(lambda ()
(set! x (rand-update x))
x)))
(define random-numbers
(cons-stream random-init
(stream-map rand-update random-numbers)))
;: (define cesaro-stream
;: (map-successive-pairs (lambda (r1 r2) (= (gcd r1 r2) 1))
;: random-numbers))
(define (map-successive-pairs f s)
(cons-stream
(f (stream-car s) (stream-car (stream-cdr s)))
(map-successive-pairs f (stream-cdr (stream-cdr s)))))
(define (monte-carlo experiment-stream passed failed)
(define (next passed failed)
(cons-stream
(/ passed (+ passed failed))
(monte-carlo
(stream-cdr experiment-stream) passed failed)))
(if (stream-car experiment-stream)
(next (+ passed 1) failed)
(next passed (+ failed 1))))
时间函数式程序设计观点
在之前提款的例子中，同样可以用流的方式来实现那
(define (stream-withdraw balance amount-stream)
(cons-stream
balance
(stream-withdraw (- balance (stream-car amount-stream))
(stream-cdr amount-stream))))
用对象做模拟是强大的，但也产生了诸如进程的棘手问题，所以推动了函数式程序设计语言的开发。但在另一方面，与时间有关的问题也潜入了函数式模型中，之前对同一个银行操作的例子中，在函数式程序设计时，就需要去归并这两个操作，但是这又引发了对真实时间的依赖，