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に触発されて書いてみました。
おもしろいので読んでみるとよいです。

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

Clojureのエラー処理

Clojureでエラー値を返すかもしれない関数ってどう書くのだろうとちょっと考えてみる。

Scalaだと例外はあまり使わず、EitherやValidationを使う派。
やはり、コンパイラの恩恵を受けることが出来る書き方が良い。

しかし、Clojureは動的型付けの言語。
コンパイラの恩恵は特にない。

なので、 どのような値が返ると扱いやすいかを考える。

Clojureは基本的に

• nil返す
• 例外投げる

の２通りだと思う。

Clojure標準のライブラリはnilを渡してもそれなりに動作するし、if-let,when-let,fnilなどの関数も用意されている。
しかし、nilだとどのようなエラーだったのか判別がつかない。
このような時に例外を使って、エラーの種類によって投げる例外を変えれば良いのだと思う。

Clojureの例外を投げるような関数は以下のように書ける。

	(defn nthv [n vec]
	(if (integer? n)
	(if (and (pos? n) (< n (count vec)))
	(get vec n)
	(throw (IndexOutOfBoundsException.)))
	(throw (IllegalArgumentException.))))

view raw ex.clj hosted with ❤ by GitHub

この場合は、Java APIのIllegalArgumentExceptionとIndexOutOfBoundsExceptionを使った。
しかし、何時でもJava APIに自分が欲しいExceptionが定義されているわけではない。
このような時は、独自の例外を作るだろう。

駄菓子菓子！

Clojureでclassを定義するのはとても面倒。
nsやgen-classを見てもらえればわかると思う。
Throwableがinterfaceならば、deftypeやdefrecordが使えたのだけれど・・・

例外を定義する部分だけJavaで書いたほうが楽かも。

class MyException extends Exception {}

view raw ex.java hosted with ❤ by GitHub

leiningenはJavaもサポートしているので、共存させるのは苦ではない。

結論

基本的にnilを返す。
独自の例外を定義したかったらJavaを使うと楽

Clojureでモナド内包表記とStateモナド

cljsbuildのcrossoversという機能を知らない所為で今まで無駄に苦労してきましたが、これでマクロが使えないという制約から解き放たれました。
万歳！cljsbuild！

マクロが使えるようになってまず一番最初にやることは何か？
もちろん、モナド内包表記の実現ですね！

HaskellのdoよりはScalaのforの方が慣れているのでこちらを採用しました。

動的型付けの言語でのモナドの実現はいくつか見てきましたが、明示的にコンテキストを指定するタイプはあまり好かないので、ClojureらしくProtocolで表現することにしました。

Monadic Protocol

通常モナドはunitとbindが実装され、モナド則

• bind f (unit x) == f x
• bind unit m == m
• あともう一個なんかあった気がする

を満たしますが、動的型付けの言語でunitを実現するのは面倒なので、モナドっぽいインターフェースを定義します。

	(defprotocol Monadic
	(fmap [m f])
	(bind [m f]))

view raw monadic.clj hosted with ❤ by GitHub

このインターフェースが実装されていれば、モナド内包表記が使えるようになります。
とてもScala的。

モナド内包表記

Lispは神の言語と皆ネタにしていますが、Lispのマクロは本当に強力です。
既存の言語にある構文の全てはLispのマクロで表現できるのではと思えるくらいです。

Clojureの標準ライブラリではパターンマッチが出来ないので、準標準ライブラリであるcontribのcore.matchを使います。

	(defmacro do-m [bindings expression]
	(match [bindings]
	[[name value]]
	`(fmap ~value (fn [~name] ~expression))
	[[name value & bindings']]
	`(bind ~value (fn [~name] (do-m ~bindings' ~expression)))))

view raw do_m.clj hosted with ❤ by GitHub

しんぷるいずべすと、MonadPlusなんて知らないのでガードは実装しません。めんどい。

このdo-mマクロがどのように展開してくれるかというと

	(do-m
	[a m
	b (f a)]
	(g a b))

view raw expand.clj hosted with ❤ by GitHub

が

(bind m (fn [a] (fmap (f a) (fn [b] (g a b)))))

view raw expanded.clj hosted with ❤ by GitHub

こんな感じになります。

実際に動かしてみます。

	user=> (defn bind [m f] (mapcat f m))
	#'user/bind
	user=> (defn fmap [m f] (map f m))
	#'user/fmap
	user=> (do-m [a [1] b [(inc a)]] (+ a b))
	(3)

view raw example.clj hosted with ❤ by GitHub

動いたー！
素敵です。

Stateモナド

私が現在製作中のアプリケーションでは、レコードを更新する関数が多数定義されています。
これは、状態をとって、新しい状態を返す関数ですが、少し問題があります。

一つ例を示します。

	(defrecord Cursor [x y])
	(defn right [n cursor]
	(assoc cursor :x (+ (:x cursor) n)))
	(defn down [n cursor]
	(assoc cursor :y (+ (:y cursor) n)))

view raw cursor.clj hosted with ❤ by GitHub

このような関数が定義されていた時、右下へ移動する関数を定義するのに->>マクロを使い、手続き的に書くことができます。

	(defn right-down [n cursor]
	(->> cursor
	(right n)
	(down n)))

view raw right_down.clj hosted with ❤ by GitHub

しかし、このrightでの計算結果、つまりxを使う関数を定義する時、コードはこのようになります。

	(defn square [n cursor]
	(let [cursor' (right n cursor)]
	(down (:x cursor') cursor')))

view raw square.clj hosted with ❤ by GitHub

このパターンが関数内で頻出する場合、一時的なcursorの状態を保存する為の変数が増えてしまいます。
さらに、この場合はxを取得するコストは微々たるものですが、フィールドの取得に複雑なロジックを用いたり、計算値が状態の更新に間接的に使われるだけで、レコードからは取得できない場合があります。

新しい状態だけを返すのではなく、計算値とのペアで返せばこのパターンを解決できます。

	(defn right' [n cursor]
	(let [x (+ (:x cursor) n)]
	[(assoc cursor :x x) x]))

view raw right.clj hosted with ❤ by GitHub

しかし、->>マクロのようにネストせずに書けるわけではありません。

そこでStateモナドの出番です！（導入長い！

Stateモナドは状態を取り、新しい状態と計算値のペアで返す関数に対してモナドを定義したものです。

先ほど定義したMonadicをStateに実装してみます。

	(defrecord State [f]
	Monadic
	(fmap [s g]
	(State. (fn [s]
	(let [[s' a] (f s)]
	[s' (g a)]))))
	(bind [s g]
	(State. (fn [s]
	(let [[s' a] (f s)]
	((:f (g a)) s'))))))

view raw state.clj hosted with ❤ by GitHub

right, down関数をStateで定義してみます。

	(defn right [n]
	(State. (fn [cursor]
	(let [x (+ (:x cursor) n)]
	[(assoc cursor :x x) x]))))
	(defn down [n]
	(State. (fn [cursor]
	(let [y (+ (:y cursor) n)]
	[(assoc cursor :y y) y]))))

view raw state_function.clj hosted with ❤ by GitHub

この時、square関数はdo-mを使って以下のように定義できます。

	(defn square [n]
	(do-m [x (right n)
	s (down x)]
	s))

view raw state_square.clj hosted with ❤ by GitHub

ヤッター！

関数の合成が手続き的に書けますね。

まとめ

マクロ強力。Stateモナド美しい。

本当はFreeモナド使おうと思ったけどStateモナドの素晴らしさを伝えたかったので控えました。

これから70個近い関数をStaeモナドに書き換える作業が待ってます。
Freeモナドの資料も作らなきゃですね。
私の代わりに大学のC言語の課題をやってくれるといいと思います。

Clojureへの不満とか

最近はClojureばかり書いているので、良い所ばかりでなく、気になるところも見えてきました。

なにか意見をもらえるかもしれないので書き並べておきます。

セルフホスティングして欲しい

Clojureのソースコードを読むときに、高確率でJavaのコードを読まなければいけないので悲しくなります。
やはり、gen-classとかでは物足りないのかなあ？
それとも、セルフホスティングにはあまりヤル気がないのか・・・・

clojure.langのJavaDoc欲しい

ソースコード追うのが面倒なので。

Protocolをもっと使って欲しい

自分で新しいデータ型を作った時に、既存の関数を使うためにclojure.langの得体の知れないinterfaceを実装するわけですが、Protocolとして存在すればClojureの中で完結するのでうれしいのだけど、これはデータ型がJavaに依存しすぎてて簡単にはいかないんだろうなあと。

関数が返す値は適用する値と同じデータ型で返して欲しい

特にStringとか。
charのシーケンスで返ってくるのが悲しい。
これはなぜだろう、効率のためかな？
どこかで読んだ気がしなくもない。

いっそのことClojure独自に文字列作るというのは・・・・まあ、それはそれで面倒臭そう。

Scalazは独自にCordというデータ型を定義しています。
さすが、尖ってる。

insertしたい

ArrayListやLinkedListを使えばいいのですが、functionalでpurelyなdata structureが欲しいわけです。

Arrowが欲しい

Haskellのfirst,secondに当たるものが欲しい。
分配束縛したくない。
もっとポイントフリーなプログラミングがしたいのです。

しかし、compとpartialとjuxtでやりすぎたコードを書くのには注意です。

if-let, when-letが１つの変数しか束縛できない

なぜ複数束縛できないのか・・・・・

要素を１つだけ持つlistとmapとmapcatまたはforを使って、Maybeモナドっぽいことは出来ます。
あとは(fn [a] (if (nil? a) (list) (list a)))のようなものがあるといいのだけど。

do記法、for内包、コンピュテーション式にあたるものが欲しい

for内包はあることにはあります。
しかし、これはSequableでSequentialなデータ型（JavaのIterableとIteratorのようなもの？）の為のもので、モナドの為のマクロではないです。

Maybeモナドやdo記法はalgo.monadsで提供されていますが、あまり設計に納得がいかない。
私はあるデータ型に対してモナドを定義したいので、Protocolをベースに設計したものが欲しかった。

限定継続が欲しい

do記法がないなら限定継続を使えばいいじゃないと昔の貴族は言ったものです。
限定継続があれば括弧を減らせるような構文がいろいろと簡単に定義できそうだなあと思い挙げてみた。 

delimicといものがあるらしい。

まとめ

私はいままではScalaばかり書いていましたが、いまはClojureばかり書いているのでこのような記事を書いています。
実際には2年前くらいから少しずつ書いていましたが、これほどClojureを書いてる期間はありませんでした。

Scalaに触れ、さらにScalazに触れたことで完全に関数型プログラミング信者になってしまいましたが、実際に有用な技法を多く知ることが出来ました。
それをClojureで実現するために、このような贅沢な不満が出てきました。

Clojureはまだまだ若い言語だと思うので、あれもこれもと求め過ぎていると思います。
なので、今後私が期待しているものに発展してくれるようClojureに貢献していきたいです。