第三章习题 3.38 - 3.72 的解答。
E-3.38:
(a) 每个人的操作都作为一个原子操作的话，有 A(3, 3) 共 6 种可能：
Peter Paul Mary: 90 70 35
Peter Mary Paul: 90 45 25
Paul Peter Mary: 80 70 35
Paul Mary Peter: 80 40 20
Mary Peter Paul: 50 40 20
Mary Paul Peter: 50 30 20
(b) 其中一种情况：假设三人同时取到账户余额都是 100，各自执行操作后最后写入账户的是 Peter，于是账户余额为 90。
E-3.39: 可能的值为 100，101 和 121。
E-3.40: 可能值为 10^2，10^3 和 10^6。加了 serializer 后只有 10^6。
E-3.41: 我觉得没必要。查看账户是一个只读操作，并且不存在被打断的情况。
E-3.42: 两个函数最后结果都一样（没有取 balance/2 这样的情况），但中间过程的结果可能不一样。因为第一个版本每次执行 withdraw 或 deposit 都会开一个新进程，这样多个用户的执行顺序是不确定的；而这个版本则是每次都使用同一个进程，保证用户的操作顺序。
E-3.43: 假设第一个人刚把 balance 取出来，第二个人完整地执行了 exchange，这样第一个人取到的值是旧的，再用来交换就会出错。因为系统允许负数，并且仅仅是在账户中交换（账户的操作 withdraw 和 deposit 都是 serialize 的），尽管最后每个账户的结果可能不对，但是总的钱数不会变。
E-3.44: 我觉得两者是一样的，反正取出多少就存入多少，总量保持不变，只是最终状态不一致。
E-3.45: 多次调用了 balance-serializer。
E-3.46: 可能一个线程刚拿到结果，另一个线程就把结果给改了，这样返回给第一个线程的结果是错的。
E-3.47: 使用 test-and-set! 参考 make-mutex 的实现。
(define (make-semaphore n)
(let ((count 0)
(mutex (make-mutex)))
(define (the-semaphore m)
(cond ((eq? m 'acquire)
(mutex 'acquire)
(if (= count n)
(begin (mutex 'release)
(the-semaphore 'acquire))
(begin (set! count (+ count 1))
(mutex 'release))))
((eq? m 'release)
(mutex 'acquire)
(if (> count 0)
(set! count (- count 1)))
(mutex 'release))))
the-semaphore))
E-3.48: 都从最小编号的取起相当于排队系统，只有一个入口，防止循环等待。
E-3.49: 略。
E-3.50:
(load "../examples/3.5.1-streams-are-delayed-lists.scm")
(define (my-stream-map proc . argstreams)
(if (stream-null? (car argstreams))
the-empty-stream
(cons-stream
(apply proc (map stream-car argstreams))
(apply my-stream-map
(cons proc (map stream-cdr argstreams))))))
E-3.51: define 语句输出 0，第一个 ref 语句应该输出的是 1-5，第二个 ref 语句输出 6-7。
如果按照书本的实现，第一条 define 语句输出了 0-10；第一个 ref 语句直接输出 5；第二个 ref 直接输出 7。只有在构造的时候输出了一次列表（并且是完整的列表），后续的两个 ref 语句都没有重复输出。如果在 delay 和 force 函数中添加打印信息，可以发现在 stream-enumerate-interval 中已经把整个列表构造好了，这是因为 plt-scheme 并不是惰性求值的，解析器会先把递归函数先算出来再执行函数 cons-stream，因此会发现在初始化的时候已经把列表构造完成了。如果要实现惰性求值的功能，可以把 cons-stream 按以下方法实现（参考资料 [1]）：
(define-syntax cons-stream
(syntax-rules ()
((_ x y) (cons x (delay y)))))
(define (stream-cdr s) (force (cdr s)))
一般的 scheme 都自带了 delay 和 force，在这里使用的 plt-scheme（mzshcme 4.2.1）是有的。
E-3.52: 结果依次为 1，6，10，36，210。如果没有记忆功能的话结果应该是错的，因为 accum 被重复执行了。
E-3.53: f(n) = 2n
E-3.54:
(load "3.50.scm")
(load "../examples/3.5.2-infinite-streams.scm")
(define (mul-streams s1 s2)
(my-stream-map * s1 s2))
(define factorials (cons-stream 1 (mul-streams (stream-cdr integers) factorials)))
E-3.55:
(load "../examples/3.5.2-infinite-streams.scm")
(define (partial-sums s)
(cons-stream (stream-car s) (add-streams (partial-sums s) (stream-cdr s))))
E-3.56: 题目说得很清楚了。
(define S (cons-stream 1 (merge (scale-stream 2)
(merge (scale-stream 3)
(scale-stream 5)))))
E-3.57: 当 n>1 时，加法运算次数应该是 2 次，因为每次计算下一个值都只是将前两次的值加起来。如果没有实现记忆功能，每次计算 f(n) 时都要重新计算 f(n-1) 和 f(n-2)。
E-3.58: expand 的意义是求在 radix 进制下，num 除以 den 的商（如果 quotient 和 remainder 的操作也遵循 radix 进制的话）。
E-3.59:
(a) 下面是自己实现的版本，当然是很丑的……
(define (integrate-series stream)
(let ((counter 0))
(define (recur s)
(set! counter (+ counter 1))
(cons-stream (* (/ 1 counter)
(stream-car s))
(recur (stream-cdr s))))
(recur stream)))
然后很不甘心地在网上搜了下，果然找到更好的（参考资料 [2]）：
(load "../exercises/3.54.scm") ; mul-streams
(load "../examples/3.5.2-infinite-streams.scm") ; ones integers
(define (div-streams s1 s2)
(stream-map / s1 s2))
(define (integrate-series a)
(mul-streams a ; a0, a1, a2, ...
(div-streams ones integers))) ; 1/1, 1/2, 1/3, ...
(b) 按定义来就行。
(define cosine-series
(cons-stream 1 (integrate-series (scale-stream sine-series -1))))
(define sine-series
(cons-stream 0 (integrate-series cosine-series)))
E-3.60: 假设两个序列为 (ca a0 a1 a2 ...) 和 (cb b0 b1 b2 ...)，其中 ca 和 cb 是常数，则可拆为 ca * cb + ca * (b0 b1 b2 ...) + cb * (a0 a1 a2 ...) + (a0 a1 a2 ...) * (b0 b1 b2 ...) = ca * cb + ca * (b0 b1 b2 ...) + (a0 a1 a2 ...) * (cb b0 b1 b2 ...)。
(define (mul-series s1 s2)
(cons-stream (* (stream-car s1) (stream-car s2))
(add-streams (scale-stream (stream-cdr s2) (stream-car s1))
(mul-series (stream-cdr s1) s2))))
E-3.61:
(define (invert-unit-series stream)
(cons-stream 1 (scale-stream (mul-series (stream-cdr stream)
(invert-unit-series stream))
-1)))
E-3.62: 使用 invert-unit-series 前需要先将分母的常数变为 1，这也是为什么常数不能为 0 的原因。
(define (div-series s1 s2)
(let ((c2 (stream-car s2)))
(if (= c2 0)
(display "error\n")
(mul-series (scale-stream s1 (/ 1 c2))
(invert-unit-series (scale-stream s2 (/ 1 c2)))))))
E-3.63: 通过在 lambda 中加入打印每次计算的 guess 值可以看到题中的写法的确存在重复计算。使用了 guesses 变量后，每次访问后续的元素的时候都能直接从链表中取出（本地变量相当于对已有计算结果的一个引用），而直接写的话就是一个函数调用，每次都得从头计算。
如果没有使用 memo-proc，则没有记忆功能，也就是说每次使用流的时候都要重新计算，这样两者就一样了。
E-3.64:
(load "../examples/3.5.3-exploiting-the-stream-paradigm.scm")
(define (stream-limit stream tolerance)
(let ((first (stream-ref stream 0))
(second (stream-ref stream 1)))
(if (< (abs (- first second)) tolerance)
second
(stream-limit (stream-cdr stream) tolerance))))
; -------------------------------------------------------
(define (my-sqrt x tolerance)
(stream-limit (sqrt-stream x) tolerance))
(my-sqrt 2 0.000001)
E-3.65: 模仿pi的计算。
(load "../examples/3.5.3-exploiting-the-stream-paradigm.scm")
(define (ln2-summands n)
(cons-stream (/ 1.0 n)
(stream-map - (ln2-summands (+ n 1)))))
(define ln2-stream
(partial-sums (ln2-summands 1)))
; -------------------------------------------------------
;(display-stream-n ln2-stream 10)
;(display-stream-n (euler-transform ln2-stream) 10)
(display-stream-n (accelerated-sequence euler-transform ln2-stream) 10)
E-3.66: interleave 的取法是，从右上角（第一排）和右下角（去掉第一行和第一列后剩下的部分）之间轮流取一个元素。也就是说，当 i>1 时，(1,i) 和 (1,i+1) 之间隔着一个右下角的元素。而 (1,1) 是第一个被取到的元素，然后从 interleave 的结果中取下一个元素，因此取到 (1,100) 时一共取了 1+99+98=198 个元素。
令 f(n,n) 表示取到 (n,n) 时一共取的元素个数。先找一下规律：
f(2,2) - f(1,2) = 0 = 2^0 - 1
f(3,3) - f(2,3) = 1 = 2^1 - 1
f(4,4) - f(3,4) = 3 = 2^2 - 1
f(5,5) - f(4,5) = 7 = 2^3 - 1
f(6,6) - f(5,6) = 15 = 2^4 - 1
f(7,7) - f(6,7) = 31 = 2^5 - 1
即 f(n,n) - f(n-1,n) = 2^(n-2) - 1，其中 n>=2。
再看下一组规律：
f(2,2) - f(1,1) = 1
f(3,3) - f(2,2) = 3
f(4,4) - f(3,3) = 7
f(5,5) - f(4,4) = 15
f(6,6) - f(5,5) = 31
同理可得：f(n,n) - f(n-1, n-1) = 2^(n-1) - 1，其中 n>=2。
初值 f(1,1)=1，解得 f(n,n) = 2^n + n - 2，其中 n>=2。
于是
f(100,100) = 2^100 + 100 - 2 = 2^100 + 98
f(99,100) = f(100,100) - 2^98 + 1 = 2^100 + 98 - 2^98 + 1 = 2^100 - 2^98 + 99
E-3.67: 把第一列剩余的部分加上。
(load "../examples/3.5.3-exploiting-the-stream-paradigm.scm")
(define (full-pairs s t)
(cons-stream (list (stream-car s) (stream-car t))
(interleave
(interleave
(stream-map (lambda (x)
(list x (stream-car t)))
(stream-cdr s))
(stream-map (lambda (x)
(list (stream-car s) x))
(stream-cdr t)))
(pairs (stream-cdr s) (stream-cdr t)))))
; -----------------------------------------------------------------
(display-stream-n (full-pairs integers integers) 20)
E-3.68: 在做 3.66 的时候已经想到这个问题了，当时发现是死循环，但是没想到是为啥。原因见参考资料 [3]，原文部分摘录如下：
猛地想起来，虽然stream是lazy的，但scheme本身不是lazy的啊！
尤其是，scheme的函数调用，仍然是call-by-value的！
也就是说，尽管调用pairs后，我们只需要计算完interleave的第一个参数(stream-map ...)的第一个元素就可以输出（而在此时，这已经可以计算出来了），但由于call-by-value的限制，我们明知计算第二个参数没有用，还是得先计算才行！
问题就出在这里，第二个参数是什么？是对pairs的递归调用！而根据刚才的分析，这一调用同样还会进行更进一步的递归……而这个过程是无穷的！
于是就只能挂掉了……
而示例程序之所以不会错，正是因为将第一项独立出来马上可以取到，而避免了先要进行无谓计算的问题。
E-3.69: 先利用 pairs 生成二元组，再从二元组和第三维生成三元组。
(load "../examples/3.5.3-exploiting-the-stream-paradigm.scm")
(define (triples s t u)
(stream-map (lambda (x)
(append (car x) (cdr x)))
(pairs (pairs s t) u)))
; ------------------------------------------------------------
(display-stream-n (triples integers integers integers) 100)
(define (square x) (* x x))
(stream-filter (lambda (x)
(= (+ (square (car x))
(square (cadr x)))
(square (caddr x))))
(triples integers integers integers))
E-3.70: 因为 p1 和 p2 是两个不同的整数对，因此 merge 不能在 weight 相等的时候只取 p1 或 p2。还有就是用 merge-weighted 取代了原来的 interleave。这里不能把 weight-pairs 定义成“(merge-weighted integer-pairs integer-pairs weight)”，原因如 3.68 所述。
(load "../examples/3.5.3-exploiting-the-stream-paradigm.scm")
(define (merge-weighted s1 s2 weight)
(cond ((stream-null? s1) s2)
((stream-null? s2) s1)
(else
(let ((s1car (stream-car s1))
(s2car (stream-car s2)))
(cond ((< (weight s1car) (weight s2car))
(cons-stream
s1car
(merge-weighted (stream-cdr s1) s2 weight)))
(else
(cons-stream
s2car
(merge-weighted s1 (stream-cdr s2) weight))))))))
(define (weighted-pairs s t weight)
(cons-stream (list (stream-car s) (stream-car t))
(merge-weighted (stream-map (lambda (x)
(list (stream-car s) x))
(stream-cdr t))
(weighted-pairs (stream-cdr s) (stream-cdr t) weight)
weight)))
; ------------------------------------------------------------
(weighted-pairs integers integers
(lambda (x)
(+ (car x) (cadr x))))
(define not235
(stream-filter (lambda (x)
(and (not (= 0 (remainder x 2)))
(not (= 0 (remainder x 3)))
(not (= 0 (remainder x 5)))))
integers))
(weighted-pairs not235 not235
(lambda (x)
(let ((i (car x))
(j (cadr x)))
(+ (* 2 i) (* 3 j) (* 5 i j)))))
E-3.71:
(load "../exercises/3.70.scm")
(define (cube x) (* x x x))
(define (cube-sum pair)
(+ (cube (car pair)) (cube (cadr pair))))
(define cube-sum-list
(stream-map cube-sum
(weighted-pairs integers integers cube-sum)))
(define (ramanujan s)
(let ((first (stream-car s))
(second (stream-car (stream-cdr s))))
(if (= first second)
(cons-stream first
(ramanujan (stream-cdr s)))
(ramanujan (stream-cdr s)))))
; ------------------------------------------------------------
(display-stream-n (ramanujan cube-sum-list) 10)
接下来的5个依次是：4104，13832，20683，32832，39312。
E-3.72: 仿照3.71的做法即可。
(load "../exercises/3.70.scm")
(define (square x) (* x x))
(define (square-sum pair)
(+ (square (car pair)) (square (cadr pair))))
(define square-sum-list
(stream-map (lambda (x)
(append (list (square-sum x)) x)) ; 第一个是平方和，后面是pair
(weighted-pairs integers integers square-sum)))
(define (square-3 s)
(let ((first (stream-car s))
(second (stream-car (stream-cdr s)))
(third (stream-car (stream-cdr (stream-cdr s)))))
(if (and (= (car first) (car second))
(= (car first) (car third)))
(cons-stream (list first second third)
(square-3 (stream-cdr s)))
(square-3 (stream-cdr s)))))
; ------------------------------------------------------------
(display-stream-n (square-3 square-sum-list) 10)
参考资料
[1] SICP 3.5时delay的疑问(关于PLT Scheme)
[2] 练习 3.59
[3] SICP学习笔记之二：“微小”的差别……