Relaxed Dependency Analysis

Presentation on theme: "Relaxed Dependency Analysis"— Presentation transcript:

1 Relaxed Dependency Analysis
〜Haskell 2009年末の集い〜 酒井 政裕

2 酒井 政裕 自己紹介 Blog: ヒビルテ Twitter: @masahiro_sakai 2001年末ごろにHaskellに遭遇
好きな関数: unfoldr

3 背景: Haskellの型推論の流れ 依存関係(の強連結成分)で定義をグループ化 末端のグループから順に型推論
例: 以下では b, c の型をまず推論し、その結果を使って a の型を推論 a = … b … b = … c … c = … b … a b c

4 Relaxed Dependency Analysis
依存関係の定義の変更 Haskell98では、aがbを参照していれば、 aはbに依存していた Haskell2010では、bに型宣言がある場合には、 aがbを参照していても、依存とはみなさない 効果 より多相的な型を推論出来るようになる これまで型宣言が必要だったのが、不要になることがある

5 例: Haskell98の場合 f :: Eq a ⇒ a → Bool f x = (x == x) ∨ g True ∨ g “Yes”
g y = (y ≤ y) ∨ f True fとgは相互に依存しているので、同時に型推論 g が二通りの型で使われている Bool → Bool String → Bool ⇒ 型エラー f g

6 例: Haskell2010の場合 × f :: Eq a ⇒ a → Bool
f x = (x == x) ∨ g True ∨ g “Yes” g y = (y ≤ y) ∨ f True fには型宣言があるので、 gはfには依存しない gを先に型推論して、 g :: ∀a. Ord a ⇒ a → Bool fの型推論では、gの型変数aをBoolとStringに具体化 f g ×

7 何が起こっているのか? Haskellの基づいているHindley-Milnerのアルゴリズムでは、ある定義グループの型推論の最後の段階で型を多相的にする。 なので、先に型推論が済んでいる部分は、型が多相的な型になっているので、それを任意に具体化出来る。 一方、型推論中の部分は、型が多相的になっていないので、複数の型で使うことが出来ない。

8 おまけ: Hindley-Milner 型推論の例
f x = let g y = (x,y) in g True の型推論 x :: α とおく g y = (x,y) の型推論 y :: β とおいて g :: β → (α,β) βに関して汎化して g :: ∀t. t → (α, t) (※ 前提に含まれる α に関しては汎化しない) g True では、g の型変数 t を Bool に具体化して、 g True :: (α, Bool) f :: α → (α, Bool) αに関して汎化して、f :: ∀u. u → (u, Bool)