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 cyclic graphs. We also outline how to inter-derive a third style of graph reduction: a graph evaluator.


Ian Zerny. On Graph Rewriting, Reduction, and Evaluation in the Presence of Cycles. Higher-Order and Symbolic Computation. To appear. [BIB].
Ian Zerny. On Graph Rewriting, Reduction, and Evaluation. In Zoltán Horváth, Viktória Zsók, Peter Achten, and Pieter Koopman, editors, Trends in Functional Programming Volume 10. Intellect Books, 2011, 81–112. Best student-paper award of TFP 2009. [BIB], [PDF].

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.