Haskellのエラー処理とMonadCatchIOの落とし穴

(この記事はHaskell Advent Calendar jp 2010のために書かれました)

Haskellではエラー処理に例外が用いられます(MaybeモナドやErrorモナドも用いられますが、ここでは例外に焦点をあてます)。

例外インターフェースの話

Haskellにも、例外を扱うためにtry, catch, finallyなどが用意されています。他の多くの言語ではこれらは構文として用意されますが、HaskellではIOモナドを引数にとる関数になっています。

try :: Exception e => IO a -> IO (Either e a)
catch :: Exception e => IO a -> (e -> IO a) -> IO a
finally :: IO a -> IO b -> IO a

tryはIOアクションを引数にとり、それを実行した結果が正常に値を返したか、はたまた例外かを返します。catchは例外が起こった場合の処理を記述できます。finallyは例外が起こっても起こらなくても第2引数のアクションを実行します。

これら(ともっと他にある例外処理用関数)を組み合わせてHaskellではエラー処理を行います。ひときわ良くあるケースとして、リソースの獲得、リソースの使用、リソースの解放の一連のパターンがあります。たとえば、ファイルをオープンして、ファイルにアクセスして、用事が済んだらファイルをクローズする処理を考えてみます。

main = do
  h <- openFile "hoge" ReadMode
  ... ファイルにアクセス
  hClose h

ファイルのオープンとクローズが別々になっているので、クローズを忘れるということがあるかもしれません。これを抽象化してみます。

main = do
  withFile "hoge" ReadMode $ \h ->
    ... ファイルにアクセス

withFile filename mode m = do
  h <- openFile filename mode
  m h
  hClose h

これでwithFileを用いている限りは、ファイルのcloseし忘れということに煩わされる心配はなくなりました。ところが、この実装は不完全です。ファイルにアクセスする部分のコードが例外を発生させた場合、withFileの最後の行、hCloseが実行されずに終わってしまいます。そのため、正しく例外を処理するコードが必要になります。

withFile filename mode m = do
  h <- openFile filename mode
  m h `finally` hClose h

これで正しいコードができました。この様なリソースの確保、リソースの解法を例外安全に行う処理というのは至る所で必要になってくるので、bracketという便利な関数が用意されています。

bracket :: IO a -> (a -> IO b) -> (a -> IO c) -> IO c

第一引数がリソース獲得関数で、第2引数がリソース解法関数で、第3引数がリソースを使用する関数です。リソース解法関数は、例外が起こった場合も正しく実行されます。これを用いると、withFileは次のようにかけます。

withFile filename mode m =
  bracket (openFile filename mode)
          hClose
          m

MonadCatchIO

このようにしてHaskellでエラー処理を記述することができますが、一つ大きな問題点があります。それは、これらの関数がすべてIOモナドを用いたインターフェースになっていることです。Haskellで例外が発生するのはIOモナドだけではありません。一つはpureなコードから発生する場合ともう一つはIOをリフトしたモナドから発生する場合です。pureなコードから発生する場合は、evaluate :: a -> IO a という関数を介することにより、IOモナド経由で例外を処理することができます。後者はたとえば変換子版のモナドを用いている場合に頻発します。近年の多くのモナディックなライブラリでは変換子版が用意されていることが多く、liftIOを用いてどこでもIOができるようになっています。liftIOによってIOをリフトできるモナドはMonadIOクラスとして抽象化されています。

MonadIOに対して例外処理を追加し、例外処理を一般化したものがMonadCatchIOクラスです。Hackage上の、MonadCatchIO-mtlや、MonadCatch-transformersのいずれかで利用できます。これを用いると、IOモナドをリフトできるIOモナド以外のモナド(たとえば StateT Int IO など)に対してtry, catch, bracketなどができるようになります。

foo :: MonadCatchIO m => m ()
foo = bracket (putStrLn "begin")
              (\_ -> putStrLn "end")
              (\_ -> ... 凝った処理 ... )

エラーモナドに対するインスタンス

ところがこれには大きな罠が潜んでいます。MonadCatchIO-transformersのドキュメントにWarningとして記載されていますが、ここでそれを解説しておきたいと思います。

(MonadCatchIO m, Error e) => MonadCatchIO (ErrorT e m)

問題となっているMonadCatchIOのインスタンスはこれです。どうしてこれがいけないのかというと、このモナドには2つのエラー通知方法があります。一つはMonadCatchIOで扱える例外、もう一つはエラーモナドです。一方のエラー処理の方法では、当然ながら他方のエラーは検出できません。つまり、エラー処理が分散してしまうことになります。これはこれでうれしいことではないのですが、さらに良くないことに、このことは奇妙な、望ましくない現象を引き起こします。

例えば、次のようなコードを考えます。

import Data.Typeable
import Control.Exception as E
import Control.Monad.CatchIO as MCIO
import Control.Monad.Trans

data MyException = MyException deriving (Show, Typeable)
instance Exception MyException

iofail :: IO ()
iofail = do
  E.throwIO MyException

foo :: MonadCatchIO m => m () -> m ()
foo m = MCIO.bracket (liftIO $ putStrLn "abc")
                     (\_ -> liftIO $ putStrLn "def")
                    (\_ -> m)

main :: IO ()
main = do
  foo iofail

MyExceptionはユーザ定義の例外を定義しています。iofailで例外をIOモナドとして発生させています。fooにiofailを渡しているので、bracketの中で例外が発生しますが、終了処理のputStrLn "def"は実行されるはずです。実行結果は次のようになります。

abc
def
mcio.hs: MyException

この場合、MonadCatchIOは単なるIOとしてインスタンス化されます。正しく動いているように見えます。次に、ErrorT String IO としてfooを実行してみます。

errfail :: MonadCatchIO m => m ()
errfail = do
  MCIO.throw MyException

foo :: MonadCatchIO m => m () -> m ()
foo m = MCIO.bracket (liftIO $ putStrLn "abc")
                     (\_ -> liftIO $ putStrLn "def")
                     (\_ -> m)

main :: IO ()
main = do
  r <- runErrorT $ foo errfail
  print (r :: Either String ())
abc
def
mcio.hs: MyException

これも正しく動いているように見えます。

これらはいずれも例外を投げていました。次に、もう一つのモナドの標準的なエラーであるfailを試してみます。

iofail :: IO ()
iofail = do
  fail "hoge"

foo :: MonadCatchIO m => m () -> m ()
foo m = MCIO.bracket (liftIO $ putStrLn "abc")
                     (\_ -> liftIO $ putStrLn "def")
                     (\_ -> m)

main :: IO ()
main = do
  foo iofail

まずはIOモナドです。

abc
def
mcio.hs: user error (hoge)

これは正しく動作します。次に、ErrorT String IO で試してみます。

errfail :: MonadCatchIO m => m ()
errfail = do
  fail "hoge"

foo :: MonadCatchIO m => m () -> m ()
foo m = MCIO.bracket (liftIO $ putStrLn "abc")
                     (\_ -> liftIO $ putStrLn "def")
                     (\_ -> m)

main :: IO ()
main = do
  r <- runErrorT $ foo errfail
  print (r :: Either String ())

さて、実行結果です。

abc
Left "hoge"

おや、さっきとは変わりました。failによるエラーがErrorモナドによるエラーの扱いになっているようですね。結果としてLeft "hoge"が返って来ています。そこはそれで良いのですが、問題なのは、defが出力されていないということです。これはどういうことなのでしょうか?

これはErrorTモナドのbindのセマンティクスおよびfailのセマンティクスに問題があります。ErrorTモナドでは、エラーが起こるとbindにおける右辺値、すなわち後続の計算がすべてショートカットされるようになっています。そして、failはErrorTモナドにおけるエラー値を返します。ゆえに、ErrorTにおいては、failが呼ばれた時点で残りの計算はすべてスキップされてしまいます。当然それにはリフトされているIOも含まれます。折角MonadCatchIOを用いて記述した例外処理も含まれます。確実にリソース解放処理を行わせるためにbracketを使っているのにこれでは大問題です。

どうすべきか

MonadCatchIOの例外処理が正しく動作するかどうかは、インスタンスにするモナドのセマンティクスに全面的に依存します。たとえば標準モナド変換子ライブラリですと、ErrorTとContTがこの問題を抱えているようで、ドキュメントにその旨が記載されています。モナドのセマンティクスに依存するので、もちろんそれ以外のモナドでもありうるかもしれません。例えば、Snap web frameworkにおけるSnapモナドでも同様の問題がありました(Snapモナドでは例外発生時でもbracketをすり抜けてしまっていました)。

どうすればいいんでしょうか。これに対する決定的な解決を私は知りません。自分がMonadCatchIOのインスタンスを作成する場合、もし可能なら、計算がショートカットしないようにすれば解決です。しかし、それは一般的には可能ではないでしょう。

この様な問題を抱えたMonadCatchIOのモナドを扱うにおいては、もっとも妥当な対策として、liftIOする前にすべての例外を捕まえてしまうようにするのがいいかと思われます(何のためのMonadCatchIOなのかという話になりますが…)。

少なくとも、この様な現象が発生し得るということを知っておくだけでもデバッグの役に立つかもしれません。私は最初この現象に遭遇した時に、必死にprintを挿んでコードを追っていましたが、突然コードパスが途切れて一体どうなっているのかとかなり悩んでしまいました。

関数型!侵略ノススメ☆

(この記事は Functional Ikamusume Advent Calendar jp 2010 の為に書かれました)

侵略!侵略!侵略!侵略!侵略!侵略!イカ娘

再帰しなイカ

main = putStrLn $ f 6 where
 f 0 = "イカ娘!"
 f n = "侵略!" ++ f (n-1)

古風に再帰しなイカ

main = putStrLn $ f 6 where
 f 0 = "イカ娘!"
 f (n+1) = "侵略!" ++ f n

左派じゃなイカ

main = putStrLn $ foldl (\a _ -> "侵略!"++a) "イカ娘!" [1..6]

右派じゃなイカ

main = putStrLn $ foldr (\_ a -> "侵略!"++a) "イカ娘!" [1..6]

右派に見せかけた左派じゃないか?

main = putStrLn $ foldr (\_ g n -> g ("侵略!"++n)) id [1..6] "イカ娘!"

const教じゃなイカ

main = putStrLn $ foldr (const ("侵略!"++)) "イカ娘!" [1..6]

ポイントフリーじゃなイカ

ika = foldr (const ("侵略!"++)) "イカ娘!" . enumFromTo 1
main = putStrLn $ ika 6

繰り返さなイカ

main = putStrLn $ until ((>=18+4) . length) ("侵略!"++) "イカ娘!"

メモ化しなイカ

ikas = "イカ娘!" : map ("侵略!"++) ikas
main = putStrLn $ ikas !! 6

メモ化しなイカ(その2)?

main = putStrLn $ iterate ("侵略!"++) "イカ娘!" !! 6

継続渡さなイカ

ikac k 0 = k "イカ娘!"
ikac k n = ikac (k . ("侵略!"++)) (n-1)
main = putStrLn $ ikac id 6

不動点じゃなイカ

import Control.Monad.Fix
main = putStrLn $ take 18 (fix $ \侵略s -> "侵略!"++侵略s) ++ "イカ娘!"

もっと不動点じゃなイカ

import Control.Monad.Fix
main = putStrLn $ (fix $ \f n -> if n==0 then "イカ娘!" else "侵略!" ++ f (n-1)) 6

モナド使わなイカ

main = putStrLn $ (do [1..6];"侵略!")++"イカ娘!"

Haskellと言ったらリスト内包表記じゃなイカ

main = putStrLn $ foldr (.) (const "イカ娘!") [("侵略!"++)|_<-[1..6]] $ ""

手続き型やらなイカ

for b e m
  | b == e = return()
  | otherwise = do
    m b
    for (b+1) e m

main = do
  for 0 6 $ \i -> do
    putStr "侵略!"
  putStrLn "イカ娘!"

熟練した手続き型Haskellerはこう書くでゲソ!

main = forM_ [1..6] (const $ putStr "侵略!") >> putStrLn "イカ娘!"

手続き型に侵略されたでゲソ!

import Control.Monad
import Data.IORef
import System.IO.Unsafe

イカ = unsafePerformIO $ newIORef "イカ娘!"

main = do
  forM_ [0..6] $ \_ -> do
    modifyIORef イカ ("侵略!"++)
  putStrLn =<< readIORef イカ

エンコードしなイカ

import Numeric
main=putStrLn$showIntAtBase 6(toEnum.fromInteger.(`mod`10^5).div 652812306412459124522040530053.(10^).(*5))25099952825734985""

ちょうど140文字でゲソ!

普通に書かなイカ

main = putStrLn $ concat (replicate 6 "侵略!") ++ "イカ娘!"

普通に書かなイカ(その2)?

main = putStrLn $ take 18 (cycle "侵略!") ++ "イカ娘!"

ゴルフしなイカ

main=putStrLn$([1..6]>>"侵略!")++"イカ娘!"

これでいいんじゃなイカ

main = putStrLn "侵略!侵略!侵略!侵略!侵略!侵略!イカ娘!"

※この記事は以下のページの関数型イカ娘風パロディでゲソ!
http://www.willamette.edu/~fruehr/haskell/evolution.html

ICFP Programming Contest 2010 優勝

   Pure Pure Code ++
Language: C++, Haskell, Python
... are the programming
languages of choice for
discriminating hackers.

今年のICFP Programming Contestにて優勝しました。(コンテスト中の様子は http://d.hatena.ne.jp/tanakh/20100702#p1 こちらにあります)

一次ソース(http://www.icfpcontest.org/2010/)はまだ来ていませんが、今年のICFP@ボルチモアにて表彰されてきました。こちら(http://twitpic.com/2swi5c)に証拠写真がアップロードされています。

Our Score: 13597.354
Our Solved: 3451
Our Cars: 72
>=5 users: 15 unsolved
3-4 users: 262 solved, 36 unsolved
2 users: 496 solved, 12 unsolved
Monopoly: 253 unsolved
91% of the Market are belong to us

最終的なスコアはこのような感じでした。特筆すべきは2 usersの占有率の高さで、508個中496個をうちのチームが解いています。しかも、リファレンス解答よりもサイズが小さいものも半分ぐらいあり、ここだけで250近い定期収入がありました。データが出てきたときにはちょっと信じられなくて何度か確かめたのですが、どうやら間違いはなさそうでした。どうしてこうなったのかは当の本人にもよくわかりませんが、コツコツソルバを改良していたのがよかったのかなと思います。http://d.hatena.ne.jp/wata_orz/20100622/1277229671 おそらくこのような被害者をたくさん作ってしまったんじゃないかと思います。でも、責任をとって優勝してきました!

本当に本当に、とても嬉しいです。同時に、やっと勝てた、という安堵の気持ちがあります。2004年に初参加して以来毎年参加していて、今年で7度目の参加です。初参加でいきなり3位になり(http://d.hatena.ne.jp/tanakh/20040926#p1)、次の年で同じく3位ながらも入賞を果たした(http://d.hatena.ne.jp/tanakh/20050930#p1)ときには、なんだかよくわからないけど、そのうち1位は取れるものだと思っていました。ところがその次の年は人数制限に泣き、さらに次の年は5位に入ったものの、それ以降は年々順位は右肩下がりで、もう勝てないんじゃないかと年々衰え行く脳みそを嘆いたりしていました。

しかし、諦めるものではありませんね。ずっと頑張っていれば報われることもあるようです。今年はチームメイトに恵まれました。これだけのメンバが6人も集まれば、文殊をも凌駕します!改めてチームの皆様に感謝します。ぴゅあぴゅあこーどの一員になれて本当によかったです。

さて、我々がDiscriminating Hackersと認められたと同時に、我々の使ったプログラミング言語にはDiscriminating Hackersの選ぶ言語として、今年一年間無制限に宣伝する権利が与えられます。何を選ぶか大変に悩みました。さすがに6人もいるとなかなか合意が得られません。というより、私以外に特に選びたい言語がある人がいないようです。私は断然Haskellを推しますが、さすがに私しか使っていない言語を選ぶのも気が引けます。はてはて、何時まで経っても決まらず、一時は間を取って(?)"crontab"にするという案も挙がりましたが、果たしてcrontabは"プログラミング言語"なのか、というそもそもの議論からして、やはり自粛すべしということになりました。crontabがDiscriminating Hackersの言語になっても喜ぶ人だれもいないですし。

結局言語選びは表彰式当日まで縺れました。最終的には、"ひとつに選べる言語はない"。強いて挙げるなら、使った言語の中で、まともにプログラミングに用いられた"C++, Haskell, Python"の3つがそれである、との結論に至りました。これらの順番には意味がないことを注記しておきます。単に辞書順です。

C++は焼きなましソルバに用いられました。焼きなましソルバに求められるのは他の全てを差し置いて速度です。速度以外に何も必要ないのでC++で書かれました。普段、Haskellでも高性能なプログラムを書けると主張している私ですが、この選択は間違っていません。他ならぬ私が書いたものです。C++で高速なプログラムを書くのは圧倒的に簡単です。普段ならともかく、時間の限られている中では、チューニングの手間がかからないC++がベストです。

Haskellは回路記述に用いられました。Haskellが使われたのは、単に私が書いたからという理由以外にはないかもしれませんが、Lava(http://hackage.haskell.org/package/xilinx-lava)などを挙げるまでもなく、このような用途にHaskellが適していることに異論はないでしょう。開始〜夜明けまでに回路ジェネレータが動いたのはHaskellのおかげだと思っています。その他、Haskellは一部の特殊ソルバなど、私専用スクリプティング言語として働いてくれました。

Pythonはその他ほぼすべての用途に用いられました。大きいのは、CGIと特殊ソルバでしょうか。CGIは制約式の可視化及び、行列表記によるサブミット、ログ蓄積とかなり重要なインフラでした。用意されたCGIでは、解いた問題や作った車すら分からなくなる仕様でしたので、このようなインフラは縁の下の力持ちとしてしっかりとチームを支えてくれました。特殊ソルバは焼きなましソルバで解けないタイプの問題のかなりの部分を潰してくれました。まさにどれが欠けても今回の優勝はなかったでしょう。

という訳で、"C++, Haskell, Python"です。これらの言語に関して、今年一杯はくれぐれも不用意な発言は避けていただくようにお願いいたします。尤も、今回のICFPコンテストにおいて、1番多くのチームに使用された言語はHaskellで、その次がC++で、その次がPythonですので、我々の選択は最も多くの人々を幸せにするものだと自負しております。ただし!私にはその権利があると思いますので、これからもC++の悪口を言いまくると思います。ワハハハは。

さて、ICFPなのです。コンテストの入賞者はICFPに招待されます。ICFPというのはその名の通り、関数プログラミングに関する国際学会です。その分野では最高峰に位置していると思います。私が研究の道に進んでいたらもしかしたら論文の方で参加していたかもしれません。そうなっていないのは、私の怠惰によるところではありますが、別の入口からとはいえ、改めてその中を覗いてみると、面白そうで面白そうで悔しくなってきます。英語が全く聞き取れないのと、そもそも内容が理解出来ないのとで、殆ど分からなかったのが悲しかったです。予習をしておけばよかったと悔やみました。でも、悔やんでも仕方が無いので、復習はしっかりしようと思います。

ICFPに参加できて本当によかったです。ともすれば日々安穏と暮らすことを良しとしようとする私の中に、知的好奇心のかけらと闘争心がまだ残っていることを確認できました。世の中にはこんなに面白くて難しいことが埋れているのに、ゆっくりなんてしていられない。もっと勉強したい。そして、いつか機会があれば論文の方で通してみたいという野望も持ち続けておこうと思いました。

併設イベントのHaskell SymposiumとHaskell Implementors Workshopにも参加しました。Haskell SymposiumはHaskellに関する研究ばかりで、私にも分かりやすいものが多かったです。Haskell Implementors WorkshopはHaskellを取り巻く現状や、ツールチェインの整備の話など、まさにHaskellの今がここにあるといった感じでとても面白かったです。Haskell界隈で有名な人が勢ぞろいしていてすごかったです。Hackageの話など、発表が終わった後も延々と議論が続いて、自分も英語が不自由なく扱えたなら、意見の一つや二つ言えるんだなあと思うと、これまた悔しさと悲しさがこみ上げてきたりして。

当時の様子はkinabaさんのまとめ(http://togetter.com/li/55345)にちょこっと載せていただいているので、よろしければご参照ください。私のはともかく、ICFP本編のkinabaさんのまとめが大変参考になります。

はてさて、そういうわけで今回は本当にいい経験をさせてもらいました。チームの皆さんに改めて感謝。このような楽しいコンテストを開催していただいた、主催者の方々にも感謝。願わくば、来年も優勝せんことを。そうそう、来年のICFPは東京開催です。皆様是非是非奮ってご参加を。

One-liner in Haskell

Haskellを現場言語にするために、こんなものを作ってみました。

hoe: Haskell One-liner Evaluator
(名前には深い意味はありません。)

Haskellワンライナーをやろうという誰得なツールです。誰得ですが、ワンライナーでも、型があると便利なんではなかろうか、型を元にユーザの望みの動作が大体決定できるんではなかろうか、という発想を元に作られました。

Haskellワンライナーは、ghc -e でも評価できますが、これは (Show a) => a か、 (Show a) => IO a な型しか評価できません。hoeでは、String -> String など、もっと色々な型を評価できます。そして、その型に応じていい感じの動作が自動的に選択されます。

例えば、idを入力すると、入力がそのまま出力されます。

$ cat tmp
Hello, Haskell World!
$ hoe 'id' tmp
Hello, Haskell World!

そうです。もうcatを作るのに、
http://d.hatena.ne.jp/nobsun/20100820/1282270092
こんなプログラムを書く必要は無いんです。

文字処理

Char -> Char なら、文字列全体に与えられた関数を適用します。

$ cat tmp | hoe 'toUpper'
HELLO, HASKELL WORLD!

大変単純明快です。

[a] -> [a] ほか

基本的にhoeは、行指向の振る舞いをします。
[a] -> [a] は、[String] -> [String] にも String -> String にもマッチしますが、このような場合は [String] -> [String] が選択されます。例えば、take 2 なら、先頭から2行を取ってくる処理になります。

$ cat tmp
Hello,
Haskell
World!
$ cat tmp | hoe 'take 2'
$ hoe 'take 2' tmp
Hello,
Haskell

また、sort なら、行をソートする処理になります。

$ cat tmp | hoe 'sort'
Haskell
Hello,
World!

大変シンプル。

String -> String の関数を書いた場合も、行ごとの処理になります。

$ cat tmp | hoe '("> "++)'
> Hello,
> Haskell
> World!

行番号

Int -> String -> String などの関数を書けば、第一引数に行番号が入ります。

$ cat tmp | hoe '\ln s -> show ln ++ "> " ++ s'
1> Hello,
2> Haskell
3> World!

先頭に行番号を書いたりするのも、このとおり。

(Int, String) を返せば、第一引数でソートした結果が出力になります。

$ cat tmp | hoe '\_ s -> (length s, s)'
Hello,
World!
Haskell

これは、行を長さでソートします。

関数のlift/join

行ごとではなく、文字ごとに処理したい場合もあります。

たとえば、drop 2 と書くと、先頭2行を落とす処理になりますが、各行2文字落とす処理が書きたいとしましょう。これは

$ cat tmp | hoe 'map $ drop 2'
llo,
skell
rld!

のように、mapを用いればできますが、これはめんどくさい。そこで、与えられた関数を [String] -> [String] ではなく、 String -> String と解釈する --join (-j) オプションを用意しました(現在の実装は極めていい加減なので、型によってはうまく動かない時もあるかもしれませんし、joinじゃなくてliftするかもしれません)。これを用いると、

$ cat tmp | hoe -j 'drop 2'
llo,
skell
rld!

と書けます。

モジュール自動import

hoeは、独断と偏見で選別したよく使われるライブラリを、自動的にimportしています。上での例でのtoUpperが装飾なしで使えていたのはこのおかげです。

なので、例えば行の長さでのソートは

$ cat tmp | hoe 'sortBy $ comparing length'
Hello,
World!
Haskell

このようにも書けます。

inplaceモード

  • i を付けると、与えたファイルを書き換えます。

例えば、

$ hoe -i 'toUpper' *

とやると、すべてのファイルを大文字にします。-iオプションに文字列を渡すと、

$ hoe -i.bak 'toUpper' *

元のファイルに.bakを付けたファイル名でバックアップが作成されます。安心です。

値評価モード

当然ですが ghc -e でできる単なる (Show a) => a や、(Show a) => IO a の評価もできます。

$ hoe '2^100'
1267650600228229401496703205376
$ hoe 'pi*50^2'
7853.981633974483

電卓としても使えますね。

$ hoe 'forM [1..10] $ \i -> writeFile ("tmp."++show i) ""'

ゴミファイルの生成もお手の物。

あとがき

という訳で、誰得ツールを作ったお話でした。
超適当な実装で、まだまだ全然機能がありませんが、
ご意見ご感想などあればどしどしご送信下さい。

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サーバを立てる必要があったので)
  • スコアボードがあった
  • ラスト見えなくなって、それなりの緊張感

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