SHARE
TWEET

Prolog Notes

a guest Sep 19th, 2019 116 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. Syntax of Prolog - (courtesy of Dr. Sunderranman)
  2. ----------------
  3.  
  4. (I) Terms represent data objects. There are 3 types of terms:
  5.  
  6.     (a) Atoms: symbolic atoms begin with lower-case letter
  7.                  ex. tom, bill, a1
  8.                numeric atoms
  9.                  ex. 217, -32, 2.76
  10.  
  11.     (b) Variables: begin with upper-case letter or underscore
  12.           ex. X, U, _x1, Tom, A1
  13.  
  14.     (c) Structures: two types:
  15.              function structure: f(t1, ..., tn)
  16.              list structure:      [t1, ..., tn]
  17.  
  18.                   where f is a symbolic atom called functor
  19.                   and t1, ..., tn are terms
  20.  
  21.  
  22.                ex. edge(3,7), f(g(1),h(2,3))
  23.                    [a,b,c], [tom,X,f(tom)], [], [[a],[b]]
  24.          
  25.          Special Notation for lists: [c1, ..., cm|T]
  26.               where c1, ..., cm are the first m elements of the list and
  27.                     T is a LIST of the remaining elements
  28.  
  29. (II) Relation: r(t1, ..., tn)
  30.           where r is a symbolic atom and t1, ..., tn are terms.
  31.  
  32.          ex. round, father(tom,bill), student(1111,jones,freshman,4.0)
  33.  
  34. (III) A Prolog Program consists of a finite number of Facts and Rules,
  35.       where
  36.  
  37.       Fact: relation.
  38.       Rule: relation :- relation-1, ..., relation-n.
  39.  
  40. (IV) Query:    ?- relation-1, ..., relation-n.
  41.  
  42.      used to invoke a program.
  43.  
  44.  
  45.  
  46. SAMPLE PROLOG PROGRAMS:
  47. -----------------------
  48.  
  49.  
  50. Ancestor program
  51. ----------------
  52.  
  53. ancestor(X,Y) :- parent(X,Y).
  54. ancestor(X,Y) :- parent(X,Z), ancestor(Z,Y).
  55.  
  56. List manipulation programs
  57. --------------------------
  58.  
  59. member(X,[X|_]).
  60. member(X,[_|Y]) :- member(X,Y).
  61.  
  62. append([],L,L).
  63. append([A|X],Y,[A|Z]) :- append(X,Y,Z).
  64.  
  65. prefix(P,L) :- append(P,_,L).
  66.  
  67. suffix(S,L) :- append(_,S,L).
  68.  
  69. sublist(S,L) :- prefix(S,L).
  70. sublist(S,[_|R]) :- sublist(S,R).
  71.  
  72. remove_contiguous([],[]).
  73. remove_contiguous([X,X|L],R) :- remove_contiguous([X|L],R).
  74. remove_contiguous([X|L],[X|R]) :- remove_contiguous(L,R).
  75.  
  76. reverse([],[]).
  77. reverse([H|L],R) :- reverse(L,L1), append(L1,[H],R).
  78.  
  79. palindrome(L) :- reverse(L,L).
  80.  
  81. minmax(X,X,[X]).
  82. minmax(Min,Max,[X|L]) :- minmax(Min2,Max2,L),
  83.                          min(X,Min2,Min),
  84.                          max(X,Max2,Max).
  85. min(X,Y,X) :- X =< Y.
  86. min(X,Y,Y) :- Y =< X.
  87. max(X,Y,X) :- Y =< X.
  88. max(X,Y,Y) :- X =< Y.
  89.  
  90. Replacing non-tail recursion with tail-recursion
  91. --------------------------------------------------
  92. Pumping technique.
  93. -----------------
  94.  
  95.      reverse a list
  96.      --------------
  97.  
  98.      reverse(L,R) :- reverse1(L,[],R).
  99.  
  100.      reverse1([],P,P).
  101.      reverse1([X|L],P,S) :- reverse1(L,[X|P],S).
  102.  
  103.  
  104.      minmax problem
  105.      --------------
  106.  
  107.      minmax(X,X,[X]).
  108.      minmax(Min,Max,[X|L]) :- minmax1(Min,Max,L,X,X).
  109.  
  110.      minmax1(Cmin,Cmax,[],Cmin,Cmax).
  111.      minmax1(Min,Max,[X|L],Cmin,Cmax) :- X =< Cmin, minmax1(Min,Max,L,X,Cmax).
  112.      minmax1(Min,Max,[X|L],Cmin,Cmax) :- Cmax =< X, minmax1(Min,Max,L,Cmin,X).
  113.      minmax1(Min,Max,[X|L],Cmin,Cmax) :- minmax1(Min,Max,L,Cmin,Cmax).
  114.  
  115.  
  116. Manipulating numbers
  117. ---------------------
  118.  
  119. V is Expression
  120.  
  121.    factorial
  122.    ---------
  123.      factorial(0,1).
  124.      factorial(N,Nfac) :- N >= 1, M is N-1, factorial(M,Mfac),
  125.                           Nfac is N * Mfac.
  126.  
  127.  
  128.  
  129. Delete an element from a list
  130. -----------------------------
  131.  
  132. del(X,[X|Tail],Tail).
  133. del(X,[Y|Tail],[Y|Tail1]) :- del(X,Tail,Tail1).
  134.  
  135. Generate all subsets of a set
  136. -----------------------------
  137.  
  138. subset([],[]).
  139. subset(S,SS) :- del(X,S,Y), subset(Y,SS).
  140. subset(S,[X|Z]) :- del(X,S,Y), subset(Y,Z).
  141.  
  142. Permutations of a list
  143. ----------------------
  144.  
  145. permute([],[]).
  146. permute(L,[X|P]) :- del(X,L,L1), permute(L1,P).
  147.  
  148. Given two equal sized lists, generate all possible pairings
  149. -----------------------------------------------------------
  150.  
  151. generate(L1,L2,Pairs) :-
  152.         permute(L2,M2),
  153.         combine(L1,M2,Pairs).
  154.  
  155. combine([],[],[]).
  156. combine([H1|T1],[H2|T2],[[H1,H2]|T]) :- combine(T1,T2,T).
  157.  
  158.  
  159. Quick Sort
  160. ----------
  161.  
  162. qsort([],[]).
  163. qsort([H|T],S) :-
  164.   qsplit(H,T,A,B),
  165.   qsort(A,A1),
  166.   qsort(B,B1),
  167.   append(A1,[H|B1],S).
  168.  
  169. qsplit(H,[A|X],[A|Y],Z) :- A =< H, qsplit(H,X,Y,Z).
  170. qsplit(H,[A|X],Y,[A|Z]) :- A > H, qsplit(H,X,Y,Z).
  171. qsplit(_,[],[],[]).
  172.  
  173. Merge Sort
  174. ----------
  175.  
  176. mergesort([],[]) :- !.
  177. mergesort([X],[X]) :- !.
  178. mergesort(X,Z) :- msplit(X,L1,L2),
  179.                   mergesort(L1,M1),
  180.                   mergesort(L2,M2),
  181.                   merge(M1,M2,Z).
  182.  
  183. msplit([],[],[]) :- !.
  184. msplit([X],[X],[]) :- !.
  185. msplit([X,Y|Z],[X|L1],[Y|L2]) :- msplit(Z,L1,L2).
  186.  
  187. merge([],X,X) :- !.
  188. merge(X,[],X) :- !.
  189. merge([X|L],[Y|M],[X|N]) :- X @=< Y, !, merge(L,[Y|M],N).
  190. merge([X|L],[Y|M],[Y|N]) :- Y @=< X, merge([X|L],M,N).
  191.  
  192. A LOGIC PUZZLE
  193. --------------
  194.  
  195. Three friends came first, second and third in a programming contest.
  196. Each of the three had a different first name, liked a different
  197. sport, and had a different nationality. Following are some clues:
  198.  
  199. - Michael likes basketball and did better than the American.
  200. - Simon, the Israeli, did better than the tennis player.
  201. - The cricket player came first.
  202.  
  203. Who is the Australian? What sport does Richard play?
  204.  
  205. did_better(A,B,[A,B,C]).
  206. did_better(A,C,[A,B,C]).
  207. did_better(B,C,[A,B,C]).
  208.  
  209. name_of(person(A,B,C),A).
  210. nationality(person(A,B,C),B).
  211. sport(person(A,B,C),C).
  212.  
  213. first([X|Xs],X).
  214.  
  215. member(X,[X|_]).
  216. member(X,[_|L]) :- member(X,L).
  217.  
  218. friends(0,[]) :- !.
  219. friends(N,[person(Name,Nat,Sport)|List]) :- M is N-1, friends(M, List).
  220.  
  221. answer(Aussie,Richards_Sport) :-
  222.     friends(3,Friends),
  223.  
  224.     did_better(M1,M2,Friends),     % First Clue
  225.     name_of(M1,michael),
  226.     sport(M1,basketball),
  227.     nationality(M2,american),
  228.  
  229.     did_better(M3,M4,Friends),     % Second Clue
  230.     name_of(M3,simon),
  231.     nationality(M3,israeli),
  232.     sport(M4,tennis),
  233.  
  234.     first(Friends,M5),             % Third Clue
  235.     sport(M5,cricket),
  236.  
  237.     member(Q1,Friends),            % First Question
  238.     name_of(Q1,Aussie),
  239.     nationality(Q1,australian),
  240.  
  241.     member(Q2,Friends),            % Second Question
  242.     name_of(Q2,richard),
  243.     sport(Q2,Richards_Sport).
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top