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.
3.1 PROLOG BASICS
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
c:-a;b.
is equivalent to the set of two rules:
c:-a.
c:-b.
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:
color(X,C):-part_of(X,Y),color(Y,C).
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:
faculty(smith,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
"location(X,Y):-location(Z,Y),dept_in(X,Z).",
a query such as
"?location(engineering,sisson)."
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]).
3.2 THE PROLOG INFERENCE ENGINE
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
consult('filename').
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).
yes
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).
L=engineering
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
?dept_in(D,engineering).
D=electrical_engineering;
D=civil_engineering;
no
As a third example, consider the query "which department or college is Smith a
faculty in?", written in Prolog as:
?is_faculty_in(smith,D).
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
D=electrical_engineering.
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
is_faculty_in(smith,D)
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.
?is_faculty_in(smith,D).
D=electrical_engineering;
D=engineering;
no
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).
3.3 NEGATION
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)).
no
The answer to the query is false, because
dept_in(electricalengineering,engineering) is proven true.
On the other hand the query:
?not(dept_in(electrical_engineering,business).
yes
was found to be true, since no proof can be reached for the query
dept_in(electricalengineering,business).
The query
?not(dept_in(electrical_engineering,X)).
no
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:
dept_in(electrical_engineering,X).
The query
?dept_in(finance,X), not(dept_in(civil_engineering,X)).
yes
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.
?not(dept_in(electrical_engineering,D)),location(D,bradleyhall).
no
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
?location(D,bradleyhall),not(dept_in(electrical_engineering,D)).
D=business
should be used.
3.4 ARITHMETIC
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).
Examples:
(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.
income(smith,58000).
middle_class(X):- income(X,Y), Y>=30000, Y=<60000.
?middle_class(smith).
yes
3.4.1 The assignment operator
The assignment operator is denoted by "is", while "=" is the test for equality.
Examples:
% Find the sum of X and Y and store it in Z.
sum(X,Y,Z):- Z is X+Y.
?sum(3,4,Z).
Z=7
?sum(3,1,5).
no
?sum(3,4,7).
yes
% arithmetic procedures are usually not reversible
?sum(3,Y,7).
no
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.
?sum(3,Y,7).
Y=4
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.
Examples:
equal(X,Y):-X=Y.
?equal(3,5).
no
?equal(3,Y).
Y=3;
yes
?equal(3,3).
yes
?equal(ab,ab).
yes
?equal(X,rich(mike)).
X=rich(mike)
?equal(father(X,mike),father(joe,Y).
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:
?fact(4,N).
N=24
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(0,1).
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(1,_,1).
exp(_,0,1).
exp(X,N,Z):-M is N-1, exp(X,M,R), Z is R*X.
3.5 LISTS
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:
schedule([saturday,swimming,sunday,church]).
the answer to the query
?schedule(X).
is X=[saturday,swimming,sunday,church]
while the answer to the query
?schedule(X,Y,Z,W).
no
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
?schedule([X,Y,Z,W]).
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
schedule([saturday,swimming,sunday,church]).
the query
?schedule([X|L]).
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,
?schedule([X,Y|L]).
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:
car([X|L],X).
or as:
car([X|L],First):-First=X.
Given the query
?car([3,4],X).
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
?cdr([3,4,5],L).
gives L=[4,5]
2. A function to determine if an atom belongs to a list.
member(X,[X|L]).
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:
?member(3,[4,c,5]).
no
?member(3,[4,3,5]).
yes
?member(X,[4,3,5]).
X=4;
X=3;
X=5;
no
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([],0).
length([X|L],N):-length(L,M), N is M+1.
When queried it gives:
?length([1,2,3], N).
N=3
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).
append([X|L],M,[X|N]):-append(L,M,N).
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.
delete(X,[],[]).
delete(X,[X|L],M):-delete(X,L,M).
delete(X,[Y|L],[Y|M]):-not(X=Y),delete(X,L,M).
When queried gives:
?delete(a,[a,b,a,c],M).
M=[b,c];
M=[b,a,c];
M=[a,b,a,c];
no
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.
reverse([],[]).
reverse([H|T],R):-reverse(T,RT),append(RT,[H],R).
When queried gives:
?reverse([a,b,c],M).
M=[c,b,a]
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,
?union([2,3,4],[3,5,4,6],L).
L=[2,3,5,4,6]
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.
union([],List,List).
union([Head|Tail],Other_list,New_list):-
member(Head,Other_list),!,union(Tail,Other_list,New_list).
union([Head|Tail],Other_list,[Head|New_list]):-union(Tail,Other_list,New_list).
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:
?eliminate([2,3,2,4,3],L).
L=[2,4,3]
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.
prefix([],_).
prefix([Head|Tail1],[Head|Tail2]):-prefix(Tail1,Tail2).
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.
sublist([Head|Tail1],[Head|Tail2]):-prefix(Tail1,Tail2).
sublist(List1,[_|Tail2]):-sublist(List1,Tail2).
?sublist([3,4],[3,5,3,4]).
yes
?sublist([2,4],[3,2,5,4]).
no
3.6 EXTRA LOGICAL PREDICATES
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:
delete(X,[],[]).
delete(X,[X|L],L):-!.
delete(X,[Y|L],[Y|M]):-delete(X,L,M).
The query
?delete(a,[d,a,b,a,c],M).
produces the answer
M=[d,b,a,c];
no
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:
delete(X,[],[]).
delete(X,[X|L],L).
delete(X,[Y|L],[Y|M]):-delete(X,L,M).
?delete(a,[a,b,a,c],M).
M=[b,a,c];
M=[a,b,c];
M=[a,b,a,c];
no
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:
?invest_in(X).
it provides the answer:
X=cdc;
X=cat;
no
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:
?invest_in(X).
X=cat;
no
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
3.6.2.1 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.
findall(Term,Query,List)
finds all the answers to the query Query and puts them in List
predicate is known as bagof instead of findall).
3.6.2.2 Examples
An example of how findall works is given below.
Given the facts:
status(engineering,accredited).
status(computerscience,accredited).
the query
?findall(X,status(X,accredited),L).
returns
L=[engineering,computerscience]
and the query
?findall(accredited(X),status(X,accredited),L).
returns
L=[accredited(engineering),accredited(computerscience)]
We give below an example of how the universal predicate "=.." works.
?location(computerscience,bradleyhall)=..L.
L=[location,computerscience,bradleyhall]
?S=..[location,computerscience,bradleyhall].
S=location(computerscience,bradleyhall)
The prolog predicate call issues its argument as a query to the system.
For example:
?call(location(ee,X)).
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.
Then
?mapcar(add1,[1,4,5],L).
L=[2,5,6]
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).
3.6.2.3 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.
3.7 A PROLOG QUESTION ANSWERING SYSTEM
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,!.
invest(X,oil):-stable_risk(X),!.
invest(X,telecommunications):-moderate_risk(X),!.
invest(X,computers):-high_risk(X),!.
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),!.
main(X,Z):-invest(X,Z),!.
ask_marital_status(X,Y):-marital_status(X,Y).
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):-income(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):-mortgage(X,Z).
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).
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:
?main(X,Z).
what is your name?
smith
what is your marital status?
married
what is your income?
45000
what is your mortgage?
60000
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.
3.8 PROCEDURAL PROGRAMS IN PROLOG
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.
Head(names_list,5).
list(5,basil,10).
list(10,chris,3).
list(3,christian,0).
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).
Gives
S=[3,2,5,4]
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:
enqueue(Element,[],[Element).
enqueue(Element,[X|T],[X|T1]):-enqueue(Element,T,T1).
When queried gives:
?enqueue(3, [2,5,4], Q).
Q=[2,5,4,3]
3.8.5 Loops
The traditional control structure of the while loop:
while (condition) do (statements);
can be implemented as follows.
whiledo:-not(condition),!.
whiledo:-statements,whiledo.
For example, consider the procedural program written in pseudolanguage:
Total=0;
Read (amount);
While amount>0 do
begin
Total=Total+amount;
Read(amount);
end.
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:
graph(1,2).
graph(2,4).
graph(3,2).
graph(4,3).
graph(1,4).
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
else
Repeat
If (a neighboring node to the head node in list Answer exists which does
not belong to the list Visited)
then
push it as a new head on both of the stacks Visited and Answer
else
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"
else
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.
graph([w,w,w,w],[e,w,e,w]).
graph([e,w,e,w],[w,w,e,w]).
graph([w,w,e,w],[e,w,e,w]).
graph([w,w,e,w],[e,e,e,w]).
graph([w,w,e,w],[e,w,e,e]).
graph([e,e,e,w],[w,w,e,w]).
graph([e,e,e,w],[w,e,w,w]).
graph([e,w,e,e],[w,w,w,e]).
graph(e,w,e,e],[w,w,e,w]).
graph([w,w,w,e],[e,e,w,e]).
graph([w,w,w,e],[e,w,e,e]).
graph([e,e,w,e],[w,e,w,e]).
graph([e,e,w,e],[w,w,w,e]).
graph([e,e,w,e],[w,e,w,w]).
Given this graph description, the issue of the query dfs([w,w,w,w],[[e,e,e,e]],Answer)
will produce the answer:
?dfs([w,w,w,w],[[e,e,e,e]],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).
3.9 OPTIMIZATION OF PROLOG PROGRAMS
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.
textile(nylon).
textile(acrylic).
textile(silk).
textile(cotton).
textile(wool).
textile(rayon).
textile(linen).
property(silk,hydrophilic).
property(cotton,hydrophilic).
property(wool,hydrophilic).
property(rayon,hydrophilic).
property(linen,hydrophilic).
property(nylon,hydrophobic).
property(acrylic,hydrophobic).
hydrophilic_textile(X):-textile(X),property(X,hydrophilic).
Now consider the query:
?hydrophilic_textile(X).
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:
hydrophilic_textile(X):-property(X,hydrophilic),textile(X).
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:
parents(X,Y,Z):-mother(X,Y),father(X,Z).
and the query:
?parents(mike,Y,Z).
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.
SUMMARY
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.
EXERCISES
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).
X=3,L=[4,8];
no
3. Write a Prolog procedure to merge two sorted lists.
?merge([2,5,7],[4,5,6,8],M).
M=[2,4,5,5,6,7,8];
no
4. Write a Prolog procedure to check if a list is in ascending or descending order.
?ordered([3,4,7]).
yes
?ordered([6,4,2]).
yes
?ordered([2,6,4,9]).
no
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).
?fib(X,4).
X=5
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,
?intree(2,T),intree(3,T),intree(1,T).
T=tree(2,tree(1,L1,R1),tree(3,L3,R3).
REFERENCES
[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.