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.4(抽象データの多重表現)、2.4.3(データ主導プログラミングと加法性)の問題 2.73を解いてみる。

その他参考書籍

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

問題 2.73

a.

やったことは、演算(derive)対型(+, *)というテーブルを使用したデータ主導プログラミングにしていて、テーブルから対応する手続きを取得し実行している。

	+	*
deriv	deriv-sum	deriv-product

述語number?やvariable?がデータ主導の振り分けに吸収できないのは、数値や変数がリストではないので、手続きoperatorやoperandsを適用できないから。

b, c.

コード

sample.scm

;; 和の微分
(define (install-sum-package)
  ;; 内部手続き
  (define (inner-deriv exp var)
    (make-sum (deriv (addend exp) var)
              (deriv (augend exp) var)))
  (define (addend exp) (cadr exp))
  (define (augend exp) (caddr exp))
  (define (make-sum a1 a2)
    (cond ((=number? a1 0) a2)
          ((=number? a2 0) a1)
          ((and (number? a1) (number? a2)) (+ a1 a2))
          (else (list '+ a1 a2))))
  (define (=number? exp num)
    (and (number? exp) (= exp num)))
    
  ;; システムの他の部分とのインターフェース
  (put 'deriv '+ inner-deriv)
  'done)

;; 積の微分
(define (install-product-package)
  ;; 内部手続き
  (define (inner-deriv exp var)
    (make-sum
      (make-product (multiplier exp)
                    (deriv (multiplicand exp) var))
      (make-product (deriv (multiplier exp) var)
                    (multiplicand exp))))
  (define (multiplier exp) (car (operands exp)))
  (define (multiplicand exp) (cadr (operands exp)))
  (define (make-product m1 m2)
    (cond ((or (=number? m1 0) (=number? v2 0)) 0)
          ((=number? m1 1) m2)
          ((=number? m2 1) m1)
          ((and (number? m1) (number? m2)) (* m1 m2))
          (else (list '* m1 m2))))
  (define (=number? exp num)
    (and (number? exp) (= exp num)))

  ;; システムの他の部分とのインターフェース
  (put 'deriv '* inner-deriv)
  'done)

;; べき乗の微分
(define (install-expt-pakcage)
  ;; 内部手続き
  (define (inner-deriv exp var)
    (let ((n (exponent exp))
          (u (base exp)))
      (* n
         (make-exponentitation u (- n 1))
         (deriv u var))))
  (define (base x) (cadr x))
  (define (exponent x) (caddr x))
  (define (make-exponentiaton a b)
    (cond ((=number? b 0) 1)
          ((=number? b 1) a)
          ((and (number? a) (number? b)) (expt a b))
          (else (list '** a b))))
  (define (=number? exp num)
    (and (number? exp) (= exp num)))

  ;; システムの他の部分とのインターフェース
  (put 'deriv '** inner-deriv)
  'done)

d.

各微分のパッケージの表を操作する手続きputの第1引数、第2引数の順序を入れ替える、つまり、次のように変更すればいい。

コード

sample.scm

;; 式の型を、結合している代数演算ではなく、derivにした場合の微分システム

;; 和の微分
(define (install-sum-package)
　;; 内部手続きは同じなので省略
  ;; システムの他の部分とのインターフェース
  (put '+ 'deriv inner-deriv)
  'done)

;; 積の微分
(define (install-product-package)
　;; 内部手続きは同じなので省略
  ;; システムの他の部分とのインターフェース
  (put '* 'deriv inner-deriv)
  'done)

;; べき乗の微分
(define (install-expt-pakcage)
　;; 内部手続きは同じなので省略
  ;; システムの他の部分とのインターフェース
  (put '** 'deriv inner-deriv)
  'done)

パッケージを呼び出して出来上がるテーブル。

	deriv
+	deriv-sum
*	deriv-product
**	deriv-expt