Prolog

Prolog Program Control

Prolog does not contain any statements that specifically "administer" the flow of the program. Instead, the interpreter starts with the query and searches for applicable facts and rules that can be substituted for elements of the query until either the query is found to be true or all facts and rules have been tried that indicates there is no resolution. Thus the sequencing of interpretation is determined by locating applicable facts and/or rules.

Conditional control is embedded in the rules of Prolog. A rule is true (or correct) if and only if the elements of its right hand side are also true or correct. There is no formal if-then-else consequential statement; consequences are bound up with the applicability or non-applicability of a fact or rule.

Repetition in Prolog is accomplished by using recursion as an element of a rule. That is, a rule is defined in terms of itself! Moreover, like recursion in other languages the use of recusion in one rule requires that there exists at least one other rule with the same name and parameters that is not recursive.

EXAMPLE:

Let us define addition in the following manner, where we define the increment property through a set of facts (named inc), and a predecessor predicate (named pre):

inc(1,0,1).
inc(1,1,2).
inc(1,2,3).
inc(1,3,4).
inc(1,4,5).
inc(1,5,6).
inc(1,6,7).
inc(1,7,8).
inc(1,8,9).
pre(1,0).
pre(2,1).
pre(3,2).
pre(4,3).
pre(5,4).
pre(6,5).
pre(7,6).
pre(8,7).
and then define the add function in terms of two rules:
add(A,B,C) <= inc(A,B,C).
add(A,B,C) <= pre(A,D) and pre(E,B) and add(D,E,C).
where the first rule tests for an applicable fact in the database, and the second rule (the otherwise case) selects two new integers to add together one of which is the predessor of the first argument (A) and the other is the successor of the second argument (B). Note that the predecessor function is used to produce a successor by giving the second argument to get the first! That is, pre(X,Y) can be used to get the predecessor of X or the successor of Y. (try it!)

Having found the predesssor and successor, then the second rule prescribes that these be used in new add operation (add(D,E,C)). This is the recursive definition - having defined a rule in which the right hand side in terms of the left hand side.

Thus the query ?add(2,4,G) would be resolved as follows:

add(2,4,G) => pre(2,D) and pre(E,4) and add(D,E,C)
           => add(1,5,C)
           => add(1,5,6).

Besides the requirement that every recursive rule have an alternative in the form of a non-recursive rule (or fact), the other important element is to ensure that the right hand side continually progresses towards a known fact. In the above case, the predecessors of first argument (A) are continually discovered, while the successors of the second argument (B) are found, so that the recursive predicate moves towards one of the inc facts.

[TOC][Next]

CS1104 Main Page
Last Updated 2002/03/26
© J.A.N. Lee, 2002.