Non-Determinism in Prolog

We will look at terms (the basic data structure) in prolog. All prolog data and prolog programs are stored as terms. A widely used term type is a list. We will look at several non-deterministic predicates over lists. Using the predicates on lists and their non-deterministic capabilities, we develop a program to do breadth first search (BFS) and a program to solve the n-queens problem. BFS is the basis for many search algorithms in AI such as $A^*$, IDA, $\alpha-\beta.$

Terms

The basic data type in prolog is a term. Terms are defined recursively,

A term is

• a constant (number, atoms, strings, eg. 123, a, ‘abc’)
• variable (eg X),
• or a compound term (eg $f(t_1, t_2, \ldots, t_n)$ where each $t_i$ is a term, $f$ is called the functor and $t_i$ an argument. The number of arguments is called the arity of the functor.)

A term can be visualized as a tree with the functor as the root. The term a = [] has a canonical representation =(a, []), where = is the functor with arity 2, and the arguments are terms a, [].

The list [a] is a syntatic sugar for the term .(a,[]), where . is the functor and [] represents an empty list. [X|R] represents a list where the first element is X and the rest of the list is R. Anonymous variables are represented by _, therefore [X|_] is a list.

Tuples such as (a,b,c) are represented as ,(a, (b,c)) where , is the functor. All k-tuples are represented as 2-tuples. The canonical representation of (a,b,c) is

| ?- write_canonical((a,b,c)).        
','(a,','(b,c))

Observe the canonical representation of the term below.

| ?- write_canonical( (a,b) = [1,2]).
=(','(a,b),'.'(1,'.'(2,[])))

A prolog program is repesented as a term. Prolog possess a unique property that data and code are stored th same way. Therefore, it is easy to write meta-programs that manipulate other programs. Prolog operator to check for equality of terms is ==. This operator does not instantiate the variables in the terms.

?- X == Y.
?- a == b.
?- a == a.

false.
false.
true.

If we want to test of equality of terms while instantiation of variables is allowed then the operator is = and the process is called unification. A recursive process for unification can be specified based on the definition of the terms. Variables unify with other variables or atoms, and two atoms unify if they are the are defined as identical atoms(== check). Two compound terms unify only if they have the same functor and the same arity, and the arguments in the compound terms unify as well. There is a little issue of a variable name repeating across the two terms that we are trying to unify. As in X = f(X), SWI prolog for efficiency reasons does not check whether X is repeated in the term f(X). Therefore, it allows for unification. There is a built in predicate unify_with_occurs_check which is computationally more expensive, but detect the dependency and rightly returns false, see below for some examples of unification (with and without occurs check in work).

Try out examples of your own in the cell below, and pay attention to unification of lists.

?- unify_with_occurs_check(X, f(X)).

false.

?- X = f(a,Y).
?- f(a,X) = g(a, X).
?- f(a, X)=f(Y, g(a, Y)).
?- [a,b,c] = [X,Y|Z]. 

X = f(a, _76), Y = _76 .
false.
X = g(a, a), Y = a .
X = a, Y = b, Z = [ c ] .

Lists

Given a list, we can query membership in the list using the predicate member. For instance member(1,[1,2,3]) return true, where member(4,[1,2,3]) returns false, for obvious reasons. This predicate can be programmed (see mem below) using recursive rules as follows. If X is the first element of the list then first rule succeeds, else the second rule is used. The second rule checks if X is a member of the remainder of the list R.

mem(X, [X|_]).
mem(X, [Y|R]) :- mem(X,R).

?- mem(1,[1,2,3]).
?- mem(2,[1,2,3]).
?- mem(4,[1,2,3]).

true.
true.
false.

?- mem(X,[1,2,3]). is a valid query, the question is what does it return. The meaning of the predicate says that for all X which are members of [1,2,3] the query should return true. Therefore, we expect that prolog with return three answers of X (separated by ;). This is non-determinism in prolog. This ability lets us write programs that follows the generate and test paradigm. We will see the example of the n-queens problem later.

?- mem(X,[1,2,3]).

X = 1 ;
X = 2 ;
X = 3 .

What if we ask the query ?- mem(1,X).? Since X is a free variable, 1 is member of all such lists, and one can occur in any position. Therefore the result of the query is a countable set. So, the number of solutions to a query do not have to be finite.

?- mem(1,X).

X = [ 1 ] ;
X = [ _80, 1 ] ;
X = [ _80, _86, 1 ] ;
X = [ _80, _86, _92, 1 ] ;
X = [ _80, _86, _92, _98, 1 ] ;
X = [ _80, _86, _92, _98, _104, 1 ] ;
X = [ _80, _86, _92, _98, _104, _110, 1 ] ;
X = [ _80, _86, _92, _98, _104, _110, _116, 1 ] ;
X = [ _80, _86, _92, _98, _104, _110, _116, _122, 1 ] ;
X = [ _80, _86, _92, _98, _104, _110, _116, _122, _128, 1 ] .

What about concatenating lists? Let’s write recursive rules to concatenate the elements of lists L1 and L2 into list L3. conc([1,2],[4,5],L) should return L=[1,2,4,5]. The base case is when the first list is empty, and in that case the result of the concatenation is the second list. The recursive case assumes that the first list is [X|R], in this case the result is [X|L3] where L3 is obtained by recursively concatenating R with the second list L2.

conc([], L, L).
conc([X|R] , L2, [X|L3]) :- conc(R,L2,L3). 

Concatenate rule can be used as a predicate, ?- conc([1,2],[3,4],[1,2,3,4]) returns true, false if the third argument (grounded variable) is not a concatenation of the first two arguments.

A more interesing query is ?- conc(L1, L2,[1,2,3,4])., which find all values of L1, L2 such that their concatenation is [1,2,3,4]. There are five different ways that this can be accomplished as shown below.

?- conc(L1, L2,[1,2,3,4]).

L1 = [  ], L2 = [ 1, 2, 3, 4 ] ;
L1 = [ 1 ], L2 = [ 2, 3, 4 ] ;
L1 = [ 1, 2 ], L2 = [ 3, 4 ] ;
L1 = [ 1, 2, 3 ], L2 = [ 4 ] ;
L1 = [ 1, 2, 3, 4 ], L2 = [  ] .

A very important feature of the concatenate predicate is its ablity to generate lists of various sizes organized by increasing order of length. This ability can be used to look for path in breadth-first order. This is important, because the default nature of search in prolog is depth-first, which can easliy lead to non-terminating programs. The query conc(L,_,_) asks how many ways can we get _ and prolog attempts to answer that by generating all the possibilities.

?- conc(L, _, _).

L = [  ] ;
L = [ _112 ] ;
L = [ _112, _124 ] ;
L = [ _112, _124, _136 ] ;
L = [ _112, _124, _136, _148 ] ;
L = [ _112, _124, _136, _148, _160 ] ;
L = [ _112, _124, _136, _148, _160, _172 ] ;
L = [ _112, _124, _136, _148, _160, _172, _184 ] ;
L = [ _112, _124, _136, _148, _160, _172, _184, _196 ] ;
L = [ _112, _124, _136, _148, _160, _172, _184, _196, _208 ] .

Concatenate can used to redefine the membership rules using the following observation. X is a member of list L, if L can be broken into two parts L1, L2 where L1 is the prefix of L (that occurs before X) and L2 is the suffix after X.

       L = [_,_, ..., X,_, ..., _]
       L1= [         ]
       L2 =            [         ]

mem2(X, L):- conc(_, [X|_], L).

?- mem2(X, [1,2,3]).

X = 1 ;
X = 2 ;
X = 3 .

Lets write a rule to delete and element from a list. delete X L returns true or false depending on whether X is in the list L or not. The recursive definition is below. If X is the first element of L then delete succeeds, else we return the result of a recursive delete from the rest of L.

We can also use delete to redefine the membership test. An element X is a member of list L if X can be deleted from L. Note, that delete is non-deterministic as well. delete(X, [1,2,3]) returns all possible values that can be deleted.

delete(X, [X|_]).
delete(X, [Y|R]) :- delete(X,R).

mem1(X, L) :- delete(X,L).

?- mem1(1, [1,2,3]).
?- delete(X, [1,2,3]).

true.
X = 1 ;
X = 2 ;
X = 3 .

BFS and DFS in Prolog

Let’s work with directed graphs Each edge $(u,v)$ in the graph is represented as relation edge(u,v). Our example has two cycles a->b->c->a and a->d->e->a. The graph is stored using the relations below.

edge(a,b).
edge(b,c).
edge(c,a).
edge(a,d).
edge(d,e).
edge(e,a).

Consider the following definition of path/3 which returns a path from X to Y as the third argument. Path from X to X exists, and is [X]. Path from X,Y exists if there is an edge from X to Z and a path R from Z to Y. This path is [X | R]. Given the non-determinstic nature of the Prolog, we expect the query path(a,a,P) should return at least the two cyles of length three each. Cycles of length $6, 9, \ldots $ should also be returned.

path(X,X,[X]).
path(X,Y,[X|Rest]) :-
    edge(X,Z),
    path(Z,Y,Rest).

?- path(a,a,P).

P = [ a ] ;
P = [ a, b, c, a ] ;
P = [ a, b, c, a, b, c, a ] ;
P = [ a, b, c, a, b, c, a, b, c, a ] ;
P = [ a, b, c, a, b, c, a, b, c, a, b, c, a ] ;
P = [ a, b, c, a, b, c, a, b, c, a, b, c, a, b, c, a ] ;
P = [ a, b, c, a, b, c, a, b, c, a, b, c, a, b, c, a, b, c, a ] ;
P = [ a, b, c, a, b, c, a, b, c, a, b, c, a, b, c, a, b, c, a, b, c, a ] ;
P = [ a, b, c, a, b, c, a, b, c, a, b, c, a, b, c, a, b, c, a, b, c, a, b, c, a ] ;
P = [ a, b, c, a, b, c, a, b, c, a, b, c, a, b, c, a, b, c, a, b, c, a, b, c, a, b, c, a ] .

As prolog does DFS, it will not discover any path starting with the second cycle a->d->e->a. Therefore we need to get creative. In fact, we need to force prolog to enumerate cycles in the increasing order of their length. This we have seen can be accomplished using conc(L,_,_) predicate. The query ?- conc(P,_,_), path(a,a,P). would generate cycles in the increasing order of their lenghts as seen below. This is an important trick to remember.

path1(X,Y,P) :-
    conc(P,_,_),
    path(X,Y,P).

?- path1(a,a,P).

P = [ a ] ;
P = [ a, b, c, a ] ;
P = [ a, d, e, a ] ;
P = [ a, b, c, a, b, c, a ] ;
P = [ a, b, c, a, d, e, a ] ;
P = [ a, d, e, a, b, c, a ] ;
P = [ a, d, e, a, d, e, a ] ;
P = [ a, b, c, a, b, c, a, b, c, a ] ;
P = [ a, b, c, a, b, c, a, d, e, a ] ;
P = [ a, b, c, a, d, e, a, b, c, a ] .

The same BFS behaviour can be obtained by reordering the subgoals in the path predicated as shown below. Try to deeply understand this behaviour of prolog when it comes to search.

path2(X,X,[X]).
path2(X,Y,[X|Rest]) :-
    path2(Z,Y,Rest),
    edge(X,Z).

?- path2(a,a,P).

P = [ a ] ;
P = [ a, b, c, a ] ;
P = [ a, d, e, a ] ;
P = [ a, b, c, a, b, c, a ] ;
P = [ a, d, e, a, b, c, a ] ;
P = [ a, b, c, a, d, e, a ] ;
P = [ a, d, e, a, d, e, a ] ;
P = [ a, b, c, a, b, c, a, b, c, a ] ;
P = [ a, d, e, a, b, c, a, b, c, a ] ;
P = [ a, b, c, a, d, e, a, b, c, a ] .

The 8-queens problem

Given is a 8x8 chess board, the goal is to place 8 queens on the board such that no two queens are in the same diagonal, column or row. We use (X,Y) to represent that a queen is in row X and column Y. X, Y take values in [1..8].

place is a single argument predicate that will place the queens. the X coordinates can be frozen as 1,2..,8 because the queens have to be in different coordinates along the X axis. Input is a list of two tuples. We need the coordinates in general form to check the safeness of the placement using arithmetic operations.

The following query will solve the problem.

?- place([(1,Y1),(2,Y2),(3,Y3),(4,Y4),(5,Y5),(6,Y6),(7,Y7),(8,Y8)]).

place is defined recursively. If the list is empty then we return true. If the list is [(X,Y) | R] then X we know is fixed in the call, and Y is a member of [1..8], and rest of the Ys in R are fixed recursively. Finally, we need to check is the placement of all the 8 queens is safe. This safety check is performed by another recursive predicated check.

place([]).   
place([(X,Y)|R]) :-
   place(R),
   member(Y,[1,2,3,4,5,6,7,8]),
   check((X,Y), R).        

Given a list [(X,Y), (X1, Y1), | R]

• we know that X=\=X1,
• so we need
  • check whether the queens are in the same column (Y == Y1),
  • whether there are in same upwards diagonal (Y1 - Y == X1 - X),
  • or they are in the same backwards diagonal (Y1-Y == X - X1),
• Furthermore, (X,Y) needs to be checked with every element in the rest of the list R. This step can be done recursively. The code is below.

Notice the use of the operator for comparing the terms without instantiation of the variables.

check(_, []).
check((X,Y), [(X1,Y1)|R]):-
    Y =\= Y1,
    Y1-Y =\= X1 - X, 
    Y1 - Y =\= X-X1,
    check((X,Y), R).

We are ready to find all the possible placements of 8 queens on a 8x8 chess-board such that no two attack each other.

?- place([(1,Y1),(2,Y2),(3,Y3),(4,Y4),(5,Y5),(6,Y6),(7,Y7),(8,Y8)]).        

Y1 = 4, Y2 = 2, Y3 = 7, Y4 = 3, Y5 = 6, Y6 = 8, Y7 = 5, Y8 = 1 ;
Y1 = 5, Y2 = 2, Y3 = 4, Y4 = 7, Y5 = 3, Y6 = 8, Y7 = 6, Y8 = 1 ;
Y1 = 3, Y2 = 5, Y3 = 2, Y4 = 8, Y5 = 6, Y6 = 4, Y7 = 7, Y8 = 1 ;
Y1 = 3, Y2 = 6, Y3 = 4, Y4 = 2, Y5 = 8, Y6 = 5, Y7 = 7, Y8 = 1 ;
Y1 = 5, Y2 = 7, Y3 = 1, Y4 = 3, Y5 = 8, Y6 = 6, Y7 = 4, Y8 = 2 ;
Y1 = 4, Y2 = 6, Y3 = 8, Y4 = 3, Y5 = 1, Y6 = 7, Y7 = 5, Y8 = 2 ;
Y1 = 3, Y2 = 6, Y3 = 8, Y4 = 1, Y5 = 4, Y6 = 7, Y7 = 5, Y8 = 2 ;
Y1 = 5, Y2 = 3, Y3 = 8, Y4 = 4, Y5 = 7, Y6 = 1, Y7 = 6, Y8 = 2 ;
Y1 = 5, Y2 = 7, Y3 = 4, Y4 = 1, Y5 = 3, Y6 = 8, Y7 = 6, Y8 = 2 ;
Y1 = 4, Y2 = 1, Y3 = 5, Y4 = 8, Y5 = 6, Y6 = 3, Y7 = 7, Y8 = 2 .

Exercise

The 8 queens program above, uses the generate and test paradigm. Consider the first sub goal place(R), upon return from this call variables Y2, ..., Y8 all have assigned. Let YL be the list of values assigned.

How about choosing a value for Y1 which does not conflict with any of the assignment to Y2, ..., Y8? One way to perform this to replace member(Y,[1..8]) with a new predicate choose(Y, L). This new predicate chooses a value for Y from elements in L (non-deterministically ofcourse), and then we construct L by removing the values that conflict with the previous assignments (conflicting with YL in our example).

• Modify the code above to implement the operation above.
• Is the predicate check still needed?
• Read the documentation on the builtin predicate statistics. Use it to compare the run time of the two versions.
• Which version runs faster? Can you give reasons why?