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.

  1. 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.
  2. Two atoms can only be unified if they are identical.
  3. 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