読者です 読者をやめる 読者になる 読者になる

kb84tkhrのブログ

何を書こうか考え中です

Scheme手習い (8) 表現と抽象化

基本的な再帰の練習は5章までで終わり
第6章「影法師」からは応用編といった感じ
6章では算術式を題材にして表現と抽象化を学びます

算術式をschemeで取り扱うためにS式で表したものを算術式の表現と呼びます
まずは単純に、n + 3を(n + 3)と表現します
ということは1 + 2 + 3の表現は(1 + 2 + 3)かと思ったらハズレ

ここでは「2つの(数を含む)アトムか算術式を+か*か^で結合したもの」を算術式と呼んでます
算術式の定義に算術式が出てきますので再帰的定義ですね
こういうのが後から出てくるのがこの本の特徴

1 + 2 + 3は算術式1 + 2と算術式3を+で結合したものか、
または算術式1と算術式2 + 3を+で結合したものとみなせるので
その表現は((1 + 2) + 3)(1 + (2 + 3))のどちらかになります

右から結合とか左から結合とかは決まっていないようなので
元の式がどちらかの意味なのかはわかりませんが
表現になっているものは必ずそれぞれの算術式がカッコで囲まれるためあいまいさはありません

まずは算術式が数からのみなる式かどうかを判別するnumbered?を考えます
この関数の定義域は算術式
この本では定義的に入らない入力についてはたいていなんの考慮もされません
そのことがわかっていないと穴埋めもできなかったりします

(define numbered?
  (lambda (aexp)
    (cond ((atom? aexp) (number? aexp))
          ((eq? (car (cdr aexp)) (quote +))
           (and (numbered? (car aexp)) (numbered? (car (cdr (cdr aexp))))))
          ((eq? (car (cdr aexp)) (quote *))
           (and (numbered? (car aexp)) (numbered? (car (cdr (cdr aexp))))))
          ((eq? (car (cdr aexp)) (quote ^))
           (and (numbered? (car aexp)) (numbered? (car (cdr (cdr aexp)))))))))

定義を忠実になぞってる感じですね

演算子のところが'-'だったらどうするの?
aexpに4つめの要素があったら?
そんな入力は存在しないのです

ちゃんとした算術式であることをアテにできるのならもっと短く書けます

(define numbered?
  (lambda (aexp)
    (cond ((atom? aexp) (number? aexp))
          (else (and (numbered? (car aexp))
                     (numbered? (car (cdr (cdr aexp)))))))))

なぜ簡単化ができるのでしょうか。
関数を正しく把握してきたと知っているからです。

そんなもんですかね
ちょっとピンときません

次は算術式の値を求めます
今度の定義域は、numbered?である算術式
構造は(最初の)numbered?とまったく同じ

(define value
  (lambda (aexp)
    (cond ((atom? aexp) aexp)
          ((eq? (car (cdr aexp)) (quote +))
           (o+ (value (car aexp)) (value (car (cdr (cdr aexp))))))
          ((eq? (car (cdr aexp)) (quote *))
           (o* (value (car aexp)) (value (car (cdr (cdr aexp))))))
          ((eq? (car (cdr aexp)) (quote ^))
           (o^ (value (car aexp)) (value (car (cdr (cdr aexp)))))))))

再帰的な構造を再帰で処理しているからとてもシンプルになります

第7の戒律
性質を同じくするすべての構成部分について再帰すべし。
すなわち、
* リストのすべての部分リストについて。
* 算術式のすべての部分式について。

ここで、算術式の表現を変え、Lispのように演算子を先に書く表現にしてみます
(+ 1 (+ 2 3))みたいな感じ
carとcdrの数で調整しても正しく動作するプログラムは書けますが・・・

(define value
  (lambda (aexp)
    (cond ((atom? aexp) aexp)
          ((eq? (car aexp) (quote +))
          (o+ (value (car (cdr aexp))) (value (car (cdr (cdr aexp))))))
          ((eq? (car aexp) (quote *))
          (o* (value (car (cdr aexp))) (value (car (cdr (cdr aexp))))))
          ((eq? (car aexp) (quote ^))
          (o^ (value (car (cdr aexp))) (value (car (cdr (cdr aexp)))))))))

ここでは第1の部分式、第2の部分式、演算子をあらわす関数を作って抽象化します

(define 1st-sub-exp
  (lambda (aexp) (car (cdr aexp))))

(define 2nd-sub-exp
  (lambda (aexp) (car (cdr (cdr aexp)))))

(define operator
  (lambda (aexp) (car aexp)))

(define value
  (lambda (aexp)
    (cond ((atom? aexp) aexp)
          ((eq? (operator aexp) (quote +))
          (o+ (value (1st-sub-exp aexp)) (value (2nd-sub-exp aexp))))
          ((eq? (operator aexp) (quote *))
          (o* (value (1st-sub-exp aexp)) (value (2nd-sub-exp aexp))))
          ((eq? (operator aexp) (quote ^))
          (o^ (value (1st-sub-exp aexp)) (value (2nd-sub-exp aexp)))))))

抽象化を行ったことにより、表現が隠蔽されました
補助関数1st-sub-exp、2nd-sub-exp、operatorを書き換えることにより
valueはそのままでも最初の表現を利用することができます
こうするだけ

(define 1st-sub-exp
  (lambda (aexp) (car aexp)))

(define 2nd-sub-exp
  (lambda (aexp) (car (cdr (cdr aexp)))))

(define operator
  (lambda (aexp) (car (cdr aexp))))

第8の戒律
表現から抽象化するに際し、補助関数を使用すべし。

さらに抽象化が進みます
実用性なんて飾りです

前にも表現を見ましたか。
はい。ただそれが表現だとは言いませんでした。

数は表現ですか。
はい。たとえば、4は4という概念を表します。

ほかには何を使うことができるでしょうか。
(() () () ())でも同様に使えます。((((()))))はどうでしょう。あるいは(I V)では。

というわけで、(() () () ())式の表現を使ってzero?、add1、sub1の代わりの関数を書いてみます

(define sero? (lambda (n) (null? n)))
(define edd1 (lambda (n) (cons (quote ()) n)))
(define zub1 (lambda (n) (cdr n)))

これでo+を書くことができます

(define o+
  (lambda (n m)
    (cond ((sero? m) n)
          (else (edd1 (o+ n (zub1 m)))))))

ちゃんと動くかな

> (o+ '(() ()) '(() () ()))
(() () () () ())

ちゃんと動いてますね

o+の定義は変わりましたか。
はいであり、いいえでもあります。変わりましたがほんの僅かです。

変わったのはzero?がsero?になったように、関数の名前だけ
本来なら僅かも変えずにすむはず
定義済みの関数と名前がかぶっては困るので名前が変えてあるだけです
僅かも変えずにすむことを確かめておきましょう

アラビア数字で数を表現した場合に合わせてsero?ほかを書き換えてやります

(define sero? zero?)
(define edd1 (lambda (n) (+ n 1)))
(define zub1 (lambda (n) (- n 1)))

と定義を変更すればさっきのo+には修正を加えずに

> (o+ 2 3)
5

と計算できます

ついでにo*とo^も作ってvalueまで動かしてやろう
0も表現を隠蔽してやりますかね
(() () () ())式表現ではatom?で判定することができないので
代わりにmumber?という関数を作りました

(define zero (quote ()))
(define sero? (lambda (n) (null? n)))
(define edd1 (lambda (n) (cons (quote ()) n)))
(define zub1 (lambda (n) (cdr n)))
(define mumber?
  (lambda (n)
    (cond ((atom? n) #f)
          ((null? n) #t)
          (else (and (null? (car n)) (mumber? (cdr n)))))))

(define one (edd1 zero))
(define o+
  (lambda (n m)
    (cond ((sero? m) n)
          (else (edd1 (o+ n (zub1 m)))))))
(define o*
  (lambda (n m)
    (cond ((sero? m) zero)
          (else (o+ n (o* n (zub1 m)))))))
(define o^
  (lambda (n m)
    (cond ((sero? m) one)
          (else (o* n (o^ n (zub1 m)))))))

(define value
  (lambda (aexp)
    (cond ((mumber? aexp) aexp)
          ((eq? (operator aexp) (quote +))
           (o+ (value (1st-sub-exp aexp)) (value (2nd-sub-exp aexp))))
          ((eq? (operator aexp) (quote *))
           (o* (value (1st-sub-exp aexp)) (value (2nd-sub-exp aexp))))
          ((eq? (operator aexp) (quote ^))
           (o^ (value (1st-sub-exp aexp)) (value (2nd-sub-exp aexp)))))))

さてこれでvalueが動くはず

> (value '((((()) + (() ())) ^ (() ())) * (() ())))
(() () () () () () () () () () () () () () () () () ())

よし
これでzero、sero?、edd1、zub1、mumber?の定義を変えてやれば

(define zero 0)
(define sero? zero?)
(define edd1 (lambda (n) (+ n 1)))
(define zub1 (lambda (n) (- n 1)))
(define mumber? number?)

valueはそのままでアラビア数字の表現を使えるはず

> (value '(((1 + 2) ^ 2) * 2))
18

満足満足

今度の新しい数のもとで(1 2 3)はなんと表現しますか。
((()) (() ()) (() () ()))

(lat? l)は何ですか、ここで
lは((()) (() ()) (() () ()))です。
まさに偽です。

数のリストのはずなのに変ですね。
影法師に注意しなければなりません。

影法師ってなんだろうと思いましたが原書ではただのShadowsでした