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 -- он занимается генерацией произвольных Char для нашего тестирования. Для простоты я ограничу это промежутком специальных символов:

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). Сначала, для простоты, значение типа [Char] равно самому себе:

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

Что произошло? QuickCheck сгенерировал 100 случайных значений [Char] и применил наше свойство, проверяя, что результат был True во всех случаях. QuickCheck сгенерирвал этот тестовый набор для нас!

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

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

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

Тестирование 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 тратит своё время, генерируя различные [Char], в то время, как нам просто нужны более длинные строки. Одно из решений для этого, изменить настройки по-умолчанию QuickCheck, чтобы тестировал глубже:

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

Это указывает системе найти как минимум 10000 тестов до того, как сделать заключение что все в порядке. Давайте проверим, что это генерирует более длинные строки:

*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]

Двигаясь дальше

QuickCheck -- эффективный встроенный язык для тестирования Haskell кода, который позволяет тестировать гораздо более сложные свойства, чем мы здесь увидели. Некоторые источники для дальнейшего чтения:

• 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

Отметим, QuickCheck не является встроенным доменным языком только для тестирования кода Haskell. Создавая instance для Arbitrary для некоторого FFI типа, вы можете использовать Haskell и QuickCheck для проверки кода на других языках.