© Alejandro Serrano Mena 2019
Alejandro Serrano MenaPractical Haskellhttps://doi.org/10.1007/978-1-4842-4480-7_15

15. Documenting, Testing, and Verifying

Alejandro Serrano Mena1 
(1)
Utrecht, The Netherlands
 

At this point you know many of the features and intricacies of the Haskell language and many of its libraries. This chapter won’t teach you any more about the language but rather will focus on some tools that help you in the process of coding libraries and applications. These tools support good engineering practices within Haskell.

An important and often overlooked practice as you program is to write good documentation for the source. Even though Haskell is a high-level language, there’s always room for documenting the purpose of each data type and function in your modules. Haddock is bundled with the Haskell Platform, and it creates beautiful documentation pages from special comments in your code.

The main set of tools I will cover is related to testing. Automatically testing your code ensures that any change in the code does not affect the behavior that it should have. Programmers today see unit testing as an essential activity, and you will learn how to create unit tests in Haskell with HUnit.

Haskell was the first language to support randomized testing in addition to unit testing, with its QuickCheck library. This form of testing generates random calls to your functions and ensures that certain properties of the output are satisfied, freeing the tester from the task of writing hundreds of test cases. Another tool called SmallCheck builds on this idea but performs exhaustive testing . This means a certain piece of code is called not with random inputs but with all possible inputs up to a size limit.

Testing can show that a bug exists in your implementation but testing along does not give you complete assurance of their absence. The next step is to formally verify that the implementation satisfies the properties that are requested. You’ll get a glimpse of how this can be done using LiquidHaskell, an extension of Haskell with refinement types.

Documenting Binary Trees with Haddock

Binary trees, like those in Chapter 4, are going to be the working example throughout this chapter. As a reminder, the following is the definition of the BinaryTree data type. The constructors refer either to a leaf or to a node that handles some inner information on it. In addition, there are a couple of tree functions.
data BinaryTree a = Leaf
                  | Node a (BinaryTree a) (BinaryTree a)
                  deriving (Show, Eq)
treeInsert :: Ord a => a -> BinaryTree a -> BinaryTree a
treeInsert x Leaf = Node x Leaf Leaf
treeInsert x (Node y l r) | x <= y    = Node y (treeInsert x l) r
                          | otherwise = Node y l (treeInsert x r)
treeMerge :: Ord a => BinaryTree a -> BinaryTree a -> BinaryTree a
treeMerge t Leaf         = t
treeMerge t (Node x l r) = treeInsert x $ treeMerge (treeMerge t l) r

Even without any extra comments, you can generate a summary of the modules in the package by running cabal haddock or stack haddock in the root of your project. A set of HTML pages will be created in the dist/doc/html folder in your package if using Cabal, or .stack-work/install if using Stack. If you open them, you’ll see the documentation in the same format in which the documentation from Hackage is presented. However, the information there is rough: only a list of modules and, inside each module, a list of all the definitions. It would be nice to incorporate comments and examples into each of the functions, data types, and type classes.

The way you can convey extra information to be included in those HTML pages is via documentation comments . Documentation comments are written in the same file where the code is written, which helps you keep both code and documentation in sync. They follow the same syntax as regular comments, but they start with a special marker. This idea is found in other documentation systems such as Javadoc and Doxygen.

The marker in the comment changes depending on whether you want to include the documentation of an element before or after the declaration. If you want to write the documentation and then the element, you will mark that documentation with |; if instead you want to include the documentation after the element, start your comment with ^. Comments beginning with | are used normally for documenting data types, functions, and type classes, whereas ^ is more often found while discussing constructors and function arguments. As an example, you can document the BinaryTree type as follows:
-- | A typical binary tree
data BinaryTree a = Node a (BinaryTree a) (BinaryTree a) -- ^Inner nodes
                  | Leaf                                 -- ^Leaves
                  deriving (Eq, Show)
The upcoming Figure 15-1 shows how the comments here manifest themselves in the HTML page created by the Haddock tool.
../images/316945_2_En_15_Chapter/316945_2_En_15_Fig1_HTML.jpg
Figure 15-1

BinaryTree documentation generated by Haddock

Caution

Haskell single-line comments start with -- followed by a space. You should respect this syntax in documentation comments and use a space between -- and either | or ^, as the example shows.

Haddock has a rich syntax for writing the documentation.

  • If you refer to other declarations by writing it in single quotes, Haddock will generate a link to that place. This functionality is also available for linking to modules; in that case, you need to write its name in double quotes.

  • Unnumbered lists are declared by prefixing each of the items by *. In the case of numbered lists, you can choose between writing n. or (n) for the nth element. Be aware that each item should be surrounded by blank lines.

  • You can introduce pieces of code by prefixing each line with >. Additionally, Haddock supports the declaration of properties, which are prefixed by prop> and of interpreter examples, in which the input is written after >>> and the output immediately after.

Here you can see an example of documentation for the treeInsert function. Notice that the comments are written in multiple-line style. Again, you can see the effect of these comments in Figure 15-1.
{-|
Inserts an element into a 'BinaryTree'
 * If it finds a leaf, insert there
 * If smaller than the item in the node, insert in the left
 * If larger than the item in the node, insert in the right
>>> treeInsert 1 Leaf
Node 1 Leaf Leaf
-}
treeInsert :: Ord a => a -> BinaryTree a -> BinaryTree a
treeInsert x Leaf = Node x Leaf Leaf
treeInsert x (Node y l r) | x <= y    = Node y (treeInsert x l) r
                          | otherwise = Node y l (treeInsert x r)
Another interesting feature of Haddock is the ability to organize the declarations in your code and to show its documentation divided into sections. The only requirement is that you must use an explicit export list. This is a good programming practice anyway, so it shouldn’t put any extra burden on you. In the list of exports, you can include a documentation comment starting with * to indicate that a new section starts at that point, or you can use ** for a subsection. Here’s a possible declaration list for a full-blown binary trees implementation:
-- | Simple implementation of binary trees
module Chapter15.BinaryTree (
  -- * The main data type
  BinaryTree(..),
  -- * Operations
  -- ** Insertion
  treeInsert, treeMerge,
  -- ** Lookup
  treeFind, treeFindMin,
  -- ** Removal
  treeDelete
) where

If you look carefully at Figure 15-1, you will notice some hyperlinks labeled as Source. The target of each of those links is the definition of that element in a colored version of your source. You can get them in your own documentation by running cabal haddock --hyperlink-source instead of plain cabal haddock. Notice that you need to have the package hscolour in your system for this feature to work.

HLint

A Haskell compiler checks whether your source code complies with the syntax and semantics of the language. However, there are cases where your code is correct but it’s not easy to read or contains some fragment that is usually seen as confusing and may lead to errors in the future. HLint is a tool that suggests changes to Haskell source in order to make the code much clearer.

You can get HLint onto your system by the usual procedure of running cabal install hlint on the command line. Then you can run hlint <source file> and get a list of suggestions. For example, say you change the third line of treeInsert to read as follows:
treeInsert x (Node y l r) | (x <= y) = Node y (treeInsert x l) r
If you run HLint, the following change will be suggested:
src/Chapter15/BinaryTree.hs:39:29: Warning: Redundant bracket
Found:
  (x <= y)
Why not:
  x <= y

HLint covers many style issues in code. HLint is also aware of laziness, so it ensures that your code never evaluates more – which could have a negative performance impact – when suggesting a change. Furthermore, HLint can apply the suggestions directly to your code.

Unit Testing with HUnit

Unit testing is a methodology for checking that your functions perform their work as intended. Following these methods, the programmer writes a set of test cases, with each of them executing a piece of code and describing the expected result. These tests can be run at the developer’s discretion or can be used to check automatically that code that was working fine doesn’t break after changes (this is called regression testing ).

To provide a unified interface to the various testing methods available, the Haskell community has created several test frameworks. In this section I’ll introduce the Tasty library, but many others are available. HTF, test-framework, and HSpec are other interesting options. The good news is that any of these test frameworks can be integrated into your Cabal project and run through the same command-line option.

Declaring Tests in Cabal

In principle, you could create the application that runs your tests as a mere executable in your package. However, Cabal embodies the idea of tests in its core and has special support for them. In this section you’ll learn how to add a test executable to your Cabal project.

Inside a Cabal file, a test is defined in its own stanza, like library and executable parts were. Thus, the declaration of a test inside the project file is headed by test-suite followed by the name of the test suite. The key field to include in that stanza is the type one. Cabal has extensible support for different kinds of test providers that can run the tests in the project in different ways.

The focus in this section will be on type being equal to exitcode-stdio-1.0, which is the best-supported option at the moment of writing. By specifying that test provider, you declare to Cabal that your tests should be compiled as an executable file. The file will run to execute the tests and will tell Cabal whether the tests were successful via its exit code. The good news is that all the test frameworks in Hackage are knowledgeable about this way of running them and make it easy to integrate them as a Cabal test.

The rest of the test-suite stanza , when type is exitcode-stdio-1.0, is equal to the definition of a regular executable. As an example, here’s the stanza corresponding to the tests of the current chapter, which has the Tasty framework as a dependency, along with the packages needed to run tests from HUnit, QuickCheck, and SmallCheck within Tasty:
test-suite Tasty
  type:             exitcode-stdio-1.0
  build-depends:    base >= 4, tasty, tasty-hunit,
                    tasty-quickcheck, tasty-smallcheck
  hs-source-dirs:   test
  main-is:          Tasty.hs
  default-language: Haskell2010

Notice that I’ve declared that the source files for my tests will reside in the test directory. It’s a good practice to keep source code and tests in different folders to make it easier to find the place where you include new functionality or new checks of behavior.

There’s one final quirk to consider. Often you’ll need to access the functions declared in your library stanza inside a test-suite one. One possibility is to reference the source folder also in your test-suite stanza. However, this causes double compiles (the same file has to be compiled in both the library and test-suite stanzas) and doesn’t delimit the responsibility of this stanza. Instead, Cabal supports having a test suite or executable in a Cabal project depend on its library part. To declare this dependency, just add the name of the package in the corresponding build-depends list. For example, in the previous case you’ll get the following:
  build-depends:    base >= 4, tasty, tasty-hunit,
                    tasty-quickcheck, tasty-smallcheck,
                    chapter15

Now you’re ready to run the tests that you’ll declare in the next section through the cabal or stack command-line tools. This functionality is quite useful because it centralizes all the project information in a single place.

Writing Unit Tests

First you need to create the test/Tasty.hs file that the stanza specifies as the main file. This file should contain a module named Main. The main executable file of a stanza is the only exception to the rule of naming both the file and the module with the same identifier, making it easier to create projects with more than one executable or test. The examples will use the Tasty test framework and the HUnit tool, so you should import the corresponding modules. The following skeleton will be the base for the rest of the section:
module Main where
import Test.Tasty
import Test.Tasty.HUnit as HU
A test suite in Tasty is composed of basic test cases that you can later group to get a hierarchical organization. Test cases are different depending on the testing tool you would like to use (HUnit, QuickCheck, or SmallCheck). In the case of HUnit, a test case is defined by the testCase function, which takes as arguments a name and an assertion, which encodes the specific functionality to be checked. For example, the following test case checks that the result equality of inserting 1 into an empty tree is the expected one using the HUnit combinatory assertEqual.
import Chapter15.BinaryTree
hunitTestInsertOnLeaf :: TestTree
hunitTestInsertOnLeaf = HU.testCase "Insert 'a' on empty tree" $
  assertEqual "Insertion is wrong"
              (treeInsert 'a' Leaf) (Node 'a' Leaf Leaf)

Note

TestTree is one of the types used in the Tasty framework. It’s not related to the binary trees you’ve been using as examples throughout the chapter.

As discussed, Tasty allows a hierarchical organization of the test cases into test groups. A test group is defined via the testGroup function, which needs to be given a name for the group and a list of elements. Those elements can be nested groups or basic test cases. Here’s an example of an organization of tests:
allTests :: TestTree
allTests = testGroup "Tasty Tests" [
    testGroup "HUnit Tests" [ hunitTestInsertOnLeaf ]
  ]

In this case there’s a top-level group called “Tasty Tests” that has another group called “HUnit Tests” inside. This nested group is where the code puts the test case defined previously.

There’s one last step before being able to run the tests. Since you declared that an executable will be responsible for automatically executing them, you need to provide a main entry point. The good news is that Tasty includes a simple function for this task, which you can include in all your tests. You just need to specify the test case or test group that will be run to defaultMain, as follows:
main :: IO ()
main = defaultMain allTests
It’s time to execute this first test. It is as easy as running cabal test or stack test, depending on your choice of build tool. In either case the test suite will be executed, and the main results are shown on the screen.
$ cabal test
Running 1 test suites...
Test suite Tasty: RUNNING...
Test suite Tasty: PASS
Test suite logged to: dist/test/chapter15-0.1-Tasty.log
1 of 1 test suites (1 of 1 test cases) passed.
If you now go to the log file shown in the message, you can see a more detailed explanation of the test suite run.
Tasty Tests
  HUnit Tests
    Insert 1 on empty tree: OK

As you can see, the file shows the hierarchical structure declared in the source file.

In addition to “long” combinators such as assertEqual, HUnit includes infix combinators that allow a more concise expression of expected equality. These are (@?=) and (@=?). Both operators check whether the elements at each side are equal. The difference is in where one writes the value to check and where the value is known to be correct. The rule of thumb is that the former should be written next to the ? sign, and the latter (the expected value) should be written next to the = sign. Thus, the previous example could have also been written in the following two forms. Remember that the expression with treeInsert is the one to check, so it should be near the ? sign.
hunitTestInsertOnLeaf' = HU.testCase "Insert 'a' on empty tree" $
  treeInsert 'a' Leaf HU.@?= Node 'a' Leaf Leaf
hunitTestInsertOnLeaf" = HU.testCase "Insert 'a' on empty tree" $
  Node 'a' Leaf Leaf HU.@=? treeInsert 'a' Leaf
Equality is the most common check in unit tests, but HUnit also allows you to check a Boolean property on the result. For example, you could check that after inserting an item in the tree, that item can be found. In this case, let’s create a template for several unit tests by creating a function that returns a test case given an original tree and the item to insert.
import Data.Maybe
hunitTestInsertFind :: Ord a => a -> BinaryTree a -> TestTree
hunitTestInsertFind e t = HU.testCase "Insert can be found" $
  assertBool "Cannot find element" (isJust $ treeFind e $ treeInsert e t)
As in the previous case, HUnit has a more concise version of the assertBool combinator, namely, (@?).
hunitTestInsertFind' e t = HU.testCase "Insert can be found" $
  (isJust $ treeFind e $ treeInsert e t) HU.@? "Cannot find element"
Now you can add several unit tests to your list by providing different parameters to this template.
allTests = testGroup "Tasty Tests" [
    testGroup "HUnit Tests" [
      hunitTestInsertOnLeaf
    , hunitTestInsertFind 'b' Leaf
    , hunitTestInsertFind 'c' (Node 'd' Leaf Leaf)
    ]
  ]

HUnit is a small library, but it embodies the most common uses of unit testing. In Exercise 15-1, you will write some extra tests to check the implementation of binary trees. Following the exercise, you will learn a little about a framework named HSpec.

Exercise 15-1.Unit Testing Binary Trees

Write test cases to check that once you add an element to a binary tree, the size (the number of internal nodes) is increased by 1. Additionally, write test cases to check that deleting an element indeed removes it from the binary tree.

Hspec

In this chapter, the test framework used to integrate all the tests is Tasty. However, as mentioned earlier, several other test frameworks are available in Hackage. Hspec is one of them and is targeted at teams that use the Behavior-Driven Development (BDD) methodology. Here’s an example of the usage:
import Data.Maybe
import Test.Hspec
import Test.HUnit
main = hspec $ do
  describe "Insertion in binary tree" $ do
    it "Inserts correctly 1 in empty tree" $
      treeInsert 1 Leaf @?= Node 1 Leaf Leaf
    it "Finds 1 after inserting it on a tree" $
      isJust $ treeFind 1 $ treeInsert 1 (Node 2 Leaf Leaf)
    it "Gets the minimum correctly" $
      pendingWith "Needs to be implemented"

As you can see, Hspec embodies a more textual style for describing tests. The aim is to be closer to the language used in the specification phase, making it easier to write the tests that check that a further implementation is correct.

Randomized Testing with QuickCheck

Unit testing is the most common approach to checking that your implementation satisfies the requirements. However, unit testing imposes quite a big load of work. For each requirement, you need to create several test cases, which you must ensure cover a big enough number of possible scenarios. Typically, you include test cases for extreme values, empty collections, invalid data, and so on.

Instead of having to think about all this by yourself, it would be great if you could express your specifications at a higher level and then test whether those properties hold for your program. Haskell’s usage of higher-order functions makes it easy to express those properties. For example, the property “reversing a list twice is the same as leaving it as is” can be written as reverse . reverse = id. The bad news is that doing so automatically is a task that’s impossible to achieve for every single property in the wild (but you’ll see in the next section how formal verification can help you in those cases where an entire proof of correctness is possible).

QuickCheck tries to bring these two worlds together. Using this library, you express how your program should behave in the form of high-level properties. Then, the tool creates a lot of random values that your program is tested against. If you use a sufficiently large set of tests (hundreds or thousands), your confidence in that property holding is increased. Furthermore, QuickCheck includes a shrinking component that is used when a value that doesn’t satisfy your specification is found. Its task is trying to make that value as small as possible, helping you in reproducing and tracking the source of the bug.

Testing List Properties

Let’s start by testing some simple properties of list functions. In particular, let’s focus on the reverse function, which builds a list in the opposite order. The initial implementation will include a small error so you can see how Tasty shows the problems of a failing QuickCheck test.
reverse' :: [a] -> [a]
reverse' []     = []
reverse' [x]    = [x, x]
reverse' (x:xs) = reverse' xs ++ [x]
For the first property, you may want to check that the length of a list is respected by reversing it (of course, this is false in this example). Here’s the corresponding definition for that QuickCheck property:
{-# LANGUAGE ScopedTypeVariables #-}
import Test.Tasty.QuickCheck as QC
reverseTests :: TestTree
reverseTests = testGroup "Tests over reverse"
  [ QC.testProperty "reverse respects length" $
      (lst :: [Integer]) -> length (reverse' lst) == length lst ]

As you can see, the definition starts similarly to an HUnit test. You call the testProperty function and give a name to the property. Then, you define the body of the property as a function, which should hold for every possible value of the arguments of that function. In other words, you can think of the property as having “for all” before each of the arguments to the body function.

Note

In some cases you will need to restrict the types of the arguments to QuickCheck properties. The reason is that it’s not possible to create random values for every possible type in Haskell. For example, you cannot generate a list of functions. Thus, in the example, the code works only for lists of integers, even though the reverse' function is applicable to any kind of list.

If you add reverseTest to the list of Tasty tests that was called allTests and then build and run the new set of tests, you should get an error message.
Test suite Tasty: RUNNING...
Tasty Tests
  Tests over reverse
    reverse respects length: FAIL
      *** Failed! Falsifiable (after 3 tests and 3 shrinks):
      [0]

The message is telling you that after trying three times, it was able to find an example where the property does not hold (although given that QuickCheck tests in a random fashion, the number in the counterexample may be different in your case). Then, it shrank the list until it made the example small. Indeed, a singleton list is the smallest example where the reverse' function fails.

Test your understanding of QuickCheck by doing Exercise 15-2.

Exercise 15-2. Quickchecking Reverse

Add more QuickCheck properties on the reverse' function that was defined at the beginning of the section. For example, applying it twice returns the original result (reverse' . reverse' == id), or the head of the list is the last element of the reversed list.

After checking that the properties do not hold for the initial implementation, change the code to be correct. Does the new version pass all the tests?

Testing Binary Tree Properties

Testing lists is interesting, but in most of the cases you are going to be creating tests of your own data types. To create such tests on a given type, you must provide QuickCheck with a generator of random values of that type. You do so by creating an instance of the Gen type class, which you do by implementing the arbitrary function. You can use several tools to generate random values of binary trees.

  • You can generate values of other data types by calling their corresponding Gen instance. In the case of binary trees, this should be done for the elements in the nodes.

  • You can make a random choice between several generators via the oneof function, which takes a list of them and at runtime gives back one of the specified generators. A more refined version of oneof is frequency, which in addition to the possible outcomes includes a relative frequency in which each generator should appear. You’ll see how to use this latter function to decide at each point whether to generate a node or a leaf of the tree.

  • If you need your values to satisfy a certain condition, you can add a call to suchThat. This function will make sure that the given predicate holds for the random values.

One of the most important properties of a random generator is that it should stop and produce a value at some point. QuickCheck refines that idea and asks the generators to give back values of a certain maximum size . Think of the size as some intrinsic measure of “how big” a value is. The length of a list, the number of leaves in a tree, and the absolute value of an integer are some examples of these sizes. If your data type admits this idea, you can get the information of the wanted size via the sized QuickCheck function.

For the working example, the idea of size makes sense: it’s the maximum number of levels that the tree may have. The strategy for generating random trees to satisfy this property is to choose between creating a leaf or a node with a decreasing probability for the second of those choices. If the generation reaches the point in which the size of the tree must be 0, it just returns a Leaf. Here’s the translation of this idea into code:
instance Arbitrary a => Arbitrary (BinaryTree a) where
  arbitrary = sized $ ->
    if (n == 0)
       then return Leaf
       else frequency [(1, return Leaf),
                       (n, resize (n-1) arbitrary)]
If you look at the Gen type class, you’ll notice another function, which has the responsibility of shrinking a value into smaller parts. For a given value, shrink should return the list of those smaller pieces that should be checked. In the case of binary trees, the natural choices are the subtrees of a given tree, as this code shows:
  shrink Leaf         = []
  shrink (Node _ l r) = [l, r]
Armed with this instance, you can test properties of binary trees. After inserting an item, let’s check that it can be found in the tree. The declaration of that test is the following:
qcTestInsert :: TestTree
qcTestInsert = QC.testProperty "insert => you will find it" $
  (n :: Int) t -> treeFind n (treeInsert n t) == Just n
Another possible test is checking that if you insert and delete an element from a tree, you can no longer find that element. Here it is in QuickCheck terms:
qcTestDelete = QC.testProperty "delete => not find it" $
  (n :: Int) t -> (treeFind n $ treeDelete n $ treeInsert n t) == Nothing

However, if you think about it, this is not a correct property to check. It may be the case that the tree t did have a copy of the element n, so inserting and deleting the item will leave that initial copy. Thus, the result of treeFind will not be Nothing, but Just n.

The solution is telling QuickCheck that the random items to test need to fulfill some precondition (in this case, that it doesn’t contain the number n initially). This is done via the (==>) combinator, which takes as arguments the Boolean condition to satisfy and the actual property body. Here’s an example:
qcTestDelete = QC.testProperty "delete => not find it" $
  (n :: Int) t ->
     (treeFind n t == Nothing) QC.==>
     (treeFind n $ treeDelete n $ treeInsert n t) == Nothing

These examples show how QuickCheck allows you to get a higher-level view on the tests. Instead of focusing on single test cases, you declare properties, which are closer to the original specification.

SmallCheck

QuickCheck uses random data to test properties of your code. SmallCheck follows a similar spirit, but instead of creating random values, it tests properties with every possible value from a set. For example, you could check the reverse . reverse == id property on every list up to a certain length.

The public interface of SmallCheck is almost the same as that of QuickCheck. It’s also integrated in almost every Haskell test framework, including Tasty and Hspec

Formal Verification with LiquidHaskell

Testing is a very useful tool to gain confidence about your code performing correctly. But even when using randomized testing, your code only runs on a subset of all possible inputs. There are other techniques which give you full guarantees over your code, these are collectively known as formal verification. Although these techniques differ in many conceptual and technical aspects, in all cases the workflow consists on describing the intention of your code in some formal language, and the running some tool (maybe completely automatic, maybe with some human intervention) to verify that the code complies with that specification.

The type system in Haskell can be seen as a form of formal verification, in which types are the formal language and the compiler automatically checks for compliance. Stronger type systems, like dependent types, allow for more invariants to be express and checked. In this section we are going to introduce LiquidHaskell, which extends regular Haskell with refinement types . In a nutshell, a refinement type is the combination of a type (in the usual sense) with a predicate over the values. For example, “integers with are greater than 0” combines the type “integer” with the predicate “greater than 0”. The main selling point of LiquidHaskell is that you do not need to learn other language to implement your code, only a refined version of types to describe your specification.

Installing LiquidHaskell

Obtaining LiquidHaskell is as simple as running cabal install liquidhaskell in the command line. Unfortunately, a successful installation does not mean that everything is in place to verify your programs. In addition you need Z3, a so-called SMT solver, which is used internally by LiquidHaskell to verify the assertions. At the moment of writing you can get binaries for Z3 at https://github.com/Z3Prover/z3/releases . Regardless of the operating system, both liquid – LiquidHaskell’s main executable – and z3 need to the on your PATH.

At the moment of writing, LiquidHaskell is not compatible with the latest version of GHC, only with the 8.4 series. If you are using a newer version of the compiler, my suggestion is to follow the instructions in LiquidHaskell’s repository1 and install LiquidHaskell using Stack.

As an example of usage of LiquidHaskell, we are going to verify some properties of the BinaryTree type introduced in the Haddock section (which I assume you have imported or copied verbatim from that section). Let’s start with a simple treeSize function, which gives you the number of nodes in the tree. The code is straightforward; the interesting part is the annotations between {-@ and @-}. Those annotations, in addition to your code, are the input to LiquidHaskell. The most important one is the second one, which refines the type signature of treeSize. In particular, it states that the output of the function is not any integer, but an integer greater or equal to 0. The refined type Nat is defined in LiquidHaskell’s standard library.
{-@ LIQUID "--no-termination" @-}
{-@ treeSize :: Tree a -> Nat @-}
treeSize :: Tree a -> Int
treeSize Leaf         = 0
treeSize (Node _ l r) = 1 + treeSize l + treeSize r

You can verify that the function obeys its specification by running liquid File.hs in the command line. If everything is fine the text SAFE appears in your screen. You can try to break this invariant and see how LiquidHaskell no longer accepts the code.

Note

The other annotation instructs LiquidHaskell for not checking whether your functions terminate for all inputs. This is another of the interesting features of LiquidHaskell (in fact, very few of your functions should loop indefinitely) but we shall not focus on it.

Now that treeSize has been accepted by LiquidHaskell, we can use it to describe a certain property of binary trees, namely, their size. To instruct the verifier to do so, we need to declare it as a measure . Not every function can be used as a measure, but when that is possible the workflow becomes easier. For the rest of the cases LiquidHaskell supports reflection of functions.
{-@ measure treeSize @-}
Going back to our example in the Haddock section, here is an annotation for the treeInsert function we defined back there, along with an incorrect implementation. The annotation declares that if you insert a value x on a binary tree v, the size of the resulting tree w is one more than that of v. As you can see here, the general syntax of a refinement type is {name: Type | predicate}.
{-@ treeInsert :: x: a -> v: BinaryTree a
               -> {w: BinaryTree a | treeSize w = treeSize v + 1} @-}
treeInsert :: Ord a => a -> BinaryTree a -> BinaryTree a
treeInsert x Leaf = Node x Leaf Leaf
treeInsert x (Node y l r) | x <= y    = Node y l r
                          | otherwise = Node y l (treeInsert y r)
If you run LiquidHaskell over this code, you get the following error message:
LiquidHaskell.hs:24:17-26: Error: Liquid Type Mismatch
24 |   | x <= y    = Node y l r
                      ^^^^^^^^^^
   Inferred type
     VV : {v : (BinaryTree a) | treeSize v == (1 + treeSize l) + treeSize r
                                && treeSize v >= 0}
   not a subtype of Required type
     VV : {VV : (BinaryTree a) | treeSize VV == treeSize ?a + 1}

This error message tells you that the second branch of the function does not obey its specification. Indeed, the size of the tree is not increased in that case.

Caution

One of the weak points of LiquidHaskell is the poor explanations given whenever the specification is not followed. In most cases you just get a pair of expected versus actual refinement types, but no indication of why the latter is not good enough.

That bug is not the only one present in the code (can you find it before I tell you where it is?). However, the second bug does not relate to the size of the binary trees, but about the elements which are present. To keep track of that property, we define a new function treeElements and declare it as an additional measure.
import Data.Set
{-@ measure treeElements @-}
treeElements :: (Ord a) => Tree a -> Set a
treeElements Empty        = empty
treeElements (Node x l r) = singleton x `union`
                            treeElements l `union` treeElements r
The second step is to refine the signature to introduce a new property that the function must obey. If you insert a value x in the tree v, regardless of what happens, the value x should be present in the output tree w.
{-@ treeInsert :: x: a -> v: BinaryTree a
               -> {w: BinaryTree a | treeSize w = treeSize v + 1
                                     && member x (treeElements w) } @-}

The error message has been left out for conciseness, but it points directly towards the third equation in treeInsert. Indeed, it your read instead Node y l (treeInsert x r), in the original version the value x is lost if it is greater than y.

Describing Binary Search Trees

In the previous section we have been treating binary trees as binary search trees in an implicit way. By using treeInsert you always get a tree in which all values at the left of a node are less or equal than the value in that node, and conversely the ones in the right subtree are greater than the value. This invariant is not present in the Haskell definition of SearchTree (which is just a copy of BinaryTree with renamed constructors), but we can make LiquidHaskell aware of it using an annotation.
data SearchTree a = EmptyS | NodeS a (SearchTree a) (SearchTree a)
                  deriving (Show, Eq, Ord)
{-@ data SearchTree a = EmptyS
                      | NodeS { x:: a
                              , left  :: SearchTree {v: a | v <= x}
                              , right :: SearchTree {v: a | v >  x} }
@-}
To understand the annotation, it is important to realize that by writing SearchTree {v: a | predicate} we are refining the elements of that search tree, not the structure of the search tree itself. Here is an example of a function which does not obey the invariant: we create a node without checking that the elements in t1 are smaller than the value x, not t2 greater than x.
wrong :: a -> SearchTree a -> SearchTree a -> SearchTree a
wrong x t1 t2 = NodeS x t1 t2
LiquidHaskell.hs:69:17-26: Error: Liquid Type Mismatch
 69 | wrong x t1 t2 = NodeS x t1 t2
                      ^^^^^^^^^^
   Inferred type
     VV : a
     not a subtype of Required type
     VV : {VV : a | VV <= x}
     In Context
     x : a
As a final example, we can copy treeInsert and make it work on our new SearchTree type. The previous properties based on size and element were enough to detect some errors, but not to find this bug in which x and y are mixed:
treeInsertS :: Ord a => a -> SearchTree a -> SearchTree a
treeInsertS x EmptyS = NodeS x EmptyS EmptyS
treeInsertS x (NodeS y l r)
  | x <= y    = NodeS x (treeInsertS y l) r
  | otherwise = NodeS y l (treeInsertS x r)

To check that you understand how LiquidHaskell works, Exercise 15-3 asks you to implement some more functions over trees.

Exercise 15-3. Verifying Binary Trees

Try to write a merge function, on both binary trees and search trees. The signature for this function should be:
mergeTree :: Tree a -> Tree a -> Tree a

This function should combine both trees into a single one with all the elements. Think about properties such as: how does the elements and size look like?

This was just a brief introduction to LiquidHaskell. Some details we have left without treatment are LiquidHaskell’s ability to check termination (you never go into an infinite loop) and totality (you cover all possible cases) of your functions. Also, the properties we checked upon trees where quite simple, but there is much more you can do. One important subset is dependent properties, in which the refinement of an argument depends on the value of the previous one. Finally, LiquidHaskell gives you the power to not only automatically check for compliance with respect to a specification, but also to prove manually properties about your program in an equational reasoning style.

Summary

The focus of this chapter was on tools that help with the testing and maintainability of Haskell code bases.

  • Haddock is the preferred tool for associating pieces of documentation to Haskell declarations and creating beautiful visualizations for it.

  • Cabal has support for including tests in packages. You learned how to declare a test-suite stanza and got familiar with several Haskell test frameworks: Tasty and Hspec.

  • The HUnit library for unit testing was introduced.

  • You read about the benefits of randomized testing and learned how to create these kinds of tests using the QuickCheck library.

  • As a final touch, you saw examples of how to formally verify your code by annotating it and running it through LiquidHaskell.

..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.
Reset
18.191.14.196