[Back]

3.3 用变动的数据做模拟

3.12

A) (b)

B) (b,c,d)

显然set-cdr!改变了它的值

3.13

盒子图形中,c的cdr指向了a,造成了一个无限循环

3.14

mystery实现了列表的逆序。

打印出来的值如下:

(a,b,c,d)

(d,c,b,a)

盒子图形很显然

3.15

自行模拟

3.16

只要这个序对中存在数据的共享,答案就会发生错误。

3.17

只需使用集合来去重即可

(define (count-pairs x)
    (define (inner x set)
        (if (and (pair? x) (not (memq x set)))
            (inner (car x) 
                (inner (cdr x) (cons x set)))
            set))
    (length (inner x `())))

3.18

(define (loop? x)
    (define (iter lst)
        (let ((id (cons `() `())))
            (cond ((null? lst) #f)
                  ((eq? id (car lst)) #t)
                  (else (set-car! (car lst) id)
                        (iter (cdr lst))))))
    (iter x))

3.19

使用步长步进法,每次前进一步和两步,如果能够相遇,则有环

(define (loop? lst)
    (define (iter x y)
        (let ((x-walk (list-walk 1 x))
              (y-walk (list-walk 2 y)))
            (cond ((or (null? x-walk) (null? y-walk))
                    #f)
                  ((eq? x-walk y-walk)
                    #t)
                  (else
                    (iter x-walk y-walk)))))
    (iter lst lst))
(define (list-walk step lst)
    (cond ((null? lst)
            '())
          ((= step 0)
            lst)
          (else
            (list-walk (- step 1)
                       (cdr lst)))))

3.20

自行模拟

3.21

由于删除操作并不对尾指针操作,因此,最后打印出来的队列尾指针还会指向最后一个数据

(define (print-queue queue)
    (define (iter que res)
        (cond ((null? que) res)
              (else (cons (car que) (iter (cdr que) res)))))
    (iter (front-ptr queue) `()))

3.22

(define (make-queue)
    (let ((front-ptr `())
          ((rear-ptr `())))
        (define (empty-queue?) (null? front-ptr))
        (define (set-front-ptr!)
            (lambda (val)
                (set! front-ptr val)))
        (define (set-rear-ptr!)
            (lambda (val)
                (set! rear-ptr val)))
        (define (front-queue)
            (cond ((empty-queue?)
                    (display "FRONT called with an empty queue"))
                  (else (car front-ptr))))
        (define (insert-queue!)
            (lambda (val)
                (let ((new-pair (cons value `())))
                    (cond ((empty-queue?)
                            ((set-front-ptr!) new-pair)
                            ((set-rear-ptr!) new-pair))
                          (else (set-cdr! rear-ptr new-pair)
                            ((set-rear-ptr!) new-pair))))))
        (define (delete-queue!)
            (cond ((empty-queue?)
                    (display "DELETE called with an empty queue"))
                  (else ((set-front-ptr!) (cdr front-ptr)))))
        (define (dispatch m)
            (cond ((eq? m `empty-queue?) (empty-queue?))
                  ((eq? m `front-queue) (front-queue))
                  ((eq? m `insert-queue!) (insert-queue!))
                  ((eq? m `delete-queue!) (delete-queue!))
                  (else (display "ERROR unknown command" m))))
        dispatch))

3.23

主要代码和queue类似,其中新定义insert-front! 和 delete - rear!

(define (insert-front! deque value)
    (cond ((empty-queue? deque) (insert-queue! deque))
          (else (let ((new-pair (cons value (front-ptr deque))))
                    (set-front-ptr! deque new-pair)))))
(define (delete-rear! deque)
    (define (find deque lst)
        (cond ((null? (cdr (cdr lst)))
                (set-cdr! lst '())
                (set-rear-ptr! deque lst)
                deque)
              (else
                (find deque (cdr lst)))))
    (cond ((empty-queue? deque)
            (display "DELETE called with an empty deque" deque))
          ((null? (cdr (front-ptr deque)))
            (set-front-ptr! deque `()))
          (else (find deque (front-ptr deque)))))

3.24

(define (assoc key table)
    (cond ((null? table) #f)
          ((same-key? key (caar table)) (car table))
          (else (assoc key (cdr table)))))

3.25

(define (lookup-inner keylist table)
    (if (null? keylist)
        table
        (let ((subtable (assoc (car keylist) (cdr table))))
            (if subtable
                (lookup-inner (cdr keylist) subtable)
                #f))))
(define (look-up keylist table)
    (if (null? keylist)
        #f
        (lookup-inner keylist table)))
(define (make-list keylist value)
    (if (null? (cdr keylist))
        (cons (car keylist value))
        (list (car keylist) (make-list (cdr keylist) value))))
(define (insert-inner! keylist value table)
    (if (null? (cdr keylist))
        (let ((record (assoc (car keylist) (cdr table))))
            (if record
                (set-cdr! record value)
                (set-cdr! table (cons (cons (car keylist) value) (cdr table)))))
                (let ((subtable assoc (car keylist) (cdr table)))
                    (if subtable
                        (insert-inner! (cdr keylist) value subtable)
                        (set-cdr! table (cons (make-list keylist value) (cdr table)))))))
(define (insert! keylist value table)
    (if (null? keylist)
        (display "INSERT! called with an empty keylist" keylist)
        (insert-inner! keylist value table)))

3.26

简要的谈谈实现

我们的每一个表格都以字典序的平衡二叉树组织起来

然后我们每次检索,就和关键字表的第一个与节点进行比对,向下搜索,同样我们也可以保证数据的嵌套性,因为一棵二叉树的一个节点也可以是一棵二叉树。

3.27

这是一种叫做记忆化搜索的技巧,环境图可以看到,对于fib 3 它不在表格中

因此计算fib 1 和 fib 2

然后fib 1 被计算出 1

Fib 2 去寻找fib1 发现表格中有fib 1,然后直接返回,不再计算

不可以,因为这样不会去执行记忆化搜索。

3.28

(define (or-gate a1 a2 output)
    (define (or-action-procedure)
        (let ((new-value
              (logical-or (get-signal a1) (get-signal a2))))
            (after-delay and-gate-delay
                (lambda ()
                    (set-signal! output new-value)))))
    (add-action! a1 or-action-procedure)
    (add-action! a2 or-action-procedure)
    `ok)

3.29

(define (orgate a1 a2 output)
    (let ((d (make-wire))
          (e (make-wire))
          (nand1 (make-wire))
          (nand2 (make-wire))
          (out (make-wire)))
          (and-gate a1 a2 d)
          (and-gate a1 a2 e)
          (invert-gate d nand1)
          (invert-gate e nand2)
          (and-gate nand1 nand2 out)
          (invert-gate out output)
    `ok))

详见与非门

时延2与2非

3.30

(define (ripple-carry-adder alist blist slist c)
    (let ((len (length alist)))
        (define (iter lenth alist blist slist)
            (cond ((= lenth 1) 
                    (full-adder (car alist) (car blist) (iter (+ lenth 1) (cdr alist) (cdr blist) (cdr slist)) (car slist) c))
                  ((= lenth len) 
                    (define cline (make-wire))
                    (full-adder (car alist) (car blist) 0 (car slist) cline)
                    cline)
                  (else (define cline (make-wire))
                    (full-adder (car alist) (car blist) (iter (+ lenth 1) (cdr alist) (cdr blist) (cdr slist)) (car slist) cline))))
        (iter 1 alist blist slist)))

时延是3个或门 2个非门和四个与门

3.31

如果我们不在加入动作之后立即执行这个动作,那么我们就会缺少一个初始开始的条件,模拟器并不会知道何时开始执行。(不会被加入到待处理表中)

在上面的半加器中,我们就永远获取不到这个结果了

3.32

我们同时监测了与门的两个输入端,如果采用FILO的栈设计,那么我们改变为1,0的过程会触发两次与门计算,后面的计算先被执行,此时答案为0,然后执行第一次,答案更新为1,就会发生错误。

数字电路的顺序性决定了数据结构的处理顺序。

3.33

(define (averager a b c)
    (define mid (make-connecter))
    (define sum (make-connecter))
    (define sumer (adder a b sum))
    (define mider (constant 0.5 mid))
    (define multer (multiplier sum mid c))
    (define (process-new-value)
        (cond ((and (has-value? a) (has-value? b))
                (inform-about-value sumer)
                (inform-about-value multer))
              ((and (has-value? c)
                    (or (has-value? a) (has-value? b)))
                (inform-about-value multer)
                (inform-about-value adder))))
    (define (process-forget-value)
        ((inform-about-no-value sumer)
        (inform-about-no-value multer)
        (process-new-value)))
    (define (me request)
        (cond ((eq? request `I-have-a-value)
                (process-new-value))
              ((eq? request `I-lost-a-value)
                (process-forget-value))
              (else (display "Unknown request -- AVERAGER" request))))
    me)

3.34

这个设计使得一个约束器上链接了两个同样的连接器,这样使得这个约束变成了单向约束,只能求得平方,而不能求得开根号。

一个解决方案是,定义一个内部的牛顿迭代法方法和平方方法,然后进行运算。

3.35

如上题提出的解决方案。

3.36

没有约束器,这个过程应该会直接结束。

3.37

(define (c- x y)
    (let ((p (make-connecter)))
        (adder p y x)
        p))
(define (c* x y)
    (let ((z (make-connecter)))
        (multiplier x y z)
        z))
(define (c/ x y)
    (let ((p (make-connecter)))
        (multiplier p y x)
        p))
(define (cv val)
    (let ((m (make-connecter)))
        (constant val m)
        m))

参见脚注,表达式风格的语言由于对复合数据采用了和基本数据一样的处理方式,可以省去定义许多中间变量,但是这样也带来了一个小小的坏处,一个表达式风格的语句不能直接越过连接器和约束器通信,或者说,无法不经过连接器获取到约束器的值,但是命令式风格的语言所提供的句柄却可以做到这一点。