Open Prolog: a Structure-Sharing Prolog for the Macintosh

Abstract

This thesis explores the design and implementation of a Prolog system with just one mode of program execution rather than the two modes of execution— interpretation and compilation—present in most Prolog implementations in use today. The main contribution of the thesis is such a design, combining reasonably high runtime performance with the ability to modify, debug and inspect program code. The design has been realised as Open Prolog, a complete Prolog environment with an integrated editor and debugger, built for the Apple Macintosh with a Motorola 68000 instruction set. The implementation supports the argument that the design offers high speed compilation combined with reasonably high speed implementation and simplicity of implementation, and compares favourably, in terms of speed of execution and ease of program development, with a number of other implementations. This work is concerned with the design and implementation of Open Prolog: the overall architecture, static and dynamic aspects of the system, including code representation, the image machine, compilation, data areas, the runtime behaviour of the system, built-in predicates and garbage collection. The performance of the implementation is benchmarked and compared with a number of other implementations, and the results of a low-level profiling study are presented.

Contribution The principal contribution is a design for a Prolog implementation based on relatively simple principles that combines high speed compilation and reasonable runtime performance with the ability to modify, inspect and debug Prolog code. Influenced by principles of Direct Correspondence Architectures, the design is based on an abstract machine with an instruction set such that every aspect of the source code is represented in the machine code. This facilitates the decompilation of machine code, i.e. the reconstruction of the source code, for inspection and debugging purposes. It also simplifies compilation. A number of subsidiary contributions are made with the intention of enhancing the design in various ways. These and suggestions for further development of the implementation are made at the end of the work.