Automatické generování testů dle specifikace
(QuickCheck)
IB016 Seminář z funkcionálního programování
Adam Matoušek, Henrieta Micheľová
(původní autoři slajdů Vladimír Štill, Martin Ukrop)
Fakulta informatiky, Masarykova univerzita
Jaro 2021
IB016: Cvičení 05 Jaro 2021 1 / 24
Testování dle konkrétních hodnot
testujeme jednotlivé součásti samostatně (unit testing)
porovnáváme výsledky na modelových datech
modelová data i výsledky na nich si musíme vytvořit ručně
IB016: Cvičení 05 Jaro 2021 2 / 24
Testování dle konkrétních hodnot
testujeme jednotlivé součásti samostatně (unit testing)
porovnáváme výsledky na modelových datech
modelová data i výsledky na nich si musíme vytvořit ručně
+ testují přesně ty případy, které chceme
+ jednoduché na přípravu
+ stačí základní znalost jazyka
− časově náročné na přípravu
− pokrývají jen ty možnosti, na které si vzpomeneme
− testují jenom konkrétní případy, ne všeobecné chování
IB016: Cvičení 05 Jaro 2021 2 / 24
Testování dle konkrétních hodnot
Například balík HUnit:
import Test.HUnit
runTests :: IO Counts
runTests = runTestTT $ TestList [testSet1, testSet2]
testSet1 :: Test
testSet1 = TestLabel "Factorials" $
TestList [ fact 4 ~?= 24, fact 0 ~?= 1 ]
testSet2 :: Test
testSet2 = TestLabel "Numerical functions" $
TestList [ even 4 ~? "4 even?", odd 4 ~? "4 odd?" ]
IB016: Cvičení 05 Jaro 2021 3 / 24
Testování dle specifikace
Chtěli bychom testovat specifikaci, ne konkrétní případy!
Chtěli bychom, aby se testy generovaly automaticky!
Chtěli bychom pěkné (pokud možno minimální) protipříklady!
IB016: Cvičení 05 Jaro 2021 4 / 24
Testování dle specifikace
Chtěli bychom testovat specifikaci, ne konkrétní případy!
Chtěli bychom, aby se testy generovaly automaticky!
Chtěli bychom pěkné (pokud možno minimální) protipříklady!
⇒ Dodejme specifikaci pomocí invariantů.
Dělejme testy na platnost invariantů v konkrétních případech.
⇒ Případy generujme náhodně.
Nejsou některé hodnoty zajímavější pro testy než jiné?
Jak vybírat náhodně v nekonečných doménách?
⇒ Po nalezení protipříkladu se ho pokusme zmenšit.
IB016: Cvičení 05 Jaro 2021 4 / 24
Hledání invariantů
Za invariant považujeme nějakou vlastnost (property), která je
univerzálně platná. V Haskellu ji můžeme zapsat třeba jako
predikát.
Co je invariantem v následujících situacích?
max :: Int -> Int -> Int
IB016: Cvičení 05 Jaro 2021 5 / 24
Hledání invariantů
Za invariant považujeme nějakou vlastnost (property), která je
univerzálně platná. V Haskellu ji můžeme zapsat třeba jako
predikát.
Co je invariantem v následujících situacích?
max :: Int -> Int -> Int
take :: Int -> [a] -> [a]
IB016: Cvičení 05 Jaro 2021 5 / 24
Hledání invariantů
Za invariant považujeme nějakou vlastnost (property), která je
univerzálně platná. V Haskellu ji můžeme zapsat třeba jako
predikát.
Co je invariantem v následujících situacích?
max :: Int -> Int -> Int
take :: Int -> [a] -> [a]
drop :: Int -> [a] -> [a]
IB016: Cvičení 05 Jaro 2021 5 / 24
Hledání invariantů
Za invariant považujeme nějakou vlastnost (property), která je
univerzálně platná. V Haskellu ji můžeme zapsat třeba jako
predikát.
Co je invariantem v následujících situacích?
max :: Int -> Int -> Int
take :: Int -> [a] -> [a]
drop :: Int -> [a] -> [a]
insertSort :: Ord a => [a] -> [a]
insert :: Ord a => a -> [a] -> [a]
IB016: Cvičení 05 Jaro 2021 5 / 24
Hledání invariantů
Za invariant považujeme nějakou vlastnost (property), která je
univerzálně platná. V Haskellu ji můžeme zapsat třeba jako
predikát.
Co je invariantem v následujících situacích?
max :: Int -> Int -> Int
take :: Int -> [a] -> [a]
drop :: Int -> [a] -> [a]
insertSort :: Ord a => [a] -> [a]
insert :: Ord a => a -> [a] -> [a]
filter :: (a -> Bool) -> [a] -> [a]
IB016: Cvičení 05 Jaro 2021 5 / 24
QuickCheck
The programmer provides a specification of the program, in the
form of properties which functions should satisfy, and QuickCheck
then tests that the properties hold in a large number of randomly
generated cases.
balík QuickCheck
(https://hackage.haskell.org/package/QuickCheck)
moduly Test.QuickCheck.*
typicky stačí importovat Test.QuickCheck
IB016: Cvičení 05 Jaro 2021 6 / 24
QuickCheck - užitečné funkce
Funkce pro samotné testování:
quickCheck :: Testable prop => prop -> IO ()
verboseCheck :: Testable prop => prop -> IO ()
quickCheckWith :: Testable prop =>
Args -> prop -> IO ()
stdArgs :: Args
IB016: Cvičení 05 Jaro 2021 7 / 24
Příklad
prop_basic1 :: Int -> [a] -> Bool
prop_basic1 n xs = length (take n xs) == n
IB016: Cvičení 05 Jaro 2021 8 / 24
Příklad
prop_basic1 :: Int -> [a] -> Bool
prop_basic1 n xs = length (take n xs) == n
prop_basic2 :: Int -> [a] -> Bool
prop_basic2 n xs = length (take n xs) <= n
IB016: Cvičení 05 Jaro 2021 8 / 24
Příklad
prop_basic1 :: Int -> [a] -> Bool
prop_basic1 n xs = length (take n xs) == n
prop_basic2 :: Int -> [a] -> Bool
prop_basic2 n xs = length (take n xs) <= n
prop_basic3 :: NonNegative Int -> [a] -> Bool
prop_basic3 (NonNegative n) xs =
length (take n xs) <= n
IB016: Cvičení 05 Jaro 2021 8 / 24
Generátory náhodných prvků
Gen a představuje generátor náhodných hodnot typu a
generátor je vlastně funkce náhodného generátoru
(v konkrétním stavu) a parametru velikosti, která vrací prvek
požadovaného typu
existuje standardní instance Monad Gen
sample :: Show a => Gen a -> IO ()
IB016: Cvičení 05 Jaro 2021 9 / 24
Typová třída Arbitrary
class Arbitrary a where
arbitrary :: Gen a
shrink :: a -> [a]
typy, pro které je možno vygenerovat „náhodný prvek“
arbitrary je náhodný generátor pro daný typ
shrink se používá při zmenšování protipříkladů
výsledný seznam nesmí obsahovat zadaný prvek
-- default shrink implementation
shrink _ = []
IB016: Cvičení 05 Jaro 2021 10 / 24
Příklad
data Pack = EmptyPack -- empty pack
| Tomatoes Double -- tomato weight in kg
| Cucumbers Int -- number of cucumbers
deriving (Eq, Show)
IB016: Cvičení 05 Jaro 2021 11 / 24
Příklad
data Pack = EmptyPack -- empty pack
| Tomatoes Double -- tomato weight in kg
| Cucumbers Int -- number of cucumbers
deriving (Eq, Show)
packGen1 :: Gen Pack
packGen1 = oneof [ pure EmptyPack
, fmap Tomatoes arbitrary
, fmap Cucumbers arbitrary ]
instance Arbitrary Pack where
arbitrary = packGen1
IB016: Cvičení 05 Jaro 2021 11 / 24
Příklad
checkout :: [Pack] -> Double
checkout = sum . map price
where price EmptyPack = 0
price (Tomatoes weight) = weight * 33.50
price (Cucumbers count) =
fromIntegral count * 19.90
prop_pack1 :: [Pack] -> Bool
prop_pack1 pack = checkout pack >= 0
IB016: Cvičení 05 Jaro 2021 12 / 24
Příklad
prop_pack2 :: [Pack] -> Property
prop_pack2 pack =
all nonNegative pack ==> checkout pack >= 0
where nonNegative (Tomatoes w) = w >= 0
nonNegative (Cucumbers n) = n >= 0
nonNegative _ = True
IB016: Cvičení 05 Jaro 2021 13 / 24
Příklad
prop_pack2 :: [Pack] -> Property
prop_pack2 pack =
all nonNegative pack ==> checkout pack >= 0
where nonNegative (Tomatoes w) = w >= 0
nonNegative (Cucumbers n) = n >= 0
nonNegative _ = True
packGen2 :: Gen Pack
packGen2 = oneof
[ pure EmptyPack
, fmap Tomatoes (arbitrary `suchThat` (>=0))
, fmap Cucumbers (arbitrary `suchThat` (>=0)) ]
IB016: Cvičení 05 Jaro 2021 13 / 24
Příklad
data BinTree = BEmpty | BNode Int BinTree BinTree
deriving (Eq, Ord, Show)
instance Arbitrary BinTree where
arbitrary = treeGen1
shrink = treeShrink
IB016: Cvičení 05 Jaro 2021 14 / 24
Příklad
data BinTree = BEmpty | BNode Int BinTree BinTree
deriving (Eq, Ord, Show)
instance Arbitrary BinTree where
arbitrary = treeGen1
shrink = treeShrink
treeGen1 :: Gen BinTree
IB016: Cvičení 05 Jaro 2021 14 / 24
Příklad
data BinTree = BEmpty | BNode Int BinTree BinTree
deriving (Eq, Ord, Show)
instance Arbitrary BinTree where
arbitrary = treeGen1
shrink = treeShrink
treeGen1 :: Gen BinTree
treeGen1 = oneof [ pure BEmpty,
liftM3 BNode arbitrary treeGen1 treeGen1 ]
IB016: Cvičení 05 Jaro 2021 14 / 24
Příklad
data BinTree = BEmpty | BNode Int BinTree BinTree
deriving (Eq, Ord, Show)
instance Arbitrary BinTree where
arbitrary = treeGen1
shrink = treeShrink
treeGen1 :: Gen BinTree
treeGen1 = oneof [ pure BEmpty,
liftM3 BNode arbitrary treeGen1 treeGen1 ]
treeShrink :: BinTree -> [BinTree]
IB016: Cvičení 05 Jaro 2021 14 / 24
Příklad
data BinTree = BEmpty | BNode Int BinTree BinTree
deriving (Eq, Ord, Show)
instance Arbitrary BinTree where
arbitrary = treeGen1
shrink = treeShrink
treeGen1 :: Gen BinTree
treeGen1 = oneof [ pure BEmpty,
liftM3 BNode arbitrary treeGen1 treeGen1 ]
treeShrink :: BinTree -> [BinTree]
treeShrink BEmpty = []
treeShrink (BNode v l r) = [l, r]
++ [ BNode v' l r | v' <- shrink v ]
++ [ BNode v l' r | l' <- shrink l ]
++ [ BNode v l r' | r' <- shrink r ]
IB016: Cvičení 05 Jaro 2021 14 / 24
Příklad
-- Create inorder list of values.
treeToList :: BinTree -> [Int]
-- Calculate sum of all nodes in tree.
treeSum :: BinTree -> Int
prop_tree1 :: BinTree -> Bool
prop_tree1 t = treeSum t == sum (treeToList t)
IB016: Cvičení 05 Jaro 2021 15 / 24
Příklad
prop_tree2 :: BinTree -> Property
prop_tree2 t = classify (treeSize t == 0) "trivial" $
prop_tree1 t→
IB016: Cvičení 05 Jaro 2021 16 / 24
Příklad
prop_tree2 :: BinTree -> Property
prop_tree2 t = classify (treeSize t == 0) "trivial" $
prop_tree1 t→
prop_tree3 :: BinTree -> Property
prop_tree3 t = classify (treeSize t == 1) "easy" $
prop_tree2 t→
IB016: Cvičení 05 Jaro 2021 16 / 24
Příklad
prop_tree2 :: BinTree -> Property
prop_tree2 t = classify (treeSize t == 0) "trivial" $
prop_tree1 t→
prop_tree3 :: BinTree -> Property
prop_tree3 t = classify (treeSize t == 1) "easy" $
prop_tree2 t→
prop_tree4 :: BinTree -> Property
prop_tree4 t = collect (treeSize t) $ prop_tree3 t
IB016: Cvičení 05 Jaro 2021 16 / 24
Příklad
-- Calculate size of tree.
treeSize :: BinTree -> Int
treeGen3 :: Gen BinTree
treeGen3 = sized treeGen where
treeGen 0 = pure BEmpty
treeGen n = frequency
[ (1, pure BEmpty)
, (4, liftM3 BNode arbitrary subtree subtree) ]
where subtree = treeGen (n `div` 2)
IB016: Cvičení 05 Jaro 2021 17 / 24
QuickCheck – užitečné funkce
(==>) :: Testable prop =>
Bool -> prop -> Property
(===) :: (Eq a, Show a) => a -> a -> Property
forAll :: (Show a, Testable prop) =>
Gen a -> (a -> prop) -> Property
classify :: Testable prop =>
Bool -> String -> prop -> Property
collect :: (Show a, Testable prop) =>
a -> prop -> Property
IB016: Cvičení 05 Jaro 2021 18 / 24
Generátory náhodných prvků - užitečné funkce
Tvorba nových generátorů:
choose :: Random a => (a, a) -> Gen a
elements :: [a] -> Gen a
Vybrané funkce pracující s generátory:
listOf :: Gen a -> Gen [a]
vectorOf :: Int -> Gen a -> Gen [a]
oneof :: [Gen a] -> Gen a
frequency :: [(Int, Gen a)] -> Gen a
sized :: (Int -> Gen a) -> Gen a
suchThat :: Gen a -> (a -> Bool) -> Gen a
IB016: Cvičení 05 Jaro 2021 19 / 24
Hromadné testování
Možnost nechat QuickCheck najít všechny testy:
{- # LANGUAGE TemplateHaskell # -}
-- all the module code
-- at the end:
return []
runTests :: IO Bool
runTests = $quickCheckAll
první řádek zapíná rozšíření TemplateHaskell (musí být před
hlavičkou modulu)
$quickCheckAll je funkce, která za kompilace vloží kód pro
spuštění všech testů pojmenovaných prop_*
return [] způsobí, že $quickCheckAll může najít testy
(které jsou před tímto řádkem)
IB016: Cvičení 05 Jaro 2021 20 / 24
Testování funkcí
class CoArbitrary a where
coarbitrary :: a -> Gen b -> Gen b
typy, které můžou být argumenty „náhodných funkcí“
IB016: Cvičení 05 Jaro 2021 21 / 24
Testování funkcí
class CoArbitrary a where
coarbitrary :: a -> Gen b -> Gen b
typy, které můžou být argumenty „náhodných funkcí“
-- Property to test if 'foldr' and 'foldl' calculates
the same things.→
prop_fold :: Fun (Int, Int) Int -> Int -> [Int]
-> Property
IB016: Cvičení 05 Jaro 2021 21 / 24
Testování funkcí
prop_fold :: Fun (Int, Int) Int -> Int -> [Int]
-> Property
prop_fold f z xs = foldr (applyFun2 f) z xs
=== foldl (applyFun2 f) z xs
IB016: Cvičení 05 Jaro 2021 22 / 24
Testování funkcí
prop_fold :: Fun (Int, Int) Int -> Int -> [Int]
-> Property
prop_fold f z xs = foldr (applyFun2 f) z xs
=== foldl (applyFun2 f) z xs
> quickCheck prop_fold
*** Failed! Falsifiable (after 3 tests and 16 shrinks):
{(0,2)->0, _->1}
2
[0]
0 /= 1
Fun a b je generovatelná funkce z a do b
je možné ji zobrazit (po případech/vzorech), provádět shrink
více viz Test.QuickCheck.Function
IB016: Cvičení 05 Jaro 2021 22 / 24
Rekapitulace – QuickCheck
+ Testujeme program vůči specifikaci, ne konkrétním případům.
+ Testy můžou najít i případy, které by nás nenapadly.
+ Konkrétní případy pro testy jsou generovány automaticky.
+ Donutí nás důkladněji se zamyslet nad specifikací.
IB016: Cvičení 05 Jaro 2021 23 / 24
Rekapitulace – QuickCheck
+ Testujeme program vůči specifikaci, ne konkrétním případům.
+ Testy můžou najít i případy, které by nás nenapadly.
+ Konkrétní případy pro testy jsou generovány automaticky.
+ Donutí nás důkladněji se zamyslet nad specifikací.
− Všechno stojí a padá na dobré volbě invariantů.
− Potřebujeme vhodný generátor náhodných prvků.
− Přesná specifikace je často příliš složitá.
− Jestliže nespecifikujeme invarianty přesně a implementujeme
špatný generátor, můžeme dostat falešný pocit bezpečí!
− Nemusí vždy nalézt neobvyklé chyby, chyby na okrajových
případech – může dávat různé odpovědi!
IB016: Cvičení 05 Jaro 2021 23 / 24
Rekapitulace – QuickCheck
QuickCheck je silný nástroj, musíme však:
rozumět, co dělá,
a především rozumět, co nedělá!
IB016: Cvičení 05 Jaro 2021 24 / 24
Rekapitulace – QuickCheck
QuickCheck je silný nástroj, musíme však:
rozumět, co dělá,
a především rozumět, co nedělá!
. . . a pak můžeme vybudovat třeba hsExprTest
IB016: Cvičení 05 Jaro 2021 24 / 24
Rekapitulace – QuickCheck
QuickCheck je silný nástroj, musíme však:
rozumět, co dělá,
a především rozumět, co nedělá!
. . . a pak můžeme vybudovat třeba hsExprTest
obdoba QuickCheck existuje i v mnoha jiných
(i imperativních) programovacích jazycích
IB016: Cvičení 05 Jaro 2021 24 / 24