[Haskell-cafe] Re: Graphical graph reduction

[apfelmus]

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