Syntax of Prolog ---------------- (I) Terms represent data objects. There are 3 types of terms: (a) Atoms: symbolic atoms begin with lower-case letter ex. tom, bill, a1 numeric atoms ex. 217, -32, 2.76 (b) Variables: begin with upper-case letter or underscore ex. X, U, _x1, Tom, A1 (c) Structures: two types: function structure: f(t1, ..., tn) list structure: [t1, ..., tn] where f is a symbolic atom called functor and t1, ..., tn are terms ex. edge(3,7), f(g(1),h(2,3)) [a,b,c], [tom,X,f(tom)], [], [[a],[b]] Special Notation for lists: [c1, ..., cm|T] where c1, ..., cm are the first m elements of the list and T is a LIST of the remaining elements (II) Relation: r(t1, ..., tn) where r is a symbolic atom and t1, ..., tn are terms. ex. round, father(tom,bill), student(1111,jones,freshman,4.0) (III) A Prolog Program consists of a finite number of Facts and Rules, where Fact: relation. Rule: relation :- relation-1, ..., relation-n. (IV) Query: ?- relation-1, ..., relation-n. used to invoke a program. SAMPLE PROLOG PROGRAMS: ----------------------- Ancestor program ---------------- ancestor(X,Y) :- parent(X,Y). ancestor(X,Y) :- parent(X,Z), ancestor(Z,Y). List manipulation programs -------------------------- member(X,[X|_]). member(X,[_|Y]) :- member(X,Y). append([],L,L). append([A|X],Y,[A|Z]) :- append(X,Y,Z). prefix(P,L) :- append(P,_,L). suffix(S,L) :- append(_,S,L). sublist(S,L) :- prefix(S,L). sublist(S,[_|R]) :- sublist(S,R). remove_contiguous([],[]). remove_contiguous([X,X|L],R) :- remove_contiguous([X|L],R). remove_contiguous([X|L],[X|R]) :- remove_contiguous(L,R). reverse([],[]). reverse([H|L],R) :- reverse(L,L1), append(L1,[H],R). palindrome(L) :- reverse(L,L). minmax(X,X,[X]). minmax(Min,Max,[X|L]) :- minmax(Min2,Max2,L), min(X,Min2,Min), max(X,Max2,Max). min(X,Y,X) :- X =< Y. min(X,Y,Y) :- Y =< X. max(X,Y,X) :- Y =< X. max(X,Y,Y) :- X =< Y. Replacing non-tail recursion with tail-recursion -------------------------------------------------- Pumping technique. ----------------- reverse a list -------------- reverse(L,R) :- reverse1(L,[],R). reverse1([],P,P). reverse1([X|L],P,S) :- reverse1(L,[X|P],S). minmax problem -------------- minmax(X,X,[X]). minmax(Min,Max,[X|L]) :- minmax1(Min,Max,L,X,X). minmax1(Cmin,Cmax,[],Cmin,Cmax). minmax1(Min,Max,[X|L],Cmin,Cmax) :- X =< Cmin, minmax1(Min,Max,L,X,Cmax). minmax1(Min,Max,[X|L],Cmin,Cmax) :- Cmax =< X, minmax1(Min,Max,L,Cmin,X). minmax1(Min,Max,[X|L],Cmin,Cmax) :- minmax1(Min,Max,L,Cmin,Cmax). Manipulating numbers --------------------- V is Expression factorial --------- factorial(0,1). factorial(N,Nfac) :- N >= 1, M is N-1, factorial(M,Mfac), Nfac is N * Mfac. Delete an element from a list ----------------------------- del(X,[X|Tail],Tail). del(X,[Y|Tail],[Y|Tail1]) :- del(X,Tail,Tail1). Generate all subsets of a set ----------------------------- subset([],[]). subset(S,SS) :- del(X,S,Y), subset(Y,SS). subset(S,[X|Z]) :- del(X,S,Y), subset(Y,Z). Permutations of a list ---------------------- permute([],[]). permute(L,[X|P]) :- del(X,L,L1), permute(L1,P). Given two equal sized lists, generate all possible pairings ----------------------------------------------------------- generate(L1,L2,Pairs) :- permute(L2,M2), combine(L1,M2,Pairs). combine([],[],[]). combine([H1|T1],[H2|T2],[[H1,H2]|T]) :- combine(T1,T2,T). Quick Sort ---------- qsort([],[]). qsort([H|T],S) :- qsplit(H,T,A,B), qsort(A,A1), qsort(B,B1), append(A1,[H|B1],S). qsplit(H,[A|X],[A|Y],Z) :- A =< H, qsplit(H,X,Y,Z). qsplit(H,[A|X],Y,[A|Z]) :- A > H, qsplit(H,X,Y,Z). qsplit(_,[],[],[]). Merge Sort ---------- mergesort([],[]) :- !. mergesort([X],[X]) :- !. mergesort(X,Z) :- msplit(X,L1,L2), mergesort(L1,M1), mergesort(L2,M2), merge(M1,M2,Z). msplit([],[],[]) :- !. msplit([X],[X],[]) :- !. msplit([X,Y|Z],[X|L1],[Y|L2]) :- msplit(Z,L1,L2). merge([],X,X) :- !. merge(X,[],X) :- !. merge([X|L],[Y|M],[X|N]) :- X @=< Y, !, merge(L,[Y|M],N). merge([X|L],[Y|M],[Y|N]) :- Y @=< X, merge([X|L],M,N). A LOGIC PUZZLE -------------- Three friends came first, second and third in a programming contest. Each of the three had a different first name, liked a different sport, and had a different nationality. Following are some clues: - Michael likes basketball and did better than the American. - Simon, the Israeli, did better than the tennis player. - The cricket player came first. Who is the Australian? What sport does Richard play? did_better(A,B,[A,B,C]). did_better(A,C,[A,B,C]). did_better(B,C,[A,B,C]). name_of(person(A,B,C),A). nationality(person(A,B,C),B). sport(person(A,B,C),C). first([X|Xs],X). member(X,[X|_]). member(X,[_|L]) :- member(X,L). friends(0,[]) :- !. friends(N,[person(Name,Nat,Sport)|List]) :- M is N-1, friends(M, List). answer(Aussie,Richards_Sport) :- friends(3,Friends), did_better(M1,M2,Friends), % First Clue name_of(M1,michael), sport(M1,basketball), nationality(M2,american), did_better(M3,M4,Friends), % Second Clue name_of(M3,simon), nationality(M3,israeli), sport(M4,tennis), first(Friends,M5), % Third Clue sport(M5,cricket), member(Q1,Friends), % First Question name_of(Q1,Aussie), nationality(Q1,australian), member(Q2,Friends), % Second Question name_of(Q2,richard), sport(Q2,Richards_Sport).