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