順序付き線形型に基づく木構造処理プログラムから

順序付き線形型に基づく
木構造処理プログラムから
ストリーム処理プログラムへの変換
末永幸平 (東京大学)
児玉紘一 (東京工業大学)
小林直樹 (東京工業大学)
XML 処理の二つの手法
• 木構造処理
– メモリ上に木を作って処理
– 例: DOM API, XDuce, CDuce
• ストリーム処理
– ストリームからデータを読みつつ処理
– 例: SAX
木構造処理
node
node
leaf leaf
leaf leaf
2
3
3
4
ここを記述
メモリ
二次記憶, ネットワーク
<node>
<leaf>2</leaf>
<leaf>3</leaf>
</node>
<node>
<leaf>3</leaf>
<leaf>4</leaf>
</node>
ストリーム処理
メモリ
二次記憶, ネットワーク
ここを記述
<node>
<leaf>2</leaf>
<leaf>3</leaf>
</node>
<node>
<leaf>3</leaf>
<leaf>4</leaf>
</node>
木構造処理とストリーム処理の比
較
木構造処理ストリーム処理
記述性
○
×
メモリ効率
×
○
良い点だけを取りたい
研究の目標
node
node
leaf leaf
leaf leaf
2
メモリ
3
ここを記述
3
4
二次記憶, ネットワーク
<node>
<leaf>2</leaf>
<leaf>3</leaf>
</node>
<node>
<leaf>3</leaf>
<leaf>4</leaf>
</node>
研究の目標
node
node
記述性を保ちつつ
leaf leaf
leaf leaf
メモリ効率を向上させることが可能
3
2
3
4
メモリ
二次記憶, ネットワーク
ここに変換
<node>
<leaf>2</leaf>
<leaf>3</leaf>
</node>
<node>
<leaf>3</leaf>
<leaf>4</leaf>
</node>
例) 要素全てに1を足した木を作る
関数
• 木構造処理
簡単な変換で済ませたい
fix f. λt.
case t of
leaf x → leaf (x + 1)
| node x1 x2 → node (f x1) (f x2)
• ストリーム処理
fix f. λt.
case read() of
leaf → write(leaf); write(read() + 1)
| node → write(node); f (); f ()
変換できないプログラムの存在
例: 二分木の各ノードの左右を入れ替えるプログラム
node
leaf
1
node
node
node
leaf
leaf
leaf
2
3
3
leaf
leaf 1
2
正しく変換するためには...
• プログラムが正しい順序で部分木にアクセス
しなければならない
– 正しい順序: 左から右, 深さ優先順
• 解決策: 順序付き線形型を使って制限
– 型付け可能なプログラムは, 部分木に正しい順序
でアクセスしていることを保証
今回の範囲
• 木構造処理とストリーム処理のための
関数型言語を定義
– 対象データを二分木に限定する
– ストリーム処理言語ではメモリ上に木を作らせな
い
• メモリ上に木を構築する拡張を後で行う
• 順序付き線形型を用いた型システムを定義
• 前者から後者への変換アルゴリズムを定義
• アルゴリズムの正しさを証明
発表の流れ
•
•
•
•
•
•
対象言語の syntax
型システム
変換アルゴリズムとその正しさ
拡張に向けて
関連研究
まとめ
発表の流れ
•
•
•
•
•
•
対象言語の syntax
型システム
変換アルゴリズムとその正しさ
拡張に向けて
関連研究
まとめ
ソース言語とターゲット言語
• ソース言語: 木構造処理
– 入力データを木として処理
– λ計算 + 二分木操作プリミティブ
• ターゲット言語: ストリーム処理
– 入力ストリームからデータを読みつつ処理
– λ計算 + ストリーム操作プリミティブ
ソース言語の syntax
M (項) ::= i (整数) | x | λx.M
| M1 M2 | M1 + M2 | fix f. M
| leaf M | node M1 M2
| (case M of
leaf x → M1
| node x1 x2 → M2)
プログラム例
• 各整数に 1 を加えた木を返す関数
fix f. λt.
case t of
leaf x
→ leaf (x + 1)
| node x1 x2 → node (f x1) (f x2)
ターゲット言語の syntax
e (項) ::= i | x | λx.e | ()
| e1 e2 | e1 + e2 | fix f. e
| leaf | node
node (leaf 1) (leaf 2) は
| read e | write e node; leaf; 1; leaf; 2 という
ストリームで表現
| (case e of
(閉じタグは考えない)
leaf → e1
| node → e2)
プログラム例
• 各整数に 1 を加えた木を出力する関数
fix f. λx.
(case read () of
leaf → write leaf; write (read() + 1)
| node → write node; f (); f ())
プログラム例 (比較)
• ソースプログラム
– fix f.λt.(case t of
leaf x → leaf (x + 1)
| node x1 x2 → node (f x1) (f x2))
• ターゲットプログラム
– fix f.λt.(case read() of
leaf → write(leaf);write(read()+1)
| node → write(node);f ();f ())
発表の流れ
•
•
•
•
•
•
対象言語の syntax
型システム
変換アルゴリズムとその正しさ
拡張に向けて
関連研究
まとめ
型システム
• 順序付き線形型を用いた
ソース言語のための型システム
• 型付け可能なプログラムに対して以下を保証
– 各ノードを左から右, 深さ優先順に
丁度 1 度ずつアクセス
– 出力木をメモリに貯めない
型の syntax
τ (型) ::= Int | τ1 → τ2 | Treed
d (モード) ::= - (入力) | + (出力)
入力木型 (Tree-) と
出力木型 (Tree+) を区別
二種類の型環境
• (順序なし) 型環境 Γ
– { x1:τ1, x2:τ2, ..., xn:τn } (τi ≠ Treed)
• 変数の束縛の集合
– 順序が強制されない変数の型情報を保持
• 順序付き線形型環境 Δ
– x1:Tree-, x2:Tree-, ..., xn:Tree• 変数の束縛の列
– 「入力木が順番に一度ずつアクセスされる」
ことを表現
型判定
Γ|Δ├M:τ
M 中の自由変数が型環境 Γ, Δ に従った型の値に
束縛されるとき, M の評価結果は型τの値となり,
評価中に Δ の順で入力木がアクセスされる
型判定の例
Γ = f : Tree- → Tree+ のとき
Γ | x1 : Tree-, x2 : Tree- ├
node (f x1) (f x2) : Tree+
Γ | x1 : Tree-, x2 : Tree- ├
node (f x2) (f x1) : Tree+
型判定規則 (1/3)
Γ|x:Tree -├ x:Tree
Γ,x:τ | Ø ├ x:τ
-
(T-VAR1)
(T-VAR2)
順序付き型環境には余計なものは含まれない
= 入力木が丁度一回読み込まれる
型判定規則 (2/3)
Γ|x:Tree ├M
:τ
-
Γ|Ø├ λx.M :Tree →τ
Γ,x:τ1|Ø├M :τ2
Γ|Ø├ λx.M :τ1→τ2
(T-ABS1)
(T-ABS2)
型判定規則 (3/3)
Γ|Δ1├M1 :Tree
+
Γ|Δ2├M2 :Tree
Γ|Δ1,Δ2├ node M1 M2 :Tree
Γ|Δ1├M :Tree Γ,x:Int|Δ2├M1 :τ
- 2├M2 :τ
Γ|x1:Tree -,x2:Tree ,Δ
+
(T-NODE)
+
(T-CASE)
Γ|Δ1,Δ2├ case M of leaf x → M1 |node x1 x2 → M2 :τ
型付け例
Γ|Ø├ f : Tree- →Tree+
Γ|x1:Tree-├ x1 : Tree+
Γ|x1:Tree-├ f x1 : Tree+
Γ|x2:Tree-├ f x2 : Tree+
Γ|t:Tree-├ t :TreeΓx:Int|Ø├ leaf (x+1) :Tree+
Γ|x1:Tree-,x2:Tree-├ node (f x1) (f x2) :Tree+
Γ|t:Tree-├case t of leaf x => leaf (x + 1)
| node x1 x2 => node (f x1) (f x2) :Tree+
Γ|Ø├λt.(case t of leaf x => leaf (x + 1)
| node x1 x2 => node (f x1) (f x2)) :Tree- → Tree+
Ø|Ø├ fix f.λt.(case t of leaf x => leaf (x + 1)
| node x1 x2 => node (f x1) (f x2)) :Tree- → Tree+
(ただしΓ= f:Tree- → Tree+とする)
発表の流れ
•
•
•
•
•
•
対象言語の syntax
型システム
変換アルゴリズムとその正しさ
拡張に向けて
関連研究
まとめ
変換アルゴリズム
•
•
•
•
•
•
•
•
•
A(x) = x
A(i) = i
A(λx.M) = λx.A(M)
A(M1M2) = A(M1)A(M2)
A(M1 + M2) = A(M1) + A(M2)
A(fix f.M) = fix f.A(M)
A(leaf M) = write(leaf);write(A(M))
A(node M1 M2) -> write(node);A(M1);A(M2)
A(case M of leaf x => M1| node x1 x2 => M2)
= (case A(M);read() of
leaf => let x=read() in A(M1)
| node => [()/x1,()/x2]A(M2))
変換例
A(fix f.λt.(case t of
leaf x → leaf (x + 1)
| node x1 x2 → node (f x1) (f x2)))
= fix f.λt.(case t;read() of
leaf => let x = read() in (write(leaf);write(x + 1))
| node => write(node);f ();f ())
変換の正しさ
• 型付け可能なプログラムは, 変換によって
意味が変わらない
– 型検査を通れば, 変換によって必ず
ストリーム処理のプログラムを得ることが出来る
発表の流れ
•
•
•
•
•
•
対象言語の syntax
型システム
変換アルゴリズムとその正しさ
拡張に向けて
関連研究
まとめ
どのような拡張が必要か
• 型システムによる制限の緩和
– 入力木のスキップ
– 何度もアクセスできる木
今回は
この部分を紹介
• 一般の XML への対応
– 子要素の数は一般に 2 より大
– タグの種類の増加
• ストリーム処理で閉じタグも考える必要
拡張の方法
• ターゲット言語
– 入力木をスキップするプリミティブを導入
– メモリ上に木を構築するプリミティブを導入
– メモリ上の木へのパターンマッチを導入
• 型システム
– “何度も使える木” の型 (MTree) を導入
– 入力木スキップ, MTreeに関する規則を導入
– 型判定と変換アルゴリズムを融合
• 変換に型情報を利用するので
ターゲット言語への変更
e (項) ::= i | x | λx.e | ()
| e1 e2 | e1 + e2 | fix f. e
| leaf | node
| read e | write e | skip e | memtree e
| (case e of leaf → e1 | node → e2)
| (mcase e of
leaf x → e1
| node x1 x2 → e2)
型の拡張
τ (型) ::= Int | τ1 → τ2 | Treed | MTree
d (モード) ::= - (入力) | + (出力)
新しい型判定
• 型判定にプログラム変換を含めて書く
– 変換に型情報が必要になるので
Γ|Δ├M:τe
M 中の自由変数が型環境 Γ, Δ に従った型の値に
束縛されるとき, M の評価結果は型τの値となり,
評価中に Δ の順で入力木がアクセスされ,
M を変換するとターゲット言語の項 e になる
型判定規則への変更 (一部のみ)
Γ, x:MTree | Δ ├ M :τ  e
(T-MEMTREE)
Γ | x:Tree-, Δ ├ M :τ 
let x = memtree () in e
Γ|Δ├M:τe
(T-SKIP)
Γ | x:Tree-, Δ├ M : τ  let x = skip () in e
発表の流れ
•
•
•
•
•
•
対象言語の syntax
型システム
変換アルゴリズムとその正しさ
拡張に向けて
関連研究
まとめ
関連研究
• 属性文法を用いたXMLストリーム処理器の
自動導出（中野 ’03）
– 長所: ストリームの一部をメモリに確保できる
– 短所: 副作用を伴う処理の記述が難しい
• XMLストリーム処理のための言語XP++
(戸沢，萩谷 ’03)
– 長所: 型検査に基づいたノード補完
– 短所: ストリーム処理を意識するが必要
関連研究
• Ordered Linear Logic and applications.
(Polakow ’01)
• A type theory for memory allocation and
data layout. (Petersen et al. ’03)
– メモリ上のデータ配置の正しさを保証
まとめ
• 二分木を扱う木構造処理プログラムを
ストリーム処理プログラムへ変換する手法を
提案
• 変換可能かを判定するため、順序付き線形
型を用いた型システムを考案
• 変換の正しさを証明
Fin
例) 要素全てに1を足した木を作る
関数
• 木構造処理
– let rec f t =
match t with
Leaf x → Leaf (x + 1)
| Node x1 x2 → Node (f x1) (f x2)
• ストリーム処理
– let rec f () =
match read () of
Leaf → write Leaf; write (read() + 1)
| Node → write Node; f (); f ()
型判定規則への変更 (一部のみ)
Γ, x:MTree | Δ ├ M :τ  e
(T-MEMTREE)
Γ | x:Tree-, Δ ├ M :τ 
let x = memtree () in e
Γ | Δ1├ M : MTree  e
Γ, x:Int | Δ2├ M1:τ  e1
Γ, x1:MTree, x2:MTree | Δ2 ├ M2 :τ  e2
(T-MCASE)
Γ | Δ1, Δ2├ case M of leaf x → M1 | node x1 x2 → M2 :τ
 mcase e of leaf x → e1 | node x1 x2 → e2

Download Report