Debugger for Hugs 
Author Message
 Debugger for Hugs

Is there any de{*filter*} for Hugs 1.4? Where can I find one?
Any pointers will be very much appreciated!

Jose' de Siqueira.
--
             Jos de Siqueira
Prof. Depto. de Cincia da Computa??o - UFMG



Fri, 27 Jul 2001 03:00:00 GMT  
 Debugger for Hugs

: Is there any de{*filter*} for Hugs 1.4? Where can I find one?
: Any pointers will be very much appreciated!

Hugs is as close as you can get to a de{*filter*} for Haskell.
You could almost be as bold as to say that is is a de{*filter*}.

        n.

--
--[ www.dtek.chalmers.se/~d95mback ]---[ PGP: 0x453504F1 ]---[ UIN: 4439498 ]--



Fri, 27 Jul 2001 03:00:00 GMT  
 Debugger for Hugs

Quote:


>: Is there any de{*filter*} for Hugs 1.4? Where can I find one?
>: Any pointers will be very much appreciated!

>Hugs is as close as you can get to a de{*filter*} for Haskell.

Sorry, but you're just plain wrong about that.
Hugs does not let you step through the computation,
browse the values of intermediate variables,
set breakpoints, or any of the usual things that
a de{*filter*} will let you do.  Lazy evaluation
makes things more complicated, but you can certainly
do a lot better than what Hugs currently gives you.

Quote:
>You could almost be as bold as to say that is is a de{*filter*}.

You could be as bold as to say that when you're using
Haskell and you have a very-fast-turnaround system
like Hugs, then there is often little need for a de{*filter*}.
And if you were to say that, then I'd agree.
But if you were to say that Hugs *is* a de{*filter*}, then
I'd have to strongly disagree -- at least for the
current and previous releases of Hugs.


implementing a de{*filter*} for Hugs, called Bhudda [1], based on some work
on declarative debugging of lazy functional languages by Lee Naish

it was not in a state he was ready to release.

[1]     Bernard Pope, "Buddha: A Declarative De{*filter*} for Haskell", Honours thesis,
        The University of Melbourne, < http://www.*-*-*.com/ ~bjpop/thesis.ps.gz>.
[2]     See < http://www.*-*-*.com/ ~lee/papers/dd.html>, in particular the
        paper "Towards a portable lazy functional declarative de{*filter*}".

--

WWW: < http://www.*-*-*.com/ ~fjh>  |   but source code lives forever"



Sat, 28 Jul 2001 03:00:00 GMT  
 Debugger for Hugs

Quote:


>implementing a de{*filter*} for Hugs, called Bhudda [1], based on some work
>on declarative debugging of lazy functional languages by Lee Naish

>it was not in a state he was ready to release.
>[1]Bernard Pope, "Buddha: A Declarative De{*filter*} for Haskell", Honours thesis,
>The University of Melbourne, < http://www.*-*-*.com/ ~bjpop/thesis.ps.gz>.
>[2] See < http://www.*-*-*.com/ ~lee/papers/dd.html>, in particular the
>    paper "Towards a portable lazy functional declarative de{*filter*}".

That is correct, I have been working on a de{*filter*} for Hugs. It is still
in a prototype phase at the moment.

Buddha is a declarative de{*filter*}, which uses the declarative semantics of
a program (rather than the operational semantics) to guide a search
for logical errors.

It is our intention that Buddha be portable across
implementations and languages (referential transparency and
laziness make this rather difficult).

Several other people have also worked on debugging for
lazy functional languages (like Haskell).

In particular Lee Naish, Henrik Nilsson, Jan Sparud and Peter Fritzson have
done a lot of work in this area.

There are too many references to mention here, however, if you grab a copy
of my thesis you can find their work mentioned in the Bibliography.

Bernie Pope.



Sat, 28 Jul 2001 03:00:00 GMT  
 Debugger for Hugs

Quote:


>> Hugs is as close as you can get to a de{*filter*} for Haskell.

Okay, I'm probably only displaying my ignorance here, but

Quote:
> step through the computation,

Is this even meaningful for a lazy evaluation language?  In a typcial
procedural language, you sorta have a well defined sequence of events
- but in Haskell, I get the feeling that anything can happen at any
time.

Quote:
> browse the values of intermediate variables,

This probably won't be a clear cut issue either, since a lot of
parameters may not be computed at all.

Quote:
> set breakpoints,
> Lazy evaluation makes things more complicated, but
> you can certainly do a lot better than what Hugs currently gives you.

But couldn't accessing internal state of the run time system (which is
what a de{*filter*} is about, isn't it) be giving different results with
different compilers/interpreters?  Would it be meaningful to debug a
program under one runtime system, and extrapolate the results to
another?

Quote:
>> You could almost be as bold as to say that is is a de{*filter*}.
> You could be as bold as to say that when you're using Haskell and you
> have a very-fast-turnaround system like Hugs, then there is often
> little need for a de{*filter*}.

In particular, I find a de{*filter*} most useful for discovering hidden
side effects.  Get rid of the side effects, and you lose at least 50%
of the reason to use a de{*filter*}.  Add readable code which lets you
convince yourself of its correctness, and easy testing of functions
from a command line, and you have most of the tools you need.  Except
grokable error messages, I guess.

I guess I should just check out the references, but is anybody able
and willing to outline the whys and hows of debugging lazy functional
code?  What would people like to have, and how to get it?

(This seems to be a recurring theme with e.g. Common Lisp: somebody is
trying to learn it, but doesn't find a graphical de{*filter*}, decides
it's all stone age technology, and goes back to C++)

-kzm
--
If I haven't seen further, it is by standing in the footprints of giants



Sat, 28 Jul 2001 03:00:00 GMT  
 Debugger for Hugs

Quote:


>>> Hugs is as close as you can get to a de{*filter*} for Haskell.

>Okay, I'm probably only displaying my ignorance here, but

>> step through the computation,

>Is this even meaningful for a lazy evaluation language?  In a typcial
>procedural language, you sorta have a well defined sequence of events
>- but in Haskell, I get the feeling that anything can happen at any
>time.

Well, in non-optimizing implementations like Hugs, the operational
semantics are probably deterministic or close to it.

If you're debugging optimized code, then yes the exact order of
execution will not be predicatablen in advance.  But there are few
reasons to debug optimized code.  One of the few times it's useful is
when you're trying to debug performance problems, and in that case it
may well be helpful to see exactly what is going on.

Quote:
>> browse the values of intermediate variables,

>This probably won't be a clear cut issue either, since a lot of
>parameters may not be computed at all.

That's true.  But if the de{*filter*} can display a readable representation
of the unevaluated closures, then that may give you useful information
anyway.  Also I believe it's possible to do tricky things like first
running the program to completion to force maximal evaluation of all
variables and then going back and tracing execution on the already
fully-evaluated tree.  See the papers cited earlier in this thread for
details, such as how to make this work in a reasonable amount of memory.

Quote:
>> Lazy evaluation makes things more complicated, but
>> you can certainly do a lot better than what Hugs currently gives you.

>But couldn't accessing internal state of the run time system (which is
>what a de{*filter*} is about, isn't it) be giving different results with
>different compilers/interpreters?

Yes, but only up to a point.

For example, different implementations may differ in the exact order
in which they traverse the execution tree, and some may even be
evaluating the tree to different depths, but (for most programs)
the different implementations will all be traversing the same tree.

Quote:
>In particular, I find a de{*filter*} most useful for discovering hidden
>side effects.  Get rid of the side effects, and you lose at least 50%
>of the reason to use a de{*filter*}.  Add readable code which lets you
>convince yourself of its correctness, and easy testing of functions
>from a command line, and you have most of the tools you need.  Except
>grokable error messages, I guess.

"Easy testing of functions from a command line" is very difficult to
achieve if your functions take as input large data structures with
complicated invariants, as is typical of programs such as compilers,
for example.  And "readable code which lets you convince yourself
of its correctness" is of course an admirable aim, and one that we
should always strive for, but it is also one that becomes more and
more difficult to achieve as our applications become more complex.

If you typically write small programs that manipulate small or simple
data structures, then you will find little need for a de{*filter*}.
But if you are writing complex applications which manipulate
large and complex data structures, then a de{*filter*} will sometimes
become almost indispensable.  You don't need one often, but for
those times that you do, it's useful to have something a little
less primitive than hacking up printf-style debugging using
`unsafePerformIO' and `seq'!

--

WWW: < http://www.*-*-*.com/ ~fjh>  |   but source code lives forever"



Sat, 28 Jul 2001 03:00:00 GMT  
 Debugger for Hugs

Quote:

> "Easy testing of functions from a command line" is very difficult to
> achieve if your functions take as input large data structures with
> complicated invariants,

But would you be able to convince yourself of the correctness of the
large data structure, even if its available for inspection from a
de{*filter*}?  And couldn't you encode checks for those complicated
invariants, and apply them to the input and output of the function in
question to verify correctness?  Or am I missing the point?

Quote:
> If you typically write small programs that manipulate small or simple
> data structures, then you will find little need for a de{*filter*}.

Ouch, I guess that hit the nail on my...I mean, the head. :-)  Yep, I
typically do that, and yes, I do find exactly that.

Okay, I'm convinced.  Thanks for the elaboration!

-kzm
--
If I haven't seen further, it is by standing in the footprints of giants



Sat, 28 Jul 2001 03:00:00 GMT  
 Debugger for Hugs
I'd just like to add to this thread about debugging Haskell that
Jan Sparud and Colin Runciman's work on debugging by backward traces
(redex trails) is available (in prototype form) in the nhc13 compiler.

Although there are several restrictions on how much of the language
and libraries it can deal sensibly with at the moment, it can still
be quite a useful tool.

Because evaluation order is tricky to understand in a lazy setting,
stepping forward through a computation is pretty useless.  Instead,
it is much more intuitive to point and click at the piece of output
that you think is wrong (or the error message), and work backwards
asking "where did this come from?".

Quote:
> But if the de{*filter*} can display a readable representation
> of the unevaluated closures, then that may give you useful information
> anyway.

Yes, nhc13's trace browser has a special notation for unevaluated
closures.

Quote:
>  Also I believe it's possible to do tricky things like first
> running the program to completion to force maximal evaluation of all
> variables and then going back and tracing execution on the already
> fully-evaluated tree.

And this is how tracing with redex trails is achieved in nhc13 - it
is a post-mortem observation of the evaluation tree.  As you say,
various tricks are needed to manage the space needs of the tree, and
Sparud and Runciman have a paper about that (IFL'97).

Quote:
> "Easy testing of functions from a command line" is very difficult to
> achieve if your functions take as input large data structures with
> complicated invariants, as is typical of programs such as compilers,
> for example.

It can also be difficult to decide whether large reduction expressions
look plausible or not in the trace.  This tends to be a problem in
algorithmic debugging, where you are presented with these enormous
equations and asked whether you believe them or not.  By contrast,
nhc13's trace browser allows the user to fold away (and re-open)
any components of any expression, so you can examine expressions to
whatever level of detail you think is appropriate in looking for
the error.

nhc13 (soon to become nhc98)'s homepage is at:
    http://www.*-*-*.com/
and more info about Sparud and Runciman's approach to tracing is here:
    http://www.*-*-*.com/ ~sparud/tracing/tracing.html
and here:
    http://www.*-*-*.com/ ~sparud/

Regards,
    Malcolm


Dr Malcolm Wallace (functional programming research)   +44 1904 434756
Department of Computer Science, University of York, YORK YO1 5DD, U.K.
----------------------------------- http://www.*-*-*.com/ ~malcolm/



Sat, 28 Jul 2001 03:00:00 GMT  
 Debugger for Hugs

Quote:

>> "Easy testing of functions from a command line" is very difficult to
>> achieve if your functions take as input large data structures with
>> complicated invariants,

>But would you be able to convince yourself of the correctness of the
>large data structure, even if its available for inspection from a
>de{*filter*}?

It's generally rather difficult to verify correctness.
However, it's much simpler to verify incorrectness ;-)
All you need to do is to find one part of the data structure
which is obviously wrong.  And you have some clues to get you
started: you know that the program's final output is incorrect
(otherwise, you wouldn't be debugging it!).

A de{*filter*} won't help you to prove that your program is correct.
However, it may well help you to find the cause of a bug.

Quote:
>And couldn't you encode checks for those complicated
>invariants, and apply them to the input and output of the function in
>question to verify correctness?  Or am I missing the point?

Automated pre/post-condition and invariant checks certainly do help.
They are another technique that you should use as often as possible.
But again they only reduce the need for a de{*filter*}, they don't
eliminate it.

Many of the bugs in the Mercury compiler that I have used a de{*filter*}
to track down have been bugs whose symptom was precisely that the
compiler aborted due to one of these kind of invariant checks failing.
When one of these checks fails, say in stage 20 of compilation,
all you know at first is that the data structure was correct at stage 0
and incorrect at stage 20, and there may have been more than 100,000
lines of source code that touched it in between.
Now the Mercury compiler has pretty-printers for most of its internal data
structures, and there are compiler options to get the compiler to dump
these to a file.  So you can usually narrow it down to a single pass,
call it say 5000 lines or so, without resorting to a de{*filter*}.  
But after that, things get tricky.  You can stare at 5000 lines
of code for a very long time and still miss lots of simple errors
of the kind that a compiler will never catch, like using "<" instead
of ">", let alone the more subtle problems.  A de{*filter*} can help you
narrow down the scope of your search to something more managable.

Often the really tricky bugs are related to invariants that you didn't
formalize when you first wrote the code; that are too expensive to
check automatically, even in debug mode; or that are simply too complicated
to easily check automatically.  In some cases, writing the code to check
the invariant may take significantly more effort than finding the bug
with a de{*filter*}.

For example, one of the invariants/post-conditions in the Mercury
compiler is that the semantics of the code produced by each stage
should be sound with respect to the semantics of the original program.
This is trivial to state, but formalizing it would require formalizing
the semantics of Mercury and of (at least a subset of) C, as well as
the two intermediate languages that we use during compilation --
all worthy tasks, no doubt, but not small ones! -- and even
then checking it at runtime would still be undecidable in general.

Note also that a single data type may have different invariants at different
points in the program, so it's not just a question of attaching invariants
to data types, you have to attach them to program points.  Doing this
in a truly disciplined way is a hell of a lot of work.

And the sometimes you find that you need to significantly restructure
large parts of the code in ways that are likely to break the invariants.
For example, to implement existential types properly in Mercury, it turns
out that we need to change the order of the compiler passes, so that the
pass which was previously about 13th needs to become the 5th pass;
this will break some of the invariants that passes 6-12 depended on.
We'll need to go through the source code extremely carefully to make
sure that we fix all such code, but being human, there is a good chance
that we will miss a spot, and so I'm frankly quite glad that we've got a
de{*filter*} around in case we should need it.

Quote:
>> If you typically write small programs that manipulate small or simple
>> data structures, then you will find little need for a de{*filter*}.

>Ouch, I guess that hit the nail on my...I mean, the head. :-)  Yep, I
>typically do that, and yes, I do find exactly that.

>Okay, I'm convinced.  Thanks for the elaboration!

I hope you'll forgive me for elaborating even further ;-)

Cheers,
        Fergus.

--

WWW: < http://www.*-*-*.com/ ~fjh>  |   but source code lives forever"



Sat, 28 Jul 2001 03:00:00 GMT  
 Debugger for Hugs

Quote:
> Would it be meaningful to debug a program under one runtime system, and
> extrapolate the results to another?

The SML people have proved this for ML (the operational semantics of SML are
formally defined). I don't know about Haskell, but I would guess so, since
Haskell is IMHO a more elegant language and the evaluation rules are simpler.

All I personally want in a Haskell or ML de{*filter*} is an application that shows
the step by step beta-reductions and alpha-substitutions and lets you zoom in
on "parts" of an expression (since a Haskell program can be thought of as one
enormous expression).

  - aj

--
"Nobody has any 'Rights'. We are entitled only to Liberties"



Sat, 28 Jul 2001 03:00:00 GMT  
 Debugger for Hugs

Quote:

>> "Easy testing of functions from a command line" is very difficult to
>> achieve if your functions take as input large data structures with
>> complicated invariants,
>But would you be able to convince yourself of the correctness of the
>large data structure, even if its available for inspection from a
>de{*filter*}?  And couldn't you encode checks for those complicated
>invariants, and apply them to the input and output of the function in
>question to verify correctness?  Or am I missing the point?

An example may help here. Quite likey Fergus has in mind something
like the data structres in the Mercury compiler (written in Mercury,
not Haskell, but the principle still applies). By the time it reaches
code-generation, the structure representing the module being compiled
can easily be several Mb in size. The syntax tree is annotated with
the lifetimes of variables and their scopes. It is an invariant (at
code-generation time) that these correspond. We have had bugs where
the code-generator has died because these two pieces of information
are not corresponding for one or more variables. It is way too impractical
to create the appropriate data structure by hand - it would take a week!
With a de{*filter*}, the `structure' that we have to create is a test case
(which can sometimes be quite tricky itself), then we can set a break
point somewhere in the code-generator, or even better where the
variable life-times are computed, and look at the appropriate bits
of the very large data structure.

Quote:
>> If you typically write small programs that manipulate small or simple
>> data structures, then you will find little need for a de{*filter*}.
>Ouch, I guess that hit the nail on my...I mean, the head. :-)  Yep, I
>typically do that, and yes, I do find exactly that.

To put the above example in context, the Mercury compiler stands at
over 180 modules totalling almost 170K lines (nearly 6M of source).

Thomas
--

To a killer whale, otters are like hairy popcorn -- Paul Dayton



Sat, 28 Jul 2001 03:00:00 GMT  
 Debugger for Hugs

Quote:

> An example may help here. Quite likey Fergus has in mind something
> like the data structres in the Mercury compiler

[large and complex data structures]

But... does being able to visually inspect this data structure really
help a lot?  Yes, accessing the leaves and branches of the evaluation
tree post-facto would be good - but I am still thinking that integrity
checking of the data structure itself is better handled by running it
through ad-hoc integrity checking functions, no?

The 6M of source you cite below sure sounds more inviting to the eye,
than a similar amount of corrupted compiler thunk.  Am I mistaken?

Quote:
> To put the above example in context, the Mercury compiler stands at
> over 180 modules totalling almost 170K lines (nearly 6M of source).

Yep.  I'm still convinced you're right, and none of your arguments
change that :-)

-kzm
--
If I haven't seen further, it is by standing in the footprints of giants



Sun, 29 Jul 2001 03:00:00 GMT  
 Debugger for Hugs

Quote:

>> Would it be meaningful to debug a program under one runtime system, and
>> extrapolate the results to another?

>The SML people have proved this for ML (the operational semantics of SML are
>formally defined). I don't know about Haskell, but I would guess so, since
>Haskell is IMHO a more elegant language and the evaluation rules are simpler.

Haskell's evaluation rules are simpler in part because they are higher level.
Haskell is generally described using a denotational (declarative) semantics
rather than giving a lower-level operational semantics.  You can define
an operational semantics for Haskell pretty easily, but it will be
a nondeterministic semantics, whereas SML's operational semantics is
(for the most part) deterministic.  So if you debug the same program
twice, with SML you will generally get the same results, but with
Haskell the behaviour may be different each time.

However, with Haskell the end result will generally still be the same
each time -- the evaluation tree is the same, the nondeterministic
part is just the order in which the implementation traverses it.
So as I explained in my other posts, it is certainly useful to have
a de{*filter*} for lazy functional languages, even if the operational
semantics for those languages is nondeterministic.

Note that the operational semantics for C has a lot of nondeterministic
parts, but de{*filter*}s for C are still in strong demand! ;-)

--

WWW: < http://www.*-*-*.com/ ~fjh>  |   but source code lives forever"



Mon, 30 Jul 2001 03:00:00 GMT  
 Debugger for Hugs

Quote:


>> An example may help here. Quite likey Fergus has in mind something
>> like the data structres in the Mercury compiler

>[large and complex data structures]

>But... does being able to visually inspect this data structure really
>help a lot?  Yes, accessing the leaves and branches of the evaluation
>tree post-facto would be good - but I am still thinking that integrity
>checking of the data structure itself is better handled by running it
>through ad-hoc integrity checking functions, no?

Writing those ad-hoc integrity checking functions may be too much work,
and they may be too costly to check automatically.

Also, often the problem may be a violated postcondition (i.e. incorrect
results) rather than a data structure invariance problem as such.
For example, a particular stage of the compiler may simply generate
incorrect code (code that does not have the same semantics as the
input) rather than generating code which is internally inconsistent.
In cases like that, post-condition checking functions won't help, because
the checking problem is undecidable.  Even in cases where the checking
problem is decidable, writing a post-condition checking functions
may be just as difficult as writing the program in the first place.

Quote:
>The 6M of source you cite below sure sounds more inviting to the eye,
>than a similar amount of corrupted compiler thunk.  Am I mistaken?

No.  We do indeed get the compiler to pretty-print its internal
data structures to files, so that they appear more like source code,
and use those dumps to isolate bugs to particular passes of the compiler.
But that only takes you so far.  A de{*filter*} is still very helpful in
isolating the bug to a more fine-grained level, i.e. a particular
procedure rather than just a whole compiler pass.

--

WWW: < http://www.*-*-*.com/ ~fjh>  |   but source code lives forever"



Mon, 30 Jul 2001 03:00:00 GMT  
 
 [ 14 post ] 

 Relevant Pages 

1. Debugger for Hugs 1.4

2. Hugs Debugger

3. Debuggers, Static Debuggers, and Algebraic Steppers

4. using python debugger (pdb) inside emacs debugger mode ...

5. small hugs problem

6. indexOf (Hugs Bug?)

7. Hugs error...

8. Hugs Graphic Library

9. Help with Haskell (Hugs)!!!

10. very very stupid newbie question about Hugs

11. Hugs - stack ?

12. Readline for Hugs?

 

 
Powered by phpBB® Forum Software