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. Наиболее близкое из того, что я нашёл и что
-- может сработать, было создать канал и конвертировать файловый дескриптор.
-- Могу ли я упростить эту функцию, чтобы убрать из нее монаду IO?

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

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

Причина, по которой сложно тестировать getList является монадический код с побочными эффектами, смешанный с чистыми вычислениями, который делает трудным тестирование без полного перевода на модель “черного ящика”, основанного на IO. Такая смесь не подходит для рассуждений о коде.

Давайте распутаем его и затем просто протестируем чистую часть с помощью QuickCheck. Мы можем, для начала, воспользоваться ленивостью IO, чтобы избежать всех неприятных обращений с низкоуровневым IO.

Итак, первым шагом вынесем IO часть функции в тонкий слой-оболочку:

-- Тонкий слой монадической оболочки
getList :: IO [Char]
getList = fmap take5 getContents

-- Собственно работа
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.