Levity polymorphismについて軽く

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

Haskellでの多相性には主にparametric polymorphismとad-hoc polymorphismがありますが、そちらに関してはHaskell入門[^haskell-book]をお読みください。
ここではghc-8.0あたりから導入された新しい多相性、levity polymorphismについて軽く説明します。
advancedな話題なのでHaskell入門を読んでいる途中の方は分からなくても気にしないでください。

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

# 概要

関数呼び出しの際にヒープを指しているポインタ、例えばリストのようなものと、倍精度浮動小数点数を渡す時には使われるレジスタは異なったりします。それらをパラメトリック多相で一緒に扱うコードを生成することはできません。この問題の簡単な解決方法は全てをヒープにアロケートされた値として扱うことです。そうすることによって全ての値を同じように扱うことができるようになりますが、同時に大きなパフォーマンス上のペナルティが加わります。
Levity polymorphismはこのcalling conventionを超えた抽象化を可能にします。またパフォーマンスペナルティもありません。
しかし制約も追加されます。levity polymorphicな値は関数の引数に渡せない、というものです。
このエントリでは簡単な例と、実用上の注意点を軽く説明します。

# 簡単な例

`toString :: a -> String`というメソッドを持つ`ToString`を定義することを考えます。Preludeには`Show`クラスが存在しますが、今回はlevity polymorphicな関数を考えます。つまり`Int#`のような値を引数に渡せるようにします。
`LevityPolymorphism`には専用の拡張はなく、`TypeInType`が必要です。`TypeInType`とは種を型と同じ構造にしてしまい、同じように扱えるようにする拡張です。


```haskell
{-# 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` あたりを確認しておきます。それらは`data`や`type`で型として定義されていますが、kindとして扱うことを期待されているものです。

```haskell
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`によるものです。

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

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

```haskell
class C (a :: *)
```

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

```haskell
class C (a :: TYPE LiftedRep)
```

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

```haskell
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`は定義できません。

```haskell
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
   |       ^
```

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

# 回避策

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

```haskell
{-# 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://ghc.haskell.org/trac/ghc/ticket/13955




# 参考資料

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