A Self-Applicable Partial Evaluator for the Logic Programming Language Godel

Abstract

Partial evaluation is a program specialisation technique that has been shown to have great potential in logic programming, particularly for the specialisation of meta-interpreters by the so-called “Futamura Projections”. Meta-interpreters and other meta-programs are programs which use another program as data. In this thesis we describe a partial evaluator for meta-programs in the logic programming language Gödel. Gödel is a declarative, general-purpose language which provides a number of higher-level programming features, including extensive support for meta-programming with a ground representation. The ground representation is a standard tool in mathematical logic in which object level variables are represented by ground terms at the meta-level. The ground representation is receiving increasing recognition as being essential for declarative meta-programming, although the computational expense that it incurs has largely precluded its use in the past. This thesis extends the basic techniques of partial evaluation to the facilities of Gödel. Particular attention is given to the specialisation of the inherent overheads of meta-programs which use a ground representation and the foundations of a methodology for Gödel meta-programs are laid down. The soundness of the partial evaluation techniques is proved and these techniques are incorporated into a declarative partial evaluator. We describe the implementation and provide termination and correctness proofs for the partial evaluator SAGE, an automatic program specialiser based upon sound finite unfolding that is able to specialise any Gödel meta-program (or indeed, any Gödel program at all). A significant illustration of the success of our techniques for specialising meta-programs which use a ground representation is provided by the self-application of this partial evaluator. We use the partial evaluator to specialise itself with respect to a range of meta-programs. By virtue of its self-applicability SAGE has been used to produce a compiler-generator, which we believe shall prove to be an immensely powerful and useful tool for meta-programming.