• Introduction to PROLOG Programming -Logic Programs - A Scene Interpretation Program -Illustrating Backtracking byFlow of Satisfaction Diagrams

Introduction to PROLOG Programming

To introduce readers to the syntax and semantics of logic programming, we first take a look at a few examples. Let us, for instance, consider the problem of a 'classroom scene' interpretation We assume that the scene has been passed through various stages of low and medium level image processing and the objects in the scene thus have been recognized and labeled by a computing machine. The data (clauses) received from the scene and the knowledge used to analyze it are presented in both English and Predicate Logic below.
Database:
Object (board)
Writes-on (john, board, classhour)
Sits-on (mita, bench, classhour)
Sits-on (rita, bench, classhour)
Person (john)
Person (rita)
Person (mita)
The above are called clauses in PROLOG.

Logic Programs - A Formal Definition

We are now in a position to formally define Logic Programs. We first define a Horn clause, the constituents of a logic program
Definition: A clause consists of two parts: the head and the body. One side of the clause to which the arrowhead (if-then operator) points to is called the head and the other side of it is called the body. A Horn clause contains at most one literal (proposition / predicate) at the head of the clause.
Example: The following are two examples of Horn clauses.
i) P (X), Q (Y) → W (X,Y)
ii) R (X, Y), Q (Y) → ?
In (i) W (X, Y) is the head and P (X), Q (Y) is the body. In (ii) R(X, Y), Q(Y) is the body and the head comprises of a null clause (sub-clause). In fact (ii) represents a query, asking whether R (X, Y), Q (Y) is true, or what are the set of instantiations for X and Y, which makes R (X, Y) ^ Q (Y) true.
Definition: A Logic Program is a program, comprising of Horn clauses.
The following example illustrates a logic program.
Example: Consider the following two sentences in Predicate Logic with one head clause in each sentence.
Father (X, Y) ← Child (Y, X), Male (X).
Son (Y, X ) ← Child (Y, X), Male (Y).
The above two clauses being horn clauses are constituents of a Logic Program. Let us now assume that along with the above knowledge, we have the following three data clauses:
Child (ram, dasaratha).
Male (ram).
Male (dasaratha).

Suppose that the above set of clauses is properly structured in PROLOG and the program is then compiled and executed. If we now submit the following queries (goals), the system responds correctly as follows.

1. Goal: Father (X, Y)?
   Response: Father (dasaratha, ram).
2. Goal: Son (Y, X)?
   Response: Son (ram, dasaratha).

But how does the system respond to our queries? We shall discuss it shortly. Before that let us learn a little bit of syntax of PROLOG programs. We take up the scene interpretation problem as an example to learn the syntax of PROLOG programming.

A Scene Interpretation Program

/* PROLOG PROGRAM FOR SCENE INTERPRETATION */
Domains
Time, X, Y, Z, W, board, classhour, bench = symbol
Predicates
Teacher (X)
Writes-on (X, board, Time )
Equal (Time, classhour)
Person (X) Person (Y) Person (Z) Person (W)
Sits-on (Y, bench, Time) Sits-on (Z, bench, Time)
Student (Y)
Student (Z)
Object (W)
Clauses
Object (board). 1
Writes-on (john, board, classhour). 2
Male (dasaratha).
Sits-on (mita, bench, classhour). 3
Sits-on (rita, bench, classhour). 4
Person (john). 5
Person (mita). 6
Person (rita). 7
Equal (Time, classhour):- 8
Object (board),
Writes-on (X, board, Time),
Teacher (X).
Equal (Time, classhour):- 9
Person (Y),
Sits-on (Y, bench, classhour),
Person (X),
Writes-on (X, board, Time).
Teacher (X):- 10
Person (X),
Writes-on (X, board, classhour).
Student (Y) :- 11
Person (Y),
Sits-on (Y, bench, Time),
Equal (Time, classhour).
This is all about the program. Readers may note that we mentioned no
procedure to solve the problem of scene interpretation; rather we stated the
facts only in the program. Here lies the significance of a logic program.
Now, suppose, the user makes a query:
Goal: Teacher (X)?
System prompts: Teacher (john).
Further, if the user asks:
Goal: Equal (Time, classhour) ?
System prompts: Yes.

Illustrating Backtracking by Flow of Satisfaction Diagrams

To explain how the system answers these queries, we have to learn a very useful phenomenon, called backtracking. Let us now concentrate on the query: Teacher (X)? Since Teacher (X) ←
Person (X),
Writes-on (X, board, classhour).
to satisfy the Goal: Teacher (X), one has to satisfy the sub-goals: Person (X), Writes-on (X, board, classhour). Now, PROLOG searches a sub-goal Person( ) for the predicate Person (X). At clause 5, it finds a match and X is instantiated to john . PROLOG puts a marker at clause 5. Now, it continues searching Writes-on (john, board, classhour) in the remaining clauses. But it fails to find so, since Writes-on (john, board, classhour) is at 2nd position in the list of clauses . So, it has to trace back above the marker place and then ultimately it finds Writes-on (john, board, classhour) . Since the sub-goals are succeeded, the goal also succeeds, yielding a solution: Teacher (john).
For answering the query Equal (Time, classhour), a number of
backtracking is required. We omit this for space constraints and ask the reader
to study it herself. The next important issue that we will learn is SLD (Select
Linear Definite clauses) resolution.