Scheme手習い(20) eval、またはvalue、またはmeaning
ついに最終章、ラスボス2です
小さいschemeの核にあたるもの、いわゆる?eval
を作ります
でもこの本ではvalue
っていう名前になってます
でもvalue
は空っぽの環境を作るだけで実際の仕事の中心はmeaning
という関数がやってます
ラスボス2と言っても、Yコンビネータみたいに何がなんだかわからないようなものではなく
ひとつひとつの関数はとてもシンプルで難しくはありません
そのかわり、たくさんの関数があるのでそれらの関連を理解する必要があります
あと、環境と呼ばれるデータ構造も
この本ではこれまでクロージャとか関数の評価方法とか説明が省かれていた部分がありますが
この章を理解すればあそこはそういうことだったのか、と納得できます
「この本では形式的な定義はしない」ので代わりにソース見ろということですね
「この本を2回以下で読み切ろうとしないこと」というのは
この章をクリアしたら2周目に突入してもう1回読め、ということを言っているのではないかと
いつもどおりなんの説明もなく始まります
エントリ(entry)とはリストのペアであり、その第1のリストが集合であるものです。
これがインタプリタの作り始めだと誰が思うでしょうかいや思いません
(知ってる人は別として)
エントリを扱うための関数を定義します
(define new-entry build)
(define lookup-in-entry
(lambda (name entry entry-f)
(lookup-in-entry-help name (first entry) (second entry) entry-f)))
(define lookup-in-entry-help
(lambda (name names values entry-f)
(cond ((null? names) (entry-f name))
((eq? (car names) name) (car values))
(else (lookup-in-entry-help name (cdr names) (cdr values) entry-f)))))
build
は名前の集合と値のリストからエントリを作る関数、
lookup-in-entry
はエントリ内で名前に対応する値を得る関数です
entry-f
は名前を引数に取る関数で、名前が見つからない場合に呼ばれます
こういうのも継続っていうんでしょうか
違う気がしますけど何が違うかというとわかりません
やっぱり継続かもしれません
名前と値の対応をつけるなら、名前と値のペアを作ってそれをリストにするほうが
自然な気がしますが理由はあとでわかります
そもそもまだ何を作っているのかわかってませんし
テーブル(table、環境ともいう)とはエントリのリストだとします。
テーブルを扱うための関数を定義します
(define extend-table cons)
(define lookup-in-table
(lambda (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)))))))
extend-table
はテーブルにエントリを追加する関数、
lookup-in-table
はテーブルから名前に対応する値を得る関数です
extend-table
のシンプルさには度肝を抜かれる思いです
本気で言語書くときはもっといろいろくっつくのかな
エラー処理とか
table-f
はやはり名前を引数に取る関数で、名前が見つからない場合に呼ばれます
entry-f
はここで、テーブル内の次のエントリから名前を探すために使われています
そうやって使うのかー
知らないで「テーブルから値を探す関数を書け」と言われたら
そこをパラメータにしようとは考えず直接書いてしまいそうですけど
(define lookup-in-table2
(lambda (name table)
(cond ((null? table) #f)
((lookup-in-entry2 name (car table)))
(else (lookup-in-table2 name (cdr table))))))
(define lookup-in-entry2
(lambda (name entry)
(lookup-in-entry-help2 name (first entry) (second entry))))
(define lookup-in-entry-help2
(lambda (name names values)
(cond ((null? names) #f)
((eq? (car names) name) (car values))
(else (lookup-in-entry-help2 name (cdr names) (cdr values))))))
実は大きなごまかしをしてて、失敗すると#f
を返すんですが、
ということは値が#fの場合と区別がつかなくなっています
見つかった値と成功/失敗と両方返せるとか、
例外があるとかならちゃんとしたものにできるんですけど
そういう方法がないから仕方なく失敗したときに呼ぶ関数を渡してます、ってことでしょうか?
それだけではなくて、何かもっといいことがあるような気がするんですが
パラメータにしておくと柔軟ではありそうですが柔軟性が役に立っているかな?
しばらくの間、ゴシック体で書いてあるところはプログラムそっくりだけど
value
という関数が扱うデータだよっていう話
ゲーデルの証明みたい
続いて、式のタイプを考えます。
- 定数
*const
※組み込みの関数も含まれます - quote
*quote
- 識別子
*identifier
- ラムダ式
*lambda
- cond
*cond
- 関数適用
*application
式のタイプを返すexpression-to-action
を作ります
単にcondが並んでいるだけで難しくはありません
consとかcarとかの組み込み関数が*const
として扱われるのがちょっと意外でした
関数というくくりで見れば*lambda
にも近いような気がするんですが
関数へのポインタみたいなものと思えば確かに定数
タイプはそのタイプの式を評価する関数を兼ねていますので
式をexpression-to-action
に渡せば評価できます
(quote ())
というのは環境です
最初はまだ覚えておくべき変数がないので環境はからっぽです
(define value
(lambda (e) (meaning e (quote ()))))
(define meaning
(lambda (e table)
((expression-to-action e) e table)))
環境を扱う関数を定義して、
タイプを判別する関数を定義して、
式を評価する関数を定義するというトップダウンともボトムアップともとれない
不思議な順番には何か意味があるんでしょうか
わかりません
とりあえずガワができたので、少しずつ作っては動かすことができます
定義してない関数があっても、呼び出すまではエラーになりません
こういうときはありがたいです
(define *const
(lambda (e table)
(cond ((number? e) e)
((eq? e #t) #t)
((eq? e #f) #f)
(else (build (quote primitive) e)))))
さっき気になった組み込み関数はここで(primitive hoge)
という形になって
ちょっと別扱いになります
じゃあ*primitive
みたいなタイプ作ってもいいんじゃないかと
さて
> (value 1)
1
> (value #t)
#t
> (value 'cons)
(primitive cons)
やったー!
・・・という感じはまだしませんけどとりあえずインタプリタ動きました
(define *quote
(lambda (e table)
(text-of e)))
(define text-of second)
e
を見てほげほげすればいいんだな、ということがちょっと見えてきました
> (value '(quote abc))
abc
本文だとこの後*identifier
と*lambda
を定義してから*cond
なんですが
*identifier
と*lambda
だけあってもつまらないので先に*cond
やります
これまでより複雑ですが、ただリストをいじってるだけです
(define else?
(lambda (x)
(cond ((atom? x) (eq? x (quote else)))
(else #f))))
(define question-of first)
(define answer-of second)
(define evcon
(lambda (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-lines-of cdr)
(define *cond
(lambda (e table)
(evcon (cond-lines-of e) table)))
(else #f)
あたりにちょっと不自然さを感じます
(and (atom? x) (eq? x (quote else)))
で済むはずですが
セルフで実行できるようにってことかな
(ここで定義するインタプリタはand
を実装していないことからして)
> (value '(cond (#t 1)))
1
> (value '(cond (#f 1) (#t 2)))
2
> (value '(cond (#f 1) (else 2)))
2
動いてます
変数も関数もないのでかなり不自然なcond
ですが