SICP第三章题解-阿里云开发者社区

开发者社区> 开发与运维> 正文
登录阅读全文

SICP第三章题解

简介: 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 判断一个表中是否包含环。

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

实现信号量。

  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(信号量)。。

死锁

有了前面“过程集”的概念作为铺垫,这里理解死锁就很容易了:比如当前并发进程P1和P2涉及到两个过程集S1和S2,每个进程都需要两个过程集里面的操作,但是由于一个过程集里同一时刻只能有一个过程被执行,一旦两个进程分别执行S1,S2中的过程,并且还要求执行另一个进程集里的过程,就产生了死锁。

小结一下:

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

3.5 流

delayforce实现延迟和强制求值,能实现流操作。
最简单的实现:

(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数量级的项才能算到同样的精度。

欧拉真猛!

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享: