Inference process

Knowledge itself is not a program. Actually, there is an initial query, or a goal, as it is called in Prolog notation, needed to start the inference process ^6.1.

Summarizing, there are the following parts of a Prolog program:

• facts,
• rules, and
• the goal.

The specification of a goal is provided in the form of a predicate. A goal: ``Who are James' children?'' (considering the program in Figures 6.1 and  6.2) can be stated as:

  parent(Child, james).

A goal has the same syntax as the body of a complex clause. In the above case, the first argument of parent predicate is a variable, the second one is a constant. Prolog will substitute in turn, all possible values for Child variable, according to knowledge it possesses. It is called a non-deterministic goal. The reply is:

  Child = john ;

  Child = mary

Therefore, the variable Child is unified in turn, with values: john and mary. These are two solutions, or answers to the goal then.

In general, the goal may be stated as:

$$p_1(A_{1,1},\ldots,A_{1,m}) \; O_1 \; p_2(A_{2,1},\ldots,A_{2,n}) \; O_2 \; \ldots \; O_{q-1} \; p_q(A_{p,1},\ldots,A_{p,o}).$$ (6.1)

Where $p_r$ are predicates, $O_s$ is a logical operator, usually a comma (logically AND), or in rare cases a semicolon (logically OR). If some arguments $A_{x,y}$ are denoted by a common variable, then the value will be shared among all predicates that use this variable in the goal. For example, finding cousins, such that one of them is Mary's child can be stated as:

  parent(Y,mary), cousin(X,Y).

And the reply is:

  Y = ann 
  X = alice ;

  Y = simon 
  X = alice

Unlike other languages, a Prolog program does not specify how to perform the task, but rather what is to be done. Details of the execution are covered by the Prolog Inference Engine, which interprets the goal. An executable Prolog program is not just what was typed by the programmer, so the knowledge base, but it also incorporates the Inference Engine.

The user specifies a goal, and expects deterministic or non-deterministic results. Issuing the query starts the inference process. Prolog tries to satisfy the current goal by matching it with a fact or the head of a rule. This matching is called unification [4]. If a fact is found, it becomes the solution. If a rule is found which head unifies with the goal, its body becomes the new goal.

The inference engine starts with a goal and works toward facts, that prove the goal. It is called backward-chaining [4]. The unification assigns a value to a variable in order to achieve a match. It is called instantiating [4] the variable. If at some point of this process there is a goal which does not unify with any clause, the process will terminate with failure.

The goal can be unified with several facts or rules. Prolog tries the rules in the order in which they appear in the knowledge base. If the rule, or fact, does not lead to success, the inference engine backs up and tries another one. It is called backtracking [4]. Whenever the inference engine finds that it has gone down a blind alley, it backs up to the most recent query for which there are still untried alternatives and tries another path. When a successful answer is found, the inference process stops, unless the user asks for alternatives, in that case backtracking continues to look for another successful path, and another solution.

The search strategy used by Prolog is the depth-first search. It involves going as far along each path as possible, before backing up and searching for alternative paths. More details on this subject are in [4,17,15,1].