Prolog
This page contains basic beginner and more advanced Prolog snippets; the purpose of this page is for those who are learning and like to learn (via pure code), as well as, a location for mpettersson to keep snippets and Prolog related links. This pages subsections are:
Prolog 101
The general and technical aspects of the Prolog programming language are:
Uses: | Application, AI |
Website: | swi-prolog.org |
Get Started: | Getting started quickly |
Download: | swi-prolog.org/Download |
Documents: | SWI-Prolog documentation |
Creator: | Alain Colmerauer, Robert Kowalski |
First Released: | 1972 |
Implementation: | Both Interpreted and Compiled |
Type Safety: | |
Type System: | |
Type Checking: | Dynamic |
Imperative: | No |
Functional: | Yes |
Procedural: | Yes |
Reflective: | Yes |
Event Driven: | No |
Standardized: | Yes |
Failsafe I/O: | Yes |
Garbage Collected: | Yes |
For a “comprehensive free Prolog environment” download SWI-Prolog from the SWI Prolog download page. For just about everything you’d ever want to know about this particular version of Prolog, check out the SWI Prolog document page.
The following code snippet contains the instructions necessary to load a Prolog (.pl) file, furthermore, please note that the symbols ‘?-‘ simply represent (or indicate) the Prolog interpreter.
1 2 3 4 5 6 7 8 9 10 11 12 |
?- true. % A comment. true. ?- help(help). % Open SWI-Prolog help. true. ?- ['/Path/To/A/File.pl']. % How to load a file. % /Path/To/A/File.pl compiled 0.00 sec, 3 clauses true. ?- factorial(0,A). A = 1 . ?- factorial(0,a). false. ?- halt. % Exit or return to OS. |
The contents of the File.pl Prolog file:
1 2 |
factorial(0,1). factorial(A,B) :- A > 0, C is A-1, factorial(C,D), B is A*D. |
Miscellaneous Prolog Code
The following code is a collection of interesting Prolog code (well, at least from the perspective of an imperative programmer).
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 |
num(s(X)) :- num(X). logical_plus(0, Y, Y). logical_plus(s(X),Y,s(Z)) :- logical_plus(X,Y,Z). logical_times(0, _, 0). logical_times(s(X),Y,Z) :- logical_plus(Y,A,Z), logical_times(X,Y,A). logical_gt(s(X),0). logical_gt(s(X),s(Y)) :- logical_gt(X,Y). fibonacci(0,0). fibonacci(s(0),s(0)). fibonacci(s(s(X)),Y) :- fibonacci(X,F1), fibonacci(s(X)),F2), logical_plus(F1,F2,Y). fac(0,s(0)). fac(s(X),Y) :- fac(X,Z), logical_times(s(X),Z,Y). is_prime(2). is_prime(3). is_prime(P) :- integer(P), P > 3, P mod 2 =\= 0, \+ has_factor(P,3). has_factor(N,L) :- N mod L =:= 0. has_factor(N,L) :- L*L<N,has_factor(N,L+2). member(X, [X|_]). member(X, [_|T]) :-member(X, T). notmemberof(_, []). notmemberof(X, [Y|T]) :- X \== Y, notmemberof(X, T). count_members(X,[],0). count_members(X,[X|L],N1) :- count_members(X,L,N), N1 is N + 1. count_members(X,[Y|L],N) :- not Y=X, count_members(X,L,N). add_member(X,S,S) :- member(X,S), !. members add_member(X,S,[X|S]). remove_member(X,[],[]). remove_member(X,[X|L],L). remove_member(X,[Y|L],[Y|Res]) :- not Y=X, remove_member(X,L,Res). remove_members(X,[],[]). remove_members(X,[X|L],Res) :- !, remove_members(X,L,Res). remove_members(X,[Y|L],[Y|Res]) :- remove_members(X,L,Res). remove_list([],L,L). remove_list([X|Rest],Lold,Lnew) :- remove_member(X,Lold,Lx), remove_list(Rest,Lx,Lnew). prefixmem(X,[X|_],_). prefixmem(X,[_|T2],[_|T3]) :- prefixmem(X,T2,T3). prefixdel(X,[X|T],_,T). prefixdel(X,[H|T1],[_|T2],[H|T3]) :- X \= H, prefixdel(X,T1,T2,T3). append([H|T],L,[H|Z]) :-append(T,L,Z). naive_rev([],[]). naive_rev([H|T],R) :- naive_rev(T,T1), append(T1,[H],R). prefix(L1,L2) :- append(L1,_,L2). suffix(L1,L2) :- append(_,L1,L2). union([], [], []). union(X, Y, [H|T]) :- (prefixmem(H, X,T) ; prefixmem(H, Y, T)), prefixdel(H,X,T,X2), prefixdel(H,Y,T,Y2), union(X2,Y2,T). intersection(X, Y, Z) :- setdiff(X,Y,XC), setdiff(X,XC,Z). setdiff([],_[]). setdiff([H|T],Y,Z) :- prefixmem(H,Y,Y) -> (prefixdel(H,Y,Y,Y2), setdiff(T,Y2,Z)) ; (prefixmem(H,Z,T), prefixdel(H,Z,T,Z2), setdiff(T,Y,Z2)). subset(X,Y) :- setdiff(X,Y,[]). sameset(S1,S2) :- subset(S1,S2), subset(S2,S1). sumlist(L,Sum) :- sumlist2(L,0,Sum). sumlist2([],Sum,Sum). sumlist2([N|L],S1,Sum) :- S2 is S1 + N, sumlist2(L,S2,Sum). % The sumlists Function, adds each of the heads to the return value, then recursivly calls the tail of the list. sumlists([], [], [], []). sumlists([H|T], [], [], [H|T]). sumlists([], [H|T], [], [H|T]). sumlists([], [], [H|T], [H|T]). sumlists([],[H2|T2],[H3|T3], [H4|T4]) :- H4 is H2 + H3, sumlists(T1, T2, T3, T4). sumlists([H1|T1],[],[H3|T3], [H4|T4]) :- H4 is H1 + H3, sumlists(T1, T2, T3, T4). sumlists([H1|T1],[H2|T2],[], [H4|T4]) :- H4 is H1 + H2, sumlists(T1, T2, T3, T4). sumlists([H1|T1],[H2|T2],[H3|T3], [H4|T4]) :- H4 is H1 + H2 + H3, sumlists(T1, T2, T3, T4). sum_alt([],0). sum_alt([H|T],S) :- sum_alt(T,S1), S is H + S1. maxlist([N|L],Max) :- maxlist2(L,N,Max). maxlist2([],Max,Max). maxlist2([N|L],M1,Max) :- domax(N,M1,M2), maxlist2(L,M2,Max). domax(N,M,N) :- N > M, !. domax(N,M,M) :- N =< M. range_list(Lo,Hi,[]) :- Lo > Hi, !. range_list(Lo,Hi,[Lo|Rest]) :- Lo1 is Lo + 1, range_list(Lo1,Hi,Rest). kth(1,[H|_],H). kth(K,[_|T],V) :- K1 is K-1, kth(K1,T,V). rotatel(L,0,L). rotatel([H|T],s(N),X) :- append(T,[H],Z), rotatel(Z,N,X). append([],L,L). lin_reverse(L,RL) :- lin_rev(L,[],RL). lin_rev([],RL,RL). lin_rev([H|T],X,Y) :- lin_rev(T,[H|X],Y). pal(L) :- reverse(L,L). delete(X,[X|T],T). %% Select Funt ≡ Delete Funt %% delete(X,[Y|T],[Y|R]) :- delete(X,T,R). permute([],[]). permute(L,[X|R]) :- delete(X,L,T), permute(T,R). concat([],L,L). concat([X|A],B,[X|L]) :- concat(A,B,L). length([],0). length([X|L],N1) :- nonvar(N1), !, N1 > 0, N is N1 - 1, length(L,N). length([X|L],N1) :- length(L,N), N1 is N + 1. hanoi(N) :- move(N, left, right, center). move(0,_,_,_) :- !. move(N,A,B,C) :- M is N - 1, move(M,A,C,B), inform(A,B), move(M,C,B,A). inform(X,Y) :- write('move a disc from the '), write(X), write(' pole to the '), write(Y),write(' pole.'), nl. %% SOLVED (# represented by char: A + B = C) %% solve(L1,L2,L3) :- lin_reverse(L1,RL1), lin_reverse(L2,RL2), lin_reverse(L3,RL3), solve(RL1,RL2,RL3,[0,1,2,3,4,5,6,7,8,9],0). solve([],[],[],_,0). solve([],[],[V3|T3],D,C) :- (var(V3) -> V3 is C, delete(V3,D,D1) ; V3 is C, D1 = D), solve([],[],T3,D1,0). solve([V1|T1], [V2|T2], [V3|T3], D, C) :- assign(V1, D, D1),assign(V2,D1,D2),TDisV1+V2+C,C1isTD// 10, (var(V3) -> V3 is TD mod 10, delete(V3, D2, D3) ; V3 is TD mod 10, D3 = D2), solve(T1, T2, T3, D3, C1). assign(X,List,Remain) :- var(X), delete(X,List,Remain). assign(X,List,List) :- nonvar(X). edge(a,b). edge(b,d). edge(c,a). tedge(Node1,Node2) :- edge (Node1,SomeNode), edge(SomeNode,Node2). path(Node1,Node2) :- edge(Node1,Node2). path(Node1,Node2) :- edge(Node1,SomeNode), path(SomeNode,Node2). node(nil). node(_,Left,Right):- node(Left), node(Right). sbt_member(X,node(X,_,_)). sbt_member(X,node(N,S,_)):- X < N, sbt_member(X,S). sbt_member(X,node(N,_,T)):- X > T, sbt_member(X,T). insert(X,nil,node(X,nil,nil)). insert(X,node(X,L,R),node(X,L,R)):-!. insert(X,node(Y,L,R),node(Y,NL,R)):- X < Y, insert(X,L,NL). insert(X,node(Y,L,R),node(Y,L,NR)):-insert(X,R,NR). predecessor(node(P,L,nil),P,L):-!. predecessor(node(K,L,R),P,node(K,L,NR)):- predecessor(R,P,NR). delete(K,node(K,nil,R),R):-!. delete(K,node(K,L,R),node(P,NL,R)):-!, predecessor(L,P,NL). delete(K,node(X,L,R),node(X,NL,R)):- K<X, !, delete(K,L,NL). delete(K,node(X,L,R),node(X,L,NR)):- delete(X,R,NR). bubblesort( List, Sorted ) :- swap( List, List1), !, bubblesort( List1, Sorted). %% BUBBLE SORT %% bubblesort( Sorted, Sorted ). swap( [X,Y | Rest] , [Y,X | Rest] ) :- gt(X,Y). swap( [Z|Rest], [Z|Rest1] ) :- swap( Rest, Rest1). gt(X,Y) :- X > Y. insertsort( [] , [] ). insertsort( [X|Tail] , Sorted ) :- insertsort(Tail, SortedTail ), insert(X, SortedTail, Sorted). insert(X , [Y|Tail] , [Y|Tail1]) :- X > Y, !, insert(X, Tail, Tail1). insert(X , Tail , [X|Tail]). merge_sort([], []). %% MERGE SORT %% merge_sort([X],[X]). merge_sort([O,E|Xs], Ys) :- split([O,E|Xs], O1, E1), merge_sort(O1, Os), merge_sort(E1, Es), merge(Os, Es, Ys). split([], [], []). split([X|Xs], [X|Os], Es) :- split(Xs, Es, Os). merge([], Ys, Ys). merge([X|Xs], [], [X|Xs]). merge([X|Xs], [Y|Ys], [X|Zs]) :- X < Y, merge(Xs, [Y|Ys], Zs). merge([X|Xs], [Y|Ys], [Y|Zs]) :- X >= Y, merge([X|Xs], Ys, Zs). quick_sort([],[]). quick_sort([H|T],Sorted) :- pivoting(H,T,L1,L2), quick_sort(L1,Sorted1), quick_sort(L2,Sorted2), append(Sorted1,[H|Sorted2]). pivoting(H,[],[],[]). pivoting(H,[X|T],[X|L],G) :- X =< H, pivoting(H,T,L,G). pivoting(H,[X|T],L,[X|G]) :- X > H, pivoting(H,T,L,G). quick_sort2(List,Sorted) :- q_sort(List,[],Sorted). q_sort([],Acc,Acc). q_sort([H|T],Acc,Sorted) :- pivoting(H,T,L1,L2), q_sort(L1,Acc,Sorted1), q_sort(L2,[H|Sorted1],Sorted). |
Binary Digits in Prolog
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
% The Language of Binary Digits b(tb(D)) --> d(D). b(tb(D,B)) --> d(D), b(B). d(0) --> [0]. d(1) --> [1]. % Semantics. sem_d(0, 0). sem_d(1, 1). sem_b(tb(D), X) :- sem_d(D,X). sem_b(tb(D,B), X) :- sem_b(B,A1), sem_d(D,A2), accum(B, Pos), A3 is 2 ** Pos, A4 is A2 * A3, X is A1 + A4. % Accumulator (this was needed for right recursion) accum(0,0). accum(1,0). accum(tb(_), 1). accum(tb(_,B), X) :- accum(B, Y), X is 1 + Y. main(L,X) :- b(Y,L,[]), sem_b(Y,X). |
Prolog Resources
The following are links to Prolog related resources, such as books, blogs, tutorials, code, etc…
Logic, Programming and Prolog (2ed) by Ulf Nilsson and Jan Maluszynski
Prolog & Logic Programming Slides by Dr. Hamlen at UTD (my favorite professor at UTD).
Prolog Tutorial by J. R. Fisher
As always, please contact us with comments, concerns, questions, etc. about Prolog!