[Haskell-cafe] Debugging partial functions by the rules

[Donald Bruce Stewart]

So all this talk of locating head [] and fromJust failures got me
thinking:

    Couldn't we just use rewrite rules to rewrite *transparently*
    all uses of fromJust to safeFromJust, tagging the call site
    with a location?

To work this requires a few things to go right:

    * a rewrite rule
    * assertions
    * and rewrite rules firing before assertions are expanded

Let's try this. Consider the program:

     1	    import qualified Data.Map as M
     2	    import Data.Maybe
     3	
     4	    main = print f
     5	
     6	    f = let m = M.fromList
     7	                    [(1,"1")
     8	                    ,(2,"2")
     9	                    ,(3,"3")]
    10	            s = M.lookup 4 m
    11	        in fromJust s

When we run it we get the not so useful error:

    $ ./A 
    A: Maybe.fromJust: Nothing

Ok, so we have a few tricks for locating this, using LocH
(http://www.cse.unsw.edu.au/~dons/loch.html), we can catch an
assertion failure, but we have to insert the assertion by hand:

     1	    import Debug.Trace.Location
     2	    import qualified Data.Map as M
     3	    import Data.Maybe
     4	
     5	    main = do print f
     6	
     7	    f = let m = M.fromList
     8	                    [(1,"1")
     9	                    ,(2,"2")
    10	                    ,(3,"3")]
    11	            s = M.lookup 4 m
    12	        in safeFromJust assert s
    13	
    14	    safeFromJust a = check a . fromJust

Which correctly identifies the call site:

    $ ./A 
    A: A.hs:12:20-25: Maybe.fromJust: Nothing

Now, this approach is a little fragile. 'assert' is only respected by GHC if -O
is *not* on, so if we happened to try this trick with -O, we'd get:

    $ ./A                                                 
    A: Debug.Trace.Location.failure

So lesson one: you have to do the bug hunting with -Onot.

Currently there's -fignore-asserts for turning off assertions, but no flag for
turning them on with -O, Simon, could this be fixed? Could we get a
-frespect-asserts that works even with -O ?


Ok, assuming this assert trick is used, can we get the compiler to insert the
asserts for us? If so, this would be a great advantage, you'd just be able to 
switch on a flag, or import a debugging module, and your fromJusts would be
transparently rewritten.  With rewrite rules we do just this!

So, to our initial unsafe use of fromJust, we add a rewrite rule:

    --
    -- rewrite fromJust to a located version, and hope that GHC expands
    -- 'assert' after the rule fires..
    --
    {-# RULES
    "located fromJust" fromJust = check assert . myFromJust
      #-}

This just tells the compiler to replace every occurence of fromJust with a
assertion-throwing fromJust, should it fail. We have to use myFromJust here, to
avoid rule recursion.

    --
    -- Inlined to avoid recursion in the rule:
    --
    myFromJust :: Maybe a -> a
    myFromJust Nothing  = error "Maybe.fromJust: Nothing" -- yuck
    myFromJust (Just x) = x

Ok, so can we get ghc to rewrite fromJust to the safe fromJust magicaly?

    $ ghc --make -Onot A.hs -fglasgow-exts -ddump-simpl-stats
    [1 of 1] Compiling Main             ( A.hs, A.o )
    1 RuleFired
        1 located fromJust
    Linking A ...

Yes, the rule fired! GHC *did* rewrite our fromJust to a more useful fromJust.
Running it:

    $ ./A
    A: A.hs:19:36-41: Maybe.fromJust: Nothing

Looks good! But that is deceiving: the assert was expanded before the rule
fired, and refers to the rewrite rule source line (line 19), not the fromJust
call site (line 12).  Now if we could just have the 'assert' token inserted
into the AST before it was expanded, we'd be home and dry. Could this be done
with TH? Or could we arrange for asserts in rewrite rules not to be expanded
till later?

Note that this is still a useful technique, we can rewrite head/fromJust/... to
some other possibly more useful message. And if we can constrain the rule to fire 
in only particular modules, we may be able to narrow down the bug, just by
turning on a rule. For example, adding:

    {-# RULES
    "located fromJust" fromJust = safeFromJust
      #-}

    safeFromJust s = case s of
        Nothing -> "safeFromJust: failed with Nothing. Ouch"
        Just x  -> x

will produce:

    $ ./A
    "safeFromJust: failed with Nothing. Ouch"
        
So rewrite rules can be used to transparently alter uses of partial functions
like head and fromJust.

So, further work:

    * have 'assert' respected when -O is on

    * think up a technique for splicing in 'assert' via rewrite rules (or TH
    ...) such that the src locations are expanded after the rewrite, and
    correctly reflect the location of the splice point.

Any ideas?

-- Don