CSE240
Chapter 5
Logic Language Prolog
Lecture 27
More recursive programs, Pairs and Lists
Reading: Textbook Sections 5.4 and 5.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)
Rulebase
Compound questions
Arithmetic operations and rules
Recursion and graph operations
Parameter Passing
More recursive programs
Structures of facts and rules
Pairs, lists and more operations
Flow Control
Chapter 5 Outline
‹#›
Ch 5
CSE240
11/19/2002
Fibonacci Numbers
fib(F, N) :- N =:= 0, F is 0.
fib(F, N) :- N =:= 1, F is 1.
fib(F, N) :- N > 1,
N1 is N-1,
N2 is N-2,
fib(F1, N1),
fib(F2, N2),
F is F1 + F2.
³
–
+
–
=
=
=
2
)
2
(
)
1
(
1
1
0
0
)
(
n
n
fib
n
fib
n
n
n
fib
Is this rule a tail-recursive rule?
Compiler
Start Prolog
Run fib program
Compute fib(F, 7)
Result
Use PuTTY to connect to ASU General server
‹#›
Ch 5
CSE240
11/19/2002
Recursive Example: Hanoi Towers
The objective of this famous puzzle is
– to move N disks from the left peg to the right peg
– using the center peg as an auxiliary holding peg.
– At no time can a larger disk be placed upon a smaller disk.
– Move one disk at one time.
‹#›
Ch 5
CSE240
11/19/2002
Example with Four Disks
N disks
N-1 disks
Algorithm
Move N-1 disks
to the center
Move 1 disk
to the right
Move N-1 disks
to the right
‹#›
Ch 5
CSE240
11/19/2002
Hanoi Towers Program
hanoi(N) :- move(N, source, center, destination).
move(1, S, _, D) :- % stopping condition
write(‘Move top from ‘), write(S), write(‘ to ‘), write(D),
nl. % nl = newline
move(N, S, C, D) :- % size-N problem
N>1,
M is N-1,
move(M, S, D, C), % move N-1 disks from S to C
move(1, S, _, D), % move remaining 1 from S to D
move(M, C, S, D). % move N-1 disks from C to D
‹#›
Ch 5
CSE240
11/19/2002
Hanoi Tower Output
?- hanoi(3).
Move top from source to destination
Move top from source to center
Move top from destination to center
Move top from source to destination
Move top from center to source
Move top from center to destination
Move top from source to destination
‹#›
Ch 5
CSE240
11/19/2002
Structures of Facts and Rules
Prolog structures represent nested relationships.
Example
course(cse240, tues, thur, 1040, 1130, 140, 230, yinong, chen, coor184, byac150).
This long relationship can be restructured as follows
course(
cse240,
day(tues, thur),
time(140, 230),
instructor(yinong, chen),
byac150
).
course(
cse240,
day(tues, thur),
time(1040, 1130),
instructor(yinong, chen),
coor184
).
Structure of an argument: relationship followed by arguments, just like a fact.
‹#›
Ch 5
CSE240
11/19/2002
Factbase of Structured Relationship
course( cse210,
day(mon, wed, fri),
time(1340, 1430),
instructor(renee, turban),
ag350
).
course( cse240,
day(tues, thur , _ ),
time(1040, 1130),
instructor(yinong, chen),
coor184
).
course( cse240,
day(tues, thur , _),
time(1340, 1430),
instructor(yinong, chen),
byac150
).
course( cse225,
day(tues, thur , _ ),
time(915, 1030),
instructor(yinong, chen),
scob228
).
course( cse310,
day(mon, wed, fri),
time(940, 1030),
instructor(barb, gannod),
coor184
).
course( cse230,
day(mon, wed, fri),
time(1440, 1530),
instructor(john, doe),
pebe201
).
‹#›
Ch 5
CSE240
11/19/2002
Rulebase Extended from Factbase
Structured facts easily allow meaningful rules to be added
instructor(Instructor, Class) :-
course( Class,
_, /* Day */
_, /* Time */
Instructor,
_ ). /* Location */
room(Location, Day, Time) :-
course( _,
Day,
Time,
_,
Location).
‹#›
Ch 5
CSE240
11/19/2002
Queries to the Rulebase
(1) What instructors teach course cse240 and cse310?
?- instructor(Instructor, cse240).
–> instructor(yinong, chen);
–> instructor(yinong, chen);
–> no
?- instructor(Instructor, cse230).
–> instructor(john, doe);
–> no
‹#›
Ch 5
CSE240
11/19/2002
Queries to the Rulebase (contd.)
(2) What room is used in what day and time?
?- room(byac150, Day, Time).
–> Day = day(mon, wed , fri);
Time = time(1340, 1430);
–> no
?- room(coor184, Day, Time).
–> Day = day(mon, tue, _)
Time = time(1040, 1130);
–> Day = day(mon, tue, _)
Time = time(1340, 1430);
–> no
‹#›
Ch 5
CSE240
11/19/2002
List Definition
Using BNF notation, a Prolog list can be recursively defined as follows
::= [] % (empty list)
::= [
]
where
H is a variable or a value;
If we use [H | T] for a list, H is “car list” and T is “cdr list”, and [H | T] is a pair defined in Scheme.
Describe a simplification process to simplify the list
[1 | [2 | [3 | []]]] into [1, 2, 3].
‹#›
Ch 5
CSE240
11/19/2002
List and List Operations
Similar to Lisp/Scheme, Prolog can be used to process lists.
Factbase:
mother_of(sam, [alice, floyd, conrad]).
?- mother_of(sam, alice). –> no
A list is considered consisting of a head and a tail:
lst = [Head | Tail], where Head: “car lst” and Tail: “cdr lst”
mother_of(sam, [H | T]).
–> H = alice
T = [floyd, conrad]
‹#›
Ch 5
CSE240
11/19/2002
List and List Operations
mother_of(sam, [alice, floyd, conrad]).
mother_of(jane, [mike, sarah, george]).
mother_of(elaine, [tom, dick]).
?- mother_of(X, [_, _, _]). % who has 3 children
X = sam;
X = jane
?- mother_of(X, [H | [M | george]]).
?- mother_of(X, [H | [M | [george]]]).
X = jane
H = mike
M = sarah
no
‹#›
Ch 5
CSE240
11/19/2002
Examining Elements of List: Member Predicate
The member predicate can be defined by
member(X, [X | _ ]).
member(X, [ _ | T ]) :- member(X, T).
X is a member of a list whose first element is X.
X is a member of a list whose tail is T if X is a member of T.
member(cat, [dog, cat, mouse]).
member( X, [ X | _ ]). –> fail
member(cat, [cat, mouse]).
member( X, [ X | _ ]). –> succeed
?- member(cat, [dog, cat, mouse]) yes
‹#›
Ch 5
CSE240
11/19/2002
Member Predicate: Other Use
member predicate can be used to print all members:
?- member(X, [dog, cat, mouse]).
X = dog;
X = cat;
X = mouse;
no
?- member(X, [dog, cat, mouse]),
member(X, [cat, tiger, cheetah, dog, horse]).
X = dog;
X = cat;
no
?- member( _, [dog, cat, mouse]). What is output?
‹#›
Ch 5
CSE240
11/19/2002
Find elements paired with a specified element:
?- member([3,Y], [[1,a],[2,m],[3,z],[4,v],[3,p]]).
Y = z ;
Y = p ;
No
Member Predicate: Other Use
Finding elements of a list which satisfy certain constraint:
?- member(X,[23,25,67,12,25,19,9,6]), Y is X*X, Y<400.
X = 12, Y = 144;
X = 19, Y = 361;
X = 9, Y = 81 ;
X = 6, Y = 36 ;
No
‹#›
Ch 5
CSE240
11/19/2002
Knapsack Problem
Knapsack problem:
Given n objects i = 1, 2, …, n; and a "knapsack".
Item i weighs wi > 0 lb and has value vi > 0.
The knapsack has capacity of W lb.
Goal: fill knapsack so as to maximize the total value.
Example: Weight limit W = 11
Greedy algorithm:
Repeatedly add the item with maximum ratio vi / wi.
Example: { 5, 2, 1 } achieves the value = 35
Is the greedy algorithm optimal?
Optimal Solution {3, 4} with value 40.
Item Value Weight Ratio
1 1 1 1
2 6 2 3
3 18 5 3.6
4 22 6 3.67
5 28 7 4
‹#›
Ch 5
CSE240
11/19/2002
Knapsack Problem: Given a set of items, with integer weights & values. Find item set within weight limit and highest value.
Change for a Dollar: You go to bank and ask for breaking a dollar into coins.
How many possibilities (combinations) of coins you can have? Problem Definition / Specification:
Half dollars
Quarters
Dimes
Nickels
Pennies
The sum of all coins = 100
Knapsack Problem for Combination Optimization
How to solve this problem in C/C++? CSE310
0, 1, 2
0, 1, 2, 3, 4
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
0, 1, 2, 3, 4, …, 20
0, 1, 2, 3, 4, …, 100
How do you solve this problem in Prolog?
‹#›
Ch 5
CSE240
11/19/2002
Change for a dollar
This simple Prolog program checks or generates change adding up to a dollar consisting of half-dollars, quarters, dimes, nickels, and pennies.
change(H, Q, D, N, P) :-
member(H,[0,1,2]), % Half-dollars member(Q,[0,1,2,3,4]), % quarters member(D,[0,1,2,3,4,5,6,7,8,9,10]) , % dimes member(N,[0,1,2,3,4,5,6,7,8,9,10,11,12,13, 14,15,16,17,18,19,20]), % nickels
S is 50*H + 25*Q +10*D + 5*N,
S =< 100,
P is 100-S.
Member Predicate: Example
‹#›
Ch 5
CSE240
11/19/2002
Several kinds of goals are possible:
?- change(H,Q,D,N,P).
...
will list all possible ways of giving change for a dollar
?- change(0,2,3,4,6).
no
since 2 quarters, 3 dimes, 4 nickels, and 6 pennies does not make a dollar.
?- change(0,2,3,2,P).
P=10
?- change(1, 1, 2, N, P).
N = 0, P = 5 ;
N = 1, P = 0 ;
no
Member Predicate: Example (contd.)
‹#›
Ch 5
CSE240
11/19/2002