Hash-consingのためのinternパッケージ

この記事は[Haskell Advent Calendar 2016](http://qiita.com/advent-calendar/2016/haskell)の16日目の記事です。

## Hash-consing

[Hash-consing](https://en.wikipedia.org/wiki/Hash_consing) は、同値な値を表現するのに同一の構造を常に再利用することで、メモリの節約や、同値性の比較の高速化(ポインタの比較で済むようになるので)を行うための手法です。 また、共有を意識して処理を行えば、時間計算量も削減することができます。

一番簡単な例としては、Lisp系の言語やRubyでのシンボルがあり、識別子などを表すデータ型として文字列の代わりにこれらを使うことでhash-consingの利点を得ることができます。 また、JavaにもStringクラスに`intern`メソッドがあって、同様の目的に使われます。

より複雑な例としては、何らかの木や式などを表現する帰納的データ構造に対して、部分木や部分式を共有したいという場合があります。 [二部決定グラフ(BDD: Binary Decision Diagram)](https://ja.wikipedia.org/wiki/%E4%BA%8C%E5%88%86%E6%B1%BA%E5%AE%9A%E5%9B%B3)などもhash-consingを用いたテクニックとみなすことができます。

## Haskellで使えるhash-consingのライブラリ

もう3年前のツイートですが、hash-consingのためのHaskellライブラリとして以下のようなものがありました。

<blockquote class="twitter-tweet" data-lang="ja"><p lang="ja" dir="ltr"><a href="https://twitter.com/keigoi">@keigoi</a> そういえば、Haskellのハッシュコンシングのパッケージは何かいいのないですかねぇ。今はinternパッケージ <a href="http://t.co/s35eMqHSC4">http://t.co/s35eMqHSC4</a> を使おうかと思ってるけれど……</p>&mdash; Masahiro Sakai (@masahiro_sakai) <a href="https://twitter.com/masahiro_sakai/status/359296249112952832">2013年7月22日</a></blockquote>

<blockquote class="twitter-tweet" data-lang="ja"><p lang="ja" dir="ltr">.<a href="https://twitter.com/keigoi">@keigoi</a> いや、汎用ではなく機能を限定したものなら、結構いろいろありますよ。 simple-atom, symbol, stringtable-atom, monad-atom, monad-atom-simple などなど。</p>&mdash; Masahiro Sakai (@masahiro_sakai) <a href="https://twitter.com/masahiro_sakai/status/359685392527667201">2013年7月23日</a></blockquote>

* [intern](http://hackage.haskell.org/package/intern)
* [simple-atom](http://hackage.haskell.org/package/simple-atom)
* [symbol](http://hackage.haskell.org/package/symbol)
* [stringtable-atom](http://hackage.haskell.org/package/stringtable-atom)
* [monad-atom](http://hackage.haskell.org/package/monad-atom)
* [monad-atom-simple](http://hackage.haskell.org/package/monad-atom-simple)

このなかで、[intern](http://hackage.haskell.org/package/intern)は前述のシンボルと帰納的データ構造の両方の用途に使える汎用性がありますが、それ以外のものはシンボルとしての用途のみを考慮したライブラリになっています。

それもあって、自分はinternを利用しています。 その一方で、internも[githubのレポジトリ](https://github.com/ekmett/intern/)を見ると、全然メンテナンスされない状態となっているので、もし他に何かよいライブラリがあれば教えてください！

## internの使い方

ここでは[intern-0.9.1.4](http://hackage.haskell.org/package/intern-0.9.1.4)について使い方を簡単に説明することにします。

### シンボル的な使い方

シンボル的な使い方については簡単です。 識別子などの短い文字列は通常、`String`、(strict) `Text`, (strict) `ByteString`などで表現されているはずで、それらに対応するモジュールがあるので、

* [Data.Interned.String](http://hackage.haskell.org/package/intern-0.9.1.4/docs/Data-Interned-String.html)
* [Data.Interned.Text](http://hackage.haskell.org/package/intern-0.9.1.4/docs/Data-Interned.Text.html)
* [Data.Interned.ByteString](http://hackage.haskell.org/package/intern-0.9.1.4/docs/Data-Interned-ByteString.html)

それをインポートして、それぞれ `InternedString`, `InternedText`, `InternedByteString` を使います。 対応する通常のデータ型からの変換には `intern` 関数を、対応する通常へのデータ型への変換には `unintern` を使います。 簡単ですね。

そのうえで、文字列を使っていた箇所をこれらのデータ型を使うように置き換えれば良いです。 なお、これらのデータ型は`IsString`クラスを実装しているため、`OverloadedStrings`拡張を有効にすれば、文字列リテラルはそのまま用いることができます。

特に、同じ識別子の共有されない複数の実体を作ってしまいがちなのはパーサで、例えば以下のような識別子のパーサは識別子の出現毎に別々の実体を作ってしまうことになります。

```hs
ident :: Parser String
ident = (:) <$> letter <*> many alphaNum
```

これを以下のようにすれば、同じ識別子の実体は共有されるようになり、同じ識別子の出現が大量にある場合には消費メモリを削減することができます。なお、`IsString`のインスタンスであるため、ここの`intern`は`fromString`としても良いです。

```hs
ident :: Parser InternedString
ident = liftA intern $ (:) <$> letter <*> many alphaNum
```

注意点として、これらの型の`Ord`のインスタンスは、`intern`前の順序ではなく、内部的に管理用に割り当てられた整数の順序となっているため、順序を比較する際には注意が必要です。 それもあり、コンテナとしては`Map`や`Set`などではなく`HashMap`や`HashSet`などを使うことを想定している気がします。

### 帰納的データ構造の使い方

単純なシンボル的用途ではあまり仕組みを考える必要はありませんでしたが、帰納的データ構造で部分木の共有をしたいといった場合には、仕組みを理解したうえでちょっとした実装が必要になります。

具体例として、[Data.Interned.IntSet](http://hackage.haskell.org/package/intern-0.9.1.4/docs/Data-Interned-IntSet.html)というモジュールが提供されており、これは`IntSet`の実現に使われている木([パトリシア木](https://ja.wikipedia.org/wiki/%E5%9F%BA%E6%95%B0%E6%9C%A8))に対してHash-consingのアイディアを使って、メモリ消費量を減らした実装で、これを読むと仕組みが分かります。以上。

……で、終わらせるのは流石に何なので、私が使おうとしたときの例を少し単純化して紹介します。

#### 命題論理式の例

以下のような命題論理式のデータ型を考え、これをHash-consingしたバージョンに置き換えることを考えます。

```hs
data Formula
  = Atom Int
  | And [Formula]
  | Or [Formula]
  | Not Formula
  | Imply Formula Formula
```

#### 実装に関係するインターフェース

実装に関係する主要なインターフェースは [Data.Interned](http://hackage.haskell.org/package/intern-0.9.1.4/docs/Data-Interned.html) で定義される以下のような型と型クラスです:

```hs
type Id = Int

class ( Eq (Description t)
      , Hashable (Description t)
      ) => Interned t where
  data Description t
  type Uninterned t
  describe :: Uninterned t -> Description t
  identify :: Id -> Uninterned t -> t
  cache :: Cache t

class Interned t => Uninternable t where
  unintern :: t -> Uninterned t
```

ここで、`Id`型は内部で振られる整数で、Haskellではポインタの同値性は存在しない(正確には`reallyUnsafePointerEquality`という関数は存在するけれど、こういう目的には使うものではない)ので、ポインタの比較の代わりに`Id`型の比較を使います。

`Interned`クラスは`intern`結果のデータ型の属するクラスです。`Uninterned`は`intern`後のデータ型から`intern`前のデータ型を得るための型族(関連型)です。 `unintern`については`Uninternable`という別の型クラスに分離されているので、`unintern`が不要な場合にはこちらは実装しないということもできます。

例えば、`InterenedString`は、`Interned`と`Uninternable`のインスタンスであり、`Uninternd InterenedString` は `String` となっています。

次に、`Description`はちょっと直観的でないのですが、内部で持つハッシュテーブルのキーとなるデータ型で、 `describe :: Uninterned t -> Description t` によってキーが計算されます。直観的には`Uninterned t`をそのままキーにすれば良い気がして、実際前述の `InternedString`, `InternedText`, `InternedByteString` の場合には、`Uninterned t`の単なる`newtype`になっているのですが、帰納的なデータ型の場合には違う扱いをしたい場合があって、このようになっているんだと思います（この点については後で少し述べます）。

次に、`Uninterned t`とそれに対して内部で割り当てられた管理用の`Id`を引数にとって、`intern`結果の型の値を作る関数が`identify`です。

最後の `cache :: Cache t` は実質的に `Description t` から `t` へのハッシュテーブルで、`unsafePerformIO`によって割り当てと更新がされます。

#### Hash-consing後の命題論理式の例

これを踏まえて、Hash-consingした結果を見ていきます。 まずは`Formula`を`Id`と`intern`前の構造である`UFormula`の組で表現します。 `Id`が等しければ同値になるので、`Eq`と`Hashable`は`Id`の値だけを使って定義します。

```hs
data Formula = Formula {-# UNPACK #-} !Id UFormula

instance Eq Formula where
  Formula i _ == Formula j _ = i == j

instance Hashable Formula where
  hashWithSalt s (Formula i _) = hashWithSalt s i
```

次に`intern`前の`UFormula`の型を定義します。ここでは部分式が`Formula`となっている命題論理式の型にしています。 このデータ型は`InternedString`に対する`String`のような広く使用するデータ型ではなく、`Formula`を作る際に一時的に使うだけのデータ型です。

```hs
data UFormula
  = UAtom Int
  | UAnd [Formula]
  | UOr [Formula]
  | UNot Formula
  | UImply Formula Formula
```

次が核心となる`Interned Formula`のインスタンス定義です。

```hs
instance Interned Formula where
  type Uninterned Formula = UFormula
  data Description Formula
    = DAtom Int
    | DAnd [Id]
    | DOr [Id]
    | DNot Id
    | DImply Id Id
    deriving (Eq, Generic)
  describe (UAtom a) = DAtom a
  describe (UAnd xs) = DAnd [i | Formula i _ <- xs]
  describe (UOr xs) = DOr [i | Formula i _ <- xs]
  describe (UNot (Formula i _)) = DNot i
  describe (UImply (Formula i _) (Formula j _)) = DImply i j
  identify = Formula
  cache = formulaCache

formulaCache :: Cache Formula
formulaCache = mkCache
{-# NOINLINE formulaCache #-}
```

`Description Formula`は、`UFormula`の部分式部分を`Id`に置き換えたデータ型として定義していて、`describe`ではまさに部分式の`Formula`の`Id`部分だけを取り出す変換を行っています。

`identify`は`Id`と`UFormula`を受け取って`Formula`を構築する関数になっています。`cache`の実体は単に`mkCache`なのですが、これは中で`unsafePeformIO`を行ってキャッシュのテーブルを生成するので、複数回実行されたりしたら困るため、`NOINLINE`を指定しています。

```hs
instance Hashable (Description Formula)

instance Uninternable Formula where
  unintern (Formula _ uformula) = uformula
```

最後に、`Description t`は`Hashable`である必要があるのでインスタンスを定義しているのと、また、`Uninternable`も実装してあります。

#### 考察？

* `Uninterned t` と `Description t` でほぼ同じデータ型を定義することになるのは、元のデータ型を関手の不動点として定義して、その関手を考えれば共通化できるはず。
* `Uninterned t` と `Description t` が別のデータ型になっているのには幾つか理由がありそう。
  * `Description t` から `t` への参照を持たせない方が、[弱参照(week pointers)](http://downloads.haskell.org/~ghc/8.0.1/docs/html/libraries/ghc-prim-0.5.0.0/GHC-Prim.html#g:19)を用いたGCに都合が良い？ ただし、現在のところそのようなGCは実装されていない模様。
  * ライブラリ作者のみが`Id`型を扱い、利用者は`Id`型を扱わずとも良いようにする。
* hash-consing版の`Formula`では元の`Not`などのデータ構築子が使えず、`Not x`の代わりに、`intern (UNot x)`などと書く必要があり、パターマンマッチの際も`unintern`した上で`UNot`とマッチする必要があります。 この問題は[PatternSynonyms](https://ghc.haskell.org/trac/ghc/wiki/PatternSynonyms)拡張を用いて双方向パターンを定義すれば解決できるはずです。 特に、GHC 8 以降ではPatternSynonyms拡張が強化され、より普通のデータ構築子に近い使い勝手で使えるようになっているので、それらを活用すると良いと思います。

## まとめ

[Hash-consing](https://en.wikipedia.org/wiki/Hash_consing) の概要と、HaskellでHash-consingを行うためのライブラリとして、[intern](http://hackage.haskell.org/package/intern)を紹介しました。 また、簡単な例として命題論理式のHash-consingの例を紹介し、いくつかの考察を述べました。

ただし、internはメンテナンスされていないので、もっとイケてるライブラリや手法があれば教えてください！