University of Toronto
Department of Computer Science
CSC324 - Principles of Programming Languages
Spring 1998 John Mylopoulos
Programming in Prolog: Tutorial Notes 5
Prepared by Thodoros Topaloglou
/*
*
* 12. Parsing.
* ----------
*/
/* Write a logic program that succeeds iff its input string is generated */
/* by the grammar G=({S,A,B}, {a,b}, P,S) where P includes the productions */
/* */
/* S ->aaB
A ->bA
*/
/* S ->bA B ->b */
/* A ->a B ->bB
*/
/* A ->aA B ->aB */
s(L):-append([a,a], X, L), bb(X).
s(L):-append([b],X,L),aa(X).
bb(X):- X=[b].
bb(X):- X=[a|Y], bb(Y).
bb(X):- X=[b|Y], bb(Y).
aa(X):- X=[a].
aa(X):- X=[a|Y], aa(Y).
aa(X):- X=[b|Y], aa(Y).
append([],Y,Y).
append([E|X],Y,[E|Z]):-append(X,Y,Z).
/*
*
* 4. More List Processing -- declarative style
* --------------------------------------------
*/
/* Define a predicate double(list1,list2) such that list1 and list2 are */
/* lists and list2 consists of the reverse of list1 appended to list1
*/
double(L1,L2):-
d_help(L1,[],R),
d_help(R,R,L2).
d_help([], Result, Result).
d_help([Head|Tail],Temp, Result):-
d_help(Tail, [Head|Temp], Result).
/* examples:
*/
/* */
/*
?-double([1,2,3],X). */
/* X =
[1,2,3,3,2,1] */
/* yes
*/
/* */
/*
?-double([1,[2,3],4],X). */
/* X =
[1,[2,3],4,4,[2,3],1] */
/* yes
*/
/*
* extend double/2 so that it can handle lists of lists
*/
double1(L1,L2):-
help1(L1,[],R),
help1(R,R,L2).
help1([Head|Tail],Temp, Result):-
structured(Head, New),
help1(Tail, [New|Temp], Result).
help1([], Result, Result).
structured(A,A):-
atomic(A).
structured(List,NewL):-
isList(List),
help1(List,[],NewL). /* reverses */
/* ?-double1([1,[2,3],4],X). */
/* X = [1,[2,3],4,4,[3,2],1]
*/
/* yes */
isList([]).
isList([H|T]):-isList(T).
/* double/2 : reverses a list and appends it to itself */
/* agr1 : is the input list, must be ground
*/
/* arg2 : is the output list */
/*
*/
/* double/2 calls the help predicate double_help/3 twice, */
/* the first call reverses List1 and leaves the result to var R, */
/* the second call reverses R again and places it in front of itself */
/* */
/* example: */
/* */
/* ?-double([1,2,3],X). */
/* X = [1,2,3,3,2,1] */
/* yes */
/* */
/* limitations: double/2 operates on the top level list, i.e., does not */
/* apply its effects on the sublists of the list. For example: */
/* */
/* ?-double([1,[2,3],4],X).
*/
/* X = [1,[2,3],4,4,[2,3],1] */
/* yes */
double(List1,List2):-
double_help(List1,[],R),
double_help(R,R,List2).
/* double_help(arg1, arg2, arg3) */
/* arg1: mode: input, type: ground list
*/
/* arg2: mode: input, type: ground list */
/* arg3: mode: output, type: list
*/
/* arg3 is a list consisting of a reverved copy of arg1 appended */
/* with arg2 */
/* used in double/2
*/
double_help([], Result, Result).
double_help([Head|Tail],Temp, Result):-
double_help(Tail, [Head|Temp], Result).
/*
traces
------
*/
| ?- flatten([[2],[3]],X).
(1) 1 Call: flatten([[2],[3]],_13) ?
(2) 2 Call: flatten([2],_65636) ?
(3) 3 Call: flatten(2,_65647) ?
(3) 3 Exit: flatten(2,[2])
(5) 3 Call: flatten([],_65648) ?
(5) 3 Exit: flatten([],[])
(2) 2 Exit: flatten([2],[2])
(9) 2 Call: flatten([[3]],_65637) ?
(10) 3 Call: flatten([3],_65699) ?
(11) 4 Call: flatten(3,_65710) ?
(11) 4 Exit: flatten(3,[3])
(13) 4 Call: flatten([],_65711) ?
(13) 4 Exit: flatten([],[])
(10) 3 Exit: flatten([3],[3])
(17) 3 Call: flatten([],_65700) ?
(17) 3 Exit: flatten([],[])
(9) 2 Exit: flatten([[3]],[3])
(1) 1 Exit: flatten([[2],[3]],[2,3])
X = [2,3]
yes
| ?- flatten([2,[3,[4]],1], X).
1 Call: flatten([2,[3,[4]],1],_15) ?
2 Call: flatten(2,_65636) ?
3 Call: 2\==[] ?
3 Exit: 2\==[]
2 Exit: flatten(2,[2])
2 Call: flatten([[3,[4]],1],_65637) ?
3 Call: flatten([3,[4]],_65663) ?
4 Call: flatten(3,_65674) ?
5 Call: 3\==[] ?
5 Exit: 3\==[]
4 Exit: flatten(3,[3])
4 Call: flatten([[4]],_65675) ?
5 Call: flatten([4],_65701) ?
6 Call: flatten(4,_65712) ?
7 Call: 4\==[] ?
7 Exit: 4\==[]
6 Exit: flatten(4,[4])
6 Call: flatten([],_65713) ?
7 Call: []\==[] ?
7 Fail: []\==[]
6 Exit: flatten([],[])
6 Call: append([4],[],_65701) ?
6 Exit: append([4],[],[4])
5 Exit: flatten([4],[4])
5 Call: flatten([],_65702) ?
6 Call: []\==[] ?
6 Fail: []\==[]
5 Exit: flatten([],[])
5 Call: append([4],[],_65675) ?
5 Exit: append([4],[],[4])
4 Exit: flatten([[4]],[4])
4 Call: append([3],[4],_65663) ?
3 Exit: flatten([3,[4]],[3,4])
3 Call: flatten([1],_65664) ?
4 Call: flatten(1,_65806) ?
5 Call: 1\==[] ?
5 Exit: 1\==[]
4 Exit: flatten(1,[1])
4 Call: flatten([],_65807) ?
5 Call: []\==[] ?
5 Fail: []\==[]
4 Exit: flatten([],[])
4 Call: append([1],[],_65664) ?
4 Exit: append([1],[],[1])
3 Exit: flatten([1],[1])
3 Call: append([3,4],[1],_65637) ?
3 Exit: append([3,4],[1],[3,4,1])
2 Exit: flatten([[3,[4]],1],[3,4,1])
2 Call: append([2],[3,4,1],_15) ?
2 Exit: append([2],[3,4,1],[2,3,4,1])
1 Exit: flatten([2,[3,[4]],1],[2,3,4,1])
X = [2,3,4,1]
yes
| ?- factorial2(3,X).
(1) 1 Call: factorial2(3,_0) ?
(2) 2 Call: 3>0 ?
(2) 2 Exit: 3>0
(3) 2 Call: _65636 is 3-1 ?
(3) 2 Exit: 2 is 3-1
(4) 2 Call: factorial2(2,_6) ?
(5) 3 Call: 2>0 ?
(5) 3 Exit: 2>0
(6) 3 Call: _65662 is 2-1 ?
(6) 3 Exit: 1 is 2-1
(7) 3 Call: factorial2(1,_10) ?
(8) 4 Call: 1>0 ?
(8) 4 Exit: 1>0
(9) 4 Call: _65688 is 1-1 ?
(9) 4 Exit: 0 is 1-1
(10) 4 Call: factorial2(0,_14) ?
(10) 4 Exit: factorial2(0,1)
(11) 4 Call: _10 is 1*1 ?
(11) 4 Exit: 1 is 1*1
(7) 3 Exit: factorial2(1,1)
(12) 3 Call: _6 is 2*1 ?
(12) 3 Exit: 2 is 2*1
(4) 2 Exit: factorial2(2,2)
(13) 2 Call: _0 is 3*2 ?
(13) 2 Exit: 6 is 3*2
(1) 1 Exit: factorial2(3,6)
X = 6
yes
| ?- factorial3(3,X).
(1) 1 Call: factorial3(3,_0) ?
(2) 2 Call: factorial3(0,3,1,_0) ?
(3) 3 Call: 0<3 ?
(3) 3 Exit: 0<3
(4) 3 Call: _7 is 0+1 ?
(4) 3 Exit: 1 is 0+1
(5) 3 Call: _65647 is 1*1 ?
(5) 3 Exit: 1 is 1*1
(6) 3 Call: factorial3(1,3,1,_0) ?
(7) 4 Call: 1<3 ?
(7) 4 Exit: 1<3
(8) 4 Call: _14 is 1+1 ?
(8) 4 Exit: 2 is 1+1
(9) 4 Call: _65682 is 1*2 ?
(9) 4 Exit: 2 is 1*2
(10) 4 Call: factorial3(2,3,2,_0) ?
(11) 5 Call: 2<3 ?
(11) 5 Exit: 2<3
(12) 5 Call: _21 is 2+1 ?
(12) 5 Exit: 3 is 2+1
(13) 5 Call: _65717 is 2*3 ?
(13) 5 Exit: 6 is 2*3
(14) 5 Call: factorial3(3,3,6,_0) ?
(14) 5 Exit: factorial3(3,3,6,6)
(10) 4 Exit: factorial3(2,3,2,6)
(6) 3 Exit: factorial3(1,3,1,6)
(2) 2 Exit: factorial3(0,3,1,6)
(1) 1 Exit: factorial3(3,6)
X = 6
yes
| ?- factorial4(3,X).
(1) 1 Call: factorial4(3,_0) ?
(2) 2 Call: factorial4(3,1,_0) ?
(3) 3 Call: 3>0 ?
(3) 3 Exit: 3>0
(4) 3 Call: _65646 is 1*3 ?
(4) 3 Exit: 3 is 1*3
(5) 3 Call: _65647 is 3-1 ?
(5) 3 Exit: 2 is 3-1
(6) 3 Call: factorial4(2,3,_0) ?
(7) 4 Call: 2>0 ?
(7) 4 Exit: 2>0
(8) 4 Call: _65681 is 3*2 ?
(8) 4 Exit: 6 is 3*2
(9) 4 Call: _65682 is 2-1 ?
(9) 4 Exit: 1 is 2-1
(10) 4 Call: factorial4(1,6,_0) ?
(11) 5 Call: 1>0 ?
(11) 5 Exit: 1>0
(12) 5 Call: _65716 is 6*1 ?
(12) 5 Exit: 6 is 6*1
(13) 5 Call: _65717 is 1-1 ?
(13) 5 Exit: 0 is 1-1
(14) 5 Call: factorial4(0,6,_0) ?
(14) 5 Exit: factorial4(0,6,6)
(10) 4 Exit: factorial4(1,6,6)
(6) 3 Exit: factorial4(2,3,6)
(2) 2 Exit: factorial4(3,1,6)
(1) 1 Exit: factorial4(3,6)
X = 6
yes