Haskell has many advantages (e.g. laziness) which however, make finding bugs difficult. In imperative languages, debugging is simply possible using printf statements. In Haskell this is only possible using the unsafe function unsafePerformIO: [^ unsafe]

import System.IO.Unsafe (unsafePerformIO)

trace :: String -> a -> a
trace str x = unsafePerformIO $ do
  putStr str
  return x

The semantics of trace is the identity, but once the calculation of trace is triggered, the string is printed as a side effect:

traceAndShow :: Show a => a -> a
traceAndShow x = trace (show x) x

One problem is the mixture of dbug output and the result of the computation. This problem could be solved by using a seperate trace file. Another problem is the dependence of the output in relation to evaluation order, which may be quite confusing in the context of lazy-evaluation.

x = let l = map traceAndShow [1..] in sum (take 4 l)
y = let l = map traceAndShow [1..] in sum (reverse (take 4 l))

Debugging with Observations (Hood)

The idee of Hood is to observe values like using traceAndShow, but delaying the output of the observation until the programm finishes (or is interrupted by pressing Strg-C). Furthermore, non-evaluated sub-structures are represented by "_". To distinguish the observations of a program, the user can add a string label:

Usage: After importing the module Debug.Observe arbitrary expressions can be observed using the function observe :: Observable a => String -> a -> a. The whole observation can be started using the function runO :: IO a -> IO ().

It is possible to observe all data types (for own data types an instance of class Observable has to be defined, details can be found in the documentation of the library). Also functions can be observes. They are represented by the used part of their function graph:

In practice, it is often more useful to observe functions instead of first order data structures, since they represent the functionality of your program. Let's consider a function definition of a function we want to observe:

Hence, all calls of

F including the recursive once will be observed. This can result in too many observations. Therefore, it is often better to only observe the initial calls of

f`:

Beside this it is also possible to only observe some special calls of a function.

Implementation of Observations for data

We start with the definition of a data type, which allows the representation of arbitrary data values. Our data type also contains representations for non-evaluated sub-expressions and demand requests, which show that an evaluation was initiated, but did not succeed to produce a head-normal-form (HNF) yet.

data EvalTree
  = Cons String [EvalRef]
  | Uneval    -- entspricht '_'
  | Demand    -- entspricht '!', abgebrochene Berechnung

type EvalRef = IORef EvalTree

The computation of fac (-1) would not terminate and the is reflected by a started, unseccessful evaluation of the second list element, represented by an exclamation mark.

The representation of this observation result as en EvalTree is presented in the following figure:

Hence, we want to modify nodes within our EvalTree during the observed computation takes place. This will be organized as a side effect and we use IORefs for every node within the EvalTree, to make mutations of EvalTrees possible.

data Tree = Empty | Node Tree Tree

oTree :: Tree -> EvalRef -> Tree
oTree Empty ref = unsavePerformIO $ do
  mkEvalTreeCons "Empty" ref 0
  return Empty
oTree (Node tl tr) ref = unsafePerformIO $ do
  [tlRef, trRef] <- mkEvalTreeCons "Node" ref 2
  return (Node (oTree tl tlRef) (oTree tr trRef))

mkEvalTreeCons :: String -> EvalRef -> Int -> IO [EvalRef]
mkEvalTreeCons consName ref n = do
  refs <- sequence $ replicate n $ newIORef Uneval
  writeIORef ref (Cons consName refs)
  return refs

isNode (Node _ _) = True
isNode _          = False

We can generalize the apporach to arbitrary data types using the following class:

class Observe a where
  obs :: a -> EvalRef -> a

instance Observe Tree where
  obs = oTree

observer :: Observe a => a -> EvalRef -> a
observer x ref = unsafePerformIO $ do
  writeIORef ref Demand
  return (obs x ref)

The function observe adds a Demand for every requestes sub-expression. If the sub-expression is evaluated to HNF, the function obs (here oTree) will convert this Demand into a Cons-value.

Furthermore, we sould correct the definition of oTree, such that also for the sub-observers, we call observe instead of oTree. The order should always be as follows:

\[\text{Uneval } \xrightarrow{\text{Request of the HNF}} \text{Demand } \xrightarrow{\text{HNF was computed}} \text{Cons}\]

global :: IORef [IO ()]
global = unsafePerformIO (newIORef [])

observe :: Observe a => String -> a -> a
observe label x = unsafePerformIO $ do
  ref <- newIORef Uneval
  modifyIORef global (showInfo ref :)
  return (observer x ref)
  where
  showInfo ref = do
    putStrLn (label ++ "\n" ++ replicate (length label) '-')
    showEvalTreeRef ref >>= putStrLn

runO :: IO () -> IO ()
runO act = do
  writeIORef global []
  catch act (\e -> putStr "Runtime Error: " >> print (e :: SomeException))
  printObs

printObs :: IO ()
printObs = do
  putStrLn ">>> Observations <<<"
  readIORef global >>= sequence_

Now, it only remains to define a the function showEvalTreeRef, which converts EvalTrees into a user friendly String representation:

showEvalTreeRef :: EvalTreeRef -> IO String
showEvalTreeRef ref = readIORef ref >>= showEvalTree

showEvalTree :: EvalTree -> IO String
showEvalTree Uneval         = return "_"
showEvalTree Demand         = return "!"
showEvalTree (Cons cons []) = return cons
showEvalTree (Cons cons rs) = do
  args <- mapM showEvalTreeRef rs
  return $ "(" ++ unwords (cons : args) ++ ")"

For arbitrary construcors, e.g. tuples or lists, it is also possible to define more readable representations, which can be done as an exercise.

So fare, it is not so trivial to define an Observe instance for own data types. However, comparing such instances, we can see, that all definitions are very similar and we can define auxiliar functions for constructors of a fixed arity:

instance Observe a => Observe [a] where
  obs (x:xs) = o2 (:) "(:)" x xs
  obs []     = o0 []  "[]"

o0 :: a -> String -> EvalRef -> a
o0 cons consName ref = unsafePerformIO $ do
  mkEvalTreeCons consName ref 0
  return cons

o2 :: (Observe a, Observe b)
   => (a -> b -> c) -> String -> a -> b -> EvalRef -> c
o2 cons consName vA vB ref = unsafePerformIO $ do
  [aRef, bRef] <- mkEvalTreeCons consName ref 2
  return $ cons (observer vA aRef) (observer vB bRef)

Observing functions

As a next step, we implement the observation of functions. Similar to lazy data structures, functions are observed by representing the used part of their function graph. Arguments and return values are data which is also observed, like implemented above:

Note: Here, (+1) is a constant and the corresponding observer is only computed once, which means that we see three elements of its function graph. Realizing this similar to data constructors, we would override one aplication of a function by its next application. The solution is extension of the EvalTree with a special constructor Fun. In contrast to Cons it contains a list as its argument. Within this list we store all applications of the function. One application is represented as a pair of the observations of the argument and the result.

data EvalTree
  = Cons String [EvalRef]
  | Uneval
  | Demand
  | Fun [(EvalRef, EvalRef)]

Fun [ (Cons "3" [], Cons "4" [])
    , (Cons "4" [], Cons "5" [])
    , (Cons "5" [], Cons "6" [])
    ]

instance (Observe a, Observe b) => Observe (a -> b) where
  obs f ref x = unsafePerformIO $ do
    applRefs <- readIOFunRef
    argRef   <- newIORef Uneval
    resRef   <- newIORef Uneval
    writeIORef r $ Fun ((argRef, resRef) : applRefs)
    return $ observer (f $ observer x argRef) resRef
  where
  readIOFunRef = do
    v <- readIORef ref
    case v of
      Fun applRefs -> return applRefs
      _            -> do
        writeIORef ref (Fun [])
        return []

showEvalTree :: EvalTree -> IO String
showEvalTree ...
showEvalTree (Fun appls) = do
  resDStrs <- mapM showApp (reverse appls)
  return $ unlines resStrs
  where
  showApp (rArg,rRes) = do
    arg <- showEvalTreeRef rArgs
    res <- showEvalTreeRef rRes
    return $ concat ["{", arg, "->", res, "}"]

Instead of using a EvalTrees for storing observations, it is also possible to store the debug information within a file. For presenting the observations, it is then possible to analyse the file at the end of the execution and and present these to the user. The opetunity is, that less memory is needed during the execution, the file contains additional information about the order in which the observations are constructed, although so fare no tool presents this order.

The presented approach is based on the implementation of Hood. There are further approaches for debugging, wich usually work as a program transformation and are in most cases only available for Haskell'98.

The advantage of Hood is, that it is light weight and relatively robust against language extensions. A disadvantage is, the fact that you usually do not obtain relations between different observations in Hood. Here approaches like Hat are more powerfull.

For a clearer understanding, we omit the references here.↩