Hypomnemata

I’ve recently been working my way through Write Yourself a Scheme in 48 Hours. This is a guided tutorial through implementing a Scheme interpreter in Haskell. It’s been really fun, and a nice change from my current contract (which involves a lot of screwdriver turning and other sysadmin duties).

That said, there is one big change that I’d like to see made in the text: build it with unit tests! I’m not a total test-driven disciple, but I do believe they’re a fantastic tool, and this is a great place to use them.

Parsing is incredibly test-friendly: you have an input string, and an expected output parse tree. It’s totally deterministic, with no random numbers, no ambiguities, and no pesky humans. There are a lot of interacting components, especially in terms of nesting, which are hard to keep in mind when manually “testing” things.

In addition, the “here’s code, extend it to do X” pattern used in the text benefits from having comprehensive tests. In working the homework exercises, you’re going to refactor big chunks of code. As you do so, you should be worried about breaking the hell out of your existing code (if you’re not worried, you’re either brilliant, inexperienced, or inattentive). There’s no better way to assuage those worries than unit tests, and, as you find broken things, adding regression tests. It gets even better if you add code coverage, guaranteeing that you’re exercising all codepaths via your tests.

Another wrinkle that makes you want tests: as you work through the book, you merge your existing code into the next snippet of example code. This is often an error-prone process, and having tests to catch mistakes is great. This is the reason I broke down and refactored the code for testing. I started getting into the interesting stuff at the end of chapter two, and suddenly my strings weren’t parsing properly. Upon examination, I found I’d merged my code into the next sample code incorrectly, and left my parseString implementation behind.

So, with all that in mind, let’s make Write Yourself a Scheme more test-friendly. The first step is to factor the parser implementation out into its own module. This is really easy: we create WYAS.hs, containing everything but main, and change the module line to:

module WYAS where

We’ll also need to extend LispVal a little bit, too. We want to be able to compare them, so we’ll add deriving(Show, Eq) immediately after the definition:

data LispVal = Atom String
             | List [LispVal]
             | DottedList [LispVal] LispVal
             | Number Integer
             | Float Float
             | String String
             | Char Char
             | Bool Bool
             deriving (Show, Eq)

Don’t worry about what “deriving()” means here; it’s just some Haskell typeclass voodoo that lets us now show (Char 'x') and have it do something useful, as well as allowing us to compare two LispVals for equality. After adding deriving(Show), you can also make readExpr‘s Right case return the actual parse tree as a string:

    Right val -> "Found value: " ++ show val

Handy, no?

Then, we add main.hs, containing:

module Main where
import WYAS
import System.Environment

main :: IO ()
main = do args <- getArgs
    putStrLn (readExpr (args !! 0))

Next, let’s compile this, and make sure we get something that acts like our old parser:

ghc --make -o main main.hs
./main 42
./main "#t"

Once we’re convinced that’s all working, save it and commit it to your version control. (You are using version control, right? svn, git, cvs, hg… they’re all great, and totally worth using here!)

Now, we add a test framework. First and foremost: make sure you have HUnit installed (on ubuntu and debian, it should be ‘apt-get install libghc6-hunit-dev libghc6-hunit-doc‘).

Then, we’ll get to using HUnit to write unit tests. I don’t really want to explain HUnit in too much detail, in part because I still don’t fully grok it. Suffice it to say, the following works, and gets good results. If you have better options, please leave them in the comments, as this is one of those things that could always use refinement.

For my purposes, I’m only really interested in running tests on each parse type. That is: I want to put together a bunch of strings representing possible Number inputs, along with their parses, and run them one after the other. I’d like to have a string to tell me the name of the grouping, but, beyond that, I’m not too picky on how much debug output I get. When an input string fails (and it will), I can use the ./main binary to examine the output parse. So, I’m going to write a small templating facility in my test setup. I’ll define a ParseTestSuite, which is a String identifying the group with a list of (String, LispVal) pairs. The String is the input, and the LispVal is the expected parse. Once I have that, add some code around it to turn them into HUnit’s internal Test representation. At the very end, we collect all these Tests, and run them. Here’s the resultant test.hs:

module Main where
import WYAS
import Test.HUnit
import Text.ParserCombinators.Parsec hiding (spaces)

-- A ParseTestSuite is a name, then a list of strings, and their expected parses
-- For instance:
--   ParseTestSuite "testNumbers" [("32", Number 32), ("3.4", Float 3.4), ..]
--
data ParseTestSuite = ParseTestSuite String [(String, LispVal)] deriving (Show)

doParse :: String -> LispVal

doParse input = case parse parseExpr "lisp" input of
    Left err -> Atom ("No Match " ++ show err)
    Right val -> val

-- Convert a ParseTestSuite into an HUnit test suite.
-- This requires extracting the boolean assert, then turning
-- it into a test case.
suiteEntryToAssert :: String -> LispVal -> Assertion
suiteEntryToAssert s p =
assertBool s (p == doParse s)

parseTestSuiteToTest :: ParseTestSuite -> Test
parseTestSuiteToTest (ParseTestSuite name tests) =
    TestLabel name bodies_t where
    bodies_t = TestList $ map (\(s,p) -> TestLabel s (TestCase (suiteEntryToAssert s p))) tests

tests_Number :: ParseTestSuite
tests_Number = ParseTestSuite "tests_Number"
    [
    ("32", Number 32),
    ("3.2", Float 3.2),
    ("0", Number 0),
    ("#d1", Number 1),
    ("#b10", Number 2),
    ("#x10", Number 16),
    ("#o10", Number      ]

tests_Bool :: ParseTestSuite
tests_Bool = ParseTestSuite "tests_Bool"
    [
    ("#t", Bool True),
    ("#f", Bool False)
    ]

-- lots of other tests elided

all_tests :: [ParseTestSuite]
all_tests = [tests_Number, tests_Bool, tests_Atom, tests_String, tests_Char, tests_List, tests_DottedList, tests_Quoted]

main :: IO ()
main = do
    runTestTT $ TestList (map parseTestSuiteToTest all_tests)
    return ()

Then, we compile this:

ghc --make -o test test.hs
./test

and its output:

0] jbm@density:~/src/wyas/ch2 $ ./test
Cases: 22  Tried: 22  Errors: 0  Failures: 0
0] jbm@density:~/src/wyas/ch2 $

From here, it’s just a matter of adding more of these ParseTestSuite entries and inserting it into all_tests. As we do this, we gain more confidence in the parser we’re building in this process.

There’s one more key consideration in confidence, though: code coverage. Unit tests are great, but they might not test all your code, leaving bugs lurking for some poor soul to find later. The best way to ensure this is to run your unit tests under a coverage tool. GHC comes with one of these, handily enough: hpc.

As with all coverage tools, we need to recompile the program with some new options. And, like many of them, we need to clean up the project a bit first. So, in the name of being lazy, I wrote a Makefile:

# NB: you're going to get this mangled.
# The things under the target names MUST be tabs, not spaces.
# The joys of ancient Unix programs.
#
all: test main

coverage: clean WYAS.hs test.hs
        ghc --make -fhpc -o test test.hs
        ./test
        hpc markup --include=WYAS ./test

test: WYAS.hs test.hs
        ghc --make -o test test.hs
        ./test

main: WYAS.hs main.hs
        ghc --make -o main main.hs

clean:
        rm -f *.tix *.hi *.o main test

distclean: clean
        rm -f *.html

This lets us run ‘make coverage‘ and get an HTML file showing the coverage of WYAS.hs:

0] jbm@density:~/src/wyas/ch2 $ make coverage
rm -f *.tix *.hi *.o main test
ghc --make -fhpc -o test test.hs
[1 of 2] Compiling WYAS             ( WYAS.hs, WYAS.o )
[2 of 2] Compiling Main             ( test.hs, test.o )
Linking test ...
./test
Cases: 22  Tried: 22  Errors: 0  Failures: 0
hpc markup --include=WYAS ./test
Writing: WYAS.hs.html
Writing: hpc_index.html
Writing: hpc_index_fun.html
Writing: hpc_index_alt.html
Writing: hpc_index_exp.html

To get a quick view of how we’re doing, we can use ‘hpc report‘:

0] jbm@density:~/src/wyas/ch2 $ hpc report test.tix
91% expressions used (416/457)
100% boolean coverage (1/1)
100% guards (0/0)
100% 'if' conditions (1/1)
100% qualifiers (0/0)
62% alternatives used (22/35)
100% local declarations used (6/6)
96% top-level declarations used (32/33)
0] jbm@density:~/src/wyas/ch2 $ hpc report test.tix  WYAS
91% expressions used (233/256)
100% boolean coverage (1/1)
100% guards (0/0)
100% 'if' conditions (1/1)
100% qualifiers (0/0)
63% alternatives used (21/33)
100% local declarations used (5/5)
95% top-level declarations used (19/20)
0] jbm@density:~/src/wyas/ch2 $

As you can see, my “alternatives used” is rather low. Looking at the highlighted output, I need to finish up the tests around my R5RS character decoding implementation. Time to go in and add more cases to my unit tests!

I hope this post helps explain the benefits of testing for this project, and helps you convert your copy of Write Yourself a Scheme into something more test-driven. If it saves you time, or you have any other ways to help the rest of us save some time, leave a comment. WYAS is a great resource, and I’d love to collect all the time-savings we can and fold them into the original text.