[Haskell-cafe] Re: GSOC Haskell Project

[Mihai Maruseac]

Hello again

Following a feedback (courtesy of lispy) of my proposal on #haskell, I
come to complete it with some bits here and there.

First, a short analysis on the impact that this tool will have on the
community. I now that right now there are plenty of clever tricks for
debugging your code, even if it involves FFI calls or Monad
Transformers Stacks but no one trick is a silver bullet. As far as I
know, there is no trick which works the same way both for FFI or
Arrows. However, having a backtrace will really help in any domain,
from DSLs to FRP and Category Theory constructs. It will help also the
beginner average Joe starting to program in Haskell and the senior PhD
doctor Bob from the University. The later will be helped by seeing
what part of his code is responsible for an unexpected failure while
the former will recognize the stack traces he saw in gdb and other
imperative programming languages.

The second completion that I want to do is to give some more details
on the timeline. Between May 26 and first of June I will contact Simon
Peyton Joynes and his coautors to see how I will integrate will their
code base, what are their policies to integrating patches, what
repository they use, etc. This is to ensure continual integration,
such that every day there will be a version of the tool which can be
built on any machine and used for debugging your own code. Moreover, I
will talk to them during this timeframe to convince myself whether the
idea of a HPC-like rewrite is good or I should stick with the existing
one. If later, this would be all that I'll be doing during this
period, otherwise, I'll try to refactor the existing rewrite to the
HPC-like one during this timeframe and during one more week after that
(that is, until 6th of June). Last but not least, this timeframe must
be used to prove several proof of concept snapshots of the debugger,
in both variants for public feedback and further guidance

Between 1st and 14th of June I will integrate higher-order functions
and typeclasses into the debugger. If choosing to do a HPC-like
rewrite only the higher order functions would be integrated until 14th
of June.

However, until 1st of July I will have both higher-order functions and
typeclasses inserted into the debugger, the period between 14th and
30th being a buffered period for cases where I'll get stuck and fall
behind the timeline.

In July, the first week will be dedicated to integrating CAFs while
the second one will be for cross module debugging providing options to
debug only certain modules while ignoring others (assuming that they
are correct). A new buffering period will be between 14th of July and
1st of August, a period which will be used to ensure that all parts
will be integrated well and will work in a non-buggy way.

The month of August is dedicated to community suggested improvements.
Through a series of stress tests or simple tests this debugger will
show its strength and its bugs. The former will be praised while the
later will be solved during this timeframe and after the GSoC period.

Next, some details about my haskell development skills. If the code
snippets found in my blog[1] are not so relevant, maybe a link to the
latest project developed in Haskell will help[2]. The project was
supposed to be a rewrite of Berkley's esspresso program allowing both
for logic expression minimization and for automatic drawing of gates.
Lately, we stopped working on it because we couldn't find a good
working example of it's utility. To add more to my level of Haskell
knowledge, I may say that I am teaching programming paradigms at my
university as a teaching assistant (students are allowed to do so if
they have a very solid knowledge of the subject and a very good
extra-curricular open-source/contest activity) and one quarter of the
course is held in Haskell (though this year will be the first when we
will teach Monads to the students, starting from one of my ideas).
Lastly, I've read books on Haskell and right now I am trying to grasp
Category Theory by reading Awodey's book. Moreover, I have the full
journal of functional programming articles downloaded on my laptop.

As for the community integration, I am one of the most active ROSEdu
members here, taking part in almost any activity that we develop. I am
project manager for one Tech Talks activity and I intend to give a
talk on side effects during the next month. More info can be found by
reading my homepage[3].

Thanks for the patience for reading another long email. Please, do
give some feedback to help me create a better application.

Not really useful PS: I am thinking to chose a graduation license
software project on Haskell though I haven't yet selected a theme and
a domain.

[1]: http://pgraycode.wordpress.com
[2]: http://dev.rosedu.org/xpresso/browser/trunk

-- 
Mihai Maruseac

On Mon, Apr 5, 2010 at 8:26 PM, Mihai Maruseac <mihai.maruseac at gmail.com> wrote:
> 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
>