Content area
Declarative meta-programming is vital, since it is the most promising means by which programs can be made to reason about other programs. A meta-program is a program that takes another program, called the object program, as data. A declarative programming language is a programming language based on a logic that has a model theory.
A meta-program operates on a representation of an object program. In a non-ground representation, object-level variables are represented by meta-variables; in a ground representation, object-level variables are represented by ground terms. The non-ground representation is insufficiently expressive for most meta-programming tasks. The ground representation is adequately expressive, but meta-programs are complex and laborious to write, and the overhead of interpretation is excessive.
Gödel is a declarative programming language based on first-order logic. It has types and modules, improves on the expressiveness and declarative semantics of Prolog, and provides extensive support for meta-programming in the ground representation.
This thesis contributes to the design of Gödel's meta-programming facilities, and investigates the techniques required to make declarative meta-programming practical. The presentation of Gödel object programs as ground terms is described. Library modules and abstract types eliminate much of the labour and complexity of meta-programming. An analysis of the sources of interpretation overhead is conducted, and an idiom for the construction of potentially efficient interpreters is developed. Carefully designed interpreters are improved significantly by a basic partial evaluator, but not all interpreter designs are susceptible. Experiments suggest that specialised interpreters can be improved still further by specific low-level mechanisms. SLDQE-resolution, a novel computational model for the compilation of programs containing universally quantified implication formulas, is also presented.
The problem of providing a language for declarative meta-programming that is both adequately expressive and efficiently executable is not completely solved, but this work demonstrates that the possibilities of a simple ground representation deserve to be taken seriously.