関数型言語の勉強にSICPを読もう - (25) 2章 - データによる抽象の構築 (107ページ)

楽しい楽しい練習問題。

問題2.73 a

expのtype tagを取り出しそれに対応したderivを表から取り出しexpに作用させている。
number?variable?の部分に適用できないのはtype tagがないから。

問題2.73 b

deriv本体

type tagを利用して手続きを得る。
number?variable?も吸収したくなる。

(define (deriv exp var)
  (cond ((number? exp) 0)
        ((variable? exp) (if (same-variable? exp var) 1 0))
        (else ((get 'deriv (operator exp)) (operands exp) var))))

operator, operands

(define (operator exp)
  (car exp))

(define (operands exp)
  (cdr exp))

和の積分の手続き

(define (deriv-sum exp var)
  (make-sum
   (deriv (addend exp) var)
   (deriv (augend exp) var)))

積の積分の手続き

(define (deriv-product exp var)
  (make-sum
   (make-product (multiplier exp)
                 (deriv (multiplicand exp) var))
   (make-product (deriv (multiplier exp) var)
                 (multiplicand exp))))

補助プログラム

(define (install-deriv-package)
  (put 'deriv '+ deriv-sum)
  (put 'deriv '* deriv-product))

put,get

put, getは自分の処理系に合わせて自作しなければいけません。
今回は'derivという手続きしか登録しないという状況なのでGaucheに用意されているHash Tableを使います。(もちろん使ってみるのは初めて)
参照：Gauche ユーザリファレンス: 6.13 ハッシュテーブル
かなり強引ですがまあ良いでしょう。

(define deriv-table (make-hash-table))
(define (put op type item) ;; なんとopを無視するよ！
  (hash-table-put! deriv-table type item))

(define (get op type)
  (hash-table-get deriv-table type)) ;; 同じくopを無視

※次の問題できちんとしたput,getを実装済みです。hash-tableを入れ子にすれば簡単にできます。

動かしてみる

できた。
毎回 trace のためにあれこれ設定するのが面倒。
きっとうまい方法があると思うのだけどあとで調べよう。

(use slib)
(require 'trace)
(trace deriv)
(trace deriv-product)
(trace deriv-sum)
(trace augend)
(install-deriv-package)
(deriv '(+ x 3) 'x)
(+ 1 0)

問題2.73 c

deriv-expを用意

(define (deriv-exp exp var)
  (let ((a (base exp))
        (b (exponent exp)))
    (make-product
     (make-product b (make-exponent a (- b 1)))
     (deriv a var))))

install-deriv-exp-package作成

(define (install-deriv-exp-package)
  (put 'deriv '** deriv-exp))

実験

できた。
ポイントは既存のderiv手続きやそれが内包しているderiv-sumのコードを一切変更することなく手続きを動的に追加できること。

(trace deriv-exp)
(trace exponent)
(install-deriv-exp-package)
(deriv '(** x 2) 'x)

問題2.73 d

put,getの引数を逆にする。

これまで使ってきたとても少ない道具で一切の違和感なくこういうことができるのはとても面白い。

今年のGWはうまいことやると9連休になるらしいですね。(自分は違いますが)。
このチャンスにSICPを読み始めてみてはいかがでしょうか。

※「SICPを読もう」の目次はこちら

計算機プログラムの構造と解釈

posted with amazlet on 06.04.15

Gerald Jay Sussman Julie Sussman Harold Abelson 和田英一
ピアソンエデュケーション (2000/02)
売り上げランキング: 56,404

Amazon.co.jp で詳細を見る