“Extensible Pattern Matching via a Lightweight Language Extension” の Survey POPL meeting 7/25 Kazuhiro Inaba

出典 “Extensible Pattern Matching via a Lightweight Language Extension” Don Syme, Gregory Neverov, James Margetson Accepted for ICFP 2007 F# の “Active Pattern” という拡張に関する論文 現在公開されているバージョンで使うことができます （ Submitted Draft を Web から入手可能）

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 なぜパターンマッチ？これでは不十分？ パターンマッチ形式の利点は 読みやすい 特に Case-Analysis が必要な場合読みやすい (nil?, head, tail 関数によるリスト操作と比較せよ ) Exhaustiveness のチェックもできて安全 type complex = {abstract} let my_function c obj = zoom (abs c) (rotate (arg c) obj)

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 my_function c obj = match c with Polar(r, t) -> zoom r (rotate t obj) ;; パターンとして使用 ( let (r,t) = (|Polar|) c in … と同義 )

Decomposition (| 識別子 | 識別子 |…| 識別子 |) という名前の関数を定 義  let (|Snoc|Nil|) lst = if lst = [] then Nil else Snoc(rev(tl(rev lst)), hd(rev lst)) ;; val (|Snoc|Nil|) : ‘a list -> Choice  match [1;2;3] with Nil -> [] | Snoc(hh, t) -> hh ;; Val it : int list = [3; 1; 2] パターンとして使用

Decomposition パターンの完全性の静的検査  match [1;2;3] with Snoc(hh,t) -> hh ;; match [1;2;3] with Snoc(hh,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\\d+ | 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

Naïve Operational Semantics Okasaki Condition Implementation

Naïve Operational Semantics 上から順に試す pat1 と v がマッチするか試す マッチしたら環境を拡張して expr1 を評価。しなかっ たら pat2 と v がマッチするか試す マッチしたら環境を拡張して expr2 を評価。しなかっ たら … match v with | pat1 -> expr1 | pat2 -> 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) -> hh (* Nil -> [] *) match (|Snoc|Nil|) [1;2;3] with Choice_2_1 () -> [] | _ -> (* Snoc(hh,t) -> hh *) match (|Snoc|Nil|) [1;2;3] with Choice_2_2 (hh,t) -> hh

Okasaki Condition Naïve Semantics には一つ問題あり 副作用 (* Nil -> [] *) match (|Snoc|Nil|) [1;2;3] with Choice_2_1 () -> [] | _ -> (* Snoc(hh,t) -> hh *) match (|Snoc|Nil|) [1;2;3] with Choice_2_2 (hh,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) -> hh *) match (|Snoc|Nil|) [1;2;3] with Choice_2_2 (hh,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 に拡張することは可能 / 有意義か？