Graphical graph reduction
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
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:Bulat.Ziganshin@gmail.com
2008/2/22
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/
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
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. -- View this message in context: http://www.nabble.com/Graphical-graph-reduction-tp15637156p15649433.html Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com.
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.
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/
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
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
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 Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
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
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:Bulat.Ziganshin@gmail.com
On 2/24/08, dainichi@gmail.com
(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
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
participants (11)
-
apfelmus -
Bulat Ziganshin -
Cale Gibbard -
Claus Reinke -
dainichi＠gmail.com -
Dominic Steinitz -
Jacques Carette -
Kim-Ee Yeoh -
Mike Thyer -
Svein Ove Aas -
Taral