型クラスの原点 How to make ad-hoc polymorphism less ad hoc を読んだ話

オレオレ型クラスの話をやめろ。原典に当たれ。ということで、Haskell に型クラスの導入を提案した論文とされる Philip Wadler. How to make ad-hoc polymorphism less ad hoc を読んだのでそれをまとめる話です。

型クラス導入の目的

2 つの多相

多相にはアドホック多相、パラメトリック多相の 2 つの種類がある。

アドホック多相

アドホック多相は、ある関数が受け入れる型によって 型に応じた振る舞いをするような多相 。典型的なのは関数や演算子のオーバーロード。

3 * 3
3.14 * 3.14

同じ演算子 * だけど、整数型と浮動小数点数型どちらでも使えています。

パラメトリック多相

名前の通り、型を表すパラメータを取ることによって 型によらない共通の振る舞いをする多相 。典型的なのは length 関数。

 length :: [a] -> Int

配列であれば中の型に関係なく使うことができる。

Hindley/Milner 型システムと多相

パラメトリック多相については Hindley/Milner 型システムがよく扱えるということで広く用いられていたけど、アドホック多相については良い手法がなかった(ためアドホック多相が導入されていなかった)。

この論文では、型クラスってものを導入して Hindley/Milner 型システムを拡張することでオーバーロード = アドホック多相ができるようにするよ。

アドホック多相の制約

算術演算の場合

整数型と浮動小数点数型にオーバーロードされた乗算演算子 * を考える。この演算子 * はアドホック多相にできるけど、それを利用した関数はアドホック多相にできない。

-- これはできない
square x = x * x

square 3
square 3.14

関数自体を Int -> Int と Float -> Float にオーバーロードさせることもできるけど

squares (x, y, z) = (square x, square y, square z)

みたいな関数を考えるとき、組み合わせが爆発する。

同値評価の場合

同値性を評価する場合にも同じような問題がある。

-- これはできない
member [] y = False
member (x:xs) y = (x == y) \/ member xs y

member [1, 2, 3] 2
member "Haskell" 'k'

そこで同値性についてはパラメトリック多相で対応するアプローチが試された。

(==) :: a -> a -> Bool
member :: [a] -> a -> Bool

ただ、この方法だと関数型や抽象データ型などの同値評価ができない型を渡しても静的に型エラーを起こすことができず、実行時に評価しようとしてエラーすることになってしまった。

そこで同値評価できる型だけに同値性評価できるように制約を書ける方法が Standard ML で導入された。

(==) :: a(==) -> a(==) -> Bool
member :: [a(==)] -> a(==) -> Bool

この方法では、関数型や抽象データ型などを member 関数に渡すと型エラーにすることができるようになったけれど、Standard ML では参照型の同値性評価は他の型の同値性評価と異なるように設計されていたので、同値性評価する型の峻別のためにランタイムシステムを構築する必要が出てきてしまった。

これに対してオブジェクト指向では、データに対して実装を与えるメソッドのポインタの集合 = 辞書 を持っているので、同値性評価関数に渡ってくる引数のいずれかの辞書に含まれる同値性評価のメソッドを用いて評価することができる。

このメソッドの集合をデータと一緒に渡すのがいい感じだから、型クラスでもこのアイディアが背景としてあるよ。

型クラスの導入例

まず、型クラスを実際に導入したコード例を示す。

class Num a where
    (+), (*) :: a -> a -> a
    negate   :: a -> a

instance Num Int where
    (+)    = addInt
    (*)    = mulInt
    negate = negInt

instance Num Float where
    (+)    = addFloat
    (*)    = mulFloat
    negate = negFloat

square            :: Num a => a -> a
square x          = x * x

squares           :: Num a, Num b, Num c => (a, b, c) -> (a, b, c)
squares (x, y, z) = (square x, square y, square z)

型クラスの定義

このコードで型クラス Num が class キーワードによって定義されている。Num 型クラスは (+)、(*)、negate が定義されている型 a が所属している。

続いて、instance として型 a を具体化した実装を与えている。これらは Num の要求する関数を実装しているか型検査される。たとえば

addInt :: Int -> Int -> Int

が検査される。

型クラス制約の利用

型クラスの導入によって、前述の square や squares が実装できた！

ここで square の型は Num a => a -> a となっているが、Num a => によって型 a は Num が実装されていることが要求されている。この square は次のように利用できる。

square 3
square 3.14

そしてもちろん

square 'x'

は Num Char の instance が存在しないからコンパイル時に静的に型エラーにできる！

アドホック多相が実現できていることが確認できる。

型クラスの 変換

実際にはこの型クラスの仕組は、コンパイル時に型クラスを用いない形に変換されて Hindley/Milner 型システムで扱えるようになる。つまりは型クラスはある種の糖衣構文になっている。

上記のコード例を型クラスを用いない形に変換したものが下記のコード。

data NumD a = NumDict (a -> a -> a) (a -> a -> a) (a -> a)
add (NumDict a m n) = a
mul (NumDict a m n) = m
neg (NumDict a m n) = n

numDInt     :: NumD Int
numDint     =  NumDict addInt mulInt negInt

numDFloat   :: NumD Float
numDFloat   =  NumDict addFloat mulFloat negFloat

square'          :: NumD a -> a -> a
square' numDa x  =  mul numDa x x

squares'  :: (NumD a, NumD b, NumD c) -> (a, b, c) -> (a, b, c)
squares' (numDa, numDb, numDc) (x, y, z)
          =  (square' numDa x, square' numDb y, square' numDc z)

class 宣言の代わりに、class で定義されていた関数の型を持つデータ型の辞書 NumDict とそれらのメソッドにアクセスするための関数が定義されている。¹

instance で宣言されていた部分は、上記の NumD a 型のデータ型の値として変換される。

numDInt     :: NumD Int
numDInt     =  NumDict addInt mulInt negInt

やってることは単純で、NumDict 値コンストラクタで値を埋めているだけ。Float も同じ。こうやって作った辞書をもとに演算は以下のように書き換えられる。

x + y     -->  add numD x y
x * y     -->  mul numD x y
negate x  -->  neg numD x

ここで引数に渡っている numD は適当な演算の入った辞書。

ここからが型クラスのマジックで、適当な演算の入った辞書が型によって自動的に挿入される！

3 * 3       -->  mul numDInt 3 3
3.14 * 3.14 -->  mul numDFloat 3.14 3.14

これによって型によって処理を切り替えるというアドホック多相が実現された。

square'          :: NumD a -> a -> a
square' numDa x  =  mul numDa x x

square 3     -->  square' numDInt 3
square 3.14  -->  square' numDFloat 3.14

力尽きたので Eq 型クラスからの話(型クラスの継承等)については割愛。変換のルール自体は上記に示されたもの。あとで書くかもしれない。

まとめ

というわけで、型クラスはオブジェクト指向でない静的型付け言語、特に Hindley/Milner 型システムを持った言語において、Hindley/Milner 型システムを用いてアドホック多相を実現する手法として導入されました。その型クラスのお手本になったのは実はオブジェクト指向言語のサブタイピング多相であり、オブジェクト指向における関数ポインタの辞書を文字通り Haskell におけるデータ型の辞書として読み替えて この辞書を型に応じて挿入する というものでした。

型クラスの原典に当たって、これで一安心ですね。

実は、全く同様の実装が Scala で借用されており、Haskell における型クラスが脱糖されたような状態で書けるようになっています。また、最近登場した Swift や Rust でも型クラスと似たようなことができるようになっています。おもしろいですね。

おしまい

参考

Philip Wadler. How to make ad-hoc polymorphism less ad hoc
Instances and Dictionaries - School of Haskell

1. 現在の GHC の実装ではレコードによって一括定義するようにしているらしい data NumD a = NumDict {add :: a -> a -> a, mul :: a -> a -> a, negate :: a -> a} みたいな ↩