common-lisp

optima - 高速パターンマッチライブラリ

More than 5 years have passed since last update.

開発が成熟してきたので、ここらで拙作のパターンマッチライブラリ、optimaを日本語で解説したいと思う。ただし解説とは言っても、詳細な仕様をだらだらと解説するようなことはしない。むしろ「なぜパターンマッチなのか」を踏まえた上で、簡単な入門と使用例を示すことで、パターンマッチの重要性を認識してもらうのが狙いだ。なお、詳細な仕様についてはマニュアルを参照されたい。


なぜパターンマッチなのか

Common Lispにはパターンマッチライブラリが多数存在するが、その大半は単にパターンマッチが便利だからという視点しか持っていない。たしかにパターンマッチは便利であるが、便利なだけでは人々はそれを使おうとはしない。より本質的な視点を与える必要があるだろう。

OCamlやHaskellなどの関数型言語では、あらゆるデータは、代数的データ型として定義され、それにともなうデータコンストラクタによって構成される。例えば二分木はHaskellで以下のように定義される。

data Tree = Leaf | Node Tree Int Tree

これは、Treeという代数的データ型を持つデータは、LeafあるいはNodeというデータコンストラクタのみで構成される、と読める。例えば1, 2, 3の三つの要素を持つ二分木は以下のように構成できる。

Node (Node Leaf 1 Leaf) 2 (Node Leaf 3 Leaf)

これをxと名付けたとしよう。では、xからラベルを取得するにはどうしたらいいだろうか。実は、OCamlやHaskellでは基本的には以下のようにパターンマッチを介さずにはデータの中身を取り出すことが出来ない。

case x of Node _ a _ -> a

つまり、データコンストラクタとパターンマッチは双対の関係にあり、データを構築・分解するという観点からは、両者は最も単純な形式であると言える。この単純な形式化からは、パターンマッチの高い表現力や網羅性など、極めて重要な性質が導出される。

また、再帰呼び出しとパターンマッチを併用することで、複雑な処理を簡潔に記述できることがしばしばある。そして、その見た目は大抵、数学の帰納法に似ている。しかも、そのように書かれたコードは、意味解析せずとも見た目で間違ってないことが確かめられることが多い。

言うまでもないが、パターンマッチはデータの中身を直接書き換えるパラダイムとはあまり相性が良くない。特に、Javaのように、基盤となるデータ型が煩雑で、命令型パラダイムに一辺倒なシステムにおいては、パターンマッチの効果を十分に発揮できない。

つまり、パターンマッチは関数型パラダイムにおいて使われないと、ほとんど意味がないのだ。幸運なことに、Common Lispはマルチパラダイム言語で、Javaのようなおかしなオブジェクトシステムも持っていない。だから、書こうと思えばいくらでも関数型っぽく書ける。ただし、もちろん限界もある。だが、その限界を差し引いても、パターンマッチによって得られるところは大きいだろうと考えている。


入門optima

解説に入る前にoptimaのロード方法について述べておこう。

少し前のバージョンならQuicklispに登録済みなので、

(ql:quickload :optima)

でロードできる。最新のバージョンを使いたい場合は、以下からリポジトリを取得して、

https://github.com/m2ym/optima

~/.config/common-lisp/source-registry.conf.d/setq-asd.confに以下を追記しよう。

(:directory (:home ホームディレクトリからのパス))

あとは上と同様に

(ql:quickload :optima)

でロードできる。ロード後は、COMMON-LISP-USERパッケージで

(use-package :optima)

しておくと便利だろう。それでは解説に移る。

前節で述べたように、optimaはデータコンストラクタと反対の作業(ここではデータデストラクタと呼ぼう)を行うよう意識して実装されている。では、Lispにおけるデータコンストラクタとは何か。

最も基本的なのはconsである。consは二つのデータを取ってペアを構成(construct)する。ペアから実際に中身を取り出すには、matchマクロを使う。matchは次のような構文になっており、

(match FORM (PATTERN BODY)...)

FORMにはパターンマッチ対象のデータを表す任意の式、PATTERNにはパターン、BODYにはそのパターンにマッチしたときに実行される任意の式を書く。ここではconsパターンを使って以下のように書く。

CL-USER> (match (cons 1 2) ((cons x y) x))

1

第一引数のconsは通常のconsで、ペアを作っている。第二引数のconsconsパターンで、consで構成されたデータに対してマッチし、そのcar要素とcdr要素を、さらにconsパターンの引数についてそれぞれマッチし、成功した場合に、対応する本体を実行する。xyなどのシンボルは、パターン変数と呼び、パターンマッチ対象のデータを変数に束縛する。上のコードは以下のコードと同じ意味である。

(let ((c (cons 1 2)))

(if (consp c)
(let ((x (car c))
(y (cdr c)))
x)))

パターンはいくらでもネストできるので、例えば以下のようなコードも書ける。

CL-USER> (match (list 1 2 3)

((cons x (cons y (cons z nil)))
(+ x y z)))
6

パターンに出現しているnilは、定数パターンと呼び、数値や文字、文字列、配列などに対して、最も自然な比較によってパターンマッチされる。

CL-USER> (match 1 (1 t))

T
CL-USER> (match #\a (#\a t))
T
CL-USER> (match "foo" ("foo" t))
T
CL-USER> (match '(1) ('(1) t))
T

リストを作るのにlistを使うのと同じように、consパターンを連続させる代わりにlistパターンを使うことも出来る。

CL-USER> (match (list 1 2 3)

((list x y z) (+ x y z)))
6

listパターンは、consパターンと定数パターンによって定義可能なため、派生パターンのひとつとして定義される。実際の定義は以下である。

(defpattern list (&rest args)

(when args
`(cons ,(car args) (list ,@(cdr args)))))

defpatternは派生パターンを定義するAPIで、deftypeとほとんど同じように利用できる。詳細は割愛するが、list*パターンやsatisfiesパターンもdefpatternによって定義されている。

matchはどれかひとつの節が成功するまで、順にパターンマッチを行う。

CL-USER> (match (list 1 2)

((list _) 1)
((list _ _) 2)
((list _ _ _) 3))
2

上の例では、二番目の節のパターンマッチに成功したため、2を評価してそれで完了となる。もし、どの節のパターンにもマッチしない場合は、matchnilを返す。

Common Lispのコンストラクタに対応するパターンはまだ色々あるが、ここではクラスパターンのみをさらに解説する。クラスパターンとは、defstructdefclassによって定義された型のデータを表現するパターンである。例えば、以下のようなperson型を定義しているとしよう。

(defstruct person name age sex)

これをパターンマッチするには、次のように書けばよい。

CL-USER> (match (make-person :name "John" :age 42 :sex :male)

((person name age sex) (list name age sex)))
("John" 42 :MALE)

お気付きのように、defstructdefclassで定義された型のパターンは、自動的に定義される。ここではperson型に対応するpersonパターンが使われており、その引数は(SLOT PATTERN)という形式をとる。単にSLOTと書いた場合は、(SLOT SLOT)と同義になる。つまり上の例のパターンは(person (name name) (age age) (sex sex))と書いても同じになる。

コンストラクタとパターンの形式を一致させるために、defstructをしばしば以下のように書くことがある。

(defstruct (person (:constructor person (name age sex)))

name age sex)

これによって、以下のようにデータを作ることができる。

CL-USER> (person "John" 42 :male)

#S(PERSON :NAME "a" :AGE 1 :SEX :MALE)

他にも様々なマクロやパターンが存在しているが、ここでは解説しない。是非、マニュアルを参照されたい。


使用例: 赤黒木

ここでは実際にoptimaを使って赤黒木を実装してみたいと思う。赤黒木とは、平衡二分探索木の一種で、最短のパスと最長のパスの差がせいぜい二倍以内に収まる。赤黒木は、各ノードに付与した色情報をもとにバランスを保とうとする。詳細はWikipediaを参照されたい。

まず、赤黒木の二分木を定義する。Haskellでの定義

data Color = Red | Black

data Tree a = Leaf | Node Color (Tree a) a (Tree a)

をイメージして、以下のように擬似的に代数的データ型を定義する。

(defstruct (leaf (:constructor leaf)))

(defstruct (node (:constructor node (color left label right)))
color left label right)

試しに二分木を作ってみる。

CL-USER> (leaf)

#S(LEAF)
CL-USER> (node :black (leaf) 1 (leaf))
#S(NODE :COLOR :BLACK :LEFT #S(LEAF) :LABEL 1 :RIGHT #S(LEAF))
CL-USER> (node :black (node :red (leaf) 1 (leaf)) 2 (node :red (leaf) 3 (leaf)))
#S(NODE
:COLOR :BLACK
:LEFT #S(NODE :COLOR :RED :LEFT #S(LEAF) :LABEL 1 :RIGHT #S(LEAF))
:LABEL 2
:RIGHT #S(NODE :COLOR :RED :LEFT #S(LEAF) :LABEL 3 :RIGHT #S(LEAF)))

次に要素が含まれるか判定するrb-member関数を定義してみる。単に二分探索すればよい。

(defun rb-member (x tree)

(match tree
((leaf) nil)
((node left label right)
(cond ((< x label) (rb-member x left))
((> x label) (rb-member x right))
(t t)))))

パターンマッチでは、データの検査(leafnodeか)とデータの分解(leftlabelrightスロットの取り出し)が同時に行えるため、rb-memberは極めて直感的な定義になっているのが分かる。rb-memberが正しく動作しているか確認する。

CL-USER> (defvar tree (node :black (node :red (leaf) 1 (leaf)) 2 (node :red (leaf) 3 (leaf))))

CL-USER> (rb-member 1 tree)
T
CL-USER> (rb-member 4 tree)
NIL

挿入操作を定義する前に、balance関数を定義する。balanceは、赤黒木の規則を破る(赤色のノードは赤色のノードを子としてもってはいけない)以下のような4つのケースの部分木を

       Bz            Bz            Bx            Bx

/ \ / \ / \ / \
Ry d Rx d a Rz a Ry
/ \ / \ / \ / \
Rx c a Ry Ry d b Rz
/ \ / \ / \ / \
a b b c b c c d

次のようにバランスする。

     Ry

/ \
Bx Bz
/ \ / \
a b c d

これを愚直に実装するとひどく骨が折れるが、パターンマッチを使えばとても簡単に定義できる。その前に、いくつかヘルパーを定義しておく。

(defun red (left label right)

(node :red left label right))

(defun black (left label right)
(node :black left label right))

(defpattern red (left label right)
`(node (color :red) (left,left) (label ,label) (right ,right)))

(defpattern black (left label right)
`(node (color :black) (left,left) (label ,label) (right ,right)))

上から順に、赤色ノード・黒色ノードを構成するヘルパー関数、赤色ノード・黒色ノードにマッチする派生パターンである。それではbalanceを定義する。

(defun balance (tree)

(match tree
((or (black (red (red a x b) y c) z d)
(black (red a x (red b y c)) z d)
(black a x (red (red b y c) z d))
(black a x (red b y (red c z d))))
(red (black a x b) y (black c z d)))
(otherwise tree)))

パターンに出現しているororパターンと呼び、引数に与えられたパターンのいずれかにマッチする。詳しく読めば、上に図示した変換を正しく行っていることが分かるだろう。

それでは、挿入操作であるrb-insert関数を定義する。

(defun rb-insert (x tree)

(labels ((ins (tree)
(match tree
((leaf) (red (leaf) x (leaf)))
((node color left label right)
(cond ((< x label)
(balance (node color (ins left) label right)))
((> x label)
(balance (node color left label (ins right))))
(t tree))))))
(match (ins tree)
((node left label right)
(black left label right)))))

少々複雑だが、しっかり読めば難しくない。要は二分探索木を辿りながら要素を挿入し、バランスしているだけだ。動作を確認する。

CL-USER> (setq tree (leaf))

#S(LEAF)
CL-USER> (setq tree (rb-insert 1 tree))
#S(NODE :COLOR :BLACK :LEFT #S(LEAF) :LABEL 1 :RIGHT #S(LEAF))
CL-USER> (setq tree (rb-insert 3 tree))
#S(NODE
:COLOR :BLACK
:LEFT #S(LEAF)
:LABEL 1
:RIGHT #S(NODE :COLOR :RED :LEFT #S(LEAF) :LABEL 3 :RIGHT #S(LEAF)))
CL-USER> (setq tree (rb-insert 2 tree))
#S(NODE
:COLOR :BLACK
:LEFT #S(NODE :COLOR :BLACK :LEFT #S(LEAF) :LABEL 1 :RIGHT #S(LEAF))
:LABEL 2
:RIGHT #S(NODE :COLOR :BLACK :LEFT #S(LEAF) :LABEL 3 :RIGHT #S(LEAF)))
CL-USER> (rb-member 1 tree)
T
CL-USER> (rb-member 2 tree)
T
CL-USER> (rb-member 3 tree)
T
CL-USER> (rb-member 4 tree)
NIL

正しく動作しているようだ。なお、実装の全文は以下から参照できる。

https://gist.github.com/4245414


まとめ


  • なぜパターンマッチなのか(=なぜ関数型パラダイムが重要なのか)を解説した

  • optimaの簡単な使い方を解説した

  • optimaを使って実際に赤黒木を実装した

私は、optimaはCommon Lispの自然な拡張だと考えているが、Common Lispはどちらかと言えば命令型パラダイムの言語である。しかし、関数型パラダイムに基づいてプログラムを記述するのは、Common Lispにおいても十分可能・有効であるし、本記事がそれを示唆していることを、読者が感じてくれれば幸いである。


参考文献