[Haskell-cafe] Re: Graphical graph reduction
apfelmus at quantentunnel.de
Fri Feb 22 12:05:50 EST 2008
> 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
There is also a paper and accompanying website
Peter Sestoft. "Demonstrating Lambda Calculus Reduction".
but graph reduction with sharing is not covered.
Slightly off topic, Twan's blog post
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
> 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
Martin Erwig. Inductive Graphs and Functional Graph Algorithms.
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".
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
More information about the Haskell-Cafe