Prolog Programming

Lecture Module 11
Objective
● What is Prolog?
● Prolog program
● Syntax of Prolog
● Prolog Control Strategy
● Execution of Prolog Query
● Programming Techniques
● Termination
● Rule Order
● Goal Order
● Rule Redundancy
● Iterative Programming
What is Prolog?
● Prolog is acronym of PROgramming in LOGic.
● Prolog program is sequence of rules and facts.
● Prolog Rule for grandfather is defined as:

gfather(X, Y) :- father(X, Z), parent(Z, Y).

father(james, robert).
Glimpse of Prolog Program
/* Rules: “X is grand father of Y if X is father of Z who is parent of Y */
gfather(X, Y) :- father(X, Z), parent(Z, Y). (1)
parent(X, Y) :- father(X, Y). (2)
parent(X, Y) :- mother(X, Y). (3)
/*Facts “James is father of robert” */
father(james, robert). (4)
father(mike, william). (5)
father(william, james). (6)
father(robert, hency). (7)
father(robert, cris). (8)
/* Goals ‘ Is abraham a grand father of mike?’*/
?- gfather(abraham, mike).
?- gfather(X, Y).
?- father(X, Y), father(Y, mike).
Back
 General Syntax of Prolog
● The rules and facts in Prolog are terminated by full stop (.).
● Goal can be included in the program or given at the prompt.
● Goal can be single or conjunction of sub-goal(s) terminated by full
stop.
● Constants are numerals and symbols such as, 4, mary, etc.
● String is a sequence of characters and is enclosed within single
quotes e.g., 'This is a string'.
● Predicate names must start with alphabet and are formed by
using lower case letters, numerals and underscore ( _ ).
● Variable names are formed similar to predicate names but it must
start with upper case letter. Normally, we use X, Y, Z, ... for
variables.
Prolog Control Strategy

● Prolog contains three basic control strategies.

− Forward movement
− Matching (Unification)
− Backward movement (Backtracking)
● Prolog uses depth first search strategy.
Forward Movement
● Choose a rule by
− searching sequentially in the program from top to
bottom whose head matches with the goal with
possible unifier.
− Remember the position of the matched rule.
− Join the rule body in front of the sequence of sub
goals to be solved.
● Repeat until either goal is satisfied or is
failed.
 Forward Movement – Cont…
● Consider the following query consisting of n sub-goals.
?- G1, ... , Gi-1, Gi, ... , Gn
● Starts executing or satisfying G1
− If G1 is satisfied using some rule, put a place marker so
that next rule for G1 will be searched after the marker.
− Continue in forward direction to satisfy G2 and if it is
satisfied then continue with common bindings of the
variables in sub-goals so far satisfied.
− Such a movement is called forward
Unification
● Unification is a process of matching or finding the
most general unifier.
− Constant matches with the same constant.
− A variable can match with any constant or any another
variable.
● Examples
− love(X, sita) unifies with love(ram, sita) with mgu as
{X / ram}.
− love(X, Y) unify with love(ram, sita) with mgu as
{X / ram, Y / sita} respectively.
Backtracking
● Backtracking refers to backtrack in search
process for a solution.
● In Prolog, backtracking takes place in two
situations.
− First when a sub goal fails and
− Other when the last sub goal succeeds, it
backtracks to find alternative solutions.
Types of backtracking
● Prolog has two kinds of backtracking.
− Shallow and
− Deep backtracking
● Both backtrackings take place in conjunction with
each other.
● Shallow backtracking occurs
− when alternative definition of the goal is tried.
− Suppose G1,.., Gi-1 have been satisfied with
some common bindings of the variables in sub-
goals.
− While satisfying Gi., if it fails for some rule then try
another rule of Gi
− This is called shallow backtracking to rules of the
same sub-goal
Backtracking Cont…
● Deep backtracking occurs
− When sub-goal Gi fails for all rules of Gi then backtrack
to Gi-1.
− This backtracking is called deep backtracking.
− Remove the bindings created earlier to satisfy Gi-1.
− Try to satisfy Gi-1 again by using an alternative rule, if it
exists, from last place marker of Gi-1. and continue the
process.
− If sub goal Gi-1 is satisfied then move forward to Gi,
else backtrack to Gi-2.
− The process of backtracking continues till we reach
G1.
− If G1 fails for all possible definitions, then entire query
fails.
Backtracking Cont…

● If entire conjunction of sub-goals succeed, then the

solution is displayed.
● For alternative solution, the sub goal Gn is tried to be
satisfied with alternative rule, if it exist, after last
place marker (Shallow backtracking) of Gn .
● Otherwise it backtracks to previous sub goal Gn-1
(Deep backtracking).
● Process is repeated till all possible solutions are
generated.
 Prolog Query
● Two types of query
− Ground query
ƒ No variable in the argument
ƒ Example:
? gfather(ram, shyam) – Is ram a grand father of shyam?
ƒ Answer to ground queries are Yes or No
ƒ Proof tree is generated while solving the query.
− Non ground query
ƒ Atleast one argument is a variable
ƒ Example:
? gfather(X, shyam) – Who is a grand father of shyam?
ƒ Answer to such queries are the values bound to the variables
in the query.
ƒ Search tree is generated using DFS to find all possible
solutions.
Execution of ground query
Ground query: Prolog Program

?- gfather(james, hency).
Proof tree: ?- gfather(james, hency).
(1)
?- father(james, Z), parent(Z, hency).
(4) { Z = robert }
?- parent(robert, hency).
(2)
?- father(robert, hency).
(7)

succeeds Answer: Yes

Execution of Non ground query
Non-Ground query:

?- gfather(william, X). Prolog Program

Search tree: ?- gfather(william, X).

(1)
?- father(william, Z), parent(Z, X).
(6) {Z = james}
?- parent(james, X).
(2) (3)
?- father(james, X). ?- mother(james, X).
(4) {X = robert}
succeeds fails

Answer: X = robert
Programming Techniques
● Recursion is one of the most important execution
control techniques in Prolog.
● Iteration is another important programming
technique.
● Prolog does not support iteration.
● It can be achieved by
− making recursive call to be the last sub goal in the rule
− using the concept of accumulators which are special types
of arguments used for holding intermediate results.
● The issues of termination, rule order, goal order and
redundancy are also important.
Recursion in Prolog
● Consider a classical example of computing factorial
using recursion.
● Recurrence relation or mathematical definition for
computing factorial of positive integer is:
1, if n = 0
FACTORIAL (n) =
n * FACTORIAL (n-1),
otherwise
● In Prolog, program for computing factorial of a
positive number is written using above definition.
● Factorial predicate contains two arguments; one as
input and another as output.
 Recursion - Cont..
/*fact(N, R) – succeeds if R is unified with the factorial of
N */
factorial(0, 1). (1)
factorial(N, R) :- N1 is N–1, factorial(N1, R1), R is N * R1. (2)

● Rule (1) states that factorial of 0 is 1 which is a

terminating clause.
● Rule (2) is a recursive rule which states that factorial of
N is calculated by multiplying N with factorial of (N-1).

Goal: ?- factorial(3, R).

Execution of factorial query
Search tree:
?- factorial(3, R).
(2) {N = 3}
?- N1 is N-1, factorial(N1, R1), R is N * R1
(2) {N1 = 2}
?-N2 is N1-1,factorial(N2,R2),R1 is N1*R2,R is N*R1.
(2) {N2 = 1}
?-N3 is N2-1, factorial(N3, R3), R2 is N2 * R3….
(1) {N3 = 0, R3 = 1}
?- R2 is 1 * R3 , R1 is N1 * R2, R is N * R1.
Succeeds {R2 = 1, R1 = 2, R = 6}
List Manipulation in Prolog
• List is a common and very useful recursive data
structure in non numeric programming.
• In Prolog, a list is represented by
− elements separated by comma and enclosed in
square brackets.
− Examples: A = [2, 4, 6, 8], B = [[a, b], [c], [p]].
− Empty list with no elements is represented by [ ]
and is useful for terminating recursive programs for
list.
Membership function
● An element is a member of a list if it matches with the
head or if it is contained in the tail of the list.
− The fact that it matches with the head of a list is written as:
mem_list(X, [X | _ ]).
− The rule that if an element does not match with the head,
then it may be in the tail is written as: mem_list(X, [ _ | Y]) :-
mem_list(X, Y).

mem_list(X, [X | _ ]). (1)

mem_list(X, [_ | Y]) :- mem_list(X, Y). (2)

− Underscore is used for non care entry.

 Ground Query
Goal: ?- mem_list(d, [a, b, c, d, e, f]).
Proof tree: ?- mem_list(d, [a, b, c, d, e, f]).
(2) {X = d, Y = [b, c, d, e, f]}
?- mem_list(d, [b, c, d, e, f]).
(2) {X = d, Y1 = [c, d, e, f]}
?- mem_list(d, [c, d, e, f]).
(2) {X = d, Y2 = [d, e, f]}
?- mem_list(d, [d, e, f]).
(1)
succeeds Ans: Yes
 Non ground Query
Goal: ?- mem_list(X, [a, b, c]).
Search tree:
?- mem_list(X, [a, b, c]).
(1) (2)
{X = a} {Y = [b, c]}
succeeds ?- mem_list(X, [b, c]).
(1) (2)
{X = b} {Y = [c]}
succeeds ?- mem_list(X, [c]).
(1) (2)
{X = c} {Y = []}
succeeds ?- mem_list(X, []).
Answer:X = a; X = b; X = c fails
 Termination
• Depth first traversal of Prolog has a serious problem. If
the search tree of a goal with respect to a program
contains an infinite branch, the computation will not
terminate.
• Prolog may fail to find a solution of a goal, even if the
goal has a finite computation.
• Non termination arises because of the following
reasons:
− Left recursive rules: The rule having a recursive goal
as the first sub goal in the body.
 Example
● Consider acyclic directed graph

r s
t
● Graph G is represented by set of connected edges.
G = { edge(p, q), edge(q, r), edge(q, s), edge(s, t)}
● Write Prolog Program to check whether there is a
route from one node to another node.
 Program
● Route from node A to B is defined as follows:
− route from A to B if there is a root from A some node C and an
edge from C to B.
− route from A to B if there is a direct edge from A to B.
● Prolog Program

route(A, B) :- route(A, C), edge(C, B). (1)

route(A, B) :- edge(A, B). (2)
edge(p, q).
edge(q, r).
edge(q, s).
edge(s, t).
back

Query: Check whether there exist a route between nodes p and t .

Proof tree
Goal: ?- route(p, t).
Proof tree: ?- route(p, t).
(1)
?- route(p, X), edge(X, t)
(1)
?- route(p, Y), edge(Y, X), edge(X, t).

Non terminating
● Non terminating program because of left recursion.
● Better way of writing a rule is to write recursive call as the last
call.
route(A, B) :- edge(A, C), route(C, B).
Circular Definition
● Non termination occurs because of Circular definition
of the rules.
● For example, ground and nonground queries will not
terminate with respect to the following program.
teacher(X, Y) :- student(Y, X). (1)
student(X, Y) :- teacher(Y, X). (2)
student(robert, mike).
student(john, robert).

Example: ?- teacher(mike, robert)

(1)
?- student(robert, mike)
(2)
?- teacher(mike, robert)
Non termination
 Rule Order
● A rule order is very important issue in Prolog.
● Change of the order of rules in a program, the
branches in any search tree for a goal to be solved
with that program get permuted.
● It may affect the efficiency of executing goal.
● Since the search tree is traversed using depth first
approach, the order of solutions will be different.
− Check the order of solutions obtained if rules are
interchanged in a Prolog program (go).
 Goal Order
● Goal order in Prolog is more significant than rule
order.
● It may affect the termination because
− subsequent sub goals have different bindings and hence
different search trees.
● Consider the following recursive rules.
ancester(X, Y) :- parent(X, Z), ancester(Z, Y).
route(X, Y) :- edge(X, Z), route(Z, Y).
● If the sub goals in the body of above rules are
swapped, then the rules becomes left recursive and all
the computations will become non terminating.
● It also affects the amount of search the program does
in solving a query .
 Redundancy
● Redundancy of the solution to the queries is another
important issue in Prolog programs.
● In Prolog, each possible deduction means an extra
branch in the search tree.
● The bigger the search tree, higher the computation
time.
● It is desirable in general to keep the size of the search
tree as small as possible.
● Redundant program at times may cause exponential
increase in runtime in the event of backtracking.
Redundancy – Cont..

● There are various reasons by which

redundancy gets introduced.
− The same case is covered by several rules
− Redundancy in computation appears in the
program by not handling special cases
separately.
− See examples given in the book.
 Iteration in Prolog
• Prolog does not have storage variables that can
− hold intermediate results of the computation
− be modified as the computation progress.
• To implement iterative algorithm one requires the
storage of intermediate results, Prolog predicates are
augmented with additional arguments called
accumulators.
• These are similar to local variables in procedural
languages.
• The programs written using accumulators are iterative
in nature.
• In iterative form of a program, make the recursive call
as the last call if possible.
Iteration – cont…
● Prolog program for factorial using accumulators.
● Accumulators I and T are used for storing the counter
value and intermediate computations
fact (N, R) :- fact1(N, R, 0, 1). (1)
fact1(N, R, I, T) :- I < N, J is I + 1, T1 is J * T,
fact1(N, R, J, T1). (2)
fact1(N, R, N, R). (3)

● In prolog, predicates can be overloaded. So we can

also use ‘fact’ instead of fact1.
Search tree
Goal: ?- fact (3, R).
Search tree: ?- fact(3, R).
(1)
?- fact1(3, R, 0, 1).
(2)
?- 0 < 3, J is 1, T1 is 1 * 1, fact1(3, R, 1, 1).
(2)
?- 1 < 3, J is 2, T1 is 2 * 1, fact1(3, R, 2, 2).
(2)
?- 2 < 3, J is 3, T1 is 3 * 2, fact1(3, R, 3, 6).

(2) (3) {R = 6}
fails succeeds
Answer: R = 6