Prolog was conceived in 1971 as a tool to process natural language (French)
Named for “PROgrammation en LOGique”
Influenced by Kowalski
“Logic programming shares with mechanical theorem proving the use of logic to represent knowledge and the use of deduction to solve problems by deriving logical consequences.”
Prolog represents facts and rules as Horn Clauses
Head :- Body.
Can be read as “Head is true if Body is true”.
Facts are represented with an empty body, for example
cat(tom).
which is equivalent to
cat(tom) :- true.
Once facts have been loaded, the system can be queried.
Is Tom a cat?
| ?- cat(tom). Yes
What things are cats?
| ?- cat(X). X = tom
A rule’s body consists of goals, for example:
animal(X) :- cat(X).
What things are animals?
| ?- animal(X). X = tom
A semicolon (;) is used to specify a disjunction. The head is true if either of the clauses in the body can be satisfied.
dog(fido). animal(X) :- cat(X) ; dog(X).
When querying the system interactively ‘;’ will instruct the system to advance beyond the choice point and look for new solutions.
| ?- animal(X). X = tom ? ; X = fido
Using ‘;’ to combine goals is the same as repeating the head:
dog(fido). animal(X) :- cat(X). animal(X) :- dog(X).
Most rules will combine goals with conjunction using the comma (,) operator:
lapdog(X) :- small(X), dog(X), irritating(X).
Prolog uses an algorithm called unification to match terms and to bind variables to terms.
fido, fido — yes
X, fido — yes, X bound to fido
X, Y — yes, X bound to Y
parent(A, B), parent(X, Y) — can unify if A can be unified with X and B can be unified with Y
father(azai, bustan). father(bustan, clopas). parent(X,Y) :- father(X,Y); mother(X,Y). grandparent(X,Z) :- parent(X, Y), parent(Y, Z).
| ?- grandparent(X,Y). grandparent(X,Y). X = azai Y = clopas ? yes | ?-
| ?- grandparent(X,Y). grandparent(X,Y). 1 1 Call: grandparent(_16,_17) ? 2 2 Call: parent(_16,_95) ? 3 3 Call: father(_16,_119) ? 3 3 Exit: father(azai,bustan) ? 2 2 Exit: parent(azai,bustan) ? 4 2 Call: parent(bustan,_17) ? 5 3 Call: father(bustan,_17) ? 5 3 Exit: father(bustan,clopas) ? 4 2 Exit: parent(bustan,clopas) ? 1 1 Exit: grandparent(azai,clopas) ? X = azai Y = clopas ? (4 ms) yes {trace} | ?-
father(azai, bustan). father(bustan, clopas). mother(magdala, bustan). parent(X,Y) :- father(X,Y); mother(X,Y). grandparent(X,Z) :- parent(X, Y), parent(Y, Z).
| ?- grandparent(X,Y). grandparent(X,Y). X = azai Y = clopas ? ; ; X = magdala Y = clopas ? yes | ?-
| ?- grandparent(X,Y). grandparent(X,Y). 1 1 Call: grandparent(_16,_17) ? 2 2 Call: parent(_16,_95) ? 3 3 Call: father(_16,_119) ? 3 3 Exit: father(azai,bustan) ? 2 2 Exit: parent(azai,bustan) ? 4 2 Call: parent(bustan,_17) ? 5 3 Call: father(bustan,_17) ? 5 3 Exit: father(bustan,clopas) ? 4 2 Exit: parent(bustan,clopas) ? 1 1 Exit: grandparent(azai,clopas) ? X = azai Y = clopas ? ; ; 1 1 Redo: grandparent(azai,clopas) ? 4 2 Redo: parent(bustan,clopas) ? 5 3 Call: mother(bustan,_17) ? 5 3 Fail: mother(bustan,_17) ? 4 2 Fail: parent(bustan,_17) ? 2 2 Redo: parent(azai,bustan) ? 3 3 Redo: father(azai,bustan) ? 3 3 Exit: father(bustan,clopas) ? 2 2 Exit: parent(bustan,clopas) ? 4 2 Call: parent(clopas,_17) ? 5 3 Call: father(clopas,_17) ? 5 3 Fail: father(clopas,_17) ? 5 3 Call: mother(clopas,_17) ? 5 3 Fail: mother(clopas,_17) ? 4 2 Fail: parent(clopas,_17) ? 2 2 Redo: parent(bustan,clopas) ? 3 3 Call: mother(_16,_119) ? 3 3 Exit: mother(magdala,bustan) ? 2 2 Exit: parent(magdala,bustan) ? 4 2 Call: parent(bustan,_17) ? 5 3 Call: father(bustan,_17) ? 5 3 Exit: father(bustan,clopas) ? 4 2 Exit: parent(bustan,clopas) ? 1 1 Exit: grandparent(magdala,clopas) ? X = magdala Y = clopas ? ; ; 1 1 Redo: grandparent(magdala,clopas) ? 4 2 Redo: parent(bustan,clopas) ? 5 3 Call: mother(bustan,_17) ? 5 3 Fail: mother(bustan,_17) ? 4 2 Fail: parent(bustan,_17) ? 1 1 Fail: grandparent(_16,_17) ? (4 ms) no
As in Lisp and the ML family, cons-lists are a fundamental data structure in Prolog
member(X, [1,2,3]) X = 1, Y = 2, Z = 3, member(3, [X|[Y|[Z|[]]]]).
append([1],[2],L). L = [1,2] append([1], Y, [1,2,3]). Y = [2,3]
| ?- append([1], Y, L), length(L,2). L = [1,A] Y = [A]
length(L,3), member(X,L). L = [X,_,_] ? ; L = [_,X,_] ? ; L = [_,_,X] ? ;
powerset([],[]). powerset([_|T], P) :- powerset(T,P). powerset([H|T], [H|P]) :- powerset(T,P).
setof(X, powerset([1,2,3], X), PS). PS = [[],[1],[1,2],[1,2,3],[1,3],[2],[2,3],[3]]
filter(List, Pivot, Lower, Higher) divides List up into items Lower & Higher than Pivot
filter( [], _, [], []). filter( [X|Y], P, [X|L], H ):- X =< P, filter(Y, P, L, H). filter( [X|Y], P, L, [X|H] ):- X > P, filter(Y, P, L, H). qsort([], []):-!. qsort([X], [X]):-!. qsort([X,Y], [X,Y]):-X=<Y,!. qsort([X,Y], [Y,X]):-X>Y,!. qsort([X|Y], SXY):- filter(Y, X, L, H), qsort(L,SL), qsort(H,SH), append(SL, [X], SLX), append(SLX, SH, SXY).
Areas in a map
Adjacency
Coloring
adjacent(X,Y,Map) :- member([X,Y],Map) ; member([Y,X],Map). map1([[1,2],[1,3],[1,4],[1,5],[2,3],[2,4],[3,4],[4,5]]). map2([[1,2],[2,3],[1,3]]). map3([[1,2]]).
find_regions discovers all parts of the map from the adjacency description
find_regions([],R,R). find_regions([[X,Y]|S], R,A) :- (member(X,R) -> (member(Y,R) -> find_regions(S,R,A) ; find_regions(S,[Y|R],A)) ; (member(Y,R) -> find_regions(S,[X|R],A) ; find_regions(S,[X,Y|R],A) )). color(Map,Colors,Coloring) :- find_regions(Map,[],Regions), color_all(Regions,Colors,Coloring), not(conflict(Map,Coloring)). color_all([R|Rs],Colors,[[R,C]|A]) :- member(C,Colors), color_all(Rs,Colors,A). color_all([],_,[]). conflict(Map,Coloring) :- member([R1,C],Coloring), member([R2,C],Coloring), adjacent(R1,R2,Map).
The birth of Prolog – Alain Colmerauer and Philippe Roussel
The Early Years of Logic Programming – Robert Kowalski
Wikipedia – Prolog
Wikipedia – Unification (Computer Science)
JR Fisher – Map colorings