Skip to content

Instantly share code, notes, and snippets.

@yuga
Last active September 11, 2016 05:34
Show Gist options
  • Save yuga/8255552 to your computer and use it in GitHub Desktop.
Save yuga/8255552 to your computer and use it in GitHub Desktop.

Haskellでバイナリデータ

1. はじめに

Haskellでバイナリファイルの読み書きをすることがこれまで何回かあったので、それをネタにアドベントカレンダーに参加したつもりだったのですが、定刻よりもだいぶ遅れての年始の到着となりました。申し訳ございません。これはHaskell Advent Calender 2013 11日目だったはずの記事です。明けましておめでとうございます。

さて。コンンピュータで扱うデータはすべてバイナリ形式で表現されています。したがってすべてはバイナリデータであるという言い方ができますが、しかし一般には、テキストでないデータをバイナリデータと呼びます。

Haskellにはバイナリデータを扱うライブラリがたくさんあります。どのライブラリも特別難しい要素があるわけでなく、Haskellのライブラリの中では扱いの容易な部類に含まれるものと思います。しかし、初めて取り組むときには、主要なライブラリのどれも同じようなインターフェイスを提供していることに、何を選べば良いか戸惑う人も多いのではないでしょうか。

そこで今回は、そうしたバイナリデータ用のHaskellライブラリをざっと見て回ることにします。
あとHaskellの実行環境はGHC 7.6.3に限定しますね。

2. バイナリデータプログラミングを解体してみる

どういうライブラリがあるかを見る前に、バイナリデータを扱うプログラミングについて整理しておきます。

Haskellのデータ型を使用しているとき、そのバイナリ表現は隠蔽されプログラマが意識する必要はありませんでした。しかしバイナリデータを入出力する場合には、C言語の場合と同じく、メモリ上のバイト列に対して直接バイナリ表現を読み書きする必要があります。データ出力の際には、 (1) 必要なメモリ領域を確保し、(2) その上に値をバイナリ表現で書き込む。データ入力の際には、(1) バイナリ表現が記述されたメモリ領域を取得し、(2)そこから値を読み込む。以上の手順を実施するわけです。このためには、

  • メモリをバイト列として取得/解放する仕組み
  • バイト列をHaskellプログラム内で持ち回る仕組み
  • バイト列上のバイナリ表現を読み書きする仕組み

これら3つが必要となります。

3. メモリを取得する/解放する

GHCで取得可能なメモリは2種類あります。1つはGHCにリンクされたC言語の標準ライブラリから取得するGHC管理外のメモリ、もう1つはGHCのランタイムで管理されるメモリです。後者はさらに2種類に分かれます。GHCが管理するメモリは不要になればGCにより解放されますが、GHCはコピーGCを採用しているため、GCが走ると、通常は確保したメモリ領域が移動してしまいます。バイナリデータを扱うときには、メモリ上に点在するバイナリ表現をポインタで指定して管理したいことが多々あるため、GCによるメモリ移動で既存のポインタが無効になるのは不都合です。そのため、GHCにはGCによる移動がおこらない特別なメモリを取得する仕組みが用意されています。これをPinned ObjectまたはPinnedメモリといい、コピーGCを行う通常のHeap領域ではなく、Mark & Sweep GCを行う領域からメモリを取得します。

3.1. C言語標準ライブラリを利用したメモリの取得/解放

C言語の標準ライブラリで管理されるメモリを取得するにはForeign.Marshalモジュールの malloc系関数を使用します。

Foreign.Marshal.malloc      :: Storable a =>        IO (Ptr a)
Foreign.Marshal.mallocBytes ::               Int -> IO (Ptr a)

1つめのmalloc関数は、後ほど出てくるForeign.StorableモジュールのStorable型クラスのインスタンスを実装したデータ型に必要なサイズのメモリを取得します。2つめの関数は最初の引数で指定したバイトサイズのメモリ領域を取得します。これらの関数が返すPtr型の定義は下の通りで、中にあるAddr#が実際にデータを格納するメモリ領域へのポインタです。

data Ptr a = Ptr Addr# deriving (Eq, Ord)

Addr#のように型の末尾に#がついている型や関数はプリミティブといってHaskell自体で定義されているのではなくGHC組み込みのものになります。取得したメモリとポインタ(Addr#)の関係を図示すると以下のようになります。

-------------
| data      |
-------------
↑
Addr#

Addr#は取得したメモリの先頭をさしています。実際には、C言語の標準ライブラリはデータ領域の他に管理のための領域をあわせて使用していますが、GHCが意識する部分ではないので省略しています。malloc系関数はGCでは解放されないので、明示的に解放する必要があります。それには、Foreign.Marshalモジュールのfree関数を使用します。

Foreign.Marshal.free :: Ptr a -> IO ()

mallocmallocBytesfreeはいずれもHaskell 2010 Language Reportに含まれている関数です。

3.2. GHCランタイムを利用したメモリの確保/解放

GHCが管理するメモリをバイト列として取得するには、GHC.ForeignPtrモジュールで定義されているmalloc系関数を使用します。

mallocForeignPtr                  :: Storable a =>               IO (ForeignPtr a)
mallocForeignPtrBytes             ::               Int ->        IO (ForeignPtr a)
mallocForeignPtrAlignedBytes      ::               Int -> Int -> IO (ForeignPtr a)

これらの関数は、GCによる移動がおこらないPinnedメモリをバイト列として取得します。GHCはランタイムで取得したメモリをImmutableなByteArray#とMutableなMutableByteArray#にわけて管理しています。これはGHCが世代GCを採用しているためです。Immutableなメモリに含まれる参照は、そのメモリと同じかより古い世代のメモリに含まれるオブジェクトに対するものだけですが、Mutableなメモリにはより新しい世代への参照が含まれる可能性があります。そのためMutableなメモリは別途リスト管理されていて、若い世代をGCするときに参照を持っているか走査する対象となります。ForeignPtrとして取得できるメモリはすべてMutableByteArray#です。

上記の3つの関数の違いは取得するメモリサイズとアライメントの決定方法です。mallocForeignPtrStorableクラスのsizeOf関数が返す値をサイズとしてalignment関数が返す値を境界としたポインタを取得します。mallocForeignPtrBytesは引数に指定したサイズのメモリを16バイト境界で、mallocForeignPtrAlignedBytesは1番目の引数に指定したサイズで2番目の引数の値を境界としたポインタを取得します。

これらの関数はmallocForeignPtrAlignedBytes関数を除いて、いろいろモジュールを経由してForeignモジュールで公開されています。

取得したメモリへのポインタはwithForeignPtr関数で取り出して利用できます。

withForeignPtr :: ForeignPtr a -> (Ptr a -> IO b) -> IO b

取り出したポインタはこの関数の中でのみ有効となっていて、外に持ち出して使用することは危険です。細かな利用方法は他の方のブログを参考にするのが良いと思います1。取得したメモリとポインタの関係を図示すると以下のようになります。

MutableByteArray#
↓
----------------------
| Header | data      |
----------------------
         ↑
         Addr#

先頭にHeaderがありその後にデータ領域が続きます。こうして取得したメモリはMutableArray#への参照がなくなったときGCで解放される対象となります。このためAddr#を保持するPtrをコード中で参照しているだけではGCで解放されてしまうので、必ずMutableByteArray#の参照を維持しなければなりません。GHCでのForeignPtrの定義は以下のようにその両者の参照を持ちます。

data ForeignPtr a = ForeignPtr Addr# ForeignPtrContents
data Finalizers
  = NoFinalizers
  | CFinalizers
  | HaskellFinalizers
    deriving Eq

data ForeignPtrContents
  = PlainForeignPtr !(IORef (Finalizers, [IO ()]))
  | MallocPtr      (MutableByteArray# RealWorld) !(IORef (Finalizers, [IO ()]))
  | PlainPtr       (MutableByteArray# RealWorld)

ForeignPtrの1つめのフィールドにはAddr#が入り、2つめのフィールドにはForeignPtrContents型が入り、この型には3つあるデータ構築子のうち2つがMutableByteArray#を持ちます。各データ構築子の使い分けは、newForeignPtrのように取得済みのメモリ領域をもとにForeignPtrを構築するにはPlainForeignPtrを使用します。mallocForeignPtrは、Haskell 2010 Language Reportで do { p <- malloc; newForeignPtr finalizerFree p }のように定義されているためか、MallocPtrを使用していますが、GHCではFinalizersは空リストになっています。また、GHC独自に以下の関数が定義されています。

GHC.ForeignPtr

mallocPlainForeignPtr             :: Storable a =>               IO (ForeignPtr a)
mallocPlainForeignPtrBytes        ::               Int ->        IO (ForeignPtr a)
mallocPlainForeignPtrAlignedBytes ::               Int -> Int -> IO (ForeignPtr a)

こちらはPlainPtrを使用していて、Finalizerのリストを生成しないため標準関数より効率が良くなっています。

その他に、Foreign.Marshalモジュールには、メモリを一時的に必要とする場合に便利な関数があります。

alloca             :: Storable a =>               (Ptr a -> IO b) -> IO b
allocaBytes        ::               Int ->        (Ptr a -> IO b) -> IO b
allocaBytesAligned ::               Int -> Int -> (Ptr a -> IO b) -> IO b

alloca fのように使用し、fが終了するとメモリは解放されます。GHCではGHCが管理するPinnedメモリから取得する実装になっています。

4. バイト列をHaskell内で持ち回る

次に取得したメモリをバイト列としてHaskell内で持ち回るには、何らかのデータコンテナが必要です。

これまでに紹介した関数を使用してメモリを確保した場合はForeignPtrを使用するのが便利です。C言語の標準ライブラリから取得したメモリでも、Finalizerとしてfree関数を登録しておくことで、不要になったタイミングでGCによりメモリ解放を行うことが可能です。これは標準ライブラリ以外から取得したメモリでも適切な解放関数が用意されていれば利用できます。

しかし、ファイルを使った入出力などの場合、そのインターフェイスとしてData.ByteString.ByteStringあるいはData.ByteString.Lazy.ByteStringが用いられることが多々あります。幸いByteStringも内部でForeignPtrを使用してバイト列の管理をおこなっているため、次の関数で手持ちのForeignPtrをそのままByteStringへ移すことと、反対にByteStringからForeignPtrを取り出すことが可能です。

Data.ByteString.Internal.fromForeignPtr :: ForeignPtr Word8 -> Int -> Int -> ByteString
Data.ByteString.Internal.toForeignPtr   :: ByteString -> (ForeignPtr Word8, Int, Int)

ForeignPtrの型をあわせるにはForeign.ForeignPtr.castForeignPtrを使用します。Internalモジュールのためインターフェイスの継続性に不安がある場合は、Data.ByteString.UnsafeモジュールのunsafePack系の関数から、メモリを取得した方法にあわせた適切な関数を選択してByteStringを構築する必要があります。

その他にData.Array.Strorable.StorableもForeignPtrを持ち込むことができます。こちらは次の関数を使います。

Data.Array.Unsafe.AU.unsafeForeignPtrToStorableArray :: Ix i 
                                                     => ForeignPtr e 
                                                     -> (i,i) 
                                                     -> IO (StorableArray i e)

ByteStringやStorable Arrayといったデータコンテナを使用することのメリットは、ForeignPtrだけでは管理されないポインタの有効範囲をひとまとめにできることです。他にもバイト単位の様々な操作関数が手に入りますが、バイナリデータを扱う場合はポインタを使用した操作を行うことが多いため、あまり役に立たないと感じるかもしれません。しかし後ほど見ていくライブラリの多くでデータコンテナとしてByteStringを使用しているなど、バイナリデータを扱う場合にも有用なことがわかります。

5. バイト列上のバイナリ表現を読み書きする

5.1 ライブラリ一覧

最初に述べたように、バイト列上のバイナリ表現の読み書き機能を提供するライブラリは多数あります。そのなかから利用例の多いパッケージとその主要なモジュールについて一覧してみます。

正確にはHaskellにライブラリという用語を持つ構成要素は存在しませんが、巨大なパッケージのなかで共通の目的に使用する複数のモジュールをひとまとめに表現したり、組み合わせて使用する複数のパッケージをひとまとめに表現する用語として、ここではライブラリという言葉を用いることにします。

  • Foreign ライブラリ
    • base パッケージ
      • Data.Bits
      • Foreign.Marhsal
      • Foreign.C
      • Foreign.ForeignPtr
      • Foreign.Ptr
      • Foreign.Storable
      • Foreign.Unsafe
  • Binary ライブラリ
    • binary パッケージ
      • Data.Binary
      • Data.Binary.Get
      • Data.Binary.Put
    • binary-bits パッケージ
      • Data.Binary.Bits.Get
      • Data.Binary.Bits.Put
  • Binary-Strict ライブラリ
    • binary-strict パッケージ
      • Data.Binary.Strict.BitGet
      • Data.Binary.Strict.Get
      • Data.Binary.Strict.IncrementalGet
      • Data.Binary.Strict.Put
  • Cereal ライブラリ
    • cereal パッケージ
      • Data.Serialize
      • Data.Serialize.Get
      • Data.Serialize.IEEE754
      • Data.Serialize.Put
    • safecopyパッケージ
      • Data.SafeCopy

5.2. 機能の比較

大雑把にいって、Foreignライブラリは、ポインタとオフセットとサイズを指定してプログラムを記述するポインタスタイルのプログラミング、その他のライブラリは関数を手続き的に利用していくモナディックスタイルのプログラミングとなるよう設計されています。

各ライブラリのもっている機能を比較してみましょう。

Foreign ライブラリ

  • 対象とするデータ型: Foreign.StorableモジュールのStorable型クラスを実装したデータ型
    • Bool, Char, Double, Float, Int, Wordなどの基本的なデータ型
    • Foreign.CモジュールにあるC言語互換のデータ型
  • データコンテナ: Ptr型に直接アクセス可能なものならなんでも
  • 読み込み: ○
  • 書き込み: ○
  • 先読み: -
  • 増分(部分)入力: -
  • Bit単位の処理: -
  • バージョン管理: -
  • Functor: ○ (IO)
  • Applicative: ○ (IO)
  • Alternative: -
  • Monad: ○ (IO)
  • MonadPlus: ○ (IO)

バイナリデータを扱うための一番基本的なライブラリです。問題点としては、FFIで使用することが前提のため、ファイル入出力を扱うときに必要になる異なるエンディアンへのサポートがないことです。

Binary ライブラリ

  • 対象とするデータ型: Data.BinaryモジュールのBinary型クラスを実装したデータ型
    • Bool, Char, Double, Float, Int, Wordなどの基本的なデータ型
    • Array, UArray, ByteStringなどの配列
    • タプル, List, IntMap, Map, Seq, Treeなどのコンテナ
    • Either, Maybeなど
  • データコンテナ: ByteString (Lazy)
  • 読み込み: ○
  • 書き込み: ○
  • 先読み: ○ (0.6以降)
  • 増分(部分)入力: ○ (0.6以降)
  • Bit単位の処理: ○ (binary-bitsを使用)
  • バージョン管理: -
  • Functor: 読み込み ○ (Get), 書き込み ○ (PutM)
  • Applicative: 読み込み ○ (Get), 書き込み ○ (PutM)
  • Alternative: 読み込み ○ (Get) (0.6以降)
  • Monad: 読み込み ○ (Get), 書き込み ○ (PutM)
  • MonadPlus: -

最新版は0.7系ですが、その2世代前の0.5系がGHCにも取り込まれている、もうひとつの基本ライブラリです。大小両方のエンディアンに対応し、ファイル入出力にも便利に利用できますが、なぜかIEEE754のサポートがありません。HaskellのFloat型、Double型を出力すると仮数部と指数部をそれぞれIntで表したバイナリ表現になります。Cerealよりもパフォーマンスが良くなるように実装されています。

Binary-Strict ライブラリ

  • 対象とするデータ型: 型クラスはないため読み書きのための関数が定義されているデータ型のみ対象となる
    • Wordなどの基本的なデータ型
    • ByteStringなどの配列
  • データコンテナ: ByteString (Strict)
  • 読み込み: ○
  • 書き込み: -
  • 先読み: ○
  • 増分(部分)入力: ○
  • Bit単位の処理: ○
  • バージョン管理: -
  • Functor: 読み込み ○ (Get)
  • Applicative: 読み込み ○ (Get)
  • Alternative: 読み込み ○ (Get)
  • Monad: 読み込み ○ (Get)
  • MonadPlus: 読み込み ○ (Get)
  • BinaryParser: 読み込み ○ (Get)

BinaryライブラリがLazy版のByteStringをデータコンテナとしていたため、入力部分をそっくりStrict版のByteStringに置き換えたものです。その後、両者のライブラリが違った発展をしたので、少々機能的な差異があります。

Cereal ライブラリ

  • 対象とするデータ型: Data.SerializeモジュールのSerialize型クラスを実装したデータ型
    • Bool, Char, Double, Float, Int, Wordなどの基本的なデータ型
    • Array, UArray, ByteStringなどの配列
    • タプル, List, IntMap, Map, Seq, Treeなどのコンテナ
    • Either, Maybe, Monoidインスタンスなど
  • データコンテナ: ByteString (Strict)
  • 読み込み: ○
  • 書き込み: ○
  • 先読み: ○
  • 増分(部分)入力: ○
  • Bit単位の処理: -
  • バージョン管理: Safecopyを使用する (cerealパッケージと作者は別)
  • Functor: 読み込み ○ (Get), 書き込み ○ (PutM)
  • Applicative: 読み込み ○ (Get), 書き込み ○ (PutM)
  • Alternative: 読み込み ○ (Get)
  • Monad: 読み込み ○ (Get), 書き込み ○ (PutM)
  • MonadPlus: -

5.3. 歴史

最後に、各ライブラリのこれまでの歩みを見てみます。

Binary、Binary-Strict、Cerealの3つのライブラリは、互いに良く似た機能とインターフェイスを持っています。これは各ライブラリの登場時期と作者に関係あります。

Hackageでパッケージのメタデータを見ると、まず最初にLennart Kolmodinが2007年頃にBinaryパッケージを開発しています。このライブラリはデータコンテナとしてLazy版のByteStringのみに対応していました。そのためAdam Langleyという人がBinaryライブラリの多くをコピペしてStrict版のByteStringをデータコンテナとしたBinary-Strictを作ります。

その後、Binaryの開発者であるLennart Kolmodinも2009年にStrict版のByteStringをデータコンテナとしたCerealライブラリを開発します。CerealはBinaryと良く似たライブラリでしたが、GetモナドがAlternativeのインスタンスになりバックトラックが可能になるなどの機能追加が行われています。Binaryよりパフォーマンス的に劣るものの機能が多いという位置づけがされたのです。

このため2011年に入ってすぐ、BinaryとCerealの機能をそろえて両者を統一してはどうかという議論がありました。Cerealの方が機能が豊富だったためそちらへ統合を望む声もあるなか、BinaryライブラリがGHC内で利用されるようになり(後にHaskell Platformを通じて公開されることになります)機能追加が停滞する一方で、Cerealにはその後も2012年にかけて部分入力(Partial Input/Incremental Read)機能が追加されていきます。

両者のライブラリの統一はなされないまま、2012年秋以降、Lennart Kolmodinは今度はBinaryの機能強化にのりだします。実際には2010年頃から着手していてHackageへの公開がなされていなかっただけのようですが、GHCに取り込まれた0.5系のバージョンから、さらに0.6, 0.7と開発をすすめ、Cerealとの機能差異を埋めてしまいました。この結果として3つのライブラリは大変似通った機能を持つことになりました。

もうひとつ見ておくべきものとしてSafecopyがあります。これはバイナリデータをバージョン管理して、複数のデータフォーマットの読み書きやマイグレーションをサポートするパッケージで、バイナリ表現の読み書き部分については実装せず既存のライブラリをラップする設計になっています。当初はBinaryに対するアドオンでしたが、2011年4月の0.5以降はCerealに対する実装になっています。ちょうどBinaryの開発が停滞した時期に、Cerealへの乗り換えが行われたように見受けられます。

6. サンプルプログラム

この記事に上げたライブラリを使って、それぞれどのような実装の違いがあるか確かめるためのサンプルプログラムを用意しました。あまり適切な例ではありませんが、ちょっとした様子を見る程度ならば使えると思います。参考程度にどうぞ。

https://github.com/yuga/haskell-sample-binary-abook/

参考文献

1 Haskell ポインタープログラミング / あどけない話

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment