Graphical graph reduction

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
13 messages Options
Reply | Threaded
Open this post in threaded view
|

Graphical graph reduction

dainichi
Hi Haskell-Cafe,

I'm relatively new to Haskell, but have a background with SML. One of the things that amaze me about Haskell is lazy graph reduction, e.g. how the graph unfolds during the evaluation of, say,

let fibs = 1 : 1 : zipWith (+) fibs (tail fibs) in take 10 fibs

Lazy lists can be simulated in SML too, but unless I do something clever with references, I end up taking exponential time to compute the n'th Fibonacci number.

Now to the point: Wouldn't it be great if I had a visual tool that visually showed me the graph while the above evaluation unfolded? I could use it to show some of my co-workers to whom laziness is a mystery, what it's all about.

Does anybody know if such a tool exists? I'd be grateful for pointers if it does. I very much doubt that I'm the first person who has thoughts like this, but then again, who knows. People who really know Haskell might think this is too trivial a task to really be worth spending time on.

If nothing similar exists, I was thinking about creating such a tool (i.e. an interpreter with additional graph-displaying features) for a very, very small subset/dialect of Haskell. I would probably be lazy (no pun intended) and start right away with abstract syntax trees to avoid lexing and parsing and such. My language of implementation would be SML, using references as the edges of the graph.

Any ideas/comments would be welcome.

Kai



_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Graphical graph reduction

Bulat Ziganshin-2
Hello dainichi,

Friday, February 22, 2008, 6:55:54 PM, you wrote:

> If nothing similar exists, I was thinking about creating such a
> tool (i.e. an interpreter with additional graph-displaying features)

not exactly this, but now i'm reading introduction into Q language [1]
which says on p.11 "The interpreter has a built-in symbolic debugger
which allows you to execute a reduction sequence step by step: ...",
so you may use it to demonstrate how reductions work. Q by itself is
rather interesting language - haskell-like syntax, dynamic, eager with
good support for laziness. btw, this manual is probably better than we
have for Haskell, i've seen programmers who thinks that Haskell is
hard to learn and Q is simple and may be it's just due to its manual
which takes into account typical learning problems and explains
"obvious" things (which are really obvious only for seasoned FP
programmers)

[1] http://switch.dl.sourceforge.net/sourceforge/q-lang/qnutshell-0.5.pdf


--
Best regards,
 Bulat                            mailto:[hidden email]

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Graphical graph reduction

Svein Ove Aas
In reply to this post by dainichi
2008/2/22  <[hidden email]>:

> Does anybody know if such a tool exists? I'd be grateful for pointers if it
> does. I very much doubt that I'm the first person who has thoughts like
> this, but then again, who knows. People who really know Haskell might think
> this is too trivial a task to really be worth spending time on.
>
> If nothing similar exists, I was thinking about creating such a tool (i.e.
> an interpreter with additional graph-displaying features) for a very, very
> small subset/dialect of Haskell. I would probably be lazy (no pun intended)
> and start right away with abstract syntax trees to avoid lexing and parsing
> and such. My language of implementation would be SML, using references as
> the edges of the graph.
>
> Any ideas/comments would be welcome.
>
Rather than spending time on a project specifically to do this, it
seems like a great addition to GHCi's still mostly theoretical
debugger. I'll understand if you don't want to take on such a project
right now, though.

I'm not aware of any program that does exactly what you're asking for,
but I'm attaching a lambdabot interaction for your reading pleasure. I
believe it will speak for itself.

< Baughn> > let fibs = 1 : 1 : zipWith (+) fibs (tail fibs) in fibs :: [Expr]
< lambdabot>  [1,1,1 + 1,1 + (1 + 1),1 + 1 + (1 + (1 + 1)),1 + (1 + 1)
+ (1 + 1 + (1 + (1 ...
1

--
In a demon-haunted world, science is a candle in the dark
http://dresdencodak.com/
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Graphical graph reduction

Heinrich Apfelmus
In reply to this post by dainichi
Kai wrote:
> Wouldn't it be great if I had a visual tool that visually
> showed me the graph while the above evaluation unfolded?
>
> Does anybody know if such a tool exists?

I don't know of such a tool, the closest one to that is probably the new
ghci debugger.

There is also a paper and accompanying website

   Peter Sestoft. "Demonstrating Lambda Calculus Reduction".
   http://www.dina.kvl.dk/~sestoft/lamreduce/

but graph reduction with sharing is not covered.

Slightly off topic, Twan's blog post

   http://twan.home.fmf.nl/blog/haskell/
     simple-reflection-of-expressions.details

demonstrates a neat way to figure out how (polymorphic) higher-order
functions like  foldr  or  foldl  work. It would be really cool if there
was a similar embedded approach for graph reduction, but I don't think
that's possible.

> If nothing similar exists, I was thinking about creating such a tool (i.e.
> an interpreter with additional graph-displaying features) for a very, very
> small subset/dialect of Haskell.

The Haskell wikibook <http://en.wikibooks.org/wiki/Haskell> would
greatly benefit from such a tool for the chapters about graph reduction,
so I'd be a potential user :)

> I would probably be lazy (no pun intended)
> and start right away with abstract syntax trees to avoid lexing and parsing
> and such.  My language of implementation would be SML, using references as
> the edges of the graph.

Of course, I'd prefer Haskell as the implementation language and since
you want to learn Haskell anyway ... :)

Concerning the graph representation, using references is probably a bad
idea anyway since they're not purely functional in style. There is
Martin Erwig's Functional Graph Library (Data.Graph.Inductive) shipping
with ghc:

   Martin Erwig. Inductive Graphs and Functional Graph Algorithms.
   http://web.engr.oregonstate.edu/~erwig/papers/abstracts.html#JFP01

There is also

   Norman Ramsey, João Dias.
   "An Applicative Control-Flow Graph Based on Huet’s Zipper".

which uses a zipper to represent a control-flow graph. I'm mentioning
this paper for the following quote: "the mutable flow graph was big and
complex, and it led to many bugs. We have replaced it by a smaller,
simpler, applicative flow graph based on Huet’s (1997) zipper. The new
flow graph is a success." In other words: forget mutable references :)

Moreover, it's not clear whether a graph should be used at all. Well, at
least concerning the _presentation_. A todo-note at the beginning of
<http://en.wikibooks.org/wiki/Haskell/Graph_reduction> lists the
possible choices, I'm currently leaning in favor of a  let .. in
statements in the spirit of

   John Maraist, Martin Odersky and Philip Wadler.
   "The call-by-need lambda calculus".
   http://homepages.inf.ed.ac.uk/wadler/topics/
     call-by-need.html#need-journal


Overall, the main problem for a graph reduction demonstration tool to
solve is not how to perform graph reduction but how to present it. The
point is: the tool is unnecessary for very simple examples since those
are better done by hand. But an unsophisticated tool is useless for the
more complicated cases too, since no one can make sense of the output
anymore!


Regards,
apfelmus

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Graphical graph reduction

Kim-Ee Yeoh-2
In reply to this post by dainichi
dainichi wrote
Now to the point: Wouldn't it be great if I had a visual tool that visually
showed me the graph while the above evaluation unfolded? I could use it to
show some of my co-workers to whom laziness is a mystery, what it's all
about.
Check out http://thyer.name/lambda-animator/. Requires Java.

Explores several forms of laziness and them some.
Reply | Threaded
Open this post in threaded view
|

Re: Graphical graph reduction

Dominic Steinitz
In reply to this post by dainichi
About 7 years ago such a tool existed:

 http://www.cs.kent.ac.uk/people/staff/cr3/toolbox/haskell/GHood/

I don't know if Claus is around. Perhaps he could give you more information.

Dominic.



_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Re: Graphical graph reduction

Claus Reinke
> About 7 years ago such a tool existed:
>
> http://www.cs.kent.ac.uk/people/staff/cr3/toolbox/haskell/GHood/

GHood was never intended to visualize graph reduction
directly (*). instead, it visualized observations - ie, you
could see if and when which parts of an observed data
structure was inspected during a program run, but not
the reductions themselves, and definitely not sharing as
in the cyclic programming example earlier in this thread.

GHood was very helpful in visualizing some aspects of
non-strict evaluation, and its main advantage over Hood
was in observing relative strictness, dynamically: you
could not only see which parts of an observed data
structure were used at all, but by observing both the
input and the output of a function, you could see the
demands for the output drive the demands for the
input. very useful for spotting strictness bugs, such
as demanding too much of the input too early, instead
of just as much as needed to produce just as much as
used for producing the output. see the example applets
on that GHood page.

claus

(*) it was, however, the lack of reduction animation
in haskell implementations that kept me looking for
such opportunities (i had grown up, functionally,
with the kiel reduction systems, and their built-in
support for displaying and editing intermediate reduction
results, with higher-order functions, free variables, avoiding
name clashes, and all, and was missing all that support in
the supposedly more modern world of haskell..)  

an earlier, simpler, example was the use of overloading
to visualize intermediate expressions, so you could see
the difference between foldr and foldl, etc:

http://www.cs.kent.ac.uk/people/staff/cr3/toolbox/haskell/R.hs

btw, in one of the previous incarnations of this thread,
Wolfram Kahl used the HOP System to generate
graphical traces of term-graph reductions:

http://www.cas.mcmaster.ca/~kahl/HOPS/


_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Graphical graph reduction

Jacques Carette
In reply to this post by dainichi
I think HOPS is what you are looking for
http://www.cas.mcmaster.ca/~kahl/HOPS/

It may advertize itself otherwise, but the main thing you 'see' when
running programs in fully explicit mode is exactly all the graph reductions.

Jacques
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe

Reply | Threaded
Open this post in threaded view
|

Re: Graphical graph reduction

Cale Gibbard
Is there any place that can we download the HOPS program itself? It
unfortunately doesn't seem available from that page.

On 24/02/2008, Jacques Carette <[hidden email]> wrote:

> I think HOPS is what you are looking for
>
> http://www.cas.mcmaster.ca/~kahl/HOPS/
>
>
> It may advertize itself otherwise, but the main thing you 'see' when
>  running programs in fully explicit mode is exactly all the graph reductions.
>
>
>  Jacques
>
> _______________________________________________
>  Haskell-Cafe mailing list
>  [hidden email]
>  http://www.haskell.org/mailman/listinfo/haskell-cafe
>
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe

Reply | Threaded
Open this post in threaded view
|

Re: Graphical graph reduction

dainichi
In reply to this post by Jacques Carette
Thank you all for showing interest and responding.

> Check out http://thyer.name/lambda-animator/. Requires Java.

Wow, this is SUCH a cool tool. Best discovery in a long time! I think
I need to brush up on my lambda-calculus, because it took me some time
to figure out what settings to use to get something similar to
Haskell. Function strategy "substitute by name", Argument strategy
"call by need" and Reduce to "weak head normal form" seem to work OK,
though.

One issue, though. When trying out my infinite-list-of-fibs example, I
have an auxiliary function

(define nth (lambda (n xs) (if (= n 0)(head xs)(nth (- n 1) (tail xs)))))

and this is not behaving the way I want, i.e. like the Haskell function

nth n (x:xs) = if n == 0 then x else nth (n-1) xs

because it doesn't do pattern matching, i.e. it doesn't force the
argument to be evaluated until it fits the x:xs pattern. I can't
figure out to simulate this eager pattern in the lisp that the
lambda-animator uses. This means that if I e.g. do a (nth 8 fibs) in
the animator, I get a long string of tail's before it actually starts
expanding the fibs list...

Anyway, on the side, I also started working on this myself in SML New
Jersey. (Sorry, this will probably make me unpopular here on
Haskell-cafe, but the ability to use references was just too tempting,
and I'm not too experienced with purely functional data structures).
My approach isn't as general, though, I don't have lambda's and
apply's in my syntax tree. I just have functions there as nodes, and
then the application of them has to be implemented as reduction rules.
This approach does make the graph a bit less messy to look at, though.
Also, since I implement the reduction rules myself, the pattern
matching problem described above isn't a problem.

> I think HOPS is what you are looking for
> http://www.cas.mcmaster.ca/~kahl/HOPS/

Yes, HOPS looks very promising. However, I cannot find the download
link either. And Kahl hasn't replied to my email yet.

Again, thank you all for replying.
Kai
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe

Reply | Threaded
Open this post in threaded view
|

Re[2]: Graphical graph reduction

Bulat Ziganshin-2
Hello dainichi,

Monday, February 25, 2008, 2:46:20 AM, you wrote:

> Jersey. (Sorry, this will probably make me unpopular here on
> Haskell-cafe, but the ability to use references was just too tempting,
> and I'm not too experienced with purely functional data structures).

we have references, Data.IORef. there is also pretty-syntax library
for them, see http://haskell.org/haskellwiki/Library/ArrayRef


--
Best regards,
 Bulat                            mailto:[hidden email]

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Graphical graph reduction

Taral
In reply to this post by dainichi
On 2/24/08, [hidden email] <[hidden email]> wrote:
>  (define nth (lambda (n xs) (if (= n 0)(head xs)(nth (- n 1) (tail xs)))))

>  nth n (x:xs) = if n == 0 then x else nth (n-1) xs

I'm guessing it's some kind of lisp variant?

(define nth (lambda (n xs) (cond ((consp xs) (if (= n 0) (head xs)
(nth (- n 1) (tail xs)))) (t nil)))

--
Taral <[hidden email]>
"Please let me know if there's any further trouble I can give you."
    -- Unknown
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Graphical graph reduction

Mike Thyer
In reply to this post by Jacques Carette
Kai wrote:

> Thank you all for showing interest and responding.
>
>> Check out http://thyer.name/lambda-animator/. Requires Java.
>
> Wow, this is SUCH a cool tool. Best discovery in a long time! I think
> I need to brush up on my lambda-calculus, because it took me some time
> to figure out what settings to use to get something similar to
> Haskell. Function strategy "substitute by name", Argument strategy
> "call by need" and Reduce to "weak head normal form" seem to work OK,
> though.

Yes those are the correct settings for a Haskell-like reduction order.

> One issue, though. When trying out my infinite-list-of-fibs example, I
> have an auxiliary function
>
> (define nth (lambda (n xs) (if (= n 0)(head xs)(nth (- n 1) (tail xs)))))
>
> and this is not behaving the way I want, i.e. like the Haskell function
>
> nth n (x:xs) = if n == 0 then x else nth (n-1) xs
>
> because it doesn't do pattern matching, i.e. it doesn't force the
> argument to be evaluated until it fits the x:xs pattern. I can't
> figure out to simulate this eager pattern in the lisp that the
> lambda-animator uses. This means that if I e.g. do a (nth 8 fibs) in
> the animator, I get a long string of tail's before it actually starts
> expanding the fibs list...

You can use the seq function to force arguments to be evaluated.  For example:

(define nth (lambda (n xs) (seq xs if (= n 0)(head xs)(nth (- n 1) (tail xs)))))

The input language is a curried dialect of Scheme.  The seq function only takes two arguments.  It reduces its first argument and then returns its second.  This ensures the pair at the root of xs is
evaluated before the evaluation of the function body continues.

You can similarly use seq to prevent an unbounded build up of suspended computations in the fibs list, for example:

(define head-strict-cons (lambda (h t) (seq h cons h t)))
(define zipWith (lambda (f xs ys) (head-strict-cons (f (head xs) (head ys)) (zipWith f (tail xs) (tail ys)))))
(define fibs (letrec ((fibs (cons 1 (cons 1 (zipWith + fibs (tail fibs)))))) fibs))
(define nth (lambda (n xs) (seq xs if (= n 0)(head xs)(nth (- n 1) (tail xs)))))
(define fib (lambda (n) (nth n fibs)))

You'll see that the size of the graph is bounded and that no more than three elements of the infinite fibs list exist at any one time.

Lambda Animator doesn't automatically do any of the deforestation that a Haskell compiler will, so there are more reduction steps and larger graphs in the reduction of the above program than you would
expect with a compiled Haskell program.

Mike

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe