PROGRAMMING LANGUAGES
6.9.5 Extended Example: Tic-Tac-Toe
In the previous subsection we saw how the order of clauses in the Prolog database,and the order of terms within a right-hand side, can affect both the efficiencyof a Prolog program and its ability to terminate. Ordering also allows the Prologprogrammer to indicate that certain resolutions are preferred, and should beconsidered before other, “fallback” options. Consider, for example, the problemof making a move in tic-tac-toe. (Tic-tac-toe is a game played on a 3 ×3 gridof squares. Two players, X and O, take turns placing markers in empty squares.
A player wins if he or she places three markers in a row, horizontally, vertically, ordiagonally.)Let us number the squares from 1 to 9 in row-major order. Further, let us usethe Prolog fact x(n) to indicate that player X has placed a marker in square n, ando(m) to indicate that player O has placed a marker in square m. For simplicity, letus assume that the computer is player X, and that it is X’s turn to move.We shouldlike to be able to issue a query ?- move(A) that will cause the Prolog interpreterto choose a good square A for the computer to occupy next.Clearly we need to be able to tell whether three given squares lie in a row. One
way to express this is:
ordered_line(1, 2, 3). ordered_line(4, 5, 6).
ordered_line(7, 8, 9). ordered_line(1, 4, 7).
ordered_line(2, 5, 8). ordered_line(3, 6, 9).
ordered_line(1, 5, 9). ordered_line(3, 5, 7).
line(A, B, C) :- ordered_line(A, B, C).
line(A, B, C) :- ordered_line(A, C, B).
line(A, B, C) :- ordered_line(B, A, C).
line(A, B, C) :- ordered_line(B, C, A).
line(A, B, C) :- ordered_line(C, A, B).
line(A, B, C) :- ordered_line(C, B, A).
It is easy to prove that there is no winning strategy for tic-tac-toe: either playercan force a draw. Let us assume, however, that our program is playing against a
Here we have again relied on the built-in predicate \+.Our fourth choice is to build toward three in a row (i.e., to get two in a row)in such a way that the obvious blocking move won’t allow our opponent to buildtoward three in a row:
strong_build(A) :- x(B), line(A, B, C), empty(C), \+(risky(C)).
risky(C) :- o(D), line(C, D, E), empty(E).
Barring that, our fifth choice is to build toward three in a row in such a way thatthe obvious blocking move won’t give our opponent a split:
weak_build(A) :- x(B), line(A, B, C), empty(C), \+(double_risky(C)).
double_risky(C) :- o(D), o(E), different(D, E), line(C, D, F),
line(C, E, G), empty(F), empty(G).
If none of these goals can be satisfied, our final, default choice is to pick anunoccupied square, giving priority to the center, the corners, and the sides in that
order:
good(5).
good(1). good(3). good(7). good(9).
good(2). good(4). good(6). good(8).
6.9.6 Imperative Control Flow
We have seen that the ordering of clauses and of terms in Prolog is significant,with ramifications for efficiency, termination, and choice among alternatives. Inaddition to simple ordering, Prolog provides the programmer with several explicitcontrol-flow features. The most important of these features is known as the cut.The cut is a zero-argument predicate written as an exclamation point: !. As asubgoal it always succeeds, but with a crucial side effect: it commits the interpreterto whatever choices have been made since unifying the parent goal with the lefthandside of the current rule, including the choice of that unification itself. For
The cut example, recall our definition of list membership:
member(X, [X | _]).
member(X, [_ | T]) :- member(X, T).
If a given atom a appears in list L n times, then the goal ?- member(a, L) cansucceed n times. These “extra” successes may not always be appropriate. They canlead to wasted computation, particularly for long lists, when member is followedby a goal that may fail:
prime_candidate(X) :- member(X, candidates), prime(X).
Suppose that prime(X) is expensive to compute. To determine whether a is aprime candidate, we first check to see whether it is a member of the candidateslist, and then check to see whether it is prime. If prime(a) fails, Prolog willbacktrack and attempt to satisfy member(a, candidates) again. If a is in thecandidates list more than once, then the subgoal will succeed again, leading toreconsideration of the prime(a) subgoal, even though that subgoal is doomed tofail.We can save substantial time by cutting off all further searches for a after the
first is found:
member(X, [X | _]) :- !.
member(X, [_ | T]) :- member(X, T).
The cut on the right-hand side of the first rule says that if X is the head of L, weshould not attempt to unify member(X, L) with the left-hand side of the secondrule; the cut commits us to the first rule. An alternative way to ensure that member(X, L) succeeds no more than onceis to embed a use of \+ in the second clause:
member(X, [X | _]).
member(X, [H | T]) :- X \= H, member(X, T).
Here X \= H means X and H will not unify; that is, \+(X = H). (In some Prolog
dialects, \+ is written not. This name suggests an interpretation that may besomewhat misleading; we discuss the issue in Section 11.4.3.) Our new version ofmember will display the same high-level behavior as before, but will be slightly lessefficient: now the interpreter will actually consider the second rule, abandoning itonly after (re)unifying X with H and reversing the sense of the test.It turns out that \+ is actually implemented by a combination of the cut andtwo other built-in predicates, call and fail:
\+(P) :- call(P), !, fail.
\+(P).
The call predicate takes a term as argument and attempts to satisfy it as a goal(terms are first-class values in Prolog). The fail predicate always fails. In principle, it is possible to replace all uses of the cut with uses of \+ —toconfine the cut to the implementation of \+. Doing so often makes a programeasier to read. As we have seen, however, it often makes it less efficient. In somecases, explicit use of the cut may actuallymake a programeasierto read. Considerour tic-tac-toe example. If we type semicolons at the program, it will continue togenerate a series of increasingly poor moves from the same board position, eventhough we only want the first move.We can cut off consideration of the others by
using the cut:
move(A) :- good(A), empty(A), !.
To achieve the same effect with \+ we would have to do more major surgery
(Exercise 11.8). _
In general, the cut can be used whenever we want the effect of if. . . then . . .
_
The fail predicate can be used in conjunction with a “generator” to implement aloop.We have already seen (in Example 11.13) how to effect a generator by drivinga set of rules “backward.” Recall our definition of append:
append([], A, A).
append([H | T], A, [H | L]) :- append(T, A, L).
If we use write append(A, B, L), where L is instantiated but A and B are not,the interpreter will find an A and B for which the predicate is true. If backtrackingforces it to return, the interpreter will look for another A and B; appendwill generate pairs on demand. (There is a strong analogy here to the generatorsof Icon, discussed in Section 6.5.4.) Thus, to enumerate the ways inwhich a list can be partitioned into pairs, we can follow a use of append with
fail:
print_partitions(L) :- append(A, B, L),
write(A), write(’ ’), write(B), nl,
fail.
The nlpredicate prints a newline character. The query print_partitions([a,
b, c]) produces the following output:
[] [a, b, c]
[a] [b, c]
[a, b] [c]
[a, b, c] []
No
If we don’t want the overall predicate to fail, we can add a final rule:print_partitions(_).
Assuming this rule appears last, it will succeed after the output has appeared, and
the interpreter will finish with “Yes.”_
In some cases, we may have a generator that produces an unbounded sequenceof values. The following, for example, generates all of the natural numbers:
natural(N) :- natural(M), N is M+1.We can use this generator in conjunction with a “test-cut” combination to iterate
over the first n numbers:
my_loop(N) :- natural(I),
write(I), nl, % loop body (nl prints a newline)
I = N, !.
So long as I is less than N, the equality (unification) predicate will fail and backtrackingwill pursue another alternative for natural. If I = N succeeds, however,then the cut will be executed, committing us to the current (final) choice of I, andsuccessfully terminating the loop. This programming idiom—an unbounded generator with a test-cut terminator—is known as generate-and-test.
repeat:
get(X) :- repeat, get0(X), X >= 32, !.
The get0 predicate attempts to unify its argumentwith the single next character ofinput, regardless of value and, like get, cannot be resatisfied during backtracking.The repeat predicate, by contrast, can succeed an arbitrary number of times; itbehaves as if it were implemented with the following pair of rules:
repeat.
repeat :- repeat.
Within the above definition of get, backtracking will return to repeat as oftenas needed to produce a printable character (one with ASCII code at least 32).In general, repeat allows us to turn any predicate with side effects into agenerator.
6.9.7 Database Manipulation
?- rainy(X).
X = seattle ;
X = syracuse ;
No
There is also a retractallpredicate that removes all matching clauses from the
database. _
?- functor(foo(a, b, c), foo, 3).
Yes
?- functor(foo(a, b, c), F, N).
F = foo
N = 3
?- functor(T, foo, 3).
T = foo(_10, _37, _24)
In the last line of output, the atoms with leading underscores are placeholders for
uninstantiated variables. _
The goal arg(N, T, A) succeeds if and only if its first two arguments (N and T)
are instantiated, N is a natural number, T is a term, and A is the Nth argument of T:
?- arg(3, foo(a, b, c), A).
A = c
Taken together, the predicates described above allow a Prolog program to createand decompose clauses, and to add and subtract them from the database. So far,however, the only mechanism we have for perusing the database (i.e., to determineits contents) is the built-in search mechanism. To allow programs to “reason” inmore general ways, Prolog provides a clause predicate that attempts to match itstwo arguments against the head and body of some existing clause in the database:
?- clause(snowy(X), B).
B = rainy(X), cold(X) ;
No
Here we have discovered (by entering a query and requesting further matcheswith a semicolon) that there is a single rule in the database whose head is a singleargumentterm with functorsnowy. The body of that rule is the conjunction
B = rainy(X), cold(X). Prolog requires that the first argument to clause besufficiently instantiated that its functor and arity can be determined.A clause with no body (a fact) matches the body true:
?- clause(rainy(rochester), true).
Yes
Note that clause is quite different from call: it does not attempt to satisfy agoal, but simply to match it against an existing clause:
?- clause(snowy(rochester), true).
No
Department of CSE/ISE NIT,Raichur