2012年10月31日水曜日

ClojureでLisp評価器

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

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

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

2012年10月27日土曜日

Clojureのエラー処理

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

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

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

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

Clojureは基本的に
  • nil返す
  • 例外投げる
の2通りだと思う。

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

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

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

駄菓子菓子!

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

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

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

結論


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

2012年10月13日土曜日

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を実現するのは面倒なので、モナドっぽいインターフェースを定義します。

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

モナド内包表記


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

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

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

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



こんな感じになります。

実際に動かしてみます。

動いたー!
素敵です。

Stateモナド


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

一つ例を示します。

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

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

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

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

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

そこでStateモナドの出番です!(導入長い!

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

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

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

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

ヤッター!

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

まとめ


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

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

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

2012年10月3日水曜日

Clojureへの不満とか

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

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

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


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

clojure.langのJavaDoc欲しい


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

Protocolをもっと使って欲しい


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

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


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

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

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

insertしたい


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

Arrowが欲しい


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

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

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


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

要素を1つだけ持つlistとmapmapcatまたは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に貢献していきたいです。