16 1024x768

move(płcXiłpjX). (handempty. clear(X). ontable(X)].

[dol<handempty), del(cloar<X)). dol(ontab!o(X)). add<holding(X))J).

movo< putdown(X). |ho!ding(X)J.

(dol(holding(X)>. add(ontablo<X». add(clcar(X)). add(handempty)]).

mov*<»tack(X.Y). [holding{X). clear(Y)).

[dol(holding(X)). del<cJear{Y)), add(handompty). add(on(X.Y». add(cIoar<X))J).

Finał ly, we havc ihe rccursive eon troi lor for thc plan gcncration. The tiret pbn prcdicatc gi\cs thc successful terminalion conditions for thc plan. nnmćly, whcn thc gnl i* produccd The finał plan prcdicatc States that after cxhaustivc scarch. no plan n possiblc. The rccursivc plan generator:

1.    Scarchcs for a move relationship.

2.    Chccks. using thc subset operator, whctlier thc State s Precondltions are met.

3.    The change.state prcdicate produccs a new Child State using thc add and delcie lisi.

4.    member. stack makes surę thc new stale has not becn yisited before.

5.    The stack operator pushes thc new Child_state out o thc New moves_stadc

6.    The stack operator pushes thc original Name State onto tlte New_been_stack.

7.    The rccursń-e plan cali scarchcs for thc ncxt stale using thc Chiłd.State and ar. updaied New_move__stack and Been_stack.

A number of supporting Utilities, built on thc stack and set ADTs of Scctions 14J2-1 and 14.2.4 are included. Of coursc. thc scarch bcing staek-based. is depth-first backtracking and tenninates with thc fint path found to a goal. It is Icft as an excrci$e to build breadth-first and best-first planncrs.

p!an(State. Goal. Move. stack) egual. set(State. Goal). write<‘moves are'), nl, reverso,print_stack(Movo.stack).

plan(State. Goal. Been.stack. Movo_stack) > move(Namo, Precondttions. Actłons). conditions met(Preconditlons. State). change_state(State. Actłons. Child_state). not(membor .stack(Child State. Been stack)). stacfc(Name. Been stack. New _ boon _stack). stack(Child_State. Move_ stack. New_move stack),

pian(Chi!d_state. Goal. Now_boen_stack. New move_stack). I.

P**°( , .. J > writefNo plan possible with theso moves!’).

PART VI / LANGUAGES FOR AJ PROBLEM SOLVINO

conditions. mot(P. 3) > subset(P. S). change_state($, [ ], 8). chango siato(S, (add(P) ITJ. S_ncw) chango stnto(S. T. 82). add Jf_not_in_sot(P. S2, S_ncw).!. chango_stalo(S. [del(P) IT], S_new) chnngo stolo(S, T. S2). dolole_lf_in_sel(P, S2. S. naw).!. rovorse„print_slack(S) omply._stack(S). rovors«_print_»tack(S) stnck(E. Rost. S).

ro verse_ pri n t_stack(Resl). writo(E), nl.

Finally. we create a go prcdicatc to iniiialize thc argument* for plan. as sell as a test prcdicatc lo demonstratc an casy metbod to savc repeated crcation of thc same input string.

go(Start. Goal)

empty_»tack(Movo_atack), empty„stack(Been_stack). stack(Start. Been_stack, New_been_stock). plan(Start, Goal. Now_boen_atack. Movostack). test:-

go([handempty. ontabie(b). ontablo(c). on(a.b). cloar(c). cloar(a)].

[handempty. óntable(a). ontablo(b). on(c.b). cloar(a). doar(c)J).

14.6 PROLOG: Meta-Predicates, Typcs and Unification

14.6.1 Mela-Logical Predicates

Mcta-Iogica! constructs cxtcnd thc cxprcssive power of any progtamminj eiwironmcot. Werefer to thcsc predicates as meta bccause tllcy are designed to match. qucry and manip-utotc other predicates that inakc up thc spcciftcations of thc problem domain. Tłtai is. they can be uscd to rcason about PROLOG predicates rather than thc term* or objeets thcsc other predicates dcnotc. Wc need mcta-prcdicates in PROLOG for (at least) five rcasons:

1.    To dctcrminc thc **typc'* of an cxprcssion.

2.    To add ”typc" constraints to logie programming applications.

3.    To build. lakę apart. and cvaluatc PROLOG structurcs.

4.    To comparc valucs of cxprcssions.

5.    To convcrt predicates passed as data to cxccutaUc codc.

633

CHARTER 14 / AN MTROOUCTION TO PROLOG