SICP 読書ノート#15 - 2.3 記号データ (pp.83-88)

「§2.3 記号データ」から。原文はSymbolic Data。

クォート

これまではデータは全て値だった。クォートするとそのデータをシンボルとしてみなすことができる。

'(a b c)と(list 'a 'b 'c)と(cons 'a (cons 'b (cons 'b nil)))は等価。
eq?とequal?の違い。JavaScriptの===と==みたいな感じ。

racket@> (eq? '(a b c) '(a b c))
#f

racket@> (equal? '(a b c) '(a b c))
#t

問題 2.55

racket@> (car ''hello)
'quote

は、なぜquoteを返すか？

うーん、わからない。

手を動かしてcarできるってことはcdrもできる？

racket@> (cdr ''hello)
'hello

それなら以下のlistによる式と等価？

racket@> (list 'quote 'hello)
''hello

おお。それなら、

racket@> '(quote hello)
''hello

も同じになる。ははん、なるほど。

つまり ''hello = '(quote hello) = (list 'quote 'hello)のため、 (car ''hello) の結果は'quoteとなる。

記号微分

代数式の記号微分を解く手続きを実装する。

問題 2.56

指数の微分演算を導入する。

(define (exponentiation? exp)
  (and (pair? exp) (eq? (car exp) '**)))

(define (make-exponentiation base exponent)
  (cond ((=number? exponent 0) 1)
        ((=number? exponent 1) base)
        (else (list '** base exponent))))

(define (base exp) (cadr exp))
(define (exponent exp) (caddr exp))

derivを拡張。

(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))))
        ;; ここに指数に対する演算を組み込む
        ((exponentiation? exp)
         (let ((b (base exp))
               (n (exponent exp)))
           (make-product
            (make-product n
                          (make-exponentiation b (- n 1)))
            (deriv b var))))
        (else
         (error "unknown expression type -- DERIV" exp))))

テスト。できてるっぽい。

racket@> (deriv '(** x 0) 'x)
0
racket@> (deriv '(** x 1) 'x)
1
racket@> (deriv '(** x 2) 'x)
'(* 2 x)
racket@> (deriv '(** x 3) 'x)
'(* 3 (** x 2))

問題 2.57

任意個の項の和や積が扱えるようにプログラムを拡張せよ。

例えば'(+ x y z)という3つの項を持つ式をzで微分しようとしても、

racket@> (require racket/trace)
racket@> (trace deriv)

racket@> (deriv '(+ x y z) 'z)
>(deriv '(+ x y z) 'z)
> (deriv 'x 'z)
< 0
> (deriv 'y 'z)
< 0
<0
0

と、2つの項しか扱えないため正解とならない。

テキストに「例えば和のaddendは第一項、augendは残りの項の和とする」とあるため、augendのみ

(define (augend s) 
  (if (= (length (cddr s)) 1)
      (caddr s)
      (cons '+ (cddr s))))

に変更すると、

racket@> (deriv '(+ x y z) 'z)
>(deriv '(+ x y z) 'z)
> (deriv 'x 'z)
< 0
> (deriv '(+ y z) 'z)
> >(deriv 'y 'z)
< <0
> >(deriv 'z 'z)
< <1
< 1
<1
1

上手く行った。

multiplicandも同じように修正。

(define (multiplicand p)
  (if (= (length (cddr p)) 1)
      (caddr p)
      (cons '* (cddr p))))

テスト。

racket@> (deriv '(* x y (+ x 3)) 'x)
>(deriv '(* x y (+ x 3)) 'x)
> (deriv '(* y (+ x 3)) 'x)
> >(deriv '(+ x 3) 'x)
> > (deriv 'x 'x)
< < 1
> > (deriv 3 'x)
< < 0
< <1
> >(deriv 'y 'x)
< <0
< 'y
> (deriv 'x 'x)
< 1
<'(+ (* x y) (* y (+ x 3)))
'(+ (* x y) (* y (+ x 3)))

OK。

問題 2.58

前置記法から中間記法に対応せよ。

まずはシンプルに'(x + y)を考えてみる。sumとaddendのみ書き換え。

(define (sum? x)
  (and (pair? x) (eq? (cadr x) '+)))

(define (addend s) (car s))

(define (augend s) (caddr s))

racket@> (deriv '(x + y) 'y)
>(deriv '(x + y) 'x)
> (deriv 'x 'y)
< 0
> (deriv 'y 'y)
< 1
<1
1

できた。

次に'(x + y + z)を考えてみる。augendを書き換え

(define (augend s)
  (if (= (length (cddr s)) 1)
      (caddr s)
      (cddr s)))

racket@> (deriv '(x + y + z) 'z)
>(deriv '(x + y + z) 'z)
> (deriv 'x 'z)
< 0
> (deriv '(y + z) 'z)
> >(deriv 'y 'z)
< <0
> >(deriv 'z 'z)
< <1
< 1
<1
1

できてるかな。

同じノリで乗算も実装。

(define (product? x)
  (and (pair? x) (eq? (cadr x) '*)))

(define (multiplier p) (car p))

(define (multiplicand p)
  (if (= (length (cddr p)) 1)
      (caddr p)
      (cddr p)))

racket@> (deriv '(x * y * z) 'z)
>(deriv '(x * y * z) 'z)
> (deriv '(y * z) 'z)
> >(deriv 'z 'z)
< <1
> >(deriv 'y 'z)
< <0
< 'y
> (deriv 'x 'z)
< 0
<'(* x y)
'(* x y)

こちらもできてそう。

テキストの式へも適用してみる。

racket@> (deriv '(x + 3 * (x + y + 2)) 'x)
>(deriv '(x + 3 * (x + y + 2)) 'x)
> (deriv 'x 'x)
< 1
> (deriv '(3 * (x + y + 2)) 'x)
> >(deriv '(x + y + 2) 'x)
> > (deriv 'x 'x)
< < 1
> > (deriv '(y + 2) 'x)
> > >(deriv 'y 'x)
< < <0
> > >(deriv 2 'x)
< < <0
< < 0
< <1
> >(deriv 3 'x)
< <0
< 3
<4
4

racket@> (deriv '(x + 3 * (x + y + 2)) 'y)
>(deriv '(x + 3 * (x + y + 2)) 'y)
> (deriv 'x 'y)
< 0
> (deriv '(3 * (x + y + 2)) 'y)
> >(deriv '(x + y + 2) 'y)
> > (deriv 'x 'y)
< < 0
> > (deriv '(y + 2) 'y)
> > >(deriv 'y 'y)
< < <1
> > >(deriv 2 'y)
< < <0
< < 1
< <1
> >(deriv 3 'y)
< <0
< 3
<3
3

racket@> (deriv '(x + 3 * (x + y + 2)) 'z)
>(deriv '(x + 3 * (x + y + 2)) 'z)
> (deriv 'x 'z)
< 0
> (deriv '(3 * (x + y + 2)) 'z)
> >(deriv '(x + y + 2) 'z)
> > (deriv 'x 'z)
< < 0
> > (deriv '(y + 2) 'z)
> > >(deriv 'y 'z)
< < <0
> > >(deriv 2 'z)
< < <0
< < 0
< <0
> >(deriv 3 'z)
< <0
< 0
<0
0