Computing Publications

Publications Home » Implementing Logic Languages by G...

Implementing Logic Languages by Graph Rewriting

Peter McBrien

PhD Thesis
Imperial College London, Department of Computing

The use of graph rewriting as a computational model for computer programming languages has received considerable attention in the scientific literature over the past decade. Whilst the implementation of functional programming languages by graph rewriting is simple and intuitive, the implementation of logic programming languages is less direct and consequently has been more limited in practice.

After describing some of the problems associated with a `direct' approach to implementing logic programming by graph rewriting, and comparing the situation to that found when using term rewriting, this thesis sets out to address the problems by proposing two innovations. The first is a modified form of graph rewriting, which supports some features of term rewriting, and directly supports the notion of the logical variable and backtracking on variables. The second is a compiler target language and corresponding abstract machine, which efficiently implements such modified graph rewriting on conventional Von Neumann computer architectures. A proof that the abstract machine correctly implements the compiler target language is given.

The approach is illustrated by demonstrating how it may be used to implement both Prolog and a more novel logic programming language called the PLL. The graph rewriting language and its associated abstract machine have been the subject of an implementation in the C language, and thus the results described within this thesis have been realized in practice. Issues relating to the use of the techniques described on a parallel computer architecture are also briefly dealt with, but no practical work has been conducted in this direction.

Postscript of full publication (4.3 megabytes)
(need help viewing Postscript files?)
BibTEX file for the publication
Conditions for downloading publications from this site. built & maintained by Ashok Argent-Katwala.