Intelligence 2E

foundations of computational agents

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.

The base-level term ${f}{\mathit{}}{o}{\mathit{}}{o}{\mathit{}}{\mathrm{(}}{X}{\mathrm{,}}{f}{\mathit{}}{\mathrm{(}}{b}{\mathrm{)}}{\mathrm{,}}{X}{\mathrm{)}}$, in a non-ground representation, will be represented as the meta-level term ${f}{\mathit{}}{o}{\mathit{}}{o}{\mathit{}}{\mathrm{(}}{X}{\mathrm{,}}{f}{\mathit{}}{\mathrm{(}}{b}{\mathrm{)}}{\mathrm{,}}{X}{\mathrm{)}}$.

In a ground representation, the base-level term ${f}{\mathit{}}{o}{\mathit{}}{o}{\mathit{}}{\mathrm{(}}{X}{\mathrm{,}}{f}{\mathit{}}{\mathrm{(}}{b}{\mathrm{)}}{\mathrm{,}}{X}{\mathrm{)}}$ may be represented as ${f}{\mathit{}}{o}{\mathit{}}{o}{\mathit{}}{\mathrm{(}}{x}{\mathrm{,}}{f}{\mathit{}}{\mathrm{(}}{b}{\mathrm{)}}{\mathrm{,}}{x}{\mathrm{)}}$, 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({t}_{1},\mathrm{\dots},{t}_{k})$ is represented as the meta-level term $p({t}_{1},\mathrm{\dots},{t}_{k})$.

Base-level bodies are also represented as meta-level terms. If ${e}_{1}$ and ${e}_{2}$ are meta-level terms that denote base-level atoms or bodies, let the meta-level term $oand({e}_{1},{e}_{2})$ denote the base-level conjunction of ${e}_{1}$ and ${e}_{2}$. 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 “$h\leftarrow b$” is represented as the meta-level atom $clause(h,{b}^{\prime})$, where ${b}^{\prime}$ 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.

The base-level clauses from Example 13.12,

${c}{}{o}{}{n}{}{n}{}{e}{}{c}{}{t}{}{e}{}{d}{}{\mathrm{\_}}{}{t}{}{o}{}{(}{{l}}_{{1}}{,}{{w}}_{{0}}{)}{.}$ | ||

${c}{}{o}{}{n}{}{n}{}{e}{}{c}{}{t}{}{e}{}{d}{}{\mathrm{\_}}{}{t}{}{o}{}{(}{{w}}_{{0}}{,}{{w}}_{{1}}{)}{\leftarrow}{}{u}{}{p}{}{(}{{s}}_{{2}}{)}{.}$ | ||

${l}{}{i}{}{t}{}{(}{L}{)}{\leftarrow}{}{l}{}{i}{}{g}{}{h}{}{t}{}{(}{L}{)}{\wedge}{}{o}{}{k}{}{(}{L}{)}{\wedge}{}{l}{}{i}{}{v}{}{e}{}{(}{L}{)}{.}$ |

can be represented as the meta-level facts

${c}{}{l}{}{a}{}{u}{}{s}{}{e}{}{(}{c}{}{o}{}{n}{}{n}{}{e}{}{c}{}{t}{}{e}{}{d}{}{\mathrm{\_}}{}{t}{}{o}{}{(}{{l}}_{{1}}{,}{{w}}_{{0}}{)}{,}{t}{}{r}{}{u}{}{e}{)}{.}$ | ||

${c}{}{l}{}{a}{}{u}{}{s}{}{e}{}{(}{c}{}{o}{}{n}{}{n}{}{e}{}{c}{}{t}{}{e}{}{d}{}{\mathrm{\_}}{}{t}{}{o}{}{(}{{w}}_{{0}}{,}{{w}}_{{1}}{)}{,}{u}{}{p}{}{(}{{s}}_{{2}}{)}{)}{.}$ | ||

${c}{}{l}{}{a}{}{u}{}{s}{}{e}{}{(}{l}{}{i}{}{t}{}{(}{L}{)}{,}{o}{}{a}{}{n}{}{d}{}{(}{l}{}{i}{}{g}{}{h}{}{t}{}{(}{L}{)}{,}{o}{}{a}{}{n}{}{d}{}{(}{o}{}{k}{}{(}{L}{)}{,}{l}{}{i}{}{v}{}{e}{}{(}{L}{)}{)}{)}{)}{.}$ |

To make the base level more readable, we use the infix function symbol “$\&$” rather than $oand$. Instead of writing $oand({e}_{1},{e}_{2})$, we write ${e}_{1}\&{e}_{2}$. 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\Leftarrow b$, where $\Leftarrow $ is an infix meta-level predicate symbol. Thus, the base-level clause “$h\leftarrow {a}_{1}\wedge \mathrm{\cdots}\wedge {a}_{n}$” is represented as the meta-level atom

$$h\Leftarrow {a}_{1}\&\mathrm{\cdots}\&{a}_{n}.$$ |

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 | $\wedge $ | function symbol | $\&$ |

“if” operator | $\leftarrow $ | predicate symbol | $\Leftarrow $ |

clause $h\leftarrow {a}_{1}\wedge \mathrm{\cdots}\wedge {a}_{n}.$ | atom $h\Leftarrow {a}_{1}\&\mathrm{\cdots}\&{a}_{n}$ | ||

clause $h.$ | atom $h\Leftarrow true$ |

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

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

${c}{}{o}{}{n}{}{n}{}{e}{}{c}{}{t}{}{e}{}{d}{}{\mathrm{\_}}{}{t}{}{o}{}{(}{{l}}_{{1}}{,}{{w}}_{{0}}{)}{\Leftarrow}{}{t}{}{r}{}{u}{}{e}{.}$ | ||

${c}{}{o}{}{n}{}{n}{}{e}{}{c}{}{t}{}{e}{}{d}{}{\mathrm{\_}}{}{t}{}{o}{}{(}{{w}}_{{0}}{,}{{w}}_{{1}}{)}{\Leftarrow}{}{u}{}{p}{}{(}{{s}}_{{2}}{)}{.}$ | ||

${l}{}{i}{}{t}{}{(}{L}{)}{\Leftarrow}{}{l}{}{i}{}{g}{}{h}{}{t}{}{(}{L}{)}{\&}{o}{}{k}{}{(}{L}{)}{\&}{l}{}{i}{}{v}{}{e}{}{(}{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 “$\Leftarrow $” are not predefined symbols of the meta-level. You could have used any other symbols. They are written in infix notation for readability.