On Graph Rewriting, Reduction and Evaluation

Abstract

We inter-derive two prototypical styles of graph reduction: reduction machines à la Turner and graph rewriting systems à la Barendregt et al. To this end, we adapt Danvy et al.’s mechanical program derivations from the world of terms to the world of graphs. We also outline how to inter-derive a third style of graph reduction: a graph evaluator.

References

Slides from the talk at TFP’09. May 02, 2009, Komárno, Slovakia. Revision November 2009.

Full derivation and tests in Standard ML. Revision November 2009.

Official TFP09 website.

designed by krukkenlund ∙ written in emacs ∙ generated with pandoc ∙ valid: xhtml, css