文章出處

SICP第三章題解

標簽（空格分隔）： 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

判斷一個表中是否包含環。
我的思路：還是用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數量級的項才能算到同樣的精度。

歐拉真猛！

文章列表

不含病毒。www.avast.com

大師兄

IT工程師數位筆記本

大師兄發表在痞客邦留言(0) 人氣()

E-mail轉寄

IT工程師數位筆記本

If you give someone a program , you will frustrate them for a day; if you teach them how to program, you will frustrate them for a lifetime.IT 這段話的意思是，如果你交給某人一隻程式，你將折磨他一整天;如果你教會某人如何寫程式，你將折磨他一輩子。

BloggerAds