14.4.3 Expanding the Base Language

The base language can be changed by modifying the meta-interpreter. The set of provable consequences can be enlarged by adding clauses to the meta-interpreter. The set of provable consequences can be reduced by adding conditions to the meta-interpreter clauses.

In all practical systems, not every predicate is defined by clauses. For example, it would be impractical to axiomatize arithmetic on current machines that can do arithmetic quickly. Instead of axiomatizing such predicates, it is better to call the underlying system directly. Assume the predicate $call(G)$ evaluates $G$ directly. Writing $call(p(X))$ is the same as writing $p(X)$ . The predicate $c a l l$ is required because the definite clause language does not allow free variables as atoms.

Built-in procedures can be evaluated at the base level by defining the meta-level relation $built\_in(X)$ that is true if all instances of $X$ are to be evaluated directly; $X$ is a meta-level variable that must denote a base-level atom. Do not assume that “ $built\_in$ ” is provided as a built-in relation. It can be axiomatized like any other relation.

The base language can be expanded to allow for disjunction in the body of a clause, where the disjunction, $A\vee B$ , is true in an interpretation $I$ when either $A$ is true in $I$ or $B$ is true in $I$ (or both are true in $I$ ). Allowing disjunction in the body of base-level clauses does not require disjunction in the metalanguage.

Figure 14.11 shows a meta-interpreter that allows built-in procedures to be evaluated directly and allows disjunction in the bodies of rules. This requires a database of built-in assertions and assumes that $call(G)$ is a way to prove $G$ in the meta-level.

Example 14.20.

An example of the kind of base-level rule the meta-interpreter of Figure 14.11 can now interpret is

\displaystyle{can\_see\Leftarrow\mbox{}eyes\_open\>\&\>(lit(l_{1})\vee lit(l_{% 2})).}

which says that $can\_see$ is true if $eyes\_open$ is true and either $lit(l_{1})$ or $lit(l_{2})$ is true (or both).

% $prove(G)$ is true if base-level body $G$ is a logical consequence of the base-level knowledge base.

	$\displaystyle{prove(true).}$
	$\displaystyle{prove((A\>\&\>B))\leftarrow\mbox{}}$
	$\displaystyle\ \ \ \ {prove(A)\wedge\mbox{}}$
	$\displaystyle\ \ \ \ {prove(B)}.$
	$\displaystyle{prove((A\vee B))\leftarrow\mbox{}}$
	$\displaystyle\ \ \ \ {prove(A)}.$
	$\displaystyle{prove((A\vee B))\leftarrow\mbox{}}$
	$\displaystyle\ \ \ \ {prove(B)}.$
	$\displaystyle{prove(H)\leftarrow\mbox{}}$
	$\displaystyle\ \ \ \ {built\_in(H)\wedge\mbox{}}$
	$\displaystyle\ \ \ \ {call(H).}$
	$\displaystyle{prove(H)\leftarrow\mbox{}}$
	$\displaystyle\ \ \ \ {(H\Leftarrow\mbox{}B)\wedge\mbox{}}$
	$\displaystyle\ \ \ \ {prove(B)}.$

Figure 14.11: A meta-interpreter that uses built-in calls and disjunction

Given such an interpreter, the meta-level and the base level are different languages. The base level allows disjunction in the body. The meta-level does not require disjunction to provide it for the base language. The meta-level requires a way to interpret $call(G)$ , which the base level cannot handle. The base level, however, can be made to interpret the command $call(G)$ by adding the following meta-level clause:

	$\displaystyle{prove(call(G))\leftarrow\mbox{}}$
	$\displaystyle\ \ \ \ {prove(G).}$

Artificial Intelligence 2E

14.4.3 Expanding the Base Language

Example 14.20.

Artificial
Intelligence 2E