EMA: Implementing the Rewriting Computational Model of Escher

Kerstin I. Eder, EMA: Implementing the Rewriting Computational Model of Escher. PhD thesis. Department of Computer Science, University of Bristol. November 1998. PDF, 1074 Kbytes.


Escher is a new functional logic programming language which was designed to combine the best ideas of existing single-paradigm languages. The computational model of Escher is based on rewriting with residuation. The Escher systems module Booleans contains a number of well-chosen rewrite rules which define the basics of logic programming in Escher. Due to the novel integration approach of functional and logic features that is used in Escher, four years ago it was still an unresolved issue whether Escher could be implemented efficiently. This thesis is devoted to finding such an efficient implementation for Escher. A comprehensive study of the Escher language and its computational model, especially the functions in the Booleans module, has been carried out. Based on the results of this study, the Brisk machine (which supports the purely functional language Haskell) has been identified as an abstract machine to serve as the basis for an Escher implementation. It is a simplified version of the Spineless Tagless G-machine, a machine which is considered to provide the fastest implementation of a lazy functional language. The Brisk machine has a basic graph reduction architecture. This thesis discusses how to extend and modify this machine by introducing a number of new components which support the functions in the Escher Booleans module. The resulting Escher machine (EMA) implements the pure rewriting computational model of Escher; it supports logic variables, residuation, pattern matching on function symbols and set processing in the Escher style. A new approach to utilise different forms of sharing in the presence of variables in function calls has been successfully integrated into the machine model. The language of the abstract machine resembles the STG language but is even simpler. A number of built-in functions are provided: one set deals with complicated control-related issues like evaluation, application and partial application; and the other supports the system functions in the Escher Booleans module. Quantification and set expressions can easily by integrated into the machine language by using specialised lifting techniques. The thesis contains the compilation route from Escher into the language of the abstract machine, and also a description of the machine's operational semantics, which can be given in the form of a state transition system. To demonstrate the feasibility of the proposed extensions and modifications, the Escher compiler and the abstract machine have been implemented on the basis of the Brisk machine. The system is still in its early stages and does not employ any of the optimisations possible for an STG-like machine. The results obtained from the implementation show that more research is necessary to increase the performance of the machine. However, a first step towards an efficient implementation has now been made.

Bibtex entry.

Contact details

Publication Admin