13.5.1 Base Languages and Metalanguages

We require a representation of the base-level expressions that can be manipulated by the interpreter to produce answers. Initially, the base language will also be the language of definite clauses. Recall that the definite clause language is made up of terms, atoms, bodies, and clauses.

The metalanguage refers to these syntactic elements of the base language. Thus, meta-level symbols will denote base-level terms, atoms, bodies, and clauses. Base-level terms will denote objects in the domain being modeled, and base-level predicates will denote relations in the domain.

One of the advantages of a meta-interpreter over writing an interpreter for a whole new language is that the object level can use the meta-level constructs. When writing a logic programming meta-interpreter, there is a choice of how to represent variables. In the non-ground representation, base-level terms are represented as the same term in the metalanguage, so in particular, base-level variables are represented as meta-level variables. This is in contrast to the ground representation, where base language variables are represented as constants in the metalanguage. The non-ground representation means that meta-level unification is available to be used for unifying base-level terms. The ground representation allows the implementation of more sophisticated models of unification.

Example 13.20: In a non-ground representation, the base-level term foo(X,f(b),X) will be represented as the meta-level term foo(X,f(b),X).

In a ground representation, the base-level term foo(X,f(b),X) may be represented as foo(var(x),f(b),var(x)), where var is a meta-level function symbol that denotes the variable with the name given as its argument.

We will develop a non-ground representation for definite clauses. The metalanguage must be able to represent all of the base-level constructs.

The base-level variables, constants, and function symbols are represented as the corresponding meta-level variables, constants, and function symbols. Thus, all terms in the base level are represented by the same term in the meta-level. A base-level predicate symbol p is represented by the corresponding meta-level function symbol p. Thus, the base-level atom p(t1,...,tk) is represented as the meta-level term p(t1,...,tk).

Base-level bodies are also represented as meta-level terms. If e1 and e2 are meta-level terms that denote base-level atoms or bodies, let the meta-level term oand(e1,e2) denote the base-level conjunction of e1 and e2. Thus, oand is a meta-level function symbol that denotes base-level conjunction.

Base-level clauses are represented as meta-level atoms. Base-level rule "h if b" is represented as the meta-level atom clause(h,b'), where b' is the representation of body b. A base-level atomic clause a is represented as the meta-level atom clause(a,true), where the meta-level constant true represents the base-level empty body.

Example 13.21: The base-level clauses from Example 12.11,
connected_to(w0,w1) ←up(s2).
lit(L) ←light(L)∧ok(L)∧live(L).

can be represented as the meta-level facts

clause(lit(L), oand(light(L),oand( ok(L) , live(L)))).

To make the base level more readable, we use the infix function symbol "&" rather than oand. Instead of writing oand(e1,e2), we write e1 &e2. The conjunction symbol "&" is an infix function symbol of the metalanguage that denotes an operator, between atoms, of the base language. This is just a syntactic variant of the "oand" representation. This use of infix operators makes it easier to read base-level formulas.

Instead of writing clause(h,b), we write h ⇐b, where is an infix meta-level predicate symbol. Thus, the base-level clause "h ←a1 ∧···∧an" is represented as the meta-level atom

h ⇐a1 &···&an.

This meta-level atom is true if the corresponding base-level clause is part of the base-level knowledge base. In the meta-level, this atom can be used like any other atom.

Syntactic construct Meta-level representation
of the syntactic construct
function symbolffunction symbolf
predicate symbol     5mmpfunction symbolp
"and" operator function symbol &
"if" operator predicate symbol     5mm
clause     h ←a1 ∧···∧an. atom     h ⇐a1 &···&an.
clause     h. atom     h ⇐true.
Figure 13.8: The non-ground representation for the base language

Figure 13.8 summarizes how the base language is represented in the meta-level.

Example 13.22: Using the infix notation, the base-level clauses of Example 13.21 are represented as the meta-level facts
lit(L)⇐light(L)&ok(L) &live(L).

This notation is easier for humans to read than the meta-level facts of Example 13.21, but as far as the computer is concerned, it is essentially the same.

The meta-level function symbol "&" and the meta-level predicate symbol "" are not predefined symbols of the meta-level. You could have used any other symbols. They are written in infix notation for readability.