[Haskell-cafe] An interesting paper from Google

[Bernie Pope]

On 17 October 2010 11:25, Dan Doel <dan.doel at gmail.com> wrote:
> On Saturday 16 October 2010 7:04:23 pm Ben Millwood wrote:
>> On Fri, Oct 15, 2010 at 9:28 PM, Andrew Coppin
>>
>> <andrewcoppin at btinternet.com> wrote:
>> > I'm still quite
>> > surprised that there's no tool anywhere which will trivially print out
>> > the reduction sequence for executing an expression. You'd think this
>> > would be laughably easy, and yet nobody has done it yet.
>>
>> I tried to do something a bit like this:
>>
>> http://github.com/benmachine/stepeval
>>
>> but it could be charitably described as "crude": has three failing
>> testcases and a bagful of unimplemented functionality.
>
> I believe the Buddha debugger could do something like this, as well, although
> normally you wouldn't dump the entire sequence.

Buddha is/was a declarative debugger. The basic idea is to build a
computation tree, and then search the tree for buggy nodes. Normally
the debugger would decide how to traverse the tree, and the user would
simply make judgements about the correctness of reductions stored in
the visited nodes. However, buddha also allowed the user to explore
the tree manually. None of this was particularly unique to buddha, and
most other declarative debuggers allow you to do this too.
Unfortunately most declarative debuggers don't make it far past the
proof of concept stage.

The HAT tracer also supports/supported declarative debugging and has
many useful trace exploration tools.

> But it has bit rotted,
> unfortunately (it's quite tied to GHC internals, as far as I can tell).

As the author of buddha I can confirm that it hasn't been maintained.
The main dependency on GHC is a small amount of code for printing data
structures. In fact some of that could would be easier to do now than
it was then, because GHC includes data constructor names by default in
compiled code (this was added to support the ghci breakpoint
debugger).

> I never used it, but I've had at least one person tell me it was the best
> debugger they'd ever used. You type in an expression, and continually step
> into different parts of the reduction sequence until you find some core source
> of whatever error you're looking for.

I'm happy to hear someone like it so much. Declarative debugging is a
very nice idea (invented for Prolog by Ehud Shapiro - he is now famous
for DNA computing), but it is hard to make practical. Probably the
best declarative debugger I know of is the one provided for the
Mercury programming language. However, Mercury is a strict language,
which simplifies some aspects of the design.

The problem is that it is hard to scale to long running computations,
because the computation tree can become huge. HAT tackles this problem
by saving a trace record to file, although this can have rather high
runtime overheads. The declarative debugger for Mercury language
tackles this problem by piecemeal construction of the computation
tree, and by regenerating parts of it on demand by re-execution of
code. Re-execution in a lazy language is quite challenging (I tried to
do it in buddha).

I have some ideas about interspersing declarative debugging with
computation, but never had the time to implement it (though I think it
would make a great research project).

> If someone were to revive it, I'm sure many people would be appreciative.

I think it might be better to put more effort into HAT.

Cheers,
Bernie.