Edited at

Levity polymorphismについて軽く

More than 1 year has passed since last update.

ghc-8.0.2, ghc-8.2.1で挙動確認しています。

Haskellでの多相性には主にparametric polymorphismとad-hoc polymorphismがありますが、そちらに関してはHaskell入門1をお読みください。

ここではghc-8.0あたりから導入された新しい多相性、levity polymorphismについて軽く説明します。

advancedな話題なのでHaskell入門を読んでいる途中の方は分からなくても気にしないでください。


概要

関数呼び出しの際にヒープを指しているポインタ、例えばリストのようなものと、倍精度浮動小数点数を渡す時には使われるレジスタは異なったりします。それらをパラメトリック多相で一緒に扱うコードを生成することはできません。この問題の簡単な解決方法は全てをヒープにアロケートされた値として扱うことです。そうすることによって全ての値を同じように扱うことができるようになりますが、同時に大きなパフォーマンス上のペナルティが加わります。

Levity polymorphismはこのcalling conventionを超えた抽象化を可能にします。またパフォーマンスペナルティもありません。

しかし制約も追加されます。levity polymorphicな値は関数の引数に渡せない、というものです。

このエントリでは簡単な例と、実用上の注意点を軽く説明します。


簡単な例

toString :: a -> Stringというメソッドを持つToStringを定義することを考えます。PreludeにはShowクラスが存在しますが、今回はlevity polymorphicな関数を考えます。つまりInt#のような値を引数に渡せるようにします。

LevityPolymorphismには専用の拡張はなく、TypeInTypeが必要です。TypeInTypeとは種を型と同じ構造にしてしまい、同じように扱えるようにする拡張です。

{-# LANGUAGE TypeInType #-}

{-# LANGUAGE MagicHash #-}
{-# LANGUAGE TypeApplications #-}
module Main where

import GHC.Types
import GHC.Prim

main :: IO ()
main = do
putStrLn $ toString 42#
putStrLn $ toString @_ @Int 42

class ToString (a :: TYPE r) where
toString :: a -> String

instance ToString Int# where
toString x = "I# " ++ show (I# x)

instance ToString Int where
toString x = show x

これによってInt#についてもStringへ変換できるようになりました。

TYPEとは(kind-levelに書いてますがTypeInTypeによって型と種は同じに扱えます)組み込みの型コンストラクタです。TYPE, *, RuntimeRep あたりを確認しておきます。それらはdatatypeで型として定義されていますが、kindとして扱うことを期待されているものです。

data TYPE (a :: RuntimeRep) :: RuntimeRep -> *

type * = TYPE LiftedRep

data RuntimeRep = VecRep VecCount VecElem -- ^ a SIMD vector type
| TupleRep [RuntimeRep] -- ^ An unboxed tuple of the given reps
| SumRep [RuntimeRep] -- ^ An unboxed sum of the given reps
| LiftedRep -- ^ lifted; represented by a pointer
| UnliftedRep -- ^ unlifted; represented by a pointer
| IntRep -- ^ signed, word-sized value
| WordRep -- ^ unsigned, word-sized value
| Int64Rep -- ^ signed, 64-bit value (on 32-bit only)
| Word64Rep -- ^ unsigned, 64-bit value (on 32-bit only)
| AddrRep -- ^ A pointer, but /not/ to a Haskell value
| FloatRep -- ^ a 32-bit floating point number
| DoubleRep -- ^ a 64-bit floating point number

次の型クラスはlevity polymorphic type classとなっています。パラメータr :: RuntimeRepによるものです。

class ToString (a :: TYPE r) where

toString :: a -> String

TYPE r周辺の事情をもう少し説明してみます。一般に、kindを省略した型クラス(Cとします)は次のように扱われます。

class C (a :: *)

つまりは*の定義より次と同じです。

class C (a :: TYPE LiftedRep)

このうちLiftedRepを型パラメータr :: RuntimeRepで抽象化すればlevity polymorphicなtype classというわけです。

class C (a :: TYPE r)


実用上の問題点

levity polymorphicな値は関数の引数に指定できません。

これはcalling conventionsによる制限で、次のように表されます。

Never move or store a levity-polymorphic value.

levity polymorphic functionでは制限がかかるということです。

(levity polymorphicな、もしくはそれに関わらず)型クラスでは辞書でメソッドを持ち回しており、その持ち回すメソッドそれぞれはlevity-polymorphicではないため、この制限に関する問題ありません。

しかしこの制限により、Levity polymorphic type classを定義しても次のような関数twiceは定義できません。

class Add (a :: TYPE r) where

add :: a -> a -> a
instance Add Int where
add x y = x + y
instance Add Int# where
add x y = x +# y

twice :: forall (r :: RuntimeRep) (a :: TYPE r). Add a => a -> a
twice x = add x x

これは次のようなコンパイルエラーを吐きます。

..../app/Main.hs:28:7: error:

A levity-polymorphic type is not allowed here:
Type: a
Kind: TYPE r
In the type of binder ‘x’
|
28 | twice x = add x x
| ^

型クラスを定義してもその制約を使った関数を定義できないというのは実用上面倒なものです。


回避策

サブクラスを定義することでその制限を回避できます。

{-# LANGUAGE MagicHash #-}

{-# LANGUAGE TypeInType #-}
{-# LANGUAGE TypeApplications #-}
{-# LANGUAGE RankNTypes #-}
module Main where

import GHC.Types
import GHC.Prim

main :: IO ()
main = do
putStrLn $ toString (add 42# 3#)
putStrLn $ toString (add @_ @Int 42 3)
putStrLn $ toString (twice 12#)
putStrLn $ toString (twice @_ @Int 12)
putStrLn "Heyhey!"

class Add (a :: TYPE r) where
add :: a -> a -> a
instance Add Int where
add x y = x + y
instance Add Int# where
add x y = x +# y

class Add a => Twice (a :: TYPE r) where
twice :: a -> a
instance Twice Int where
twice x = add x x
instance Twice Int# where
twice x = add x x

class ToString (a :: TYPE r) where
toString :: a -> String
instance ToString Int# where
toString x = "I# " ++ show (I# x)
instance ToString Int where
toString x = show x

これなら実用上そこまで問題にならないでしょう。

levity polymorphicな関数を作るならその辺も考慮して設計することになるだろう、ということです。


雑感

Levity polymorphismはHaskellが実用的に使われるようになるにつれて、速度が(C++等より)遅いという問題に対する取り組みのひとつであるようにも思えますし、今まで特別扱いされていたUnlifted typesに対して統一的に扱えるように型システムを拡張したようにも思えます。個人的にはlevity polymorphismによってUnlifted typesを扱うライブラリの拡充が期待できることが大きいかなあと思っています。


ところで

backpackでunlifted typesを扱えるようになっているらしいので、場合によってはそちらを使う方がいいのかもしれません。


参考資料

https://www.microsoft.com/en-us/research/publication/levity-polymorphism/





  1. Haskell入門 関数型プログラミング言語の基礎と実践 http://gihyo.jp/book/2017/978-4-7741-9237-6