Automatisiertes Testen

Tests sind ein wichtiges Hilfsmittel um Programmierfehler aufzudecken. Sie können zwar niemals die Abwesenheit von Fehlern zeigen (dazu braucht man Beweise) zeigen jedoch häufig deren Anwesenheit und sind oft einfacher zu erstellen als Korrektheitsbeweise.

Diese QuickSort Implementierung

qsort :: Ord a => [a] -> [a]
qsort []     = []
qsort (x:xs) =
  filter (<x) xs ++ x : filter (>x) xs

können wir manuell im GHCi testen:

ghci> qsort [12,3,4]
[3,4,12]

Alternativ könnten wir eine Reihe solcher Tests in eine Datei schreiben und diese jedesmal ausführen, wenn wir die Implementierung ändern (Regressionstests).

Eigenschaftsbasiertes Testen

Regressionstests zu schreiben ist langweilig. Programmierer vernachlässigen diese Aufgabe deshalb oft und schreiben nur wenige Tests, die nicht alle interessanten Eingenschaften überprüfen. Dabei ist es interessant, über Programmeigenschaften nachzudenken! Besser wäre es aber, wenn man diese Eigenschaften selbst als Tests verwenden könnte, statt sich Tests zu überlegen, die sie überprüfen.

In Haskell kann man statt Tests Eigenschaften von Funktionen schreiben und diese mit automatisch generierten Eingaben testen. Dazu verwenden wir das Tool QuickCheck, das man mit

bash# cabal install QuickCheck

installieren kann.

Das folgende Haskell Prädikat spezifiziert, dass qsort idempotent sein soll.

import Test.QuickCheck

idempotence :: [Int] -> Bool
idempotence xs = qsort (qsort xs) == qsort xs

Wir können dieses Prädikat von Hand mit Beispieleingaben aufrufen.

ghci> idempotence [1,2,3]
True

Wir können aber auch die Funktion quickCheck verwenden, die Listen vom Typ [Int] generiert und prüft, ob das Prädikat für diese erfüllt ist.

ghci> quickCheck idempotence
Falsifiable, after 14 tests:
[5,-1,-3]
ghci> quickCheck idempotence
Falsifiable, after 5 tests:
[1,0,-5,-5]
ghci> quickCheck idempotence
Falsifiable, after 11 tests:
[4,1,1]

Bei unterschiedlichen quickCheck-Aufrufen bekommen wir unterschiediche Gegenbeispiele für das angegebene Prädikat, da die Eingaben zufällig generiert werden.

Wir haben bei der Implementierung von qsort einen Fehler gemacht. Um diesen zu finden testen wir qsort für eines der von quickCheck gefundenen Gegenbeispiele.

ghci> qsort [4,1,1]
[1,1,4]
ghci> qsort [1,1,4]
[1,4]

Das Ergebnis nach dem zweiten Aufruf enthält eine 1 zu wenig. Wir passen die Definition daher wie folgt an und schreiben (>=x) anstelle von (>x):

qsort :: Ord a => [a] -> [a]
qsort []     = []
qsort (x:xs) =
  filter (<x) xs ++ x : filter (>=x) xs

Zumindest für die obige Eingabe funktioniert die Implementierung nun.

ghci> idempotence [4,1,1]
True

Wir verwenden wieder quickCheck um weitere Fehler zu suchen.

ghci> quickCheck idempotence
Falsifiable, after 8 tests:
[-1,-4,-3,2,-5]
ghci> quickCheck idempotence
Falsifiable, after 14 tests:
[3,2,2,-5]
ghci> quickCheck idempotence
Falsifiable, after 7 tests:
[3,2,-3]

Noch immer enthält unsere Implementierung einen Fehler:

ghci> qsort [3,2,-3]
[2,-3,3]

Wir haben die rekursiven Aufrufe vergessen:

qsort :: Ord a => [a] -> [a]
qsort []     = []
qsort (x:xs) =
  qsort (filter (<x) xs)
   ++ x : qsort (filter (>=x) xs)

Diese Implementierung ist augenscheinlich idempotent. Zumindest findet quickCheck kein Gegenbeispiel mehr.

ghci> quickCheck idempotence
OK, passed 100 tests.

Idempotenz ist eine notwendige Eigenschaft einer Sortierfunktion aber nicht hinreichend. Zum Beispiel wäre die Definition qsort _ = [] auch idempotent.

Als weitere Eigenschaft spezifizieren wir daher, dass alle Elemente aus dem Argument von qsort auch im Ergebnis vorkommen müssen und umgekehrt.

preservation :: [Int] -> Bool
preservation xs =
  null (xs \\ qsort xs) && null (qsort xs \\ xs)

Wir verwenden dazu die Funktion (\\) zur Berechnung der Differenz zweier Listen aus dem Data.List Modul.

Auch diese Eigenschaft ist augenscheinlich erfüllt:

ghci> quickCheck preservation
OK, passed 100 tests.

Jede Funktion, die eine Permutation ihrer Eingabe liefert, erfüllt die obige Eigenschaft. Wir könnten daher zusätzlich testen, ob das erste Element einer sortierten Liste das kleinste ist um zu testen, ob die Funktion richtig herum sortiert.

smallest_first :: [Int] -> Bool
smallest_first xs =
  head (qsort xs) == minimum xs

Die Funktion minimum berechnet das kleinste Element einer Liste und ist im Modul Data.List vordefiniert.

Wenn wir diese Eigenschaft mit quickCheck testen, erhalten wir einen Fehler.

ghci> quickCheck smallest_first
*** Exception: Prelude.head: empty list

Diese Eigenschaft ist nur für nicht-leere Listen sinnvoll und liefert mit der leeren Liste als Eingabe einen Patternmatch-Fehler.

QuickCheck stellt eine Funktion (==>) zur Spezifikation von Vorbedingungen bereit, die wir verwenden um die obige Eigenschaft anzupassen.

smallest_first :: [Int] -> Property
smallest_first xs =
  not (null xs) ==>
    head (qsort xs) == minimum xs

Durch die Verwendung von (==>) ändert sich der Ergebnistyp der Eigenschaft von Bool zu Property. Wir können sie aber weiterhin mit quickCheck testen.

ghci> quickCheck smallest_first
OK, passed 100 tests.

Häufig verwendet man statt einzelner Eigenschaften eine Referenz- oder Prototyp-Implementierung. Wenn man zum Beispiel eine offensichtlich korrekte aber ineffiziente Variante einer Funktion programmieren kann, kann man diese benutzen um eine effiziente Implementierung dagegen zu testen. Beispielhaft testen wir unsere qsort-Funktion gegen die vordefinierte sort-Funktion aus dem Data.List-Modul.

reference :: [Int] -> Bool
reference xs = qsort xs == sort xs

Für 100 von quickCheck generierte Eingaben vom Typ [Int] berechnet qsort das selbe Ergebnis wie die vordefinierte Sortierfunktion, was zu einigem Vertrauen in die Implementierung von qsort berechtigt.

ghci> quickCheck reference
OK, passed 100 tests.

Klassifikation der Testeingabe

Es gibt verschiedene Wege zu Informationen über die ausgeführten Tests zu gelangen. Die Funktion verboseCheck gibt alle Tests der Reihe nach aus, was allerdings meistens zu unübersichtlich ist. Deshalb gibt es Funktionen, die es erlauben Tests zu klassifizieren.

Mit der Funktion classify können Testfälle in Kategorien grupiert werden und so die Tests wie in einem Histogramm zu klassifizieren. Wenn wir das Referenz-Prädikat so implementieren

reference :: [Int] -> Property
reference xs =
  classify (length xs < 5) "small" $
    qsort xs == sort xs

erzeugt quickCheck die folgende Ausgabe:

ghci> quickCheck reference
OK, passed 100 tests (54% small).

Schließlich können wir auch die Längen selbst verwenden um Tests zu gruppieren.

reference :: [Int] -> Property
reference xs =
  collect (length xs) $
    qsort xs == sort xs

Danach gibt quickCheck aus wie viele Listen wie lang waren.

ghci> quickCheck reference
OK, passed 100 tests.
16% 0.
14% 1.
11% 2.
8% 4.
7% 7.
7% 6.
6% 3.
5% 5.
4% 9.
3% 21.
3% 13.
2% 8.
2% 17.
2% 15.
2% 10.
1% 31.
1% 29.
1% 25.
1% 24.
1% 23.
1% 22.
1% 19.
1% 11.

Es zeigt sich, dass Listen etwa bis zur Länge 30 generiert werden und kürzere Listen häufiger als lange. Man kann die Klassifikationen auch kombinieren wie das folgende Beispiel zeigt.

reference :: [Int] -> Property
reference xs =
  classify (length xs < 5) "small" $
  classify (length xs > 10) "large" $
    qsort xs == sort xs

Jede vierte der generierten Listen enthält mehr als zehn Elemente.

ghci> quickCheck reference
OK, passed 100 tests.
63% small.
25% large.

(Die Zahlen variieren leicht in unterschiedlichen Läufen von quickCheck.)

Eingabe-Generatoren

In QuickCheck legt die Klasse Arbitrary fest, wie für einen bestimmten Typ Testdaten erzeugt werden.

class Arbitrary a where
  arbitrary :: Gen a
  shrink :: a -> [a]

Hierbei ist Gen eine Monade, die Zufallsentscheidungen erlaubt. Wir werden später sehen, wie man Gen implementieren kann und beschränken uns zunächst auf die Benutzung. Die Funktion shrink wird verwendet um Gegenbeispiele zu verkleinern. Hierzu gibt man zu einem gegebenen Wert mögliche "kleinere" Testkandidaten an. Die Funktion ist als const [] vordefiniert.

Wir definieren einen Datentyp für kleine natürliche Zahlen, den wir verwenden um unsere QuickSort Implementierung zu testen.

newtype Digit = Digit Int
 deriving (Eq, Ord)

Damit QuickCheck Gegenbeispiele anzeigen kann, müssen wir eine Show-Instanz definieren. Anders als eine 'derivete' Instanz, lässt unsere den newtype-Konstruktor weg:

instance Show Digit where
  show (Digit d) = show d

Wir passen den Typ unserer Eigenschaft an um nur noch Listen von kleinen natürlichen Zahlen zu sortieren.

reference :: [Digit] -> Property
reference xs =
  classify (length xs < 5) "small" $
  classify (length xs > 10) "large" $
    qsort xs == sort xs

Wenn wir nun versuchen, quickCheck mit der angepassten Eigenschaft aufzurufen erhalten wie einen Typfehler.

ghci> quickCheck reference
No instance for (Arbitrary Digit)

QuickCheck weiß nicht, wie man Werte vom Typ Digit generiert. Wir müssen dies durch eine Aribitrary-Instanz festlegen.

instance Arbitrary Digit where
  arbitrary =
   do d <- oneof (map return [0..9])
      return $ Digit d

Die Definition von arbitrary für den Typ Digit wählt mit der Funktion oneof :: [Gen a] -> Gen a eine kleine natürliche Zahl zufällig aus und gibt diese als Digit-Wert zurück. Alternativ zu oneof (map return [0..9]) hätten wir auch choose (0,9) verwenden können. Die Funktion choose wählt zufällig einen Wert aus dem angegebenen Intervall.

Die vordefinierte Arbitrary-Instanz für Listen verwendet unsere Instanz für Digit um Werte vom Typ [Digit] zu erzeugen. Sie ist wie folgt definiert:

instance Arbitrary a => Arbitrary [a] where
  arbitrary = sized $ \n ->
   do l <- choose (0,n)
      sequence [ arbitrary | _ <- [1..l] ]

Die Funktion

sized :: (Int -> Gen a) -> Gen a

kann man verwenden um einen Generator, der Werte bis zu einer gewissen Größe erzeugt, zu definieren. In diesem Fall wird der Größen-Parameter n verwendet um die Länge der erzeugten Liste zu beschränken. Mit choose wird eine Länge zwischen 0 und n gewählt und dann mit sequence eine zufällige Liste entsprechender Länge erzeugt. Die Elemente der Liste werden durch einen Aufruf der Funktion arbitrary für den Element-Typ generiert.

Implementierung

Wir werden nun sehen, dass QuickCheck als Bibliothek in Haskell programmiert werden kann. Die hier vorgestellte Implementierung ist eine vereinfachte Variante der wirklichen Implementierung. Es fehlt zum Beispiel der Property-Typ und mit ihm die Möglichkeit, Vorbedingungen zu spezifizieren oder die Verteilung der Testeingabe zu berechnen. Unsere Variante unterstützt aber ansonsten beliebige Eigenschaften mit Ergebnistyp Bool. AUßerdem verwenden wir die etwas einfachere Implementierungsidee von Quickcheck 1.

Die Gen-Monade zur Erzeugung zufälliger Test-Eingaben greift intern auf einen Zufallsgenerator zu. Wir verwenden dazu die folgende Schnittstelle, die vom Modul System.Random bereit gestellt wird:

data StdGen

newStdGen :: IO StdGen
split     :: StdGen -> (StdGen,StdGen)
randomR   :: (Int,Int) -> StdGen -> (Int,StdGen)

Zufallszahlen-Generatoren sind vom Typ StdGen und können mit split in zwei unabhängige Generatoren zerlegt werden. Die Funktion randomR liefert eine Zahl aus dem angegebenen Intervall und einen neuen Zufallszahlen-Generator. Nur newStdGen zur Erzeugung eines Zufallszahlen-Generators ist eine IO-Aktion. Die anderen Funktionen sind rein funktional.

Zusätzlich zu einem Zufallszahlen-Generator haben Gen-Berechnungen auch Zugriff auf einen Parameter, der angibt, wie groß der generierte Wert höchstens sein soll.

newtype Gen a = Gen (Int -> StdGen -> a)

runGen :: Gen a -> Int -> StdGen -> a
runGen (Gen g) = g

Die Monadeninstanz für Gen ist ähnlich wie die der Zustandsmonade und fast genauso wie die der Umgebungsmonade (siehe Übung). Wir geben daher nur die Instanz an und verzichten auf einen Nachweis der Monadengesetze.

instance Monad Gen where
  return x = Gen (\_ _ -> x)

  a >>= f =
    Gen (\size rnd ->
         let (r1,r2) = split rnd
          in runGen (f (runGen a size r1)) size r2)

Bei der Implementierung von (>>=) ist zu beachten, dass die Berechnungen des linken und rechten Arguments mit unabhängigen Zufallszahlen-Generatoren ausgeführt werden.

Die choose-Funktion zur Definition eines Testfall-Generators für Zahlen definieren wir mit Hilfe der Funktion randomR.

choose :: (Int,Int) -> Gen Int
choose bounds =
  Gen (\_ rnd -> fst (randomR bounds rnd))

Wir ignorieren dabei den Größen-Parameter, rufen randomR mit den angegebenen Intervallgrenzen auf und ignorieren den Zufallszahlen-Generator, den randomR als zweites Ergebnis liefert.

Wir können choose verwenden um in der Definition von oneof einen zufälligen Index auszuwählen.

oneof :: [Gen a] -> Gen a
oneof [] = error "oneof empty list"
oneof xs =
 do n <- choose (0,length xs-1)
    xs !! n

Da man aus einer leeren Liste keinen Wert auswählen kann, brechen wir in diesem Fall mit einem Fehler ab.

Schließlich definieren wir noch die Funktion sized, die den Zugriff auf den Größen-Parameter ermöglicht.

sized :: (Int -> Gen a) -> Gen a
sized f = Gen (\size -> runGen (f size) size)

Der Größen-Parameter wird der Argument-Funktion übergeben und der resultierende Generator ausgeführt.

Als weiteres Beispiel für die Verwendung von sized geben wir die Default-Implementierung des Testfall-Generators für Int-Zahlen an:

instance Arbitrary Int where
  arbitrary = sized $ \n -> choose (-n,n)

Wir konstruieren damit eine Zahl, deren Betrag die gegebene Größe nicht übersteigt.

Wir wollen nun eine Funktion quickCheck definieren, die eine in Haskell programmierte Eigenschaft als Parameter nimmt und diese mit 100 zufälligen Eingaben testet. Bei einem fehlschlagenden Test soll zudem die Eingabe, die zum Fehlschlag führte, ausgegeben werden.

Wir definieren einen Typ Test für einen Testlauf, der eine String-Representation der Argumente und das Ergebnis des Tests speichert:

type Test = ([String],Bool)

Wenn das einzige Argument einer Eigenschaft Instanz der Klassen Arbitrary und Show ist, können wir die Eigenschaft in einen Generator für Test-Ergebnisse konvertieren.

genTest :: (Arbitrary a, Show a)
        => (a -> Bool) -> Gen Test
genTest p =
 do x <- arbitrary
    return ([show x],p x)

Dazu erzeugen wir ein zufälliges Argument mit arbitrary und wenden dann die Eigenschaft auf dieses Argument an. Zusätzlich geben wir im ersten Argument des Ergebnisses die String-Representation des Arguments zurück.

Diese Funktion können wir verwenden um eine quickCheck-Funktion für einstellige Eigenschaften zu implementieren.

quickCheck :: (Arbitrary a, Show a)
           => (a -> Bool) -> IO ()
quickCheck p = do rnd <- newStdGen
                  check 1 rnd (genTest p)

Wir erzeugen einen initialen Zufallszahlen-Generator und rufen dann die Funktion check auf, die den folgenden Typ hat.

check :: Int -> StdGen -> Gen Test -> IO ()

Das erste Argument ist ein Zähler für die Nummer des nächsten Tests. Das zweite Argument ist ein Zufallszahlen-Generator und das dritte ein Generator für Test-Ergebnisse.

check n rnd gtest
  | n > 100   = putStrLn "OK, passed 100 tests."
  | snd test  = check (n+1) r2 gtest
  | otherwise =
     do putStrLn $ "Falsifiable, after "
                ++ show n ++ " tests:"
        putStr . unlines $ fst test
 where
  (r1,r2) = split rnd
  test    = runGen gtest (n `div` 2 + 3) r1

Die check-Funktion führt 100 Tests aus es sei denn, einer schlägt fehl. In diesem Fall werden die Nummer des fehlschlagenden Tests und die den Fehlschlag verursachenden Argumente ausgegeben. Jeder Test wird mit einem neuen Zufallszahlen-Generator ausgeführt, damit nicht jedesmal die selbe Eingabe generiert wird. Die Größenbeschränkung berechnen wir mit einer linearen Gleichung aus der Nummer des Tests, so dass sie in späteren Tests immer größer wird.

Sowohl der Test-Typ als auch die check-Funktion erlauben mehrere Argumente für ein Test-Ergebnis. Der Typ der eben definierten quickCheck-Funktion erlaubt dagegen nur einstellige Eigenschaften. Wir wollen quickCheck nun so verallgemeinern, dass Eigenschaften mit beliebig vielen Argumenten getestet werden können.

Dabei stellt sich die Frage, welchen Typ quickCheck haben soll, wenn man es sowohl auf eine Funktion vom Typ Int -> Bool als auch auf eine vom Typ Int -> [Int] -> Bool anwenden können soll. Welcher Typ verallgemeinert die folgenden Typen und alle ähnlichen, d.h. solche, bei denen die übergebene Eigenschaft beliebig viele Argumente hat, die Instanzen der Klassen Arbitrary und Show sind?

quickCheck :: (Int -> Bool)          -> IO ()
quickCheck :: (Int -> [Int] -> Bool) -> IO ()

Wir können eine solche quickCheck-Funktion mit Hilfe von Überladung, also mit einer Typklasse, definieren. Dazu abstrahieren wir vom Typ der Eigenschaft.

quickCheck :: Testable p => p -> IO ()
quickCheck p =
 do rnd <- newStdGen
    check 1 rnd (genTest p)

Damit diese Definition typkorrekt ist, müssen wir die obige Definition von genTest durch eine Funktion der Typklasse Testable ersetzen.

class Testable p where
  genTest :: p -> Gen Test

Wir geben nun Instanzen dieser Klasse an, die es erlauben, Eigenschaften mit beliebig vielen Argumenten zu testen.

Zunächst definieren wir eine Instanz für Bool, was einer Eigenschaft ohne Argumente entspricht.

instance Testable Bool where
  genTest b = return ([],b)

Die Liste der Argumente ist in diesem Fall leer und das Ergebnis des Tests ist der übergebene Boole'sche Wert.

Außerdem definieren wir die folgende Instanz für Funktionen:

instance (Arbitrary a, Show a, Testable b)
      => Testable (a -> b) where

Diese Instanz macht auf einen Schlag Eigenschaften beliebiger Stelligkeit Testable, deren Argumente Instanzen der Klassen Arbitrary und Show sind. Zum Beispiel ist der Typ Int -> [Int] -> Bool eine Instanz von Testable, wenn der Typ [Int] -> Bool einer ist und dieser ist eine Instanz, wenn Bool einer ist, was der Fall ist.

Die Funktion genTest für Eigenschaften mit mindestens einem Argument definieren wir wie folgt.

  genTest p =
   do x <- arbitrary
      (args,ok) <- genTest (p x)
      return (show x:args,ok)

Zunächst wählen wir ein zufälliges Argument x, rufen dann die Eigenschaft p mit x auf und erzeugen rekursiv mit der genTest-Funktion der nächsten Instanz ein Test-Ergebnis. Diesem fügen wir als neues erstes Argument die String-Representation von x hinzu und erhalten das Test-Ergebnis zur Eigenschaft p.

Das 'echte' QuickCheck ist im Wesentlichen so definiert wie hier angegeben erlaubt aber neben der Definition von Vorbedingungen und der Klassifikation von Test-Eingaben gewisse Parameter, die wir fest eingebaut haben, zu konfigurieren. So ist es zum Beispiel möglich die Anzahl der auszuführenden Tests oder die Formel, nach der der Größen-Parameter berechnet wird, zu verändern.

Quelltextüberdeckung

Kombinatoren wie classify oder collect erlauben einen gewissen Einblick in die Art der durchgeführten Tests. Um zu beurteilen wie gründlich die Tests das Programm testen, wäre es aber hilfreich zu wissen, welche Teile des Programms von den Tests ausgeführt wurden und welche nicht.

Haskell Program Coverage (HPC) ist ein in den GHC integriertes Werkzeug, dass Statistiken darüber aufstellt, welcher Anteil eines Programms ausgeführt wurde. Diese Information kann auch in Form von farblich markiertem Programmtext im HTML-Format angezeugt werden. HPC eignet sich daher dazu, die von QuickCheck ausgeführten Tests zu bewerten und gibt Hinweise, was für Eigenschaften man gegebenenfalls hinzufügen sollte um noch gründlicher zu testen.

Zur Demonstration von HPC speichern wir die zuvor definierten Eigenschaften für die QuickSort-Funktion in einer Datei qsortChecks.hs zusammen mit einer main-Funktion, die alle Eigenschaften ausführt.

main =
 do quickCheck idempotence
    quickCheck preservation
    quickCheck smallest_first
    quickCheck reference

Wir geben nun beim Kompilieren das hpc-Flag an um später diie Quelltextüberdeckung protokollieren zu können.

bash# ghc -fhpc --make qsortChecks

Wenn wir die Datei ausführen, werden alle Eigenschaften von quickCheck überprüft und währenddessen eine Datei qsortChecks.tix geschrieben in der die Überdeckungsinformation enthalten ist.

bash# ./qsortChecks
OK, passed 100 tests.
OK, passed 100 tests.
OK, passed 100 tests.
OK, passed 100 tests.
bash# ls *.tix
qsortChecks.tix

Den Inhalt dieser Datei kann man mit dem Programm hpc verarbeiten. Zum Beispiel gibt der Aufruf

bash# hpc report qsortChecks

eine kurze Statistik über die verwendeten Programmteile aus:

100% expressions used (57/57)
100% boolean coverage (0/0)
     100% guards (0/0)
     100% 'if' conditions (0/0)
     100% qualifiers (0/0)
100% alternatives used (2/2)
100% local declarations used (0/0)
100% top-level declarations used (6/6)

Wir können diese Information auch visuell aufbereiten, indem wir einen HTML-Report generieren.

bash# hpc markup qsortChecks
Writing: Main.hs.html
Writing: hpc_index.html
Writing: hpc_index_fun.html
Writing: hpc_index_alt.html
Writing: hpc_index_exp.html

Dieser Aufruf generiert unterschiedliche HTML-Seiten mit Tabellen über die ausgeführten Programmteile. Außerdem wird für jedes Modul eine HTML-Version generiert, in der ausgeführte Teile fett und nicht ausgeführte Teile gelb markiert werden.

Bei mehreren Läufen von mit -fhpc kompilierten Programmen wird die Überdeckungsinformation in der .tix Datei akkumuliert. Dies schlägt fehl, wenn sich das Programm geändert hat. In soeinem Fall (oder wenn man alte Läufe ignorieren möchte) muss man die .tix Datei manuell Löschen, bevor man das Programm erneut ausführt.