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

概要

このページでは高速パターンマッチングライブラリであるoptimaについて簡単に説明します。optimaの作者は日本人ですので、作者自身による日本語ドキュメントも参照してください。

optimaは以下の状態でロードされていることとします。
(asdf:load-system :optima)
; => T

(use-package :optima)
; => T

Clozure CLで名前の衝突が発生する場合は、shadowing-importを使用してからuse-packageしてみてください。
(shadowing-import 'optima:place)
; => T

(use-package :optima)
; => T

なお、optimaにはtriviaという派生ライブラリも存在します。triviaは後発ですがoptimaと互換性があるので、triviaを使用する場合も構文はほぼ同じです。

パターンマッチングとは

パターンマッチングは文字列における正規表現検索の文脈でよく使われますが、optimaがメインの対象とするのはオブジェクトのパターンマッチングです。特に力を発揮するのは、オブジェクトの中身に対するマッチングです。

パターンマッチングは一般に、2つの機能を併せ持っています。
  1. データ構造の分解(分配束縛)を行う「デストラクタ」としての機能
  2. データ構造の判定を行う「条件分岐」としての機能
ANSI Common Lispにはいくつかパターンマッチングに類似するオペレータが定められています。
  • caseマクロ: 定数パターンのマッチングを行います
  • typecaseマクロ: 型パターンのマッチングを行います
  • destructuring-bindマクロ: リストパターンのマッチングを行いますが条件分岐の機能はありません
  • with-slotsマクロ: スロットパターンのマッチングを行いますが条件分岐の機能はありません
それぞれ、標準仕様入門の第5章「データと制御フロー」(case, typecase)、第3章「評価とコンパイル」(destructring-bind)、第7章「オブジェクト」(with-slots)を参照してください。

定番の汎用束縛マクロであるlet-plus(let+)もパターンマッチングを行いますが、条件分岐の機能がありません。複数の分配束縛を行いながら処理をする場合にはlet+が便利ですが、パターンによる条件分岐を行う場合はoptimaが便利です。

このページでは英語の公式ドキュメントを参考にしながら、様々なパターンをのサンプルを紹介します。

パターン一覧
  • 基本パターン
    • 定数
    • 変数: _, otherwise
    • 汎参照: place
    • 述語: guard
    • 否定: not
    • 論理和: or
    • 論理積: and
  • コンストラクタパターン
    • コンス: cons, assoc, property
    • ベクトル: vector, simple-vector
    • スロット: class, structure
  • 派生パターン
    • リスト: list, list*
    • 述語: satisfies, eq, eql, equal, equalp
    • 型: type
  • エキストラパターン
    • 連想リスト: alist
    • 属性リスト: plist
    • 条件分岐マッチ: if-match, when-match, unless-match
    • 束縛マッチ: let-match, let-match*, let-match1
    • 正規表現マッチ:ppcre

基本パターン

基本パターンの中で特徴的なのはplaceパターンです。これはsetfマクロの第1引数の汎参照と同じで、値ではなくコードを束縛します。

また、guardパターンはマッチングを行った後に特定の条件を満たすかどうか、つまり述語関数が真を返すかを判定するために使います。

その他のパターンは自明ですので、以下のサンプルで確認してください。

サンプル1: or, guard, _

;; パターンマッチで実装するフィボナッチ数列
;; orパターン, guardパターン, _パターンを使用
(defun fib (n)
  (match n
    ((or 0 1) n)
    ((guard x (minusp x)) (error "~a is a negative number!" n))
    (_ (+ (fib (1- n)) (fib (- n 2))))))

なお、_パターンは任意の1オブジェクトにマッチします。otherwiseパターンは他にマッチしなかった場合のデフォルト用です。

サンプル2: place

;; placeパターンで汎参照そのものを束縛する
;; この例で x に束縛されるのは '(aref v 1) というコード
(let ((v #(1 2 3)))
  (match v
    ((vector _ (place x) _) (setf x 20) v)))
; => #(1 20 3)

サンプル3: 定数

;; 定数パターンは文字列も使用可能
;; if を使う場合は string= など等価性判定述語関数を使い分ける必要がある
;; match を使う場合は何も考えなくて良い
(let ((string "Hello"))
  (match string
    ("Hello" t)
    (_ nil)))
; => T

コンストラクタパターン

コンストラクタはコンス、ベクトル、クラス(インスタンス)、構造体などに対するマッチングを提供します。どれも直感的に使えますので、以下のサンプルで確認してください。

サンプル4: cons, assoc, property

コンスパターンとしては基本のconsのほか、連想リストに対するassocと属性リストに対するpropertyが定められています。連想リストについては第14章「リスト」を、属性リストについては第10章「シンボル」を参照してください。
(match '(1 . 2)
  ((cons x y) (list x x y y)))
; => (1 1 2 2)

(match '((:x . 1)(:y . 2))
  ((assoc :y value) (format t "y = ~a~%" value)))
; y = 2
; => NIL

(match '(:x 1 :y 2)
  ((property :y value) (format t "y = ~a~%" value)))
; y = 2
; => NIL

なお、連想リストと属性リストはエキストラパターンに複数のマッチングに対応したものが入っていますので、そちらを使用することもできます。

サンプル5: vector, simple-vector

ベクトルに関してはvectorパターンの他にsimple-vectorも用意されています。「シンプル」の意味については標準仕様入門の第15章「配列」を参照してください。
(match #(1 2)
  ((vector x y) (format t "(~a, ~a)~%" x y)))
(1, 2)
; => NIL

(match #(1 2)
  ((simple-vector x y) (format t "(~a, ~a)~%" x y)))
(1, 2)
; => NIL

サンプル6: class

;; クラスの定義
(defclass point ()
  ((x :initarg :x :accessor point-x)
   (y :initarg :y :accessor point-y)))
; => #<STANDARD-CLASS POINT>

;; クラスの実体(インスタンス)の生成
(defparameter *p* (make-instance 'point :x 2 :y 4))
; => *P*

;; class パターンでマッチする
;; (class は省略可)
(match *p*
  ((class point x y)
   (format t "(x, y) = (~a, ~a)~%" x y)))
; (x, y) = (2, 4)
; => NIL

サンプル7: structure

;; 構造体を定義する
(defstruct date year month date)
; => DATE

;; 構造体の実体を生成する
(defparameter *today* (make-date :year 2018
                                 :month 3
                                 :date 24))
; => *TODAY*

;; structure パターンでマッチングする
;; (structureは省略可)
(match *today*
  ((structrure date- year month date)
   (format t "~a/~a/~a" year month date)))
; 2018/3/24
; => NIL

派生パターン

派生パターンは他のパターンで記述できるパターンです。

サンプル8: list, list*

;; proper list
(match '(1 2 3)
  ((list x y z) (list z y x)))
; => (3 2 1)

;; improper list
(match '(1 2 . 3)
  ((list* x y z) (list z y x)))
; => (3 2 1)

サンプル9: satisfies

satisfiesパターンは関数を引数に取りますが、関数の名前を示すシンボルをクォートなしで指定します。
(match 1
  ((satisfies evenp) 'even)
  ((satisfies oddp) 'odd))
; => ODD

サンプル10: type

(match 1.0
  ((type single-float) 'single-float)
  ((type double-float) 'double-float))
; => SINGLE-FLOAT

(match 1.0d0
  ((type single-float) 'single-float)
  ((type double-float) 'double-float))
; => DOUBLE-FLOAT

エキストラパターン

エキストラパターンはoptima.extraパッケージに入っていますので、使用する場合は追加でインポートしてください。
(use-package :optima-extra)
; => T
最後に紹介している正規表現パターンppcreCL-PPCREを使用したものです。ASDFのレベルから分離されているため、ASDFでロードしてから使用してください。
(asdf:load-system :optima.ppcre)
; => T

(use-package :optima.ppcre)
; => T

サンプル11: alist, plist

連想リストや属性リストのエントリーのうち、複数にマッチした場合を分岐させたいなら、andパターンとassoc/propertyを併用するよりもalist/plistを使用した方が直感的です。
(match '((:x . 1)(:y . 2))
  ((alist (:x . x)(:y . y)) (list x y)))
; => (1 2)

(match '(:x 1 :y 2)
  ((plist :x x :y y) (list x y)))
; => (1 2)

サンプル12: if-match, when-match, unless-match

条件分岐の中でパターンマッチを使えるように拡張したエクストラパターンです。matchの中に条件分岐の機能が含まれますが、構文的にANSI Common Lisp標準のif, when, unlessに近いため、あえて定義されているようです。
(if-match (type string) "Hello" t nil)
; => T

(if-match (type string) 1 t nil)
; => NIL

上の例は、matchで記述した以下のバージョンと等価です。
(match "Hello" ((type string) t)(otherwise nil))
; => T

(match 1 ((type string) t)(otherwise nil))
; => NIL

サンプル13: let-match, let-match*, let-match1

letを拡張するマクロとしてはlet+が有名ですが、optimaにも束縛に特化したパターンマッチマクロがあります。let-matchをはじめとするマクロの中では、matchで使用できるパターンを使って分配束縛することができます。

let-match1は束縛対象が1つだけの場合のシンタックスシュガーです。
;; 束縛部分にパターンを使用できる
(let-match (((list x y z) '(1 2 3)))
  (list z y x))
; => (3 2 1)

;; let-match1は束縛が1つだけの場合に使用できる
(let-match1 (list x y z) '(1 2 3)
  (list z y x))
; => (3 2 1)

サンプル14: ppcre

optima.ppcreを使用すると、Cl-PPCREをより直感的に使用することができます。
(match "独学 Common Lisp"
  ((ppcre "(.+)\\s(.+)\\s(.+)" v1 v2 v3)
   (list v1 v2 v3)))
; => ("独学" "Common" "Lisp")

これをCl-PPCREのscan-to-stringsだけで記述すると、以下のようになります。
(multiple-value-bind (match regs)
    (ppcre:scan-to-strings "(.+)\\s(.+)\\s(.+)" "独学 Common Lisp")
  (list (svref regs 0) (svref regs 1) (svref regs 2)))
; => ("独学" "Common" "Lisp")

0 件のコメント :

コメントを投稿