あどけない話

doの中のif

Haskell

Haskellの文法はかなり心地よいが、もちろん嫌な点もある。その代表例が、do の中の if 式である。

if は一つの式を成す必要があるので、以下のように行を下げないといけない。

deleteFile :: FilePath -> IO ()
deleteFile file = do
    exist <- doesFileExist file
    if exist
        then removeFile file
        else return ()

以下のように書きたいけれど、Haskell 98 としては誤りである。

deleteFile :: FilePath -> IO ()
deleteFile file = do
    exist <- doesFileExist file
    if exist then
        removeFile file
    else
        return ()

Haskell 2010 では、if 式を三つの式から校正されるよう変更することで、上記のように書けるようにした。Haskell 98 であっても、DoAndIfThenElse拡張を使えば、この形式が利用できる。

しかし、実際に使ってみると、以下のような問題がある。

• DoAndIfThenElse に対応していない GHC 6 がまだ使われいる
• hlint が新しい if 式に対応していない

そこで、当面僕は do の中の if 式を以下のように書くことにした。

deleteFile :: FilePath -> IO ()
deleteFile file = do
    exist <- doesFileExist file
    if exist then
        removeFile file
      else
        return ()

つまり、else の前に 2 つ空白文字を入れる。if は一つの式になり、見た目もあまり損ねない。

Permalink | コメント(0) | トラックバック(0) | 15:28

なぜConduitなのか？

Haskell

Iteratee という概念は、Haskell 界に適切な資源管理と合成可能な IO をもたらした。そして、以下の3つのパッケージが乱立することになった。

• iteraee
• enumerator
• iterIO

昨年の ICFP の際、Iteratee の生みの親である Oleg さんに「この状況をどう思っているのか」と聞いてみた。曰く「とてもよい状況です。いくつかの実装が現れ実際に使われることで、本当に必要な機能が分かるでしょう」。

もしかすると、Conduit によって彼の願いがもう実現されたのかもしれない。

Iteratee には何が足らなかったのか？

以下は、enumerator の使用経験基づく考察だが、たぶん Iteratee 全体に言えると思う。

1. Iteratee で資源を割り当てられない
   • Michael Snoyman さんの不満
2. 例外処理が大変
   • liftIO と catch を使いたいのに、tryIO と catchError を使わないといけない
3. Enumerator という情報源を自由に引き回せない
   • 僕を含めた Proxy サーバを作っている人の不満

1) は簡単に分かる。enumFile はあるのに、iterFile がない。

2) は、コードを書いてみれば、すぐに嫌になる。

3) は難しいが説明してみる。読飛ばしてもらってもかまわない。WAI + Warp + http-enumerator で Proxy を作るとする。以下のようにデータがやり取りされる。

       ---a-->       ---c--> 
Brower         Proxy         Server
       <--b---       <--d---

ここで、HTTP の POST を考える。HTTP Request のボディは、a から c へ固定長のバッファを使ってストリーミングされてほしい。HTTP Response のボディも d から b へ固定長のバッファを使ってストリーミングされてほしい。

WAI では、a の HTTP Reuqest ヘッダが引数として受け取ることができるが、a のボディは enumerator として配管の下に埋まっている。このボディを c を作成する http-enumrator に渡す方法が存在しない。逆に d から b へのストリーミングは、何もしなくても実現できる。

つまり、WAI 上に Proxy を作成すると、上りはストア＆フォワード、下りはストリーミングになる。これは、大きな HTTP ボディを持つ DOS に対して、あまりにも脆弱だ。

結局、Iteratee は簡単な問題に利用するのはよかったが、複雑な問題を解くには窮屈な感じだった。

Iteratee では、Enumerator は Iteratee というオートマトンを駆動する主役であって、自分自身がどこかに引き渡されることなんて想定されていなかった訳だ。

Conduit

昨年の11月頃に、Michael さんに3) の不満を伝えたところ、最初は理解されなかった。幸運なことに、そのころあるイタリア人が Proxy を作っていて、僕の問題を理解してくれた。そして、二人掛かりでの説明が始まった。結局、Oleg さんとか、3 つのライブリの作者とかを巻き込んだ大議論が起こり、enumerator に不満を感じていた Michael さんが猛烈な勢いで Conduit を実装した。yesodweb のブログを見れば、その勢いが分かるだろう。

Conduit は、Iteratee の push 型を改め、pull 型に先祖帰りした。3人の登場人物の名前は以下の通り。

• 生産者：Source
• 消費者：Sink
• パイプ：Conduit

Sink という名前には違和感があるが、水道管を意味する Conduit からの連想と思えば納得できる。

Conduit では、モナドを IO (と ST) に制限しており、IORef (STRef) を使って、資源の解放を管理する。また、上記3つの問題がすべて解決されている。

1) を解決する例：

import Data.Conduit
import qualified Data.Conduit.Binary as CB

copyFile :: FilePath -> FilePath -> IO ()
copyFile src dest = runResourceT $ CB.sourceFile src $$ CB.sinkFile dest

2) は、lifted-base の Control.Exception.Lifted が自由自在に使えることで解決されている。2) と3) を解決する例の一部を示す：

import Control.Exception (SomeException)
import Control.Exception.Lifted (catch)
import qualified Network.HTTP.Conduit as H
import Network.Wai

-- WAI の Request を HTTP.Conduit の Request へ変換
toHTTPRequest :: Request -> RevProxyRoute -> Int64 -> H.Request IO
toHTTPRequest req route len = H.def {
    H.host = revProxyDomain route
  , H.port = revProxyPort route
  , H.secure = isSecure req
  , H.checkCerts = H.defaultCheckCerts
  , H.requestHeaders = addForwardedFor req $ requestHeaders req
  , H.path = pathByteString path'
  , H.queryString = rawQueryString req
  -- WAI から Source なボディが取れる！
  -- enumerator だとこれができない
  , H.requestBody = H.RequestBodySource len (toSource . requestBody $ req)
  , H.method = requestMethod req
  , H.proxy = Nothing
  , H.rawBody = False
  , H.decompress = H.alwaysDecompress
  }
  where
    path = fromByteString $ rawPathInfo req
    src = revProxySrc route
    dst = revProxyDst route
    path' = dst </> (path <\> src)

-- catch も自由自在だよ
revProxyApp :: ClassicAppSpec -> RevProxyAppSpec -> RevProxyRoute -> Application
revProxyApp cspec spec route req =
    revProxyApp' cspec spec route req
    `catch` badGateway cspec req

revProxyApp' :: ClassicAppSpec -> RevProxyAppSpec -> RevProxyRoute -> Application
revProxyApp' cspec spec route req = do
    let mlen = getLen req
        len = fromMaybe 0 mlen
        httpReq = toHTTPRequest req route len
    -- Request のボディをストリーミングしながら転送
    H.Response status hdr downbody <- H.http httpReq mgr
    let hdr' = fixHeader hdr
    liftIO $ logger cspec req status (fromIntegral <$> mlen)
    -- Response のボディは自動的にストリーミングになる
    return $ ResponseSource status hdr' (toSource downbody)
  where
    mgr = revProxyManager spec
    fixHeader = addVia cspec req . filter p
    p ("Content-Encoding", _) = False
    p _ = True

badGateway :: ClassicAppSpec -> Request-> SomeException -> ResourceT IO Response
badGateway cspec req _ = do
    liftIO $ logger cspec req st Nothing
    return $ ResponseBuilder st hdr bdy
  where
    hdr = addServer cspec textPlainHeader
    bdy = byteStringToBuilder "Bad Gateway\r\n"
    st = statusBadGateway

備考

WAI 1.0 と Yesod 1.0 は、Conduit ベースになります。

Permalink | コメント(0) | トラックバック(0) | 18:17

HaskellとテストとBDD

Haskell

Haskellでの BDD を実践するとどうなるかを考えるためのメモ。

型

豊かなデータ型とセクシーな型システムを持つ Haskell では、型が以下のような意味を持つ。

• 仕様
• 保守性の向上
• 簡単なドキュメント
• 設計図

BDD では、テストの用語ではなく設計の用語を使ってテストを記述する。だから Haskell で、まず型を書く習慣があれば、ある意味 BDD を実践していると言える。この感覚は、他の言語のプログラマには分からないかもしれない。

fromList :: Ord a => [a] -> Set a
fromList = undefined

このコードはコンパイルを通過するので、型に関する誤りがないことを確かめられる。

僕はへなちょこなので、型を先に書くこともあれば、後から書くこともある。

• 単純なコードはさっさと実装したい
  • 型は GHC に推測させて、ghc-mod で自動挿入する
• 難しいコードは型を書いてよく考える
  • 型のレベルで設計する。そうすれば型が実装を導いてくれる

値

型に関する仕様が書けたら、次は値に関する仕様を書くべきだ。依存型とかを使えば、それ以上のことができるという意見もあるだろうけど、とっつきにくいので今は考えない。

Haskell には、Ruby の rspec をまねた hspec があり一部の人は絶賛している。rspec のチュートリアルを読んでみて、気持ちはわかったのだけれど、僕にはピンとこなかった。

結局 rspec は、仕様書だと思ってテストコードをコードとは別のファイルに書く訳で、それがドキュメントに反映されない。（反映するツールはあるのかもしれないけれど。）

それよりも、Python の doctest の方が、僕としてはいいと思う。Haskell には Python をまねた doctestがある。

{-| Creating a set from a list. O(N log N)

>>> empty == fromList []
True
>>> singleton 'a' == fromList ['a']
True
>>> fromList [5,3,5] == fromList [5,3]
True
-}

fromList :: Ord a => [a] -> Set a
fromList = undefined

このように対話的な使用例を書く。この書式には haddock が対応しているので、doctest は haddock から使用例のデータをもらって、対話的に実行し検査する。BBD 風にするには、それぞれの使用例にもう少し説明を加えるべきかもしれないと思う一方で、これで十分な気もする。

でも、まだいろいろ不満がある。

• test-framework と統合されていない
• 対話的な例ではなく、等式だけを書きたい
• QuickCheck のプロパティが書けない

test-framework

test-framework のドライバは、HUnit 用、QuickCheck2 用、doctest 用が用意されている。test-framework-th を使えば、HUnit のユニットテストと QuickCheck2 のプロパティを書くのが簡単になる。それぞれ、"case_" と "prop_" で始まる関数を書けばいい。

module Main where

import Test.Framework.TH
import Test.Framework.Providers.HUnit
import Test.Framework.Providers.QuickCheck2
import Test.QuickCheck2
import Test.HUnit

import Data.MySet

main :: IO ()
main = $(defaultMainGenerator)

prop_toList :: [Int] -> Bool
prop_toList xs = ordered ys
  where
    ys = toList . fromList $ xs
    ordered (x:y:xys) = x <= y && ordered (y:xys)
    ordered _         = True

case_ticket4242 :: Assertion
case_ticket4242 = (valid $ deleteMin $ deleteMin $ fromList [0,2,5,1,6,4,8,9,7,11,10,3]) @?= True

defaultMain に与える Test のリストが Template Haskell で自動生成され、すごく便利だ。しかし、doctest が統合されていないので、test-framework-th-prime を作成してみた。手伝ってくれた @mr_konn さん、ありがとう！

module Main where

import Test.Framework.TH.Prime
import Test.Framework.Providers.DocTest
import Test.Framework.Providers.HUnit
import Test.Framework.Providers.QuickCheck2
import Test.QuickCheck2
import Test.HUnit

import Data.MySet

main :: IO ()
main = $(defaultMainGenerator)

doc_test :: DocTests
doc_test = docTest ["../Data/MySet.hs"] ["-i.."]

prop_toList :: [Int] -> Bool
prop_toList xs = ordered . toList . fromList $ xs
  where
    ordered (x:y:xys) = x <= y && ordered (y:xys)
    ordered _         = True

case_ticket4242 :: Assertion
case_ticket4242 = (valid $ deleteMin $ deleteMin $ fromList [0,2,5,1,6,4,8,9,7,11,10,3]) @?= True

なお、Mac 上の GHC 7.0 でこのコードを実行するにはコンパイルする必要がある。runghc などで動かすと segfault する。GHC 7.4 では直るようだ（未確認）。

等式

対話的な例よりも、等式の方がしっくりくる場合がある。

{-| Creating a set from a list. O(N log N)

>>> empty == fromList []
>>> singleton 'a' == fromList ['a']
>>> fromList [5,3,5] == fromList [5,3]
-}

fromList :: Ord a => [a] -> Set a
fromList = undefined

こうなると、こういう具体例だけではなく、QuickCheck のプロパティ、つまり関数の持つ性質を記述したくなる

QuickCheck

Simon M さんは、すでに haddock に対し、”prop>”という新しい書式を導入することに賛成しているそうだ。加えて "unit> という新しい書式を導入し対話的な例と区別することにすると、こんな感じになるだろうか？

{-| Creating a set from a list. O(N log N)

prop> empty == fromList []

unit> singleton 'a' == fromList ['a']
prop> singleton (x :: Char) == fromList [x]

unit> fromList [5,3,5] == fromList [5,3]
prop> fromList (xs :: [Int]) == fromList (uniq xs)

prop> ordered . toList . fromList $ (xs :: [Int])
-}

fromList :: Ord a => [a] -> Set a
fromList = undefined

test-framework のテストコードに書いているコードの多くはドキュメントに移動することになる。こんな環境が整ったら、テストコードには以下を記述することになるだろう。

• ドキュメントに書きたくないユニットテスト
• ドキュメントに書きたくないプロパティ
• QuickCheck が見つけてくれた失敗例を切り出したユニットテスト
• IO がからむユニットテスト

考察

"prop>" と "unit>" は統合できるのか否か？ 乱数的な変数のないプロパティを QuickCheck に与えると、1回しか実行しなくていいのに、100 回実行してしまう問題がある。

プロパティに現れる自由変数はどうする？無名関数を書かせて、閉じたλ式にさせる？

prop> \(xs :: [Int]) -. ordered . toList . fromList $ xs

そもそも、テストコードは test-framework の延長ではなく、hspec を発展させる方がいいのではないかという意見もあるかもしれない。そういう意見の方は、ぜひ僕を納得させてほしい。

Permalink | コメント(0) | トラックバック(1) | 11:36

ハッシュテーブル攻撃とHaskell

Haskell

以下を理解しようとしたときのメモ：

• Efficient Denial of Service Attacks on Web Application Platforms
  • slides
• n.runs-SA-2011.004 - web programming languages and platforms - DoS through hash table

概要

外部からのデータに対して、効率の悪いアルゴリズムで処理するとセキュリティホールになるという一般的な問題の一例。N要素のハッシュテーブルの作成は、平均でO(N)だが、最悪で O(N^2) となる。

いろんな言語で、DJB のハッシュが利用されている。

• DJBX33A
  • Equivalent string で衝突をたくさん作れる。理解は容易。
• DJBX33X
  • 中間一致(Meet-in-the-middle)攻撃で衝突をたくさん発見できる。この理解は少し難しい。
  • Haskell の hashable パッケージはこっちを使っている。

DJBX33X

XOR を使っているので、基本的に総当たり攻撃で衝突を発見する。中間一致攻撃を使うと、計算量を格段に低減できる。中間一致攻撃を実現するためには、DJBX33X の逆関数が必要。

もし逆関数があるなら、以下のように中間一致攻撃が実現できる。実際に使われている初期値を調べる。適当に最終的な値を決める。この値が衝突する値。3文字程度のランダムな文字列(suffix と呼ぶ)をたくさん用意し、最終的な値と文字列から逆関数を使って中間値をたくさん求める。衝突もあるけど、概ね用意した文字列の数、中間値が求まる。

7文字程度のランダムな文字列(prefixと呼ぶ)をたくさん用意する。初期値と文字列から DJBX33X を使ってハッシュ値を計算し、中間値の中に一致するものを調べる。一致すれば、prefix+suffix が得たい文字列。この文字列はたくさん発見でき、すべて初期値から同じ最終的な値を生成する。つまり、衝突する文字列がたくさん手に入る。

実際に Haskell でコードを書いてみたら、驚くほどたくさん見つかった。

DJBX33X の逆関数

f × g = 1 を満たすのが、f の逆関数 g。

DJBX33X を数値式で表すと：

h_n+1 = (33 h_n) xor x   (mod 2^m)

A xor B xor B = A だから、両辺に xor x を右から施すと：

h_n+1 xor x = 33 h_n  (mod 2^m)

あとは、法 2^m における 33 の逆元を求めればよい。これは拡張ユークリッドの互除法を用いれば、簡単に見つかる。それを (1/33) と表現すると：

(h_n+1 xor x) × (1/33) = h_n  (mod 2^m)

よって逆関数が求まった。

サーバ攻撃

フォームのデータとして key と value の組を POST する。この key に求めたたくさんの文字列を使う。サーバは自動的にハッシュテーブルを生成するので、CPU 時間をたくさん消費する。

Haskell

Haskell では、ハッシュテーブル(辞書という方が適切)の実装に木が用いられているので、基本的にこの攻撃には弱くない。つまり、Data.Map や Data.IntMap は平均でも最悪の場合でも O(N log N)。

hashable パッケージの Hashable クラスを利用している hashmap の Map や unordered-containers の HashMap は、DJBX33X を使うことになる。

• hashmap の Map は、木であり、末端も木(Data.Map)
  • すべての要素が衝突するなら、木は成長しないので O(1)
  • 衝突した要素の挿入は O(log N)
  • よって、最悪 O(N log N) となる
• unordered-containers の HashMap は、木であるが、末端はリスト(FullList)
  • すべての要素が衝突するなら、木は成長しないので O(1)
  • 衝突した要素の挿入は O(N)
  • よって、最悪 O(N^2) となる

対策

Hashable の hash ではなく hashWithSalt とランダムな Salt を使う。Salt とは初期値。初期値が推測できなければ、衝突する文字列を発見するのは困難。Johan によれば、以下のようにして秘密の(ランダムな) secretSalt と mix を定義すればいいのではないかとのこと。

newtype SaltedString = SS ByteString

instance Hashable SaltedString where
  hashWithSalt salt (SS str) = hashWithSalt (secretSalt `mix` salt) str

Permalink | コメント(0) | トラックバック(0) | 17:41

Haskellのリスト定義の謎

haskell

ghci を起動し、":info []" とタイプすれば、リストの定義が表示されます。

> :info []
data [] a = [] | a : [a]

これが何を意味しているのか、僕は長い間分かりませんでした。同じように悩んでいる人もいるかもしれないので、説明してみます。

まず、第一の分かりにくい点は表記が揺れていることです。リスト型を意味する部分が、= の左側では "[] a"、右側では "[a]" となっています。これはどちらか一方に統一すべきでしょう。ここでは、"[] a" を選んでみます。

data [] a = [] | a : [] a

ちなみに、型の部分に "[a]" と書くと、それは "[] a" の別表現になります。a は型変数です。値の部分に "[a]" と書くと、"a:[]" の構文糖衣です。a は単なる変数です。

第二の分かりにくい点は、データ構成子が二項演算子として使われていることです。"()" で囲んで前に出してみましょう。

data [] a = [] | (:) a ([] a)

第三の分かりにくい点は、data の定義に記号が使われていることです。ユーザが定義するデータ型では、型の部分に記号は使えません。ただ、構成子なら ":" で始まる記号列を使って二項演算子風に書くこともできます。

第四の分かりにくい点は、"[]" が構成子である空リストと型の名前に使われていることです。

型の名前と、構成子を区別がつくようにアルファベットに変えてみましょう。

data List a = Nil | Cons a (List a)

これなら、分かると思います。ちなみに二分木と比べてみましょう。

data Tree a = Leaf | Node a (Tree a) (Tree a)

リストが木の特殊形であることがよく分かりますね。

Permalink | コメント(2) | トラックバック(0) | 11:09