[Haskell-cafe] GSOC Haskell Project

[Mihai Maruseac]

Hello haskellers (men and women)!

I had an idea about a graphical debugger for Haskell but it has proven
to be not really so much useful. However, I was directed into trying
to implement a backtrace-printing debugger as it is known that the
community will benefit from it. With this idea in mind, I've settled
down and browsed the web until I gathered enough material to design a
proposal for Google Summer of Code 2010, which I present here to
receive as much feedback from any of you as possible before posting it
on Google.

I am hereby proposing a project to add stack traces to a Haskell
Debugger, either integrated with GHCi or as a stand-alone tool (or,
even better with possibility to be integrated with GHC, HUGS and other
interpreters and compilers). This will help novice users reason about
their programs and grasp a solid foothold on the language while
jumping to more and more ambitious projects without fear that their
code may break and they'll be left with a cryptic error message like
``head: empty list'. Also, this will help veteran haskellers by
providing the so much desired tool they asked several times for.
Leaving the marketing away, following are some descriptions of the
project.

My idea tries to address two tickets issued on haskell.org trac. The
first one of them (in a chronological order, not sorted by importance
and relevance) is #960 [0]: providing a lexical call site in order to
ease the debugging. Now, this is not too important for a stand alone
project taking into account that HPC exists and that GHCi has
debugging[5], [6].

However,  the second ticket (#3693) [1] is what my proposal aims to
solve. Obtaining and showing stack traces on errors is a very good
thing in imperative languages and someone who have used GDB more than
20% of his programming hours knows this. However, obtaining them in
Haskell (or any other lazy functional programming language) is not
that easy. This is what the community suggested me to do if I want to
implement a debugger and this is what I will want to do.

Now, the fact that both these tickets are marked as never ending (with
a bottom value as milestone) I know that they can be solved in one
project. Proof of this is offered in several places, some of them
gathered together into one single wiki page[2]. Following the work of
Tristan Allwood, Simon Peyton Jones and Susan Eisenbach presented a
paper to the Haskell Symposium from May 2009[3] in which they laid
down the basis for offering stack traces in GHC.

Needless to say, my GSoC project will be implemented starting from
their article. It combines ideas from that paper with ideas from a
presentation at Haskell Implementors Workshop 2009[4] and tries to
solve the open problems suggested by Tristan and colleagues in their
paper: providing stack traces for higher order functions, taking care
of typeclasses and modules, taking into account constant applicative
forms and/or mutually recursive functions.

In order to do this, I may either expand on their work, extending the
Core to Core rewriting system that they wrote to include these cases
or I may write a new system which I will detail in the following
phrases in a very short manner: if HPC uses a transformation just
before desugarising Haskell AST into Core in order to obtain the
moment when expressions are evaluated (and we know it does), then a
similar transformation can be done to record each function call in a
global hash-table-like data structure. When the buggy code shows up
and our program fails, by simply looking into that table and following
the links to the callers we may reconstruct the stack trace on the
fly.

I believe that this approach doesn't break the system set by Tristan
while extending it in a very user-configurable way. The user may
select to print only several levels of the stack, to elide multiple
apparitions of the same function name (even to elide them if a certain
threshold is passed) or to ask for function arguments if they can be
printed and are known when the function is called (displayed as ? or _
otherwise).

As for the integration with library code or code that was already
debugged and proved correct, I believe that if this tool will only
analyse user's code no previously working code will be broken or
hampered in any way.

The time complexity of this kind of debugging is the same as that of
parsing the code and that of following some pointers to parents in a
tree. Space complexity, however, is not that simple to compute. Yet, I
believe that it can be bounded and restricted to a polynomial
dependence on the source code length.

As for an approximate timeline, I guess that before the first of June
I can offer several proof of concept snapshots of the debugger and I
will have settled on one of the mini branches that my idea has (I am
refering to the fact that I can either implement a HPC like rewrite or
expand on the existing one). At the end of June, however, we will be
able to use the tool to obtain stack traces from simple programs and
from programs using higher-order functions and (though not really sure
about this) typeclasses or CAFs. The remaining parts will be finished
by the end of July and a stress testing period will start afterwards
when bugs issued by the community will be solved.

I guess that this timeline ensures that at the end of summer, a
debugger with stack traces will exist in the world of Haskell.

I planned to give more information about myself at the end of the
message but I observed that it has already become too long, just like
my blog posts. I will stop it here right now and add those
informations at a later date.

I apologize for taking up your time with a such lengthy message, and
eagerly await your feedback!


[0]: http://hackage.haskell.org/trac/ghc/ticket/960
[1]: http://hackage.haskell.org/trac/ghc/ticket/3693
[2]: http://hackage.haskell.org/trac/ghc/wiki/ExplicitCallStack
[3]: http://research.microsoft.com/~simonpj/papers/stack-trace/DebugTraces.pdf
[4]: http://ww2.cs.mu.oz.au/~bjpop/slides/stack_tracing.pdf
[5]: http://cgi.cse.unsw.edu.au/~dons/blog/2007/11/14
[6]: http://www.haskell.org/haskellwiki/Debugging