tools.macroを使ってLet Over Lambdaのパンドリックマクロを実装する
(このエントリは Clojure Contrib Library Advent Calendar 18日目の記事です。)
はじめに
今回のネタはtools.macroです。
tools.macroは,ライブラリのREADMEによれば「マクロを書くためのツール」という位置づけで,現在提供している主要な機能はmacroletとsymbol-macroletです。これらは,Common Lispの同名の特殊形式と同じように,それぞれローカルマクロとシンボルマクロを定義するのに使うことができます。Clojureは,(少なくとも現時点では)ローカルマクロやシンボルマクロを言語としてサポートしていないため,そういった機能が必要な複雑なマクロを定義する場合等にはtools.macroのマクロを使うのが便利です。
インストール
2013年12月現在のtools.macroの最新版は0.1.2です。tools.macroをインストールするには,Leiningenを使用している場合はproject.cljの:dependenciesに以下を追加します。
[org.clojure/tools.macro "0.1.2"]
使い方
macroletはletfnと同じ形式でローカルマクロを定義します。
(defn foo [x flag] (macrolet [(f [x] `(if ~'flag (* ~x ~x) ~x))] (+ x (f x) (f (+ x 1)))))
これは以下と等価です。
(defn foo [x flag] (+ x (if flag (* x x) x) (if flag (* (+ x 1) (+ x 1)) (+ x 1))))
symbol-macroletはletと同じ形式でシンボルマクロを定義します。
(symbol-macrolet [x 'foo] (list x (let [x 'bar] x)))
これは以下のように展開されます。
(list 'foo (let [x 'bar] x))
この展開結果を見ても分かるように,macroletやsymbol-macroletはマクロと同名のシンボルが出現する箇所を盲目的に置き換えるのではなく,Clojureの構文を理解してマクロの展開が可能な位置を認識します。コードウォークが必要なマクロを定義する場合は,この観点から,むやみにclojure.waok/postwalkなどの関数を使うのではなく,macroletやsymbol-macroletを使う方が安全です。
例
ここでは,シンボルマクロの応用例として,Let Over Lambdaに登場するパンドリックマクロを実装してみます。
パンドリックマクロ
パンドリックマクロ(pandoric macros)とは,クロージャが捕捉しているローカルな環境に,その環境の外側から(見かけ上)アクセスできるようにするマクロです。本来,外側からはアクセスできないはずのローカル環境に無理矢理アクセスする禁忌を,「パンドラの箱」を開けることになぞらえてこの名前がつけられています。
外側からローカル環境にアクセス可能なクロージャを作るためにはpfnマクロを使います。
user=> (def f (let [x 42] (pfn [y] [x] (* x y)))) #'user/f user=> (f 2) 84 user=>
pfnの第1引数は通常の引数リストです。第2引数には外からアクセス可能にする変数を指定します。上の例ではクロージャが捕捉するローカル変数xをアクセスできるようにしています。pfnで生成されたクロージャはもちろん通常のクロージャと同じように関数適用できます。
pfnでアクセス可能にした変数の値を取得するにはwith-pandoricマクロを使います。
user=> (with-pandoric [x] f #_=> (println "the value of closed variable x is:" x)) the value of closed variable x is: 42 nil user=>
with-pandoricマクロの第1引数では,pfnで作ったクロージャでアクセス可能にした変数のうち,with-pandoricのボディで実際にアクセスする変数を指定します。第2引数にはpfnで作ったクロージャを渡します。上の例では,fで捕捉された変数xの値42がwith-pandoric内で取得できています。
実装
このようなマクロpfnおよびwith-pandoricをシンボルマクロを使って作ってみましょう。実装は以下のようになります:
(ns contrib-calendar.tools.macro (:require [clojure.tools.macro :refer [symbol-macrolet]])) (defmacro pfn [args pargs & body] `(let [f# (fn ~args ~@body)] (fn [& args#] (if (= (first args#) ::pandoric-get) (case (second args#) ~@(mapcat #(list % %) pargs) (throw (Exception. (str "Unknown pandoric get: " (second args#))))) (apply f# args#))))) (defmacro with-pandoric [syms f & body] (let [gf (gensym)] `(let [~gf ~f] (symbol-macrolet [~@(mapcat #(list % `(~gf ::pandoric-get '~%)) syms)] ~@body))))
パンドリックマクロの使用例
pfnとwith-pandoricを使って,リセット可能なカウンタを作ってみましょう。
(defn make-counter [] (let [x (atom 0)] (pfn [] [x] (swap! x inc) @x)))
これを以下のように使います。
user=> (def c (make-counter)) #'user/c user=> (c) 1 user=> (c) 2 user=> (c) 3 user=> (with-pandoric [x] c #_=> (reset! x 0)) 0 user=> (c) 1 user=> (c) 2 user=>
おわりに
今回はtools.macroが提供するmacroletとsymbol-macroletを紹介しました。また,シンボルマクロの使用例としてLet Over Lambdaのパンドリックマクロを実装しました。
ここではmacroletの実用例については詳しく見ていませんが,(手前味噌ですが)たとえば以下のようなマクロが参考になるかもしれません。
- trampolineを使わないで相互末尾再帰を末尾再帰最適化するマクロ
- optimizing mutual tail recursion without trampoline
- ローカル関数をメモ化再帰できるようにするマクロ
- ローカルな関数でメモ化再帰できるようにするマクロをClojureで - Qiita [キータ]
data.priority-mapを使ってダイクストラ法で迷路を解く
(このエントリは Clojure Contrib Library Advent Calendar 14日目の記事です。)
はじめに
今回はdata.priority-mapについてです。以前はclojure.contrib.priority-mapと呼ばれていました。
data.priority-mapは優先度つきマップ(priority map)の実装を提供します。優先度つきマップは,Clojureコアが提供するソートされたマップ(sorted map)と非常に類似したデータ構造です。両者の違いは,ソートされたマップがキーによってソートされるのに対し,優先度つきマップは値によってソートされるという点です。
今回は,data.priority-mapの基本的な使い方と,優先度つきマップの応用例としてダイクストラ法を使って迷路を解く例を見ます。
インストール
data.priority-mapを使う際は,Leiningenを使ってる場合,project.cljの:dependenciesに
[org.clojure/data.priority-map "0.0.4"]
を追加します。2013年12月現在の最新版は0.0.4です。
使い方
優先度つきマップを作るにはclojure.data.priority-map/priority-mapという関数を使います。この関数はClojureコアのarray-mapやsorted-mapと同じように使うことができます。
user=> (require '[clojure.data.priority-map :as p]) nil user=> (def xs (p/priority-map :a 3 :b 1 :c 4 :d 1 :e 5)) #'user/xs user=> xs {:b 1, :d 1, :a 3, :c 4, :e 5} user=>
Clojureコアが提供するその他のマップと同じように,優先度つきマップへのエントリの追加やキーに対応する値を引くことができます。
user=> (assoc xs :f 0) {:f 0, :b 1, :d 1, :a 3, :c 4, :e 5} user=> (conj xs [:f 0]) {:f 0, :b 1, :d 1, :a 3, :c 4, :e 5} user=> (xs :c) 4 user=> (:c xs) 4 user=>
優先度の一番高い値をもつエントリを取得するにはpeekを使います。また,優先度の一番高い値をもつエントリを除くにはpopを使います。
user=> (peek xs) [:b 1] user=> (pop xs) {:d 1, :a 3, :c 4, :e 5} user=>
比較関数を指定して優先度つきマップを作るには,clojure.data.priority-map/priority-map-byを使います。
user=> (def ys (p/priority-map-by > :a 3 :b 1 :c 4 :d 1 :e 5)) #'user/ys user=> ys {:e 5, :c 4, :a 3, :b 1, :d 1} user=> (peek ys) [:e 5] user=>
マップに持たせる値から優先度を計算する方法をカスタマイズしたい場合は,clojure.data.priority-map/priority-map-keyfnが使えます。以下の例では,2つ組を表すベクタを値としてマップに持たせ,各ベクタの2つめの要素を優先度として扱っています。
user=> (def zs (p/priority-map-keyfn second :a ["a" 2] :b ["b" 7] :c ["c" 1] :d ["d" 8] :e ["e" 2])) #'user/zs user=> zs {:c ["c" 1], :a ["a" 2], :e ["e" 2], :b ["b" 7], :d ["d" 8]} user=> (peek zs) [:c ["c" 1]] user=>
例
data.priority-mapの使い方が分かったところで,優先度つきマップを使った応用例として,ダイクストラ法を使った迷路の解法を見てみましょう。
お題となる迷路は,以前にこのブログでも話題として出した以下のブログ記事からとってきました。
以下のサンプルプログラムでは,ダイクストラ法による解法と合わせて,以前に書いた単純な幅優先探索による解法(を一部書き直したもの)も比較のために示しています。
(ns contrib-calendar.data.priority-map (:require [clojure.data.priority-map :as p] [clojure.java.io :refer [reader]]) (:import clojure.lang.PersistentQueue)) (defn value-at ([maze [y x]] (value-at maze y x)) ([maze y x] ((maze y) x))) (defn nrows [maze] (count maze)) (defn ncols [maze] (count (maze 0))) (defn neighbors [maze [y x]] (for [[dy dx] [[0 1] [1 0] [0 -1] [-1 0]] :let [y (+ y dy), x (+ x dx)] :when (not= \* (value-at maze y x))] [y x])) ; 幅優先探索による解法 (defn breadth-first-search ([maze start] (breadth-first-search maze (conj PersistentQueue/EMPTY [start [start]]) #{})) ([maze candidates visited] (let [[pos path] (peek candidates)] (cond (nil? pos) nil (= (value-at maze pos) \G) path :else (recur maze (into (pop candidates) (for [neighbor (neighbors maze pos) :when (not (visited neighbor))] [neighbor (conj path neighbor)])) (conj visited pos)))))) ; ダイクストラ法による解法 (defn dijkstra-algorithm ([maze start] (dijkstra-algorithm maze (p/priority-map-keyfn count start [start]) #{})) ([maze candidates visited] (let [[pos path] (peek candidates)] (cond (nil? pos) nil (= (value-at maze pos) \G) path :else (recur maze (merge-with #(if (> (count %1) (count %2)) %2 %1) (pop candidates) (->> (for [neighbor (neighbors maze pos) :when (not (visited neighbor))] [neighbor (conj path neighbor)]) (into {}))) (conj visited pos)))))) (defn search-start [maze] (first (for [y (range (nrows maze)), x (range (ncols maze)) :when (= \S (value-at maze y x))] [y x]))) (defn print-solution [maze path] (let [ncols (ncols maze), path? (apply hash-set path)] (doseq [y (range (nrows maze)), x (range ncols) :let [v (value-at maze y x)]] (if (and (path? [y x]) (not (#{\S \G} v))) (print \$) (print v)) (when (= x (dec ncols)) (newline))))) (defn -main [& args] (with-open [r (reader (first args))] (let [maze (vec (map vec (line-seq r))) start (search-start maze) bench (fn [strategy] (let [solution (time (strategy maze start))] (print-solution maze solution)))] (print "breadth first search: ") (bench breadth-first-search) (newline) (print "dijkstra algorithm: ") (bench dijkstra-algorithm) (newline))))
以下が実行例です。
$ cat maze.txt ************************** *S* * * * * * * ************* * * * * ************ * * * * ************** *********** * * ** *********************** * * G * * * *********** * * * * ******* * * * * * ************************** $ lein run -m contrib-calendar.data.priority-map maze.txt breadth first search: "Elapsed time: 902.255 msecs" ************************** *S* * $$$$ * *$* *$$* $************* * *$* $$* $$************ * *$$$$* $$$$$ * **************$*********** * $$$$$$$$$$$$$ * **$*********************** * $$$$$* $$$$$$$$$$$$$G * * * $$$$*********** * * * * ******* * * * * * ************************** dijkstra algorithm: "Elapsed time: 38.862 msecs" ************************** *S* * $$$ * *$* *$$*$ ************* * *$*$$$* $ ************ * *$$$ * $$$$$$$ * **************$*********** * $$$$$$$$$$$$$ * **$*********************** * $$$ *$$$$$$$$$$$$$$G * * *$$$$$ *********** * * * * ******* * * * * * ************************** $
ダイクストラ法を使った場合の方が単純な幅優先探索よりも効率的に最短経路を探索できているのが分かります。よく見ると,得られる解が両者でところどころ違っているのもおもしろいですね。
おわりに
今回は,data.priority-mapが提供する優先度つきマップの使い方と,その応用例としてダイクストラ法で迷路を解く例を見ました。
data.finger-tree: フィンガーツリー
(このエントリは Clojure Contrib Library Advent Calendar 13日目の記事です。)
はじめに
今回はdata.finger-treeについてです。data.finger-treeは名前が示すとおり,フィンガーツリーの実装を提供します。Wikipediaによれば,フィンガーツリーは以下のようなデータ構造です:
2-3フィンガーツリー(2-3 finger tree、または単にfinger tree)とは、列を表す永続データ構造の一種であり、償却定数時間で両端への追加・削除が可能であり、対数時間で連結・分割・挿入が可能である。また、分割演算を変更すると優先度つきキューや探索木などを実装できる。
2-3 フィンガーツリー - Wikipedia
data.finger-treeでは,先頭と末尾に定数時間でアクセス可能な「ダブルリスト」と呼ぶデータ構造とその亜種,およびフィンガーツリーを使って独自のデータ構造を作るためのインタフェースが提供されています。
今回は,ダブルリストとその亜種の使い方について見てみます。
インストール
data.finger-treeを使うには,Leiningenのproject.cljへ依存ライブラリとして以下を追加します。
[org.clojure/data.finger-tree "0.0.1"]
使い方
以下は各データ構造に関する特徴的な関数です。
- double-list
- (double-list & args): 引数に与えられた値を要素にもつダブルリストを生成します
- (consl s a): ダブルリストの先頭に要素を追加します
- (conjr s a): ダブルリストの末尾に要素を追加します
- (ft-concat t1 t2): 2つのダブルリストを連結します
- counted-double-list (定数時間のcountをサポートしたダブルリスト)
- (counted-double-list & args): 引数に与えられた値を要素にもつcounted double listを生成します
- (ft-split-at o k): ダブルリストをインデックスkの位置で分割します
- counted-sorted-set (counted double listに似たsorted set)
- (counted-sorted-set & args): 引数に与えられた値を要素にもつcounted sorted setを生成します
例
以下,実際の使用例です。
user=> (use 'clojure.data.finger-tree) nil user=> (def xs (double-list 1 2 3)) #'user/xs ; conslで先頭に要素を追加できる user=> (consl xs 0) (0 1 2 3) ; conjrで末尾に要素を追加できる user=> (conjr xs 4) (1 2 3 4) ; ft-concatで2つのダブルリストを連結できる user=> (ft-concat xs xs) (1 2 3 1 2 3) user=> (def ys (counted-double-list 1 2 3)) #'user/ys ; counted double listは定数時間のcountをサポート user=> (count ys) 3 ; ダブルリストと同様に,consl, conjr, ft-concatも適用できる user=> (consl ys 0) (0 1 2 3) user=> (conjr ys 4) (1 2 3 4) user=> (ft-concat ys ys) (1 2 3 1 2 3) ; ft-split-atでリストを分割できる user=> (ft-split-at ys 1) [(1) 2 (3)] user=>
おわりに
今回はdata.finger-treeが提供する種々のデータ構造について見てみました。
フィンガーツリー自体について,詳しく知りたい場合は以下が参考になります。
次回は,さらにデータ構造つながりでdata.priority-mapについて書きます。
core.rrb-vector: 新しいベクタの実装
(このエントリは,Clojure Contrib Library Advent Calendar 12日目の記事です。)
はじめに
今回のネタはcore.rrb-vectorです。core.rrb-vectorは2013年1月にContribライブラリに入った比較的新しいライブラリです。
core.rrb-vectorが提供するのは,新しいベクタの実装です。core.rrb-vectorで実装されるベクタはRRB(Relaxed Radix Balanced)木に基づいています。
RRB木の特徴は,現在のClojureコアのベクタの実装である32分木のO(log(N))でのインデクシングや更新に加え,O(log(N))の連結操作とスライシングを備えていることです。
32分木 | RRB木 | |
インデクシング | O(log(N)) | O(log(N)) |
更新 | O(log(N)) | O(log(N)) |
連結 | O(N) | O(log(N)) |
スライシング | O(1) | O(log(N)) |
core.rrb-vectorが提供する連結およびスライシングのための関数は,Clojureコアのベクタを混在させて使用できるため,コアのベクタからrrb-vectorへシームレスに移行することができます。
このようなClojureコアとの互換性の高さや,Reducers方面への応用に対する期待から,将来コア側へ取り込まれることも視野に入れながらcore.rrb-vectorの開発は進められています。
インストール
core.rrb-vectorを実際に使ってみるには,Leiningenを使っている場合は:dependenciesに
[org.clojure/core.rrb-vector "0.0.9"]
を追加すればOKです。弱冠バージョン0.0.9ということで,位置づけとしてはまだアルファ版です。
使い方
では,core.rrb-vectorを使ってみましょう。
ベクタを生成するには,clojure.core.rrb-vector/vectorを使います。生成したベクタはClojureコアのベクタと同じように使うことができます。
user=> (require '[clojure.core.rrb-vector :as v]) nil user=> (def v (v/vector 1 2 3)) #'user/v user=> (class v) clojure.core.rrb_vector.rrbt.Vector user=> (first v) 1 user=> (next v) (2 3) user=> (conj v 4) [1 2 3 4] user=>
ベクタの連結とスライシングにはそれぞれclojure.core.rrb-vector/catvecおよびclojure.core.rrb-vector/subvecを使用します。
user=> (v/catvec (v/vector 1 2 3) (v/vector 4 5 6)) [1 2 3 4 5 6] user=> (v/subvec *1 2 5) [3 4 5] user=>
先述したように,catvecとsubvecはClojureコアのベクタを混ぜても使うことができます。
user=> (v/catvec [1 2 3] (v/vector 4 5 6)) [1 2 3 4 5 6] user=> (class *1) clojure.core.rrb_vector.rrbt.Vector user=> (v/subvec [1 2 3 4 5 6] 1 3) [2 3] user=> (class *1) clojure.core.rrb_vector.rrbt.Vector user=>
ベンチマーク
せっかくなので,ベンチマークもとってみましょう。以下のようなプログラムで,ベクタの連結にかかる時間を計測します。
(ns contrib-calendar.core.rrb-vector) (defn bench [vec concat] (doseq [n [100000 200000 500000 1000000 2000000 5000000]] (dotimes [_ 5] (let [v1 (vec (range n)), v2 (vec (range n))] (time (concat v1 v2)))) (newline)))
以下,ベンチマークの実行結果です。
user=> (require '[contrib-calendar.core.rrb-vector :refer [bench]]) nil user=> (require '[clojure.core.rrb-vector :as v]) nil user=> (bench vec into) "Elapsed time: 2.652 msecs" "Elapsed time: 2.643 msecs" "Elapsed time: 3.013 msecs" "Elapsed time: 2.605 msecs" "Elapsed time: 2.89 msecs" "Elapsed time: 5.589 msecs" "Elapsed time: 7.535 msecs" "Elapsed time: 5.539 msecs" "Elapsed time: 5.944 msecs" "Elapsed time: 5.659 msecs" "Elapsed time: 22.922 msecs" "Elapsed time: 16.553 msecs" "Elapsed time: 14.555 msecs" "Elapsed time: 14.104 msecs" "Elapsed time: 14.567 msecs" "Elapsed time: 28.71 msecs" "Elapsed time: 29.276 msecs" "Elapsed time: 30.195 msecs" "Elapsed time: 33.978 msecs" "Elapsed time: 27.959 msecs" "Elapsed time: 59.322 msecs" "Elapsed time: 58.319 msecs" "Elapsed time: 55.902 msecs" "Elapsed time: 57.206 msecs" "Elapsed time: 58.474 msecs" "Elapsed time: 145.583 msecs" "Elapsed time: 131.498 msecs" "Elapsed time: 130.354 msecs" "Elapsed time: 130.446 msecs" "Elapsed time: 130.875 msecs" nil user=> (bench v/vec v/catvec) "Elapsed time: 3.138 msecs" "Elapsed time: 0.586 msecs" "Elapsed time: 0.623 msecs" "Elapsed time: 0.624 msecs" "Elapsed time: 0.743 msecs" "Elapsed time: 0.7 msecs" "Elapsed time: 0.64 msecs" "Elapsed time: 0.669 msecs" "Elapsed time: 0.786 msecs" "Elapsed time: 0.685 msecs" "Elapsed time: 0.9 msecs" "Elapsed time: 0.919 msecs" "Elapsed time: 0.889 msecs" "Elapsed time: 1.031 msecs" "Elapsed time: 0.896 msecs" "Elapsed time: 1.035 msecs" "Elapsed time: 0.91 msecs" "Elapsed time: 0.906 msecs" "Elapsed time: 0.902 msecs" "Elapsed time: 0.901 msecs" "Elapsed time: 4.438 msecs" "Elapsed time: 0.913 msecs" "Elapsed time: 0.914 msecs" "Elapsed time: 0.945 msecs" "Elapsed time: 0.618 msecs" "Elapsed time: 0.807 msecs" "Elapsed time: 0.972 msecs" "Elapsed time: 0.76 msecs" "Elapsed time: 0.693 msecs" "Elapsed time: 0.726 msecs" nil user=>
Clojureコアのベクタの方は綺麗に線形に時間が増加しているのが分かります。一方,RRBベクタの方はほとんど連結にかかる時間が変わっていません。これだけ速いとちょっとどこか計測の仕方が間違ってるのかと心配になりますが,大丈夫でしょうか…?(^^;
tools.loggingを使ってSLF4J+Logbackでログをとる
(このエントリは, Clojure Contrib Library Advent Calendar 9日目の記事です。)
概要
今日紹介するライブラリはtools.loggingです。tools.loggingは,Javaで実装されたいくつかのロギングライブラリを,共通したインタフェースでClojureから使えるようにするライブラリです。デフォルトでサポートされているロギングライブラリは以下のとおりです。
また,tools.loggingで定義されているプロトコルを実装することにより,それ以外のライブラリもtools.loggingから使用可能になります。
今回は,tools.loggingを使って,実際にSLF4JとLogbackでログを出力する方法を見てみます。
インストール・設定
tools.loggingを使用するためには,tools.logging自体とtools.loggingから使用するライブラリの両方を依存ライブラリとして追加する必要があります。SLF4Jやcommons-loggingを使う場合にはさらに,それらが実装として使用するロギングライブラリやアダプタを依存ライブラリとして追加します。
今回はSLF4JからLogbackを使用するので,tools.loggingとそれらのライブラリをLeiningenのproject.cljへ依存ライブラリとして追加します。
[org.clojure/tools.logging "0.2.6"] [org.slf4j/slf4j-api "1.7.0"] [ch.qos.logback/logback-classic "1.0.13"]
また,Logbackを使用するにあたり,設定ファイルのlogback.xmlをクラスパスの通った適当な場所へ配置します。今回の例では以下のような,コンソールへ出力するだけの単純な設定を使います。
<configuration> <appender name= "STDOUT" class= "ch.qos.logback.core.ConsoleAppender"> <encoder> <pattern>%d {HH:mm:ss.SSS} [%thread] %-5level %logger {36} - %msg%n</pattern> </encoder> </appender> <root level= "debug"> <appender-ref ref= "STDOUT" /> </root> </configuration>
使い方
tools.loggingの使い方は至って簡単です。ログを出力したい箇所で各ログレベルに対応したマクロを呼び出せばいいだけです。
- (trace message & more)
- (debug messsage & more)
- (info message & more)
- (warn message & more)
- (error message & more)
- (fatal message & more)
各マクロと実際のログレベルの対応は,tools.loggingから呼び出されるライブラリに依存します。たとえば,今回のようにSLF4Jを使う場合には, (SLF4JにFATALに対応するログレベルがないため)errorマクロとfatalマクロのどちらを呼んでもERRORレベルのログとして扱われます。
例
tools.loggingを使った以下のようなHello Worldを実行してみましょう。
(ns contrib-calendar.tools.logging (:require [clojure.tools.logging :as log]) (:gen-class)) (defn -main [& args] (log/info "Hello, World!"))
以下が実行結果です。ログ出力ができました。
$ lein run -m contrib-calendar.tools.logging 15:14:45.040 [main] INFO contrib-calendar.tools.logging - Hello, World! $
おわりに
今回はtools.loggingを使ったSLF4JとLogbackでのログ出力の方法について紹介しました。
tools.loggingを使っていると,ロギングライブラリの設定のためにXMLやプロパティファイルを書く必要のあるシチュエーションがよくあります。そういった設定ファイルの記述が面倒だと思う方は,設定がClojureで記述できるなど,よりハイレベルな機能を提供するロギングツールである Timbreや,ロギングの設定に特化した clj-logging-configのようなライブラリを使ってみるといいかもしれません。
次回は@halcat0x15aさんで,data.codecについてです。
core.matchを使って算術式インタプリタを実装する
(このエントリは Clojure Contrib Library Advent Calendar 8日目の記事です。)
はじめに
今回のネタは,Clojureのパターンマッチライブラリであるcore.matchです。パターンマッチは,Lispのマクロの応用的な例として本などのネタで取り上げられることが多いですが,データ構造によって処理を分岐したり,複雑なデータの中から一部を取り出す場合などに実際に使える便利な機能です。
今回はこのcore.matchを使って型システム入門の3,4章に出てくる算術式のインタプリタを実装します。
なお,core.matchを使用する場合には,Leiningenのproject.cljに以下を追加する必要があります。2013年12月現在の最新版は0.2.0-rc6です。
[org.clojure/core.match "0.2.0-rc6"]
パターンマッチ
core.matchでは,matchというパターンマッチマクロが提供されています。matchマクロの構文はこのようになっています。
(match [<式1> <式2> ...] [<パターン11> <パターン12> ...] <アクション1> [<パターン21> <パターン22> ...] <アクション2> ... :else <アクションN>)
matchマクロはまず,<式1>, <式2>, ... を評価します。
次に,評価の結果として得られた値 v1, v2, ... が <パターン11>, <パターン12>, ... を満たすかどうかを確かめます。値 v1, v2, ... がそれぞれ <パターン11>, <パターン12>, ... を満たす場合,<アクション1>が実行されます。<パターン11>, <パターン12>, ... を満たさない場合には,次のパターンである <パターン21>, <パターン22>, ... を満たすかどうかを試します。以降同様に,マッチするパターンが見つかるまで順にパターンが試されます。
すべてのパターンにマッチしなかった場合には,:else節に記述された<アクションN>が実行されます。:else節は省略することもできますが,その際にはマッチするパターンが見つからなかった場合に例外が投げられます。
実際にmatchマクロを使ってみましょう。以下はmatchを使ったFizzBuzzの例です。
user=> (require '[clojure.core.match :refer [match]]) nil user=> (defn fizzbuzz [x] #_=> (match [(mod x 3) (mod x 5)] #_=> [0 0] :fizzbuzz #_=> [0 _] :fizz #_=> [_ 0] :buzz #_=> :else x)) #'user/fizzbuzz user=> (map fizzbuzz (range 1 16)) (1 2 :fizz 4 :buzz :fizz 7 8 :fizz :buzz 11 :fizz 13 14 :fizzbuzz) user=>
ベクタのパターンマッチは単純です。
user=> (match [[1 2 3]] #_=> [[1 1 1]] :a0 #_=> [[1 2 3]] :a1 #_=> :else :a2) :a1 user=>
マップのパターンマッチは,パターンに指定したキーのみに対してパターンにマッチするかどうかが確かめられます。そのため,パターンに現れないキーをマップが持っていることはパターンにマッチするかどうかに影響を与えません。
user=> (match [{:a 0, :b 1, :c 2}] #_=> [{:a a, :b b}] [a b] #_=> :else nil) [0 1] user=>
シーケンスのパターンマッチはちょっと複雑で,ベクタのパターンを(... :seq)で囲んでやる必要があります。
user=> (match ['(1 2 3)] #_=> [([1 1 1] :seq)] :a0 #_=> [([1 2 3] :seq)] :a1 #_=> :else :a2) :a1 user=>
この例からも分かるように,( )はパターン内でリストやシーケンスを表すパターンとしては扱われず,:seqや(ここでは詳しく触れませんが)ガードやアズパターンなどの特殊なパターンで使われるので注意が必要です。
パターンマッチの対象となる値が1つの場合は,matchマクロの第1引数の[ ]と,各パターンの外側の[ ]を省略することができます。なので,上のシーケンスのパターンマッチの例は以下のようにも書けます。
(match '(1 2 3) ([1 1 1] :seq) :a0 ([1 2 3] :seq) :a1 :else :a2)
この他にもさまざまなパターンが用意されていますが,詳しくはcore.matchのWikiを見るのがいいでしょう。
算術式インタプリタの実装
さて,それではcore.matchの応用例として,型システム入門の3,4章に出てくる算術式のインタプリタを実装してみましょう。
ここで扱う算術式の項は以下のとおり。
- 0, true, false
- (succ <項>)
- (pred <項>)
- (if <項> <項> <項>)
- (zero? <項>)
この算術式の各項の大まかな振る舞いは次のとおり。
- (succ t)はtの後者値
- (pred t)はtの前者値を返す。tが0の場合は0を返す。
- (zero? t)はtが0の場合にtrueを返し,それ以外の場合にはfalseを返す
- (if t1 t2 t3)はt1がtrueの場合にt2の評価結果を返し,falseの場合にt3の評価結果を返す
この算術式のインタプリタを,core.matchを使って実装したのが以下のコードです*1。
(ns contrib-calendar.core.match (:refer-clojure :exclude [eval]) (:require [clojure.core.match :refer [match]])) (defn- numeric-val? [t] (match t 0 true (['succ t1] :seq) (numeric-val? t1) :else false)) (defn- eval1 [t] (match t (['if true t2 t3] :seq) t2 (['if false t2 t3] :seq) t3 (['if t1 t2 t3] :seq) (let [t1' (eval1 t1)] (list 'if t1' t2 t3)) (['succ t1] :seq) (let [t1' (eval1 t1)] (list 'succ t1')) (['pred 0] :seq) 0 (['pred (['succ (nv1 :guard numeric-val?)] :seq)] :seq) nv1 (['pred t1] :seq) (let [t1' (eval1 t1)] (list 'pred t1')) (['zero? 0] :seq) true (['zero? (['succ (nv1 :guard numeric-val?)] :seq)] :seq) false (['zero? t1] :seq) (let [t1' (eval1 t1)] (list 'zero? t1')) :else (throw (Exception.)))) (defn- eval [t] (try (let [t' (eval1 t)] (eval t')) (catch Exception _ t))) (defn arith [] (print "arith=> ") (flush) (when-let [t (read *in* false nil)] (let [t' (eval t)] (prn t') (recur))))
実行例はこんな感じになります。
user=> (use 'contrib-calendar.core.match) nil user=> (arith) arith=> (succ (pred (succ (succ 0)))) (succ (succ 0)) arith=> (if (zero? (succ 0)) (succ 0) (pred 0)) 0 arith=>
おわりに
今回はcore.matchによるパターンマッチを紹介しました。パターンマッチを使うと,コードの見通しがよくなることもあるので,使える場面では積極的に使ってみたい機能です。
また,パターンマッチの実装についても,以下のような文献を参考に効率的な実装になっています。core.matchの実装について興味があれば参照してみるのもいいでしょう。
次回は,引き続きathosがtools.loggingについて書きます。
tools.traceで実行トレースをとる
(このエントリは Clojure Contrib Library Advent Calendar 7日目の記事です。)
概要
今回はtools.traceについてです。tools.traceは実行トレースをとるのに便利な関数/マクロを提供するライブラリです。標準でデバッグ機能が弱いClojure上での開発で,シンプルに関数呼び出しだけトレースしたいような場合に使えます。
インストール
Leiningenを使用している場合は,project.cljの:dependenciesに
[org.clojure/tools.trace "0.7.6"]
と追加するだけで使えます。2013年12月現在では,0.7.6が最新の安定版です。
基本的には,tools.traceは開発時に使用するライブラリなので,:devプロファイルの:dependenciesとして追加するのがいいでしょう。
使い方
tools.traceが提供する主な関数/マクロは以下です。
- (trace-vars & vs)
- トレースする関数の名前を指定すると,その関数のVarが束縛する値をトレース出力つきの関数に置き換えます。
- (untrace-vars & vs)
- trace-varsで置き換えた関数を元に戻すことができます。
- (trace value)
- 関数呼び出し以外にトレース結果として出力したい値がある場合に使用します。
以下のマクロについては,使用する場合に注意するか,使用しない方がよいでしょう。
- dotrace
- マクロのボディ内だけ関数をトレース出力つきの関数に動的束縛する関数です。^:dynamicとして定義されたVar以外には適用できません。これは,1.3以降でVarがデフォルトで:dynamicでなくなったことに依ります。
- trace-forms
- 引数に与えた式のあらゆるサブフォームに対して,トレース出力を行う式を挿入します。コードウォークの実装が雑なため,引数に与える式によっては式の挿入に失敗します。
- trace-ns
- 引数に与えた名前空間で定義されたすべての関数に対してtrace-varsを適用し,トレース出力つきの関数に置き換えます。マップやセットなどclojure.lang.IFnインタフェースを実装した値を関数と誤判定し,トレース出力つきの関数に置き換えるため,トップレベルにマップやセットの定義がある場合に問題になることがあります。
適用例
以下のようなプログラムを対象にトレース出力の結果を見てみましょう。
(ns even-and-odd (:refer-clojure :exclude [even? odd?])) (declare odd?) (defn even? [x] (or (= x 0) (odd? (dec x)))) (defn odd? [x] (and (not= x 0) (even? (dec x))))
以下がtools.traceの適用例です。
user=> (require '[even-and-odd :as e]) nil ; 何もせずに関数を呼び出せば,通常通り関数の結果が返るだけ user=> (e/even? 5) false user=> (require '[clojure.tools.trace :refer :all]) nil ; 関数even?とodd?をトレース user=> (trace-vars e/even? e/odd?) #'contrib-calendar.tools.trace/odd? user=> (e/even? 5) ; 出力の各行にはユニークなIDがつけられ,関数の呼び出しと戻り値の対応を示す TRACE t1895: (contrib-calendar.tools.trace/even? 5) TRACE t1896: | (contrib-calendar.tools.trace/odd? 4) TRACE t1897: | | (contrib-calendar.tools.trace/even? 3) TRACE t1898: | | | (contrib-calendar.tools.trace/odd? 2) TRACE t1899: | | | | (contrib-calendar.tools.trace/even? 1) TRACE t1900: | | | | | (contrib-calendar.tools.trace/odd? 0) TRACE t1900: | | | | | => false TRACE t1899: | | | | => false TRACE t1898: | | | => false TRACE t1897: | | => false TRACE t1896: | => false TRACE t1895: => false false ; untrace-varsでトレースを無効化 user=> (untrace-vars e/even? e/odd?) #'contrib-calendar.tools.trace/odd? user=> (e/even? 5) false user=>
おわりに
今回は,シンプルなデバッグツールとしてtools.traceを紹介しました。
今回この記事を書くにあたって改めてtools.traceのコードを確認してみて,実装のやや甘い部分が散見されました。適用例で示したような使い方をする範囲では便利に使うことができますが,その他の機能を使用する場合には十分に注意が必要です。今後,tools.trace自体の完成度が上がること,また,別の高機能なトレースツールが現れることが期待されます。
次回は,引き続き僕athosがcore.matchについて書きます。