目錄

• SICP第三章題解
  • ex3-17
  • ex3-18
  • ex3-19
  • 隊列
  • ex3-21
  • ex3-22
  • ex3-24
  • ex3-25
  • 3.4 并發：時間是一個本質問題
  • ex3-38
  • 3.4.2 控制并發的機制
  • ex3-39
  • ex3-41
  • ex3-42
  • 串行化、序列化
  • ex3-44
  • 串行化的實現
  • ex3-47
  • 死鎖
  • 3.5 流
  • ex3-50
  • 序列加速器

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)(elsejudge-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數量級的項才能算到同樣的精度。

歐拉真猛！

總結

以上是生活随笔為你收集整理的SICP第三章题解的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。