Skip to main content

Implementing Escher on a Graph Reduction Machine

Kerstin Eder, Implementing Escher on a Graph Reduction Machine. Proceedings of the International Workshop on Implementation of Declarative Languages (IDL'99), pp. 1–20. September 1999. PDF, 244 Kbytes.


Escher is a functional logic programming language which is based on a rewriting computational model with residuation. Similar to purely functional languages, computation is regarded as the successive application of rewrite rules to an expression until the expression cannot be reduced further; there is only one computation path. Logic computations are integrated into functional computations via a well-chosen collection of rewrite rules that allow to handle the logic connectives, quantification, unification and set processing. These rules are rather unconventional. Most of them are not constructor-based, and a comprehensive study was necessary to understand the intended behaviour of Escher programs. The efficient implementation of Escher's computational model is a considerable challenge. This paper gives an overview of a simple graph reduction machine and some of the extensions and modifications needed to support Escher. Sharing is the key for high performance in purely functional language implementations, but cannot always be used safely in graph reduction where redexes are not ground. A technique to utilise sharing in an Escher implementation is introduced and discussed.

Bibtex entry.

Contact details

Publication Admin