Transcript Introduction to Prolog - Faculty Personal Homepage

An Introduction to Prolog
Dr. Muhammed Al-Mulhem
ICS535-101
1
Prolog statements
Like other programming languages, Prolog
consists of collection of statements.
Prolog has two basic statement forms:
– Headless Horn clause – called facts
– Headed Horn clause – called rules
Dr. Muhammed Al-Mulhem
ICS535-101
2
Facts
Represent statements that are always true.
The parameters are usually (but not always) constants
Examples:
– female(mary).
– male(bill)
– male(jake)
– father( bill, jake).
– mother( mary , jake).
These simple structure state certain facts about jake, bill and mary.
Note that these Prolog facts have no intrinsic semantics. They mean
whatever the programmer wants them to mean.
For example father( bill, jake). Could mean:
– Bill and jake have the same father
– Jake is the father of bill
The most common meaning is that bill is the fatehr of jake.
Dr. Muhammed Al-Mulhem
ICS535-101
3
Facts (contd.)
fortran
algol60
Example Facts:
link(fortran,algol60).
simula67
cpl
bcpl
c
link(c,cplusplus).
cplusplus
smalltalk80
link(algol60,cpl).
link(algol60,simula67).
link(cpl,bcpl).
link(simula67,cplusplus).
link(bcpl,c).
link(simula67,smalltalk8).
Dr. Muhammed Al-Mulhem
ICS535-101
4
Rules
This is the other basic form of Prolog statement.
Used to construct the database corresponds of
facts.
It is a headed Horn clause
Use :- instead of  and a comma instead of a 
Right side: antecedent (if part)
– May be single term or conjunction
Left side: consequent (then part)
– Must be single term
Dr. Muhammed Al-Mulhem
ICS535-101
5
Rules
parent(kim,kathy):- mother(kim,kathy).
Can use variables (universal objects) to generalize
meaning:
parent(X,Y):- mother(X,Y).
sibling(X,Y):- mother(M,X),
mother(M,Y),
father(F,X),
father(F,Y).
Dr. Muhammed Al-Mulhem
ICS535-101
6
Rules (contd.)
Example Facts:
link(fortran,algol60).
link(c,cplusplus).
fortran
algol60
simula67
link(algol60,cpl).
link(algol60,simula67).
link(cpl,bcpl).
cpl
bcpl
c
link(simula67,cplusplus).
cplusplus smalltalk80
link(bcpl,c).
link(simula67,smalltalk8).
Example Rules:
path(X,Y) :- link(X,Z) , link(Z,Y).
Dr. Muhammed Al-Mulhem
ICS535-101
7
Goals
Facts and rules are used to describe both known facts and rules that
describe logical relationships among facts.
These statements are the basis for the theorem proving model.
The theorem is in the form of a proposition that we want the system to
either prove or disprove.
In Prolog, these propositions are called goals.
A series of one or more propositions, separated by commas
Should be thought of as a query
If the parameters of the goal are all constants, then the answer to the
query should be “Yes” or “No”
If the parameters of the goal contain variable(s), then the answer to the
query should be all the values for those variables which satisfy the query,
or “No” if no value satisfies it.
Dr. Muhammed Al-Mulhem
ICS535-101
8
Goals
Example:
– link(algo60,L) , link(L,M).
/* “Are there some values for L and M such that algo60 is
linked to L and L is linked to M?” */
=============================================
– male(ahmad).
/* Answer should be Yes/No */
– father(X,ali).
/* Answer should be X = “ ??” or No */
– father(ali,naser).
/* Answer should be Yes/No */
– father(bill,X), mother(mary,X).
/* Answer should be X = “??? or NO*/
Dr. Muhammed Al-Mulhem
ICS535-101
9
Prolog Programs
Are a series of facts and/or rules.
Can be placed in any order, due to
the nonprocedural nature of logicbased languages
Are “executed” in a Prolog
environment using goal statements.
Dr. Muhammed Al-Mulhem
ICS535-101
10
Inferencing Process of Prolog
If a goal is a compound proposition, each of the facts is a subgoal.
To prove a goal is true, the inferencing process must find a chain of
inference rules and/or facts in the database that connect the goal to
one or more facts in the database.
For example, if Q is a goal, then either Q must be found as a fact in
the database or the inferencing process must find a fact P1 and a
sequence of propositions P2, P3, …Pn such that
P2 :- P1.
P3 :- P2.
…
Q :- Pn.
Process of proving a subgoal is called matching, satisfying, or
resolution
Dr. Muhammed Al-Mulhem
ICS535-101
11
Example
Consider this goal
man(bob)
This goal is compared with the facts and rules in the
database. If the database includes the fact
man(bob)
The proof is trivial—Yes.
If , however, the database contains the following fact
and rule.
father(bob)
man(X) :- father(X)
Prolog should find these two statements and use them
to infere truth of the goal.
Dr. Muhammed Al-Mulhem
ICS535-101
12
Trace Example
Dr. Muhammed Al-Mulhem
ICS535-101
13
Inferencing Process of Prolog
Bottom-up resolution, forward chaining
– Begin with facts and rules of database and attempt
to find sequence that leads to goal
– works well with a large set of possibly correct
answers
Top-down resolution, backward chaining
– begin with goal and attempt to find sequence that
leads to set of facts in database
– works well with a small set of possibly correct
answers
Prolog implementations use backward chaining
Dr. Muhammed Al-Mulhem
ICS535-101
14
Inferencing Process of Prolog
When goal has more than one subgoal, can use either
– Depth-first search: find a complete proof for the first
subgoal before working on others
– Breadth-first search: work on all subgoals in parallel
Prolog uses depth-first search
– Can be done with fewer computer resources
Dr. Muhammed Al-Mulhem
ICS535-101
15
Inferencing Process of Prolog
With a goal with multiple subgoals, if fail to show
truth of one of subgoals, reconsider previous
subgoal to find an alternative solution:
backtracking.
Begin search where previous search left off.
Can take lots of time and space because may
find all possible proofs to every subgoal.
Dr. Muhammed Al-Mulhem
ICS535-101
16
Simple Arithmetic
Prolog supports integer variables and integer arithmetic
is operator: takes an arithmetic expression as right
operand and variable as left operand
A is B / 10 + C.
Not the same as an assignment statement!
Should not be done with parameters
Either both sides must have all variables instantiated (in
which case is acts as a relational =) or just the lefthand
side is not instantiated (which means the lhs receives a
value)
Therefore, the following is never appropriate:
– Sum is Sum + Number.
Dr. Muhammed Al-Mulhem
ICS535-101
17
Arithmetic Example
Dr. Muhammed Al-Mulhem
ICS535-101
18
Arithmetic Example
Dr. Muhammed Al-Mulhem
ICS535-101
19
Recursion
Is the only way to do iteration in Prolog
Is usually accomplished with at least one fact and one
rule
Example: Consider the following mathematical definition
of factorial:
– 0! = 1
– n! = (n-1)! * n  n > 0
Here is the equivalent Prolog statements:
– fact(0,1).
– fact(N,NFact) :- N > 0, N1 is N-1,
fact(N1,N1Fact), NFact is N1Fact * N.
Dr. Muhammed Al-Mulhem
ICS535-101
20
List Structures
The value of a list consists of zero or more elements,
separated by commas and enclosed in square brackets.
Example: [apple, prune, grape, kumquat]
Each element can be an atom or a list
A variable such as L can be used to represent an entire
list in a statement.
The expression [E] in a statement denotes a oneelement list.
The expression [ ] in a statement denotes an empty list.
Dr. Muhammed Al-Mulhem
ICS535-101
21
List Structures
The expression [X | Y] in a statement denotes a list with
one or more elements where the first element is the
head X and the rest of the list (which may be empty) is
the tail Y.
– This is how recursion can be used to traverse each
element of a list.
– X is called the “car” and Y is called the “cdr”.
(These terms are from Lisp.)
– For example, in [apple, prune, grape, kumquat], apple
is the car, and [prune, grape, kumquat] is the cdr.
Dr. Muhammed Al-Mulhem
ICS535-101
22
List Structures
A list can be created with simple proposition.
new_list ([apple, prune, grape])
This does the kind of thing that the proposition
male(ahmad) does.
We could have a second proposition like
new_list ([ apricot, peach, pear])
In goal mode, the list can be dismantled into head and tail.
new_list ([ Head, Tail])
Then Head is instantiated to apricot, and Tail to [peach, pear]
The | can specify a list construction or a list dismanteling. Note that
the following are equivalent:
new_list ([ apricot, peach, pear | [ ]])
new_list ([ apricot, peach | [pear]])
new_list ([ apricot | [peach, pear]])
Dr. Muhammed Al-Mulhem
ICS535-101
23
Example 1
Appending two lists together
– append([ ],List,List).
– append([Head|List_1],List_2,[Head|List_3]) :- append(List_1,List_2,
List_3).
The first one specifies that when the empty list is appended to any other
list, that list is the result.
The second one specifies several characteristics of the new list.
The left-side states that the fist element of the new list is the same as
the first element of the first given list, because they are both named
Head.
The right-side specifies that the tail of the first given list (List_1) has the
second given list (List_2) appended to it to form the tail (List_3).
Dr. Muhammed Al-Mulhem
ICS535-101
24
Example 1
Dr. Muhammed Al-Mulhem
ICS535-101
25
Example 2
Reversing a list
– reverse([ ], [ ]).
– reverse([Head|Tail], List) :-
reverse(Tail,Result), append(Result,
[Head],List).
Dr. Muhammed Al-Mulhem
ICS535-101
26
Example 2
Dr. Muhammed Al-Mulhem
ICS535-101
27
Example 3
Seeing if a list has a particular member
– member(Element,[Element| _ ]).
– member(Element,[ _|List] :member(Element,List).
The _ is an “anonymous” variable; i.e., we don’t
care what the value is, although a value does
need to be there.
Dr. Muhammed Al-Mulhem
ICS535-101
28
Example 3
Dr. Muhammed Al-Mulhem
ICS535-101
29
Example 4
Definition of sum function:
sum([],0).
sum([H|T],N):-sum(T,M), N is H+M.
Dr. Muhammed Al-Mulhem
ICS535-101
30
Example 6
Definition of findOccurrences
function:
findOccurrences(X,[],0).
findOccurrences(X,[X|T],N):findOccurrences(X,T,Z), N is Z+1.
findOccurrences(X,[_|T],N):findOccurrences(X,T,Z), N is Z.
Dr. Muhammed Al-Mulhem
ICS535-101
31
Useful Exercises
Write a Prolog functor that interleaves two lists. For example given
the query:
?- interleave([1,2,3,4,5],[6,7,8,9,10],X).
It should return X = [1,6,2,7,3,8,4,9,5,10]
Write a Prolog functor that succeeds if its list input consists of
palindrome values. For example given the query:
?- palindrome([1,2,3,4,5,4,3,2,1]).
It should return Yes.
Write functors to compute:
– the Fibonacci function
– xy for integers x and y.
Dr. Muhammed Al-Mulhem
ICS535-101
32
Example 5
Definition of diffList function:
diffList([], List, []).
diffList([H|L1], L2, L3) :- not(member(H,L2)),
diffList (L1, L2, L4), append([H],L4,L3).
diffList([_|L1], L2, L3) :- diffList (L1, L2, L3).
Dr. Muhammed Al-Mulhem
ICS535-101
33
Deficiencies of Prolog
Resolution order control
The closed-world assumption
The negation problem
Intrinsic limitations
Dr. Muhammed Al-Mulhem
ICS535-101
34
Deficiencies of Prolog
Resolution Order Control
Depth-first search method can cause infinite recursion
– Example:
ancestor(X,X).
ancestor(X,Y) :- ancestor(Z,Y), parent(X,Z).
– Keeps trying to satisfy the second rule
– Can be solved by reversing the two propositions on
the right, but that is against the basic nonprocedural
philosophy of Prolog
Dr. Muhammed Al-Mulhem
ICS535-101
35
Deficiencies of Prolog
Resolution Order Control (Cont.)
The cut operator !
– Can eliminate backtracking
– Is useful when a proposition can only be satisfied once
– Form is a,b,!,c,d
If c is not satisfied, the statement cannot go back and find
another possible value for b
– Example:
member(Element, [Element | _ ]) :- !
member(Element, [ _ | List]) :- member(Element,List).
The change in the first statement assumes that the list
consists of unique members.
– The cut operator also is contrary to the Prolog philosophy of
nonprocedural programming
Dr. Muhammed Al-Mulhem
ICS535-101
36
Deficiencies of Prolog
Close World Assumption
• If Prolog has insufficient data to answer a
question, the answer is “no”, just as it would
be if it had sufficient data to answer “no”.
Dr. Muhammed Al-Mulhem
ICS535-101
37
Deficiencies of Prolog
The Negation Problem
Consider the following statement:
sibling(X,Y) :- parent(M,X), parent(M,Y).
– Nothing keeps a person from being their own sibling!
Can be solved with a not proposition:
sibling(X,Y) :- parent(M,X), parent(M,Y),not(X = Y).
However, the not proposition is not a not operator (double
negation is not allowed), which causes some limitations
Dr. Muhammed Al-Mulhem
ICS535-101
38
Deficiencies of Prolog
Intrinsic Limitations
• Prolog is often not efficient
• Example:
sorted([ ]).
sorted([x].
sorted([x, y | list]) :- x <= y, sorted([y | list]).
– All permutations of list must be tried until the
right one is found.
Dr. Muhammed Al-Mulhem
ICS535-101
39
Applications of Logic
Programming
Relational database management
systems
Expert systems
Natural language processing
Education
Dr. Muhammed Al-Mulhem
ICS535-101
40
Conclusions
Advantages:
– Prolog programs based on logic, so likely to
be more logically organized and written
– Processing is naturally parallel, so Prolog
interpreters can take advantage of multiprocessor machines
– Programs are concise, so development time
is decreased – good for prototyping
Dr. Muhammed Al-Mulhem
ICS535-101
41
Summary
Predicate calculus provides a formal means for logical
expressions (I.e. those that evaluate to true or false)
Horn Clauses provide a particular structure which can be
used for most logical expressions
Declarative semantics allows both for the focus of
problem solving to be on “what” rather than “how” and for
nonprocedural programming
Prolog uses declarative semantics
There are some deficiencies in Prolog, some of which
are inherent to declarative semantics
Dr. Muhammed Al-Mulhem
ICS535-101
42