読者です 読者をやめる 読者になる 読者になる

taketoncheir.log

Like the Decatoncheir by Poseidon Industrial, This blog is Yet Another Storage for My Long Term Memories.

QuickCheckのコード読んでみた

QuickCheckでtestデータがgenerateされる仕組み

実際に定義したデータ型に対してデータを生成する方法はこちら
ここではQuickCheckのソースコードについて記します。
実際に読み取った順に書いているので分かりにくいです、すいませんm(__)m

登場人物

  • class Testable : ユーザが定義した、Boolを返すプロパティ
  • quickCheck : ユーザが定義したTestableを受け取り、試行ごとにランダム値を生成しながらStateを引き回していくテスト管理部分
  • newtype Gen a : StdGenとサイズ上限値を取って生成されたデータを返す。サイズ上限値は例えばリスト型のデータ生成時に生成するlengthの上限値xとなり、lengthは1~xの中からランダムな値が選ばれる。
  • class Arbitrary a : テストデータ生成部分
  • type Property = Gen Prop : プロパティがテストされた結果としてのPropをGenで包んだもの

お題

以下のコードにおいて、quickCheckによりプロパティ部分にどのような値が与えられるのか?

quickCheck ¥xs -> reverse . reverse xs == xs

また、QuickCheckではテストデータ生成は検証開始時点では生成する範囲が狭く、テストが進むとだんだん範囲が広くなっていくふるまいをとります。このふるまいが決まるのはどこなのか?

ghciデバッグ

上記のxsに渡される型は[a]になります。
これを確かめるには、ghciでデバッグするのがよいでしょう。
QuickCheckプロジェクト直下、QuickCheck.cabalが存在するディレクトリでcabal-dev ghciを実行し、

Prelude > :i ¥xs -> (reverse . reverse) xs == xs

と入力すると、以下のように型を得ます。

¥xs -> (reverse . reverse) xs == xs :: Eq a => [a] -> Bool

つまり、quickCheckはランダムな長さ(サイズ)のリスト[a]を生成し、reverse.reverseに渡していきます。

quickCheck

quickCheckはTest.QuickCheck.Testモジュールに定義されています。
最終的にquickCheckWithResult :: Testable prop => Args -> prop -> IO Resultに処理が渡り、test MkState (unGen (property p))のpにユーザーが定義したプロパティ(上のラムダ式)が入ります。

test関数はテストのMkStateに記された実行状況(成功した試行数等)を見て、呼び出す関数を切り替えます。通常はrunATest関数が呼ばれます。

runATestでは、MkStateで定義されたcomputeSize'関数が成功した試行数とDiscardされた試行数を元に次の試行で生成するサイズを決定します(注:このcomputeSize'関数で試行毎に渡されるサイズが決定されています。ここでお題に書いた振る舞いが決まります。これについては後述します。)
このサイズとMkStateに格納されたrandomSeedを(StdGen -> Int -> Prop)に入力します。それが、runATest関数中の(f rnd1 size)部分です。それに対してunPropを呼び、結果を取り出します。
ここで、fは上のunGen (property p)の結果が入ります。
propertyというのは型クラスTestableのメソッドです。

型クラスTestable

Test.QuickCheck.Propertyモジュールに記載されています。
Testable型クラスは、ユーザが定義したプロパティ(a -> Bool)からProperty型を生成するpropertyメソッドを提供します。
その実装はこうです。

instance (Arbitrary a, Show a, Testable prop) => Testable (a -> prop) where
  property f = forAllShrink arbitrary shrink f

forallShrinkの実装は以下です。

-- | Like 'forAll', but tries to shrink the argument for failing test cases.
forAllShrink :: (Show a, Testable prop)
             => Gen a -> (a -> [a]) -> (a -> prop) -> Property
forAllShrink gen shrinker pf =
  gen >>= \x ->
    shrinking shrinker x $ \x' ->
      printTestCase (show x') (pf x')

gen >>= \x部分はGen aのMonad実装が該当します。
Gen aのMonad実装は以下です。

instance Monad Gen where
  return x =
    MkGen (\_ _ -> x)

  MkGen m >>= k =
    MkGen (\r n ->
      let (r1,r2)  = split r
          MkGen m' = k (m r1 n)
       in m' r2 n
    )

ここではGen aのGenを剥いて、aを取り出して¥xに渡したと考えればよい。つまり、forAllShrinkに与えられた第一引数のarbitrary関数の結果がGen aで、そのaが¥xに入ることになります。arbitrary関数はテストデータを産み出す関数ですので、このaは生成された値をさします。そして、shrinking関数の中でこのaがforAllShrinkの¥x'に入り、ユーザが定義したプロパティpfにx'が渡されます。これでやっと、プロパティと生成された値が繋がりました!

Arbitrary型クラス

実際に値を生み出す関数、arbitraryはTest.QuickCheck.ArbitraryモジュールのArbitrary型クラスで定義されています。

-- | Random generation and shrinking of values.
class Arbitrary a where
  -- | A generator for values of the given type.
  arbitrary :: Gen a
  arbitrary = error "no default generator"

今回生成するテストデータの型は[a]なので、そのinstanceはこうです。

instance Arbitrary a => Arbitrary [a] where
  arbitrary = sized $ \n ->
    do k <- choose (0,n)
       sequence [ arbitrary | _ <- [1..k] ]

じゃchooseってなんだと。

-- | Generates a random element in the given inclusive range.
choose :: Random a => (a,a) -> Gen a
choose rng = MkGen (\r _ -> let (x,_) = randomR rng r in x)

と、タプルで範囲(rng)を取ってその範囲内の値ひとつをGenで包んで返します。
つまり、property関数の中で呼ばれるarbitrary関数は、choose関数を呼んで0からサイズ上限値の範囲からランダムな長さのリストを返す、という流れになります。

Gen型クラス

Gen型クラスはStdGenとサイズ上限値を取って生成されたデータを返す振る舞いを表します。
その生成は、unGen :: StdGen -> Int -> a関数によって行われます。
このunGenが呼ばれるのは、quickCheckWithResult関数の中のtest関数です。

テストデータのサイズが広くなっていく振る舞い

QuickCheckでは、テストデータ生成は検証開始時点では生成する範囲が狭く、テストが進むとだんだん範囲が広くなっていくふるまいをとります(リストであれば、[]から始まり、lengthが長くなっていく)。
この振る舞いが決まるのが、runATest内で定義されているcomputeSize'関数です。
詳しく読んでいないのですが、

-- e.g. with maxSuccess = 250, maxSize = 100, goes like this:
-- 0, 1, 2, ..., 99, 0, 1, 2, ..., 99, 0, 2, 4, ..., 98.

とあるので、numSuccessTestsとnumRecentlyDiscardedTestsを受け取って、上のようにサイズが大きくなっていく振る舞いを取る、と。

おわり

QuickCheck、小さくていいのですが頭がこんがらがりますね...
やってることはarbitraryで生成した値を受渡しているだけです。
使う側もarbitraryだけ定義すればいいのがわかります。
QuickCheckのコードを読む上で嬉しいのは、依存ライブラリがbaseくらいであることです!dep-hellと無縁!
QuickCheck、Haskell初心者の勉強におすすめです。