[Haskell-cafe] Re: GSOC Haskell Project

[Mihai Maruseac]

Oops, forgot to add the third link: my homepage is at
http://people.rosedu.org/people/mihai_maruseac

On Tue, Apr 6, 2010 at 10:11 PM, Mihai Maruseac
<mihai.maruseac at gmail.com> wrote:
> 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
>>
>