Scheme - 汎用演算のシステム(記号代数、多項式の算術演算、零、符号反転、減算、項リストの表現と濃さ)

計算機プログラムの構造と解釈
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.87、問題 2.88、問題 2.89を解いてみる。

その他参考書籍

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

問題 2.87

コード

sample.scm

;; 追加個所
;; 多項式のパッケージ
;; install-polynomial-package
  (define (=zero? p) (empty-termlist? p))
  (put '=zero? '(polynomial) =zero?)

問題 2.88

コード

sample.scm

;; 追加個所
;; 汎用符号反転演算
(define (negation x) (apply-generic 'negation x))

;; 多項式のパッケージ
;; install-polynomial-package
  (define (sub-poly p1 p2)
    (if (same-variable? (variable p1) (variable p2))
        (add-poly p1 (negation p2))
        (error "Polys no in same var -- SUB-POLY"
        (list p1 p2))))
  (define (negation-poly p)
    (make-poly (variable p)
               (mul-terms (term-list p)
                          (list (make-term 0 -1)))))

  (define (negation p)
    (make-poly (variable p) (map (lambda (term) (mul -1 term))
                                 (term-list p))))
  (put 'sub '(polynomial polynomial)
       (lambda (p1 p2) (tag (sub-poly p1 p2))))
  (put 'negation '(polynomial)
        (lambda (p) (tag (negation-poly p))))

問題 2.89

コード

sample.scm

;; 濃い多項式に適してる項リストの表現
;; install-dense-polynomial-package
  ;; 項と項リストの表現
  (define (adjoin-term term term-list))
  (define (the-empty-termlist) '())
  (define (first-term term-list)
    (make-term (- (length term-list) 1)
               (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))