accomplish nothing

Fare-matcherは、MLスタイルのパターンマッチングによる処理の分岐を、本格的にCommon Lispに取り入れるために作られたライブラリ。リストと多値、ベクタ、CLOSオブジェクトに対応し、パターンの表現力が高い。以下は2011年6月28日現在で最新のリビジョンの解説。

まずはパターンについて。パターンはS式で表現され、次のような種類がある。なお、定義リスト中の「*」と「+」は、0回以上の繰り返し、1回以上の繰り返しを表す。

リテラル

値同士をequalで比較して一致するときにマッチする

シンボル

どんな値にもマッチし、その値でシンボルを束縛する。ただし「_」と「*」の場合、値を束縛せずに捨てる（ワイルドカード）

(cons パターン パターン)

consは、car部とcdr部がそれぞれのパターンとマッチするコンスにマッチする

(list パターン+)

listは、要素の数がパターンの数と一致し、それぞれの要素の値とパターンがマッチするリストにマッチする

(list* パターン* シンボル)

list*は、要素の数がパターンの数以下で、それぞれの要素の値とパターンがマッチするリストにマッチする。最後のシンボルは、パターンのマッチングが済んだ後に残っている要素のリストで束縛される

(values パターン+)

valuesは、それぞれの値とパターンがマッチする多値にマッチする。多値の数とパターンの数が一致しない場合、nilがマッチングに使われる

(vector パターン+)

vectorは、要素の数がパターンの数と一致し、それぞれの要素の値とパターンがマッチするベクタ（一次元の配列）にマッチする

(slot* (スロット名 パターン)+)

slot*は、スロットの値とパターンがマッチするCLOSオブジェクトにマッチする

(accessor* (アクセサ名 パターン)+)

accessor*は、アクセサが返す値とパターンがマッチするCLOSオブジェクトにマッチする

(and パターン+)

andは、値とすべてのパターンがマッチしたときにマッチする

(or パターン+)

orは、値とパターンのいずれかがマッチしたときにマッチする

(of-type 型)

of-typeは、値の型と型が一致したときにマッチする

(when テスト)

whenは、テストが真のときにマッチする（ガード）

(like-when パターン テスト)

like-whenは、値とパターンがマッチし、テストが真のときにマッチする。(and パターン (when テスト))の構文糖

whenやlike-when、andやorの組み合わせで、複雑なパターンを作ることができる。

次はAPIについて。

ifmatch pattern exp &optional (ifmatches t) iffails

ifm pattern exp &optional (ifmatches t) iffails

ifと同じ二方向の条件分岐。expがpatternにマッチした場合ifmatchesを評価し、しなかった場合iffailsを評価する。ifmはifmatchの別名。

match exp &rest clauses

ematch exp &rest clauses

condやcaseなどと同じ、任意の数の方向への条件分岐。clauseのcar部がパターンで、cdr部がマッチした場合の処理。caseとecaseの関係と同じで、ematchはどのパターンにもマッチしない場合、エラーを発生させる。

letm pattern val &body body

destructuring-bindのような、構造化代入のためのマクロ。valがpatternにマッチした場合bodyを評価し、しなかった場合はエラーを発生させる。

letmという名前はモナド方面で使われている可能性があるため、use-packageするときは気を付けたほうが良いかもしれない。

使用例を挙げる。

(ql:quickload :fare-matcher)
(defpackage :fare-matcher-test (:use :cl :fare-matcher))
(in-package :fare-matcher-test)

(ifm 0 0)
(ifm 'x 'x)
(ifm #\a #\a)
(ifm "a" "a")
;=> T

(ifm x 2 x)
;=> 2

(ifm (list x y) '(0 1) (values x y))
;=> 0, 1

(ifm (cons f r) '(0 1 2) (values f r))
(ifm (list* f r) '(0 1 2) (values f r))
;=> 0, (1 2)

(ifm (values x y) (truncate 3.14) (values x y))
;=> 3, 0.1400001

(ifm (vector 1 2 x) #(1 2 3) x)
;=> 3

(defclass point ()
  ((x :accessor point-x :initarg :x :initform 0)
   (y :accessor point-y :initarg :y :initform 0)))

(let ((p (make-instance 'point :x 3 :y 2)))
  (ifm (slot* (x px) (y py)) p (values px py)))
;=> 3, 2

(let ((p (make-instance 'point :x 4 :y 5)))
  (ifm (accessor* (point-x px) (point-y py)) p (values px py)))
;=> 4, 5

(ifm (and (cons x 2) (cons 1 y)) '(1 . 2) (values x y))
;=> 1, 2

(ifm (or 1 3) 3)
;=> T

(ifm (of-type number) 1)
;=> T

(ifm (when t) :anytime-t)
(ifm (and x (when (symbolp x))) 'symbol)
;=> T

(ifm (like-when (list x y z) (eql (+ x y z) 6)) '(1 2 3))
(ifm (like-when (list x y z) (eql (+ x y z) 6)) '(0 0 6))
;=> T

(ifm (list (list x y) z) '((:a :b) :c) (values x y z))
;=> :A, :B, :C

(ifm (cons (cons key value) rest) '((:x . 100) (:y . 200)) (values key value rest))
;=> :X, 100, ((:Y . 200))

複雑な構造のリストも難なく処理できるため、リスト処理に威力を発揮する。

マクロを展開してみる。

; (ifm (cons f r) '(0 1 2) (values f r))
(FLET ((#:FAILURE-CONTINUATION NIL NIL))
  (DECLARE (IGNORABLE #'#:FAILURE-CONTINUATION))
  (LET ((#:FORM
         (MULTIPLE-VALUE-BIND (#:R012110)
             '(0 1 2)
           #'(LAMBDA NIL (VALUES #:R012110))))
        F
        R)
    (DECLARE (IGNORABLE #:FORM))
    (FUNCALL (BLOCK #:M%POINT
               (MULTIPLE-VALUE-CALL
                 (FUNCALL #'(LAMBDA (#:R012110 #:R112111)
                              #'(LAMBDA (#:FORM)
                                  (FARE-UTILS:MVBIND (#:R212112 #:R312113)
                                                     (FUNCALL
                                                      #'(LAMBDA
                                                         (FARE-MATCHER::FORM)
                                                         (IF (CONSP FARE-MATCHER::FORM)
                                                             (PROGN (VALUES (CAR FARE-MATCHER::FORM) (CDR FARE-MATCHER::FORM)))
                                                             (RETURN-FROM #:M%POINT #'#:FAILURE-CONTINUATION)))
                                                      #:FORM)
                                                     (PROGN (FUNCALL #:R012110 #:R212112) (FUNCALL #:R112111 #:R312113)))))
                          #'(LAMBDA (#:FORM) (SETF F #:FORM))
                          #'(LAMBDA (#:FORM) (SETF R #:FORM)))
                 (FUNCALL #:FORM))
               #'(LAMBDA NIL (VALUES F R))))))

funcallでクロージャを呼ぶようになっている。このため、On Lispの「構造化代入」で紹介されているような、マクロでifなどのプリミティブな式まで変換する手法に比べて、コストが大きい。

(declaim (optimize (speed 3) (safety 1) (debug 1) (space 1)))

(time (iter (repeat 1000000)
            (letm (list x y z)
                (list (random 10) (random 10) (random 10))
              (values x y z))))
;-> (ITER (REPEAT 1000000) (LETM (LIST X Y Z) (LIST (RANDOM 10) (RANDOM 10) (RANDOM 10)) (VALUES X Y Z))) took 1,906 milliseconds (1.906 seconds) to run 
;                       with 2 available CPU cores.
;   During that period, 1,766 milliseconds (1.766 seconds) were spent in user mode
;                       47 milliseconds (0.047 seconds) were spent in system mode
;   531 milliseconds (0.531 seconds) was spent in GC.
;    352,000,032 bytes of memory allocated.

(time (iter (repeat 1000000)
            (destructuring-bind (x y z)
                (list (random 10) (random 10) (random 10))
              (values x y z))))
;-> (ITER (REPEAT 1000000) (DESTRUCTURING-BIND (X Y Z) (LIST (RANDOM 10) (RANDOM 10) (RANDOM 10)) (VALUES X Y Z))) took 312 milliseconds (0.312 seconds) to run 
;                       with 2 available CPU cores.
;   During that period, 312 milliseconds (0.312 seconds) were spent in user mode
;                       0 milliseconds (0.000 seconds) were spent in system mode
;   63 milliseconds (0.063 seconds) was spent in GC.
;    24,000,032 bytes of memory allocated.

速度を気にしない場所では問題にならないけど、性能が必要な部分で使うには厳しいかもしれない。とは言え、いつでも速度が求められるわけではないから、例えば、複雑なリスト処理が必要とされがちだけど、速度は問題にならないマクロの定義などでは、便利に使えるんじゃないだろうか。少なくとも自分は便利に使っている。

まとめると、性能が要求される部分ではボトルネックになる可能性があるが、複数のデータ型に対応し、表現力も高いため、速度を気にしないで良い部分では威力を発揮する。

以下参考文献。

• CLiki : fare-matcher
• CLiki : fare-matcher-docs
• fare-matcher.git
• fare-matcher.texinfo
• matcher.lisp