Tuesday, June 9, 2009

Visualizing the graphrewrite process behind Haskell

As I have already mentioned in the introduction post, I am currently working on version 0.4 of visual-graphrewrite, which is destined to be a tool to show steps of the graph rewriting process executed when evaluating a particular expression in the context of a Haskell module.

What does this mean (if you are familiar with term/graph rewrite systems, you might as well skip this paragraph)? Each time you write an expression that you want to be evaluated, a slightly complicated process is begun by the runtime system (or interpreter or whatever that's evaluating your code), which is called graph reduction. This process essentially tries to automagically make sense of the expression you have written by using a set of rules (which are, surprisingly, called rewrite rules). These rules basically come from functions defined in the context of your expression and are represented mostly by function definitions in Haskell.
The rewrite process takes your expression and tries to search a matching rule. This means just what you think: it tries to find a function definition that fits the expression. Since rewrite rules come from function definitions, each and every rewrite rule has a right hand side which corresponds to an expression on the right hand side of = in a function definition. So if a matching rule is found, the right hand side of the rule is written in place of your original expression - with the correct actual arguments of course. This is about all that is to a rewrite step. This is then repeated over and over again, until there is no matching rule left, when it is said that the resulting expression is in normal form.

Now this tool tries to visualize these steps by representing the expression with a graph and drawing it on-screen. The ultimate goal is to be able to take any haskell98 module and be able to use it as a context for an arbitrary (but correct) expression to execute the rewriting procedure. This should be able to get a behind-the-scenes peek of what is going on when your functional program is running. It is intended as a demonstration tool for newcomers to the functional world, but it can also be used as a debugging tool, although I admit that I have never debugged anything with it to this day on.

The current version uploaded to hackage is only version 0.3.2 which doesn't actually show the rewrite steps, instead it shows only the right hand sides of rule definitions in a given module (that is, function definitions). There is a README file in the package which goes on lying about some next version released by the end of May but some complications arose (I didn't count with the fact that I had to prepare a paper as well for my degree), so this next version is still in the works, although it looks promising as shown on the right.

If you are interested in the source code (or my thesis which is unfortunately only available in hungarian /yet?/), you should check out the project's github page.

Thanks for reading, I hope to write some more details about the project in the not so distant future, so stay tuned! :)


Hello, world!

This is my first serious attempt at blogging, so please bear with me. Since I am just finishing my thesis and it is about graph rewriting in functional languages, particularly in Haskell, I thought that I could post some ideas that come to my mind about such things so when someone hopefully reads all this, he/she will be shocked by how much I can complicate such simple matters and post a really elegant solution to my problems. :)

Aside from Haskell, I am also a system administrator at one of Hungary's largest universities, Eotvos Lorand University of Sciences (I am in charge of the Caesar cluster), so it is possible that some posts concerning general UNIX issues will eventually slip in.

Well, here goes nothing...

(Edit: I wonder why this is Anonymous)