ClojureでLisp評価器

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

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

	(define (eval exp env)
	(cond ((self-evaluating? exp) exp)
	((variable? exp) (lookup-variable-value exp env))
	((quoted? exp) (text-of-quotation exp))
	((assignment? exp) (eval-assignment exp env))
	((definition? exp) (eval-definition exp env))
	((if? exp) (eval-if exp env))
	((lambda? exp)
	(make-procedure (lambda-parameters exp)
	(lambda-body exp)
	env))
	((begin? exp)
	(eval-sequence (begin-actions exp) env))
	((cond? exp) (eval (cond->if exp) env))
	((application? exp)
	(apply (eval (operator exp) env)
	(list-of-values (operands exp) env)))
	(else
	(error "Unknown expression type -- EVAL" exp))))

view raw eval.scm hosted with ❤ by GitHub

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

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

Protocol

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

	(defprotocol Eval
	(eval [this env exp]))

view raw eval.clj hosted with ❤ by GitHub

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

	(def nothing (Object.))
	(defn literal? [exp]
	(or (true? exp)
	(false? exp)
	(nil? exp)
	(number? exp)
	(string? exp)))
	(def literal
	(reify Eval
	(eval [this env exp]
	(if (literal? exp)
	exp
	nothing))))

view raw literal.clj hosted with ❤ by GitHub

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

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

special form

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

	(defn tagged? [tag exp]
	(and (seq? exp)
	(-> exp empty? not)
	(-> exp first (= tag))))

view raw tagged.clj hosted with ❤ by GitHub

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

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

	(deftype Special [tag f]
	Eval
	(eval [this env exp]
	(if (tagged? tag exp)
	(f env (rest exp))
	nothing)))

view raw special.clj hosted with ❤ by GitHub

Specialを使ったquote

	(def quotation
	(Special. 'quote
	(fn [env exp]
	(first exp))))

view raw quotation.clj hosted with ❤ by GitHub

if

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

	(def divergence
	(Special. 'if
	(fn [env exp]
	(if (->> exp first (eval ? env))
	(eval ? env (nth exp 1))
	(eval ? env (nth exp 2))))))

view raw divergence0.clj hosted with ❤ by GitHub

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

	(def lisp (compose literal
	quotation
	(divergence lisp)))

view raw lisp0.clj hosted with ❤ by GitHub

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

	(defn divergence [f]
	(Special. 'if
	(fn [env exp]
	(if (->> exp first (f env))
	(f env (nth exp 1))
	(f env (nth exp 2))))))

view raw divergence.clj hosted with ❤ by GitHub

compose

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

	(defn compose [e & es]
	(reduce (fn [e e']
	(reify Eval
	(eval [this env exp]
	(let [result (eval e env exp)]
	(if (= result nothing)
	(eval e' env exp)
	result)))))
	e
	es))

view raw compose.clj hosted with ❤ by GitHub

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

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

	(def lisp
	(compose literal
	(divergence (fn [env exp]
	(eval lisp env exp)))))

view raw lisp.clj hosted with ❤ by GitHub

実行

	user=> (eval lisp {} '(if true 1 2))
	1
	user=> (eval lisp {} '(if false 1 2))
	2

view raw result.clj hosted with ❤ by GitHub

ヤッター

まとめ

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

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

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