# SICP第三章题解

[toc]

## 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

(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

(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))
)
)

## 队列

;;构造队列，默认为空队列
(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

(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

(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 并发：时间是一个本质问题

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

## ex3-39

(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变量的值，这一操作本身就是原子的。

## 串行化、序列化

java里有关键字Serializable，意思是（对象）序列化。

## ex3-44

Louis多虑了，并不需要更复杂精细的方法。交换操作要求交换的双方都处于空闲状态。

## 串行化的实现

mutex是mutual exclusion的缩写：互斥量，是信号量机制的一种简化形式。信号量来自THE操作系统，由Dijkstra提出，主要是经典的PV操作。

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
)
)
)

(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
)
)
)

## ex3-47

1. 基于互斥元的实现

(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
)
)
2. 基于原子的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（信号量）。。

## 死锁

并发问题==>用“串行化”解决==》但会产生“死锁”
||
||
\/
用mutex（互斥量）实现

## 3.5 流

delayforce实现延迟和强制求值，能实现流操作。

(define (delay exp)
(lambda () exp)
)

(define (force delayed-object)
(delayed-object)
)

(define (memo-proc)
(begin (set! result (proc))
result
)
)
)
)

(define (dalay exp)
(memo-proc (lambda () exp))
)

## ex3-50

(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图，递归地表示了信号处理流程。

+ 订阅