2011-06-28

パターンマッチングによる処理の分岐(2):Fare-matcher

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.

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

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

以下参考文献。

2011-06-25

パターンマッチングによる処理の分岐(1):Alexandria

OCamlHaskellなどのコードを読むと、パターンマッチングによる処理の分岐が良く出て来る。この機能は実に便利で、リストの要素の内容に合わせて処理を分岐したり、関数の引数の数で処理を分岐したり、といった処理を、非常に簡潔に、そして読みやすく書ける。自分はこれをAndrew Wrightが書いたSchemeのマクロで知ったんだけど(Schemeの世界では有名なマクロ)、今では手放せなくなってしまった。今回は、パターンマッチングによる処理の分岐をCommon Lispで使うとき、どうすれば良いかの案内。パターンマッチングによる処理の分岐が、具体的にどのように便利かは、OCamlやHaskellなどの関数型言語の文書で多く紹介されているので、そちらを読んで欲しい。On Lispの「構造化代入」の章を読むのも良い。

パターンマッチング自体は特に新しい技術ではないので、Lispの世界でも馴染みが深い。On Lispにも登場するし、読んでないけどPAIPでも触れられているそうだ。Makoto Hiroiさんのxyzzy Lisp Programmingでも、「記号のパターンマッチング(1)」で取り上げられている。こういったコードを持ってきても良いんだけど(ライセンスに注意。幸いどれも自由に使えるけれど、使ったコードを第三者に公開するなら、出典は明記しなければいけないだろう)、使う側からすると、最初からASDFに対応していて欲しいし、Quicklispで楽に読み込めるともっと嬉しい。

そして、その嬉しいことに、パターンマッチングによる処理の分岐に使えるライブラリが、2011年6月25日の時点でもQuicklispに登録されている。自分が知っている範囲では、

  • Alexandria
  • Fare-matcher
  • arnesi
  • cl-match
  • cl-pattern

がそうだ。一連の記事で順番に紹介していく。

Alexandriaは、Common Lispを今でも使っている人ならお馴染みのユーティリティライブラリだ。with-gensymsやonce-only、flattenなどの、有名なユーティリティマクロや関数が収録されている。その中のdestructuring-caseで、非常に限定された形だけれど、パターンマッチングによる処理の分岐ができる。

(alexandria:destructuring-case '(3 0 1 2)
  ((1 x) x)
  ((2 x y) (+ x y))
  ((3 x y z) (+ x y z)))
;=> 3

(alexandria:destructuring-case '(:a :b :c)
  ((x y z) :in-destructuring-case)
  ((:a x y) :car-cannot-take-binding))
;=> :CAR-CANNOT-TAKE-BINDING

(alexandria:destructuring-case '(1 #\x "string")
  ((1 #\x "string") :literal-causes-error))
;>> Error: Invalid lambda list: (#\x "string")

第一引数がパターンマッチングの対象になるリストで、以降がパターンと対応する処理の組み合わせだ。このマクロは名前の通り、destructuring-bindとcaseを組み合わせたもので、それぞれの性質を引き継ぐ。展開したあとの式も見てみよう。

(LET ((#:KEY0 '(3 0 1 2)))
  (IF (TYPEP #:KEY0 'CONS)
      (CASE (CAR #:KEY0)
        (1 (DESTRUCTURING-BIND (X) (CDR #:KEY0) X))
        (2 (DESTRUCTURING-BIND (X Y) (CDR #:KEY0) (+ X Y)))
        (3 (DESTRUCTURING-BIND (X Y Z) (CDR #:KEY0) (+ X Y Z))))
      (ERROR "Invalid key to DESTRUCTURING-~S: ~S" 'CASE #:KEY0)))

とても単純な仕組みになっている。パターンのcar部はcaseで処理できなければならない。パターンのcdr部はdestructuring-bindに渡されるため、リテラルを含んではいけない。

一見、かなり厳しい制限に思えるけど、リストの最初の要素が処理の成否を表し、それ以降の要素が処理のデータを表す、といった、ありがちなパターンには十分対応できる。あるいは、最初の要素はアクションを表し、以降の要素はアクションのパラメータを表す、なんていう場合でも問題ない。リストの最初の要素にはアクセスしやすいので(carするだけだ)、リストの最初に条件分岐のためのキーを置くことは多い。多値にもmultiple-value-listで対応でき、意外に適用範囲は広い。

(alexandria:destructuring-case '(nil (10 . 5) "syntax error")
  (((t) syntactic-tree) (process syntactic-tree))
  (((nil) (line . char) msg) (error "line ~a: char ~a: ~a" line char msg)))
   
(alexandria:destructuring-case `(:write ,stream #\a)
  ((:write s x) (princ x s))
  ((:read s) (aif (read-char s nil) (push it buf))))

特徴をまとめると、alexandria:destructuring-caseは、対応するデータ型はリストのみで、表現力も乏しいけれど、限られた用途には十分で、仕組みが単純なため、destructuring-bindが最適化されている処理系では速い。

2011-06-04

Mercurial 1.8.4のインストール

OpenIndiana oi_148に収録されているMercurialは1.3.1と古いので、現時点での最新版の1.8.4をインストールした。

まず、Mercurialのドキュメントの作成に必要なDocutilsをインストール。

% wget "http://prdownloads.sourceforge.net/docutils/docutils-0.7.tar.gz?download"
% tar xf docutils-0.7.tar.gz
% cd docutils-0.7
% ./setup.py install --prefix=$HOME/opt/docutils-0.7
% cd ~/opt/bin
% for f in ../docutils-0.7/bin/*; do; ln -s $f; done
% cd ~/opt/lib
% mkdir -p python2.6/site-packages
% cd python2.6/site-packages
% for f in ../../../docutils-0.7/lib/python2.6/site-packages/*; do; ln -s $f; done

標準じゃないディレクトリにインストールしたので、PYTHONPATHの設定が必要。今回だと

PYTHONPATH=$HOME/opt/lib/python2.6/site-packages; export PYTHONPATH

のように、~/opt/lib/python2.6/site-packagesを追加する必要がある。.profileなどで設定。

Mercurialをインストール。

% wget http://mercurial.selenic.com/release/mercurial-1.8.4.tar.gz
% tar xf mercurial-1.8.4.tar.gz
% make PREFIX=$HOME/opt/mercurial-1.8.4 all
% make PREFIX=$HOME/opt/mercurial-1.8.4 INSTALL="ginstall -c -m 644" install
% cd ~/opt/bin
% ln -s ../mercurial-1.8.4/bin/hg
% hg debuginstall

doc/MakefileがBSD installを想定しているので、makeのINSTALLマクロを上書きして、ginstallを使う。hg debuginstallは、きちんとインストールできているかのチェック。