History of Prolog
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.”
Representing knowledge
Prolog represents facts and rules as Horn Clauses
Head :- Body.
Can be read as “Head is true if Body is true”.
Facts
Facts are represented with an empty body, for example
cat(tom).
which is equivalent to
cat(tom) :- true.
Interacting with a Prolog system
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
Rules
A rule’s body consists of goals, for example:
animal(X) :- cat(X).
What things are animals?
| ?- animal(X). X = tom
Combining goals
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
Combining goals
Using ‘;’ to combine goals is the same as repeating the head:
dog(fido). animal(X) :- cat(X). animal(X) :- dog(X).
Combining goals
Most rules will combine goals with conjunction using the comma (,) operator:
lapdog(X) :- small(X), dog(X), irritating(X).
Unification
Prolog uses an algorithm called unification to match terms and to bind variables to terms.
- A variable which is uninstantiated—i.e. no previous unifications were performed on it—can be unified with an atom, a term, or another uninstantiated variable, thus effectively becoming its alias.
- Two atoms can only be unified if they are identical.
- Similarly, a term can be unified with another term if the top function symbols and arities of the terms are identical and if the parameters can be unified simultaneously. Note that this is a recursive behavior.
Unification – Examples
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
Example 1
father(azai, bustan). father(bustan, clopas). parent(X,Y) :- father(X,Y); mother(X,Y). grandparent(X,Z) :- parent(X, Y), parent(Y, Z).
Example 1 – Output
| ?- grandparent(X,Y). grandparent(X,Y). X = azai Y = clopas ? yes | ?-
Example 1 (Trace)
| ?- 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} | ?-
Example 2 (Backtracking)
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).
Example 2 – Output
| ?- grandparent(X,Y). grandparent(X,Y). X = azai Y = clopas ? ; ; X = magdala Y = clopas ? yes | ?-
Example 2 – Trace
| ?- 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
Lists
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|[]]]]).
Lists
append([1],[2],L). L = [1,2] append([1], Y, [1,2,3]). Y = [2,3]
Lists
| ?- append([1], Y, L), length(L,2). L = [1,A] Y = [A]
Lists
length(L,3), member(X,L). L = [X,_,_] ? ; L = [_,X,_] ? ; L = [_,_,X] ? ;
Powerset
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]]
Quicksort
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).
Map coloring (1)
Areas in a map
Adjacency
Coloring
Map coloring (2)
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]]).
Map coloring (3)
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).
References
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