Logic Programming

Prolog (4)

Metaprogramming

A metaprogram is a program which takes other programs as data. Most declarative programming languages, especially Prolog, are powerful enough to possess other languages and programming paradigms. This is because Prolog implements symbol manipulation. This feature enables replacing a term or an argument with a predicate without loosing overall logical sense. For example:

good_at_prolog(X) :- good_at(X,prolog).

No syntax modification is necessary to implement metaprogramming as the predicates can be substituted by terms, clauses by lists of predicates and so on. The interpreter does not need to be modified too as the computation does not change its logical sense.

As well as the ability to implement other languages, Prolog is also a meta-interpreter (an interpreter for Prolog written in Prolog). This feature of declarative metaprogramming makes it very useful for prototyping, implementing new ideas and developing new languages.

Prolog meta-interpreter

Meta-interpreters differ from regular interpreters because of the additional functionality they provide. They input a program and a goal and derive the goal with respect to the program. This is equivalent to proving that the program logically implies the goal; so the meta-interpreter traces the execution and generates the proof tree. In order to make a proof tree it is necessary to break down the 'grain size' of the interpreter. This is done by the built-in predicate, from Prolog's library. Allowing the computation to be split into its head and body and analysed separately. The body, depending on its complexity, can be a unit clause or a rule, which will be broken down again into a sequence of goals. The head, however, must never be a variable. This tracing feature of Prolog limits the number of sub-goal calls and ensures that the interpreter will never execute an infinite loop and run out of memory. Thus the sequence of splitting the other goals must eventually end.

For example:
Computation: (Head, Body)
Body: (Goal, Other Goals)
Other goals: (unit computation)