第10章：このすべての値は何だ
Scheme 手習い第 10 章。
いわゆる eval を実装する。この本では value という関数名になっているけど。
準備
リストを操作するための便利関数を事前に定義しておく。
(define (build a b)
(cons a (cons b '())))
(define (first x)
(car x))
(define (second x)
(car (cdr x)))
(define (third x)
(car (cdr (cdr x))))
エントリーとテーブル（環境）
new-entry
(define new-entry build)
(new-entry '(appetizer entree beverage) '(patee boeuf vin))
エントリーとは２つの要素からなるリストである。
第１要素が集合のリスト、第２要素がその値であるリスト。
変数名とそれらに対応する値のリストである。
lookup-in-entry
(define (lookup-in-entry name entry entry-f)
(lookup-in-entry-helper
name
(first entry)
(second entry)
entry-f))
(define (lookup-in-entry-helper name names values entry-f)
(cond [(null? names) (entry-f name)]
[(eq? name (car names)) (car values)]
[else (lookup-in-entry-helper name (cdr names) (cdr values) entry-f)]))
entry から name に対応する値を探す関数。
指定された entry 内に name が見つからなかった場合には、entry-f を呼び出す点が特徴的。
これをどうやって利用するかはあとで分かる。
extend-table
テーブルというのはエントリーのリスト。テーブルは環境とも呼ぶ。
テーブルを拡張するには、単にリストの先頭にエントリーを追加すればよい。
(define extend-table cons)
(define entry-1 '((a b c) (1 2 3)))
(define entry-2 '((d e f) (4 5 6)))
(define entry-3 '((g h i) (7 8 9)))
(extend-table entry-1
(extend-table entry-2
(extend-table entry-3 '())))
lookup-in-table
(define (lookup-in-table name table table-f)
(cond [(null? table) (table-f name)]
[else (lookup-in-entry name (car table)
(lambda (name)
(lookup-in-table name (cdr table) table-f)))]))
テーブルから任意の名前に対応する値を探す関数。
それぞれのエントリには同じ名前が含まれいてる可能性があるが、そういう場合は先頭にあるエントリの値を優先する。
テーブルの先頭にあるエントリーに対し lookup-in-entry を行う。
もし値が見つからなかった場合は entry-f として再帰する処理を lambda で渡している。
こうやって再帰を渡す方法もあるんだなぁと感心。継続に近いのかな。
value
さて、ここからは value を実装する長い旅にでる。
value は「渡された S 式の自然な値を返す（評価する）関数」である。
いわゆる eval と同等のものになる。
value の仕様
まず、value の返すべき値について本に書かれていた実例を挙げておく。
(value '(car (quote (a b c))))
(value '(quote (car (quote (a b c)))))
(value '(add1 6))
(value '6)
(value 'car)
(value '(quote nothing))
(value 'nothing)
(value '((lambda (nothing)
(cons nothing (quote ())))
(quote
(from nothing comes something))))
(value '((lambda (nothing)
(cond [nothing (quote something)]
[else (quote nothing)]))
#t))
(primitive car) はプリミティブな基本関数であること示している。
これについては後述。
タイプ
value にはさまざまな S 式が渡されるので、まずその種類に応じてタイプを定義する。
type はタイプを取得する関数だと仮定する。
(type '6)
(type '#f)
(type 'cons)
(type '(quote nothing)
(type 'nothing)
(type '(lambda (x y) (cons x y)))
(type '((lambda (nothing)
(cond [nothing (quote something)]
[else (quote nothing)]))
#f))
(type '(cond [(nothing (quote something))]
[(else (quote nothing))]))
これらのタイプそれぞれに対しての評価する処理を実装していく。
アクション
与えられた S 式に対して、それぞれのタイプに対するアクションを実装する。
(define (expression-to-action e)
(cond [(atom? e) (atom-to-action e)]
[else (list-to-action e)]))
e に対して atom かリストであるかを判別してそれぞれに対して正しいアクションへの変換を定義する。
atom-to-action は次のとおり。
(define (atom-to-action e)
(cond [(number? e) *const]
[(eq? e #t) *const]
[(eq? e #f) *const]
[(eq? e (quote cons)) *const]
[(eq? e (quote car)) *const]
[(eq? e (quote cdr)) *const]
[(eq? e (quote null?)) *const]
[(eq? e (quote eq?)) *const]
[(eq? e (quote atom?)) *const]
[(eq? e (quote zero?)) *const]
[(eq? e (quote add1)) *const]
[(eq? e (quote sub1)) *const]
[(eq? e (quote number?)) *const]
[else *identifier]))
list-to-action は次の通り。
(define (list-to-action e)
(cond [(atom? (car e))
(cond [(eq? (car e) (quote cond)) *quote]
[(eq? (car e) (quote cond)) *cond]
[(eq? (car e) (quote lambda)) *lambda]
[else *application])]
[else *application]))
アクションである *const、*identifier、*cond などはこのあと定義していく。
expression-to-action を使うと value は次のように定義できる。
(define (value e)
(meaning e '()))
(define (meaning e table)
((expression-to-action e) e table))
value は空のテーブル（環境）を定義し、meaning を呼ぶ。
meaning は与えられた S 式からアクションを生成して、そのアクションを S 式と与えられた環境で評価する。
アクション定義
アクションは S 式と環境を受け取って評価する関数。
すべてのアクションは S 式である e と環境である table を引数として受け取る。
*const
(define (*const e table)
(cond [(number? e) e]
[(eq? #t e) #t]
[(eq? #f e) #f]
[else (build (quote primitive) e)]))
(*const '1 '())
(*const '#t '())
(*const 'cons '())
定数に対するアクション。
S 式が数字や真偽値ならそのまま S 式を返す。
それ以外の場合はプリミティブな基本関数であることを示す (primitive e) というリストを返す。
プリミティブな基本関数とはシステムに組み込まれた何をすればいいかすでに分かっている関数を指す。
*quote
(define (*quote e table)
(second e))
(*quote '(quote hoge) ())
クオートに対するアクション。
渡される S 式は (quote hoge) のような形になっているので、単に第２要素を返せばよい。
この挙動を考えると、そもそも Scheme の quote が何をするものかより明確に理解できる。
quote を使うと S 式を評価をせずそのまま返すことができる。
*identifier
(define (*identifier e table)
(lookup-in-table e table initial-table))
(define (initial-table name)
(car '()))
(*identifier 'x '(((x y) (1 2))))
(*identifier 'z '(((x y) (1 2)) ((z) (0))))
識別子に対するアクション。
テーブル（環境）から、名前に対応する値を返す関数。
テーブルから名前がひけない場合はエラー（空リストに対する car）となるようになっている。
*cond
次は *cond を実装する。
cond は次のような構文である。
<cond-form> := (cond cond-line cond-line cond-line ...)
<cond-line> := (question answer)
これを踏まえて *cond を実装する。
(define (else? e)
(cond [(atom? e) (eq? e 'else)]
[else #f]))
(define question-of first)
(define answer-of second)
(define (evcon lines table)
(cond [(else? (question-of (car lines)))
(meaning (answer-of (car lines)) table)]
[(meaning (question-of (car lines)) table)
(meaning (answer-of (car lines)) table)]
[else (evcon (cdr lines) table)]))
(define (*cond e table)
(evcon (cdr e) table))
(*cond '(cond (#t 1) (#f 2) (else 3)) '())
(*cond '(cond (#f 1) (#f 2) (else 3)) '())
(*cond '(cond (val1 1) (val2 2) (else 3)) '(((val1 val2) (#f #t))))
evcon は cond-line を先頭から見ていく。
まず question 式が else の場合には #t だと見なすので、対応する answer 式を評価して返す。
評価には meaning を用いる。
そうでない場合、question 式を評価して #t であれば answer 式を評価して返す。
それ以外の場合は、残りの cond-line について再度 evcon を再帰的に評価する。
*lambda
*lambda アクションではノンプリミティブな非基本関数であることを示す (non-primitve ...) というリストを返す。
次の3要素を覚えておくようにしておく。
(define (*lambda e table)
(build (quote non-primitive)
(cons table (cdr e))))
(*lambda '(lambda (x y) (cons x y)) '(((y) (1))))
これらを踏まえると *lambda は (non-primitive (テーブル 仮引数リスト 関数定義)) というリストを返す。
それぞれを取得できるように次の便利関数も定義しておく。
(define table-of first)
(define formals-of second)
(define body-of third)
ちなみに *lambda のアクションで環境を保存しておくのは Scheme の静的（レキシカル）スコープの特徴。
動的スコープならここでテーブルを覚えておく必要はないのかな？
*application
最後は関数適用アクション。
関数適用は (fun arg arg arg arg ...) という形になるのでそれを踏まえて順にアクションを定義していく。
evlis
関数を適用する際、まずは引数をすべて評価する必要がある。
そこで、関数適用の実引数のリストをすべて評価してリスト化する関数 evlis を定義する。
(define (evlis args table)
(cond [(null? args) '()]
[else (cons (meaning (car args) table)
(evlis (cdr args) table))]))
処理としては与えられた実引数のリストを先頭要素を meaning で評価して、再帰して cons していく。
apply
次に関数を適用する apply メソッドを実装する。
(define (primitive? fun)
(eq? (first fun) (quote primitive)))
(define (non-primitive? fun)
(eq? (first fun) (quote non-primitive)))
(define (apply fun vals)
(cond [(primitive? fun) (apply-primitive (second fun) vals)]
[(non-primitive? fun) (apply-closure (second fun) vals)]))
apply メソッドは関数本体と実引数のリストを受け取る。
そして、関数本体がプリミティブかノンプリミティブに応じて別の関数を呼び出す。
apply-primitive と apply-closure はこの後定義する。
apply-primitive
(define (apply-primitive name args)
(cond [(eq? name (quote cons)) (cons (first vals) (second vals))]
[(eq? name (quote car)) (car (first vals))]
[(eq? name (quote cdr)) (cdr (first vals))]
[(eq? name (quote null?)) (null? (first vals))]
[(eq? name (quote eq?)) (eq? (first vals) (second vals))]
[(eq? name (quote atom?)) (atom?? (first vals) (second vals))]
[(eq? name (quote zero?)) (zero? (first vals))]
[(eq? name (quote add1)) (add1 (first vals))]
[(eq? name (quote sub1)) (sub1 (first vals))]
[(eq? name (quote number?)) (number? (first vals))]))
関数が primitive だった場合は、関数名を調べて正しい関数を適用するだけの処理。
apply-closure
最後に non-primitve な関数、すなわちクロージャーを適用する。
(define (apply-closure fun args)
(meaning (body-of fun)
(extend-table
(new-entry (formals-of fun) args)
(table-of closure))))
処理としてはけっこうシンプル。
やっている内容は分かりやすい文が載っていたのでそのまま転載する。
非基本関数（クロージャー）を値のリストに適用することは、(formals values) の形のエントリで拡張したテーブルのもとでクロージャーの本体の意味を求めることと同じです。
レキシカルスコープ
この時、クロージャーに含まれいてる環境を meaning に与えていることがポイントだと思う。
次のようにクロージャーのテーブルではなく評価時のテーブルを次のように与えることもできる。
(define (apply-closure fun args)
(meaning (body-of fun)
(extend-table
(new-entry (formals-of fun) args)
table)))
この違いは、レキシカルスコープか動的スコープかの違いになるのではないだろうか（たぶん）。
レキシカルスコープは (lambda ...) が評価された場所の環境が使えるためコード上で環境が見えやすい。
一方、動的スコープだと関数が呼び出された場所の環境に依存するためコードが分かりづらくなりそうだ。
動的スコープの言語はあまり触ったことがないのであまり感覚をつかめていない。
ただ、オブジェクト指向の this だけは動的スコープ的な評価になるというのは、どこかに書いてあって確かに「言われてみれば〜」という感じ。
*application
apply と evlis ができたので *application が作れるようになった。
(define (*application e table)
(apply (meaning (function-of e) table)
(evlis (cdr e) table)))
*application は、e の関数部分を評価し、引数リストを評価してから、apply する。
実例
ようやくすべてのアクションがそろったので、value が機能するようになった。
下記の式を例にして value の適用を順を追って見てみることにする。
((((lambda (y)
(lambda (x)
(lambda (f)
(f x y))))
2)
1)
(lambda (a b)
(cons a b)))
適用は長くなるのでこちらに。
この関数の適用では、値の束縛が引数の呼び出し（スタック）に積まれていくのが分かる。
((lambda (f)
((lambda (x)
((lambda (y)
(f x y))
2))
1))
(lambda (a b)
(cons a b)))
適用は長くなるのでこちらに。
こちらの関数の適用では値の束縛がクロージャの環境として保持されているのが分かる。
同じような関数呼び出しだが値の束縛を保持する位置が違うのが興味深い。
define は作っていないけど、Y コンビネータを使えば再帰が使えるので define は必須ではないことが分かる。
(value
'(((lambda (le)
((lambda (f)
(f f))
(lambda (f)
(le (lambda (x)
((f f) x))))))
(lambda (length)
(lambda (l)
(cond
((null? l) 0)
(else (add1 (length (cdr l))))))))
(quote (1 2 3 4 5))))
さらに
さらに次のような課題が。
≪Y コンビネータによる変形を行うと、インタプリタ上でインタプリタを走らせることが可能であるということですか。≫
はい。でもそんなに悩まないでください。
Y コンビネーターを使えば作った value 上でさらにインタプリタを走らせることができるらしい。
こちらの課題に関してはこちらのブログがとてもよくまとまってたので、それを見て満足したのでやってない。
というか、本書全体を通してこちらのブログがとても細かく書かれていて参考になった。
kb84tkhr.hatenablog.com
おわりに
これで Scheme 手習いは終わり。
途中、半年くらいさぼってしまって終わるのに一年くらいかかった。
最初の7割と最後の3割くらいで、難易度がずいぶんと違う気がする。
継続や Y コンビネーター、eval について簡単にだけど学ぶことができたので満足。
それぞれが何を意味しているかくらいは理解した。
やっぱりこうやってブログにしながら学習すると理解がはかどるな。
時間はかかるけど。
気が向いたら Scheme 修行やるかな。なんか絶版っぽいけど。。。
