CS 342 Principles of Programming Languages Homework 9
Homework Solutions: Logic Programming
Learning Objectives:
1. Problem solving using logic programming paradigm
2. Prolog programming
Instructions:
• Total points 36 pt
• Early deadline: Apr 21 (Wed) at 11:59 PM; Regular deadline: Apr 23 (Fri) at 11:59 PM (or till TAs
start grading the homework)
• Download and install Swi-prolog http://www.swi-prolog.org/
• Please zip .pl files and output files (e.g., screenshot) for all the solutions and submit it to Canvas.
Questions:
1. (3 pt) Understand the following Prolog program:
Given:
mystery([ ], [ ]).
mystery([H|Tail], [H,H|DTail]) : −
mystery(Tail,Dtail).
What would Z be in mystery([1, 4, 6], Z).
Sol: Z = [1, 1, 4, 4, 6, 6]
2. (10 pt) Prolog programming:
• (4 pt) [Prolog for numbers] Compute GCD of two numbers.
Example:
1 ?- gcd(10,6,X).
2 2.
3 ?- gcd(10,5,X).
4 5.
Sol:
1 gcd(0, A, A):- A > 0, !.
2 gcd(A, B, Z):- A >= B, X is A-B, gcd(X,B,Z).
3 gcd(A, B, Z):- A < B, X is B-A, gcd(X,A,Z). Spring 2021 page 1 of 5 CS 342 Principles of Programming Languages Homework 9 • (6 pt) [Prolog for list] Duplicate the elements of a list a given number of times. Example: 1 ?- duplicate ([a,b,c],2,X). 2 X = [a,a,b,b,c,c]. 3 ?- duplicate ([a,b,c],3,X). 4 X = [a,a,a,b,b,b,c,c,c]. Sol: 1 duplicate(L1 ,N,L2) :- duplicate(L1 ,N,L2 ,N). 2 duplicate ([],_,[],_). 3 duplicate ([_|Xs],N,Ys ,0) :- duplicate(Xs ,N,Ys ,N). 4 duplicate ([X|Xs],N,[X|Ys],K) :- K > 0, K1 is K – 1, duplicate ([X|Xs],N,Ys ,K1).
3. (6 pt) [Prolog for integer constraints] Write a Prolog program to generate the integer values of x, y
and z that can satisfy the constraints in the following C program. If no such values can be found,
return false.
1 if (2x == y) {
2 if (y == x+ 10)
3 z = x+y;
4 else
5 z = x-y;
6 }
Sol:
1 mypred(X,Y,Z):-((2*X) =:= Y) -> ((Y =:= (X+10)) -> Z is X+Y; Z is X-Y).
4. (5 pt) [Prolog for logic puzzle] Write a Prolog program to solve the following logic puzzle:
Five people were eating apples, A finished before B, but behind C. D finished before E, but behind B.
What was the finishing order?
Sol:
1 puzzle(Hs):-
2 length(Hs ,5),
3 member(a,Hs),
4 member(b,Hs),
5 member(c,Hs),
6 member(d,Hs),
7 member(e,Hs),
8 order(a,b,Hs), order(c,a, Hs), order(d,e, Hs), order(b,d, Hs).
9
10 order(a,b, Ls):-append(_,[a,b|_], Ls).
11 order(c,a, Ls):-append(_,[c,a|_], Ls).
12 order(d,e, Ls):-append(_,[d,e|_], Ls).
13 order(b,d, Ls):-append(_,[b,d|_], Ls).
Finishing order: Hs = [c, a, b, d, e] ( Query: puzzle(Hs). )
Spring 2021 page 2 of 5
CS 342 Principles of Programming Languages Homework 9
5. (12 pt) [Prolog for parsing] Write a Prolog program for parsing:
(a) (7 pt) Consider the grammar we worked in HW1 below. Write a Prolog program that parses
strings using this grammar. Your program can be used to check if a given sentence can be
generated by the grammar. An example interpreter session is provided below.
Grammar:
• terminals: x, y, z,>,<, 0, 1,+,−,=, if, then, else • non-terminals: S, F,B, T,E,N • start symbol: S • production rules: S → F |T N T F →if B then begin S end |if B then begin S else S end B → (T E T ) T → x|y|z|1|0 E →> | < N → +| − | = Example: 1 2 | ?- sentence ([if ,’(’, x, > , 0,’)’, then , begin , [x, =, 1], end]).
3 | true.
4 | ?-sentence ([if , ’(’, x, >, 0 ,’)’, then , begin ,[x, =, 1] , end , else ,
begin ,[x, =, 0] , end]).
5 | false.
6 | ?sentence ([if , x, > , 0, then , begin , [x, =, 1], end]).
7 | false.
8 | ?- sentence ([if , x, > , 0, then , begin , ’(’,[x, =, 1] ,’)’, end , else ,
(x, =, 0)]).
9 | false.
(b) (3 pt) Write the query to generate all possible sentences that can be derived from the grammar.
Show the screenshot of 3 sentences.
(c) (2 pt) Does the order of the sub-goals in your rules make a difference?
Sol:
(a)
1 sentence ([]).
2 sentence ([A,B,C]):- tntexpr(A,B,C).
3 sentence ([A,B,C,D,E,F,G,H,I,J]):-
4 ifterm(A), openbracket(B), bcond(C,D,E), closebracket(F), thenterm(G), beginterm(
H), sentence(I), endterm(J).
5 sentence ([A,B,C,D,E,F,G,H,I,J,K,L]):-
6 ifterm(A), openbracket(B), bcond(C,D,E), closebracket(F), thenterm(G), beginterm(
H), sentence(I),elseterm(J), sentence(K),endterm(L).
7
8 tntexpr(A,B,C):- t(A), n(B), t(C).
9 bcond(A,B,C):- t(A), e(B), t(C).
Spring 2021 page 3 of 5
CS 342 Principles of Programming Languages Homework 9
10
11 t(x).
12 t(y).
13 t(z).
14 t(1).
15 t(0).
16 n(+).
17 n(-).
18 n(=).
19 e(>).
20 e(<). 21 ifterm(if). 22 thenterm(then). 23 elseterm(else). 24 beginterm(begin). 25 endterm(end). 26 openbracket(’(’). 27 closebracket(’)’). (b) For this particular implementation type in sentence(A). into prolog continue to ask for more solutions until no more backtracking can be done First few solutions: 1 A = [] 2 A = [x, (+), x] 3 A = [x, (+), y] 4 A = [x, (+), z] (c) No. Spring 2021 page 4 of 5