Ru/Introduction to QuickCheck

Краткое введение в QuickCheck и тестирвание кода Haskell.

Мотивация

В сентябре 2006г. Bruno Martínez задал следующий вопрос:

-- Я написал функцию, которая выглядит примерно так

getList = find 5 where
     find 0 = return []
     find n = do
       ch <- getChar
       if ch `elem` ['a'..'e'] then do
             tl <- find (n-1)
             return (ch : tl) else
           find n

-- Я хочу протестировать эту функцию без использования файловой системы.  
-- В C++ я бы использовал istringstream. Я не смог найти функцию, которая 
-- возвращает Handle из String.
.  The closer thing that may work that I could find
-- was making a pipe and convertind the file descriptor.  Могу ли я упростить эту функцию, чтобы убрать из нее монаду IO?

Итак, проблема в том как эффективно протестировать эту функцию в Haskell. Решение к которому мы пришли это рефакторинг и QuickTest.

Сохранение чистоты кода

Причина, по которой сложно тестировать getList является монадический код с побочными эффектами смешанный с чистыми вычислениями, который делает трудным тестирование без полного перевода на модель “черного ящика”, основанного на IO. Such a mixture is not good for reasoning about code.

Let's untangle that, and then test the referentially transparent parts simply with QuickCheck. We can take advantage of lazy IO firstly, to avoid all the unpleasant low-level IO handling.

So the first step is to factor out the IO part of the function into a thin "skin" layer:

-- A thin monadic skin layer
getList :: IO [Char]
getList = fmap take5 getContents

-- The actual worker
take5 :: [Char] -> [Char]
take5 = take 5 . filter (`elem` ['a'..'e'])

Тестирование с QuickCheck

Теперь мы можем протестировать ‘внутренности’ алгоритма, то есть функцию take5, отдельно. Используем QuickCheck. Для начала нам нужно воплощение(instanse) Arbitrary для типа Char -- this takes care of generating random Chars for us to test with. Для простоты я ограничу это промежутком специальных символов:

import Data.Char
import Test.QuickCheck

instance Arbitrary Char where
    arbitrary     = choose ('\32', '\128')
    coarbitrary c = variant (ord c `rem` 4)

Запустим GHCi(или Hugs) и испытаем какие-нибудь обобщенные свойства (хорошо что мы можем использовать QuickCheck прямо из Haskell promt). Сначала для простоты значение типа [Char] равен самому себе:

*A> quickCheck ((\s -> s == s) :: [Char] -> Bool)
OK, passed 100 tests.

Что произошло? QuickCheck сгенерировал 100 случайных значений [Char], and applied our property, checking the result was True for all cases. QuickCheck сгенерирвал этот тестовый набор для нас!

Теперь более интересное свойство: двойное обращение тождественно:

*A> quickCheck ((\s -> (reverse.reverse) s == s) :: [Char] -> Bool)
OK, passed 100 tests.

Великолепно!

Testing take5

Первое что нужно сделать, это придумать свойства которые являются истинными для всех входных значений. То есть нам нужно найти инварианты.

Простой инвариант может быть таким:

    $\forall ~s~.~length~(take5~s)~=~5$

Запишем его как свойство QuickCheck:

\s -> length (take5 s) == 5

Которые мы можем запустить в QuickCheck так:

*A> quickCheck (\s -> length (take5 s) == 5)
Falsifiable, after 0 tests:
""

А! QuickCheck поймал нас. Если на входе строка, содержащая менее 5 фильтруемых символов, длина строка на выходе будет менее 5. Итак, ослабим немного свойство:

    $\forall ~s~.~length~(take5~s)~\leq ~5$

То есть take5 возвращает строку длинной не более 5. Протеcтируем это:

*A> quickCheck (\s -> length (take5 s) <= 5)
OK, passed 100 tests.

Хорошо!

Еще одно свойство

Еще одним свойством для проверки могла могла бы быть корректность возвращаемых символов.То есть, любые возвращённые символы принадлежат множеству ['a','b','c','d','e']

Это можно записать как: $\forall ~s~.~\forall ~e~.~e~\in ~take5~s~\to ~e~\in ~[abcde]$

И в QuickCheck:

*A> quickCheck (\s -> all (`elem` ['a'..'e']) (take5 s))
OK, passed 100 tests.

Отлично. Таким образом мы можем иметь некоторую уверенность что функция не возвращает строки ни слишком длинные ни содержащие неправильные символы.

Покрытие

Есть одна проблема настройки QuickCheck по умолчанию c тестированием [Char], 100 тестов недостаточно для нашей ситуации.В действительности QuickCheck никогда не сгенерирует строку, содержащую более 5 символов, используя предложенное воплощение Arbtrary для Char. Мы можем проверить это:

*A> quickCheck (\s -> length (take5 s) < 5)
OK, passed 100 tests.

QuickCheck wastes its time generating different Chars, when what we really need is longer strings. One solution to this is to modify QuickCheck's default configuration to test deeper:

deepCheck p = check (defaultConfig { configMaxTest = 10000}) p

Это указывает системе найти как минимум 10000 тестов до того как сделать заключение что все в порядке. Let's check that it is generating longer strings:

*A> deepCheck (\s -> length (take5 s) < 5)
Falsifiable, after 125 tests:
";:iD^*NNi~Y\\RegMob\DEL@krsx/=dcf7kub|EQi\DELD*"

Мы можем проверить генерируемые тестовые данные с помощью 'verboseCheck'. Тестирование целочисленных списков:

*A> verboseCheck (\s -> length s < 5)
0: []
1: [0]
2: []
3: []
4: []
5: [1,2,1,1]
6: [2]
7: [-2,4,-4,0,0]
Falsifiable, after 7 tests:
[-2,4,-4,0,0]

Going further

QuickCheck is effectively an embedded domain specific language for testing Haskell code, and allows for much more complex properties than those you've seen here to be tested. Some sources for further reading are:

The QuickCheck source
- QuickCheck GHC batch script
Library documentation
A large testsuite of QuickCheck code
QuickCheck Manual
Paper QuickCheck: A Lightweight Tool for Random Testing of Haskell Programs, Koen Claessen and John Hughes. In Proc. of International Conference on Functional Programming (ICFP), ACM SIGPLAN, 2000.
Paper Specification Based Testing with QuickCheck, Koen Claessen and John Hughes. In Jeremy Gibbons and Oege de Moor (eds.), The Fun of Programming, Cornerstones of Computing, pp. 17--40, Palgrave, 2003.
Paper QuickCheck: Specification-based Random Testing, Koen Claessen. Presentation at Summer Institute on Trends in Testing: Theory, Techniques and Tools, August 2004.
Paper Testing Monadic Programs with QuickCheck, Koen Claessen, John Hughes. SIGPLAN Notices 37(12): 47-59 (2002):
More research on correctness and testing in Haskell
Tutorial: QuickCheck as a test set generator
Tutorial: QuickCheck / GADT

Note, QuickCheck doesn't need to just be an embedded domain specific language for testing Haskell code. By making instances of Arbitrary for FFI types you can use Haskell and QuickCheck to check code in other languages.