计算机程序的构造和解释(SICP) 第3章习题解析 Part5

这次回顾第三章第五部分习题。

学习资料：

https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-001-structure-and-interpretation-of-computer-programs-spring-2005/index.htm

https://github.com/DeathKing/Learning-SICP

https://mitpress.mit.edu/sites/default/files/sicp/index.html

https://www.bilibili.com/video/BV1Xx41117tr?from=search&seid=14983483066585274454

参考资料：

https://sicp.readthedocs.io/en/latest

http://community.schemewiki.org/?SICP-Solutions

http://community.schemewiki.org/?sicp

3.43(p215)

如果是顺序运行，那么任意一个账户不会同时和其他两个账户进行交易，因此最终的结果为$10,20,30$的排列。

如果使用第一个版本的程序进行交换，那么就无法保证这点；但是注意到$10,20,30$是等差数列，所以即使同时交换，也依然能保持综合不变，原因如下：

a   b   c    delta
10  20  30
10  20  30   a - b = -10
10  30  20   a - b = -10 (exchange b c)
20  20  20

a   b   c    delta
10  20  30
10  20  30   a - b = -10
30  20  10   a - b = -10 (exchange a c)
40  10  10

a   b   c    delta
10  20  30
10  20  30   b - c = -10
20  10  30   b - c = -10 (exchange a b)
20  20  20

a   b   c    delta
10  20  30
10  20  30   b - c = -10
30  20  10   b - c = -10 (exchange a c)
30  30  00

a   b   c    delta
10  20  30
10  20  30   a - c = -20
20  10  30   a - c = -20 (exchange a b)
40  10  10

a   b   c    delta
10  20  30
10  20  30   a - c = -20
10  30  20   a - c = -20 (exchange b c)
30  30  00

3.44(p215)

感觉Louis说的不对，因为transfer是如下的形式：

$a_0 \pm a_1 \pm \ldots \pm a_n$

这里交换$a_i ,i>0$的次序，并不会影响结果。

但是exchange的形式为

$a + (b -a' )$

我们希望的情形是$a=a’$，但是由于并发的原因，有可能出现$a\neq a’$的情形，所以会产生不正确的结果。

概括来说，这两者本质的不同是，后者增量不是固定的。

3.45(p216)

参考资料：

https://sicp.readthedocs.io/en/latest/chp3/45.html

http://community.schemewiki.org/?sicp-ex-3.45

(define (serialized-exchange account1 account2)
    (let ((serializer1 (account1 'serializer))
          (serializer2 (account2 'serializer)))
        ((serializer1 (serializer2 exchange))
          account1
          account2)))

(define (exchange account1 account2)
    (let ((difference (- (account1 'balance)
                        (account2 'balance))))
        ((account1 'withdraw) difference)
        ((account2 'deposit) difference)))

(serialized-exchange account1 account2)
(serializer1 (serializer2 exchange) account1 account2)
(account1.balance-serializer 
    (account2.balance-serializer exchange)
        account1 account2)
; 调用account1.balance-serializer, account2.balance-serializer
((account1 'withdraw) difference)
; 注意之前已经调用过account1.balance-serializer, 所以会产生死锁
((account1.balance-serializer withdraw) difference)

; 对比之前的方法
(serialized-exchange account1 account2)
(serializer1 (serializer2 exchange) account1 account2)
(account1.balance-serializer 
    (account2.balance-serializer exchange)
        account1 account2)
; 调用account1.balance-serializer, account2.balance-serializer
((account1 'withdraw) difference)
((account1.withdraw amount) difference)
((account2 'deposit) difference)
((account2.deposit amount) difference)

3.46(p218)

假设a, b可以同时访问互斥元，如果在访问过程中a将互斥元设置为false，那么下一时刻a, b都可以获得互斥元，这就产生了问题。

3.47(p218)

(load "serializer.scm")

(define false #f)
(define true #t)

; 基于mutex
(define (signal-n n)
    ; mutex列表
    (define (get-mutex-list i arr)
        (if (= i n)
            arr
            (get-mutex-list (+ i 1) (cons (make-mutex) arr))))
    ; 获得第i个元素
    (define (get-ith-element i arr)
        (if (= i 0)
            (car arr)
            (get-ith-element (- i 1) (cdr arr))))
    (let ((cells (get-mutex-list 0 '()))
          ; 可用位置的前一个位置
          (i -1))
        (define (the-signal m)
            (cond ((eq? m 'acquire)
                    ; 如果访问到最后, 则回到第一项, 否则访问下一个
                    (cond ((= i (- n 1)) 
                            (set! i -1)
                            (the-signal 'acquire))
                          (else
                            ;更新下标
                            (set! i (+ i 1))
                            (if (test-and-set! (get-ith-element i cells))
                                (the-signal 'acquire)))))
                  ((eq? m 'release)
                    (set! i (- i 1))
                    (clear! (get-ith-element i cells)))))
            the-signal))

; 基于test-and-set!
(define (make-n-signal n)
    (let ((cnt 0)
          (cell (list false)))
        (define (get-cells i arr)
            (if (= i n)
                arr
                (get-cells (+ i 1) (cons false arr))))
        (define (the-signal m)
            (cond ((eq? m 'acquire)
                    (set! cnt (+ cnt 1))
                    (if (= cnt n)
                        (if (test-and-set! cell)
                            (the-signal 'acquire))))
                  ((and (eq? m 'release) (= cnt n)) 
                    (set! cnt (- cnt 1))
                    (clear! cell))))
            the-signal))

(define (clear! cell)
    (set-car! cell false))

3.48(p219)

参考资料：

https://sicp.readthedocs.io/en/latest/chp3/48.html

问题所在是serialized-exchange时没有指定顺序：

(define (serialized-exchange account1 account2)
  (let ((serializer1 (account1 'serializer))
        (serializer2 (account2 'serializer)))
    ((serializer1 (serializer2 exchange))
     account1
     account2)))

解决方式是给每个account1指定一个编号，按照编号从小到大的顺序构造serialized-exchange。

(load "serializer.scm")

(define false #f)
(define true #t)

(define (exchange account1 account2)
  (let ((difference (- (account1 'balance)
                       (account2 'balance))))
    ((account1 'withdraw) difference)
    ((account2 'deposit) difference)))

(define (make-account-and-serializer balance index)
  (define (withdraw amount)
    (if (>= balance amount)
        (begin (set! balance (- balance amount))
               balance)
        "Insufficient funds"))
  (define (deposit amount)
    (set! balance (+ balance amount))
    balance)
  (let ((balance-serializer (make-serializer)))
    (define (dispatch m)
      (cond ((eq? m 'withdraw) withdraw)
            ((eq? m 'deposit) deposit)
            ((eq? m 'balance) balance)
            ((eq? m 'serializer) balance-serializer)
            ; add index
            ((eq? m 'index) index)
            (else (error "Unknown request -- MAKE-ACCOUNT"
                         m))))
    dispatch))

(define (serialized-exchange account1 account2)
  (let ((serializer1 (account1 'serializer))
        (serializer2 (account2 'serializer))
        (index1 (account 'index))
        (index2 (account 'index)))
    (if (< index1 index2)
        ((serializer2 (serializer1 exchange))
            account1
            account2)
        ((serializer1 (serializer2 exchange))
            account1
            account2))))

; test
(define account1 (make-account-and-serializer 100 1))
(display (account1 'index))

(exit)

测试结果：

3.49(p219)

参考资料：

https://sicp.readthedocs.io/en/latest/chp3/49.html

3.50(p225)

(load "stream.scm")

; proc(a[0], b[0], c[0], ...)
; proc(a[1], b[1], c[1], ...)
(define (stream-map proc . argstreams)
    (if (stream-null? (car argstreams))
        the-empty-stream
        (cons-stream
            (apply proc (map stream-car argstreams))
            (apply stream-map
                (cons proc (map stream-cdr argstreams))))))

; test
(define x (stream-enumerate-interval 0 10))
(define y (stream-enumerate-interval 0 10))
(define z (stream-enumerate-interval 0 10))
(define a (stream-map + x y z))
(display-stream a)

(exit)

结果如下：

3.51(p226)

(load "stream.scm")

(define (show x)
    (display-line x)
    x)

(define x (stream-map show (stream-enumerate-interval 0 10)))
(newline)
(display (stream-ref x 5))
(newline)
(display (stream-ref x 7))

(exit)

实验结果：

3.52(p226)

因为我使用的是Chez Scheme，此题和网上大佬的结果都不太一致，作为遗留问题吧。

(load "stream.scm")

(define (delay proc)
    (lambda () 
        (proc)))

(define sum 0)

(define (accum x)
  (set! sum (+ x sum))
  sum)

; (1 + ... + 20, 2 + ... + 20, ...)
(define seq (stream-map accum (stream-enumerate-interval 1 20)))
(display "sum: ")
(display sum)
(newline)

(define y (stream-filter even? seq))
(display "sum: ")
(display sum)
(newline)

(define z (stream-filter (lambda (x) (= (remainder x 5) 0))
                          seq))
(display "sum: ")
(display sum)
(newline)

(stream-ref y 7)
(display "sum: ")
(display sum)
(newline)

(display-stream z)
(newline)
(display "sum: ")
(display sum)
(newline)

(exit)

结果如下

sum: 210
sum: 210
sum: 210
sum: 210

210
200
195
165
155
105
90
20
sum: 210