Lazy I/O must go! - Iteratee: 列挙ベースのI/O

最近ちょっと気になるiterateeを勉強したので、日本語の解説を書いてみます。と言いつつ、大部分が The Monad.Reader Issue 16 *1 からの引用です。

はじめに

Iterateeと呼ばれる新たなI/Oの抽象化手法が、最近にわかに広まりつつあります。既存のI/Oが抱える問題を解決するべくOleg Kiselyovによって2008年頃に提唱されたiterateeは、新しい高性能webフレームワークsnap *2 や、hyena *3 で利用されています。また、HackagDB上にて、iterateeパッケージ*4、およびiterateeを利用できる様々なパッケージ *5 *6 *7 *8 が公開されています。

しかし、ドキュメントの少なさなどからiterateeがどういうものなのかよく分からないという人も多いようです。そういうわけなので、iterateeを易しく解説してみようと思います。

Haskellにおける既存のI/Oとその問題点

さてHaskellでは標準APIとしてHandleベースのI/Oライブラリが用意されています(hGetLine, hPutStr, など)。しかし、HandleベースのI/Oはもともと手続き型言語の世界からやってきたもので、HaskellAPIとして考えたとき十分に使いやすいとは言えません。その理由としては、

  • composableでない
  • 関数型でない
  • 格好良くない!

などがあります。Haskellには、Lazy I/Oというものもあります。hGetContentsなどを用いると、なるほど確かに String -> String のような関数的でとても綺麗なインターフェースで入出力処理を行うことができます。しかし、Lazy I/Oにはとても致命的ないくつかの問題点があるのです。

  • I/Oが終わると同時にリソースを開放できない。GCを待つ必要がある。これはネットワークソケットなどの限られたリソースの場合は致命的。
  • エラーハンドリングが困難。エラーの発生も遅延されるので、pureなコード内でI/Oエラーが発生するかもしれません。

これらの理由から、Lazy I/Oは使うべきではないとする意見もあるようです*9

そこでこれらの問題を解決した、次のようなAPIが望まれます。

  • composable
  • 高レベル
  • 堅牢
  • 思い通りに動く (リソース管理など)
  • ハイパフォーマンス

iterateeでは、これを逆転の発想で実現します。Handleのインターフェースは、データが必要になる度にユーザがデータを取りに行くという、いわばpull式のインターフェースですが、iterateeでは、データを受け取って処理するpush式のインターフェースになります。

iterateeとは

iterateeはfoldlのインターフェースで説明されます。Haskellプログラマならfoldlには親しみ深いと思います。foldlは3つの引数を取ります。それぞれ、

foldl :: (a -> b -> a) -> a -> [b] -> a
  • 合成関数
  • 初期値アキュームレータ
  • データ列

です。foldlはデータ列をアキュームレータに合成関数を用いて供給することにより最終出力を得ます。アキュームレータと合成関数を合わせて、iterateeと呼ぶことにします。そうすると、foldlは"iteratee"を用いて入力データを"イテレート"する、と考えることができます。

入力例を生成し、iterateeに与えるものをenumeratorと呼ぶことにします。foldlでは単なるリストですが、我々の目的であるI/Oならば、Handleから入力例を得て、それをiterateeに渡す働きをすることになります。

どうしてこのような抽象化にするのでしょうか。これはひとえに計算の合成のためです。

iterateeの合成

2つのiterateeを合成して大きなiterateeをつくるというのを考えることができます。1つ目のiterateeを走らせて計算が完了したら、残りの入力列で2つ目のiterateeを走らせます。

enumeratorの合成

1つ目のenumeratorの要素に続けて2つ目のenumeratorの要素が続くようなenumeratorが考えられます。

実装してみる

具体的なコードを見たほうが理解も速いと思いますので、実際にiterateeを実装していくことにします。

まずはデータストリームとiterateeのデータ構造を定義します。

data StreamG el = Empty | El el | EOF

data IterV el a
  = Done a (StreamG el)
  | Cont (StreamG el -> IterV el a)

StreamGが入力ストリームを表しますが、一般的なストリームの定義とは異なります。ストリーム全体を保持するのではなく、ただ1つ(もしくは0個)の要素を保持します。ストリーム全体は[StreamG]として表されます。これはEOFの情報を持たせたいためです。

iterateeを表しているのがIterVです。IterVはfoldlにおけるiterateeに対応するものですが、foldlの概念とは少し異なります。それはストリーム全体を消費しなくても計算を終了できる所です。Doneが終了した状態を現しており、計算結果と最後の要素を消費したかを持っています。Contは計算途中であることを表し、続きの計算を持っています。

さて、これを動作させるために、IterVにデータを供給するためのenum関数(enumeratorを表す)と、最終結果を取り出すためのrun関数を作る必要があります。iterateeには次の3つのタイプのものがあります。enum関数はこれらをハンドルできなければなりません。

  • 有限個の要素を消費し、Doneになる
  • ストリーム全体を消費し、EOFが来るとDoneになる(例えばsumのようなもの)
  • 決してDoneにならない

enum関数は基本的にfoldlのような関数になりますが、Doneをハンドルしなければいけないところが異なっています。

加えて、未完了のiterateeにEOFを送って結果を取り出すrun関数を作ります。

enum :: IterV el a -> [el] -> IterV el a
enum i [] = i
enum i@(Done _ _) _ = i
enum (Cont k) (x:xs) = enum (k (El x)) xs

run :: IterV el a -> Maybe a
run (Done x _) = Just x
run (Cont k) = run' (k EOF)
 where
   run' (Done x _) = Just x
   run' _ = Nothing

iterateeの例

具体的なiterateeの例を、よくあるリストの操作を定義することで見ていきます。

  • 先頭要素を消費して、先頭要素を返す。
head :: IterV el (Maybe el)
head = Cont step
  where
    step (El el) = Done (Just el) Empty
    step Empty = Cont step
    step EOF = Done Nothing EOF
  • 先頭要素を消費せず先頭要素を返す。
peek :: IterV el (Maybe el)
peek = Cont step
  where
    step c@(El el) = Done (Just el) c
    step Empty = Cont step
    step EOF = Done Nothing EOF
  • 要素をn個消費する。
drop :: Int -> IterV el ()
drop 0 = Done () Empty
drop n = Cont step
  where
    step (El _) = drop (n-1)
    step Empty = Cont step
    step EOF = Done () EOF
  • 要素の数を数える。
length :: IterV el Int
length = Cont (step 0)
  where
    step acc (El _) = Cont (step (acc+1))
    step acc Empty = Cont (step acc)
    step acc EOF = Done acc EOF

合成

このようなiterateeの定義に対して、iterateeの合成を考えることができます。実際のところ、IterVはモナドであり、ApplicativeやFunctorにもできます。合成の意味は前の章で説明したとおりです。bindは1つめのiterateeを実行して、残りの入力列で2つめのiterateeを実行するiterateeを返します。

instance Monad (IterV el) where
  return x = Done x Empty
  m >>= f = case m of
    Done x str -> case f x of
      Done x' _ -> Done x' str
      Cont k -> k str
    Cont k -> Cont (\str -> k str >>= f)

instance Functor (IterV el) where
  fmap f (Done x str) = Done (f x) str
  fmap f (Cont k) = Cont (fmap f . k)

instance Applicative (IterV el) where
  pure x = Done x Empty
  (Done f str) <*> i2 = fmap f i2
  (Cont k) <*> i2 = Cont (\str -> k str <*> i2)

こうして我々はiterateeをHaskellの標準的な方法で合成できるようになりました。簡単な例を示します。drop1keep1は、入力を1文字捨てて、次の文字を返すiterateeです。alternatesは入力列を1つ置きに、先頭5つまで取り出すiterateeです。

drop1keep1 :: IterV el (Maybe el)
drop1keep1 = drop 1 >> head

alternates :: IterV el [el]
alternates = fmap catMaybes . sequence . replicate 5 $ drop1keep1

実行例:

*Main> let alts = enum alternates [1..10]
*Main> run alts
Just [2,4,6,8,10]
*Main> let alts2 = enum alternates [1..]
*Main> run alts2
Just [2,4,6,8,10]

モナドの導入

さて、ここまでiterateeを実装して来たわけですが、前の章の実装はpurelyな世界に閉じていて何もI/Oをしていません。I/Oをできるようにするため、enumeratorをモナドに対応させてやることにします。

type EnumeratorM el m a = IterV el a -> m (IterV el a)

enumHandle :: Handle -> EnumeratorM Char IO a
enumHandle h iter = loop iter
  where
    loop i@(Done _ _) = return i
    loop i@(Cont k) = do
      isEOF <- hIsEOF h
      if isEOF then return i else hGetChar h >>= loop . k . El

enumFile :: FilePath -> EnumeratorM Char IO a
enumFile fp i =
  bracket
    (openFile fp ReadMode)
    (hClose)
    (flip enumHandle i)

モナド対応版のenumeratorの型がEnumeratorMです。先程のenum関数と同じく、IterVを引数に取りIterVを返しますが、EnumeratorがI/Oをできるようにモナドに包まれています。

実際のenumeratorの例がenumHandleとenumFileです。それぞれハンドルとファイルの文字要素を列挙します。これらのenumeratorは次のような重要な安全性を持っています。

  • ハンドルがリークしない

Handleがiterateeに渡らないので、どこかにエスケープしてしまうことがない。bracketによって例外が起きても安心。

  • 完了後すぐにハンドルを閉じることができる

iterateeが遅延評価されないので、すぐに閉じることができます。

enumHandleがEOFをiterateeに送らないのは重要です。enumeratorがEOFを送らないことによって、enumeratorの連結が可能になります。EOFを送るのはrunの仕事になります。

2つのファイルの長さを計算する例:

lengthOfTwoFiles :: FilePath -> FilePath -> IO (Maybe Int)
lengthOfTwoFiles fp1 fp2 =
  fmap run $ ((enumFile fp1) >=> (enumFile fp2)) length

モナディックiteratee

I/Oのうち、入力はこれでできるようになりましたが、出力はどうでしょう。iterateeをモナドに対応させることによりこれは可能になります。しかしenumeratorより多少ややこしいです。

data IterVM el m a
  = DoneM a (StreamG el)
  | ContM (StreamG el -> Iteratee el m a)

newtype Iteratee el m a
  = Iteratee { runIter :: m (IterVM el m a) }

IterV が IterVMになって、Iteratee型が増えています。Iterateeが、モナド対応版iterateeで、IterVMは内部的な型です(IterVMのコンストラクタが2つあるのでIterateeの内部には書けない)。

モナド版のIterV(head, peek, drop, lengthなど)に対して、自動的にIterateeに変換する持ち上げ(lift)を定義することができます。

liftIter :: Monad m => IterV el a -> Iteratee el m a
liftIter (Done x str) = Iteratee . return $ DoneM x str
liftIter (Cont k) = Iteratee . return $ ContM (liftIter . k)

さらに、IterateeをMonadTransとMonadIOにしておくと便利です。

instance MonadTrans (Iteratee el) where
  lift m = Iteratee $ m >>= \x -> return (DoneM x Empty)

instance MonadIO m => MonadIO (Iteratee el m) where
  liftIO = lift . liftIO

モナディックiterateeの例をいくつか挙げておきます。

  • ストリームのデータをすべてファイルに書き込む
streamToFile :: FilePath -> Iteratee Char IO ()
streamToFile fp = Iteratee (openFile fp WriteMode >>= go)
  where
    go h = return $ ContM (step h)
    step h (El el) = Iteratee (hPutChar h el >> go h)
    step h Empty = Iteratee (go h)
    step h EOF = Iteratee (return $ DoneM () EOF)
  • 100文字ごとに読み込んだ文字数を表示する
throbber :: Iteratee el IO ()
throbber = Iteratee (cont $ step (100 :: Int) 99)
  where
    step acc 0 (El _) =
      Iteratee
        (printf "Read %d chars\n" acc >>
         cont (step (acc+100) 99))
    step acc cnt (El _) = Iteratee (cont $ step acc (cnt-1))
    step acc cnt Empty = Iteratee (cont $ step acc cnt)
    step _ _ EOF = Iteratee (return $ DoneM () EOF)
    cont = return . ContM

Iteratee自体もモナドですので、もちろんもっと高レベルな書き方もできます。

sequenceI_ :: [Iteratee el m a] -> Iteratee el m ()
-- 定義はエクササイズとして考えてみてね

throbber2 :: Iteratee el IO ()
throbber2 = sequenceI_ $ map i ([100,200..] :: [Int])
  where
    i n = liftIter (drop 100) >> lift (printf "Read %d elems\n" n)

複数のiterateeを1つのenumeratorで並列に評価するというコンビネータを考えます。

enumPair :: Iteratee el m a -> Iteratee el m b -> Iteratee el m (a, b)
enumPair i1 i2 = Iteratee step
 where
   step ... -- 実装は各自考えてみてね

streamToFile "hoge" `enumPair` throbber とすることにより、ファイル書き込みに簡単に進捗表示をつけることができるようになります。その他、時間のかかるような処理にプログレスバー表示を取り付けたりするのも簡単です。これは遅延I/Oでは(少なくとも低レベルの実装を隠したままでは)、できないことです。

ネストしたenumerator

head, drop, lengthといった、fold的な関数を見てきましたが、ではfilterやmapのような関数はどうでしょう?これらをうまく定義するために、"ネストしたenumerator"というものを導入します。これをenumerateeと呼びます。

enumerateeは、ストリーム変換子としての型を持ちます。

type EnumerateeM elOuter elInner m a =
  Iteratee elInner m a
  -> Iteratee elOuter m (Iteratee elInner m a)

以下では簡単のために非モナド版iterateeで考えます。

filter :: (el -> Bool) -> IterV el a -> IterV el (IterV el a)
filter pred i@(Done _ _) = return i
filter pred (Cont k) = Cont step
  where
    step e@(El el) | pred el = filter pred (k e)
    step EOF = Done (k EOF) EOF
    step _ = Cont step

mapIter :: (elOuter -> elInner)
           -> IterV elInner a
           -> IterV elOuter (IterV elInner a)
mapIter f i@(Done _ _) = return i
mapIter f (Cont k) = Cont step
  where
    step (El el) = mapIter f (k (El $ f el))
    step Empty = Cont step
    step EOF = Done (k EOF) EOF

outerストリームが元のstreamで、innerストリームがフィルタされたストリームになります。filterはまずpredicateを引数に取り、さらにもう一つ、フィルタされたinnerストリームを処理するためのiterateeを引数に取ります。mapIterも同様です。

enumerateeを簡単に作るためにヘルパ関数を定義します。

convStream :: Iteratee elOuter m [elInner]
              -> EnumerateeM elOuter elInner m a

outer要素をinner要素に変換するiterateeを引数に取り、enumerateeを構築します。これはmapIterと異なり、1対1の変換でなくても可能です。many-to-one, many-to-none, one-to-many、さらにはnone-to-manyの関係も有り得ます。これを利用すると、例えば、Word8のストリームからInt16のストリームに変換するenumerateeが定義できます。

その他の実装

ここまでiterateeの実装を一通り見てきましたが、実はiterateeの実装にはいろいろなものが提案されています。iteratee-0.2*10では上記実装とは少々異なったものになっています。

data IterVM el m a = DoneM a (StreamG el)
                   | ContM (Iteratee el m a)

newtype Iteratee el m a =
  Iteratee { runIter :: StreamG el -> m (IterVM el m a) }

この定義では、Iterateeは(入力を何も消費しない場合でも)少なくとも一つのデータを要求します。その他の点には違いはありません(これは何が嬉しいんだろう?)。

iteratee-0.4以降*11(未リリース?)ではRankNTypesを用いたCPSスタイルになっています。

newtype Iteratee el m a =
  Iteratee {
    runIter :: forall r.
      (a -> Stream el -> m r) ->
      ((Stream el -> Iteratee el m a) -> Maybe ErrMsg -> m r) ->
      m r
    }

CPSスタイルには、他の実装と異なり型が一つしかなくて関数なので、標準の合成演算子、>>=や(.)で合成できる、あるいは低レベルなiterateeの定義がシンプルになるなどのアドバンテージがあります。

パフォーマンス

iterateeのデザインゴールはLazy I/Oに匹敵するパフォーマンスが得られることでした。実際のところiterateeは速いのでしょうか?残念ながら上記の実装そのままではとても遅いです。それは主に文字の読み書きを1文字ずつやっていることが原因です。

その解決策として、StreamGを1文字保持するのではなく、データのチャンクを保持するように変更します。そうするとI/Oをより大きなバッファで行うことができるようになります。またそうすることによりEmptyコンストラクタを消すことができます。

データのチャンクを保持するバッファの選択がパフォーマンスに大きく影響を与えます。リストはHaskellにおいては一般的で自然な選択で、要素に対して多態でとても使いやすいのですが、パフォーマンスの点からはあまり良くありません。StrictなByteStringを用いると素晴らしいパフォーマンスが得られますが、一般性を損ないます。

そこでiterateeパッケージではポリモーフィックなコンテナを表現できるListLikeクラス*12を利用しています。これによって、一般性を欠くことなく適切なコンテナを選択できるようになっています。

まとめ

というわけでiterateeの概要を見てきました。この記事では基本的な部分しか説明できませんでしたが、実際のiterateeライブラリ*13をいじってみると理解が深まると思います。最近ではhackageDBに類似のライブラリ*14が登場したりしており、まだまだ発展途上のライブラリな感がありますが、将来的にはメインストリームになるんではないかなあと個人的には思っています。

[ICFP] ICFP Programming Contest 2010 参加記

pure pure code ++ というチームで参加していました。今回は問題がとても面白かったと思います。楽しめました。チームのメンバは http://twitter.com/nya3jp/status/16604202811 の6人。6人目のメンバーはトンちゃんでしょうか。
http://www.icfpcontest.org/2010/ コンテストのページはこちら。
http://icfpcontest.org/icfp10/score/teamAll 順位表はこちら。
上位5チームはリストには表示されないようです。pure pure code ++ は表示されていないので5位以内ということみたいです。上位5チームのの点数とチーム名が非表示なので自分のチームが一体何位なのか全くわからないのですが、それなりの手応えはあります。発表まで順位が分からないようにとのことなので、点数などの公表は控えておきます。

問題の詳細は、http://icfpcontest.org/2010/task/
mr_konnさんによる日本語訳 http://d.hatena.ne.jp/mr_konn/20100618/icfp2010task

大まかな内容は次のような感じです:

  • 車と燃料を作って期間内になるべくたくさん儲けよう
  • 車は一定時間ごとに利益を生む。車から生じた利益は燃料の供給元で(だいたい)山分けされる
  • 車のエンジンは行列の制約式として表され、それを満たす燃料(行列)を供給できる
  • つまり、なるべく他のチームに燃料を作られない車を作って、なるべく他のチームの車の互換燃料を作った人が勝ち


当時の様子を書いて行きます。

一日目

開始直前

京都からやって来るchunさんが乗り物酔いと闘いながらbitbucketのプライベートレポジトリなどを用意してくれる。私はhgの使い方を勉強するなど。普通にコミットする分には適当に何とかなりそう。とても緊張してくる。

21時

いよいよ開始。英語と格闘するが殆ど理解出来ない。やばい。チーム名がぴゅあぴゅあこーどに決まる。

23時頃

全く問題読みに貢献できないまま、大まかな解読が終わる。車と燃料を作るようだが、それぞれは詳細秘密の3進表記で表される。さらに燃料は3進表記そのままではなくて、それを生成する回路で送信する必要がある。それももちろん詳細は秘密ですって、なんぞそれ。リバースエンジニアリングゲーか。リバースエンジニアリングならまかせろー、って感じでもないが、とりあえず回路の仕様を頑張って調べる。

0時頃

とりあえず適当な回路を投げて反応を見てみる。うえーい、全然わからん。悶々としていると、phoenixさんが表埋められそうと言ってサクサクと表が埋まっていく。何が起こっているんだ。とりあえず私は並行して回路シミュレータを書く事にした。これも問題の仕様がよくわからず、どういう条件で信号が遅延するのか曖昧なまま書いていたが、なんとかなった。

1時頃

シミュレータが出来る頃、表も完成していた。シミュレータに入力を突っ込んで鍵を生成してみる。鍵はできたが合ってるかどうか全然わからない。入力をパススルーする回路がなんだか私には良く分からないが作られて、入力が得られる。それを元に検算、シミュレータのバグが取れて、正しい鍵が得られる。

4時頃

素子の挙動と出力すべきキーとサーバの入力(の先頭17文字)は分かったが、果たして如何にしてキーを出力するのか?入力から出力への簡単な回路があるか少し考えてみたが、さっぱり分からない。それも分からないが、本番の燃料投入では17文字以上出力しなければならない。それは即ち不明な入力に対してこちらの意図した列を出力しなければならないということ。入力に対してキーを出力する簡単な回路を見つけても意味がないことに気付く。入力非依存で指定した列を出力できる回路を生成できなければいけない。

5時頃

nyaさんとphoenixさんが謎の技法により定数回路などをさくさくと作り上げていく。若者の人間離れというのを目の当たりにする。私は他にできることがないので、それらを組み合わせてジェネレータを作ることに。Haskellで書かれたとってもぴゅあぴゅあグローバル変数を書き換えまくる)なコードが完成した。この時の回路はパススルー回路と定数加算回路を逆順でつないだだけの単純なもので、1tritあたり約16gateも消費するお粗末なものだった。しかし、結局最後までこれと大差のないコードが使われることになる。6時半ごろ、ついに最初の得点が入る。他の人は寝ていたようなので、一人で盛り上がる。すでに8チームほどがサブミットした後だっただろうか。ちょっと出遅れたと思った。

9時頃

phoenixさん邸へ移動。任意の列を送れるようになったので、まずは燃料を何とかしようということに。適当な列をひたすら投げまくる。システムのエラーメッセージがどう見てもParsecのエラーです。これはHaskellで書かれているな。どうやら3進コードの最初のところにタンク数が入っているらしいことが分かる。そして数のエンコード方法が大体分かってくる。燃料は3次元配列になっていると睨んでいろいろ突っ込んでみるが、これがなかなかうまくいかない。dimension errorとひたすら言われるが、車と燃料の仕組みを理解せずにやっていたので、そもそも何のdimensionなのか分からない。

昼過ぎ

相変わらず進展せず。ぼちぼち鍵車以外の車が解かれ始めて焦る。あまりにも解読が難航しすぎて眠い眠い。この頃サーバーの反応をWikiにまとめていたが、とても面倒だったので、nyaさんがサブミットして入力と結果を保存するコマンドラインツールとCGIを作り始める。これによってサブミット作業がとても楽になる。CGIは今後継続的に更新されていき、欲しい機能がいつの間にか実装される神インフラとなる。

15時頃

あまりにも眠かったので1時間ほどうとうとしていると、なんと車と燃料のフォーマットと整数のエンコードがすべて分かったという。そ、そんなバカな?yuizumiさんとphoenixさんが人間離れを起こしたらしい。どうやら解読が難航していたのは、リストの長さを表す整数と、行列の成分を表す整数のエンコードが異なっていたせいらしかった。車が読めるようになったので、いまさらになって車のお勉強をする。分かったような分からんような。1次元の2を突っ込むと解けてしまう車が幾つかあるというのが分かったのでサブミット。実は試行錯誤の最中にもなぜか解けている車があったが、ようやくちゃんと理解して送れた。

17時頃

問題の全貌がようやく理解できて、ICFPにはありがちな、遠い遠いスタートラインにようやく立てた。さて、問題が分かったが、これは非線形の整数計画問題なのか?答えが出せるのかこれは?私には全然分からないが、簡単に解けるならこんなの問題になるはずがないということは恐らく間違いない。chunさんが1次元の解をブルートフォースで見つけるプログラムを書いて、いくつかの車に対してトリビアルでない燃料を投入することができるようになった。

18時頃

もしかして:やることがない?何をやったらいいのか分からない。

19時頃

高次元に対応するにはブルートフォース以外の方法が必要だ。焼きなましとか。焼きなましならまかせろー、バリバリ。Marathon Matchで培った焼きなまし技術を今こそ活かすとき。

20時頃

焼きなましソルバ完成。しかし、全然解いてくれない。極稀に解ける車もあったが、これでは話にならない。焼きなましで上手くいく類の問題ではなかったのか。はたまたプログラムがバグっているのか。焼きなましを信じてこのままやっていいのか。

20時40分頃

一頻り弄って、やっぱり焼きなましでは無理でした。と報告した矢先にひどいバグが見つかる。[0-1)の乱数が欲しい場所でrand()と書いていた。なぜこれで解けていた問題があるのかは謎だ。ともかく、これを直すと結構な数の車を解けるようになった。方針は間違っていなかったのか。Lightning Division終わるまでしばしのサブミット祭り。

二日目

21時

Lightning Division終了。濃密な一日であった。この時点で5位に入っていたようだが、6位との間をふらふらしていたので、そんなに良い順位ではないだろう。ご飯を食べながら明日以降の作戦会議。一つはゴルフ。ゴルフは最大で収入が2倍近く変わる可能性があるのでおそらく重要だろうと言う事。もう一つは車の製造。gusさんが作っているそうなので、それを完成させてもらう方向で。最後にソルバの強化。ソルバは車の耐久試験にも使われることになるだろうから、車の強度にとっても重要。ご飯を食べて帰宅。眠すぎて電車の中で立っているのが辛かった。

0時

帰宅。回路ジェネレータに明らかな無駄があったので取り急ぎ修正。回路規模が半分ほどになって、おそよ1tritあたり8ゲート。眠気の限界に達する。

11時30分

再びphoenixさん宅へ。昼食後作業。まず私のすることはソルバの強化。焼きなましに用いるスコアとして、満たしている制約式の数を用いていたが、これは離散的過ぎるし、ひとつの制約式を満たすのが完全にランダムでしか見つけられないので良くない。それぞれの制約式が満たされている度をうまく0-1の値にすることにする。まず最初に、行列の要素のうち満たされているものの個数を入れることにした。とても単純だが、これだけでもかなり性能向上した。次に各要素がどれぐらい条件に反しているかを考慮するようにする。試行錯誤していろいろ式を試してみるが、この問題は行列を乗算するので係数は非常に大きくなる傾向にあって、故に、ずれている分のlogをとって、さらにそれを0-1に正規化することにした。

昼ごろ

車の量産体制が整ったようで、少しずつ車が出荷されていく。解かれないかどきどき。ソルバの自動化が行われ始める。ポンコツ車が結構な割合で出荷されてくるので、まず決め打ちのいくつかの行列を突っ込んでみて、次にブルートフォースを走らせて、ダメだったら焼きなましソルバを走らせるような感じ。

9時頃

20台ほどの車が出荷される。最初の方に出荷した数台以外は解かれていないようだ。良かった。私とchunさんはひたすらソルバの改良をする。それに加えて焼きなましが漏らす巨大整数を入力しないと解けないタイプの問題をみんなで各個撃破。このころにはかなりの車を解けるようになっており、相当の収入が得られるようになっていた。最盛期のぴゅあぴゅあこーど++:ご飯を食べている間に+100点なる発言がなされてから夕食に行ったら実際には+200点だったり、http://twitter.com/wata_orz/status/16615142451 を見てにやにやしたりするなどする。

三日目

0時頃

最終日に向けて私は泊り込みで作業。焼きなましソルバの性能がほぼ完成を迎え、ランダム生成系をほぼ全て廃車にできるようになり、残りの手動生成系を各個撃破した結果、2種類の車を残しほぼ解けるようになった。解けないものの1つは1日目の終了時点頃に投稿された3000番台〜4000番台の車で、一見普通のランダム生成に見えるが、他のとどこかが違うのか何故か解けない。右辺が左辺よりも大きいのでおそらく解の存在する領域がとても狭いのだと思うが、それにしても他の類似の車はさくさく解けるのでこれは大変な謎だった。もう一つが巨大整数を必要にしているように見えるが手計算では規則性のつかめない問題(45076番など)。同じタイプの車で番号が若くてサイズの小さい試作機のようなのがあったので、もしかしたらと思って焼きなましにかけてみると2x2行列の比較的小さい解が得られた。この解を元に式の意味をphoenixさんと考えていると、紆余曲折の末、これは巨大整数の素因数分解を要求していることがわかった。行列の積で任意の数をエンコードできるとか…。作るのは簡単だけど解くのは難しいのは:素因数分解というのはまあそうだけど、それを実際に制約式にエンコードして出荷してくるというのは脱帽だった。

4時頃

一応素因数分解はどこかで走らせることに。サイズとしては10^100程度で、これが初めて素因数分解されたのは1990年頃らしいが、果たしてそのころのスパコンに今のPCが追いついているのだろうか。サーバが重くなりすぎて結果が返ってくるのに2分ぐらいかかるようになる。この調子で最終日大丈夫なのかと心配。車のサイズが100文字までになったというtwitter上の噂。なんぞそれ。そんな仕様変更があったら今回一気にクソゲー化だ。そんなこんなでなるほど4時じゃねーのを見届けて寝る。

10時頃

寝ている間に新車カタログの仕様変更があって、車のスクレイプができなくなっていた模様。ひどい…。早速対応してもらうが、これでロスした点数は少なくないだろう。とりあえず夜のうちに増強されたのか、サーバはずいぶん軽くなった。車100文字制限も撤回された模様。車の出荷も再開。私は自動ソルバをくぐり抜けた車を焼いていく作業の繰り返し。車の投稿スピードが上がってきてだんだん辛くなってくる。素因数分解は結局無理っぽいので諦める。

12時頃

ご飯を食べながら。今朝から新しく提供されるようになった車リストに供給された燃料のサイズが乗っているらしく、それを見ると他のチームの燃料は相当小さいらしい。1文字1-2ゲートのチームもいる。これは結構まずいのではないか。やはりゴルフもやるべきか。

昼頃

CGIに2-5チームしか解いてない車のうち自分たちの解けた車の数を表示する機能がついた。それによると、2チームしか解いていない車の実に9割以上がうちが解いたものだということが判明した。にわかには信じがたい数であったが、リストをダウンロードしなおして眺めてみるに本当にそのようだ。それを元に収入を見積もると、200程度はあると出た。これは恐ろしい数だ。しかも2チームの車のうち約半数がうちの燃料の方がサイズが小さいらしい。これはどういう事か?つまりゴルフの必要性は少なくなったということだ。100チームの中でトップを取るのは2チームの中でトップをとるより遥かに難しいが、100チームの中でトップを取ることの意味は殆ど無い。そこを目指すよりsolved 1の車を解いていったほうが遥かに効率が良い。車の生産も終わり、全体の方針としては、後はひたすら出てくる新車をスクラップにしていくという事になる。

改めてリストを見ると、鍵生成は6ゲートでできるらしい。それと2のみの行列を出すコードは7ゲートでできるらしい。結構多くのチームがそれで提出している。これが分かったところで任意の列を生成することはできないだろうから得点にはほとんど影響がないが、7ゲートの方は割とたくさんの車に供給できるので、見つけたら収入が10点ぐらいは増えるかもしれない。たくさんの人がサブミットしてるなら簡単な回路かもしれないので、適当に考えてみるがよくわからず。yuizumiさんが全探索組んで6ゲートの回路が発見される。ちょっと嬉しい。しかし出てきた回路を見ても、意味はさっぱりわからない。7ゲートの回路は探索が終わらなくて見つからず。無念。

夕方頃

もはや車をひたすら潰すのみ。潰せども潰せども車はやってくる。終わりに近付いて新車の入荷するペースも加速度的に上がってくる。しかし思い出出荷のような簡単に解けるのががほとんどで、CGIをリロードするたびに数十という単位で車が減っていく。デフォルトパラメータの自動焼きなましソルバで生焼けになってしまった車を手動でじっくり焼きなます。ひたすら焼きなます。入荷する車は、ポンコツ、簡単に焼ける、硬いがパラメータをうまく選んでじっくり時間をかければ焼ける、手動で簡単に解ける、のおおよそ4種で、前者二つは自動的に消えて、手動が必要なものに対しては各個スペシャルソルバを作成し、硬いが焼けるものに関してはchunさんが膨大なコンピュータリソースにものを言わせて超並列で焼いていく。このころにはソルバのさらなる性能向上により3/4000番台の車も頑張れば焼けるにカテゴライズされていたので、これも超並列で頑張って、最終的には30台程度はスクラップにすることができた。それにしてもあんなに初期に出た割にはなんという硬い車だったのだろう。十分に役割を果たしたに違いない。

終了直前

全員総出でひたすら車を潰し続ける。無限プチプチにも似た楽しさがあったが、さすがに何時間もやり続けるとしんどい。8時頃、まだ1時間もあるのか、などの声も。それでもなんとか、できるだけの車を潰しきって時間終了。完走することができた。

反省・感想

とにかくとても楽しかった。問題がとても良かったと思う。前半のリバースエンジニアリング部分は蛇足にも見えるが、個人的にはそういうのも楽しめた。行列いじるだけではなんだかICFPという感じがしないような気もするし。参加者同士の問題の出し合いというのはICFPでは新しかったと思う。解けない車が出てきて、そのアイデアに驚嘆したり、さらにゴルフもあり、非常に盛りだくさんだった。独りでやっていたらやることが多すぎて相当厳しかったかもしれないが、そういう意味では、チームに恵まれて十分に楽しめたと思う。nyaさんの強力なインフラとgusさんの車製造のおかげで私は燃料製造に集中することができた。インフラと車がどうなってるのかは今でもよく分かっていない。今回良かったのはとにかくきちんと平行に作業が進んで、個々のタスクもほぼ間違った方向に行かなかった事だと思う。

後日談

http://icfp.gnumaniacs.org/2010/06/21/whats-this-thing-with-cars-and-fuels/

公式ブログに解説記事のようなものがアップされた。曰く、

  • 車は本当は "relative termination problem in string rewriting" と呼ばれる問題で
  • 燃料はそれを解く方法。"matrix interpretation"と呼ばれるもの
         ナ ゝ   ナ ゝ /    十_"    ー;=‐         |! |!
          cト    cト /^、_ノ  | 、.__ つ  (.__    ̄ ̄ ̄ ̄   ・ ・
ミミ:::;,!      u       `゙"~´   ヾ彡::l/VvVw、 ,yvヾNヽ  ゞヾ  ,. ,. ,. 、、ヾゝヽr=ヾ
ミ::::;/   ゙̄`ー-.、     u  ;,,;   j   ヾk'! ' l / 'レ ^ヽヘ\   ,r゙ゞ゙-"、ノ / l! !ヽ 、、 |
ミ/    J   ゙`ー、   " ;, ;;; ,;; ゙  u ヾi    ,,./ , ,、ヾヾ   | '-- 、..,,ヽ  j  ! | Nヾ|
'"       _,,.. -─ゝ.、   ;, " ;;   _,,..._ゞイ__//〃 i.! ilヾゞヽ  | 、  .r. ヾ-、;;ノ,.:-一'"i
  j    /   ,.- 、  ヾヽ、 ;; ;; _,-<  //_,,\' "' !| :l ゙i !_,,ヽ.l `ー─--  エィ' (. 7 /
      :    ' ・丿   ̄≠Ξイ´,-、 ヽ /イ´ r. `ー-'メ ,.-´、  i     u  ヾ``ー' イ
       \_    _,,......::   ´゙i、 `¨ / i ヽ.__,,... '  u ゙l´.i・j.冫,イ゙l  / ``-、..- ノ :u l
   u      ̄ ̄  彡"   、ヾ ̄``ミ::.l  u   j  i、`ー' .i / /、._    `'y   /
              u      `ヽ  ゙:l   ,.::- 、,, ,. ノ ゙ u ! /_   ̄ ー/ u /
           _,,..,,_    ,.ィ、  /   |  /__   ``- 、_    l l  ``ーt、_ /  /
  ゙   u  ,./´ "  ``- 、_J r'´  u 丿 .l,... `ー一''/   ノ  ト 、,,_____ ゙/ /
        ./__        ー7    /、 l   '゙ ヽ/  ,. '"  \`ー--- ",.::く、
       /;;;''"  ̄ ̄ ───/  ゙  ,::'  \ヾニ==='"/ `- 、   ゙ー┬ '´ / \..,,__
、      .i:⌒`─-、_,....    l   /     `ー┬一'      ヽ    :l  /  , ' `ソヽ
ヾヽ     l      `  `ヽ、 l  ./  ヽ      l         )  ,; /   ,'    '^i 

…て、知らんがな。どうやら我々は分からぬうちになんだか与り知らない問題に挑戦させられていたようです。で、このコンテストによって

  • 互換 matrix interpretations を見つける新しいアイデア
  • 新しいhard termination problem

が作られるはずだったと。

  • 実際に、これらの両方で成功したと考えている

まじかー。うちはひたすら焼きなましただけだけどな。

さて如何様にして、参加者と主催者は科学の発展に貢献しようとしたのか?

  • good fuel producerなコンテストチームは、来る [termination competition] の "relative termination of string rewriting" 部門に、そのソルバーをエントリーすることが促される。

まあぶっちゃけどうなんでしょう。こんな急造のものが戦えるんでしょうか。good fuel producer なのはおそらく確かなんですけど。

  • 運営は難しい車を、来る termination competition のベンチマークとしてサブミットしていた

そのへんのテストは通過していたわけですか。

なんか大層な話になってきましたな。

もしあなたがパズル好きなら:

  • Car { chambers = [ Chamber { upper = [0,1], mode= Main, lower = [1,0] } ] } に供給できる燃料が存在しないことを証明できるか?

難しいですね。

  • コンテストの各車が linear derivational complexity を持つことを証明できるか?

linear derivational complexity ってなんだろう。

まとめ

俺達はようやくのぼりはじめたばかりだからな このはてしなく遠い relative termination of string rewriting 坂をよ…

未完

第五回チームラボ天下一武道会

第五回チームラボ天下一武道会 : ATND

第五回チームラボ天下一武道会で優勝しました。

第三回に続いて二回目です(第四回も参加していましたが、あまりに成績が悪かったので、参加記書くの忘れてました…)。

問題

http://tam-lab.sakura.ne.jp/tenkaichi/

マルチプレイヤー数当てゲームのような感じでした。サーバがある数を保持しているので、その数を当てる。外れていた場合、大きすぎたのか小さすぎたのかが帰ってくる。正解した場合、スコアが1加算され、サーバが保持している数が1増える。ただし、サーバがレスポンスを返すのはリクエストしてから1秒後。さらに同時に張れるコネクションは2つまでという制限がありました。

当日の様子

バトルロワイヤルということで、問題解説中もすでにバトルは始まっています。すでに手動参加してる人が居るってことで、なかなか熱い感じでした。問題聴きながら手動で二分探索してみたら確かに50ぐらいまで既に増えているようでした。手で適当にクエリを投げながらどうするか考えて、とりあえず数当てゲームだったら二分探索じゃないかということで実装を始めました。

プログラムはHaskellで書きました。クエリはHTTPで投げるので、httpライブラリを使いました。適当にクエリを投げてみるところ、かなりの割合で503が出ました。その時はどうしてかわからず、そのまま進めていましたが、やはりどうしても効率が悪いのでちゃんと調べてみたら、どうやらhttpライブラリのシンプルAPIがコネクションをcloseしないらしい。手動でコネクションを用意するAPIを使うと、ようやくちゃんと動くようになりました。最初のほうあまりスコアが取れてませんでしたが、それで徐々にスコアが上がってきました。

二分探索で数を当てていたのですが、サーバの数字はリアルタイムでカウントアップしていくので、上限と下限の数をアドホックに少しずつ上昇させていくようにしていました。それでしばらくやっていたのですが、よく考えると、そうなってくると二分探索でやる意味がほとんどない。一回正解したらその一秒後に再度クエリを投げられるので、一秒間に他の人たちが正解を当てる回数程度インクリメントして送りつければいい。見た感じでは大体秒速3-4ほどだったので、それをハードコーディングして適当にインクリメントするだけのものに変更しました。

こうなってくると結局、問題は一秒間に他の人たちがどれぐらい正解するかというのをどれだけ精度よく予測するかというところに帰着されます。最初のほうは手で入れていましたが、周りのプログラムの精度がよくなってくるにつれてカウントアップも早くなるので、それに追従するためにちゃんと履歴から計算することにしました。

今回の問題の難しいのは、プログラムを改良している最中にも他の人のスコアはどんどん増えていくというところです。プログラムを動かさないと自分のスコアは伸びませんから、なるべく停止時間を短くしなければなりません。また、改良によって精度が下がるとトータルではかなり損をしてしまうので、プログラムを書き換えるのにかなり勇気が要ります。私は、コネクションが二つ張れるというのを利用して、常時二つプログラムを走らせるという戦略をとりました。ひとつのコネクションでそこそこ精度がいいプログラムをずっと走らせ、もうひとつでいろいろ実験して改良しているプログラムを走らせませます。改良の結果精度がそれなりに向上したら、ずっと走らせている方も切り替えます。こういうコネクションが二つというのを生かした開発が出来るのは面白かったと思います。他にも二つのコネクションを強調させながら効率をよくする戦略なども考えられますし、なかなか面白い制限だったと思います。

残り1時間ぐらいになった時、いろいろな地味な改良が実を結んだのか一位になりました。残り30分になるとスコアボードが隠され、さらにレスポンスタイムが半分になるとのことでした。残り30分の時点で2位との差が150ほどあったのですが、トータルの得点からすると5%ほどの差だったので、少し精度が悪いと十分逆転されそうでした。レスポンスタイムが半分になることを考慮して、プログラムを改良すべきかどうかなかなか難しいところでしたが、何もしないで負けたら悲しいので結局最後まで改良し続けました。予測する式を微妙にいじったりいろいろしていましたが、結局あまり精度は変わりませんでした。おそらくプログラムを止めていた分だけスコアは悪くなったと思います。

さてそれで、どきどきしながら結果発表を迎えたのですが、割といい感じのスコアで勝っていました。2位と3位のプログラムは次の数の予測を決めうちの数でやっていたそうですが、レスポンスタイムが変わってから周りの正答率が若干下がったような感じだったので、履歴を用いて予測していた私のプログラムがうまく動いたのかなと思います。

感想

また優勝できて嬉しいです。今回はヘリコプターをもらいました。ありがとうございました。今回の課題は個人的にはかなり楽しめました。いろいろ要素は考えられますが、次のような感じでしょうか。

  • 問題が十分にシンプル
  • 環境構築が容易(前回はHTTPサーバを立てる必要があったので)
  • スコアボードがあった
  • ラスト見えなくなって、それなりの緊張感

次回も近々あるそうなので、また参加させてもらえればと思います。面白いのを考えるのも大変かと思いますが、期待しております。

ファミコンエミュレータ for Java

http://d.hatena.ne.jp/tanakh/20050506#p2

のあたりで開発したファミコンエミュレータJavaに移植しました。

ここで公開中
http://github.com/tanakh/bjne-java

jarもあります。
http://github.com/tanakh/bjne-java/downloads

オリジナルのC++版。
http://github.com/tanakh/bjne

セーブ機能意外はすべて移植しました。
マッパは#0〜4と、VRC6を実装しました。VRC6は趣味です。
割と動いてるんじゃないかなあと思います。

なぜJava?

Androidで動かすためです。今のところは普通のAWTアプリです。

Javaで辛かったこと

  • 符号なし整数型がない。

メモリは基本的にbyteの配列で持つことになりますが、そこから取り出すときに気をつけないと負の数になってしまったり、レジスタをbyteなどで持ちますがこれも気をつけないと負の数になったり、アドレスが16ビットだけど、これも気をつけなければ負の数になったりとか、とかく短い長さの符号なし整数を多用するエミュレータではしんどいです。気を付ける箇所が無数にあるのに、コンパイラは何も言ってくれないので、とても怖いです。

CPUのエミュレーション部分など、似たような箇所が多いので、C++版ではマクロでまとめていたところがあまりうまく書けなかった。

  • プリミティブ型の参照がない

書き換える変数をパラメータ化できない。load(regHoge, addr)とかみたいなのができないので、loadHoge(addr)とかをレジスタごとに作ったり…。

どうしたものか。

Javaで良かったこと

C++でもVCを使えばいいという話ですが。LinuxでVCが使いたい…。

メモリアクセスのバグがすぐ見つかるので、かなり楽。安心感もあって良いです。必ずスタックトレースが出るし、Eclipseだとクリック一発でコードの当該箇所に飛べるので便利。

  • GUI作りやすい

思ったよりはるかに楽だった。クロージャがあればもっと楽なのに。

手動でミキサー書くのがびっくりするほど楽でびっくりした。

Haskellでメモ化を行うもう一つの方法

はじめに

Haskell で動的計画法を書くための3つの方針 - tosの日記

これを読んで、私もちょっと前にHaskellでメモ化をやる方法を考えていたことを思い出したので、書いてみることにします。

Haskellでのメモ化は、私のかなり昔の駄文(リアルにびっくりするほど駄文なのでご注意。メモ化の綴りも間違ってます)や、このあたりに日本語の文章があります。

これらのページでのメモ化実現方針は、1. 計算済み値を保持するテーブルをMapなどを用いて用意する 2. そのテーブルを副作用を用いて更新する、というものになっています。なるほど、これは手続き型言語との対比でとても直接的な実装です。しかし、テーブルを更新するために関数全体がモナドになってしまったりして、あまり使い勝手が良くなさそうです。モナドであることを悟らせないために、演算子モナド化したり、あるいはモナドじゃなくするためにunsafePerformIOを使うなどのトリックも考えられますが、どちらもあまり綺麗には見えません。

メモ化においてやりたい事は、テーブルの作成でもテーブルの更新でも無くて、一回計算した値がもう一度計算されないようになっているということです。一度計算したものがもう一度計算されない―――おあつらえ向きの物がHaskellにはあります。そう、遅延評価です。

基本的な考え方

簡単のために、メモ化関数の引数は1つの自然数とします(この制約は後である程度ゆるくします)。無限のサイズのテーブルがあると考えます。そこに、その関数(fとしましょう)のすべての引数に対する値が格納されています。0番目の所にはf 0、1番目のところにはf 1、…というふうにすべて入っています。遅延評価を用いて、各々の値は参照されるまで計算されないようにします。f n を計算したければ、そのテーブルをルックアップするだけです。そのノードが参照されるのが初めてならその時点でf nが計算され、二回目以降ならすでに計算された値が返されます。問題は、そのテーブルをどうやって表現するかです。効率的にルックアップ出来なければいけませんし、計算されていないノードは存在しないようにしなりません。

無限リストからの類推で、無限ツリーというものを考えます。無限ツリーはノードが無限にあるツリーです。ここではリーフはないとします。つまり、ノードはすべて内部ノードで、子を持っています。その特殊な場合として、無限完全二分木を考えます。すべてのノードが2つの子をもち、無限に広がっているような木です。これにヒープよろしく、ルートには0を、その子には1と2、さらにその子には3と4と5と6…というように番号をふります。そして、その対応する番号を引数とする関数の値をノードに持たせます。これは完全にバランスした二分木なので、O(log n)でルックアップできます。

         0
    1         2
  3   4     5     6
 7 8 9 10 11 12 13 14
...

実装

メモ化のインターフェースは、fixと同じものを採用します(fixというのは、ここではControl.Monad.fixを指しています。これは一般には"不動点演算子"と呼ばれるものです。不動点演算子に関しては、私のブログの駄文や、Googleに聞いてみてください)。fixをこれから実装するmemofixに挿げ替えるだけで関数がメモ化されるという目論見です。利用例は次の様になります。

-- normal version
fib = fix $ \f n -> if n<2 then n else f (n-1) + f (n-2)
-- memoised version
memofib = memofix $ \f n -> if n<2 then n else f (n-1) + f (n-2)

まずは無限完全二分木を定義します。これはリーフを考えなくていいので、とても簡単です。

data Tree a = Tree a (Tree a) (Tree a)

次に、このツリーのルックアップを定義します。添字の上位ビットからみて、ツリーを辿っていくだけです。

findTree :: Tree b -> Integer -> b
findTree tree ix = f (bits $ ix + 1) tree
  where
    f []     (Tree v _ _) = v
    f (0:bs) (Tree _ l _) = f bs l
    f (_:bs) (Tree _ _ r) = f bs r

    bits = tail . reverse . map (`mod`2). takeWhile (>0) . iterate (`div`2)

次に、関数の値がすべて詰まった無限ツリーの生成です。ノードの値を計算するための関数を渡してもらって、適当に全部生成するだけです。遅延評価がすべて何とかしてくれます。

genTree :: (Integer -> b) -> Tree b
genTree f = gen 0 where
  gen ix = Tree (f ix) (gen $ ix*2+1) (gen $ ix*2+2)

さて、あとはメモ化コードを書くだけです。これもとてもシンプルです。

memofix :: ((Integer -> b) -> (Integer -> b)) -> (Integer -> b)
memofix f = memof where
  memof = f $ findTree tbl
  tbl = genTree memof

memofがメモ化versionのfで、tblがすべての答えの詰まった無限ツリーです。tblは先程のgenTreeにmemofを渡してやれば出来上がりで、memofはfにtblをルックアップする関数を渡してやればいいのです。簡単でしょ?

memofib = memofix $ \f n -> if n<2 then n else f (n-1) + f (n-2)
main = print $ map memofib [(0 :: Integer)..100]

実行してみます。

$ ghc --make Main.hs && time ./Main 
[1 of 1] Compiling Main             ( Main.hs, Main.o )
Linking Main ...
[0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368,75025,121393,196418,317811,514229,832040,1346269,2178309,3524578,5702887,9227465,14930352,24157817,39088169,63245986,102334155,165580141,267914296,433494437,701408733,1134903170,1836311903,2971215073,4807526976,7778742049,12586269025,20365011074,32951280099,53316291173,86267571272,139583862445,225851433717,365435296162,591286729879,956722026041,1548008755920,2504730781961,4052739537881,6557470319842,10610209857723,17167680177565,27777890035288,44945570212853,72723460248141,117669030460994,190392490709135,308061521170129,498454011879264,806515533049393,1304969544928657,2111485077978050,3416454622906707,5527939700884757,8944394323791464,14472334024676221,23416728348467685,37889062373143906,61305790721611591,99194853094755497,160500643816367088,259695496911122585,420196140727489673,679891637638612258,1100087778366101931,1779979416004714189,2880067194370816120,4660046610375530309,7540113804746346429,12200160415121876738,19740274219868223167,31940434634990099905,51680708854858323072,83621143489848422977,135301852344706746049,218922995834555169026,354224848179261915075]

real	0m0.012s
user	0m0.010s
sys	0m0.000s

動きました。メモ化しないと、

fib = fix $ \f n -> if n<2 then n else f (n-1) + f (n-2)
main = print $ map fib [(0 :: Integer)..100]
$ ghc --make Main.hs && time ./Main 
[1 of 1] Compiling Main             ( Main.hs, Main.o )
Linking Main ...
^C

帰って来ず。

添字の一般化

添字が自然数1つというのは嬉しくありません。自然数以外や二つ以上の引数を扱うことを考えます。無限完全二分木以外のデータ構造を考えるのが面倒なので、任意の引数を自然数に変換することを考えます。つまり、当該データ型のすべてのデータに番号を振ってやって、その番号によってツリーをルックアップするのです。もちろんこれはその型が可算無限集合でなければいけないのですが、可算無限でない引数をメモ化の引数にするのはここでは考えないことにします。複数の引数はそのまま扱うのはとても難しいので、タプルにするということで妥協します。

自然数に変換できるというクラスMemoIxを定義します。逆変換も後で必要になるので用意しておきます。

class MemoIx a where
  index   :: a -> Integer
  unindex :: Integer -> a

ところで、Haskellの標準ライブラリにIxというクラスがあります。MemoIxと同様に値に対して整数を振るためのクラスですが、これを利用するには値の上限・下限が必要になります。遅延評価でせっかく無限のものを扱えるようになったのに、値の上限・下限を要求されるのは大変イケてないので、これをそのまま使うことは出来ませんでした。

具体的な型に対するインスタンスを書きます。まずはIntegerです。Integerは整数であって自然数ではないので、自然数に変換してやる必要があります。正の数を偶数に、負の数を奇数にエンコードすることにします。

instance MemoIx Integer where
  index n | n>=0 = n*2
          | otherwise = -n*2-1

  unindex n | n`mod`2==0 = n`div`2
            | otherwise = -((n+1)`div`2)

次にタプルを考えます。タプルはペアで表現できるので、ペアのみを考えます。ペアにうまく番号を振るには、次のように斜めに振ってやれば良いです(方法は他にも色々考えられます)。

 | 0 1 2 3 ...
-+-----------
0| 0 2 5 9 ...
1| 1 4 8 ...
2| 3 7 ...
3| 6 ...
.| ...

この番号を頑張って計算します。unindexで二次方程式浮動小数を用いて解いているのですが、これのせいでIntegerのメリットが失われているのがあまり良くないです(何とかならないでしょうか)。

instance (MemoIx a, MemoIx b) => MemoIx (a, b) where
  index (a, b) = l*(l+1)`div`2 + ib
    where
      ia = index a 
      ib = index b
      l  = ia+ib

  unindex ix = (unindex ia, unindex ib)
    where
      l  = floor ((-1 + sqrt (1 + 8 * fromIntegral ix))/2)
      ib = ix - l*(l+1)`div`2
      ia = l-ib

ところでこのコードは自然数への変換の際にかなり数が大きくなります。これは大丈夫なのでしょうか?入力a, bに対して、出力の大きさはO(ab)程度です。ということは、これをルックアップするのはO(log(max(a, b)))程度ということになります。なので、大丈夫そうです。

文字列型など他の型のMemoIxのインスタンスも考えられますが、それぞれ皆様各自お考え下さいませ。

さて、後はツリーとメモ化コードをMemoIxに対応させれば完成です。

findTree :: MemoIx a => Tree b -> a -> b
findTree tree ix = f (bits $ index ix + 1) tree
  where
    f []     (Tree v _ _) = v
    f (0:bs) (Tree _ l _) = f bs l
    f (_:bs) (Tree _ _ r) = f bs r

    bits = tail . reverse . map (`mod`2). takeWhile (>0) . iterate (`div`2)

genTree :: MemoIx a => (a -> b) -> Tree b
genTree f = gen 0 where
  gen ix = Tree (f $ unindex ix) (gen $ ix*2+1) (gen $ ix*2+2)

memofix :: MemoIx a => ((a -> b) -> (a -> b)) -> (a -> b)
memofix f = memof where
  memof = f $ findTree tbl
  tbl = genTree memof

適当な関数を書いてみます。

comb :: (Integer, Integer) -> Integer
comb = memofix $ \f (i, j) -> if i==1||j==1 then 1 else f (i-1, j) + f (i, j-1)

main = print $ comb (100,50)

実行してみます。

$ ghc --make Main.hs -O2 && time ./Main 
[1 of 1] Compiling Main             ( Main.hs, Main.o )
Linking Main ...
4503056131931081050165600532646379362000

real	0m0.082s
user	0m0.070s
sys	0m0.010s

正しく動作しました。

インターフェースのバリエーション

fixのインターフェースではなくて、次のようなものも考えられます。テーブルを作ってルックアップする関数を返すだけのシンプルなものです。

memo :: MemoIx a => (a -> b) -> (a -> b)
memo f = findTree (genTree f)

これを用いてfibを定義するとこうなります。

fib :: Integer -> Integer
fib = memo $ \n -> if n<2 then n else fib (n-1) + fib (n-2)

fixのインターフェースよりもこちらの方が書きやすいかもしれません。

ソースコード

全体のソースコードを再掲しておきます。

class MemoIx a where
  index :: a -> Integer
  unindex :: Integer -> a

instance MemoIx Integer where
  index n | n>=0 = n*2
          | otherwise = -n*2-1

  unindex n | n`mod`2==0 = n`div`2
            | otherwise = -((n+1)`div`2)

instance (MemoIx a, MemoIx b) => MemoIx (a, b) where
  index (a, b) = l*(l+1)`div`2 + ib
    where
      ia = index a 
      ib = index b
      l  = ia+ib

  unindex ix = (unindex ia, unindex ib)
    where
      l  = floor ((-1 + sqrt (1 + 8 * fromIntegral ix))/2)
      ib = ix - l*(l+1)`div`2
      ia = l-ib

data Tree a = Tree a (Tree a) (Tree a)

findTree :: MemoIx a => Tree b -> a -> b
findTree tree ix = f (bits $ index ix + 1) tree
  where
    f []     (Tree v _ _) = v
    f (0:bs) (Tree _ l _) = f bs l
    f (_:bs) (Tree _ _ r) = f bs r

    bits = tail . reverse . map (`mod`2). takeWhile (>0) . iterate (`div`2)

genTree :: MemoIx a => (a -> b) -> Tree b
genTree f = gen 0 where
  gen ix = Tree (f $ unindex ix) (gen $ ix*2+1) (gen $ ix*2+2)

memofix :: MemoIx a => ((a -> b) -> (a -> b)) -> (a -> b)
memofix f = memof where
  memof = f $ findTree tbl
  tbl = genTree memof

memo :: MemoIx a => (a -> b) -> (a -> b)
memo f = findTree (genTree f)

とかいうことを

嬉々として書いていたら、
http://www.haskell.org/haskellwiki/Memoization
こんなのがあったのですよ…。ぶわっ。
こっちのほうがツリーのエンコード方法が上手いので、後でコード書きなおします。

という夢を見ました

エイプリルフールなので、普段できない、関数型言語を貶しまくるというのをやってみましたが、思った以上に普通になりました。嘘をつくのは自分の心だけにして、それ以外はなるべく説得力のある文章を心掛けましたが、いかがでしたでしょうか。なんだ、分かってるんじゃないか、というご意見も頂きました。ちなみに、嘘でも、Haskellが嫌いだとか嫌になったとかとは書けませんでした。

先日のスライドが、関数型の都合の悪いところを無視して良く見えるところだけ書いていたのに対して、関数型のいいところを全く無視して、いかにも駄目そうに書いてみたのが昨日のです。つまりこれらは表裏一体で、二つ揃って初めて世界の均衡が取れるという訳です(ほんとかよ)。

そういう訳で、私は本当に関数型言語に見切りをつけたわけではないので、悪しからず。今後ともより一層のご愛顧を賜りますよう、よろしくお願いいたします。

手続き型に改宗しました

つい先日にあのような資料をアップロードして心苦しいのですが、手続き型に改宗することにしました。誰よりも関数型言語を愛し、常日頃よりどうして関数型が流行らないのかを考え続けていた私ですが、10年余りを経てようやく気付きました。関数型がイケてないから流行らないのだと。

関数型の人たちは言います。immutableこそ正義であると。でもそうなんでしょうか?変数に代入できる方が書きやすいに決まっています。書きにくいと思いつつも、Haskellというのは曰く、素晴らしい言語なのだから、そんなことはないはずだと自分をごまかしごまかしこれまで生きてきましたが、そうじゃないんです。ようやく目が覚めました。変数に代入できる方が書きやすいのは当たり前なんです。

モナドなんてへんてこなものを当たり前のように持ち出さなければならない時点でおかしいことに気付くべきでした。なぜ私はコンソールから文字を入力したいだけなのに、そんな妙な数学の匂いのするものを利用しなければならないのでしょうか。うまく使えば便利だという話はそれはそれで尤もですが、殆どの場合にそんなものは必要ないでしょう。他の言語を見てご覧なさい。どれも困った様子はないでしょう?

型も良くないです。型があれば実行時にバグに悩まされないなどと仰いますが、結局のところ配列の添字がおかしいとか、パターンマッチ漏れとかはわからないんです。コンパイルが通ってそれがそのまま動作するなんて、ほとんど幻想です。それなのに、コンパイルの通りは著しく悪くなります。コンパイル通すだけで一苦労です。私なんて、コンパイルが通らなくてプログラムを完成させるのを諦めたこともしばしばです。それならいっそ、バグっててもいいから動いて欲しいと思います。

高階関数も良くないんです。人間というのは、あまり複雑なものを扱えるように出来ていません。関数の時点で難しいんです。それなのに、関数に関数を渡すとか、難しすぎるんです。さらにそれが許されると、関数を渡す関数を渡す関数なども考えなければならなくなります。とても人間の制御出来る範囲を超えています。関数がファーストクラスじゃないというのは、考えてみれば、人間の能力の限界にフィットしたとても現実的な制約だったんです。ループを再帰で表すというのもありますが、無茶もいいところです。再帰というのは難しいんです。私の周りでも、再帰が分からずに躓く人を大勢見てきました。どうしてfor文で簡単に扱えるものを再帰で書かなければならないんでしょう。人は制御の流れをイメージするのは得意だけど、再帰的なものをイメージするのは苦手なのです。

冷静になって考えてみれば、とてもシンプルな理由でした。「関数型は書きにくい」。初めて関数型に触ったときは今まで自分がやってきたプログラムとは全く違っていて、それはそれは素晴らしいものに見えました。でもそれはプログラマが罹るはしかのようなものだったのです。10年もの間熱に浮かされていましたが、ようやく目が覚めました。現実が見えてきました。私は手続き型に改宗します。

ついでに言いますと、オブジェクト指向もいらないです。純粋手続き型(?)でいいのです。オブジェクト指向コンポーネント再利用できて生産性向上、というのが典型的なオブジェクト指向プログラマの言い分ですが、皆さん、クラスを作ってそれが他のプロジェクトで再利用できたためしなんてあるでしょうか?

デザインパターンなどというものもありますが、あれも必要ないです。ご存じの方はご理解いただけるかと思いますが、あれはとてもややこしいものです。やろうとしていることはどれもとても単純なことのはずなのに、クラス階層図は目を背けたくなるほどの複雑さです。そんな仰々しく天下り的なものを受け入れなければならない時点で、何かがおかしいと気付くべきです。

そうです。世の中にはC言語があればそれで十分なのでした。Cのプログラムやライブラリを見てみなさい。どれも何の過不足もなくうまく廻っているではありませんか。なぜ関数型などを持ち出す必要がありましょうか!そういうことなんです、関数型が一向に流行らないのは。こんな簡単なことに私もようやく気づきました。

これからはこのページは純粋手続き型雑記帳としてやっていこうと思います。以前の内容は、とてもお見苦しいものではありますが、若気の至りということで残しておくことにします。落胆された方も中にはおられるかと思いますが、必ずご理解いただけるものだと思っております。これからも変わらぬご愛顧をよろしくお願いいたします。