Transcript P21 college 2 - Institute for Computing and Information

a generic test-system
Pieter Koopman, Artem Alimarine,
Jan Tretmans, Rinus Plasmeijer
Nijmegen, NL
IFL2002 Madrid
1
overview
testing:
• why
• what will be tested
• how do we test
by an automatic system
generic testing by a generic system
automatic and systematic generation of test data
• research question: can we make such a system
• conclusions / related & future work
IFL2002 Madrid
2
why testing
• even in functional programming we make errors
even errors that the type system does not spot
• to improve quality and confidence the software
• proving is often too much work, or not feasible
manual testing is
• much work (up to 50% of project cost)
• dull
• to be repeated after changes
 make an automatic system
encourages writing specifications
makes testing easier, faster and more reliable
IFL2002 Madrid
3
what will be tested
• there is a rich palette of quality aspects
suitability: validating
obeying the specification: functional testing
efficiency
...
we restrict ourselves to:
obeying the specification, functional testing
• specification can be:
executable specification inefficient but obviously correct
reference implementation older version
relation between input and output
...
IFL2002 Madrid
4
specification
• specification by functions in Clean
prop_DeMorgan :: Bool Bool -> Bool
prop_DeMorgan x y = x && y == not (not x || not y)
semantics:  x,  y • x && y == not (not x || not y)
prop_DropDrop :: Int Int [Int] -> Bool
prop_DropDrop m n xs = drop n (drop m xs) == drop (n+m) xs
prop_Sqrt :: Real -> Property
prop_Sqrt x = x>=0.0 ==> let r = sqrt x in r*r == x
• monomorph in order to generate test data
for polymorphic functions this tests all types
for overloaded functions the instance does matter
IFL2002 Madrid
5
how: basic idea
• generate test data, finite and  
• check property for all these values
test prop
| and [ evaluate prop x \\ x <- generate ]
= "Passed"
= "Counter-example found"
• requirements
one generate for all types
information about the counter-example
information about test data used
• what test data should be generated ?
IFL2002 Madrid
6
what test data?
• random ? (as in QuickCheck by Claessen & Hughes)
+ easy to implement
+ easy to use
+ works pretty well for small programs
- are all relevant cases covered?
- duplicates (which are useless)
• systematic !
+ coverage of standard cases (guaranteed)
Int: 0, 1, ...
List Int: [ ], [ 0 ], [ 1 ], ...
+ no duplicates
+ more confidence, better results
- harder to implement
IFL2002 Madrid
7
systematic generation of test data
what do we want?
finite types
:: Bool = True | False
:: Colour = Red | Yellow | Blue
– all values can and should be tested
very large types (always basic types)
Int, Real, Char, String, ...
– common border values (like 0, 1) and random values
recursive types
List a = Nil | Cons a (List a)
Tree a = Tip | Node a (Tree a) (Tree a)
– always handled by recursive functions
– systematic generation from small to large
IFL2002 Madrid
8
systematic generation 2
• basic types (Int, Real, ...) are handled separately
• for all other types systematic generation from
small to large is better than random
covers interesting cases
avoids duplicates
• how to define one general generate function ?
one function for all types
no new instance for each new type
systematic generation
– no duplicates
– small to large
• use generics !
IFL2002 Madrid
9
what are generics
• uniform tree representation of types
• conversion between actual type and tree
representation by system
• tree representation can be manipulated in
generic functions
• we use standard generics
See Hinze, Alimarine, ...
• enables us to define one generate function
systematic generation of generic trees
automatic conversion of trees to needed types
IFL2002 Madrid
10
generic trees
:: UNIT
= UNIT
// tip of tree
:: EITHER a b = LEFT a | RIGHT b // choice
:: PAIR
a b = PAIR a b
// product type
example:
:: Colour = Red | Yellow | Blue
generic representation of this type
:: Colour° = EITHER UNIT (EITHER UNIT UNIT)
generic representation of constructors
Red°
= LEFT UNIT
Yellow° = RIGHT (LEFT UNIT)
Blue° = RIGHT (RIGHT UNIT)
tree representation of all colours
Red°
Yellow°
IFL2002 Madrid
Blue°
11
generic trees 2
representation of [] (which is Nil):
note: same representation as Red!
LEFT UNIT
representation of [Red] ( Cons Red Nil):
RIGHT (PAIR (LEFT UNIT) (LEFT UNIT))
tree of all possible values of type [ Colour° ]°
[]
Cons
Red
Yellow
IFL2002 Madrid
[]
Blue
...
Cons
...
12
generic functions
• Basic idea:
instead of a function F :: A -> B for each A and B
we define a generic function F°
we implement F as GenToB o F° o AToGen
transformations are generated by the compiler
A
F
toGen
fromGen
A°
IFL2002 Madrid
B
F°
B°
13
Example a generic equality
generic eq a :: a a -> Bool
instances for generic type:
eq{|UNIT|} UNIT UNIT = True
eq{|PAIR|} eqx eqy (PAIR x1 y1) (PAIR x2 y2)
= eqx x1 x2 && eqy y1 y2
eq{|EITHER|} eql eqr (LEFT x) (LEFT y) = eql x y
eq{|EITHER|} eql eqr (RIGHT x) (RIGHT y) = eqr x y
eq{|EITHER|} eql eqr e1
e2
= False
eq{|Int|} n m = n == m // similar for other basic types
for each type
T
derive eq T
we either use the generic version:
or define an own instance:
T
T
eq
Bool
eq{|T|} t1 t2 = ...
T° T°
IFL2002 Madrid
eq
Bool
14
function generate
• using generics we can define one generate
function
algorithm:
• systematic generation of generic trees
• automatic conversion to desired type
IFL2002 Madrid
15
systematic generation of generic trees
• preorder traversal
remember current tree
– first all subtrees starting with LEFT
– then all subtrees starting with RIGHT
• works fine for Colour, [ Colour], ...
• problems if left generic subtree is infinite
Tree a = Tip | Node a (Tree a) (Tree a)
using :: T = C
Tree T generates: Tip, Node C Tip Tip,
Node C (Node C Tip Tip) Tip,
Node C (Node C (Node C Tip Tip) Tip) Tip, ...
never generates Node C Tip (Node C Tip Tip),...
[[T]] generates: [ ], [[ ]], [[C]], [[C, C]], [[C, C, C]],...
never generates [[ ], [ ]], [[ ], [C]], [[C], [ ]],...
IFL2002 Madrid
16
generation of generic trees 2
• breadth first traversal
order trees with respect to number of
LEFT/RIGHT nodes, or constructors
yield trees with increasing depth
within same depth: left to right
• problems
not easy to generate trees with increasing depth
efficiently
– not every tree represents a valid data value
– adding a constructor requires adding its arguments
large administration needed
IFL2002 Madrid
17
generation of generic trees 3
• preorder does not work with left recursion
• breath first is nasty
• use mixed approach
remember generated branches of tree
extend tree for next test-data item
at each EITHER node choose randomly between
extending LEFT or RIGHT branch
• Properties:
systematic
no duplicates
interesting cases occur soon (with high probability)
also bigger values earlier in list of test-data
IFL2002 Madrid
18
testing
• administrate arguments used in a record
:: Result = { ok :: Maybe Bool, args :: [String] }
• define class Testable:
class Testable a
where evaluate :: a RandomStream Result -> [Result]
instance Testable Bool
where evaluate b rs result = [ {result & ok = Just b} ]
instance Testable (a->b) | Testable b & TestArg a
where evaluate f rs result = let (rs, rs2) = split rs
in forAll rs2 f result (generate rs)
forAll rs f r list
= diagonal [apply (genRand seed) f a r \\ a<-list & seed <- rs ]
apply rs f a r = evaluate (f a) rs {r & args = [show a:r.args]}
use generic functions generate and show
IFL2002 Madrid
19
conditional tests
prop_Sqrt :: Real -> Property
prop_Sqrt x = x>=0.0 ==> let r = sqrt x in r*r == x
• implementation
:: Property = Prop (RandomStream Result -> [Result])
(==>) infixr 0 :: Bool p -> Property | Testable p
(==>) b p
| b = Prop (evaluate p) // continue testing
= Prop (\rs r = [r]) // stop testing, dummy result
instance Testable Property
where evaluate (Prop p) rs result = p rs result
IFL2002 Madrid
20
example results
prop_Sqrt :: Real -> Property
prop_Sqrt x = x>=0.0 ==> let r = sqrt x in r*r == x
counter-example found after 2 tests: .1191576
prop_DropDrop :: Int Int [Int] -> Bool
prop_DropDrop m n xs = drop n (drop m xs) == drop (n+m) xs
counter-example found after 13 tests: -1 1 [0,0]
prop_RevRev :: [Int] -> Property
prop_RevRev xs
= classify (isEmpty xs) xs ( reverse (reverse xs) == xs )
Passed 1000 tests
[]: 1 (0.1%)
prop_DeMorgan :: Bool Bool -> Bool
prop_DeMorgan x y = x && y == not (not x || not y)
counter-example found after 3 tests: False True
with correction specification: Passed 4 tests
IFL2002 Madrid
21
conclusions
• a test system is useful
writing specifications is encouraged
testing improves quality and confidence
• a generic test system is useful
property is arbitrary Clean function
system applies predicate to test-data
system generates test-data automatically
use generics to generate, show and compare values
• systematic generation of test data
no duplicated tests
covers interesting cases
stops if all cases are tested
IFL2002 Madrid
22
related work
• for FPL: QuickCheck
• advantages of our generic approach
one generate function for all types
– no user defined instances needed
» generate
» show
» equal
systematic generation of data
– no duplicates
– covers interesting cases
– stops when all cases are tested
IFL2002 Madrid
23
future work
• handling 
• generating better functions
prop_Map :: (Int->Int) (Int->Int) [Int] -> Bool
prop_Map f g xs = map f (map g xs) == map (f o g) xs
• easier user control over test-data
• better info about test-data used
• case studies
• GUI
• testing application specified in Clean but
written in some other programming language
• integration with proof-system
• ...
IFL2002 Madrid
24