特級シリアライズライブラリ、winery 1.0解禁

fumieval.hatenablog.com

あれから9ヶ月…wineryのバージョン1.0をついにリリースした。

前回までのあらすじ

データの保存や通信に直列化は不可欠の概念である。 binaryなどの直列化ライブラリは、レコードのフィールド名などの情報が欠けており、構造が変わると互換性を持たせることができない。 一方、JSONやCBORなどのフォーマットで愚直にフィールド名などを残すと極めて冗長になり、時間・空間効率が悪い。 コード生成が前提のProtobufなどはHaskellの既存のデータ構造との相性がよくない。 そんな現状に殴り込みをかけたのがwineryだ。値を「スキーマ」と「データ」に分割して保存することによって、冗長性を避けつつ、メタデータを保持させることができる。wineryは最強のライブラリとなりうるか…？

特徴と特長

JSON, MessagePack, CBORなど、多くのフォーマットでは値にフィールド名などの情報を付属させる。

[{"id": 0, "name": "Alice"}, {"id": 1, "name": "Bob"}]

wineryが違うのは、それらメタデータをデータ本体から分離し、一箇所にまとめて保存することにある。これにより、冗長性はなくなり、しかも要素がwell-typedであることを保証する。

0402 0402 0269 6410 046e 616d 6514  [{ id :: Integer, name :: Text }]
0200 0541 6c69 6365 0103 426f 62    [(0, "Alice"), (1, "Bob")]

メタデータのおかげでデシリアライザに互換性を持たせることも可能となる。もちろん、目的に応じてメタデータを省き、binaryやcerealと同じように使うこともできる。 整数のエンコードにはVLQを採用しているため、binaryやcerealよりも短くなりやすい。

使い方

まずSerialiseのインスタンスを定義する。DerivingViaを使って簡単にインスタンスを導出できる。この導出機構は再帰的なデータ型にも対応している。

{-# LANGUAGE DerivingVia, DeriveGeneric, OverloadedStrings, ApplicativeDo #-}
import Control.Applicative
import Data.Winery
import Data.Text (Text)
import qualified Data.Text as T
import GHC.Generics (Generic)

data User = User
  { first_name :: !Text
  , last_name :: !Text
  , email :: !Text
  } deriving (Show, Generic)
  deriving Serialise via WineryRecord User

WineryRecordはどのようなインスタンスにするか選ぶためのラッパーだ。目的に応じてWineryProduct (フィールド名なし), WineryVariant(コンストラクタ名あり)と使い分けよう。

あとはserialise :: Serialise a => a -> ByteStringとdeserialise :: Serialise a => ByteString -> Either WineryException aで自由にシリアライズ・デシリアライズができる。

> serialise (User "Fumiaki" "Kinoshita" "fumiexcel@gmail.com")
"\EOT\EOT\ETX\nfirst_name\NAK\tlast_name\NAK\ENQemail\NAK\aFumiaki\tKinoshita\DC3fumiexcel@gmail.com"

> deserialise @User "\EOT\EOT\ETX\nfirst_name\NAK\tlast_name\NAK\ENQemail\NAK\aFumiaki\tKinoshita\DC3fumiexcel@gmail.com"
Right (User {first_name = "Fumiaki", last_name = "Kinoshita", email = "fumiexcel@gmail.com"})

互換性

レコードにフィールドを追加したときや、バリアントからコンストラクタを削除したときなどに古いデータとの互換性が失われる。そんな場合のための処理をコンポーザブルに記述できる仕組みがwineryには備わっている。

UserにRoleというフィールドを追加したい場合を考えよう。

data Role = Admin | Moderator | Member
  deriving (Show, Generic)
  deriving Serialise via WineryVariant Role

data User = User
  { first_name :: !Text
  , last_name :: !Text
  , email :: !Text
  , role :: !Role
  } deriving (Show, Generic)

データにroleが欠けている場合の振る舞いも、ApplicativeDo記法を用いてカスタマイズができる。なんとメールアドレスがexample.comで終わっていれば自動で昇格するといった芸当も可能だ。

instance Serialise User where
  bundleSerialise = bundleRecord $ const $ buildExtractor $ do
    f <- extractField "first_name"
    l <- extractField "last_name"
    e <- extractField "email"
    r <- const <$> extractField "role"
      <|> pure (\x -> if T.isSuffixOf "example.com" x then Moderator else Member)
    return $ User f l e (r e)

RoleからModeratorを削除した場合も簡単に対応できる。

instance Serialise Role where
  bundleSerialise = bundleVia WineryVariant
  extractor = buildVariantExtractor $ HM.fromList
    [ ("Admin", pure Rice)
    , ("Moderator", pure Member)
    , ("Member",  pure Member)
    ]

パフォーマンス

どんなに便利でも遅くては仕方がない。広く使われているbinary, cereal, aeson, serialiseと比較するためのテイスティング・セッションを行った。

課題となるのは以下のデータ型だ。それぞれの方法でインスタンスを導出し、1000要素のリストのシリアライズ・デシリアライズをする。

data Gender = Male | Female deriving (Show, Generic)

data TestRec = TestRec
  { id_ :: !Int
  , first_name :: !Text
  , last_name :: !Text
  , email :: !Text
  , gender :: !Gender
  , num :: !Int
  , latitude :: !Double
  , longitude :: !Double
  } deriving (Show, Generic)

{-
1,Shane,Plett,splett0@free.fr,Male,-222,53.3928271,18.3836801
2,Mata,Snead,msnead1@biblegateway.com,Male,-816,51.5141668,-0.1331854
3,Levon,Sammes,lsammes2@woothemes.com,Male,485,51.6561,35.9314
...
-}

結果は以下の通りだ。wineryがダントツで速いだけでなく、生成されるバイト列も最も短い。

	encode 1	encode 1000	decode	length
winery	0.28 μs	0.26 ms	0.81 ms	58662
cereal	0.82 μs	0.78 ms	0.90 ms	91709
binary	1.7 μs	1.7 ms	2.0 ms	125709
serialise	0.61 μs	0.50 ms	1.4 ms	65437
aeson	9.9 μs	9.7 ms	17 ms	160558

総評

互換性と拡張性、あらゆるデータ型に対応できる柔軟な導出メカニズム、そして卓越したパフォーマンスと簡潔な表現を提供するwinery 1.0は、ここ数年で最高の出来栄えと言えるだろう。Hackageへ急げ！

報告はGitHubもしくはHaskell-jp Slackまで。

旅のチェックリスト

筆者が旅に出る際に確認する項目をまとめた。

事前の準備

• 渡航ビザ: 必要な場合もあるので事前に確かめよう。
• ESTA(アメリカの場合): どんな理由であれUSに入国する場合申請する必要がある。大抵すぐ承認されるが、遅くとも出発の72時間前に済ませるべきである。
• 宿: 好みに応じてホテルでもAirBnBなどで民泊を予約しても。後者はキッチンが用意されているところもある。
• 交通手段: 電車は大抵の場合当日で大丈夫だが、もちろん船舶や航空機の場合は予約が必須である。
• 冷蔵庫の整理: 日持ちしないものは消費してしまおう。

携帯するもの

• 財布: 財布は現金やカードを収納する。リスク回避の観点から財布は省きセキュリティポーチで代用することもできる。
• 鍵: 自宅を施錠、および帰りに解錠するのに必要である。こちらもリスク回避のため、自宅の鍵のみを持っていくという選択もある。
• 交通系ICカード: 空港や港に向かったり、コンビニで買い物したりする際に便利である。
• 保険証(国内の場合): 怪我や病気などになった場合、ないと損する。
• クレジットカード: 紛失した場合無効化できる。
• 腕時計 時間を気にするならあったほうがよいだろう。
• 装飾品 首掛けバードコールやブレスレットなど。省略可

一般

汎用性が高いため、これらはまとめて一つの袋などに入れておくと有用である。

• ビニール袋: ゴミや細々とした物をまとめるために、2枚程度は用意したい。
• マイクロファイバークロス: レンズやメガネなどの光学機器を使う場合必須である。
• 非常食 質量・体積あたりのカロリー密度が高いものを100kcal*日数くらい用意しておくと、いざという時の体力の回復に役立つ。
• インスタント食品 カップ麺やスープなどは熱湯を要求するが、食味とカロリー密度において優れている。特に海外に行く際、一つは用意しておくと心も暖まる。宿泊場所にキッチンがあるがスーパーは遠いといった場合、袋麺なども選択肢になり、荷物の圧縮につながる。

国内で入手しやすいものの質量とカロリーを比較すると以下のようになる。

名前	質量(g)	カロリー(kcal)	質量比
inゼリー スーパーエネルギー	120	200	1.67
大粒ラムネ	41	153	3.73
カップヌードル カレー	87	422	4.85
カロリーメイト	80	400	5.0

ゼリーは液体として扱われ、国際線には手荷物として持ち込めないので注意が必要である。

• 酔い止め: 乗り物酔いする体質の場合
• サプリメント: 旅先でバランスのいい食事ができるとは限らないのでマルチビタミンは確保したい。また、疲労対策としてアミノ酸のサプリメントもあるとよい。小分けにする場合は怪しまれないよう気を付けたい。
• ボディソープ、シャンプー、コンディショナー、洗顔料など　機内に持ち込めるよう、小さい容器に入れ密封可能な袋にまとめておく。もし宿泊先にあるという確証がある場合は省いても良い。
• 固体石鹸: もし上記のいずれかを切らした場合のバックアップになる。液体枠を圧迫しないため持っておいて損はない。
• 剃刀: 除去すべき体毛がある場合用意すべきである。
• ネックライト: 街灯がなく真っ暗闇になるところもあり、安全を確保する上で重要だ。
• 爪切り: 爪が伸びすぎると危険かつ不衛生である。1週間を超える滞在の場合は爪切りは必須である。
• 日焼け止め: 低緯度地域に向かう場合、紫外線から体を守るために用意したい。
• ポケットティッシュ
• 布: 袋でもいいしハンカチでもいい。
• 絆創膏: 大きめのものが3枚程度あると安心だ。
• 櫛・ヘアブラシ
• 新聞紙などの薄い紙: 靴が濡れた際に乾かすのに使える。

衣類

行き先の気候に合わせたものを用意する。

• 下着
• 靴下
• シャツ
• 手袋
• 洗濯可能な衣類ケース

電子・電気製品

電気製品は一つの袋にまとめておくと、手荷物検査を迅速に進められる。

• イヤホン・ヘッドホン: 移動中に音楽を楽しみたい場合。音漏れしにくく、遮音性が高いものを選びたい。国際線では機内エンターテイメントのためにイヤホンが配布される場合もあるが、音質は極めて劣悪だ。
• 撮影機材: 旅の思い出を残す一つの手段だ。
  • カメラボディ: 割となんでもよい。レンズを交換する隙を晒したくない場合は複数持って行こう。
  • 広角レンズ: 風景、建築、料理や集合写真など、トリミングする前提で幅広く応用できる。大は小を兼ねるとはこのことだ。
  • 超望遠ズーム: 150-600mmなど。2kg程度で取り回しがよく、野鳥や動物の撮影に適する。
  • 高倍率ズームレンズ: 画質・明るさにこだわらないなら、18-300mmなどの高倍率ズームレンズの一本だけでもよい。多くはAPS-C向けで、風景から、野鳥などの撮影まで使える画角を持つ。
  • 三脚: 夜景、自撮り、動画のいずれかを撮る予定なら三脚は欲しい。いざという時は武器にもなる
  • カメラのバッテリーの充電器: 写真のみなら大抵数日は持つが、それ以上の場合は充電器を用意しておくと安心だ。
  • カメラの予備バッテリー
• カメラとPCを接続するためのケーブルやハブ
• ラップトップPC: 現地で撮った写真を取り込んで編集、投稿するという一連の流れを実現する上であると望ましい。
• USB充電器: タップに5V出力が付いたようなものは変換プラグとのシナジーがある。
• スマートフォンを充電するためのケーブル
• モバイルバッテリー: 携帯端末のバッテリー切れは避けたい。航空機を使う場合、こちらは預けることができないので要注意。

国外の場合

• ボールペン: 税関申告書や出入国カードの記入に必要となる。機内で取り出せるようにしておこう。
• SIMカードを二枚挿しできるスマートフォン: SIMカードの入れ替えは紛失のリスクが伴う。二枚挿入できるスマートフォンを持って行こう。　
• 旅券(パスポート): 言わずもがな。
• 海外キャッシングのできるカード: 大量の現金を事前に用意するのはコストやリスクの観点からあまりよろしくなく、通貨によってはそもそも事前に用意できないケースもある。現地で現金を得る手段として確保しておきたい。
• 変換プラグ: 行き先によっては必要となる。
• 現金: 最低限、現地の通貨をあらかじめ用意しておきたい。それが難しい場合、現地で両替できるようなものを代わりに持って行こう(メキシコペソなら米ドルなど)。

娯楽

荷物に余裕があるなら、いずれかを持っていくのも一興だ。

• 携帯用ゲーム機: 移動中の暇潰しになる。
• トランプ、花札、サイコロなど: 筆者とは無縁だが、複数人での旅なら一つの楽しみとなりうる。
• DJコントローラ: もし知人同士で自動車に乗り、運転しないということであれば車内が盛り上がること間違いなしだ。
• MIDIキーボード: 旅先の雰囲気を音楽として残したいなら是非とも用意したい。25鍵など小さいものでもあるとないとでは大違いだ。

出発の直前に(国外の場合)

• 日本食は食べたか？ 長旅の前に日本の食べ物を体に蓄えておきたい。和食やラーメンなどはもちろんだが、見落としがちなのは洋食(オムライスなどの日本料理)だ。
• 風呂に入ったか？ 日本から北米までの距離を渡る際、ほぼ一日風呂に入らずに過ごすことになる。しかも浴室は日本よりも簡素な場合がほとんどなので、出発する直前に入念に体を洗おう。

余録

いかがだろうか？今回ダラスへと向かう機内で執筆していたが、ネックライトと新聞紙を忘れていたことに気づいた。次回はこのリストを見返して気をつけると同時に、読者にもチェックリストの作成をおすすめしたい。

ある期間内に更新されたデータを素早く検索できるモデル

特定の技術とは関係ない、誰でも思いつきそうな、でも便利なお話。

こんなケースを考えてみよう。

人気のトレーディングカードゲームAugur Unlimitedを扱うショップ「しらさぎ商店」では、1000種類にも及ぶカードの買い取り・販売をしている。記録のため、カードごとに日時、価格、在庫数などをまとめたレコードを毎日データベースに書き込んでいる。

新着・売り切れや、価格の変化などを、指定された期間について一覧で表示するようなWebページを作りたいとオーナーは考えた。しかし、ユーザーからの要求ごとに全データの差分を取るのは、あまり効率的な手段とはいえない。レアなカードでもない限り価格は一定であることが多いからだ。 どうすれば更新されたものだけを効率よく取り出せるだろうか？

答えはシンプルで、「日時」を「作成日時」と「終了日時」に分け、価格などが変わった時だけ新しくレコードを作成すると同時に、前のレコードの終了日時を更新すればよいのだ。新しいレコードの終了日時は未来永劫先とする。こうすると、任意の期間t0 ～ t1について、「更新される前のデータの集合」と「更新後のデータの集合」を取得することができる(データベースがこのようなクエリを許す限り)。

• 更新前: t0 < 終了日時 < t1 かつ 作成日時 < t0
• 更新後: t0 < 作成日時 < t1 かつ 終了日時 > t1

図にするとこんな感じだ。

赤で示したレコードと緑で示したレコードを比較すると、サンカノゴイが削除され、イスカとカワセミが更新、コブハクチョウが新しく追加されたことがわかる。二番目の条件は、期間内に作成・終了されたレコード(カワセミ)を弾くためのものだ。

至極単純なアプローチだが、このような問題について記述している文章が見つからなかったので、今後のために残しておく。

追記 この形式はValid timeと呼ばれているらしい。

戊戌の追憶

この記事は、筆者が過ごした2018年を簡潔に振り返り、その経験を糧とすることを狙う。

1月

第二鰓弓由来側頸嚢胞という先天異常が原因で首が化膿し、激痛に苦しんでいた。対人関係のトラブルなどもあり軽い錯乱状態にあったのか、自分が知らない間に高い買い物をすることがあった。

drinkery: Boozy streaming library というストリーム処理ライブラリを作った。当初はすべて酒関係の用語を用いていたが、批判を受けてそこはやめた。今思えばそれで正解だった気がする。 パフォーマンスはモナディックなAPIを持つライブラリの中ではトップクラスで、双方向性や多入力多出力のような発展的な機能もあるが、ListTが正しく効率的に実装されているのがなによりの魅力である。ListTのために時々使っている。

• Drinkery the boozy streaming library - School of Haskell | School of Haskell

危うい精神状態だったが被写体には恵まれた。この写真はけっこう気に入っている。

寒烏今日のおやつは霜柱 pic.twitter.com/wtbOIkGhYP

— 🐦ふみ (@fumieval) 2018年1月20日

2月

警察のおかげで対人トラブルは解消された。アリピプラゾール(エビリファイ)の服薬を始めて、自分の脳の働きが変質しているような感じがした。薬のせいか忘れ物が増えた。

Discordのボイスチャンネルに入った際に通知メッセージを投稿する GitHub - fumieval/discord-vc-notification を作った。実用とHaskellのチュートリアルを兼ねている。けっこうな数のサーバーに導入されたようで喜ばしい。

fumieval.hatenablog.com

生き甲斐の一つである野鳥撮影は続けた。

写真を撮っていたらヤマガラが至近距離に割り込んできた pic.twitter.com/EMlHZEsBhn

— 🐦ふみ (@fumieval) 2018年2月11日

3月

花粉症とその薬のせいで生産性がかなり削られていた気がする。

PPL 2018: 第20回プログラミングおよびプログラミング言語ワークショップ

のために鳥取に行った。ヘラサギというレアな鳥に会えた。

ヘラサギを初めて見た。これだけでも鳥取に来た甲斐がある pic.twitter.com/2Jl0CjMAlO

— 🐦ふみ (@fumieval) 2018年3月7日

4月

溜め込んでいた力を解放できた月だ。

Bigmoonが私の看板ライブラリであるextensibleを使っており、偵察のためにアルバイトを始めた。2週ごとに名古屋に出勤という形で楽しく仕事を続けている。

Haskell-jpの新しいロゴ案を作り、投票によって正式に採用された。薬でブーストされたセンスのおかげだと思う。

私がデザインしたHaskell-jpのロゴが採用された pic.twitter.com/jytvvOIk3M

— 🐦ふみ (@fumieval) 2018年4月12日

5月

アリピプラゾールの副作用の悪夢や物忘れが気になってくる。

Wikiシステムを作った。アルゴリズムからWebプログラミングまで様々な技術を応用するいい課題だった。現在もextensible攻略Wikiに使われている。

https://t.co/vI3YAK7KvS Haskell(と一部PureScript)でWikiを作ってみた。変更がリアルタイムで反映され、コンフリクトが発生した場合もその場で処理する迅速さが売りだ。extensibleパッケージの攻略Wikiとして現在も稼働中 https://t.co/ZWz3pxzRTR pic.twitter.com/Ei7TkgkWkS

— 🐦ふみ (@fumieval) 2018年5月9日

この時期はシギ・チドリ類が飛来し、干潟などでよく観察できる。毎年お疲れ様と言いたい。

死屍累々 pic.twitter.com/Ux3zZG7Vq5

— 🐦ふみ (@fumieval) 2018年5月25日

6月

スキーマを導出してWell typedかつ短いエンコードができるだけでなく、後方互換でコンポーザブルなデシリアライザを構築できる直列化ライブラリ、wineryを創り出した。機能面もパフォーマンスもなかなか優秀なライブラリだと思う。

fumieval.hatenablog.com

サギの雛たちが育ってきてコロニーでは賑やかな光景が見られた。

pic.twitter.com/a7InQydZIH

— 🐦ふみ (@fumieval) 2018年6月18日

7月

CAT S60という、サーモグラフィー搭載のごついスマートフォンを買った。他に使っている人を見たことはなく、自慢できる一本だ。

Overwatchでメインで使っていたキャラクターであるシンメトラがリワークを受け、使える技が一新された。研究がされてないこともあいまって環境にぶっ刺さり、シルバーからプラチナ帯までのし上がった。

とあるオフ会に参加して知り合いが増えた。

togetter.com

8月

Lisztというデータベースの実装を一新し、全データを一つのファイルにまとめる試みをしていた。非常に興味深い例題でけっこうな時間を費やした。

Minecraft (Bedrock Edition)でよく遊んだ。しばらくMinecraftから離れていたが、新しい生物やブロックなどが追加されていて通話などもしつつ楽しめた。新たな居場所を見出したような気がした。

9月

Compact regionsというGHC 8.2の新機能の効果的な使い方を発見した。更新頻度が低いデータを納め、それをIORefで保持するのがよい。私が執筆したものではないがこの記事でよく説明されている。

qiita.com

ガス欠気味であまり新しいものを生み出せなかった。なおOverwatchではシンメトラで暴れまくった。

10月

三宅島へと飛んだ。船で行く予定だったが台風で欠航になり、仕方なく新中央航空の19人乗りの双発機で行った。

ほぼ徒歩で島を一周するという目論見で、穏やかながら新鮮な離島の雰囲気を味わうことができた。

上京した pic.twitter.com/vozwPdHWh9

— 🐦ふみ (@fumieval) 2018年10月1日

予約していた民宿の女将は欠航が理由で私は来ないと思い込んでいたようで、無人の宿の前で待ちぼうけを食うというアクシデントがあった。幸い、数時間したら女将が戻ってきたため蚊に血を吸い尽くされるのは免れた。女将の作ってくれた料理はとても美味しかった。結局、宿泊費はただにしてもらったので結果オーライである。

個人経営の古めかしいスーパーマーケットに東方や艦これのグッズが飾ってあり、離島は離島でも同じ世界にいることを感じた。

三宅島で過ごした三日間は、間違いなく幸せなものだった。鳥の多い時期にまた行きたい。

行きつけのMinecraft BEのサーバーが過疎気味だったので、自分で新しいサーバーを立てた。Java版ゆえにサーバーMODなどが豊富で、以前とはまた違った楽しみ方ができた。

11月

Haskell Day 2018が開催された。Haskell関連の勉強会が開催されるのは久しぶりだ。来場者は150人と大盛況で、有意義なものだった。なお、私はLisztについての発表をしたが、しばらくこのような場に立つことがなかったため発表スキルの低下を痛感した。

仕事ではGHC 8.6への移行に従事していた。セグメンテーション違反で落ちる致命的なバグが見つかったのもいい思い出だ。#15892 (Segmentation fault with ByteString) – GHC

自分でも理由はよくわからないが、この月は写真をあまり撮らなかった。よくよく考えると精神的に不安定だった気がする。

カラスは荒々しいイメージを持たれることが多いが、水浴びしている時の表情は本当に無邪気だ pic.twitter.com/uAuvmcd5x1

— 🐦ふみ (@fumieval) 2018年12月1日

12月

心の調子が急激によくなった。

簡潔データ構造に興味が湧き、厳密には簡潔データ構造ではないがElias-fano encodingという手法について調べていた。

fumieval.hatenablog.com

普段扱っている純粋関数型データ構造とはまた違ったトリッキーさがあり、刺激的な体験だった。

ローグライクなカードゲームのSlay the Spireに少しはまったりした。一押しはディフェクトで、「山札から任意の2枚を選ぶ」「山札の先頭数枚から好きなだけ選んで捨てる」「捨て札を手札に戻す」といった制御系のカードを揃えていき、運ゲーを運ゲーでなくする過程が楽しい。

そして鳥の季節がやってきた。昨年は見られなかったアトリが来ていて喜ばしい。

アトリの飛来を確認した pic.twitter.com/cAnrqVi8qE

— 🐦ふみ (@fumieval) 2018年12月10日

総評

一年を通して、私の心と体、そして人間関係などの環境は徐々に改善された。ストレスの減少によって体づくりの効率も上がったのも間違いない。

そして、私は新しい能力、新しい道具、新しい仲間を得ることができた。来年からとは言わず今日から、それらを無駄にすることのないよう心がけていきたい。

Elias-Fano encoding: 単調増加する数列をほぼ簡潔に表現する

Haskell Advent Calendar 2018 20日目

単調増加する自然数の列を、最低限のビット数で表現するための興味深いテクニックと、Haskellによる実装を紹介する。

Elias-Fano encoding

この手法は、簡潔データ構造に分類されるもの一つであるが、厳密には条件を満たさないため疑似簡潔データ構造と呼ばれる。1970年代、Peter EliasとRobert Mario Fanoによって独立して発見された。

例題として1, 1, 4, 10, 17, 22, 23, 30という列をエンコードしてみよう。まず、それぞれの数を上位3ビットと下位2ビットに分割する。列の長さをNとしたとき、上位のビット数はとする。

上位ビットの列は000 000 001 010 100 101 101 111となる。これをヒストグラムのようにして2³個のビンに分ける。

• 000: 2個
• 001: 1個
• 010: 1個
• 011: 0個
• 100: 1個
• 101: 2個
• 110: 0個
• 111: 1個

これにアルファ符号(個数分だけ1を並べ、0で区切る)を適用すれば上位の表現は完成だ。要素数分の1と、バケット数分の0を合わせるのでおよそビット使う。

1101010010110010

下位ビットの列は、そのまま結合する。こちらは、元のビット数をWとしたとき、 ビット消費する。

0101001001101110

32ビットの整数を10⁵個格納する場合、消費ビット数は17*10⁵ビットとなかなか優秀な圧縮率を誇る。

n番目の値を読み出すときは、上位はを求め、下位はそのまま取り出してくっつければよい。は簡潔データ構造の文脈でよく使われる演算の一つで、ビット列のn番目に出現する1の位置を求める。nを引くのは、ちょうどn個だけ0が混ざっているからだ。

実装

早速実装してみよう。上位ビットのエンコーダは非自明そうに見えるが、要素の位置、上位ビット、カウンタの三つ組(i, u, n)を持つステートマシンで簡単に表現できる。

• (i, u, n) = (0, 0, 0)から開始する
• uが最大値を超えたとき、nを出力し停止
• i番目の上位ビットとuを比較する
  • 等しい場合、(i + 1, u, n + 1)に更新する
  • 異なる場合、nを出力し、(i, u + 1, 0)に更新する

あまり知られていないが、vectorパッケージにはData.Vector.Fusion.Stream.Monadicという簡単なオートマトンを表現するためのモジュールがある。状態と、それを更新する関数の対という単純な作りで、最適化が効く限りこの構造は消滅してただのループとなる。表現力は限られているが、他の追従を許さないパフォーマンスを誇る。

data Stream m a = forall s. Stream (s -> m (Step s a)) s

data Step s a where
  Yield :: a -> s -> Step s a
  Skip  :: s -> Step s a
  Done  :: Step s a

ビット列をVector Boolのように愚直に扱っていては空間効率が悪いので、まずはビット列をWord64の配列に変換する仕組みを作りたい。ここでは受けとったWord64から任意のビット数だけ切り取り、それらを連結して出力する変換器を定義する。Bの最初のフィールドが切り取るビット数となる。溢れたビットの処理はやや煩雑だが、やるだけなので読み飛ばしても構わない。ただしINLINEは必須で、これがないと最適化が止まってしまいポテンシャルを発揮できない。

import Data.Bits
import Data.Word (Word64)
import qualified Data.Vector.Fusion.Stream.Monadic as S

data B = B !Int !Word64

data Chunker s = Chunker s !Word64 !Int
  | ChunkerDone

chunk64 :: Applicative m => S.Stream m B -> S.Stream m Word64
chunk64 (S.Stream upd s0) = S.Stream go $ Chunker s0 zeroBits 0 where
  go ChunkerDone = pure S.Done
  go (Chunker s acc len) = flip fmap (upd s) $ \case
    S.Done -> S.Yield acc ChunkerDone
    S.Skip s' -> S.Skip $ Chunker s' acc len
    S.Yield (B width w) s' -> case mask width .&. w of
      w' | width + len >= 64 -> S.Yield (acc .|. unsafeShiftL w' len)
            $ Chunker s' (unsafeShiftR w' (64 - len)) (len + width - 64)
         | otherwise -> S.Skip $ Chunker s' (acc .|. unsafeShiftL w' len) (len + width)
{-# INLINE chunk64 #-}

次に、アルファ符号のエンコーダを定義する。chunk64は64より長いビット列を受け取れないので、複数に分けるという処理をする。

data Unary s = Unary s | UnaryCont !Int s

unary :: Applicative m => S.Stream m Int -> S.Stream m B
unary (S.Stream upd s0) = S.Stream go $ Unary s0 where
  go (Unary s) = flip fmap (upd s) $ \case
    S.Done -> S.Done
    S.Skip s' -> S.Skip (Unary s')
    S.Yield n s' -> step n s'
  go (UnaryCont n s') = pure $ step n s'
  step n s'
    | n < 64 = S.Yield ((n + 1) `B` mask n) (Unary s')
    | otherwise = S.Yield (B 64 (complement zeroBits)) (UnaryCont (n - 64) s')
{-# INLINE unary #-}

これらを組み合わせてエンコーダを定義する。エンコードの結果として出力するのは以下の5つ組だ。

data EliasFano = EliasFano
    { efLength :: !Int
    , efWidth :: !Int
    , efUpper :: !(UV.Vector Word64)
    , efRanks :: !(UV.Vector Int)
    , efLower :: !(UV.Vector Word64)
    }
    deriving Show

• efLength: 要素数
• efWidth: 下位ビットの幅
• efUpper: 上位ビットの列
• efRanks: 上位ビットの列をpopcountして累積加算させた列(あとで有利に働く)
• efLower: 下位ビットの列

以下がエンコーダの実装だ。Streamを効率よくVectorに変換する関数が提供されており、fromStream'でそれらを利用している。upd関数は先に述べたアルゴリズムを実装している。unsafeが散らばっていて可読性はよくないが、ロジックは比較的わかりやすいだろう。

import Control.Monad.ST
import Data.Bits
import qualified Data.Vector.Generic as V
import qualified Data.Vector.Generic.Mutable as GM
import qualified Data.Vector.Unboxed as UV
import qualified Data.Vector.Fusion.Bundle.Monadic as B
import qualified Data.Vector.Fusion.Bundle.Size as B
import qualified Data.Vector.Fusion.Stream.Monadic as S
import Data.Word

data EncoderState s = ESCont !Int !Word64 !Int | ESDone

unsafeFromVector :: V.Vector v Word64 => v Word64 -> EliasFano
unsafeFromVector vec = runST $ do
  efLower <- fromStream' ((efWidth * efLength + 63) `div` 64)
    $ chunk64 $ S.map (B efWidth . fromIntegral) $ B.elements $ B.fromVector vec
  efUpper <- fromStream' ((efLength + 3) `div` 4)
    $ chunk64 $ unary $ S.Stream upd $ ESCont 0 0 0
  return EliasFano
    { efRanks = UV.prescanl (+) 0 $ UV.map popCount efUpper
    , ..
    }
  where
    upd ESDone = pure S.Done
    upd (ESCont i current n)
      | current > maxValue `unsafeShiftR` efWidth = pure $ S.Yield n ESDone
      | otherwise = pure $ case fromIntegral $ V.unsafeIndex vec i `unsafeShiftR` efWidth of
        u | u == current -> S.Skip $ ESCont (i + 1) current (n + 1)
          | otherwise -> S.Yield n (ESCont i (current + 1) 0)

    efLength = V.length vec

    fromStream' len s = GM.munstream (B.fromStream s (B.Exact len))
      >>= UV.unsafeFreeze
    {-# INLINE fromStream' #-}

    maxValue
      | V.null vec = 1
      | otherwise = V.last vec + 1
    efWidth = max 1 $ ceiling $ logBase 2 (fromIntegral maxValue / fromIntegral efLength :: Double)
{-# SPECIALISE unsafeFromVector :: UV.Vector Word64 -> EliasFano #-}

鬼門となるのは要素のアクセスだ。まずはWord64に対するselect関数を実装しなければならない。これに関しては優れたアルゴリズムが研究されており*1、ekmett先生によってすでに実装されていた*2のでそれを拝借した。この手法を直感的に理解するのは、私の頭では不可能だった。

ここさえクリアすれば、Word64の配列に対してselectを実装するのはさほど難しくない。どの要素に対してselectWord64を呼べばいいかは、先に用意しておいたpopcountの配列に対する二分探索によって判断できる。

select :: (V.Vector v Int, V.Vector v Word64) => v Int -> v Word64 -> Int -> Int
select ranks vec q = go 0 (V.length ranks - 1) where
  go l r
    | l >= r = selectWord64 v (q - V.unsafeIndex ranks l) + 64 * l
    | q < V.unsafeIndex ranks (i + 1) = go l i
    | otherwise = go (i + 1) r
    where
      i = div (l + r) 2
      v = V.unsafeIndex vec i
{-# SPECIALISE select :: UV.Vector Int -> UV.Vector Word64 -> Int -> Int #-}

下位ビットを読み出す処理は、ビットを跨ぐ場合さえ気をつければ大丈夫だ。

readBits :: V.Vector v Word64 => v Word64 -> Int -> Int -> Word64
readBits vec width pos
  | b + width > 64 = unsafeShiftL extra (64 - b) .|. base
  | otherwise = base
  where
    i = unsafeShiftR pos 6
    b = pos .&. 63
    base = (V.unsafeIndex vec i `unsafeShiftR` b) .&. mask width
    extra = V.unsafeIndex vec (i + 1) .&. mask (width + b - 64)
{-# SPECIALISE readBits :: UV.Vector Word64 -> Int -> Int -> Word64 #-}

これらを合わせればインデックスの処理が出来上がる。上位ビットの配列は、元の列の長さNに対して個、selectの計算量は配列の長さNについてなので、この演算の計算量はとなる。

(!) :: EliasFano -> Int -> Word64
(!) (EliasFano _ width upper ranks lower) i
  = fromIntegral (unsafeShiftL (select ranks upper i - i) width)
  .|. readBits lower width (i * width)

ここで紹介したコードはGitHubに保存している。

github.com

テスト

ビット演算という性質上、同じ型の中でたくさんの値を扱うためバグが湧きやすい。QuickCheckは大いに役立った。最終チェックとして以下のテストを残した。

import qualified Test.QuickCheck as QC

prop_access :: [QC.NonNegative Int] -> QC.NonNegative Int -> QC.Property
prop_access xs i_ = QC.counterexample (show (base, ef, i))
  $ ef ! i == base !! i
  where
    i = QC.getNonNegative i_ `mod` length base
    base = scanl (+) 0 $ map (fromIntegral . QC.getNonNegative) xs
    ef = unsafeFromVector $ UV.fromList base

ベンチマーク

やはり気になるのはパフォーマンスだ。適当に単調増加する数列をこしらえ、反転やインデックスなどの基本的な演算と比較した。

td :: V.Vector Word64
td = V.scanl (+) 0 $ V.fromList $ map (toEnum . fromEnum) $ "Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua. Ut enim ad minim veniam, quis nostrud exercitation ullamco laboris nisi ut aliquip ex ea commodo consequat. Duis aute irure dolor in reprehenderit in voluptate velit esse cillum dolore eu fugiat nulla pariatur. Excepteur sint occaecat cupidatat non proident, sunt in culpa qui officia deserunt mollit anim id est laborum."

main = do
  let ef = unsafeFromVector td
  defaultMain
    [ bench "encode/elias-fano" $ whnf unsafeFromVector td
    , bench "encode/vector" $ whnf V.reverse td
    , bench "access/elias-fano" $ nf (map (ef!)) [0..V.length td - 1]
    , bench "access/vector" $ nf (map (td V.!)) [0..V.length td - 1]
    ]

結果はこの通りだ。インデックスはUnboxed Vectorの2倍強遅いが、内部で3つの配列を使っていることを考えると期待以上であると言える。

encode/elias-fano                        mean 3.891 μs  ( +- 78.82 ns  )
reverse/vector                            mean 705.7 ns  ( +- 12.20 ns  )
access/elias-fano                        mean 16.69 μs  ( +- 423.2 ns  )
access/vector                            mean 7.499 μs  ( +- 2.076 μs  )

応用

Elias-Fano encodingはマイナーな手法ではあるが、よく知られている応用として検索のためのインデックス化が挙げられる。単語ごとに、マッチする文書の番号の一覧をメモリ上に保持するといった風に利用できる。ここでは紹介しなかったが、ある値より等しいかそれ以上の要素を探すという演算も効率よく実装でき、積集合を求める操作において並外れたパフォーマンスを発揮する。

また、個人的な研究として、LOUDSなどの木構造の簡潔な表現と組み合わせ、シリアライズに応用できないか模索している。直列化に簡潔データ構造を用いる例は少ないので開拓しがいがあると感じている。

まとめ

• Elias-Fano encodingは、単調増加する自然数の列を圧縮しつつ、効率の良いアクセスも提供する
• Data.Vector.Fusion.Stream.Monadicを使って、パフォーマンスを犠牲にすることなく抽象度を高められる
• QuickCheckにより、複雑でバグを仕込みやすい処理も簡単にテストできる
• 利用例がまだ少なく、研究しがいがある

参考文献

• Sorted integers compression with Elias-Fano encoding | Antonio Mallia

*1:Sebastiano Vigna, Broadword implementation of Rank/Select Queries, 2014

*2:https://github.com/ekmett/succinct/blob/master/src/Succinct/Internal/Broadword.hs#L82

「名前の束縛」という名の束縛

実用的なプログラミングにおいて、名前と概念を結びつける「束縛」はほぼ必須の概念である。しかし、その言葉には大きな誤解と混乱が根付いていた。

事の発端となったのは「Haskellにおいては、変数は値を代入するものではなく、値に束縛するものである」という議論である*1 *2。しかし、これは大きな誤解を孕んでいる。言葉の定義に立ち返ってその誤解を解いていこう。

束縛とバインディング

実は「束縛」には二つの意味がある。一つは、数学的な意味での変数の束縛*3、もう一つは、識別子と実体の結合という意味での束縛*4だ。

前者は変数の導入と言い換えることもできる。ラムダ計算におけるラムダ抽象と変数の関係もこれである。重要なのは、これはあくまで変数とそれを導入する抽象の関係であり、変数と実体の関係ではないことだ。

「AをBに束縛する」と言った場合後者で、プログラミングの文脈ではこちらを耳にすることが多いだろう。混乱を避けるため、後者を「バインディング」、あるいは「バインド」と本稿で呼ぶことにする。バインディングは以下のような関係性として説明できる。

• 主語 バインディングが
• 目的語 識別子を
• 間接目的語 実体(式、値、計算など)に
• 述語 束縛する

Haskellにおける誤解

Haskellは、x = 42のような定義を与えることによって、変数で値を参照できる。だからといって「Haskellでは変数を値にバインドする」と言い切ってしまうことには大きな問題がある。理由は簡単で、変数に対して値以外もバインドできるからだ。例えばy = x + 1という宣言を考えてみよう。この宣言はyをバインドするが、その対象はx + 1という計算であり、式を評価した結果の値ではない。

定義がインライン化(その名前が使われている場所に展開)されず、メモリ上に領域を確保すべきものと処理系が判断した場合、初めて値に関する議論が始まる――これが「代入」である。代入は、オブジェクトをヒープ(実行時に確保されるメモリ領域)上の場所にセットする。ここで言うオブジェクトは大きく分けて2種類ある*5。

• 未評価の計算(1 + 1など)
• 値(1、Just (6 * 7)、\x -> x * x)など

代入に構文上の概念である変数が介在する必要はなく、しかも値以外のオブジェクトも代入できる。したがって、Haskellの文脈で「変数に値を代入する」と言うのは便宜的に通用こそするものの、実は二重、三重に混乱した表現であることがわかる。

この混乱は言語仕様ですらやらかしてしまっている。Haskell 2010 Language Reportの3.17.2 Informal Semantics of Pattern Matchingを見ると、"Binding does not imply evaluation"と注記しているにもかかわらず、本来オブジェクトに対するものであるパターンマッチを値に対するものと宣言してしまい、変数を値に束縛するという旨の表現を二箇所で使ってしまっている。学習者は言語仕様を読むだけでなく、case undefined + undefined of _ -> 42のような式を手元で評価し、実際の意味論を把握することを推奨する。

さらなる誤解？

Rustの公式ドキュメント *6 では、「値を変数に束縛する(bind some value to a name)」という、ここまでの議論からすればもってのほかな表現が使われている。この節は削除されたが、同様の表現が最新版にも残っている。これに関して、所有権によって変数と値の一対一対応があるから可能であるという意見が有識者によって述べられた。

Rust、所有権があって型によっては値と変数が一対一になるのでそういう意図かなーと好意的に解釈してます

— κeen (@blackenedgold) October 30, 2018

加えてHaskellと違いRustにはサンクなどは存在しないため、確かにそう言うこともできるのかもしれない。

まとめ

以下のような主張はすべて誤りである。

• Haskellに変数は存在しない: 変数は本来不定のものという意味で、一度代入した値を変えられる構造ではない。それだけでなく、HaskellにはIORefのような参照型も存在する。そもそも本来「ミュータブルな参照」と呼ぶべき概念を変数と呼称すべきではない。
• Haskellでは全てが定数である: 定数は場合にかかわらず決まった値を持つもの、例えば0や円周率などで、実行時に変化させることのできないものがすべて定数というわけではない。
• Haskellには代入は存在しない: 代入そのものはほとんどの実用的な言語に存在する概念で、もちろんHaskellも例外ではない。変数が直接指し示す場所に再代入をすることは許されていない点が、Cなどの典型的な手続き型言語と異なる。繰り返しになるが、IORefやミュータブルな配列などを使えば、同じ構造を参照しながら、中身の値を実行時に変化させることができる。
• 純粋な関数型言語では変数は値に直接束縛される: この文言を信じていると、遅延評価を原則とする言語で痛い目を見ることになるだろう。バインディングは式の評価とは無関係であることを忘れてはいけない。

また、英語などで書かれた文書を翻訳するときも、bindがどちらの意味で使われているかに注意を払うべきである。

*1:Haskellの変数には値を代入しません、束縛します。

*2:手続き型との違い

*3: 自由変数と束縛変数

*4: 束縛 (情報工学) - Wikipedia

*5:GHCにおけるオブジェクトの正確な分類は、Commentary/Rts/Storage/HeapObjects – GHCで詳しく述べられている

*6: Variable Bindings - The Rust Programming Language

日持ちする直列化のためのライブラリ「winery」

人類は、酒と共に発展してきたと言っても過言ではない。穀物や果実などを酒に変換することにより、糖を除く栄養を保ったまま、高い保存性を持たせることができる。酒は人々の喉を潤し、時に薬として使われた。

プログラミングにおいても、終了したら消えてしまうデータを、保存性の高いバイト列に変えたい場面がよくある。そのような操作を直列化(シリアライズ)と呼び、いくつかのアプローチが存在する。

コード生成タイプ

Protocol Buffers、cap'n'protoなど

データの構造を記述する言語(スキーマ)から、データ構造およびシリアライザ・デシリアライザをコードごと生成する。幅広い言語で使える一方、作れる構造が限られており、定義済みの構造にも使えないので、Haskellのような言語とは相性があまりよくない。

互換性を保つ機能が充実していることが多い。

汎用フォーマットタイプ

CBOR、MessagePack、JSON、XMLなど

数値や文字列などを自由に組み合わせられる表現を用いる。腐りにくく、表現の自由度も高いが、レコードの配列などをエンコードするとフィールド名の分だけ冗長になってしまう。また、既存のデータ型との相互変換において互換性を保つには自分で処理を書く必要がある。

固定タイプ

Marshal (OCaml)、binary (Haskell)など

何のメタデータも持たせず、値の集まりを直接エンコードする。バイト数を短縮でき、型さえ合っていれば正しくデコードできるが、型が変わってしまうと元のデータは使い物にならなくなってしまう。そのため、複雑な構造の長期保存には向かない。

winery

これらのアプローチの欠点を克服するため、wineryという新しいライブラリを開発した。

基本のインターフェイスはbinaryと同様、至ってシンプルである。Serialiseクラスのインスタンスなら、 serialiseで値をByteStringにエンコードし、deserialiseでデコードできる。

instance Serialise a where
  schemaVia :: Proxy a -> [TypeRep] -> Schema
  toEncoding :: a -> Encoding
  deserialiser :: Deserialiser a

serialise :: Serialise a => a -> ByteString
deserialise :: Serialise a => ByteString -> Either StrategyError a

ジェネリクスを用いて、レコードや和型にインスタンスを与えることもできる。以下のように書けばレコードのためのインスタンスを生成できる。gdeserialiserRecordにJustを与えれば、デフォルト値を指定することもできる。

instance Serialise Foo where
  schemaVia = gschemaViaRecord
  toEncoding = gtoEncodingRecord
  deserialiser = gdeserialiserRecord Nothing

このように宣言を省略した場合、任意の和型に対応したものが作られる。

instance Serialise Foo

wineryがbinaryと違うのは、データだけでなく、そのスキーマも直列化するという点だ。serialiseはスキーマを付属させることにより、生成元のプログラムが変わったり失われたりしても、データがどのような構造を持っているか知ることができる。フィールド名などのメタデータを一箇所に集約することによって、CBORやJSONなどの持つ冗長性を解決している。

|スキーマのバージョン|スキーマ|データ|

以下はwineryのスキーマ型の定義である。Serialiseのインスタンスはジェネリクスによって導出されている。

data Schema = SSchema !Word8
  | SUnit | SBool | SChar
  | SWord8 | SWord16 | SWord32 | SWord64
  | SInt8 | SInt16 | SInt32 | SInt64 | SInteger
  | SFloat | SDouble
  | SBytes | SText
  | SList !Schema | SArray !(VarInt Int) !Schema
  | SProduct [Schema] | SProductFixed [(VarInt Int, Schema)]
  | SRecord [(Text, Schema)]
  | SVariant [(Text, [Schema])]
  | SFix Schema
  | SSelf !Word8
  deriving (Show, Read, Eq, Generic)

SFixとSSelfはやや奇妙に映るかもしれない。これは、再帰的なデータ型のためのもので、SFixは不動点を束縛し、SSelf nは直近n番目の不動点を参照する。このFooとBarのような複雑に絡み合った再帰も、wineryならば難なく直列化できる。

data Foo = Foo | FooBar Foo Bar
data Bar = BarFoo Foo | BarBar Bar

スキーマとデータを分別して使うことももちろん可能だ。serialiseOnlyは、データのみを直列化する。

serialiseOnly :: Serialise a => a -> ByteString

スキーマはschema関数で取得できるので、そのままserialiseすれば良い。

schema :: Serialise a => proxy a -> Schema

データを復元する際は、まずdeserialiseでSchemaを取り出したのち、getDecoderでデシリアライザを生成する。対応していないスキーマの場合はエラーになり、成功した場合はByteStringから値を復元する関数が得られる。スキーマを解釈する関数と、デコードする関数が分離されているため、一度スキーマを与えれば、多数のデータを高速に処理することができる。

getDecoder :: Serialise a => Schema -> Either StrategyError (ByteString -> a)

互換性

レコードからのフィールドの削除と、バリアントへのコンストラクタの追加は自明に互換性を保てる。それ以外の場合、自分でデシリアライザを組み立てることも可能である。

Deserialiserが基本となる構造である。Alternativeのインスタンスなので、複数の値を取り出したり、スキーマに対応できなかった場合に代わりを用意するといった合成可能性を持つ。

deserialiser :: Serialise a => Deserialiser a

レコードから値を取り出すにはextractFieldを使う。

extractField :: Serialise a => Text -> Deserialiser a

コンストラクタを抽出したい場合、extractConstructorを使う。 gdeserialiserVariant <|> (\() -> Unknown) <$> extractConstructor "Obsolete"のように、 ジェネリックな実装と組み合わせることによって今は無きコンストラクタにも対応することができる。

extractConstructor :: Serialise a => Text -> Deserialiser a

検査性

wineryのコマンドラインツールを使えば、元のプログラムなしにデータをいい感じに成形して閲覧できる。どんなデータもデシリアライズできるTerm型を内部で利用している。

$ winery --print-schema < test.winery
μ { foo :: ( Nothing | Just Integer ), bar :: [ByteString], nodes :: [Self 0] }
{ foo = Nothing
, bar = ["hello"]
, nodes = [{ foo = Just 42, bar = ["world"], nodes = [] }] }

将来的には、jqのような豪華なDSLを用意する予定だ。雑に(しかしながらコンパクトかつ高速に)ダンプした情報をwineryコマンドで整形し、UNIXのコマンドや表計算ソフトで解析するといった斬新な戦法も可能になるだろう。

隠し能力

binaryと違い、wineryのデシリアライザはステートレスである。その心は、値を取り出すために、バイト列を全て走査する必要がない。正格でない構造なら、巨大なデータの一部を必要に応じて取り出すという使い方もできる。

まとめ

wineryはbinaryに似た簡単なインターフェイスを持ちながら、シリアライズした情報の可用性を飛躍的に高める。まだまだ荒削りではあるが実用にも耐え、定番ライブラリであるbinaryやaesonの代替として高いポテンシャルがあると信じている。もしバグや要望などがあれば、ぜひGitHubに投稿願いたい。