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について書きます。

*1:このコードは型システム入門4章に掲載されているOCamlのコードをそのままClojureに翻訳した形になっています。Clojureとして,特にこのような例外の使い方が推奨されているわけではありません。念のため。