Scheme - 記号代数(多項式のGCD(greatest common divisor、最大公約数)と非整数演算、整数化因子と擬除算、擬剰余)

計算機プログラムの構造と解釈
Gerald Jay Sussman, Julie Sussman
Harold Abelson (原著) 和田 英一 (翻訳)

開発環境

• OS X Lion - Apple(OS)
• Emacs、BBEdit - Bare Bones Software, Inc. (Text Editor)
• プログラミング言語: MIT/GNU Scheme

計算機プログラムの構造と解釈(Gerald Jay Sussman(原著)、Julie Sussman(原著)、Harold Abelson(原著)、和田 英一(翻訳)、ピアソンエデュケーション、原書: Structure and Interpretation of Computer Programs (MIT Electrical Engineering and Computer Science)(SICP))の2(データによる抽象の構築)、2.5(汎用演算のシステム)、2.5.3(例: 記号代数)、拡張問題: 有理関数の問題 2.95、問題 2.96を解いてみる。

その他参考書籍

• Instructor's Manual to Accompany Structure & Interpretation of Computer Programs

問題 2.95

コード(BBEdit)

sample.scm

(define p1 (make-polynomial 'x '((2 1) (1 -2) (0 1))))
(define p2 (make-polynomial 'x '((2 11) (0 7))))
(define p3 (make-polynomial 'x '((1 13) '(0 5))))

(define q1 (mul p1 p2))
(define q2 (mul p1 p3))

(define gcd-of-q1-q2 (greatest-common-divisor q1 q2))

問題 2.96

a.

コード(BBEdit)

sample.scm

;; install-terms-package
  ;; システムの内部手続き
  (define (gcd-terms a b)
    (if (empty-termlist? b)
        a
        (gcd-terms b (pseudoremainder-terms a b))))
  (define (pseudoremainder-terms a b)
    (let ((o1 (caar a))
          (o2 (caar b))
          (c (cadr b)))
      (cadr (div-terms (mul (expt c (- (+ 1 o1)
                                       o2))
                            p1)
                       p2))))
  
  ;; システムの他の部分とのインターフェース
  (put 'remainder '(term-list term-list)
       (lambda (a b) (tag (pseudoremainderr-terms a b))))

b.

コード(BBEdit)

sample.scm

;; install-terms-package
  ;; システムの内部手続き
  (define (gcd-terms a b)
    (define (iter terms result)
      (if (null? terms)
          result
          (let ((t (car terms)))
            (let ((c (coeff t)))
              (iter (cdr terms) (gcd result c))))))
    (if (empty-termlist? b)
        (let ((n (numer a))
              (d (denom a)))
          (let ((g (iter (append n (cdr d)) (car d))))
            (make-rat (div n g) (div d g))))
        (gcd-terms b (pseudoremainder-terms a b))))

入出力結果(REPL)で確認できあない状態が続いてるから、解答がどんどん微妙になってきてる気がする。。ただ、もうちょっと先にputとgetの定義の仕方が出てくるみたいなので、それを憶えてから2周目に本書を取り組む時に、いろいろと確認してみることに。今は本書の全体像を掴むために、正確さよりも一歩一歩先に進めることを優先。