Clojure内部のメソッド定義について
最近Clojureのコード読んでたんですが、いたるところ（このへんとか）に
public Object invoke() ; public Object invoke(Object arg1) ; public Object invoke(Object arg1, Object arg2) ; public Object invoke(Object arg1, Object arg2, Object arg3) ; public Object invoke(Object arg1, Object arg2, Object arg3, Object arg4) ;
...といった調子でメソッドが定義されててギョェ〜〜ってなってた。
なんで可変長引数使わないのかよくわからなかったのでIRCに投げてみたところ、可変長引数はコストが大きいんだそうで。だからJVMの速度的な問題でこのような実装になっているとのこと。
うえのinvokeメソッドはClojureの関数を引数に適用するメソッドなわけなのですが、なるほど確かに関数に引数1000個とか渡さないわ。
だったら上の実装が現実的なのね。
instaparseで遊ぶ
この記事はClojure Advent Calendar 2013 - Qiita [キータ]１９日目の記事です。
instaparse
本記事ではinstaparseというライブラリを使って遊んでみます。
instaparseはEBNFやABNFで記述された文脈自由文法から自動的にパーサを生成してくれます。 左再帰、右再帰、曖昧性など、いかなる文脈自由文法でも動作します。 生成されたパーサは文字列からenliveまたはhiccup風の木構造を生成します。
今回は型なしラムダ計算を題材にします。
型なしラムダ計算
型なしラムダ計算は、型がない（または型がひとつしかない）ラムダ計算です。
ラムダ計算はとてもシンプルで、すべての計算が関数定義と関数適用だけで実現可能です。
ラムダ計算の構文は以下の３つからなります。
t ::= 項
x 変数
| \x . t ラムダ抽象
| t t 関数適用
定義くらいはほしいだろう、ということで、今回作るパーサは以下のような拡張をした構文にします。
lang ::= (expr | def)+
def ::= var '=' expr ';'*
expr ::= (var | app | abs)
| '(' app | abs ')' ';'*
var ::= [a-zA-Z-]+
app ::= expr expr
abs ::= '\\' var '->' expr
さて、上の構文を用いてパーサを作ってみます。
(ns lambda.core (:require [instaparse.core :as insta] [clojure.core.match :as match])) (def parser (insta/parser "lang = (expr | def)+ def = <w> var <'='> expr <';'*> <w> <expr> = <w> (var | app | abs | <'('> (app | abs) <')'>) <w> <';'*> var = <w> #'[a-zA-Z-]+' <w> app = expr expr abs = <'\\\\'> var <arrow> expr w = #'[\\n\\s]*' arrow = '->' "))
簡単に書けました。
実行すると以下のような結果が得られます。
(parser "true = \\x -> \\y -> x;") ; => [:lang [:def [:var "true"] [:abs [:var "x"] [:abs [:var "y"] [:var "x"]]]]]
驚きのお手軽感です。
お分かりかとは思いますが、langやdefなどがキーとなった木（ベクタ）ができています。そして< >で囲まれたexprやwは出力結果にはありません。 < >はパース結果を隠す役割があります。他にも正規表現が使えたりと大変便利なライブラリです。
またパース結果をグラフ化することもできます。
(insta/visualize (parser (slurp "sample.lambda")))
せっかくパーサができたので評価できるようにします。
α変換．．．本来だと条件によって置換しなくてもいいこともある。ﾌﾑﾌﾑ〜〜〜。
面倒だし、全部置き換えたところで一緒なので全部置換することにします。
(gensym)でユニークな変数が降ってくるので、\x -> \y -> x yのような形のものを、\unique_symbol -> \y -> \unique_symbol yのように変換します。 そのようにすれば適用する式の中身と変数名がかぶりませんね。
HaskellやOCamlみたいなパターンマッチがClojureにもあったらなーと思っていたら、clojure.core.matchがなかなか良さそうなので使ってみました。
(def env (atom {})) (defn evaluate [expr] (match/match expr [:def v e] (do (swap! env conj {v e}) v) [:var v] (get @env [:var v] [:var v]) [:app [:var v] n] [:app (get @env [:var v] [:var v]) n] [:app [:app m n'] n] [:app (evaluate [:app m n']) n] [:app [:abs [:var v] body] n] (clojure.walk/postwalk (fn [z] (if (= z [:var v]) n z)) (evaluate body)) [:abs [:var v] body] (let [v' (str (gensym))] [:abs [:var v'] (clojure.walk/postwalk (fn [z] (if (= z [:var v]) [:var v'] z)) (evaluate body))]))) (defn show [expr] (match/match expr [:lang & n] (reduce str (map show n)) [:def v e] (str (show v) " = " (show e)) [:var v] v [:app f x] (str "(" (show f) " " (show x) ")") [:abs arg e] (str "^" (show arg) "." (show e)))) (defn evaluate-all [expr] (match/match expr [:app m n] (evaluate-all (evaluate expr)) :else expr)) (let [code (str "true = \\x -> \\y -> x;" ;; "true = ^x.^y.x" "false = \\x -> \\y -> y;" ;; "false = ^x.^y.y" "if = \\p -> \\t -> \\f -> ((p t) f);" ;; "if = ^p.^t.^f.((p t) f)" "cons = \\x -> \\y -> \\f -> ((f x) y);" ;; "cons = ^x.^y.^f.((f x) y)" "car = \\p -> p true;" ;; "car = ^p.(p true)" "cdr = \\p -> p false;" ;; "cdr = ^p.(p false)" "(car ((cons true) false))" ;; "^x.^y.x" "(((if true) false) true)") ;; "^x.^y.y" parsed (parser code) results (map evaluate-all (rest parsed))] (map show results))
Clojureすごい！instaparseすごい！
というわけで、１９日目はこれでおしまいです。
シリコンバレーいってきた
すごいおいしいみたいな印象があったライスクリスピー、久しぶりに食べたらクッソまずかった。
けど友達にも「美味しいよこれ！！！」って言って買わせた手前、美味しいねこれ！って言いながら食べ続けた。
食事は結構美味しかったんだけど、普段一日一杯ジュース飲むだけみたいな生活送ってたせいかお腹壊した。
しかも３日目くらいに熱が出てつらい目にあった。
GoogleとかFacebookとかEvernoteとか色々訪問したけれど、どの国のどの企業でも開発部門と営業企画部門では雰囲気が全然違うなって。
開発部門は暗い部屋にぼうっとディスプレイの光に照らされたおっさんの顔がたくさんあるし、デスクの周りにおいてあるのは美少女なフィギュア。一方企画側はオフィス内で弓矢を飛ばして遊んでいた。
欧米は欧米はっていう人たちもいるらしいけど、日本は最高の国ですわ。 泊まってたのはヒルトンホテルだったんだけど、数ブロック離れるとあら不思議マリファナの匂い。というかもう道がめちゃくちゃ汚い。
日本サイコー。
まじで。
macroless unless
(defn unless [test then else] (if test (else) (then))) (unless true #(println "hello") #(println "good bye")) good bye nil
素直にマクロ使おう。
Clojure：binding と遅延シーケンス
Clojure in Action読んでて、へえってなったのでメモ。
当然と言えば当然なのかもしれないけれど。
(def ^:dynamic *factor* 10) (defn multiply [x] (* x *factor*)) (map multiply [1 2 3]) (binding [*factor* 20] (map multiply [1 2 3]))
Clojure の var はbindingで束縛することができる。
しかし直感に反して上のどちらのmapも [10 20 30] を返す。
これはなぜかというと、mapのような関数は遅延シーケンスを返すからで、この遅延シーケンスは必要となるまで評価されない。そして評価が実際に行われたときはすでにbindingフォームの外であるので、 factor も元々の10に戻っている。
これを意図したようにするには
(binding [*factor* 20] (doall (map multiply [1 2 3])))
とする必要がある。
どうてきすこーぷ、気をつけよう。
なんかこれ同じようなことをDBでもやったような気がする。
DBのコネクションをラップしたマクロが用意されてて、そいつが返すのは遅延シーケンスだということに気づかず、コネクションを閉じる前に結果を現実化しなかったせいでDBから結果が返ってきてないように見えて慌てたような。
- 作者: Amit Rathore
- 出版社/メーカー: Manning Pubns Co
- 発売日: 2011/11/28
- メディア: ペーパーバック
- クリック: 24回
- この商品を含むブログ (2件) を見る
パーサの連接とか
前回までに出てきた基本的なパーサをくっつけることで複雑なパーサが書けるわけですが、 今回はそのような連接とかを手助けしてくれるパーサコンビネータを紹介？します。
Kern のパーサコンビネータはシーケンス化、反復、選択、それと括弧の対応とかの面倒を見てくれるみたいです。
例のごとく kern をロード。
(use 'blancas.kern.core)
skip-ws は入力のはじめにあるすべての空白をスキップ。
doc.core> (run (skip-ws letter) "\t \n x") \x nil
<|> はあたえられたパーサを成功するまで試す。すべてのパーサが失敗するか、入力を消費するパーサが失敗すると全体として失敗する。
doc.core> (run (<|> digit letter) "x") \x nil doc.core> (run (<|> digit letter) "9") \9 nil doc.core> (run (<|> digit letter tab) "?") line 1 column 1 unexpected \? expecting digit, letter or tab nil
で、 >> は１つ以上のパーサを適用する。最後のパーサの結果だけを返す。
doc.core> (run (>> digit digit letter) "91x") \x nil
<< は１つ以上のパーサを適用する。最初のパーサの結果だけを返す。
doc.core> (run (<< upper (sym* \-) digit digit) "F-16") \F nil
<$> は与えられたパーサを入力に適用して、そのあとパースした結果に対して与えられた関数を適用、その結果を返す。
doc.core> (run (<$> #(* % %) dec-num) "12") 144 nil
<*> は２つ以上のパーサを適用して、それらの結果をベクタにして返す。
doc.core> (run (<*> dec-num tab oct-num tab hex-num) "737\t747\tA340") [737 \tab 487 \tab 41792] nil
<:> はバックトラックするパーサらしい。もし失敗しても消費した入力は回復。
doc.core> (:input (parse (<:> float-num) "5005.a")) (\5 \0 \0 \5 \. \a)
many は入力に対しパーサを０回以上、失敗するまで適用。many1 は１回以上で、最低１回生功しないと失敗。
doc.core> (run (many letter) "123") [] nil doc.core> (run (many letter) "xyz") [\x \y \z] nil doc.core> (run (many1 letter) "xyz") [\x \y \z] nil doc.core> (run (many1 letter) "123") line 1 column 1 unexpected \1 expecting letter nil
optional はパーサが成功するか消費を行わかなった場合に全体として成功する。
doc.core> (run (<+> (optional (sym* \-)) dec-num) "-45") "-45" nil doc.core> (run (<+> (optional (sym* \-)) dec-num) "45") "45" nil doc.core> (run (<+> (optional float-num) letter) "45.A") line 1 column 4 unexpected \A expecting digit nil
option は与えられたパーサを適用する。もし入力を消費せずに失敗したら、与えられた値を結果として返すっぽい。
doc.core> (run (option 3.1416 float-num) "foo") 3.1416 nil
skip は１つ以上のパーサを取ってそれらの結果をすべて飛ばす。結果として nil を返す。
doc.core> (run (skip letter digit letter digit) "A5E8") nil nil
skip-many はパーサを０回以上適用し結果を飛ばす。nil を返す。skip-many は１回以上。
doc.core> (run (skip-many letter) "xyz") nil nil doc.core> (run (skip-many1 letter) "xyz") nil nil doc.core> (run (skip-many1 letter) "123") line 1 column 1 unexpected \1 expecting letter nil
sep-by は与えられたパーサによって分けたものに対して別のパーサを０回以上適用する。sep-by1 は１回以上。
doc.core> (run (sep-by (sym* \&) (many1 letter)) "a&bb&ccc&ddd") [[\a] [\b \b] [\c \c \c] [\d \d \d]] nil
end-by は与えられたパーサによって別れる/終わるものに対して別のパーサを０回以上適用する。end-by1 は１回以上。
doc.core> (run (end-by (sym* \&) (many1 letter)) "a&bb&ccc&") [[\a] [\b \b] [\c \c \c]] nil
between は1,2つ目のパーサの間のちに対して３つ目のパーサを適用する。
doc.core> (run (between (sym \() (sym \)) dec-num) "(1984)") 1984 nil
<+> はひとつ以上のパーサをとる。で、結果を潰してくっつけて、文字列にする。
doc.core> (run (<+> letter (many alpha-num)) "a177") "a177" nil
