CSE240
Chapter 5
Logic Language Prolog
Lecture 25
Prolog Operations and Rules
Reading: Textbook Sections 5.1 – 5.3 and Appendix B.5
Dr. Yinong Chen
CSE240
Introduction to Programming Languages
‹#›
Ch 5
CSE240
11/19/2002
Introduction
Logic programming paradigm
Prolog programs: facts, rules, and goals
Factbase
Goals (Questions)
Matching and Searching for a solution
Compound questions
Arithmetic operations and rules
Recursion and graph operations
Parameter Passing
More recursive programs
Structures of facts and rules
Pairs, lists and their operations
Flow Control
Chapter 5 Outline
‹#›
Ch 5
CSE240
11/19/2002
Prolog Computing Model: Match and Search a Solution
?- qst(a1, …, an).
/*Facts*/
f1(x11, …, x1q).
f2(x21, …, x2q).
f3(x31, …, x3q).
. . .
fp(xp1, …, xpq).
/*Rules*/
r1(y11, …, y1t) :- s1.
r2(y21, …, y2t) :- s2.
r3(y31, …, y3t) :- …
. . .
rk(yk1, …, ykt) :- …
/*End*/
for i = 1 to p // check facts
if qst == fi then
if a1, …, an ==
xi1, …, xiq
then “yes”
If (read) == “enter”
exit
If (read) == “;”
continue
for i = 1 to k // check rules
if qst == ri then
. . .
‹#›
Ch 5
CSE240
11/19/2002
Example Part 1
/*Facts */
mother_of(jane, elaine).
mother_of(jane, mike).
father_of(mike, andrew).
father_of(andrew, luke).
/*Rules */
grandmother_of(X, Z) :-
mother_of(X, Y),
(mother_of(Y, Z);
father_of(Y, Z)).
?- grandmother_of(jane, conrad).
grandmother_of(jane, conrad).
mother_of(jane, Y).
mother_of(jane, elaine).
Prolog runtime searches iteratively, not recursively.
‹#›
Ch 5
CSE240
11/19/2002
Example Part 2
/*Facts
mother_of(jane, elaine).
mother_of(jane, mike).
father_of(mike, andrew).
father_of(andrew, luke).
/*Rules
grandmother_of(X, Z) :-
mother_of(X, Y),
(mother_of(Y, Z);
father_of(Y, Z)).
?-grandmother_of(jane, conrad).
grandmother_of(jane, conrad).
mother_of(jane, Y).
mother_of(jane, elaine).
mother_of(elaine, conrad).
father_of(elaine, conrad).
‹#›
Ch 5
CSE240
11/19/2002
Example Part 3
/*Facts
mother_of(jane, elaine).
mother_of(jane, mike).
father_of(mike, andrew).
father_of(andrew, luke).
/*Rules
grandmother_of(X, Z) :-
mother_of(X, Y),
(mother_of(Y, Z);
father_of(Y, Z)).
?-grandmother_of(jane, conrad).
grandmother_of(jane, conrad).
mother_of(jane, Y).
mother_of(jane, elaine).
mother_of(elaine, conrad).
father_of(elaine, conrad).
mother_of(jane, mike).
No
mother_of(mike, conrad).
father_of(mike, conrad).
‹#›
Ch 5
CSE240
11/19/2002
Example Part 3:
If we have this fact:
/*Facts
mother_of(jane, elaine).
mother_of(jane, mike).
father_of(mike, andrew).
mother_of(mary, conrad).
father_of(mike, conrad)
/*Rules
grandmother_of(X, Z) :-
mother_of(X, Y),
(mother_of(Y, Z);
father_of(Y, Z)).
?-grandmother_of(jane, conrad).
grandmother_of(jane, conrad).
mother_of(jane, Y).
mother_of(jane, elaine).
mother_of(elaine, conrad).
father_of(elaine, conrad).
mother_of(jane, mike).
Yes
mother_of(mike, conrad).
father_of(mike, conrad).
‹#›
Ch 5
CSE240
11/19/2002
Factbase Example
weather(phoenix, spring, hot). weather/3
weather(phoenix, summer, hot).
weather(phoenix, fall, hot).
weather(phoenix, winter, warm).
weather(wellington, spring, warm).
weather(wellington, summer, warm).
weather(wellington, fall, hot).
weather(wellington, winter, cold).
weather(toronto, spring, cold).
weather(toronto, summer, hot).
weather(toronto, fall, cold).
weather(toronto, winter, cold).
‹#›
Ch 5
CSE240
11/19/2002
Prolog Variables and Compound Questions
A anonymous variable represents a “don’t care” argument. It is indicated by an underscore, matches with anything, but no value will be return to the variable.
1) ?- weather(City, fall , hot).
–> City = phoenix
2) ?- weather(City, _ , hot).
–> City = phoenix; –> City = phoenix;
–> City = phoenix; –> City = wellington;
–> City = toronto; –> no
3) ?- weather(_, Season , warm).
–> Season = winter; –> Season = spring;
–> Season = summer; –> no
‹#›
Ch 5
CSE240
11/19/2002
Compound Questions
Use “,” as an and operator. Use “;” as an or operator.
1) ?- weather(C, summer, hot), weather(C, fall, hot).
–> C = phoenix
2) ?- weather(C, spring, warm), weather(C, fall, warm).
–> no
3) ?- weather(C, summer, hot); weather(C, fall, hot).
–> C = phoenix; –> C = phoenix;
–> C = toronto; –> C = wellington
4) ?- weather(C, summer, hot), weather(D, fall, hot).
–> C = D = phoenix; –> C = toronto
–> C = phoenix D = phoenix;
D = wellington; –> C = toronto
‹#›
Ch 5
CSE240
11/19/2002
Rules
A rule states a general relationship, normally uses variables as arguments, that may be used to conclude a specific fact or another rule.
Syntax of rules:
relationship(object, …, object) :- relationship(object, …, object).
head or conclusion neck or if body or condition
A fact is a special case of a rule: a rule without the body!
Examples:
dad(X, Y) :- father(X, Y). /* synonym */
child(Y, X) :- father(X, Y).
parent(X, Y) :- mother(X, Y); father(X, Y). /* “;” = “or” */
grandmother(X, Y) :- mother(X, Z), parent(Z, Y). /* “,” = “and” */
‹#›
Ch 5
CSE240
11/19/2002
Rules: More Examples
warmer_than(C1, C2) :-
weather(C1, spring, hot),
weather(C2, spring, warm).
colder_than(C1, C2) :-
weather(C1, winter, cold),
weather(C2, winter, warm).
weatherquestions :-
warmer_than(phoenix, X),
write(‘Phoenix is warmer than ‘), write(X), nl,
weather(City1, fall , hot),
write(‘City1 = ‘), write(City1), nl,
weather(City2, _ , hot),
write(‘City2 = ‘), write(City2), nl.
Stored program concept: Store/program all questions and ask them together
‹#›
Ch 5
CSE240
11/19/2002
Built-in Operators and Functions: Comparison
Each language has its strength and weakness. The weakness would be the Prolog syntax for manipulating of numbers, e.g.,
greater_than_or_equal_to (item1, item2)
is the way following the Prolog syntax and the idea of using the natural language style. It isn’t convenient.
To overcome this weakness, Prolog provides a set of built-in operators without following its syntax (use infix instead).
item1 @>= item2. item1 @< item2. 5 =< 4, 5 >= 4
X == ‘Zooey’. Y \== ‘Zooey’ 12 =:= 25
Note difference: 12 =\= 25
X = ‘Zooey’ –> X is given the value (unification)
‹#›
Ch 5
CSE240
11/19/2002
Arithmetic Operators
Addition:
?- X is 1+2.
–> X = 3
Subtraction:
?- X is 5 – 3.
–> X = 2
Multiplication:
?- X is 5 * 3.
–> X = 15
Floating-point division:
?- X is 5 / 2.
–> X = 2.5
Integer division:
?- X is 5 // 2.
–> X = 2
Modulo:
?- X is 75 mod 12.
–> X = 3
Exponential:
?- X is 2 ** 3.
–> X = 8
round(X, N).
random.
abs, sqrt, exp, sin, cos, tan, …
The general form:
‹#›
Ch 5
CSE240
11/19/2002
Arithmetic Operations: Example 1
A U.S. climatologist has following factbase:
ave_temp(berlin, 49).
ave_temp(karlsruhe, 60).
ave_temp(paris, 55).
ave_temp(belgrade, 52).
ave_temp(chicago, 50).
ave_temp(boston, 48).
ave_temp(johannesburg, 55).
ave_temp(phoenix, 80).
ave_temp(jerusalem, 61).
‹#›
Ch 5
CSE240
11/19/2002
Arithmetic Operation: Example 1
The climatologist now needs temperature in Celsius.
Hire a student to convert the temperature using the formula C = (F – 32) * 5 / 9 and add to the database:
ave_temp_celsius(berlin, 9).
ave_temp(karlsruhe, 16).
…
ave_temp_celsius(Location, C_temp) :-
ave_temp(Location, F_temp),
C_temp is (F_temp – 32) * 5 // 9.
?- ave_temp_celsius(berlin, Celsius_temp).
–> Celsius_temp = 9
Time consuming
Data redundancy
‹#›
Ch 5
CSE240
11/19/2002
Arithmetic Operation: Example 2
A school geography teacher has a factbase of city locations with the format: (City, Latitude, Longitude)
location(london, 51, 0).
location(phoenix, 33, 112).
location(tokyo, 35, -139).
location(rome, 41, -12).
location(madrid, 48, 3).
location(canberra, -35, -149).
location(johannesburg, -26, -28).
‹#›
Ch 5
CSE240
11/19/2002
Arithmetic Operation: Example 2
We can add a few rules to allow comparison of locations
north_of(X, Y) :-
location(X, Lat1, _),
location(Y, Lat2, _),
Lat1 > Lat2.
west_of(X, Y) :-
location(X, _, Long1),
location(Y, _, Long2),
Long1 > Long2.
north_of(madrid, tokyo). –> “yes”
north_of(Cities, rome). –> Cities = london, madrid
west_of(london, phoenix). –> “no”
west_of(london, Cities). –> Cities = canberra, johannesburg
Latitude
Longitude
‹#›
Ch 5
CSE240
11/19/2002
GNU Prolog Tutorial
Yinong Chen
‹#›
Ch 5
CSE240
11/19/2002
Read Unix and GNU Prolog Tutorial
Read Unix Tutorial in HW1 Folder
Use PuTTY on Windows or
Use Mac Built-in Terminal
PuTTY Download: http://www.chiark.greenend.org.uk/~sgtatham/putty/download.html
Connect to ASU General Server
Type your Prolog program in vim:
Prolog1.pl
Compile your program:
gplc Prolog1.pl
Execute your program: ./Prolog1
‹#›
Ch 5
CSE240
11/19/2002
GNU Prolog Video Tutorial
‹#›
Ch 5
CSE240
11/19/2002
Tutorial: Getting Started with GNU Prolog on Unix
‹#›
Ch 5
CSE240
11/19/2002