Download presentation
Presentation is loading. Please wait.
Published byこうしろう いんそん Modified 約 8 年前
1
“Extensible Pattern Matching via a Lightweight Language Extension” の Survey POPL meeting 7/25 Kazuhiro Inaba kinaba@is.s.u-tokyo.ac.jp
2
出典 “Extensible Pattern Matching via a Lightweight Language Extension” Don Syme, Gregory Neverov, James Margetson Accepted for ICFP 2007 F# の “Active Pattern” という拡張に関する論文 現在公開されているバージョンで使うことができます ( Submitted Draft を Web から入手可能)
3
Motivation
4
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
5
Motivation なぜパターンマッチ?これでは不十分? パターンマッチ形式の利点は 読みやすい 特に Case-Analysis が必要な場合読みやすい (nil?, head, tail 関数によるリスト操作と比較せよ ) Exhaustiveness のチェックもできて安全 type complex = {abstract} let my_function c obj = zoom (abs c) (rotate (arg c) obj)
6
Examples
7
Active Patterns by Examples Total Patterns Single Total Patterns Decomposition with Recognizers Partial Patterns
8
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 … と同義 )
9
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) -> [t] @ hh ;; Val it : int list = [3; 1; 2] パターンとして使用
10
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]
11
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”
12
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
13
Advanced Topics Parameterized Patterns Recursive Definition of Patterns
14
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
15
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));;
16
Semantics
17
Naïve Operational Semantics Okasaki Condition Implementation
18
Naïve Operational Semantics 上から順に試す pat1 と v がマッチするか試す マッチしたら環境を拡張して expr1 を評価。しなかっ たら pat2 と v がマッチするか試す マッチしたら環境を拡張して expr2 を評価。しなかっ たら … match v with | pat1 -> expr1 | pat2 -> expr2 | …
19
Naïve Operational Semantics “pat1 と v がマッチするかどうか ” パターンに関して構造帰納的に ( ほぼ自明に ) 定義される Active Pattern p と値 v がマッチするかどうかは、 関数呼び出し式 (|p|) v の評価結果で決まる
20
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
21
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
22
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
23
Okasaki Condition Chris Okasaki, “Views for Standard ML”, 1998 Sensible な Semantic とするためには、「同じ引数 には高々1回しかユーザー定義パターンを適用し てはならない」 という制約が必要 一つの match 文の実行中は、ユーザー定義パター ン関数の1回目の呼び出し結果をテーブルに記憶 しておき、2回目以降は関数を呼ばずにその値を 返す
24
Implementation ※ 現在 ( 論文執筆時点 ) の実装は Okasaki Condition を満たしていない → Future Work [Scott and Ramsey 2000] Algorithm ( 効率的 に Decision Tree を作る Heuristics) を Active Pattern の追加に対応させるためちょっと変 更
25
Conclusion
26
Related Work データ構造に対する View の研究は最近盛んで 多くの関連研究がある ( Reference は略 ) [Peyton Jones 2007] による分類 Parameterized Patterns Partial Patterns Total Patterns Nesting Patterns as first-class values を全て兼ね備えているのは Active Pattern だけらしい
27
Future Work 主に、 F# にない Haskell 等の言語機能で Active Pattern と相性がいいものがないか探 りたい、としている E.g. “Monadic Pattern Matching” Partial Pattern と、それによる match 文は Maybe モ ナドとみなすことができる。これを任意の MonadPlus に拡張することは可能 / 有意義か?
Similar presentations
© 2024 slidesplayer.net Inc.
All rights reserved.