Needed Computations Shortcutting Needed Steps

Sergio Antoy
Jacob Johannsen
Steven Libby

We define a compilation scheme for a constructor-based, strongly-sequential, graph rewriting system which shortcuts some needed steps. The object code is another constructor-based graph rewriting system. This system is normalizing for the original system when using an innermost strategy. Consequently, the object code can be easily implemented by eager functions in a variety of programming languages. We modify this object code in a way that avoids total or partial construction of the contracta of some needed steps of a computation. When computing normal forms in this way, both memory consumption and execution time are reduced compared to ordinary rewriting computations in the original system.

In Aart Middeldorp and Femke van Raamsdonk: Proceedings 8th International Workshop on Computing with Terms and Graphs (TERMGRAPH 2014), Vienna, Austria, July 13, 2014, Electronic Proceedings in Theoretical Computer Science 183, pp. 18–32.
Published: 26th May 2015.

ArXived at: http://dx.doi.org/10.4204/EPTCS.183.2 bibtex PDF
References in reconstructed bibtex, XML and HTML format (approximated).
Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org