この記事は CAMPHOR- Advent Calendar 18日目の記事です．

こんにちは @yu_i9 です．CAMPHOR- Advent Calendar には今年が初参加になります！本記事では「Typing Haskell in Haskell (通称 thih)」から型クラスを含んだ型推論のエッセンスを紹介したいと思います．多少専門的な内容ですが，なるべく多くの人に理解してもらえるように頑張ります．

論文のホームページは以下になります．論文本体とオリジナルの実装が利用できます．

1.概要

Typing Haskell in Haskell から型クラスを含む型推論のアイディアを実装を交えて紹介します．
オリジナルの実装を修正し stack でビルドできるようにしました．

2.注意

現在の仕様・実装とは異なる部分が存在する可能性があります．
実装は基礎概念を理解するためのものでエラー処理や効率は考慮されていません．
説明のため特に説明なくコードを省略・改変している部分があります．

以上3点に注意して本編をお読みください．

3.準備

必要な知識を準備します．分かる方は飛ばしていただいて結構です．

3.1.カインド

カインドとは「型の型」を指す概念です．「値には型が付き」「型にはカインドが付く」という対応関係で見れば分かりやすいでしょう．値と型の関係を一段階持ち上げた時に出てくるのがカインドです．Haskellでは「（引数を取ったりしないという意味で）単純」な型に対してカインド * (Star) を与え，それを -> (Kfun) で組み合わせることで型を引数に取ったり適用したりということ表現します．

例を見てみましょう．

- Int, String, Int -> Int :: *
- [] :: * -> *
- [Int] :: *

カインドを利用すれば，例えば Monad m なる m に Int を代入するといった操作を防ぐことができます．この場合，前者のカインドは * -> *，後者のカインドは * でカインドが異なるため代入が不正であると判断されます．

3.2.型代入

型代入とは型変数を型へマッピングする関数のことです．実装ではそのまま型変数から型への Map で表現されることが多いです．

a -> b に型代入 [(a, Int), (b, Char -> Char)] を適用
=> Int -> Char -> Char

3.3.単一化

単一化とは二つの型 t1 と t2 が与えられた時に t1 と t2 が等しくなるような型代入を発見する操作のことです．この操作においては最も一般的な（つまり他のあらゆる代入はその代入を拡張することで得られる）代入を得ることが重要です（後述 4.1.4）．例を以下に示します．

a -> b と Int -> Int -> c を等しくするような代入をいくつか考えます．

[(a, Int), (b, Int -> Int), (c -> Int)]
=> Int -> Int -> Int

[(a, Int), (b, Int -> c)]
=> Int -> Int -> c

以上の型代入は二つの型を単一化しますが，二つ目の例が c を残しているのでより良い解であると言えます．

3.4.型スキーム

型スキームは多相性を記述するための概念です．「多相的に扱って良い型変数のリスト」と型の組で表されます．型推論中のコンテキストで変数を型スキームと結びつけておけば，ある変数を参照するたびに，型スキームで多相的に扱って良いとされている変数をフレッシュな型変数に置き換えられるので，簡単に多相性を表現できます．分かりづらいと思うので例を見てみましょう．

length :: [a] -> Int

hoge = length [1, 2, 3] + length [True, False]

もしも length の型が型スキームとして扱われていなかったら，length [1, 2, 3]に対して型推論を実行した時点でa = Intとなりlength [True, False]の型推論が失敗してしまいます．length の型が型スキームとして扱われていれば，length [1, 2, 3]の型推論を行うときにはlength :: [a1] -> Intとしてa1 = Intを得て，length [True, False]の型推論ではlength :: [a2] -> Intとしてa2 = Bool を得ることができます．このように，参照するたびに新しい型変数でインスタンス化して多相性を獲得するのが型スキームの考え方です．

4.型推論

さて，準備が終わったので実際にHaskellの型推論を見て行きましょう．以下の3段階で進みます．

型と単一化
型クラス
型推論全体のアイディア

4.1.型と単一化

ここではまず型とカインドを定義し型代入と単一化を考えていきます．

4.1.1.カインド

data Kind = Star | Kfun Kind Kind deriving(Eq)

-- * -> *      = Kfun Star Star
-- * -> * -> * = Kfun Star (Kfun Star Star)

4.1.2.型

type Id    = String
data Tyvar = Tyvar Id Kind deriving Eq
data Tycon = Tycon Id Kind deriving Eq

data Type  = TVar Tyvar      -- 型変数
           | TCon Tycon      -- 型定数 Bool, IO, Monad … など
           | TAp  Type Type  -- 型適用 IO Int など
           | TGen Int        -- 型スキームで量化された型変数 (後述)
           deriving Eq

-- tInt  = TCon (Tycon "Int" Star)
-- tList = TCon (Tycon "[]" (Kfun Star Star)) … つまり型レベルの[]
-- [a]   = TAp tList (TVar (Tyvar "a" Star))

-- カインドの右結合性に注意しながらTApで一つずつ型を適用して構築していきます．

4.1.3.型代入

型代入は3.2で説明した通りの定義になっています．

type Subst = [(Tyvar, Type)]

(+->) :: Tyvar -> Type -> Subst
u +-> t = [(u, t)]

class Types t where
  apply :: Subst -> t -> t
  tv    :: t -> [Tyvar]

instance Types Type where
  apply s (TVar u)  = case lookup u s of
                        Just t  -> t
                        Nothing -> TVar u
  apply s (TAp l r) = TAp (apply s l) (apply s r)
  apply s t         = t

  tv (TVar u)  = [u]
  tv (TAp l r) = tv l `union` tv r
  tv t         = []

infixr 4 @@
(@@) :: Subst -> Subst -> Subst
s1 @@ s2 = [ (u, apply s1 t) | (u,t) <- s2 ] ++ s1

apply は代入 s を型 t に適用する関数で，型変数 tyvar を発見した時には，Subst で最初に見つかった(tyvar, t')の t' で置き換えます（この動作は lookup の仕様に依存しています）．
tv 関数は型の中に存在する型変数の集合を返します．

これら二つの関数は Types 型クラスのメンバ関数として定義されており，これから登場する Type を含んだdata型に対しても自然に定義されます．他のケースではデータ構造を崩して Type 型まで関数を伝播させるだけなので特に実装は提示しません．

@@は代入を合成する関数です．apply (s1@@s2) = apply s1 . apply s2を満たします．

4.1.4.単一化

上で説明したとおり単一化とは二つの型を等しくするような型代入を発見する操作です．そのような型代入のことを単一化子 - unifier と呼びます．このとき重要なのは「最も一般的な単一化子 - most general unifier, mgu」を発見することです．s が mgu であるとは，任意の単一化子 u についてなんらかの単一化子 s' が存在して u = s' @@ s となることです．この定義から mgu を適用することによって得られる型が最も一般的であるということがわかります．length :: [Int] -> Int よりも length :: [a] -> Int という推論が行われたほうが便利なように，単一化の結果はできる限り一般的なものが良いのです．

以下に示す mgu 関数は，二つの型に対する単一化子が存在する時は必ず mgu を計算します．本当にそうなのか気になる方は帰納法を回してみるとよいでしょう．

mgu :: Monad m => Type -> Type -> m Subst
mgu (TAp l r) (TAp l' r') = do s1 <- mgu l l'
                               s2 <- mgu (apply s1 r) (apply s1 r')
                               return (s2 @@ s1)
mgu (TVar u) t = varBind u t
mgu t (TVar u) = varBind u t
mgu (TCon tc1) (TCon tc2)
    | tc1==tc2 = return nullSubst
mgu t1 t2 = fail "types do not unify"

varBind :: Monad m => Tyvar -> Type -> m Subst
varBind u t | t == TVar u      = return nullSubst
            | u `elem` tv t    = fail "occurs check fails"
            | kind u /= kind t = fail "kinds do not match"
            | otherwise        = return (u +-> t)

varBind では型変数と何らかの型 t を単一化する場合の処理を記述しています．ひとつ目の条件は u |-> u なる代入を生成しないようにしています．二つ目の条件は u |-> u -> Int のように無限の型が生成されないようにしています．三つ目の条件ではカインドが異なる代入を生成しないようにしています．

4.2.型クラス

さて今回の記事の本題とも言える章です．型クラスは他のML系言語にはない独特の機能です．ひとことで言えば関数のオーバーロードの仕組みで，Haskellの抽象化機構を支える重要な機能です．しかし一方で型クラスは型推論を複雑にする機能の一つでもあります．この章では型クラスやその環境を定義し，クラス宣言やインスタンス宣言の整合性をチェックすることを考えていきます．

4.2.1.Predicates

ある型が型クラスに属していることを表す情報を predicate (ここでは「述語」と訳します）と呼びます．Applicative m => Monad m とあったとき，=>の両側にあるものが述語です．これは以下のように実装できます．

data Pred = IsIn Id Type deriving Eq

-- Monad m = IsIn "Monad" (TVar (Tyvar "m" (Kfun Star Star)))

4.2.2.Qualified

=>によって述語の制約が与えられることを qualified （ここでは「修飾」と訳します）と呼びます．

Applicative m => Monad m とあったとき，Monad m という述語は Applicative m という述語によって修飾されています．これは以下のように定義されます．修飾する対象は述語の場合と型の場合があるので，その部分を t として抽象化しています．

data Qual t = [Pred] :=> t deriving Eq

-- Monad m => m a = (IsIn "Monad" (TVar (Tyvar "m" (Kfun Star Star))))  
--                  :=> TAp (TVar (Tyvar "m" (Kfun Star Star))) 
--                          (TVar (Tyvar "a" Star))

4.2.3.型クラスと環境

-- 型クラスは上位クラス名のリストとインスタンスのリストの組で与えられる
type Class = ([Id], [Inst])

-- インスタンスは [Pred] :=> Pred の形で与えられる
type Inst = Qual Pred

data ClassEnv = ClassEnv { classes  :: Id -> Maybe Class }

-- 上位クラスを求める
super :: ClassEnv -> Id -> [Id]
super ce i = case classes ce i of Just (is, its) -> is

-- インスタンスを求める
insts     :: ClassEnv -> Id -> [Inst]
insts ce i = case classes ce i of Just (is, its) -> its

4.2.4.Entailment

型推論中に得られた述語 ps が全て満たされている時に，新たに得られた述語 p に整合性があるかをチェックします（このことを entailment 処理と述べていますが，良い訳が見つからなかったので特に訳しません）．この問題は二つの処理に分けることができます．

ps および ps から得られる上位クラスの中に p が含まれていれば直ちに整合性があると判断できる．
型クラス環境 ce を用いれば，述語 p で述べられている型クラスのインスタンスを全て求めることができる．そのインスタンスの中で，p に一致，もしくは p を包含するようなインスタンス qs が存在すれば，qs の上位クラスに関して整合性をチェックする問題に置き換えることができる．

後者の問題で述べている「p に一致，もしくは p を包含するようなインスタンス qs」かを判定するために match という操作が用いられます．単一化が apply s t1 = apply s t2 なる s を発見する操作であったのに対して，match は apply s t1 = t2 なる s を発見する操作です．例えば instance Eq a が環境に存在するなら，これは instance Eq Int などに match するので包含関係を確認することができます．

以下にコードを示します．

-- 「ps および ps から得られる上位クラス」を求める
bySuper :: ClassEnv -> Pred -> [Pred]
bySuper ce p@(IsIn i t)
 = p : concat [ bySuper ce (IsIn i' t) | i' <- super ce i ]

-- 「p に一致，もしくは p を包含するようなインスタンス qs」を求める
byInst :: ClassEnv -> Pred -> Maybe [Pred]
byInst ce p@(IsIn i t)    = msum [ tryInst it | it <- insts ce i ]
 where tryInst (ps :=> h) = do u <- matchPred h p
                               Just (map (apply u) ps)

entail :: ClassEnv -> [Pred] -> Pred -> Bool
entail ce ps p = any (p `elem`) (map (bySuper ce) ps) ||
                 case byInst ce p of
                   Nothing -> False
                   Just qs -> all (entail ce ps) qs

4.3.型推論のアイディア

最後の章です．ここからはコードを掲載せずに言葉でアイディアを説明していきます．コードを全て掲載して説明していたらここからさらに3倍くらいの分量になりますし，そもそもそこまでやるなら元の論文を読んだほうがずっと良いですし……

対象にするのは「型が宣言された関数定義」です．前処理を経たデータは以下のような要素で構成されています．

関数名
宣言された型に対応する型スキーム
関数定義における = の左辺．つまり変数をどのように束縛するかについての情報．
関数定義における = の右辺．式 / Expr

ここから型推論を始めます．まずは宣言された型スキームをインスタンス化し，述語のリスト qs と型 t を得ます．型の宣言における => の左側と右側にそれぞれ対応しています．ここで得られた情報から，我々がやらなければいけないことは以下の二つに分けられます．

t と関数本体から推論された型 t' を単一化できるか調べる．単一化できれば型が合っているということになります．
関数本体の推論で得られた述語 ps が，既に宣言されている述語 qs と矛盾していないかを調べる．4.2.4 で述べた entailment 処理にあたります．

-- 全体図

hoge :: qs => t
hoge x1    x2  ...   xn =  式  -- 式の型推論中に述語 ps が得られる
     ::    ::        ::    ::
    (a1 -> a2 ->  -> an -> b ) = t' とする

-- 1. t と t' を単一化する．つまり宣言された型と推論した型が一致するか調べる．
-- 2. qs のもとで ps が成立するか調べる（entailment 処理)

ひとつ目を見て行きましょう．関数本体から推論される型 t' を求めるのが目的です．最初に = の左辺から得られた情報を考えます．関数の引数が x1, x2, ... , xn であるなら，まずはそれぞれについて a1, a2, ..., an なる型変数を生成します．すると全体の型 t' は a1 -> a2 -> ... -> an -> 右辺の型 というように書けます．

次に = の右辺にあたる式ですが，この部分は大まかな動作を説明するにとどめます．大まかな動作は，式の抽象構文木を再帰的にたどって各部分に対応する型を返すというものです．例えば変数を見つけたら型環境を参照して得られた型を返す，関数適用 e1 e2 が現れたら e1 が要求する引数の型と e2 の型を単一化したあと e1 の結果の型を返す，といったような動作をします．

ただ一つ注意しなければいけないのは，通常の型推論が結果の型だけ返すのに対して，今回の場合は途中で得られる述語も返すことです．例えば式を再帰的に処理する過程で変数 show が現れたとしましょう．show は Prelude にある関数ですから，事前に show :>: Show a => a -> String という情報が環境に登録されています（型スキーム化されていることに注意）．型推論で変数を見つけた時は対応する型スキームをインスタンス化しなければいけません．ここでは型変数に b1 を用いましょう．すると，show 部分の型推論の結果は，

結果の型 b1 -> String
述語 Show b1

の組になります．このように型クラスを含んだ型推論では，通常の型推論の処理と並行して型クラスの制約が積み上げられていきます．

さて，かなり乱暴でしたが関数定義の右辺についても型推論を行ったことにしましょう．その結果，型 b と述語のリスト ps が得られたものとします．すると関数定義全体の型推論の結果は以下のようになります．

結果の型 t' = a1 -> a2 -> ... -> an -> b
述語のリスト ps

最後に，得られた t' と型宣言から得られた t を単一化すれば上で述べた処理のうちのひとつ目をクリアしたことになります．

次にふたつ目の処理を見てみましょう．ここまでの説明で，我々はすでに関数本体の型推論で得られる述語のリスト ps を持っています．その整合性は以下のようにチェックすることができます．

if null (filter (not . entail classEnv qs) ps)
then ... -- OK
else ... -- fail

既に述べられている qs を引数にして，ps に対して entailment 処理を実行します．その結果，整合性がないと判断された述語が一つでもあれば型推論は失敗します．

5.実装

ホームページで公開されているコードを GHC 7.10.2 でも動くように修正して公開しています．

大きな変更点は以下の二つです．

それっぽくモジュール分割した
stack でビルド可能にした

分かっている主な問題点は以下の二つです．

実装されているライブラリが当時のまま
パーサーがないので生のASTを書かなければいけない

一口にパーサーを書くと言っても，型推論の手前まで持って行くには，今回の論文で「型推論に先立って行われるものとする」とされていたものを全て自力で書くことになるのでちょっとした大仕事です．これ以上の使いやすさを求めるとなると，GHCを引っ張ってきてハックするほうが現実的かもしれません．これらの実装の目的は，あくまで実装を通して型推論を理解することであったというところでご理解いただきたいと思います．

まとめ

ずいぶんと長くなりましたが以上が「概観」となります．この内容をベースにして，thih の完全な実装，GHCのデフォルトの型推論，GHC拡張…と深めていくことができるでしょう．今回の記事がみなさまの楽しい型推論ライフの一助となれば幸いです．

明日の CAMPHOR- Advent Calendar 2015 19日目は @siriusjack が書いてくれます！お楽しみに！！