07 1024x768

?*path(1.3. [1J>.

U»

path(l. 3. (1J) attempts to match 1. fali 1 * 3. path<1. 3. [1J) matches 2. X is 1. Y is 3. L is J1J movc(l. 2) matches Z as 6. not(member(6. (1))) Ib truo. cali path(6. 3, (6.lh path(6. 3. (6. 1J) attompts to match 1. fail 6 m 3. path(6. 3. (6. IJ) matches 2. X is 6. Y Is 3. L is (6.1). move(6. Z) matches Z as 7. not(mombor(7. [6.1))) is true. path(7.3.17 « path(7.3. (7.6.1]) attempts to match 1. fali 7*3. path(7. 3. (7.6.1)) matches 2. X is 7. Y Is 3. L is [7. 6. 1). move(7. Z) ta Z - 6. not{membor(6. (7. 6. 1J» fails. backtrackl mov«(7. Z) is Z ■ 2. not(member(2. (7. 6. 1))) true. path(2. 3, [2. 7.6.1A path cali attempts 1. fail. 2*3. path matches 2. X is 2. Y is 3. L is [2. 7. 6.1] move matches Z as 7. not(member(...)) fails. backtrackl move matches Z as 9. not(mombor(...)) true. path(9. 3. [9.2. 7.6. ifl path fails 1.9 *3.

path matches 2. X is 9. Y is 3. L is [9. 2. 7. 6. 1J movo is Z = 4. not(member(...)) true. path(4. 3. J4.9. 2. 7.6.1]) path fails 1.4 * 3.

path matches 2. X is 4. Y Is 3. L la (4. 9. 2. 7.6.1] move Z = 3. not(membcr(...)) true. paih(3. 3. (3.4.9.2.7.6.10 path attempts 1. true. 3*3. yes

yes

yes

yes

yes

yes

yes

In summary. the recursivc path cali is a shcll or generał contro! stnacture for searefe a a graph: in path(X, Y, L). X is the present siatę; Y is the goal statc. W hen X and Y ar idcntical. the rccursion terminates. L is the list of States on the currcnt path to stale Y. ad as cach nevv statc Z is found with the cali move(X, Z) it is placcd on the list: |Z IL}. The sute list is chcckcd. using not(member(Z. L)). to be surę the path does not loop.

The diflcrcncc between the State list L in the path cali abovc and the closcd set ■ Chapicr 3 is thst closed rccords all States visited. while the statc list L kecps trackofcdy the present path. It is straightforward to expand the record kceping in the path cali * record all visitcd States and do this in Section 14.4.

14.1.5 The Usc of Cut 10 ControI Search in PROLOG

The cut is rcprcscntcd by an cxclamation point.!. The syntax for cut is that of a goal *4 no argument*. that has *cvcrsl side cftccts: first, when originally cncountcrcd it aNP succceds. and sceood. if it is “failed back to” in backtracking. it causcs the entire goal » 'duch it »* contamed to fail. For a simplc examplc of the cffect of the cut. rccall tbc nunc path cali from the knight*s lour exantplc. The prcdicatc path2 could be crcatcd:

PART VI / LANOUAGES FOR Al PROBLEM SOLVING

path2(X. Y) movo(X. Z). move(Z. Y).

(Thcrc is a iwo-movc path bclwccn X and Y if ihcrc cxists an iniermedialc stop Z bctwrcn them.) For this cxnmplc. assumc parł of the knight*s daiabasc:

inovo(l. 6). move(i. 8). movo(6, 7). movc(6,1). movo(8. 3). movo(8, 1).

The interpreter is uskcd to find all tbc iwo-movc paihs from I: thcrc are four answcrsr

?-poth2(1. W).

W =* 7

W«1

W-3

W® 1

no

Whcn path2 is altercd willi cut. only two answrrs result:

path2(X. Y) movo(X, Z). I. movo(Z. Y).

?• path2(1. W).

W • 7

W®1

no

This happens bccausc variablc Z lakcs on only one \aluc (the first valuc it is bound to), aandy 6. On cc the first subgoal succccds. Z is bound to 6 and the cut is cncountcrcd. This prohibits further backlracking to the first subgoal and no further bindings for Z.

Thcrc aro scvcral uses for the cut in programming. First, as this cxample dcmonstratcd. it allows the program mer to control cxpliciłly the shapc of the scarch trcc.

Wheo further fexhaiislivc) scarch is not rcquircd. the troć can be exp!icitly pruncd at that point. This allows PROLOG codc to havc the fiavor of function cal ling: whcn one set of 'aloes (bindings) is “relumed" by a PROLOG prodicatc (or set of predkrates) and the cut n cncountcrcd. the interpreter docs not scarch for other unifications. If that set of values ifocs not lead on to a solution then no further valucs are attempted.

A second use of cut Controls recursion. For examplc in the path cali:

CMAPTER 14 / AN INTROOUCTION TO PROLOG 615