Towards fast and declarative meta-programming

Meta-programming, the ability to manipulate programs as data, is fundamental to the suc-cess of declarative languages. Regardless of the choice of logic, without properly representing object variables as ground terms, declarative meta-programs are severely limited. However, use of the ground representation seems to involve unacceptable programming eort and computational overhead. We examine the underlying reasons for these problems, and investigate techniques for addressing them so that the dream of declarative meta-programming can be realised. Godel is a programming language based on rst order logic which is intended to have better declarative semantics than Prolog. Taking Godel interpreters as typical meta-programs, we show how aware-ness of eÆciency issues in the interpretation algorithm suggests a particular programming style. The careful design and construction of the Godel system modules has made writing such inter-preters straightforward, and also made them amenable to partial evaluation. By using mutable data structures to represent programs and substitutions, it is possible to optimise these inter-preters further until they approach the speed of interpreters using the traditional non-ground representation. The details of these optimisations may remain entirely hidden from the pro-grammer. The eÆciency gains apply equally to interpreters performing tasks that require the full power of the ground representation, and so have no declarative non-ground equivalent for comparison.