ClojureでLisp評価器

SICP読書会、毎週月曜19時からmixiでやってます。
現在第４章の超循環評価器を作っています。

4章の一番最初に出てくるevalの定義は以下の通り

とてもわかりやすいけど、データ主導にしたいよね、そうしよう、というのが問題4.3にあります。

これをClojureっぽく書くことを考えてみる。

Protocol

ClojureといったらやっぱProtocolだよね！ということでプロトコルベースで考える。
とりあえず評価器プロトコル、Eval(uator)の定義

このプロトコルを実装したリテラルの評価器を書いてみる。

部分関数っぽくしたいのだけど、例外を投げるか迷った。
今回はとりあえずこれで。

このように、小さな評価器をいっぱい作って合成していくという考え方。

special form

ifやdefineやbeginなんかのspecial formをチェックする関数tagged?の定義

先頭要素を比較するだけ。

これを使って、special formを以下のように表してみる

Specialを使ったquote

if

ifは式を評価しなければいけない。
しかし、どの評価器を使えばいいのかわからない。

評価器を引数にとるという選択肢もあるけど、不都合がある。

この式を評価するとよくわからないエラーが投げられると思う。
ここでは評価機が部分適用されたeval関数をとることにする。

compose

一番大事な評価器を合成する関数

やっていることは簡単、引数の先頭の評価器から順に、式を評価器で評価して失敗したら次の評価器で評価するという評価器を作っているだけ。

これを使ってifとliteralだけが使えるlispを定義すると以下のようになる。

実行

ヤッター

まとめ

こんな感じで小さな評価器を書いていって大きな評価器を作っています。
なかなか楽しい。

今回のプログラムはScalaBaseで@maeda_さんが発表されていた、Javascript as an Embedded DSLに触発されて書いてみました。
おもしろいので読んでみるとよいです。

次はぱーさーこんびねーたについて書く、書きたい、書けたらいいな。