Hat is a source-level tracer for the programming language Haskell. Hat gives access to detailed, otherwise invisible information about a computation.

Hat helps locating errors in programs. Furthermore, it is useful for understanding how a (correct) program works, especially for teaching and program maintenance. Hat is not a time or space profiler. Hat can be used for programs that terminate normally, that terminate with an error message or that terminate when interrupted by the programmer.

How do I use it?

Tracing a program with Hat consists of two phases:

First you run your program such that it additionally writes a trace to file. To do so you use hat-trans to translate all the source modules Module of your Haskell program into tracing versions Hat.Module. You compile these and when run the program does exactly the same as the original program except for additionally writing a trace to file.

Second, after the program has terminated, you view the trace with a browsing tool. The trace consists of high-level information about the computation. It describes each reduction, that is, the replacements of an instance of a left-hand side of an equation by an instance of its right-hand side, and the relation of the reduction to other reductions. Because the trace describes the whole computation, it is huge. Hat comes with several tools to selectively view the fragments of the trace that are of interest. Each tool shows fragments of the computation in a particular way, highlighting a specific aspect.

How can I view a trace?

All tools show function arguments in evaluated form, more precisely: as far evaluated as the arguments are at the end of the computation. For example, although in a computation the unevaluated expression (map (+5) [1,2]) might be passed to the function length, the tools will show the function application as length [1+5,2+5] or length [_,_].

For example, the computation of the faulty program

main = let xs :: [Int]
           xs = [4*2,5 `div` 0,5+6]
       in  print (head xs,last' xs)

last' (x:xs) = last' xs
last' [x] = x

gives the result

(8, No match in pattern.

and the Hat viewing tools can be used to explore its behaviour as follows:

Hat-observe (inspired by Hood)

Hat-observe is an interactive tool that shows how top-level functions are used. That is, for a given top-level function name it shows all the arguments with which it is called during the computation, together with the respective results.

$ hat-observe Example

                hat-observe 2.04    (:h for help, :q to quit)

hat-observe> main
1  main = IO (print (8,_|_))
hat-observe> print
1  print (8,_|_) = IO (print (8,_|_))
hat-observe> last'
1  last' [8,_,_] = _|_
2  last' [_,_] = _|_
3  last' [_] = _|_
4  last' [] = _|_
hat-observe> :quit
$

Hat-trail

Hat-trail is an interactive tool that enables exploring a computation backwards, starting at the program output or an error message (with which the computation aborted). This is particularly useful for locating an error. You start at the observed faulty behaviour and work backwards towards the source of the error.

Every reduction replaces an instance of the left-hand side of a program equation by an instance of its right-hand side. The instance of the left-hand side ``creates'' the instance of the right-hand side and is therefore called its parent. With hat-trail you can obtain the parent of any expression.

Each line of the trail is the parent of the highlighted subexpression directly above it.

Error: -------------------------------------------------------
No match in pattern.
Output: ------------------------------------------------------
(8,
Trail: ---------------------- Example.hs line: 2 col: 12 -----
<- last' []
<- last' [_]
<- last' [_,_]
<- last' [8,_,_]
<- 4 * 2
<- xs

Here, the error message is chosen as the starting point, rather than any of the output. The first trail is therefore last' [], because its evaluation caused the error message. The parent of last' [] is last' [_]. The parent of last' [_] is last' [_,_]), etc. The parent of the subexpression 8 is 4*2 whose parent is xs.

Hat-explore

Hat-explore allows you to step through a computation. Like a conventional debugger hat-explore highlights your current position in the computation in the program source and shows a stack backtrace of function calls. In contrast to conventional debuggers you are free of the actual evaluation order when stepping through the computation. From any function call you can go down to any further function called by it, to a function call in the same function definition, or upwards to the caller of the current function call.

Because arguments and the result are shown for each function call, it is easier to determine which function is incorrect. You can also mark reductions as correct/incorrect which enables the tool to pinpoint the bug to a smaller and smaller slice of the program.

==== Hat-Explore 2.04 ==== Press h for help. ===================
 1. main = {IO}
 2. last' [8,_,_] = _|_
 3. last' [_,_] = _|_
 4. last' [_] = _|_
 5. last' [] = _|_
---- Last.hs ---- lines 1 to 7 ---------------------------------

main = let xs :: [Int]
           xs = [4*2,5 `div` 0,5+6]
       in  print (head xs,last' xs)

last' (x:xs) = last' xs
last' [x] = x

Hat-detect (inspired by Freja)

Hat-detect is an interactive tool that enables the semi-automatic location of an error in a program by answering a sequence of yes/no questions. Each question asked by hat-detect concerns the reduction of a redex - that is, a function application - to a value. You have to answer yes, if the reduction is correct with respect to your intentions, and no otherwise. After a number of questions hat-detect states which reduction is the cause of the observed faulty behaviour - that is, which function definition is incorrect.

Example session (y/n answers are given by the user):

$ hat-detect Example

                hat-detect 2.0x    (:h for help, :q to quit)

1  main = IO (print [3,3,3])   ? n
2  sort [3,2,1] = [3,3,3]   ? n
3  insert 1 [] = [1]     ? y
4  insert 2 [1] = [2,2]     ? n
5  insert 2 [] = [2]     ? y

Error located!
Bug found in reduction:   insert 2 [1] = [2,2]

Hat-stack

For aborted computations, that is computations that terminated with an error message or were interrupted, hat-stack shows in which function call the computation was aborted. It does so by showing a virtual stack of function calls (redexes). Thus, every function call shown on the stack caused the function call above it. The evaluation of the top stack element caused the error (or during its evaluation the computation was interrupted). The stack shown is virtual, because it does not correspond to the actual runtime stack. The actual runtime stack enables lazy evaluation whereas the virtual stack corresponds to a stack that would be used for eager (strict) evaluation.

Using the same example program as above, hat-stack shows

$ hat-stack Example
Program terminated with error:
        No match in pattern.
Virtual stack trace:
(Last.hs:6)     last' []
(Last.hs:6)     last' [_]
(Last.hs:6)     last' [_,_]
(Last.hs:4)     last' [8,_,_]
(unknown)       main
$

Language Coverage

Originally Hat was built to trace programs written in Haskell 98, using the Haskell 98 standard libraries. Hat now also supports most of Haskell 2010 (only part of the foreign function interface) plus some language extensions, such as multi-parameter type classes and functional dependencies.

Documentation

In the distribution there is documentation in the "docs" folder. Some of it is outdated (installation!), but the tools are basically described correctly. There are a few small programs for exploring tracing in the "examples" folder.

Documentation in the "docs" folder

Development

The code repository for Hat is on Github. There are usually several branches, some of which may not compile.

The following work is ongoing or planned:

The source-to-source transformation of hat-trans is being rewritten to use the haskell-src-exts parser. Thus small bugs of the current parser will disappear and in the future it will be easier to cover more Haskell language extensions.
When a traced program uses any libraries besides the standard Haskell 98 / 2010 ones, these libraries currently have to be manually transformed (in trusted mode). A new tool will be built to easily wrap any existing libraries such that they can be used by a traced program (without tracing the computations inside the libraries).
All viewing tools use a textual interface; however, many tools use some Unix-specific features and thus run on Unix / Linux / OS X, but not on Windows. The tools will be modified to use only libraries for their user interfaces that work also on Windows.

Download & Installation

Don't download from Git. Hat is available as a package from Hackage. Ensure that you have the Glasgow Haskell compiler ghc and the package manager cabal. You can get both easily by installing the Haskell Platform. Then execute

$ cabal install hat -v

Flag -v allows you to see what is going on. Building takes a long time (one module has 25.000 lines of code). Don't worry about numerous warning messages.

Use:

$ hat-make MyProgram.hs

to transform and compile all modules of your program and produce the tracing version Hat/MyProgram.

Run your program

Hat/MyProgram

which will produce the trace files MyProgram.hat*

Use the viewing tools to explore the trace:

$ hat-trail / hat-observe / hat-explore /...   MyProgram

Comments and Suggestions

Please leave your comments and suggestions on the Hat Wiki.

Hat - generating and viewing traces