Scheme手習い　第６章　影法師 - プログラミング再入門

『影法師（Shadow）』が何を意味しているのか正確には分かりません。影法師と言う言葉はこの章の最後に『影法師に注意しなければなりません。』とだけ出てきます。『Scheme修行』まで読んだ感じでは同じ機能を持つ別の実装の事を指している様に思いますが、山本和彦さんの解説では影法師は補助関数の事だそうです。

ここではデータを抽象化してデータの表現形式から分離されたプログラムを習います。

ノート：

numbered?

最初の定義

> (let ((x 1))
    (numbered? x))
#t
> (let ((y '(3 ＋ (4 ↑　5))))
    (numbered? y))
#t
> (let ((z '(2 × sausage)))
    (numbered? z))
#f
> (let ((z '(2 ÷ 1)))
    (numbered? z))
>

数の場所が数でなければ偽となるが、演算子が間違っているとcase漏れ（cond漏れ？）を起こして何も起きずに終了する。

case漏れに対処するとコードは

(define numbered?
  (lambda (aexp)
    (cond ((atom? aexp) (number? aexp))
          ((eq? (car (cdr aexp)) '＋) (and (numbered? (car aexp)) (numbered? (car (cdr (cdr aexp))))))
          ((eq? (car (cdr aexp)) '×) (and (numbered? (car aexp)) (numbered? (car (cdr (cdr aexp))))))
          ((eq? (car (cdr aexp)) '↑) (and (numbered? (car aexp)) (numbered? (car (cdr (cdr aexp))))))
          (else #f))))

となる。これで評価すると：

> (let ((x 1))
    (numbered? x))
#t
> (let ((y '(3 ＋ (4 ↑　5))))
    (numbered? y))
#t
> (let ((z '(2 × sausage)))
    (numbered? z))
#f
> (let ((z '(2 ÷ 1)))
    (numbered? z))
#f
>

２番目の定義では演算子は任意のアトムとなる。こうするとここでは想定していない÷が入っていても#tとなるので正しい演算子しか使われない事が前提となる。

> (numbered? '(3 ↑ 3))
#t
> (numbered? '(4 ÷ 3))
#t
>

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

原文が無いので良く分からないが、関数を呼ぶ側が関数を正しく把握している事を前提と出来るからと言う意味か。

value

最初のvalueの定義で評価する。

> (let ((u 13))
    (value u))
13
> (let ((x '(1 ＋ 3)))
    (value x))
4
> (let ((y '(1 ＋ (3 ↑ 4))))
    (value y))
82
> (let ((z 'cookie))
    (value z))
cookie
>

最後のcookieの例は、答えが無い事になっているが、valueの定義はアトムであればそれが数かどうかは確認せずそのまま値としているのでシンボルもそのまま返って来る。

特に明記されていないが、各リストは

リストまたは数字
演算子
リストまたは数字

と言うフォーマット、つまり中置記法を取り扱う。また括弧の扱いはベースのSchemeとしての括弧を利用している。

次に前置記法を解釈する時の定義。

> (value 13)
13
> (value '(＋ 1 3))
. . car: expects argument of type <pair>; given ()
> (value '(＋ 1 (↑ 3 4)))
. . car: expects argument of type <pair>; given ()
>

演算子の数部分(value (cdr nexp))および(value (cdr (cdr nexp)))が間違いなので、ちゃんとエラーになる。修正した定義は以下の通り。

(define value
  (lambda (nexp)
    (cond ((atom? nexp) nexp)
          ((eq? (car nexp) '＋) (＋ (value (car (cdr nexp))) (value (car (cdr (cdr nexp))))))
          ((eq? (cdr nexp) '×) (× (value (car (cdr nexp))) (value (car (cdr (cdr nexp))))))
          (else (↑ (value (car (cdr nexp))) (value (car (cdr (cdr nexp)))))))))

評価する。

> (value 13)
13
> (value '(＋ 1 3))
4
> (value '(＋ 1 (↑ 3 4)))
82
>

1st-sub-exp / 2nd-sub-exp / operator

補助関数による算術式の抽象化。

これまで殆どcondで始めていたからと言ってなぜここでも態々condを入れるのかは良く分からない。condが必要だから使っていたのであれば必要の無い所では使わないのは当然。本書ではあくまで定型から始めて不要な部分は取り除く考え方を徹底している模様。

valueを求めるロジック（アルゴリズム）とデータ構造（ここでは表現）を分離するのに補助関数を使う。

> (value 13)
13
> (value '(＋ 1 3))
4
> (value '(＋ 1 (↑ 3 4)))
82
>

中置記法に対応した補助関数に変更して評価する。

> (value 13)
13
> (value '(1 ＋ 3))
4
> (value '(1 ＋ (3 ↑ 4)))
82
>

ここの部分で「表現」と訳されているのはひょっとするとexpression＝式（数式）の事ではないかと思う。

sero? edd1 zub1

「数」を数値リテラル（あるいはアトム）ではなく、リストに含まれる空リストの数で表現し、この表現で使える述語と演算子を定義する。

> (zub1 '())
. . cdr: expects argument of type <pair>; given ()
> (zub1 '(()))
()
> (sero? (zub1 '(())))
#t
>

負の数は定義していない事になっているので(zub1 0)はエラーでも良い。S式を一つ持っているリストは１を表しているので、そこから１を引くと０になる事が確認出来る。

新しい表現を使った+の定義を⊞として定義して評価してみる。ただし下のコードでは⊞がうまく表示出来ないので全角の＋で代用する。

> (＋ '(()) '(() () ())) ; 1 + 3
(() () () ())
> (length (＋ '(() () () ()) '(() () () () () ()))) ; 4 + 6
10
>

最後の問答は、lat?は数のリストに対しては#tとなる筈だったと言っている。lat?はアトムのリストであると言う述語であり、数がアトムとして表現されていなければ数のリストでは#tとはならない。影法師は同じ機能を持つ別の実装なので、ある実装で成り立つ性質が別の実装上では成り立たない事があるので注意と言う事か。