[ 目次, 前節, 次節, 索引 ]

2.3.2 例: 記号微分



記号操作の実例とデータ抽象の更なる実例として, 代数式の記号微分を実行する手続きの設計を考えよう. 手続きは引数として代数式と変数をとり, 代数式のその変数に関する微分を返すものとしたい. 例えば, 手続きの引数がax2 + bx + cxなら, 手続きは2ax + bを返すものとする. 記号微分はLispには特別な歴史的重要性がある. それは記号操作用の計算機言語開発の背景にあった動機づけの例の一つであった. さらにそれは, 現在では絶えず増え続ける応用数学者や物理学者に使われる数式処理研究の強力なシステム開発に至る一連の研究の開始であった.

   記号微分プログラムの開発に際し, 2.1.1節の有理数システムの開発の時に採用したデータ抽象と同じ手法を採用しよう. つまりわれわれはまず「和」, 「積」や「変数」のような抽象オブジェクトに, それがどう表現されるかには心配せず, 操作する微分アルゴリズムを定義する. その後で表現の問題に向うことにする.

抽象データによる微分プログラム
ことを簡単にするため, 二つの引数を持った加算と乗算の演算だけからなる式を扱う, ごく単純な記号微分プログラムを考える. そういう式の微分は次の簡約規則を使うことで実行出来る:









   後の二つの規則は本来再帰的であることに注意しよう. つまり和の微分をとるには, まず項の微分を求め, それらを足す. 各項はまた分解が必要な式であるかも知れない. 段々と小さい部分に分解すると, 遂には定数か変数になり, その微分は0か1である.

   これらの規則を手続きに組み込むには, 有理数の実装の設計の時のように, 多少の 希望的思考をしなければならない. 代数式を表現する手段があれば, その式が和か積か定数か変数か分る必要がある. 式のその部分を取り出すことが出来なければならない. 例えば和については加数[addend](第一項)と被加数[augend](第二項)が取り出したい. また部品から式が構成出来なければならない. 次の選択子, 構成子と述語を実装した手続きは既にあると仮定しよう:

(variable? e)               eは変数か.
(same-variable? v1 v2)      v1とv2は同じ変数か.

(sum? e)                    eは和か.
(addend e)                  eの加数.
(augend e)                  eの被加数.
(make-sum a1 a2)            a1とa2の和を構成.

(product? e)                eは積か.
(multiplier e)              eの乗数.
(multiplicand e)            eの被乗数.
(make-product m1 m2)        m1とm2の積を構成.
これらと数を見分ける基本述語 number?を使うと, 次の手続きのように微分規則を表すことが出来る:

(define (deriv exp var)
  (cond ((number? exp) 0)
        ((variable? exp)
         (if (same-variable? exp var) 1 0))
        ((sum? exp)
         (make-sum (deriv (addend exp) var)
                   (deriv (augend exp) var)))
        ((product? exp)
         (make-sum
           (make-product (multiplier exp)
                         (deriv (multiplicand exp) var))
           (make-product (deriv (multiplier exp) var)
                         (multiplicand exp))))
        (else
         (error "unknown expression type -- DERIV" exp))))
このderiv手続きは完全な微分アルゴリズムを取り込んでいる. これは抽象データを使って表されているので, 正当な選択子と構成子を設計しさえすれば, 代数式の表現をどう選ぶかに無関係に働く. これが次に論ずべき点である.
代数式の表現
代数式を表現するのにリスト構造を使う方法をいくつも考えることが出来る. 例えば通常の代数記法を反映した記号のリストと使うことが出来, ax + bをリスト(a * x + b)と表現する. しかし特に直截な選択はLispが組合せに使うかっこによる前置記法と同じものを使うことである; つまりax + b(+ (* a x) b)と表現する. そうすると微分問題のデータ表現は次のようになる:

• 変数は記号とする. 基本手続き symbol?で識別出来る:

(define (variable? x) (symbol? x))
• 二つの変数はそれを表現している記号がeq?なら同じである:

(define (same-variable? v1 v2)
  (and (variable? v1) (variable? v2) (eq? v1 v2)))
• 和と積はリストとして構成する:

(define (make-sum a1 a2) (list '+ a1 a2))


(define (make-product m1 m2) (list '* m1 m2))
• 和は最初の要素が記号+であるリストである:

(define (sum? x)
  (and (pair? x) (eq? (car x) '+)))
• 加数は和のリストの第二項である:

(define (addend s) (cadr s))
• 被加数は和のリストの第三項である:

(define (augend s) (caddr s))
• 積は最初の要素が記号*であるリストである:

(define (product? x)
  (and (pair? x) (eq? (car x) '*)))
• 乗数は積のリストの第二項である:

(define (multiplier p) (cadr p))
• 被乗数は積のリストの第三項である:

(define (multiplicand p) (caddr p))
ところで, 動作する微分プログラムにするためには, derivのアルゴリズムとこれらを組み合せればよい. その振舞いの例を見よう.
(deriv '(+ x 3) 'x)
(+ 1 0)

(deriv '(* x y) 'x)
(+ (* x 0) (* 1 y))

(deriv '(* (* x y) (+ x 3)) 'x)
(+ (* (* x y) (+ 1 0))
   (* (+ (* x 0) (* 1 y))
     (+  x 3)))
このプログラムは正しい答を出す; しかし簡約化はしていない. 確かに



ではあるが, プログラムにx・0=0, 1・y=yそして0+y=yであることは知っていて欲しい. 第二の例は単にyであるべきだ. 第三の例で見るように, 式が複雑になると, これは重要な問題だ.

   この困難は有理数の実装で出会ったのとよく似ている: 答を最も簡単な形にまで簡約しなかった. 有理数の簡約化を実施するのに, 実装の構成子と選択子だけを変更する必要があった. ここでも似たような戦略をとろう. derivは変更したくない. そうではなく, make-sumを変更し, 両方の被演算子が数値なら, make-sumはそれらを足し, 和を返す. また被演算子の一方が0なら, make-sumはもう一方の被演算子を返す.


(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))))
これは式が与えられた数に等しいかを見る手続き =number?を使っている:

(define (=number? exp num)
  (and (number? exp) (= exp num)))
同様にmake-productを変更し, 0掛ける何かは0で, 1掛ける何かはそれ自身という規則を組み込もう:

(define (make-product m1 m2)
  (cond ((or (=number? m1 0) (=number? m2 0)) 0)
        ((=number? m1 1) m2)
        ((=number? m2 1) m1)
        ((and (number? m1) (number? m2)) (* m1 m2))
        (else (list '* m1 m2))))
先ほどの三つの例がどうなるか見よう.
(deriv '(+ x 3) 'x)
1

(deriv '(* x y) 'x)
y

(deriv '(* (* x y) (+ x 3)) 'x)
(+ (* x y) (* y (+ x 3)))
これはかなりの改善であるが第三の例は, われわれが「最簡だ」と賛成する形へ式を持っていくプログラムにするには, まだ長い道のりがあることを示している. 代数的単純化の問題は, いろいろな理由のうちでも, ある目的にとって最簡なのが, 他の目的にはそうでないということがあって, 複雑なのである.

問題 2.56


更に多くの形の式が扱えるように微分プログラムを拡張する方法を示せ. derivに新しい節を追加し, 例えば



の微分規則を, 適切な手続きexponentiation?, base, exponentおよびmake-exponentiationを定義して実装せよ. (べき乗を表すのに記号**を使おう.) 何かの0乗は1で, 何かの1乗はそれ自身という規則を組み込め.

問題 2.57


微分プログラムを拡張し, (2かそれを超える)任意個の項の和と積が扱えるようにせよ. 上の最後の例は
(deriv '(* x y (+ x 3)) 'x)
と表現出来る. 和と積の表現だけを変更し, derivの手続きは全く変更せずに試みよ. 例えば和のaddendは第一項, augendは残りの項の和とする.

問題 2.58


微分プログラムを修正し, 前置演算子でなく+*が中置きになっている通常の数学の式に動作させたいと思う. 微分のプログラムは抽象データを使って定義してあるので, 微分プログラムが操作する代数式の表現を定義する述語, 選択子, 構成子だけを変更するだけで, 式の別の表現形で動作するように出来る.

a. (x + (3 * (x + (y + 2))))のような中置き表現の代数式を微分するにはどうしたらよいかを示せ. 作業を単純にするため, +*は常に二つの項をとり, 式は完全にかっこで囲まれていると仮定せよ.

b. 不要なかっこは省き, 乗算は加算より前に行うと仮定する(x + 3 * (x + y + 2))のような, 標準の代数記法を許すと問題は実質的に難しくなる. われわれの微分プログラムが相変らず動作するように, この記法の適切な述語, 選択子, 構成子が設計出来るか.



[ 目次, 前節, 次節, 索引 ]