PrologでR6RS
R6RSのAppendix AにはSchemeのサブセットの形式的意味論が載っています。
形式意味論というからには、しっかりと定義してある。
しっかりと定義してあるからには、論理的に正しい。
論理的に正しい、ということはPrologで書くことができる。
という謎の発想が生まれたのでPrologでこの形式的意味論に沿った
Schemeインタプリタを書いてみることにしました。
言い訳をしておきますが、Prologをまともに使うのは初めてです(*1)。
まだ、作っている途中なのですが、ある程度動いたので、
とりあえず、先に実行結果とソース(つくりかけで非常に汚い)を載せておきます。
?- gen_atom(seed). Yes ?- eval([store,[], [begin, 1, 2]], X). X = [store, [], [values, 2]] ; No ?- eval([store,[], [if, [+,1,2], [+,3,4], [+,5,6]]], X). X = [store, [], [values, 7]] ; No
ソース
入力/表示形式がPrologのリストで非常に見づらいですがお許し下さい。
最初の gen_atom はユニークなアトムを得るための述語(Lispで言うところのgensym)の初期化。
入力においての [store, X, Y] はXが抽象マシンのストア(メモリ)の内容、Yが評価すべき式。
出力においてはYが得られた式の値となります。
(詳しくはR6RSのAppendix Aを読んでください。)
未束縛の変数を気軽に扱ったりできて、Prologって楽しいですね。
しかし、今回に関してはなんといっても、
簡単なBNFを写して、 即 パース♪
といった感じでした。
遊びなので効率は気にしない方向で。
けど、評価文脈に沿って評価を行うというのが非常に辛かったです。
評価文脈の穴が三種類(通常用、多値用、単一値用)あるということを無視して放置していたら、
あとで、評価文脈関連の述語全てに引数を一つ付け足す羽目になったり、
あと、実行結果がおかしいと思ったら、原因がR6RSの誤字(*2)だったり。
(*1)「リストをアペンドするプログラムくらいなら書いたことあります。」という程度。
(*2)Figure A.2aのnoprocの ‘sym は恐らく sym の誤り。