Clojureで相互再帰最適化

そろそろClojureでのloop/recurによる末尾再帰最適化に慣れてきたんじゃないでしょうか。
Clojureでは相互再帰も最適化されません。例えばこんな例

;; ちょっと変わったみんな大好きFizzBuzz
(declare fizz buzz)

(defn fizz-buzz [n]
  (when (> n 0)
    (print n " = ")
    (fizz n)))

(defn- fizz [n]
  (if (zero? (rem n 3))
    (print 'fizz))
  (buzz n))

(defn- buzz [n]
  (if (zero? (rem n 5))
    (print 'buzz))    
  (println)
  (fizz-buzz (dec n)))




このような再帰もスタックを消費します。手元の環境ではn = 2000でjava.lang.StackOverflowErrorが発生しました。

このような状況を最適化するために用意されている関数は。。。trampolineです。
プログラミングClojureをお持ちの方はP.149を開いてください。さらっと説明されていますｗ

trampolineで最適化したコード

trampoline化させるには返り値の括弧の前に#をつけてクロージャ(closureの方)を返すように修正します。

(declare fizz buzz)

(defn fizz-buzz [n]
  (when (> n 0)
    (print n " = ")
    #(fizz n)))

(defn- fizz [n]
  (if (zero? (rem n 3))
    (print 'fizz))
  #(buzz n))

(defn- buzz [n]
  (if (zero? (rem n 5))
    (print 'buzz))    
  (println)
  #(fizz-buzz (dec n)))

呼び出すときは(trampoline f & args)です。

user> (trampoline fizz-buzz 2000) ; これでjava.lang.StackOverflowErrorが発生しなくなりました!

部分適用でインタフェース改善

このままだと使うとき毎回trampolineを書かなくてはいけなくて面倒ですね。本来渡したいのfizzbuzzの引数だけです。こんなときのためにpartial部分適用があります！
プログラミングClojureをお持ちの方はP.146を開いてください。trampolineの第一引数がfizz-buzzである新しい関数を作っちゃいます。 

(declare fizz buzz)

;; rename
(defn- fizz-buzz-1 [n]
  (when (> n 0)
    (print n " = ")
    #(fizz n)))

(defn- fizz [n]
  (if (zero? (rem n 3))
    (print 'fizz))
  #(buzz n))

(defn- buzz [n]
  (if (zero? (rem n 5))
    (print 'buzz))    
  (println)
  #(fizz-buzz-1 (dec n)))

;; 部分適用
(def fizz-buzz (partial trampoline fizz-buzz-1))

user> (fizz-buzz 2000) ; これでもともと期待していたインタフェースで最適化できました!

面白いですねClojure!
まだプログラミングClojureを買っていない人はぽちりましょう！
プログラミングClojure

Created at : 2010-03-24 01:38:59   Updated at : 2010-03-24 02:34:42
Category : Programming::Lisp::Clojure

Clojrueのmapの使い方（データ構造の方）

Shibuya.lispでClojureはデータ構造が貧弱といわれていましたが、Mapはもうちょっと評価されてもいいと思うので使い方メモ。

Clojure1.1.0で確認。

Map作成

リテラルは{}です。key valueの組み合わせを並べます。必ず要素数は偶数。 またClojureでは半角カンマは空白とみなされるので、key valueの後に半角カンマを入れると見やすい。

user> (def m {:a 1 :b "a" :c 'foo})
#'user/m
user> m
{:a 1, :b "a", :c foo}
user> (class m)
clojure.lang.PersistentArrayMap

リテラルのはArrayMapですね(仕様ではない気がするが)。array-map関数でも作成できます。

user> (def am (array-map :a 1 :b "a" :c 'foo))
#'user/am
user> am
{:a 1, :b "a", :c foo}
user> (class am)
clojure.lang.PersistentArrayMap

HashMapはhash-map関数でつくれます。入力と順番が違う点に注意。

user> (def hm (hash-map :a 1 :b "a" :c 'foo))
#'user/hm
user> hm
{:a 1, :c foo, :b "a"}
user> (class hm)
clojure.lang.PersistentHashMap

sorted-mapもあるよ。

user> (def sm (sorted-map :a 1 :b "a" :c 'foo))
#'user/sm
user> sm
{:a 1, :b "a", :c foo}
user> (class sm)
clojure.lang.PersistentTreeMap

普通のMap

要素取得

(key map)または(map key)の形式で値取得。

user> (:a m)
1
user> (:b m)
"a"
user> (m :a)
1

keyを先頭にできるのはkeyがSymbolかKeywordのときだけだと思う。多分。
この場合、keyを関数のように適用できる利点がある。変な例だけど

user> (map :b [m m m])
("a" "a" "a")

関数ではgetが使える。

user> (get m :a)
1

keyやvalueのシーケンスがほしいときはkeys、valsで。

user> (keys m)
(:a :b :c)
user> (vals m)
(1 "a" foo)

要素追加(更新)

assocです。

user> (def updated-m (assoc m :d 100))
#'user/updated-m
user> updated-m
{:d 100, :a 1, :b "a", :c foo}
user> (assoc m :d 100 :e 200)
{:e 200, :d 100, :a 1, :b "a", :c foo}
user> (assoc m :b 100)
{:a 1, :b 100, :c foo}

immutableなのはいわずもがな。

要素削除

dissocです。

user> (dissoc updated-m :c)
{:d 100, :a 1, :b "a"}
user> (dissoc updated-m :d :c)
{:a 1, :b "a"}

immutableな(ry

ネストしたMap

便利なデータ構造として使うからにはネストしたい。たとえばこんな感じ。

(def nested-map {:lisp {:cl {:c 'sbcl, :java 'abcl},
                        :scheme {:c 'gauche, :java 'kawa}}, 
                 :ruby {:c 'matz-ruby :java 'jruby}})

いままでの知識だけでsbclをaclに変えたいとき、

user> (let [lisp-map (:lisp nested-map),
            cl-map (:cl lisp-map)]
       (assoc lisp-map :lisp (assoc cl-map :c 'acl)))
{:lisp {:c acl, :java abcl}, :cl {:c sbcl, :java abcl}, :scheme {:c gauche, :java kawa}}

こんな感じになります。さらにネストが深くなると。。。目も当てられないことになりますね。
こんなときのためにちゃんと関数が用意されています。

要素追加(更新)

assoc-inです。使い方は(assoc-in m [k & ks] v)。↑の例だと

user=> (assoc-in nested-map [:lisp :cl :c] 'acl)
{:lisp {:cl {:c acl, :java abcl}, :scheme {:c gauche, :java kawa}}, :ruby {:c matz-ruby, :java jruby}}

追加ももちろんできる。

user> (assoc-in nested-map [:lisp :cl :lisp] 'oreore-lisp)
{:lisp {:cl {:lisp oreore-lisp, :c sbcl, :java abcl}, :scheme {:c gauche, :java kawa}}, :ruby {:c matz-ruby, :java jruby}}

ちなみにdissoc-inはない。

要素更新(関数適用版)

現在の要素に関数を適用させて値を更新するupdate-inってのもある。使い方は(update-in m [k & ks] f & args)。
変な例だけど、こんな感じ。 

user> (update-in nested-map [:lisp :cl :c] str "-1.0.36") 
{:lisp {:cl {:c "sbcl-1.0.36", :java abcl}, :scheme {:c gauche, :java kawa}}, :ruby {:c matz-ruby, :java jruby}}

値取得

get-inもあるよー。使い方は(get-in m ks)。

user> (get-in nested-map [:lisp :cl :java])
abcl

なんで(get-in m k & ks)にしなかったんだろ。。(assoc,updateと合わせるためかな。)

とりあえず、mapの使い方はこんな感じです。(他にも破壊的なassoc!、dissoc!もあるけど、使わないほうが良いと思う。)
まあまあ使えると思いませんか？

Created at : 2010-03-23 01:50:57   Updated at : 2010-03-23 03:33:40
Category : Programming::Lisp::Clojure

Clojure+LeiningenでGoogle App Engineアプリ作成!

宣言していた通り、Clojure+Leiningenでやや簡単にGAEアプリをつくれるようにしてみました。
blankプロジェクトはこちら。
Compojureは最新の0.4.0のスナップショットをjarに固めてClojarsにおきました。
leiningenのインストールがまだの場合はこちらを参考にインストールしてください。

Quick Start

Google App Engine SDKを用意していない場合はここからDLしてきてbinディレクトリをパスに追加してください。いまのところ1.3.1対応です(appengine-java-sdk-1.3.1.zip)

$ git clone git://github.com/making/clj-gae-blank.git
$ cd clj-gae-blank
$ lein compile
# 開発版サーバ起動
$ dev_appserver war # -> http://localhost:8080/にアクセスすると「Hello!」と出るはず。
# 本番環境へデプロイ
$ vi war/WEB-INF/appengine-web.xml # applicationタグ内に自分のAPPIDを記入
$ appcfg.sh update war # -> http://APPID.appspot.com/にアクセスすると「Hello!」と出るはず。

あとはソースみていじってください。コードは数行しか書いてないから雰囲気でわかると思います。

注意

  • lein replでwar/WEB-INF/classes, libにパスが通っていないみたいなので、projectホームに、シンボリックリンクを貼った方が良いです。ln -s war/WEB-INF/classes,ln -s war/WEB-INF/lib。lein-swakを使う場合も同様。
  • ローカルサーバ立ち上げた後、コンパイルしてもサーバ再起動しないと反映されません（いまのところ）
  • spinupに10秒くらいかかるのでちょっと遅いです。
  • データストア用の関数はまだ用意していません。
  • Compojure0.3.2と0.4.0は中身が別物。Ringに乗っとられた。CompojureとRingの話は今度記事書く。

Created at : 2010-03-22 06:15:56   Updated at : 2010-03-22 06:31:06
Category : Programming::Lisp::Clojure::Leiningen