Skip to main content

Effective Meta-programming in Declarative Languages

Antony Bowers, Effective Meta-programming in Declarative Languages. PhD thesis. Department of Computer Science, University of Bristol. January 1998. PDF, 889 Kbytes.

Abstract

Abstract Declarative meta-programming is vital, since it is the most promising means by which programs can be made to reason about other programs. A metaprogram 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 metavariables; 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. Godel 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 Godel meta-programming facilities, and investigates the techniques required to make declarative metaprogramming practical. The representation of Godel 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.

Bibtex entry.

Publication Admin