;3.24
(define (make-table same-key?)
    ...
    (define (assoc key records)
      (cond ((null? records) false)
            ((same-key? key (caar records)) (car records))
            (else (assoc key (cdr records)))))
    ...
    dispatch)

;test
(define (same? a b)
  (if (and (number? a)
           (number? b))
      (< (abs (- a b)) 2)
      (equal? a b)))
(define t1 (make-table same?))
(insert! 'c 10 1000 t1)
(insert! 'c 9 90 t1)
> (lookup 'c '10 t1)
90
> (lookup 'c '11.4 t1)
90
可以看到，(c 10 1000)那条记录已经被覆盖掉了，变成了(c 10 90)

2.93
除了把make-rat改了，还要把apply-generic中的drop语句弄掉，否则当时用的round过程会报错。
2.94
  (define (gcd-terms l1 l2)
    (if (empty-termlist? l2)
        l1
        (gcd-terms l2 (remainder-terms l1 l2))))
  (define (remainder-terms a b)
    (cadr (div-terms a b)))
然后加上interface:poly，g-c-d

2.95
Drscheme返回的结果：
(polynomial x (2 8+106/169) (1 -17+43/169) (0 8+106/169))，可以看到这与x^2-2*x+1的对应项系数是成比例的。
原因在于除法的计算过程，每次上的商的系数都是(div (coeff t1) (coeff t2))，这里没有考虑这个系数是否为整数。然后之后的相减就出现了一系列的分数。

2.96
方法题目中已经讲的很细了，要做的只是简单实现一下。又一次看到SICP是怎样把一个复杂的问题一点一点嚼碎了喂给我们的。
(define (gcd-terms l1 l2)
    (define (div-term-by-number l a)
        (if (null? l)
            '()
            (let ((t (first-term l)))
              (adjoin-term (make-term (order t)
                                      (/ (coeff t) a))
                           (div-term-by-number (rest-terms l) a)))))
    (define (gcd-terms-helper l1 l2)
      (if (empty-termlist? l2)
          l1
          (gcd-terms-helper l2 (pseduoremainder-terms l1 l2))))
    (define (gcd-coeff l)
      (define (coeff-list term-list)
        (if (empty-termlist? term-list)
            '()
            (cons (coeff (first-term term-list))
                  (coeff-list (rest-terms term-list)))))
      (apply gcd (coeff-list l)))
    (div-term-by-number (gcd-terms-helper l1 l2)
                        (gcd-coeff (gcd-terms-helper l1 l2))))

 (define (pseduoremainder-terms a b)
    (let ((t1 (first-term a))
          (t2 (first-term b)))
      (let ((o1 (order t1))
            (o2 (order t2))
            (c2 (coeff t2)))
        (let ((pseduo-c (expt c2 (+ 1 (- o1 o2)))))
          (cadr (div-terms (mul-terms (list pseduo-c) a)
                           b))))))
                          
2.97
a) poly包里面：
(define (reduce-terms n d)
    (let ((the-gcd-term (gcd-terms n d)))
      (let ((nn (car (div-terms n the-gcd-term)))
            (dd (car (div-terms d the-gcd-term))))
        (list nn dd))))
(define (reduce-poly p1 p2)
    (if (same-variable? (variable p1) (variable p2))
        (let ((reduce-temp (reduce-terms (term-list p1) (term-list p2))))
          (list (make-poly (variable p1) (car reduce-temp))
                (make-poly (variable p1) (cadr reduce-temp))))
        (error "Poly not in the same variable--REDUCE-POLY"
               (list p1 p2))))
(put 'reduce '(polynomial polynomial)
       (lambda (p1 p2)
         (list (tag (car (reduce-poly p1 p2)))
               (tag (cadr (reduce-poly p1 p2))))))
              
b) (define (make-rat number denom)
    (let ((reduce-temp (reduce number denom)))
      (cons (car reduce-temp)
            (cadr reduce-temp))))
看着以前写的一大坨代码有条不紊的互相合作，感觉真是相当不错——尽管这是被一步一步引导的。

一看提示“这绝不简单!" ……希望有机会写上

  本题比较简单了，只有一个小问题，除法返回的有商和余式，所以不可以直接作为多项式返回。我给加的tag是div-poly，感觉加上polynomial可能也是可行的，不过需要修改很多选择函数。不过主要注意的是div-term，别的也就不管了
 (define (div-terms l1 l2)
    (if (empty-termlist? l1)
        (list (the-empty-termlist) (the-empty-termlist))
        (let ((t1 (first-term l1))
              (t2 (first-term l2)))
          (if (> (order t2) (order t1))
              (list (the-empty-termlist) l1)
              (let ((new-c (div (coeff t1) (coeff t2)))
                    (new-o (- (order t1) (order t2))))
                (let ((new-term (make-term new-o new-c)))
                  (let ((rest-of-result (sub-terms l1 (mul-terms l2 (list new-term)))))
                    (list (adjoin-term new-term
                                       (car (div-terms rest-of-result l2)))
                          (cadr (div-terms rest-of-result l2))))))))))

2.89
我基本没修改add-term以上的过程，只在下面的first-term(rest-term两者相同)/make-term/adjoin-term/coeff/order这些上区分了两者。
first-term要携带order的信息：(define (first-term x) x)
(make-term order coeff)生成一个car为coeff,其余项为0，总长度为order+1的list
adjoin-term：由于此过程都用于高次项加入低次的项表中，所以直接连接term和term-list，空项由0来填充。
coeff/order返回一个数值，具体过程实现后面会写。

2.90
为了通用稍微修改了一下add-term过程：
  (define (add-terms l1 l2)  
    (cond ((and (empty-termlist? l1)
                (empty-termlist? l2)) '())
          (else (let
                    ((t1 (first-term l1))
                     (t2 (first-term l2)))
                  (cond ((> (order t1) (order t2))
                         (adjoin-term (make-term (order t1) (coeff t1))
                                      (add-terms (rest-terms l1) l2)))
                        ((< (order t1) (order t2))
                         (adjoin-term (make-term (order t2) (coeff t2))
                                      (add-terms (rest-terms l2) l1 )))
                        (else
                         (adjoin-term (make-term (order t1)
                                                 (add (coeff t1)
                                                      (coeff t2)))
                                      (add-terms (rest-terms l1)
                                                 (rest-terms l2)))))))))
对比之前存在rect和polar两种表示的复数过程。当时是把各个表示前分别cons上了'rectangular和'polar，这样可行的原因之一是由于两种表示方法所区分的过程都是直接应用在这个复数上的，如real-part。
本题遇到的最大麻烦在于虽然first-term这样的过程是用在term-list上的，而coeff、order这些是应用在term上的过程。怎样区分两种term-list的表示方法，而又怎样把term-list区分的结果传递到提取的term上，是本题的关键。
    1.两种term-list表示方法我命名为thin和dense(thin太丑陋了……貌似应该是sparse)。在表示term-list方面两者的分别是：thin为一个序对组成的list，而dense是由一个个系数组成的list。
    2.注意到整个系统中只有first-term是用来取单个term的，所以在这里根据term-list的区别分别加上'dense或是'thin的标签。
ps.才指导有load这东西，总算不用把之前敲的大片大片的粘过来了。
具体实现：里面返回的多项式采用了dense-term-list的表示方法
(define (install-dense-term)
    ;=======procedures of termlist=========
    (define (first-term term-list)
      (if (null? term-list)
          (attach-tag 'dense '(0))
          (attach-tag 'dense term-list)))
    ;======procedures of terms=========  
    ;~~~~~~~~~~~~~~~~~
    (define (adjoin-term term term-list) ;term-list次数一定比term要低
      (let ((order-dense (get 'order '(dense))))
        (if (= (order-dense term-list) (order-dense term))
            term-list
            (cons (car term)
                  (adjoin-term (cdr term) term-list))))) 
    (define (make-term order coeff)
      (define (make-term-helper temp-order)
        (if (> temp-order 0)
            (append (make-term-helper (- temp-order 1))
                    '(0))
            (list coeff)))
      (make-term-helper order))      
    ;~~~~~~~~~~~~~~~~~
    (define (order t)
      (cond ((null? t) -1)
            ((null? (cdr t)) 0)
            (else (+ 1 (order (cdr t))))))
    (define (coeff t) (car t))
    ;interface
    (put 'first-term '(dense-term-list) first-term)
    (put 'coeff '(dense) coeff)
    (put 'order '(dense) order)
    'Done-dense-termlist)
 
  ;--------install-thin---------
  (define (install-thin-term)
    ;======procedures-of-termlist==========
    (define (first-term term-list)
      (if (null? term-list)
          (attach-tag 'thin '(0 0))
          (attach-tag 'thin (car term-list))))
    ;=====procedure-of-terms============
    ;~~~~~~~~~~~~~~~~~~
    (define (adjoin-term term term-list)
      (let ((coeff-thin (get 'coeff '(thin))))
        (if (=zero? (coeff-thin term))  
            term-list
            (cons term term-list))))  
    (define (make-term order coeff)
      (list order coeff))
    ;~~~~~~~~~~~~~~~~~~~~
   
    (define (order t) (car t))
    (define (coeff t) (cadr t))
   
    ;interface
    (put 'first-term '(thin-term-list) first-term)
    (put 'coeff '(thin) coeff)
    (put 'order '(thin) order)
    'Done-thin-termlist)
 
  ;-----procedures of term-list------
  (define (the-empty-termlist) '())
  (define (empty-termlist? term-list)
      (null? term-list))
  (define (rest-terms term-list)
    (if (null? term-list)
        '()
        (cdr term-list)))
  (define (dense-termlist? term-list)
    (cond ((null? term-list) #f)
          ((pair? (car term-list)) #f)
          (else #t)))
  (define (first-term term-list)
    (if (dense-termlist? term-list)
        ((get 'first-term '(dense-term-list)) term-list)
        ((get 'first-term '(thin-term-list)) term-list)))
  (define (coeff term) (apply-generic 'coeff term))
  (define (order term) (apply-generic 'order term))
  ;========adjoin-term, make-term需要手动交换========
  (define (adjoin-term term term-list)
      (let ((order-dense (get 'order '(dense))))
        (if (= (order-dense term-list) (order-dense term))
            term-list
            (cons (car term)
                  (adjoin-term (cdr term) term-list))))) 
  (define (make-term order coeff)
    (define (make-term-helper temp-order)
      (if (> temp-order 0)
          (append (make-term-helper (- temp-order 1))
                  '(0))
          (list coeff)))
    (make-term-helper order))       
 
 
  ;rest-terms相同，暂且不写
 

http://eli.thegreenplace.net/2008/06/06/signed-copy-of-sicp/#comments

那位做完习题的以色列牛，竟然收到了作者寄来的免费的签名紫皮书，太爽了。

一个微妙的问题：在polynomial包中写了一个negative-poly的过程，在put的时候才加上'polynomial；而其他的如scheme-number,rational,complex都没有相应的negative-complex等等。开始在poly中我也是不分negative和negative-poly，结果(add-poly p1 (negative p2)的时候发生错误。对于内部negative(如negative-poly)和外部negative何时该分别对待这个问题，我觉得如果内部对于本类型没有负操作的需要，那么不用区分内外的negative；如果有需要，则可能需要区分……待验证
(define (sub-poly p1 p2)
    (add-poly p1 (negative-poly p2)))
(define (negative-poly poly)
    (define (negative-term-list term-list)
      (if (null? term-list)
          '()
          (let ((t1 (first-term term-list)))
            (adjoin-term (make-term (order t1)
                                    (negative (coeff t1)))
                         (negative-term-list (rest-terms term-list))))))
  (make-poly (variable poly)
             (negative-term-list (term-list poly))))
(put 'negative '(polynomial)
     (lambda (poly)
       (tag (negative-poly poly))))
;-------scheme-number---------
(put 'negative '(scheme-number)
     (lambda(x) (make-scheme-number (* -1 x))))
;---------rational------------
(put 'negative '(rational)
     (lambda(x) (make-rational (negative (numer x))
                               (denom x))))
;---------complex-------------
(put 'negative '(complex)
     (lambda(x) (make-complex-from-real-imag (negative (real-part x))
                                             (imag-part x))))

ps. 今天是7月2日，DrScheme里多了个按钮，点开一看是Happy Birthday,Robby!看了下帮助，有个作者叫Robby Findler，有点意思

把第二章落下的一些东西补完：
书中的思路清晰的很，add-poly剥离了变量的复杂性；add-term剥离的项表表示的复杂度，只解决运算的关系；然后adjoin-term、make-term这些用来完成项表的具体实现。
在敲代码的时候把add-terms里面相加的语句写成了(add-terms (rest-terms l1) (adjoin-term t1 l2))，开始还以为只是另一种写法，后来发现这样是会出现死循环的。

关于本题的=zero?过程，写进install-polynomial-package中
(define (coeff-zero? term-list)
    (cond ((null? term-list) #t)
          ((not (= (coeff (first-term term-list)) 0))
           #f)
          (else (coeff-zero? (rest-terms term-list)))))
  (put '=zero? '(polynomial)
       (lambda(poly)
         (if (empty-termlist? (term-list poly))
             #t
             (coeff-zero? (term-list poly)))))

;08/6/28
;ex 3.23
;deque
;rear-delete-deque!是四个过程中比较特殊的，因为删除之后需要寻址队列的倒数第二个节点。
;又题目要求时间复杂度为O(1)，所以采用双向链表。
;与以前不同是front-delete-deque!和rear-delete-deque!需要确保两端的一致性
;另外写了个print过程用来做显示输出
;--------deque-node------------
(define (make-deque-node former-ptr data next-ptr)
  (list former-ptr data next-ptr))
(define (former-ptr node)
  (car node))
(define (data node)
  (cadr node))
(define (next-ptr node)
  (caddr node))
(define (set-former-ptr! node new-ptr)
  (if (null? node)
      '()    ;do nothing
      (set-car! node new-ptr)))
(define (set-data! node new-data)
  (if (null? node)
      '()  ;do nothing
      (set-car! (cdr node) new-data)))
(define (set-next-ptr! node new-ptr)
  (if (null? node)
      '()    ;do nothing
      (set-car! (cddr node) new-ptr)))
 
;--------deque--------
(define (front-ptr deque) (car deque))
(define (rear-ptr deque) (cdr deque))
(define (set-front-ptr! deque item)
  (set-car! deque item))
(define (set-rear-ptr! deque item)
  (set-cdr! deque item))

(define (empty-deque? deque)
  (null? (rear-ptr deque)))
(define (make-deque) (cons '() '()))
(define (front-deque deque)      ;队列前端的数据项
  (if (empty-deque? deque)
      (error "FRONT called by empty deque" deque)
      (data (front-ptr deque))))
(define (rear-deque deque)      ;队列前端的数据项
  (if (empty-deque? deque)
      (error "REAR called by empty deque" deque)
      (data (rear-ptr deque))))

(define (rear-insert-deque! deque item)
  (let ((new-node (make-deque-node '()
                                   item
                                   '())))
    (cond ((empty-deque? deque)
           (set-front-ptr! deque new-node)
           (set-rear-ptr! deque new-node)
           deque)
          (else
           (set-former-ptr! new-node (rear-ptr deque))
           (set-next-ptr! (rear-ptr deque) new-node)
           (set-rear-ptr! deque new-node)
           deque))))
(define (front-insert-deque! deque item)
  (let ((new-node (make-deque-node '() item '())))
    (cond ((empty-deque? deque)
           (set-front-ptr! deque new-node)
           (set-rear-ptr! deque new-node)
           deque)
          (else
           (set-next-ptr! new-node (front-ptr deque))
           (set-former-ptr! (front-ptr deque) new-node)
           (set-front-ptr! deque new-node)
           deque))))
(define (front-delete-deque! deque)
  (cond ((empty-deque? deque)
         (error "DELETE an empty deque " deque))
        (else (set-front-ptr! deque
                              (next-ptr (front-ptr deque)))
              (if (null? (front-ptr deque))         ;保持front-ptr和rear-ptr一致
                  (begin (set-rear-ptr! deque '())
                         deque)
                  deque))))
(define (rear-delete-deque! deque)
  (cond ((empty-deque? deque)
         (error "DELETE an empty deque " deque))
        (else (set-rear-ptr! deque (former-ptr (rear-ptr deque)))
              (set-next-ptr! (rear-ptr deque) '())
              (if (null? (rear-ptr deque))         ;保持front-ptr和rear-ptr一致
                  (begin (set-front-ptr! deque '())
                         deque)
                  deque))))
(define (print deque)
  (define (print-helper ptr)
    (if (null? ptr)
        'Done
        (begin
          (display (data ptr))
          (display "   ")
          (print-helper (next-ptr ptr)))))
  (print-helper (front-ptr deque)))

才明白一点，这样的方法类似面向对象的类，其中的成员front-ptr/rear-ptr不需要用cons联系起来...
(define (make-queue)
  (let ((front-ptr '())
        (rear-ptr '()))
    (define (set-front-ptr! item) (set! front-ptr item))
    (define (set-rear-ptr! item) (set! rear-ptr item))
    (define (empty-queue?) (null? front-ptr))
    (define (insert-queue! item)
      (let ((new-pair (cons item '())))
        (cond ((empty-queue?)
               (set-front-ptr! new-pair)
               (set-rear-ptr! new-pair)
               (cons front-ptr rear-ptr))
              (else
               (set-cdr! rear-ptr new-pair)
               (set-rear-ptr! new-pair)
               (cons front-ptr rear-ptr)))))
    (define (delete-queue!)
      (cond ((empty-queue?)
             (error "DELETE an empty queue " (cons front-ptr rear-ptr)))
            (else (set-front-ptr! (cdr front-ptr))
                  (cons front-ptr rear-ptr))))
    (define (dispatch m)
      (cond ((eq? m 'front-ptr) front-ptr)
            ((eq? m 'rear-ptr) rear-ptr)
            ((eq? m 'set-front-ptr!) set-front-ptr!)
            ((eq? m 'set-rear-ptr!) set-rear-ptr!)
            ((eq? m 'empty-queue?) empty-queue?)
            ((eq? m 'insert-queue!) insert-queue!)
            ((eq? m 'delete-queue!) delete-queue!)
            (else (error "UNKNOWN operation" m))))
    dispatch))
(define (front-ptr queue) (queue 'front-ptr))
(define (rear-ptr queue) (queue 'rear-ptr))
(define (insert-queue! queue item)
  ((queue 'insert-queue!) item))
(define (delete-queue! queue)
  ((queue 'delete-queue!)))

(define (print-queue queue)
  (print-list (front-ptr queue)))
(define (print-list item)
  (if (null? item)
      'Done
      (begin (display (car item))
             (display "  ")
             (print-list (cdr item)))))

 

临走那天宿舍一帮哥们忙里忙外的搬东西，前一分钟还跟出租车司机有说有笑，之后关上车门就走了。我这边也才明白过来，丫们不是出去办事了，以后来学校才是过来办事了。不过随之而来的感觉不是伤离别，而是马上想出他们还在北京我也还在北京，都没跑多远呢，别那么做作的伤感了。然后像之前几天一样，借着毕业的理由，去吃烤肉。回来也不能闲着，DOTA、GGXX照常进行，赶紧把自己折腾累了好睡觉。
没睡好，做梦都是楼管带着刷墙队过来清宿舍的场面。醒来的时候宿舍剩的几个哥们的行李都卷起来了，一个电话之后，宿舍就留下我跟一地的乱七八糟，有用的和没用的。我是三个宿舍最后一个走的，在宿舍里一个人转悠了一个钟头，心里堵的慌，但脑子里是空的，脸上是木的。“毕业了，关好宿舍的门”，关什么阿，楼管阿姨还得进去收拾收拾呢。
到了家，蛋疼的时候想，为啥咱的毕业就这么土呢？可能是因为手机、E-mail到处都是，该联系的又没分开，毕业并没改变什么。多喝点酒，应该就有气氛了，就算不能放大感情，至少让人专心点感受毕业的气氛，而不会想以后还能联系这些混帐理由，这样才不会像个三流演员演戏那样一副欠打的样子。

这半年毕设做的马马虎虎，也学了些以后基本用不到的东西，而且知道了学校里面的实验室不都是那么正规的。

这段时间就忙着写论文编论文改论文了。要求是两万字左右——什么概念，原来的800字作文还要给你90分钟吧，然后老师提些建议“题目不好”“格式不对 ”“内容太少”，或者说“我很忙，没时间”。然后打印装订成册，上交。据说答辩完毕后统一销毁——估计差不多的，要不这种东西都留在图书馆作索引，要浪费很多资源的。现在才知道很多称之为论文的东西都是这样搞出来的，而且还在这样顺理成章的继续着。

毕设答辩还要过两天，又是个费心的活计。然后这半年的过渡就彻底结束了。

;3.19
;08/5/26

;设置两个指针first-man/second-man，一个一次走一步，另一个走两步，如果可以达到两者相等的状态说明有环存在；反之则无。
;这样空间消耗只需记录两个指针即可，而不用把环出现之前的所有节点都记录下来。
(define (cycle? x)
 
  (let ((first-man (if (pair? x)
                       (cdr x)
                       '())))
    (let ((second-man (if (or (null? first-man)
                              (not (pair? (cdr x))))
                          '()
                          (cdr (cdr x)))))
      (define (cycle-helper)
        (cond
          ((eq? first-man second-man) #t)
          ((and (pair? first-man)
                (pair? second-man))
           (begin (set! first-man (cdr first-man))
                  (set! second-man
                        (if (pair? (cdr second-man))
                            (cdr (cdr second-man))
                            '()))
                  (cycle-helper)))
         
          (else #f)))
      (cycle-helper))))

;与前面的count-pairs类似，不同之处在于不用考虑car了，只遍历cdr即可
;这样空间复杂度是O(n)的，因为要把环出现之前的节点全部保存在checked-list中
(define (cycle? x)
  (let ((checked-list '()))
  ;---already-in-list---
    (define (already-in-list? x the-list)
      (cond ((null? the-list) #f)
            ((eq? x (car the-list))
             #t)
            (else
             (already-in-list? x (cdr the-list)))))
    ;----checked-pair?----
    (define checked-pair?
      (lambda(x)
        (if (already-in-list? x checked-list)
            #t
            (begin (set! checked-list
                         (cons x checked-list))
                   #f))))
   
    (define (cycle-helper xx)
      (cond ((not (pair? xx)) #f)
            ((checked-pair? (car xx)) #t)
            (else (cycle-helper (cdr xx)))))
   
  (cycle-helper x)))

;3.17
;08/5/26
;checked-list要定义为count-pairs的内部变量，因为每一次count-pairs执行都要清空一次checked-list，否则就会出现第一次执行返回3，而第二次执行返回0的错误。
(define (count-pairs x)
  (let ((checked-list '()))
  ;---already-in-list---
    (define (already-in-list? x the-list)
      (cond ((null? the-list) #f)
            ((eq? x (car the-list))
             #t)
            (else
             (already-in-list? x (cdr the-list)))))
    ;----checked-pair?----
    (define checked-pair?
      (lambda(x)
        (if (already-in-list? x checked-list)
            #t
            (begin (set! checked-list
                         (cons x checked-list))
                   #f))))
   
    (define (count-helper xx)
      (cond ((not (pair? xx)) 0)
            ((checked-pair? xx) 0)
            (else (+ (count-helper (car xx))
                     (count-helper (cdr xx))
                     1))))
   (count-helper x)))

PS：做这道题的时候又遇到之前的一个问题，但是还是不知道怎样解释...

开始对“统计序对的个数”不太理解，后来认为题目的意思应该是把盒子指针图画出来以后其中“盒子”的数目。
这样Ben的count-pairs过程的bug就出在会把引用两次以上的同一个序对看做成多个。比如：
(define p3 (list 1 2 3))   ;3

(define temp4 (cons 1 2))
(define p4 (cons 0 (cons temp4 temp4))) ;4

(define temp7_1 (cons 1 2))
(define temp7_2 (cons temp7_1 temp7_1))
(define p7 (cons temp7_2 temp7_2))   ;7

(define temp0 (cons 1 2))
(set-cdr! temp0 temp0)
(define p0 (cons 1 (cons temp0 temp0)));死循环

讲完共享这一小节，明白了eq?和equal?的区别：eq?比较的是指针，而equal?是值。不过要说明的是共享基本符号时，如1，'a这些数字或者变量，eq?是不会区分的；但是如果x和y都指向了'(a b c)，(eq? x y)就是#f, 而(equal？ x y)就是#t。

本题见图：

(mystery x)返回的相当于原来的(reverse x)

题目中的v返回(a)，w返回(d c b a)
具体见图：（不同颜色指运行到不同阶段，顺序是红、蓝、绿、紫）