SICP第三章题解
标签（空格分隔）： SICP
ex3-17
统计一个表结构中的序对个数
(define (count-pairs x)
(count-helper x '()))
(define (count-helper x seq)
(if (memq? x seq)
(count-helper (cdr x) seq)
(count-helper (cdr x) (list x seq))
)
)
ex3-18
判断一个表中是否包含环。
我的思路：还是用memq去判断。
(define (judge-cycle x)
(judge-cycle-helper x '()))
(define (judge-cycle-helper x seq)
(cond ((null? x) #f)
((memq? (car x) seq) #t)
(else
(judge-cycle-helper (cdr x) (list x seq))
)
)
)
ex3-19
重做ex3-18，采用一种只需要常量空间的做法。
我的思路：难道是用套圈的方式吗？相当于两个人跑步，一个人速度为v，另一个速度为2v，如果某人遇到nil就结束，如果两人除了开始节点外还有同样的节点就是套圈了。
(define (judge-cycle x)
(cond ((null? (cdr x)) #f)
((null? (cddr x)) #f)
(judge-cycle-helper (cdr x) (cddr x))
)
)
(define (judge-cycle-helper x y)
(cond ((null? (cdr x)) #f)
((null? (cddr y)) #f)
((eq? (car x) (car y)) #t)
(else
judge-cycle-helper (cdr x) (cddr y))
)
)
队列
设定一个queue，是cons序对，用来在O(1)时间内访问front和rear。这方法确实不错。
;;构造队列，默认为空队列
(define (make-queue) (cons '() '()))
;;队首指针
(define (front-ptr queue) (car queue))
;;队尾指针
(define (rear-ptr queue) (cdr queue))
;;队列判空。这里发现中文译文不是很准确。英文原文：
;;We will consider a queue to be empty if its front pointer is the empty list
(define (empty-queue? queue) (null? (front-ptr queue)))
;;队首元素
(define (front-queue queue)
(if (empty-queue? queue)
(error "FRONT called with an empty queue" queue)
(car (front-ptr queue))
)
)
ex3-21
原因在于，把queue中用来指引头指针和为指针的q的cdr也打印了。不打印cdr，只打印car即可。
(define (print-queue q)
(car q)
)
ex3-22
将队列构造成一个带有局部状态的过程
(define (make-queue)
(let ( (front-ptr '())
(rear-ptr '())
)
(define (dispatch m)
(cond ((eq? m 'insert-queue!) inserrt-queue!)
((eq? m 'delete-queue!) delete-queue!)
((eq? m 'empty-queue?) empty-queue?)
(else
(error "Unknown operation -- DISPATCH" m)
)
)
)
dispatch
)
)
ex3-24
我认为本题重写assoc过程即可。
(define (make-table same-key?)
(let ((local-table (list '*table*)))
(define (lookup key-1 key2)
(let ((subtable (assoc key-1 (cdr local-table))))
(if subtable
(let ((record (assoc key-2 (cdr subtable))))
(if record
(cdr record)
#f
)
)
#f
)
)
)
(define (assoc key records)
(cond ((null? records) false)
((same-key? key (caar records)) (car records))
(else (assoc key (cdr records)))
)
)
(define (dispatch m)
(cond ((eq? m 'lookup-proc) lookup)
((eq? m 'insert-proc!) insert!)
(else (error "Unknown operation -- TABLE" m))
)
)
dispatch
)
)
ex3-25
用递归做。
(define (lookup key-list table)
(if (list? key-list)
(let ((record (assoc ((cdr key-list) (cdr table)))))
(if record
(if (null? (cdr key-list))
(cdr record)
(lookup (cdr key-list) record)
)
#f
)
)
;;else
#f
)
)
(define (insert! key-list value table)
(if (list? key-list)
(let ((record (assoc (car key-list) (cdr table))))
(if record
(if (null? (cdr key-list))
(set-cdr! record value)
(insert! (cdr key-list) value (cdr table))
)
(set-cdr! table
(cons (list (key-list value)) (cdr table))
)
)
)
;;else
#f
)
)
3.4 并发：时间是一个本质问题
为什么Erlang适合高并发？我猜测是，Erlang中局部变量非常少，基本上没有内部变量，因此不会涉及太多访问顺序的问题。
对一个表达式求值的结果不仅依赖于该表达式本身，还依赖于求值发生在这些时刻之前还是之后：时间（顺序）是一个本质问题。
比如两个人都能操作同一个银行账户，同时取钱就可能产生错误：只要取钱过程不是原子操作（比如没有被锁住），就可能使内部变量的值算错。但是，怎样实现原子操作？
P.S.终于看到书的一半了！（经典的书值得慢慢读）
ex3-38
mary->peter->paul 40
mary->paul->peter 40
peter->mary->paul 35
peter->paul->mary 45
paul->mary->peter 50
paul->peter->mary 45
3.4.2 控制并发的机制
串行访问：进程能并发执行，但过程不能并发执行。
具体说就是：串行化操作会创建若干“过程集”，每个“过程集”中的过程只能串行执行，如果一个进程要执行一个“过程集”的一个过程，就要等到这个“过程集”当前执行的过程执行完毕才可以执行。
用串行化能控制共享变量的访问。比如，修改变量S的操作依赖于S原有的值，那么我们把读取S和给S赋值的操作放到同一个过程。并且还要设法保证，其他任何给S赋值的过程，能和这个过程并发执行；具体做法是：把其他为S赋值的操作与这个操作（读取S再修改S这个过程）放到一个串行化集合（即“过程集”）里面。
ex3-39
一个思路是把(set!)表达式抽象出来看作一个整体。因为 ((s (lambda () (* x x)))) 和 ((s (lambda () (set! x (+ x 1))))) 都是串行化操作，因此可以将它们看作是一个单独的执行单位 sa 和 sb ，并将题目给出的表达式转换成以下表示：
(parallel-execute (lambda () (set! x sa))
sb)
以上表达式可能的执行序列有以下这些（ ? 符号表示执行过程被其他操作打断）：
sb –> (set! x sa)
(set! x ?) –> sb –> (set! x sa)
(set! x sa) –> sb
这些执行序列会产生以下结果：
(set! x (+ 10 1)) => x = 11 => (set! x (* 11 11)) => x = 121
[计算 sa=100] => (set! x (+ 10 1) => x = 11 => (set! x sa) => x = 100
(set! x (* 10 10)) => x = 100 => (set! x (+ 100 1)) => x = 101
ex3-41
Ben的做法没有必要。读取balance变量的值，这一操作本身就是原子的。
ex3-42
和上面一题应该是一致的效果，是安全的。不同点在于，ex-3.41是调用deposit或withdraw时产生响应的串行过程，而ex-3.42是在调用make-account的时候返回的过程中就包含了withdraw和deposit对应的串行过程。
虽然ex-3.42使用的是same serializer（同一个串行化过程），但是因为串行化过程本身就是一个原子操作，同一个make-account生成的对象的并发调用withdraw或deposit的操作，还是会被正确执行。
串行化、序列化
java里有关键字Serializable，意思是（对象）序列化。
稍微搜了下java Serializable，排名靠前的文章都没有提到并发问题。think in java中似乎也没有提到serializable和并发是相关的。
但读SICP的P214时候，明显感觉到，串行化（序列化）就是使进程可以并发执行的一种解决办法。大家都没有注意到吗？
ex3-44
Louis多虑了，并不需要更复杂精细的方法。交换操作要求交换的双方都处于空闲状态。
串行化的实现
终于到讨论Serializable的实现的时候了：用mutex实现。
mutex是mutual exclusion的缩写：互斥量，是信号量机制的一种简化形式。信号量来自THE操作系统，由Dijkstra提出，主要是经典的PV操作。
在我们的实现里，每个串行化组关联着一个互斥元；给了一个过程P，串行化组将返回一个过程，该过程将获取相应互斥元，而后运行P，而后释放该互斥元。这样就保证，由这个串行化组产生的所有过程中，一次只能运行一个，这就是需要保证的串行化性质。
P.S. P219提到：在当前的多处理器系统里，串行化方式正在被并发制的各种新技术取代
(define (make-serializer)
(let ((mutex (make-mutex)))
(lambda (p)
(define (serialized-p . args)
(mutex 'acquire)
(let ((val (apply p args)))
(mutex 'release)
val
)
)
serialized-p
)
)
)
看到LISP的代码被我写成这个样子，我才发现，Python用缩进(indent)是多么正确的一件事：各种反括号都不用写了！
互斥元的实现
(define (make-mutex)
(let ((cell (list false)))
(define (the-mutex m)
(cond ((eq? m 'acquire)
;;注意：if语句不写else分支也是ok的
(if (test-and-set! cell)
(the-mutex 'acquire)
)
)
((eq? m 'release) (clear! cell))
)
)
the-mutex
)
)
(define (clear! cell)
(set-car! cell false)
)
(define (test-and-set! cell)
(if (car cell)
true
(begin (set-car! cell true)
false
)
)
)
这里的一个细节是：需要保证test-and-set!过程的原子性：显然，一旦cell的值为false，那么测试cell的值和修改cell的值这两个过程就要一气呵成。
对于单处理器，如果是分时系统，只要保证在检查和设置cell值之间禁止进行时间分片，就能保证原子性。
对于多处理器，硬件中已经支持原子操作了。
ex3-47
实现信号量。
- 基于互斥元的实现
(define (make-semaphore n)
(let ((mutex (make-mutex)))
(define (acquire)
(mutex 'acquire)
(if (> n 0)
(begin (set! n (- n 1))
(mutex 'release)
)
(begin
(mutex 'release)
(acquire)
)
)
)
(define (release)
(mutex 'acquire)
(set! n (+ n 1) )
(mutex 'release)
)
(define (dispatch m)
(cond ((eq? m 'acquire) (acquire))
((eq? m 'release) (release))
(else (error "Unknown mode MAKE-SEMAPHORE" mode))
)
)
dispatch
)
)
- 基于原子的
test-and-set!操作
(define (make-semaphore n)
(let ((cell (list #f))) ;;modified
(define (request m)
(cond ((eq? m 'acquire)
(if (test-and-set! cell)
(request m)
(cond ((= n 0)
(clear! cell)
(request m)
)
(else
(begin (set! n (- n 1))
(clear! cell)
)
)
)
)
)
((eq? m 'release)
(if (test-and-set! cell)
(request m)
(begin
(set! n (+ n 1))
(clear! cell)
)
)
)
(else (error "Unknown request" m))
)
)
request
)
)
但是其实这里内部变量cell仍然是一个mutex（信号量）。。
死锁
有了前面“过程集”的概念作为铺垫，这里理解死锁就很容易了：比如当前并发进程P1和P2涉及到两个过程集S1和S2，每个进程都需要两个过程集里面的操作，但是由于一个过程集里同一时刻只能有一个过程被执行，一旦两个进程分别执行S1，S2中的过程，并且还要求执行另一个进程集里的过程，就产生了死锁。
小结一下：
并发问题==>用“串行化”解决==》但会产生“死锁”
||
||
\/
用mutex（互斥量）实现
3.5 流
用delay和force实现延迟和强制求值，能实现流操作。
最简单的实现：
(define (delay exp)
(lambda () exp)
)
(define (force delayed-object)
(delayed-object)
)
带记忆功能的实现：
(define (memo-proc)
(let ((already-run? false) (result false))
(if (not already-run?)
(begin (set! result (proc))
(set! already-run? true)
result
)
)
)
)
(define (dalay exp)
(memo-proc (lambda () exp))
)
ex3-50
实现推广的stream-map
(define (stream-map proc . argstreams)
(if (null? (car argstreams))
'()
(cons-stream
(apply proc (map (lambda (s) (stream-car s))
argstreams))
(apply stream-map
(cons proc (map (lambda (s) (stream-cdr s))
argstreams))
)
)
)
)
Henderson图，递归地表示了信号处理流程。
序列加速器
欧拉提出的方法，对于交错级数的部分和十分有效。比如S(n)表示前n项和，那么S(n+1)-(S(n+1)-S(n))^2/(S(n-1)-2S(n)+S(n+1))就是加速序列
用这种方法逼近π，只需要8次计算，就能算到14位精度，而如果不使用加速，那么需要10^13数量级的项才能算到同样的精度。
欧拉真猛！