Knowledge processing

Prolog also offers more advanced knowledge processing. It can be divided into two categories:

Prolog allows to extend the current knowledge base, by consulting other programs. Such a program is read by the runtime, interpreted, and its knowledge is merged with the current one. It provides very convenient way for extending current knowledge by both new facts and new rules. Such an action extends current knowledge with clauses from the newly added program. It has one performance drawback: the consulted program must be interpreted and knowledge must be merged.

Figure 6.7 gives an example. This is the main program. There is an empty rule with multifile keyword. Such a rule, without the head, is executed by the inference engine when the program is loaded, multifile means that the specified predicates may be defined over more than one file.

**Figure 6.7:** Consulting other programs, the main program.
$\begin{figure}\begin{verbatim}fact(1). rule(X):- fact(Y), X is Y * 2. dis... ...line'). :- multifile(fact/1), multifile(rule/1).\end{verbatim} \end{figure}$

A program which extends current knowledge is given in Figure 6.8. It adds a new fact (fact/1) and a new rule (rule/1). The program is stored in extra.pl file.

**Figure 6.8:** Consulting other programs, the extension.
$\begin{figure}\begin{verbatim}fact(10). rule(X):- fact(X).\end{verbatim} \end{figure}$

**Figure 6.9:** Consulting other programs, the result.
$\begin{figure}\begin{verbatim}fact: 1 rule: 2 --- end of line fact: 1 fac... ...le: 2 rule: 20 rule: 1 rule: 10 --- end of line\end{verbatim} \end{figure}$

There is another way to extend extensional knowledge dynamically. Two predicates assert/1 and retract/1 allow to add or remove facts, respectively. They provide so-called dynamic database functionality. The program in Figure 6.10 provides a search for the maximum value among facts defined as res/1 (compare it with the previous search program in Figure 6.6).

**Figure 6.10:** Prolog Dynamic Database.
$\begin{figure}\begin{verbatim}res(1). res(2). res(3). res(4). res(5). res(4... ...mp(X)), fail. best(X):-temp(X), retract(temp(_)).\end{verbatim} \end{figure}$

The predicate best/1 finds the maximum value in the set of values, defined by res/1 predicate. First best/1 calls set/0 to initialize a temporary predicate temp/1 with the first value in the set. Then, it searches for another value, which is greater then the one stored in the temp/1 clause. If such a value is found, the current greatest value is replaced by the new one, so the old knowledge is retracted (retract/1) and the new one becomes valid (assert/1). The operations are repeated until there is nothing left in the set. The inference engine do not backtrack past the cut, so set/0 is called only once.

When the set is browsed, the second clause of best/1 unifies its argument with the value kept in temp/1, and finally knowledge stored in temp/1 is retracted (retract/1).

The underscore (_) variable is called the anonymous variable. It means that the value which is going to be unified with it, does not matter and it will not be used, thus the unification takes place. In other words the statement retract(temp(_)) says: ``retract the dynamic database data concerning temp/1 clause, whatever is the value which is unified with its argument''.

One of the most important data structures of Prolog is the list. It is an ordered sequence of zero or more terms. The terms are listed between square brackets and separated by comas, for example: [1,2,3]. Any list can be divided into its head, and tail by '|' operator. The head of a list is its first element, and the tail is the rest of the elements, which is also a list. The following expression:

The following example shows one of the applications. A list is used to keep track of the acceptable solution of the problem. And the problem is stated as follows: ``How a certain amount of money can be changed into the following coins: one dollar, quarter dollar, and a dime''.

An example program is given in Figure 6.11. Available coins are denoted as extensional knowledge by clauses of coin/1 predicate. The argument denotes number of cents the particular coin covers.

**Figure 6.11:** Prolog Lists.
$\begin{figure}\begin{verbatim}coin(100). coin(25). coin(10). change(S,[S])... ...S1,L1), L1=[H\vert _], H >= M, L = [M\vert L1].\end{verbatim} \end{figure}$

**Figure 6.12:** Prolog Lists, the reply to the following query: `change(100,X)`.
$\begin{figure}\begin{verbatim}X = [100] ; X = [25, 25, 25, 25] ; X = [1... ...] ; X = [10, 10, 10, 10, 10, 10, 10, 10, 10, 10]\end{verbatim} \end{figure}$

A solution is a list of coins. If the requested amount is equal to the amount denoted by one of the coins, then it is a proper solution. The above statement is implemented as the first clause of change/2 predicate. In this case it will be a one-element list which contains a single, valid coin value. The second clause covers recursively the other cases. If the amount to change is greater then 0, find a coin M, and run the search recursively with the amount to change decreased by M. Then, check if the first element, on the returned from the recursion list, is greater or equal to M. It provides an ascending order into the list. If it is true, then append M at the front of the list, and unify the list with the second argument of the clause.

A goal of changing one dollar bill can be denoted as: change(100,X) (the amount is given in cents, in order to avoid floating point computations). The result is given in Figure 6.12. These are four, different, acceptable solutions to the problem. They are subsets of the set of coins.

The above example is a case of Subset Selection Problem, so it belongs to C1 class. In general problems of class C1 and C2 (the classes are defined in Chapter 2, Section 2.2) can be tackled with Prolog. Some examples are given in [4,1].