Implementing Escher on a Graph Reduction Machine

Abstract. 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 computa-tions via a well-chosen collection of rewrite rules that allow to handle the logic connectives, quantication, unication 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 ecient 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 modications 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.