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

この記事はHaskell Advent Calendar 2016の16日目の記事です。

Hash-consing

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

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

より複雑な例としては、何らかの木や式などを表現する帰納的データ構造に対して、部分木や部分式を共有したいという場合があります。二部決定グラフ(BDD: Binary Decision Diagram)などもhash-consingを用いたテクニックとみなすことができます。

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

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

@keigoi そういえば、Haskellのハッシュコンシングのパッケージは何かいいのないですかねぇ。今はinternパッケージ http://t.co/s35eMqHSC4 を使おうかと思ってるけれど……
— Masahiro Sakai (@masahiro_sakai) 2013年7月22日

.@keigoi いや、汎用ではなく機能を限定したものなら、結構いろいろありますよ。 simple-atom, symbol, stringtable-atom, monad-atom, monad-atom-simple などなど。
— Masahiro Sakai (@masahiro_sakai) 2013年7月23日

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

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

internの使い方

ここではintern-0.9.1.4について使い方を簡単に説明することにします。

シンボル的な使い方

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

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

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

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

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

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

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

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

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

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

具体例として、Data.Interned.IntSetというモジュールが提供されており、これはIntSetの実現に使われている木(パトリシア木)に対してHash-consingのアイディアを使って、メモリ消費量を減らした実装で、これを読むと仕組みが分かります。以上。

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

命題論理式の例

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

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

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

実装に関係する主要なインターフェースは Data.Interned で定義される以下のような型と型クラスです:

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の値だけを使って定義します。

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を作る際に一時的に使うだけのデータ型です。

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

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

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を指定しています。

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)を用いたGCに都合が良い？ただし、現在のところそのようなGCは実装されていない模様。
- ライブラリ作者のみがId型を扱い、利用者はId型を扱わずとも良いようにする。
hash-consing版のFormulaでは元のNotなどのデータ構築子が使えず、Not xの代わりに、intern (UNot x)などと書く必要があり、パターマンマッチの際もuninternした上でUNotとマッチする必要があります。この問題はPatternSynonyms拡張を用いて双方向パターンを定義すれば解決できるはずです。特に、GHC 8 以降ではPatternSynonyms拡張が強化され、より普通のデータ構築子に近い使い勝手で使えるようになっているので、それらを活用すると良いと思います。

まとめ

Hash-consing の概要と、HaskellでHash-consingを行うためのライブラリとして、internを紹介しました。また、簡単な例として命題論理式のHash-consingの例を紹介し、いくつかの考察を述べました。

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