Document

“Extensible Pattern Matching via a
Lightweight Language Extension”
の Survey
POPL meeting 7/25
Kazuhiro Inaba
[email protected]
出典

“Extensible Pattern Matching via a
Lightweight Language Extension”
Don Syme, Gregory Neverov, James Margetson
Accepted for ICFP 2007
（Submitted DraftをWebから入手可能）


F# の “Active Pattern” という拡張に関する論文
現在公開されているバージョンで使うことができます
Motivation
Motivation


Abstract Data Type でもパターンマッチしたい
複数のViewでパターンマッチしたい
type complex = {abstract}
let my_function c obj =
match c with
Polar(r, t) -> zoom r (rotate t obj)
let another_function c =
match c with
Rect(x, y) -> x + y
Motivation

なぜパターンマッチ？これでは不十分？
type complex = {abstract}
let my_function c obj =
zoom (abs c) (rotate (arg c) obj)

パターンマッチ形式の利点は


読みやすい
特にCase-Analysisが必要な場合読みやすい


(nil?, head, tail 関数によるリスト操作と比較せよ)
Exhaustiveness のチェックもできて安全
Examples
Active Patterns by Examples

Total Patterns



Single Total Patterns
Decomposition with Recognizers
Partial Patterns
Single Total Patterns

(|識別子|) という名前の関数を定義
type complex = Rect of float * float ;;
type complex = Rect of float * float
let (|Polar|) c =
match c with
Rect(x,y) -> (atan2 y x, sqrt(x*x+y*y)) ;;
val (|Polar|) : complex -> float * float

パターンとして使用 (let (r,t) = (|Polar|) c in … と同義)
let my_function c obj =
match c with
Polar(r, t) -> zoom r (rotate t obj) ;;
Decomposition

(|識別子|識別子|…|識別子|) という名前の関数を定義
let (|Snoc|Nil|) lst =
if lst = []
then Nil
else Snoc(rev(tl(rev lst)), hd(rev lst)) ;;
val (|Snoc|Nil|)
: ‘a list -> Choice<(‘a list*’a),unit>

パターンとして使用
 match [1;2;3] with
Nil
-> []
| Snoc(hh, t) -> [t] @ hh ;;
Val it : int list = [3; 1; 2]
Decomposition

パターンの完全性の静的検査
 match [1;2;3] with Snoc(hh,t) -> [t] @ hh ;;
match [1;2;3] with Snoc(hh,t) -> [t] @ hh
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
stdin(59,0): warning FS0025: Incomplete pattern
match.
val it : int list = [3; 1; 2]
Partial Patterns

次のようなパターンマッチを書きたいことがある



元々completeでない
各caseがdistinctでもない
後からcaseを付け足したくなる可能性がある
type value = IntVal of int
| FloatVal of float
| ColorVal of int * int * int
match str with
| ParseInt
i -> IntVal i
| ParseFloat f -> FloatVal f
| ParseColor c -> ColorVal c
| _ -> failwith “invalid input”
Partial Patterns

(|識別子|_|) という名前の関数を定義
let (|ParseInt|_|) s =
let i = ref 0 in
if Int32.TryParse (s,i) then Some !i
else None
val (|ParseInt|_|) : string -> int option
;;
Advanced Topics


Parameterized Patterns
Recursive Definition of Patterns
Parameterized Patterns

パターンはパラメタライズできる
 let (|ParseRegex|_|) re s =
if match re s then Some s else None ;;
val (|ParseRegex|_|)
: regex -> string -> string option
 match str with
| ParseRegex “\\d+”
s -> dec s
| ParseRegex “0x[\\dA-Fa-f]+” s -> hex s
Recursive Definition

実体は普通の関数なので、再帰的定義も可能
type ‘a joinlist = Empty
| Single of ‘a
| Join of ‘a joinlist * ‘a joinlist ;;
let
|
|
|
|
|
rec (|Nil|Cons|) = function
Empty
-> Nil
Single(x)
-> Cons(x, Empty)
Join(Nil, Nil)
-> Nil
Join(Nil,Cons(x,xs))-> Cons(x,xs)
Join(Cons(x,xs),ys) -> Cons(x,Join(xs,ys));;
Semantics
Semantics



Naïve Operational Semantics
Okasaki Condition
Implementation
Naïve Operational Semantics

上から順に試す
match v with
| pat1 -> expr1
| pat2 -> expr2
| …

pat1 と v がマッチするか試す


pat2 と v がマッチするか試す


マッチしたら環境を拡張してexpr1を評価。しなかったら
マッチしたら環境を拡張してexpr2を評価。しなかったら
…
Naïve Operational Semantics

“pat1 と v がマッチするかどうか”

パターンに関して構造帰納的に(ほぼ自明に)
定義される

Active Pattern p と値 v がマッチするかどうかは、
関数呼び出し式 (|p|) v の評価結果で決まる
Naïve Semantics (例)
 let (|Snoc|Nil|) = … ;;
 match [1;2;3] with
Nil
-> []
| Snoc(hh, t) -> [t] @ hh
(* Nil -> [] *)
match (|Snoc|Nil|) [1;2;3] with
Choice_2_1 () -> []
| _ ->
(* Snoc(hh,t) -> [t] @ hh *)
match (|Snoc|Nil|) [1;2;3] with
Choice_2_2 (hh,t) -> [t] @ hh
Okasaki Condition

Naïve Semantics には一つ問題あり
 副作用
(* Nil -> [] *)
match (|Snoc|Nil|) [1;2;3] with
Choice_2_1 () -> []
| _ ->
(* Snoc(hh,t) -> [t] @ hh *)
match (|Snoc|Nil|) [1;2;3] with
Choice_2_2 (hh,t) -> [t] @ hh
Okasaki Condition

Active Patternはユーザーが自由に定義できる
関数であるため、 (|Snoc|Nil|) が参照透明とは
限らない

元のプログラムではExhaustiveなmatch文だが、
以下のsemanticsではfailする可能性がある
(* Nil -> [] *)
match (|Snoc|Nil|) [1;2;3] with
Choice_2_1 () -> []
| _ ->
(* Snoc(hh,t) -> [t] @ hh *)
match (|Snoc|Nil|) [1;2;3] with
Choice_2_2 (hh,t) -> [t] @ hh
Okasaki Condition

Chris Okasaki, “Views for Standard ML”,
1998

SensibleなSemanticとするためには、「同じ引数には
高々１回しかユーザー定義パターンを適用してはなら
ない」という制約が必要

一つのmatch文の実行中は、ユーザー定義パターン
関数の１回目の呼び出し結果をテーブルに記憶して
おき、２回目以降は関数を呼ばずにその値を返す
Implementation

※ 現在(論文執筆時点)の実装は Okasaki
Condition を満たしていない → Future Work

[Scott and Ramsey 2000] Algorithm (効率的に
Decision Treeを作るHeuristics) を Active
Pattern の追加に対応させるためちょっと変更
Conclusion
Related Work

データ構造に対するViewの研究は最近盛んで
多くの関連研究がある（Referenceは略)

[Peyton Jones 2007] による分類





Parameterized Patterns
Partial Patterns
Total Patterns
Nesting
Patterns as first-class values
を全て兼ね備えているのはActive Patternだけらしい
Future Work

主に、F# にないHaskell等の言語機能で
Active Pattern と相性がいいものがないか探り
たい、としている

E.g. “Monadic Pattern Matching”

Partial Pattern と、それによる match 文は Maybe モナド
とみなすことができる。これを任意の MonadPlus に拡張
することは可能/有意義か？

Download Report