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
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
