14.4 Implementing Knowledge-Based Systems

14.4.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. Meta-level symbols will denote base-level terms, atoms, and clauses. Base-level terms will denote objects in the domain being modeled, and base-level predicates will denote relations in the domain.

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 14.16.

The base-level term foo(X,f(b),X), in a non-ground representation, 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(x,f(b),x), along with a declaration that x is a base-level variable.

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 definite clauses are represented as meta-level atoms. Base-level rule “hb” is represented as the meta-level atom clause(h,b), where b is the representation of body b. A base-level fact a is represented as the meta-level atom clause(a,true), where the meta-level constant true represents the base-level empty body.

Example 14.17.

The base-level clauses from Example 13.12,

connected_to(l1,w0).
connected_to(w0,w1)up(s2).
lit(L)light(L)ok(L)live(L).

can be represented as the meta-level facts

clause(connected_to(l1,w0),true).
clause(connected_to(w0,w1),up(s2)).
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 hb, where is an infix meta-level predicate symbol. Thus, the base-level clause “ha1an” is represented as the meta-level atom

ha1&&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
variable X variable X
constant c constant c
function symbol f function symbol f
predicate symbol p function symbol p
“and” operator function symbol &
“if” operator predicate symbol
clause         ha1an. atom         ha1&&an
clause         h. atom         htrue
Figure 14.8: The non-ground representation for the base language

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

Example 14.18.

Using the infix notation, the base-level clauses of Example 14.17 are represented as the meta-level facts

connected_to(l1,w0)true.
connected_to(w0,w1)up(s2).
lit(L)light(L)&ok(L)&live(L).

This notation is easier for humans to read than the meta-level facts of Example 14.17, 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.