SICP 問題 2.58（中置記法での代数式に対する微分について）

問題

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

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

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

解答

a. について

前置記法から中置記法への変更だ。注意するのは、

・演算子の位置が変わったこと

・加算数、乗算数の位置が変わったこと

の２つ。自ずと述語、選択子、構成子を修正しないとね〜ってことは理解できる。
しかも問題を簡単にするために、一つの式に項は２つとまでお膳立てされてる。
この前提なら§2.3.2でまとめた内容をほんの少し修正すりゃいけるだろう。アレも２項が前提だったし。
こんな感じかねぇ？

;==============================
;和
;==============================
;述語
(define (sum? x)
  (and (pair? x)
       (eq? (cadr x) '+))) ;リストの中間を取り出して「+」と比較するように修正。

;選択子（加算数）
(define (addend s)
  (car s)) ;リストの先頭を取り出すように修正。

;選択子（被加算数）※変化なし
(define (augend s)
  (caddr s))

;構成子
(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 (product? x)
  (and (pair? x)
       (eq? (cadr x) '*))) ;リストの中間を取り出して「*」と比較するように修正。

;選択子（乗算数）
(define (multiplier p)
  (car p)) ;リストの先頭を取り出すように修正。

;選択子（被乗算数）※変化なし
(define (multiplicand p)
  (caddr p))

;構成子
(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)))) ;「*」がリストの中央にくるように修正。

では実験。

gosh> (deriv '(x + (3 * (x + (y + 2)))) 'x)

4

gosh> (deriv '(x + (3 * ((x * x) + (y + 2)))) 'x)

(1 + (3 * (x + x)))

gosh> (deriv '(x + (3 * ((x * x) + (x * (y + 2))))) 'x)

(1 + (3 * ((x + x) + (y + 2))))

gosh> 

いいね〜。

b. について

すんごいデバッグに時間かかっちゃったよオイ。

この問題、当初は「無理なんじゃね？」と思っていたんだが、ちょっと考えてたらできそうな感じがしたのでやってみた。

述語、選択子、構成子を考えるために具体例で考えていってみる。

(x * y * z + 3 * x + (x * x) * 4) 

で考えてみよう。まずは述語。
対象とする式（リスト）の中の「要素」に、「+」が発見されたら加算式と判断する。
（要素ってのは、数値、シンボル（+ とか *）、リスト（ネストされた式）とする。）
この述語だと、先頭から6番目の要素の + が判定式にヒットする。
で、この式に対して選択子を摘要すると、こんな風に抽出されればOK。

　　　

addend（加算数）  適用 → (x * y * z)

augend（被加算数）適用 → (3 * x + (x * x) * 4)

では実装してみよう。
ちなみにおかしなフォーマットの式（例えば演算子が連続して出現するとか）への対応とかは一切なしw
memq手続きを使ってザクザクやっちゃう。

;述語
(define (sum? x)
  (if (eq? #f (memq '+ x))
      #f
      #t))

;選択子（加算数）
(define (addend x)
  ;最初に「+」を確認するまでの先頭側のリストを抽出する手続き
  (define (loop head tail)
    (cond ((null? tail)	(reverse head))
	  ((eq? '+ (car tail)) (reverse head))
	  (else 
	   (loop (cons (car tail) head)
		 (cdr tail)))))
  ;上記内部定義手続きを使って適切な加算数を返却。
  ;（※要素がひとつだけだった場合は、リストでなく要素だけを返却）
  ;この考え↑が抜けててうまくいかず、えらい苦労した。。
  (let ((ans (loop '() x)))
    (if (eq? 1 (length ans))
	(car ans)
	ans)))
		      
		   

;選択子（被加算数）
(define (augend x)
  (let ((ans (cdr (memq '+ x))))
    (if (eq? 1 (length ans))
	(car ans)
	ans)))


;構成子は a. の構成子をそのまま使えるハズ。

さて実験。

gosh> (sum? '(x * y * z * 3 * x * (x * x) * 4))

#f

gosh> (sum? '(x * y * z + 3 * x + (x * x) * 4))

#t

gosh> (sum? '(x * y * z * 3 * x + (x * x) * 4))

#t

gosh> (addend '(x * y * z + 3 * x + (x * x) * 4))

(x * y * z)

gosh> (augend '(x * y * z + 3 * x + (x * x) * 4))

(3 * x + (x * x) * 4)

gosh> 

いいね〜。次！積について！

乗算は全ての項が * で連結されていないとならない。ひとつでも + が存在したらそれはもう和算とみなされないと、一般の代数式じゃねぇ。
なので、次のような式に対して述語 product? を適用した場合は #f が返却されないとダメ。

(x * y * z + 3 * x + (x * x) * 4) 

#tが返却されるのは次の様な、要素が全て * で連結されているような式。

(x * y * z * 3 * x * (x * x) * 4)

この式に対して、選択子を適用すると、こんな風に取れるとうれしい感じ。

　　　

multiplier　（乗算数）  適用 → x

multiplicand（被乗算数）適用 → (y * z * 3 * x * (x * x) * 4)

じゃ、実際に実装してみよう。

;==============================
;積
;==============================
;述語
(define (product? x)
  (cond ((pair? (memq '+ x)) #f)
	((pair? (memq '* x)) #t)
	(else #f)))


;選択子（乗算数）
(define (multiplier p)
  (car p))

;選択子（被乗算数）
(define (multiplicand p)
  (let ((ans (cdr (memq '* p))))
    (if (eq? 1 (length ans))
	(car ans)
	ans)))

では確認。

gosh> (product? '(x * y * z + 3 * x + (x * x) * 4))

#f

gosh> (product? '(x * y * z * 3 * x + (x * x) * 4))

#f

gosh> (product? '(x * y * z * 3 * x * (x * x) * 4))

#t

gosh> (multiplier '(x * y * z * 3 * x * (x * x) * 4))

x

gosh> (multiplicand '(x * y * z * 3 * x * (x * x) * 4))

(y * z * 3 * x * (x * x) * 4)

gosh> 

よしよし。じゃ、これで微分をやってみよう！

gosh> (deriv '(x + (3 * ((x * x) + (x * (y + 2))))) 'x)

(1 + (3 * ((x + x) + (y + 2))))

gosh> 

おっしゃ！a.と同じ結果になった！

つーわけで、答えは「できる」！