By Prof. Chris Nikolopoulos

This material is copyrighted and all rights are reserved by the author. No part of this material may be reproduced or transmitted via any means without permission from the author.


Kowalski, (in "Algorithms=Logic+Control",[9]), proposed that the problem specification can be separated from control and declarative logic statements can be interpreted as procedural computer instructions. Prolog, (Programming in Logic), a declarative logic programming language which implements these ideas, was developed by Colmerauer and his colleagues of the Artificial Intelligence Group at Marseilles, [5,6].

Unlike the traditional procedural languages, Prolog is a declarative programming language. The Prolog programmer expresses in logic syntax the logical specifications about the problem to be solved, ("declares" the available knowledge about the problem domain) and does not need to specify "how" a solution is to be derived. The built in inference mechanism is based on Robinson's resolution principle and contains the necessary control and algorithmic knowledge on how to execute the specifications and retrieve the answers to queries automatically. The search strategy employed is based on Kowalski's linear resolution strategy and set of support. Negation is handled by employing the closed world assumption.

Although Prolog may not be the best choice for certain application domains, for example systems programming, it is ideal for knowledge representation and reasoning tasks. Its knowledge representational ability and automated deductive power render Prolog suitable for solving problems in such varied domains as expert systems, database systems, natural language processing and computer aided design, (Subrahmanyan, [14]). It will be used in subsequent chapters to demonstrate various expert system concepts.

The basic unit of Prolog programming is a Horn clause, i.e., a clause with at most one positive literal. This translates to inference rules with only one literal at the rule head. The Prolog rule syntax is of the form: p:-q1, q2, ..., qn . where p, qi , i=1, . . . ,n are literals. The above formula is interpreted as: If (q1 and q2 and ... and qn) then p. In Prolog, a comma is used to indicate the logical AND. Implication is written from right to left and denoted by ":-". A period indicates the end of a prolog statement or query. The left side of the rule is called the head of the rule and can only consist of one literal. The right side of the rule is called its body. Literals contained in the body of a rule can also be joined by the logical OR operator which in prolog is indicated by a semicolon ";". A rule with a disjunctive body can be rewritten without disjunctions. For example the rule


is equivalent to the set of two rules:



A set of rules, which have the same head predicate with the same arity, is called a procedure. A Prolog predicate and its arguments are represented by strings of characters. The arguments may be variables, constants or functions. A variable starts with an uppercase character while predicates, constants or functions with lowercase. Here is an example of a rule:


This rule could be used to indicate that:

IF(object X is part of an object Y and the color of Y is C) THEN the color of X is C.

The variables in the head of the rule are universally quantified, while the ones that only appear in the body are existentially quantified. For example, the rule given above corresponds to the logic formula:

X C[( Y(part_of(X,Y) color(Y,C))) color(X,C)]

A fact is a rule whose body is always true. For example, the following fact indicates that Smith is a faculty member in the College of Engineering:


The user interacts with a Prolog program by typing in expressions to be evaluated (queries or goals). Evaluation entails proof of the goals by the automated inference engine. After a successful proof, the bindings made to query variables are given as the answer to the user query, or in the absence of variables in the query the answer yes is provided. In case the proof fails, the answer no is given to indicate that the query is unsatisfiable and therefore false according to the CWA.

A Prolog knowledge base is given below, which will be used in the sequel for explaining basic Prolog programming concepts. Figure 3.1 displays the knowledge base in the form of a semantic network. A semantic network is a knowledge representation technique where knowledge is displayed as a directed labeled graph. The nodes correspond to concepts or objects and the arcs correspond to relations between the concept nodes. The arc labels indicate the relation names. An arc (relation) can be bidirectional, like "is the brother of", or unidirectional like "is a faculty in". Knowledge representation techniques will be examined in more detail in Chapter 5.

Figure 3.1 A semantic network representation of the college knowledge base.

The knowledge expressed in the semantic network of figure 3.1 can be expressed in Prolog syntax as follows.

location(engineering,bradleyhall). (F1)

location(business,bradleyhall). (F2)

dept_in(electricalengineering, engineering). (F3)

dept_in(civilengineering, engineering). (F4)

dept_in(finance, business). (F5)

status(engineering, accredited). (F6)

is_faculty_in(smith, electricalengineering). (F7)

is_faculty_in(jones, civilengineering). (F8)

is_faculty_in(X,Y) :- dept_in(Z,Y), is_faculty_in(X,Z). (R1)

location(X,Y) :- dept_in(X,Z), location(Z,Y). (R2)

status(X,Z) :- dept_in(X,Y), status(Y,Z). (R3)

Observe that in the college knowledge base, the facts precede the rules. In general, the prolog programmer has to exercise care to always insert facts before rules in the knowledge base. As it will be explained later, a search for a proof is done in a sequential depth first manner with backtracking. Facts can be the stopping criteria for recursion, so facts out of place can cause infinite loops during execution of recursive prolog rules. Rules (R1), (R2) and (R3) are tail recursive rules. They are preferable to head recursive rules which can lead to infinite loops. For example, if rule (R2) is written as


a query such as


will cause an infinite loop.

A reader with background in database management systems may recognize the similarities of a prolog knowledge base and a relational database. A collection of facts under the same predicate corresponds to a relational table and rules correspond to relational views. In contrast to relational databases, which lack recursive abilities, a Prolog knowledge base allows recursion. Prolog can form the basis for implementing a deductive, object oriented database system, (Nikolopoulos, [11]).


A Prolog program is a collection of rules and facts, which form the knowledge base. It expresses the programmer's knowledge for the particular problem domain in a declarative manner and is not merely a set of procedural instructions to the computer. Prolog inference is based on backward chaining, so the knowledge base is utilized by "querying" it. Using a text editor the knowledge base can be created and then loaded into the prolog working memory, usually by a command such as


At the prolog prompt queries on the consulted knowledge base can be issued. The built in inference engine of Prolog uses a depth first search strategy with backtracking based on the set of support resolution of Horn clauses, (see Chapter 2). An example is given below, of how the inference engine processes a prolog query.

Consider the college knowledge base of (F1) to (R3). The query "Is civil engineering one of the departments in engineering?" can be formulated in Prolog as:

?dept_in(civil_engineering, engineering).


The Prolog inference engine works in top down fashion. It unifies the query with fact (F4), so the answer to the query is yes.

Next consider the query "Which college does the department of electrical engineering belong to?", which can be formulated in prolog format as:

?dept_in(electrical_engineering, L).

During unification the query is unified with fact (F1) by binding the variable L to the constant bradleyhall. The values bound to query variables are displayed in response to the query after a proof is complete, as follows:

?dept_in(electrical_engineering, L).


Both of the queries given above were deterministic, in the sense that there is exactly one proof path and one answer to them. We give below an example of a nondeterministic query for which there is more than one answer. Some Prolog implementations (for example sb-prolog) print the first answer to the query and then wait for the user to ask for alternate answers, while others (for example Prolog-86) find and print all the alternate answers.

Consider the more complicated query "find all the departments which belong to engineering". In Prolog format the query is expressed as follows:

?dept_in(D, engineering).

After the first match and unification with fact (F3) the variable D is bound to the constant electrical_engineering. This is the first answer to the query. To continue the search for possible alternate bindings, which also provide an answer to a query, type the semicolon ";" followed by the key, after each binding is exhibited. For example, in the query above typing ";" after the query answer D=electrical_engineering, causes the last binding for D to be undone and the search is continued forward from the position of the last binding. The query dept_in(D,engineering) is then successfully unified with fact (F4) under the binding D=civil_engineering. Another semicolon will not produce further answers, as the continued search will produce no more matches. So, all the departments, which belong to engineering, are produced by repeated use the or operator(semicolon) after each alternate answer, until the interpreter returns a "no" (meaning no more matches).





As a third example, consider the query "which department or college is Smith a faculty in?", written in Prolog as:


The query answering process can be depicted by the AND/OR search tree shown in Figure 3.2. The root of the tree is the original query. The nodes of the tree are conjunctions of subgoals that are to be proven during backward chaining. A subgoal that matches the head of more than one rule, becomes an OR node with one outgoing branch for each alternate way of pursuing the proof. When a path down the proof tree leads to an unsatisfiable node, the search engine backtracks to its first ancestor OR node, which has unexplored search branches, undoes the bindings that led to the unsatisfiable node, and pursues an alternate branch.

The given query unifies with fact (F7) under the binding


Typing a semicolon after the binding is exhibited by the system, continues the search of the AND/OR tree for possible alternate bindings that validate the query. The last binding for D is undone and search continues on from the point where the last binding occurred, i.e., Fact (F7). The query fails to unify with any more facts, so the rule (R1) is used. The query can be unified with the rule head by binding X to smith and Y to D. Under this binding the rule head will be true if both of the literals in the conjunction at the rule tail are true. So, search proceeds backwards trying to verify the subgoals :

dept_in(Z,D) and is_faculty_in(smith,Z).

The first conjunct matches fact (F3) by binding Z to electrical engineering and D to engineering. The second subgoal thus becomes


and the search for proof of this subgoal starts again from the top of the knowledge base, matching with fact (F7). Since both of the conjunct subgoals were verified as true the original goal is true and the value bound to D is returned as an answer to the query.





Typing a ";" undoes the binding unifying (F5) with the subgoal dept_in(Z,D). The search continues from (F3). Using (F4), Z is bound to civil_engineering and D to engineering. The second subgoal in the conjunctive proof tree node becomes is_faculty_in(smith,civil_engineering). In order to verify this subgoal, the search for a proof starts at the top of the knowledge base. The subgoal can be unified with the head of rule (R1) to yield the conjunctive subgoal dept_in(Z,civil_engineering), is_faculty_in(smith,Z). The subgoal dept_in(Z,civil_engineering) fails, so is_faculty_in(smith,civil_engineering) fails. Backtracking to dept_in(Z,D) takes place. The next branch of the OR node is followed and fact (F5) is used to bind Z to finance and D to business. The subgoal is_faculty_in(smith,finance) is pursued by applying rule (R1) and fails. Since all disjunctive branches of is_faculty_in(smith,D) have been tried, the search for alternate proofs terminates.

Figure 3.2 AND/OR proof tree for the query: ?is_faculty_in(smith,D).


Prolog employs the closed world assumption (CWA) hypothesis in order to deal with negation, (see Chapter 2, section 2.10). Everything not deduced from the knowledge base through its proof search procedure is assumed to be false (negation by failure). The built in predicate not takes one argument, which is a conjunction of literals and returns true if the search for a proof for the argument fails, false otherwise. Consider for example the query:

?not(dept_in(electrical_engineering, engineering)).


The answer to the query is false, because dept_in(electricalengineering,engineering) is proven true. On the other hand the query:



was found to be true, since no proof can be reached for the query


The query



expresses the query "Is it true that electrical engineering is not a department in any division?" and not the query "which of the colleges does the dept. of electrical engineering not belong to?". A variable cannot be assigned a binding inside the not predicate. The answer to the query is false, since there is a binding to satisfy the query:


The query

?dept_in(finance,X), not(dept_in(civil_engineering,X)).


returns true since X is bound to business when the not subgoal is reached.

If the negation of a predicate is part of a conjunction, care has to be taken, as a variable cannot be bound inside the not. For example, in order to find all colleges to which electrical engineering does not belong and which are located in bradleyhall, the following query will not work.



The answer to the query is no, since dept_in(electrical_engineering,D) succeeds for D=engineering and therefore not(dept_in(electrical_engineering,D)) is false.

Instead the query



should be used.


Although Prolog is not designed for number crunching applications and should not be used for such, it does have the ability to perform numeric calculations. The notation used is the infix notation.

There are a number of built in relational operators:

< (less than), > (greater than), <=, >=, = (equal), <> (not equal).


(the prefix of "%" indicates that the rest of that line is a comment)

% a rule to classify an individual as middle class, if his/her income is between 30000

% 60000.


middle_class(X):- income(X,Y), Y>=30000, Y=<60000.



3.4.1 The assignment operator

The assignment operator is denoted by "is", while "=" is the test for equality.


% Find the sum of X and Y and store it in Z.

sum(X,Y,Z):- Z is X+Y.







% arithmetic procedures are usually not reversible



If the right side of the assignment operator contains an unbounded variable, this will result in failure. If the left and right side are both bound, then if they are equal the predicate succeeds, else it fails. A useful extralogical predicate is the built in var(X) predicate. It has one argument and returns true if the argument is a free variable, and false if the argument is bound.

For example, we could expand the usefulness of the sum procedure by adding the rule:

sum(X,Y,Z):-not(var(X)),var(Y),not(var(Z)), Y is Z-X.



This rule enables the success of the predicate "sum" in the case where Y is a variable and X, X are bound. It evaluates Y to the difference of Z and X.

3.4.2 The comparison operator.

The comparison operator returns the value true if the expressions on its left and right side are unifiable. Any unbound variables on either side become bound to their corresponding constant on the other side.















X=joe, Y=mike

3.4.3 Recursion

Consider a prolog predicate fact of two arguments N and K which evaluates K as the factorial of N, N!=1*2*...*N. For example:



The product 1*2*...*N is equal to (1*2*...*(N-1))*N, so the factorial of N is equal to N times the factorial of N-1. To avoid an infinite loop in evaluating the recursion we need a stopping criterion: the factorial of 0 is 1. In Prolog syntax the procedure "fact" is expressed as follows:


fact(N,M):-K is N-1, fact(K,X), M is N*X.

Observe that fact is not a reversible predicate. The query ?fact(N,24) will not return N=4 but it will lead to an error. This is usually the case with arithmetic predicates, since the assignment operator "is" doesn't allow unbound variables in its assignment side.

As a final example, consider the following program which evaluates XN. The predicate exp accepts three arguments X,N and Z and evaluates Z as X to the power N. The recursive rule states that XN=(XN-1)*X. The stopping criteria state that 1 to any exponent is equal to 1 and that anything raised to the exponent 0 is equal to 1. The underscore "_" is used in Prolog to indicate an unnamed variable (a variable that does not need to pass its binding to other subgoals can be indicated by underscore instead of a variable name).



exp(X,N,Z):-M is N-1, exp(X,M,R), Z is R*X.


Lists are a basic tool for implementing more complex data structures in Prolog and are extensively used in many applications including text processing. A list is an atomic element in the sense that variables can be bound to lists. A list is represented in Prolog by a sequence of elements enclosed in brackets and separated by commas. For example, [saturday,swimming,sunday,church] is a list of four elements. Lists can be embedded in other lists. For example, [[saturday,swimming],[sunday,church]] is a list of two elements, each of which happens to be a sublist. The empty list is represented by [ ].

Given the fact:


the answer to the query


is X=[saturday,swimming,sunday,church]

while the answer to the query



is no (failure), since the predicate schedule is a predicate of one argument (which happens to be a list), while in the query the predicate schedule has four arguments making unification impossible.

In contrast to the query given above, the query


can be matched with the fact involving the predicate schedule and gives after unification:

X=saturday, Y=swimming, Z=sunday, W=church

The first element of a nonempty list is called the head of the list, and the remaining part of the list is called the tail of the list. The head is an atom or a list, while the tail of a list is always a list itself.

For example, saturday is the head of the list [saturday,swimming,sunday,church] and [swimming,sunday,church] is the tail. As another example, consider the list: [[a,b],c]. Its head is the list [a,b] and its tail the list [c].

The built in functor "|" is used to extract elements from a list, using the syntax [A1,A2,...,An|L]. The left side of the functor can include one or more arguments (constants or variables) which are atoms and the right side one argument which is a list. During unification with a list M, A1,A2,...,An are matched to the first n elements of the list M and L is bound to the remainder of the list M. For example, given the fact


the query


will produce

X=saturday, L=[swimming,sunday,church]

The reader who is familiar with the list processing language LISP will recognize that [A|L] is the equivalent of the LISP car function. During unification the variable at the left of the | operator is bound to a corresponding element of the list, while the variable to the right of the | operator is bound to the rest of the list (excluding the first element).

For example,


X=saturday, Y=swimming, L=[sunday,church]

Note that the query ?schedule([X,Y,Z,W,G|L]) fails, since the schedule list has only four arguments and unification to the five atoms of the query cannot succeed.

3.5.1 Some basic list processing functions

More examples of list processing functions written in Prolog are given below. 1. The equivalent of the LISP function car which extracts the head of a list can be written in Prolog as:


or as:


Given the query


the answer is X=3, since during pattern matching X is bound to 3 and L to the list [4].

Similarly the LISP "cdr" function which gives the remainder of a list after its head is deleted can be written in Prolog as:

cdr([X|L], L).

which when queried by


gives L=[4,5]

2. A function to determine if an atom belongs to a list.


member(X,[Y|L]) :- member(X,L).

This is a recursive predicate. The first rule is the stopping criterion of the recursion. If X is bound to a value equal to the head of the list then X is a member of the list. If X is bound to a value not equal to the head of the list then X is a member of the list if and only if X is a member of the tail of the list.

When queried the member predicate gives:










3. Function to find the length of a list (number of atoms in the list).

The length of the empty list is 0. The length of a list is equal to the length of its tail plus 1.


length([X|L],N):-length(L,M), N is M+1.

When queried it gives:

?length([1,2,3], N).


4. Concatenate two lists.

The predicate append(L,M,N) has three arguments which are lists and concatenates L and M to produce N. The result of appending the empty list [ ] to a list L is L. The result of appending a list [X|L], whose first element is X, to a list M, is a list whose first element is X and whose tail is the appendum of L to M. This is expressed in Prolog as follows:

append([], L, L).


5. Delete an element from a list.

The predicate delete(X,L,M) given below has three arguments: an atom X, and two lists L and M, and deletes all occurrences of atom X from the list L to produce the list M. If an element is deleted from an empty list the result is the empty list. To delete all occurrences of an element X from a list whose head is equal to X, delete the head of the list and delete X from the tail of the list.




When queried gives:






6. To reverse a list:

The predicate reverse of two arguments returns in the second argument the reverse list of the list bound to the first argument. The reverse of the empty list is the empty list. To reverse a list L of length n, whose first element is H and the tail T, reverse the tail T of the list L and append the result to the first element of L.



When queried gives:



7. Union of two lists:

Union is a predicate of arity 3, union(M,N,L), which accepts two lists M and N and calculates their union L.

For example,



If the first element of list M is a member of the list N, then the union of lists M and N is equal to the union of the tail of M and N else the union of M and N is equal to the first element of M followed by the union of the tail of M and N.





8. Eliminate duplicate elements from a list:

The eliminate predicate accepts two lists M and L as arguments, and bounds the second list to the first after eliminating the duplicate elements of the first list. For example:



In order to eliminate duplicates in list M to get list L:

IF the head element of list M is a member of the tail of the list M, THEN the list L without duplicates is equal to the list we get by eliminating duplicates from the tail of M ELSE the list L without duplicates is equal to the list whose head is the head of M and whose tail is the list we get by eliminating duplicates from tail of M.

eliminate([ ],[ ]).

eliminate([X|L],M):-member(X,L),eliminate(L,M). eliminate([X|L],[X|M]):-eliminate(L,M).

9. Check if a list is a prefix of another list:

The prefix predicate accepts as input two lists and returns true if the first list is a prefix of the second. For example

?prefix([2,4],[2,4,5,6]). returns true,

while ?prefix([2,5],[2,4,5,6]). returns false.

The empty list is a prefix to any other list. If the list is not empty, then List1 is a prefix to List2 iff they have the same head and the tail of List1 is a prefix of the tail of List2.



10. Determine if a list M is a sublist of a list N.

A list M is a sublist of N iff the sequence of elements in M is a contiguous subsequence of N.

If lists M and N have the same head and the tail of M is a prefix of the tail of list N THEN list M is a sublist of N ELSE if list M is a sublist of the tail of N then list M is a sublist of L.








A number of extra logical predicates have been introduced in Prolog in order to improve efficiency.

3.6.1 The cut The cut, denoted by !, is a predicate of no arguments and allows the programmer to control the search for a proof by pruning branches from the proof tree. The predicate at the head of the rule with the cut, is considered to have failed when the cut is encountered during backtracking. The cut is always satisfied on forward subgoal expansion, but on backtracking it always fails. Furthermore, the goal that called the rule containing the cut fails. All other rules following the rule with the cut and which share the same head are aborted and not tried either.

We demonstrate the effect of the cut in the following examples. Suppose we want to write a version of the delete predicate, delete(X,L,M), which deletes only the first occurrence of X in the list L and binds the result to the list M. The cut can be used to achieve this as follows:




The query


produces the answer



The search terminates after the first deletion because of the cut which kills the delete goal. If in the second rule the cut is omitted then more than one occurrence of an element can be deleted as:









The effect of the cut on the proof tree of delete is shown in Figure 3.3. The cut terminates the search after the first occurrence of the element is deleted from the list.

Figure 3.3 The AND/OR proof tree for ?delete(a,[a,b,a,c],M).

Another example of how the cut affects a program is given below. cdc and cat are the names of two local companies. Consider the following knowledge base, where the facts and rules have been labeled for future reference:

(F1) local(cdc).

(F2) local(cat).

(F3) growing(cdc).

(F4) growing(cat).

(F5) nolayoffs(cdc).

(F6) stocksup(cat).

(R1) invest_in(X):-local(X),stable(X).

(R2) stable(X):-growing(X),stocksup(X).

(R3) stable(X):-nolayoffs(X).

When queried on which company to invest in:


it provides the answer:




If the cut is introduced in the second rule and rule (R2) is replaced by (R2')

(R2) stable(X):-growing(X),!,stocksup(X).

the query invest_in gives:




The proof tree is shown in figure 3.4. During traversal of the proof tree for the program with the cut, the disjunctive subgoal stable(cdc) is reached. Following the branch with rule (R2) leads to a dead end. During backtracking, the cut is encountered and its effect is to kill the subgoal stable(cdc) and the other disjunctive branches are not tried. So backtracking goes all the way to the conjunctive subgoal local(X).

Figure 3.4 The AND/OR proof tree for ?invest_in(X).

3.6.2 Other Extra_Logical Predicates Some built in predicates

An additional list of extra logical predicates which are quite useful in writing programs is given below.

var(X) is true iff X is an unbound variable, false otherwise.

see(Filename) opens a file for input.

read(X) reads from the currently open input file and bounds X to the input value. If no file has been opened it reads input from the screen.

seen closes the input file opened by see and the screen is reset as the input medium.

tell(Filename) opens file Filename as output file.

write(X) writes the value bound to X into the file currently open by tell or if no output file has been opened, it writes on the screen.

told closes the current output file and resets the screen as output medium.

fail forces backtracking as it is always false.

clause(A,B) creates a rule with head equal to A and body B, A:-B.

S=.. L where S is a term and L is a list. A list is L is converted into a term S and vice versa.


finds all the answers to the query Query and puts them in List predicate is known as bagof instead of findall). Examples

An example of how findall works is given below.

Given the facts:



the query




and the query




We give below an example of how the universal predicate "=.." works.





The prolog predicate call issues its argument as a query to the system. For example:


returns X=bradleyhall.

As an example of using the call and =.. predicates, consider the following prolog procedure to implement the Lisp function mapcar. mapcar applies a given operator to each individual element of a list to derive a new list. Suppose add1 is defined as:

add1(X,Y):-Y is X+1.




Procedure mapcar can be defined as follows:

mapcar(Op,[ ],[ ]).

mapcar(Op,[H1|T1],[H2|T2]):-Goal=..[Op,H1,H2],call(Goal),mapcar(Op,T1,T2). Updating the knowledge base

The following predicates can alter the knowledge base by adding or deleting knowledge. If the variable Fact is bound to a prolog fact or rule, then:

asserta(Fact)____adds the value bound to Fact as a fact in front of all the

facts and rules with the same predicate name.

assertz(Fact)____appends the value bound to Fact as a new fact in the knowledge

base after all the facts and rules with the same predicate name.

retract(Fact)____deletes the fact equal to the value bound to Fact from the

knowledge base.


The following example shows how a decision tree knowledge structure can be implemented in Prolog.

An investor is to be advised which stock to buy into: oil, computers or telecommunications. The advice is based on the type of portfolio the investor is to maintain.

For example, investors can be classified into one of the following categories, based on the type of portfolio:

high_risk, moderate_risk, or stable_risk portfolios.

A sample classification tree incorporating the knowledge used for determining the portfolio type is shown in the decision tree of Figure 3.5.

Figure 3.5 Decision tree for portfolio type classification.

A decision on which stock to invest in can be made based on the investor's portfolio type. An investor suited for a stable risk portfolio should invest in oil, a moderate risk portfolio in telecommunications and a high risk in computers.

The rule base representation of the investment knowledge above can then expressed in Prolog as follows:

moderate_risk(X):-ask_marital_status(X,Y), Y=married, ask_income(X,I), I<=50000, 'ask_mortgage(X,Z), Z<=50000,!.

moderate_risk(X):-ask_marital_status(X,M),M=married),ask_income(X,I), I>50000,!.

moderate_risk(X):-ask_marital_status(X,M), M=single, ask_income(X,I), I<=35000,!.

stable_risk(X):-ask_marital_status(X,M), M=married, ask_income(X,I), I<=50000,

' ' ask_mortgage(X,Z), Z>50000,!.

stable_risk(X):-ask_marital_status(X,M), M=single, ask_income(X,I), I>35000,

' ' ask_age(X,A),A>50,!.

high_risk(X):-ask_marital_status(X,M), M=single, ask_income(X,I), I>35000,

' ' ask_age(X,A),A<=50,!.




We now build a input/output interface module to extract the needed nformation about income, mortgage, age and marital status from the user.

main(X,Z):-var(X), write('what is your name?'),read(X), invest(X,Z),!.



ask_marital_status(X,Y):-not(marital_status(X,Y)), write('what is your marital

' ' status:married or single?'), read(Y), asserta(marital_status(X,Y)).


ask_income(X,Y):-not(income(X,Y)),write('what is your annual income?'), read(Y),

' ' asserta(income(X,Y)).


ask_mortgage(X,Z):-not(mortgage(X,Z)),write('what is your remaining mortgage?'),

' ' read(Z), asserta(mortgage(X,Z)).


ask_age(X,A):-not(age(X,A)), write('what is your age?'), read(A), asserta(age(X,A)).

Here is a sample run of the program:


what is your name?


what is your marital status?


what is your income?


what is your mortgage?


X=smith, Y=oil

Questions about one's income, marital status, etc. are not repeated after they are asked once. This is achieved as follows. Every time an answer to a question is supplied by the user, the answer is appended to the knowledge base as a fact. Before asking a question we check to see if there is a fact already appended in the knowledge base providing the answer, in which case the question is not repeated.


Even though Prolog was not intended as a procedural language and should not be used as such, we show in this section that it is possible to implement procedural programs in Prolog.

3.8.1 If-Then-Else

Consider the IF control structure:

If X=0 Then A=1

Else A=2;

It can implemented in Prolog as the predicate if(X,A):

if(X,A):-X=0,A is 1.

if(X,A):-not(X=0), A is 2.

or using the cut:

if(X,A):-X=0,!,A is 1.

if(X,A):-A is 2.

3.8.2 Linked Lists

The linked list of Figure 3.6 can be implemented in Prolog as a set of facts of the form:

list(Previous_pointer, Data, Next_pointer),

where the arguments correspond to the list node identifier, the data stored in the node and the pointer to the next node of the linked list. The predicate head(List_name, Head_pointer_id) is also used to indicate the identifier number of the first element of the list List_name.

Figure 3.6 A linked list.





A predicate delete(P) to delete the element at position P of the list List_name is given below:

delete(P,List_name):-head(List_name,Head),Head=P,list(P,D,N),retract(head(Head,P)), assert(head(Head,N)).

delete(P,List_name):-list(P,D,N),list(A,B,P),L is N, retract(list(P,D,N)),

, ' retract(list(A,B,P)), asserta(list(A,B,L)).

3.8.3 Stacks

The abstract data type stack is a list of elements where insertion and deletion can only take place at one end of the list called the stack top. The stack operators are the pop (delete element on top of stack) and push (insert an element on top of the stack). A stack can be easily implemented as a list.

Here is the push operator in Prolog:

push(Element,Stack, [Element|Stack]).

When queried:

?push(3, [2,5,4], S).



3.8.4 Queues

The Abstract data type queue is a list of elements where insertion takes place at one end called the rear of the queue and deletion at the other end called the front of the queue. The queue operators are enqueue (insert an element in the queue) and dequeue (delete an element from the queue).

The enqueue operator in Prolog is given below:



When queried gives:

?enqueue(3, [2,5,4], Q).


3.8.5 Loops

The traditional control structure of the while loop: while (condition) do (statements); can be implemented as follows.



For example, consider the procedural program written in pseudolanguage:


Read (amount);

While amount>0 do





An implementation in Prolog would be:

calculate(Total):-Subtotal is 0,read(Amount),whilepositive(Amount,Subtotal,Total).

whilepositive(Amount,Stotal,Total):-Amount<=0,Total is Stotal.

whilepositive(Amount,Stotal,Total):-Stotal1 is Stotal+Amount, read(Amount1),

' , whilepositive(Amount1,Stotal1,Total).

Note: The variables Amount1 and Stotal1 were used in the third rule because the prolog read predicate requires an unbound variable as argument and similarly Stotal is Stotal+Amount is always false in Prolog whenever Stotal is bound to a value.

3.8.6 Graph search algorithms

A graph can be easily implemented in Prolog by using its linked list representation. It is denoted by a set of facts of the form graph(Source_node,Destination_node).

For example the graph of Figure 3.7 can be represented as the set of facts:






Figure 3.7 A graph

Search algorithms are a focal point of AI techniques and form the basis for many A.I. algorithms. The reader is referred to Winston's book on Artificial Intelligence [18] for a complete review of various search algorithms including A*, minimax etc.

As a Prolog exercise, we present here the Prolog implementation of the depth first search algorithm. (see the text "Techniques of Prolog Programming", by Van Le, ([16]), for prolog implementations of dfs and many other search algorithms).

The depth first search algorithm for a graph can be expressed in pseudo language as follows.

Depth First Search

To find a path from the source node to the goal node start with an initial path consisting of the source node and extend it until the goal state is reached. The list Visited and Answer are initialized to contain the source node and the list Answer will eventually contain the path to the goal. Both lists are treated as stacks.

If the path in Answer has reached the goal node then this is the answer path



If (a neighboring node to the head node in list Answer exists which does not belong to the list Visited)


push it as a new head on both of the stacks Visited and Answer


pop the stack Answer.

Until the goal node has been reached or the Answer stack is empty.

If the stack Answer is empty

then "there is no path from source node to destination"


Answer contains a path from source to destination node.

The prolog implementation of the dfs algorithm is given below. dfs(Goal,Visited,Answer) is a recursive procedure where the variable Goal contains the goal state, Visited contains a list of states already traversed with current state at the head and Answer is the list of states from start to goal.

dfs(Goal, [Goal|_], [Goal]).

dfs(Goal,[Current|Past],[Current|Future]):-graph(Current,Next), not(member(Next,Past)), dfs(Goal,[Next,Current|Past], Future).

The second rule states that if the visited stack has Current at the top and Next is a neighboring node of Current, then the answer stack will be the element Current followed by the dfs path starting at Next.

3.8.7 The Farmer, Fox, Goose and Grain.

As an example of an application of depth first search consider the Farmer, fox, goose and grain problem often used in A.I. to demonstrate concepts. On the west side of a river a farmer stands with a fox, a goose and some grain. He wants to cross to the east side and carry all his belongings with him. The only means of crossing the river is a boat which can only hold two objects at a time one of which has to be the farmer as he has to row the boat. In what order should he carry his belongings across the river? The constraints of the problem are that he cannot leave the fox and the goose alone on one side of the river while he is on the other. The fox will eat the goose. Similarly he cannot leave the goose and the grain alone on one side without him being there. What is the sequence of moves to get everything on the other side?

This is a typical state-space problem. The environment is described by a state. There are operators that transform one state to another. One state is designated as the initial state and another as the goal state. The search problem is to find which sequence of operator applications will lead to the final state.

In the Farmer-fox-goose-grain problem, a state can be described as a list containing the positions of the four objects in the order [Farmer_position, Fox_position, Goose_position, Grain_position]. For example, the list [west,west,east,east] represents the state where the farmer and the fox are on the west side and the goose and the grain on the east side of the river (an undesirable state). The problem can be represented as a graph with the nodes being the problem states. An arc between two nodes indicates that it is possible to get from one to the other by a boat trip of the farmer across the river. The starting state is [west,west,west,west] and the goal state is [east,east,east,east]. The graph of legal moves is given below.















Given this graph description, the issue of the query dfs([w,w,w,w],[[e,e,e,e]],Answer) will produce the answer:


Answer=[[w,w,w,w],[e,w,e,w],[w,w,e,w],[e,e,e,w],[w,e,w,w],[e,e,w,e],[w,e,w,e], [e,e,e,e]]

So the farmer should carry the goose across, come back and carry the fox across. Come back to the west side with the goose and carry the grain over to the east side. Come back to the west side by himself and take the goose to the east side at which point he is done.

3.8.8 Towers of Hanoi

The Towers of Hanoi problem requires that a sequence of moves is found to move a set of disks from one peg to another under certain constraints on how the disks can be moved.

Consider the three pegs labeled 1, 2 and 3. Assume N disks are located on peg 1. Each disk on top of another is of smaller diameter than the disk it rests on. The goal is to move all disks from peg 1 to peg 3. In each move we are allowed to only move one disk and we have to place it on one of the pegs. A disk of larger diameter is not allowed to be placed on top of a disk of smaller diameter. What sequence of moves have to be employed?

Here is a Prolog program to solve the Towers of Hanoi problem:

The predicate hanoi takes four arguments. The first is the number of disks that are to be moved, the second is the starting peg label, the fourth is the final destination peg label, and the third is the intermediate peg label which is to be used as auxiliary peg during the moves.

hanoi(1,S,M,G):-write('move'), write(S), write('to'), write(G).

hanoi(N,S,M,G):-L is N-1, hanoi(L,S,G,M),write(S), write('to'), write(G), hanoi(L,M,S,G).


The efficiency of a Prolog program can be affected by the order in which the OR clauses are written as well as by the order in which the AND clauses inside a rule body are written. To increase efficiency various techniques for optimization of sequential or parallel prolog programs have been proposed.

3.9.1 Optimization of sequential processing of Prolog.

Prolog uses a resolution based inference mechanism with set of support and the theorem to be proved is in the initial set of support. The search strategy is a depth first search of the proof tree with backtracking. Using this blind search a lot of time could be wasted going down a very long path of the AND/OR tree to only meet failure and backtrack. The order in which conjunctive clauses in the body of a rule are written, as well as the order in which disjunctive clauses appear in a procedure, can shorten or prologue the search for an answer to the query. Warren, [17], proposed the following measure for estimating the cost of queries:

The cost of a subgoal is the number of facts matching the subgoal divided by the product of the domain size of each instantiated argument. The total cost of a conjunction is the sum of the costs of the conjunctive subgoals.

We give an example to demonstrate how reordering of conjunctions can affect efficiency. Consider the following knowledge base.
















Now consider the query:


The costs for the subgoals in the first rule are:

cost(textile)=7, cost(property)=7/(7*5)

since X will be instantiated and there are 7 choices for it and there are 5 facts with hydrophilic in them. The total cost is 7.02.

If the subgoals in the rule are reordered as:


the total cost is cost=cost(property)+cost(textile)=7/5+5/7=2.114.

The reader can verify that reordering the subgoals in the rule, so that "property" is listed first and "textile" second results in a more efficient and quick answer to the query.Warren's measure can also be extended to reorder disjunctive clauses.

Another method for optimizing sequential processing of Prolog code is given in Gooley and Wah, [8]. They evaluate the cost and the probability of success of a goal using Markov chains. A version of the A* algorithm is used to find which reordering of conjunct produces the smallest total cost. For optimization techniques based on semantic and entropic measures which are applied to logic programs in general and Prolog in particular, the reader is referred to Nikolopoulos, [10].

3.9.2 Parallel logic programs and languages

Logic programming languages render themselves to parallelism in a natural way because of the separation of control from the program semantics and their nondeterministic nature. Many parallel logic programming languages and parallel extensions of Prolog have been proposed including Parlog, Concurrent Prolog, Guarded Horn Clauses and the Relational Language (Takeuchi, [15]).

In OR-parallelism, when a disjunctive (OR) node is reached in the proof tree, searches can be performed for all the disjunctive branches in parallel. When one of the paths reaches a solution, search can terminate for the disjunctive goal, unless of course all the solutions are required. Pure OR-parallelism eliminates the need for backtracking, but imposes high copy time and storage overhead. At each branching node, the previous environment, containing the unifications done so far, has to be copied to each of the parallel processes. Various methods have been proposed for reducing copy overhead (Overbeek, [12], Ciepielewski, [3]).

AND-parallelism can improve both nondeterministic and deterministic logic programs. Conjunctive subgoals have to communicate with each other by passing information about their bindings. When the ANDed subgoals are independent (they do not share variables) execution can proceed without conflicts. If the goals share variables, the two variables must be bound to the same value. Thus, AND-parallelism occurs overhead in variable binding conflicts and communication. Consider the rule:


and the query:


The conjunctive subgoal is created: mother(mike,Y),father(mike,Z) and both predicates can be searched in parallel as they are independent. On the other hand, given the

query ?parents(X,mary,joe).

the conjunctive subgoal mother(X,mary),father(X,joe) is created. The two predicates are dependent as they share a variable, and this complicates parallel processing. The interested reader is referred to Conery, ([7]), for more details on parallel execution of logic programs and parallel versions of Prolog.


Prolog is a logic programming language based on Kowalski's procedural interpretation of logic programs. Its knowledge representation language is first order predicate calculus restricted to Horn clauses, and its inference strategy is based on depth first search of the proof tree with backtracking. The deductive technique is based on Robinson's set of support resolution strategy. Prolog is a declarative, not a procedural language. It frees the programmer from having to specify how things are to be done (the built in inference engine takes care of that) and instead requires that the programmer declares what he knows about the problem domain in the Prolog logical syntax. This makes Prolog especially suitable for applications like expert system development, natural language processing and deductive databases.


1. Write a Prolog program which determines the IRS tax return filling status for an individual. As your knowledge acquisition source use the IRS rules contained in the IRS instructions for filling booklet.

2. Write a prolog program to retrieve in variable X the element at the front of a queue and dequeue the queue.

?dequeue(X, [3,4,8],L).



3. Write a Prolog procedure to merge two sorted lists.




4. Write a Prolog procedure to check if a list is in ascending or descending order.







5. Write a procedure, fib(X,N), to find the Nth Fibonacci number (in the Fibonacci sequence the element in position 0 is equal to 1, the element in position 1 is equal to 1 and in general the element in position N is equal to the sum of the previous two elements in positions N-1 and N-2).



6. Modify the Prolog program of section 3.7 which implements a decision tree, so that when the user responds to a question with an illegal answer, the system asks to please reenter an answer among the set of specified choices.

7.* Write a Prolog procedure to sort a given list using Quicksort. (for an explanation of the quicksort sorting algorithm see any Data Structures book).

8.* Write a Prolog procedure, mult(A,B,C), to multiply two matrices A, B and store the result in matrix C. A matrix is represented as a list of lists, where each sublist is a matrix row.

For example, [[1,4,3],[3,2,4],[6,5,3]] is a 3 by 3 matrix.

(Hint: write a procedure to transpose a matrix (make the rows columns and the columns rows) and a procedure to find the inner product of two vectors. Then, to find the product of matrices A*B, transpose the matrix B and use the inner product procedure on A and the transpose of B).

9.* Write a Prolog procedure to insert an element into a binary search tree. (A binary search tree has the form tree(Root,tree(Leftsubtree),tree(Rightsubtree)).

For example,




[1] Bratko, Ivan, Prolog Programming for Artificial Intelligence, Addison Wesley, 1990.

[2] Clark, K., Gregory, S. "PARLOG: Parallel programming in Logic", ACM Transactions on Programming Languages and Systems, Vol. 8, 1, 1986, pp. 1-49.

[3] Ciepielewski, A., Haridi, S., "Control of activities in the OR-parallel token machine", Proc. of 1984 Symp. on Logic Programming, Atlantic City, NJ, 1984, 49-57.

[4] Clocksin, W.F., Mellish, C.S., Programming in Prolog, Springer Verlag, New York, 1987.

[5] Colmerauer, A., "Prolog and infinite trees", in: Logic Programming, K.L. Clark and S.A. Tarnlund, Eds., Academic Press, 1982, pp. 231-251.

[6] Colmerauer, A., "Prolog in 10 Figures", Communications of the ACM, 28:12, 1985, pp. 1296-1310.

[7] Conery, J., Parallel execution of logic programs, Kluwer Academic Publs, 1987.

[8] Gooley, M.M., Wah, B.W., "Efficient reordering of Prolog programs", Trans. Knowledge and Data Engineering, vol. 1, n. 4, pp. 470-482.

[9] Kowalski, R.A., "Algorithm=logic+control", Commun. ACM, 22, 7, 1979, pp. 424-436.

[10] Nikolopoulos, C. "An intelligent search strategy for logic programs", Proc. of Fourth Intern. Confer. on Symbolic and Logical Computing, 1989, pp. 307-318.

[11] Nikolopoulos, C. "Object Oriented, Deductive Databases", Database and Network Journal, 23, 1,1994

[12] Overbeek, R.A., J. Gabriel, T. Lindholm, E.L.Lusk, "Prolog on Multiprocessors", Techn. report, Argonne Nat., Labs, 1985.

[13] Robinson, J.A., "A machine oriented logic based on the resolution principle", J. ACM, 12, 1, 1965, pp. 23-41.

[14] Subrahmanyan, P.A., "The software engineering of Expert Systems: Is Prolog appropriate?", IEEE Trans. Softw. Engin., SE-11, 11, 1985, pp. 1391-1400.

[15] Takeuchi, A., Furukawa, T., "Parallel logic programming languages", ICOT Techn. report, Tokyo, Japan, 1986.

[16] Van Le, T., Techniques of Prolog Programming, John Wiley, 1993.

[17] Warren, D.H., Efficient Processing of interactive relational database queries expressed in logic", Proc. of Intern. Confer. on VLDB, 1981.

[18] Winston, P., Artificial Intelligence, Reading, MA: Addison Wesley, 1987.