SICPゼミ第40回

2章はやばいので4章に帰ってきました。

練習問題4.2

applicaionかどうかの判定 (application?) はタグを気にせずペアかどうかしか見ていない.これが最後でないと (define …) みたいなのも適用として扱ってしまうのでおかしくなる. call を使うことにするのであれば,ほかのやつと同じように,callというタグが付いてると思って扱えばよい.

by dolicas

練習問題4.3

(define (eval exp env)
  (if (self-evaluating? exp)
    exp
    (if (get 'eval (get-tag exp))
      ((get 'eval (get-tag exp)) (get-content exp) env)
      (apply (eval (operator exp) env) (list-of-values (operands exp) env)) 
    )
  ))
(define (get-tag exp)
  (car exp))
(define (get-content exp) (cdr exp))

by dolicas

SICPゼミ第38回

練習問題2.91

(define (install-polynomial-package)
  ;; 内部手続き
  ;; poly の表現
  (define (make-poly variable term-list) (cons variable term-list ))
  (define (variable p) (car p))
  (define (term-list p) (cdr p))
  (define same-variable? eq?)
  (define variable? symbol?)
  ;; 項と項リストの表現
  (define (add-poly p1 p2)
    (if (same-variable? (variable p1) (variable p2))
        (make-poly (variable p1)
                   (add-terms (term-list p1) (term-list p2)))
        (error "Polys not in same var: ADD-POLY" (list p1 p2))))
  (define (add-terms L1 L2)
    (cond (( empty-termlist? L1) L2)
          (( empty-termlist? L2) L1)
          (else
           (let ((t1 (first-term L1))
                 (t2 (first-term L2)))
             (cond ((> (order t1) (order t2))
                    (adjoin-term
                     t1 (add-terms (rest-terms L1) L2)))
                   ((< (order t1) (order t2))
                    (adjoin-term
                     t2 (add-terms L1 (rest-terms L2))))
                   (else
                      (adjoin-term
                     (make-term (order t1)
                                (add (coeff t1) (coeff t2)))
                     (add-terms (rest-terms L1)
                                (rest-terms L2 )))))))))
  (define (inversion termList)
    (if (empty-termlist? termList)
        termList
        (let ((term (first-term termList)))
          (if (eq? (type-tag term) 'polynomial)
              (adjoin-term
               (make-term (order term)
                          (inversion (coeff term)))
               (inversion (rest-terms termList)))
              (adjoin-term
               (make-term (order term)
                          (mul (make-scheme-number -1) (coeff term)))
               (inversion (rest-terms termList)))))))
  (define (mul-poly p1 p2)
    (if (same-variable? (variable p1) (variable p2))
        (make-poly (variable p1)
                   (mul-terms (term-list p1) (term-list p2)))
        (error "Polys not in same var: MUL-POLY" (list p1 p2))))
  (define (mul-terms L1 L2)
    (if (empty-termlist? L1)
        (the-empty-termlist)
        (add-terms (mul-term-by-all-terms (first-term L1) L2)
                   (mul-terms (rest-terms L1) L2))))
  (define (mul-term-by-all-terms t1 L)
    (if (empty-termlist? L)
        (the-empty-termlist)
        (let ((t2 (first-term L)))
          (adjoin-term
           (make-term (+ (order t1) (order t2))
                      (mul (coeff t1) (coeff t2)))
           (mul-term-by-all-terms t1 (rest-terms L))))))
  (define (adjoin-term term term-list)
    (if (=zero? (coeff term ))
        term-list
        (cons term term-list )))
  (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 ((rest-of-result
                       (let ((rest (add-terms L1
                                              (inversion
                                               (mul-terms L2 (list (make-term new-o new-c)))))))
                         (div-terms rest L2))))
                  (cons (adjoin-term (make-term new-o new-c)
                                     (car rest-of-result))
                        (cdr rest-of-result))
                  ))))))
  (define (div-poly p1 p2)
     (if (same-variable? (variable p1) (variable p2))
        (make-poly (variable p1)
                   (div-terms (term-list p1) (term-list p2)))
        (error "Polys not in same var: ADD-POLY" (list p1 p2))))
(define (the-empty-termlist) '())
(define (first-term term-list) (car term-list ))
(define (rest-terms term-list) (cdr term-list ))
(define (empty-termlist? term-list) (null? term-list ))
(define (make-term order coeff) (list order coeff ))
(define (order term) (car term ))
(define (coeff term) (cadr term ))
  ;; システムのほかの部分とのインターフェイス
  (define (tag p) (attach-tag 'polynomial p))
  (put 'add '(polynomial polynomial)
       (lambda (p1 p2) (tag (add-poly p1 p2))))
  (put 'mul '(polynomial polynomial)
       (lambda (p1 p2) (tag (mul-poly p1 p2))))
  (put 'make 'polynomial
       (lambda (var terms) (tag (make-poly var terms ))))
  (put 'div '(polynomial polynomial)
       (lambda (p1 p2) (tag (div-poly p1 p2))))
  'done)

by tube

SICPゼミ第37回

練習問題2.88

install-polynomial-package内に以下の関数を追加する。

(define (inversion termList)
  (if (empty-termlist? termList)
      termList
      (let ((term (first-term termList)))
        (if (eq? (type-tag term) 'polynomial)
            (adjoin-term
              (make-term (order term)
                         (inversion (coeff term)))
              (inversion (rest-terms termList)))
            (adjoin-term
              (make-term (order term)
                         (mul (make-scheme-number -1) (coeff term)))
              (inversion (rest-terms termList)))))))

by pine

練習問題2.89

(define (install-polynomial-dense-package)
  ;; 内部手続き
  ;; poly の表現
  (define (make-poly variable term-list) (cons variable term-list ))
  (define (variable p) (car p))
  (define (term-list p) (cdr p))
  (define same-variable? eq?)
  (define variable? symbol?)
  ;; 項と項リストの表現
  (define (add-poly p1 p2)
    (if (same-variable? (variable p1) (variable p2))
        (make-poly (variable p1)
                   (add-terms (term-list p1) (term-list p2)))
        (error "Polys not in same var: ADD-POLY" (list p1 p2))))
  (define (add-terms L1 L2)
    (cond (( empty-termlist? L1) L2)
          (( empty-termlist? L2) L1)
          (else
            (let ((t1 (first-term L1))
                  (t2 (first-term L2)))
              (cond ((> (order t1) (order t2))
                     (adjoin-term
                       t1 (add-terms (rest-terms L1) L2)))
                    ((< (order t1) (order t2))
                     (adjoin-term
                       t2 (add-terms L1 (rest-terms L2))))
                    (else
                      (adjoin-term
                        (make-term (order t1)
                                   (add (coeff t1) (coeff t2)))
                        (add-terms (rest-terms L1)
                                   (rest-terms L2 )))))))))
  (define (inversion termList)
    (if (empty-termlist? termList)
        termList
        (let ((term (first-term termList)))
          (if (eq? (type-tag term) 'polynomial)
              (adjoin-term
                (make-term (order term)
                           (inversion (coeff term)))
                (inversion (rest-terms termList)))
              (adjoin-term
                (make-term (order term)
                           (mul (make-scheme-number -1) (coeff term)))
                (inversion (rest-terms termList)))))))
  (define (mul-poly p1 p2)
    (if (same-variable? (variable p1) (variable p2))
        (make-poly (variable p1)
                   (mul-terms (term-list p1) (term-list p2)))
        (error "Polys not in same var: MUL-POLY" (list p1 p2))))
  (define (mul-terms L1 L2)
    (if (empty-termlist? L1)
        (the-empty-termlist)
        (add-terms (mul-term-by-all-terms (first-term L1) L2)
                   (mul-terms (rest-terms L1) L2))))
  (define (mul-term-by-all-terms t1 L)
    (if (empty-termlist? L)
        (the-empty-termlist)
        (let ((t2 (first-term L)))
          (adjoin-term
            (make-term (+ (order t1) (order t2))
                       (mul (coeff t1) (coeff t2)))
            (mul-term-by-all-terms t1 (rest-terms L))))))
  (define (adjoin-term term term-list)
    (if (=zero? (coeff term ))
        term-list
        (cons (coeff term) term-list )))
  (define (the-empty-termlist) '())
  (define (first-term term-list) term-list)
  (define (rest-terms term-list) (cdr term-list ))
  (define (empty-termlist? term-list) (null? term-list ))
  (define (make-term order coeff) (list order coeff ))
  (define (order term) (- (length term) 1)
  (define (coeff term) (car term ))  
  ;; システムのほかの部分とのインターフェイス
  (define (tag p) (attach-tag 'polynomial p))
  (put 'add '(polynomial polynomial)
       (lambda (p1 p2) (tag (add-poly p1 p2))))
  (put 'mul '(polynomial polynomial)
       (lambda (p1 p2) (tag (mul-poly p1 p2))))
  (put 'make 'polynomial
       (lambda (var terms) (tag (make-poly var terms ))))
  'done)

練習問題2.90

(install (dense-term-package)
  (put 'coeff 'term coeff-dense)
  ;他の関数もがんばる
  ;後で名前が衝突するので、2.89のはdenseとかつける
  )

(install (sparse-term-package)
  ;同上
    )
(install (term-package)
  ;上の2つをinstall
  (define (coeff term) (apply-generic 'coeff term))
  ;他の関数もがんばる。
  )

SICPゼミ第36回

練習問題2.78からやり直し

練習問題2.78

(define (attach-tag type-tag contents)
  (if (eq? type-tag 'scheme-number)
      contents
      (cons type-tag contents )))
(define (type-tag datum)
  (if (pair? datum)
      (car datum)
      (if (number? datum)
          'scheme-number
          (error "Bad tagged datum: TYPE-TAG" datum ))))
(define (contents datum)
  (if (pair? datum)
      (cdr datum)
      (if (number? datum)
          datum
          (error "Bad tagged datum: CONTENTS" datum ))))
続きを読む

SICPゼミ第35回

練習問題2.82

例えば引数が長方形と菱形と正方形であるときを考えると、全ての引数を平行四辺形に強制型変換しなければならないが、各引数の型へと変換しようとする限り、平行四辺形にはたどり着かない。つまり、型の関係において分岐が生じており、その分岐の葉にあたる型のみが引数として与えられたときにうまく動かないと考えられる。
by tube

練習問題2.83
(define (integer->rational n)
  (make-rational (contents n) 1))

(define (rational->scheme-number n)
  (let ((nu (car (contents n)))
        (de (cdr (contents n))))
    (make-scheme-number (/ nu de))))

(define (scheme-number->complex n)
  (make-complex-from-real-imag (contents n) 0))

ジェネリックなraiseは適当にputして適当にgetすればいい。

練習問題2.84

一つ目の型をraiseを使ってあげていく。二つ目の型と一致したらOK。一致するまえに一番上に行く(raiseがエラーを返す)ときは、二つ目の型をあげていく。

練習問題2.85

一度projectをしてからraiseをして、元の値と比較することで、情報落ちがないかを確認するというdropの手続きを実装せよという問題だが、端的に言ってこの問題で要求されている処理には無駄が大きいと言わざるを得ない。
projectの実装は当然project前後の型に依存しており、projectの動作を記述する際に、projectによって情報落ちが発生するかの判定を組み込むことは容易に可能である。
これにも関わらず、projectの段階で情報落ちの判定をせずに、dropの処理の段階に情報落ちの判定を分割することは明らかに無駄であり、不要な処理を記述することになってしまう。
以上より、dropの実装は省略する。

練習問題2.86

複素数パッケージの内部手続きの演算(+とか*とか)をジェネリック演算にする。
sine、cosineは実数に型変換してつっこむ。

SICPゼミ第34回

2章に帰ってきました。

put, get など

(define (key-compare a b) 0)
(define (make-table)
  (let (( local-table (list '*table* )))
    (define (lookup key-1 key-2)
      (let (( subtable
              (assoc key-1 (cdr local-table ))))
        (if subtable
            (let (( record
                    (assoc key-2 (cdr subtable ))))
              (if record (cdr record) false ))
            false )))
    (define (insert! key-1 key-2 value)
      (let (( subtable
              (assoc key-1 (cdr local-table ))))
        (if subtable
            (let (( record
                    (assoc key-2 (cdr subtable ))))
              (if record
                  (set-cdr! record value)
                  (set-cdr! subtable
                            (cons (cons key-2 value)
                                  (cdr subtable )))))
            (set-cdr! local-table
                      (cons (list key-1 (cons key-2 value ))
                            (cdr local-table )))))
      'ok)
    (define (dispatch m)
      (cond ((eq? m 'lookup-proc) lookup)
            ((eq? m 'insert-proc!) insert!)
            (else (error "Unknown operation: TABLE" m))))
    dispatch ))

(define operation-table (make-table ))
(define get (operation-table 'lookup-proc ))
(define put (operation-table 'insert-proc! ))

(define (attach-tag type-tag contents)
  (cons type-tag contents ))

(define (type-tag datum)
  (if (pair? datum)
      (car datum)
      (error "Bad tagged datum: TYPE-TAG" datum )))

(define (contents datum)
  (if (pair? datum)
      (cdr datum)
      (error "Bad tagged datum: CONTENTS" datum )))


(define (apply-generic op . args)
  (let (( type-tags (map type-tag args )))
    (let ((proc (get op type-tags )))
      (if proc
          (apply proc (map contents args))
          (error
           "No method for these types: APPLY-GENERIC"
           (list op type-tags ))))))

(define (add x y) (apply-generic 'add x y))
(define (sub x y) (apply-generic 'sub x y))
(define (mul x y) (apply-generic 'mul x y))
(define (div x y) (apply-generic 'div x y))

(define (install-scheme-number-package)
  (define (tag x) (attach-tag 'scheme-number x))
  (put 'add '(scheme-number scheme-number)
       (lambda (x y) (tag (+ x y))))
  (put 'sub '(scheme-number scheme-number)
       (lambda (x y) (tag (- x y))))
  (put 'mul '(scheme-number scheme-number)
       (lambda (x y) (tag (* x y))))
  (put 'div '(scheme-number scheme-number)
       (lambda (x y) (tag (/ x y))))
  (put 'make 'scheme-number (lambda (x) (tag x)))
  'done)

(define (install-rational-package)
  ;; 内部手続き
  (define (numer x) (car x))
  (define (denom x) (cdr x))
  (define (make-rat n d)
    (let ((g (gcd n d)))
      (cons (/ n g) (/ d g))))
  (define (add-rat x y)
    (make-rat (+ (* (numer x) (denom y))
                 (* (numer y) (denom x)))
              (* (denom x) (denom y))))
  (define (sub-rat x y)
    (make-rat (- (* (numer x) (denom y))
                 (* (numer y) (denom x)))
              (* (denom x) (denom y))))
  (define (mul-rat x y)
    (make-rat (* (numer x) (numer y))
              (* (denom x) (denom y))))
  (define (div-rat x y)
    (make-rat (* (numer x) (denom y))
              (* (denom x) (numer y))))
  ;; システムのほかの部分とのインターフェイス
  (define (tag x) (attach-tag 'rational x))
  (put 'add '(rational rational)
       (lambda (x y) (tag (add-rat x y))))
  (put 'sub '(rational rational)
       (lambda (x y) (tag (sub-rat x y))))
  (put 'mul '(rational rational)
       (lambda (x y) (tag (mul-rat x y))))
  (put 'div '(rational rational)
       (lambda (x y) (tag (div-rat x y))))
  (put 'make 'rational
       (lambda (n d) (tag (make-rat n d))))
  'done)
(define (make-rational n d)
  ((get 'make 'rational) n d))



(define (install-complex-package)
  ;; 直交形式パッケージと極形式パッケージからインポートした手続き
  (define (make-from-real-imag x y)
    204
    ((get 'make-from-real-imag 'rectangular) x y))
  (define (make-from-mag-ang r a)
    ((get 'make-from-mag-ang 'polar) r a))
  ;; 内部手続き
  (define (add-complex z1 z2)
    (make-from-real-imag (+ (real-part z1) (real-part z2))
                         (+ (imag-part z1) (imag-part z2))))
  (define (sub-complex z1 z2)
    (make-from-real-imag (- (real-part z1) (real-part z2))
                         (- (imag-part z1) (imag-part z2))))
  (define (mul-complex z1 z2)
    (make-from-mag-ang (* (magnitude z1) (magnitude z2))
                       (+ (angle z1) (angle z2))))
  (define (div-complex z1 z2)
    (make-from-mag-ang (/ (magnitude z1) (magnitude z2))
                       (- (angle z1) (angle z2))))
  ;; システムのほかの部分とのインターフェイス
  (define (tag z) (attach-tag 'complex z))
  (put 'add '(complex complex)
       (lambda (z1 z2) (tag (add-complex z1 z2))))
  (put 'sub '(complex complex)
       (lambda (z1 z2) (tag (sub-complex z1 z2))))
  (put 'mul '(complex complex)
       (lambda (z1 z2) (tag (mul-complex z1 z2))))
  (put 'div '(complex complex)
       (lambda (z1 z2) (tag (div-complex z1 z2))))
  (put 'make-from-real-imag 'complex
       (lambda (x y) (tag (make-from-real-imag x y))))
  (put 'make-from-mag-ang 'complex
       (lambda (r a) (tag (make-from-mag-ang r a))))
  'done)

by tube

練習問題2.81

ちなみに put-coercion, get-coercion は新しいテーブルを持てばいいので

(define coercion-table (make-table ))
(define get-coercion (coercion-table 'lookup-proc ))
(define put-coercion (coercion-table 'insert-proc! ))

a.
型変換メソッドが存在し続ける、つまり apply-generic 内にある cond 条件文の else 節に入らないため、無限ループがおきる。

b.
そのままで動く。

c.

(define (apply-generic op . args)
  (let (( type-tags (map type-tag args )))
    (let ((proc (get op type-tags )))
      (if proc
          (apply proc (map contents args))
          (if (= (length args) 2)
              (let (( type1 (car type-tags ))
                    (type2 (cadr type-tags ))
                    (a1 (car args ))
                    (a2 (cadr args )))
                (if (equal? type1 type2)
                    (error "No method for these types")
                (let (( t1->t2 (get-coercion type1 type2 ))
                      (t2->t1 (get-coercion type2 type1 )))
                  (cond (t1->t2
                         (apply-generic op (t1->t2 a1) a2))
                        (t2->t1
                         (apply-generic op a1 (t2->t1 a2)))
                        (else (error "No method for these types"
                                     (list op type-tags )))))))
              (error "No method for these types"
                     (list op type-tags )))))))