Logic Programming in Prolog
• BacktrackingwiththeCut – The “Cut”
– Coding the existence of a single solution • no other rules should be tried
• no backtracking across this point
Copyright By PowCoder代写 加微信 powcoder
– Abandoning a goal with cut and fail • Datastructures:Lists
– Basic list processing
– Appending a list to another – Reading into a list
The “Cut” !
• “cut” off some backtracking path
– Prolog will not try to re-satisfy certain goals.
• Reasons for using the cut
– faster execution
– more efficient use of memory (don’t have to keep track of as many backtrack points)
• Syntax:!
– goal that always succeeds and has a side effect (on the way backtracking works)
Cut-off concept
• The cut choice allows you to tell Prolog that you do not want to keep the choice points on hold
• Useful when there are mutual exclusive clauses * Ex: the following 2 rules
human(X):- male(X). human(X):- female(X).
* is written:
human(X):- male(X) ,!. human(X):- female(X) ,!.
If we already have demonstrated that X is a male,
there is no need to check if X is a female
2021-03-04
A Simple Example:
• Goal:Removingbranches(pruning)fromthesearchtree that are known not to produce a solution.
human (X): – male (X),!. human (X): – female (X),!.
– The cut commits Prolog to the facts established
• if the subgoal male(X) succeeds, the cut succeeds
and the cat rule in the first row succeeds. The backtracking path is now cut off and Prolog will not search to re-satisfy male(X) or human(X).
Effect of the Cut
• When a cut is encountered as a goal, the system becomes committed to all choices made since the parent goal was invoked.
– This means the choice of which clause, and all the choices in the “sibling” goals up to the cut are fixed.
• Therefore the Cut permits the elimination of branches in the search tree by
– eliminating other rules for the same goal – eliminating other choices for subgoals
The cut! allows to eliminate all the choices not yet explored.
The cut choice becomes active when demonstrated Its effect going back to the point that it was
introduced
The choices not explored before the introduction of the cut and after its demonstration remain available
Rules and facts a,b,c,d,e,h arranged in a tree
h(X) :- d(X). h(X) :- X=e. d(X) :- X=a. d(X) :- X=b. d(X) :- X=c. a.
Query initiating a tree traversal: ?- h(X).
Produces the leave nodes (depth first search): abce
Rules and facts a,b,c,d,e,h arranged in a tree
hX) :- d(X). h(X) :- X=e. d(X) :- X=a,!. d(X) :- X=b. d(X) :- X=c. a.
Query initiating a tree traversal: ?- h(X).
When the cut is met, we can no longer prove otherwise.
Produces only the leave nodes (depth first search): ae
p(X,Y):-q(X,Y),s(Y). p(a,a). q(X,Y):-v(X),w(Y). q(m,Y).
v(a). v(b). w(b). w(c). s(c).
?- p(X,Y). X=a,Y=c ; X=b,Y=c ; X = m, Y = c ; X = Y, Y = a.
v(X),w(Y),s(Y)
X=a v(a),w(Y),s(Y)
p(X,Y):-q(X,Y),s(Y). p(a,a). q(X,Y):-v(X),w(Y). q(m,Y).
p(X,Y) q(X,Y),s(Y)
q(m,Y),s(Y)
v(b),w(Y),s(Y) Y=b Y=c
v(a),w(b),s(b) v(a),w(c),s(c) v(b),w(b),s(b) v(b),w(c),s(c)
X=m,Y=c X=a,Y=c fail X=b,Y=c
p(X,Y):-q(X,Y),!,s(Y). p(a,a). q(X,Y):-v(X),w(Y). q(m,Y).
v(a). v(b). w(b). w(c). s(c).
?- p(X,Y). false.
The cut is demonstrated here
v(X),w(Y),!,s(Y) X=b
v(a),w(c),s(c) v(b),w(b),s(b) v(b),w(c),s(c) X=a,Y=c fail X=b,Y=c
Introduction the cut
q(m,Y),s(Y)
v(a),w(Y),!,s(Y) v(b),w(Y),s(Y)
q(X,Y),!,s(Y) X=m
p(a,a) X=a,Y=a
p(X,Y):-q(X,Y),!,s(Y). p(a,a). q(X,Y):-v(X),w(Y). q(m,Y).
Y=b Y=c
v(a),w(b),!,s(b)
p(X,Y):-q(X,Y),s(Y). p(a,a). q(X,Y):-v(X),!,w(Y). q(m,Y).
v(a). v(b). w(b). w(c). s(c).
?- p(X,Y).
X = a, Y = c ; X = Y, Y = a.
Introducing the cut
The cut is demonstrated here
v(X),!,w(Y),s(Y) X=a X=b
X=a,Y=c fail X=b,Y=c
q(X,Y),s(Y)
q(m,Y),s(Y)
v(a),!,w(Y),s(Y)
v(b),w(Y),s(Y)
Y=c Y=b Y=c v(a),w(b),s(b) v(a),w(c),s(c) v(a),w(b),s(b) v(a),w(c),s(c)
?- p(X,Y).
X = a, Y = c ; X = Y, Y = a.
Introducing the cut
p(X,Y):-q(X,Y),s(Y). p(a,a). q(X,Y):-v(X),!,w(Y). q(m,Y).
v(a). v(b). w(b). w(c). s(c).
The cut is demonstrated here
v(X),!,w(Y),s(Y) X=a X=b
Y=c Y=b Y=c v(a),w(b),s(b) v(a),w(c),s(c) v(a),w(b),s(b) v(a),w(c),s(c)
X=a,Y=c fail X=b,Y=c
q(X,Y),s(Y)
q(m,Y),s(Y)
v(a),!,w(Y),s(Y)
v(b),w(Y),s(Y)
An Arithmetic Example: roots
• Anaivewaytocalculatetheintegerrootofanumberis to use a generator for integer numbers and see if the result succeeds.
• Generator
int(N) :- int(N1), N is N1+1.
• Rootpredicate
root(N,R) :- int(K), K*K>N,!, R is K-1.
– Cut ensure that once 𝐾2 > 𝑁, backtracking of the generator stops (int). As the generation of integers has no end.
– change the solution space (see the previous root example).
• GreenCuts
– remove choices that wouldn’t work anyway – efficiency gain
– reduced memory footprint
Summary: Utility of the Cut
• Delete branches that will not lead to a solution
• Removemutuallyexclusivecasesinrules
• Reducethenumberofsolutionsproduced
• Makesurethatcertainprograms(recursion)terminate • Controloftheproofprocedure
leave(friday). weather(friday, fine). weather(saturday, fine). weather(sunday, fine). weekend(saturday). weekend(sunday).
The request:
? – picnic (J).
The results:
D = saturday; D = sunday; D = friday.
% The rules:
picnic(J):- weather(J, fine), weekend(J). picnic(J):- leave(J).
leave(friday). weather(friday, fine). weather(saturday, fine). weather(sunday, fine). weekend(saturday). weekend(sunday).
The rules:
The request:
? – picnic (J).
The results:
picnic (J): – weather (J, fine),!, weekend (J). picnic (J): – leave (J).
leave(friday). weather(friday, fine). weather(saturday, fine). weather(sunday, fine). weekend(saturday). weekend(sunday).
The rules:
picnic (J): – weather (J, fine), weekend (J),!. picnic (J): – leave (J).
The request:
? – picnic (J).
The results:
D = Saturday.
%Facts: The request: leave(friday). ? – picnic (J). weather(friday, fine). weather(saturday, fine). weather(sunday, fine). weekend(saturday). weekend(sunday).
The rules:
picnic (J): – !, weather (J, fine), weekend (J). picnic (J): – leave (J).
http://www.cse.unsw.edu.au/~billw/dictionaries/prolog/cut.html
The results:
D = Saturday; D = Sunday.
p(X, Y):-q(X), r(X, Y). p(c, c1).
r(a, a1). r(a, a2). r(b, b1). r(b, b2). r(b, b3).
6 solutions
p (X, Y):- q (X), r (X, Y),!. p (c, c1).
1 solution
p (X, Y):- q (X),!, r (X, Y). p (c, c1).
2 solutions
p (X,Y):- !, q (X), r (X,Y). p (c, c1).
5 solutions
p(X, Y):- q(X), r(X, Y). p(c, c1).
q(a). q(b). r(a, a1). r(a, a2). r(b, b1). r(b, b2). r(b, b3).
If-then-else
• Max function returning the larger of two numbers
max(X,Y,X) :- X >= Y.
max(_,Y,Y).
• This will produce surprising results, consider
?- max(7,5,X).
Call: (6) max(7, 5, _G1326) ? creep Call: (7) 7>=5 ? creep
Exit: (7) 7>=5 ? creep
Exit: (6) max(7, 5, 7) ? creep
Redo: (6) max(7, 5, _G1326) ? creep Exit: (6) max(7, 5, 5) ? creep
If-then-else with the Cut
• Solution: Use an explicit test
max(X,Y,X) :- X >= Y.
max(X,Y,Y) :- X < Y.
• Solution: Use the Cut for efficiency
max(X,Y,X) :- X >= Y, !.
max(_,Y,Y).
?- max(7,5,X).
Call: (6) max(7, 5, _G1326) ? creep Call: (7) 7>=5 ? creep
Exit: (7) 7>=5 ? creep
Exit: (6) max(7, 5, 7) ? creep
max (X, Y, Y): – X<=Y. max (X, Y, X): - X>Y.
max (X, Y, Y): – X<=Y,!. max (X, Y, X).
max (X, Y, Y): - X<= Y,!. max (X, Y, X): - X>Y.
max (X,Y, Z): – X<=Y,!,Y= Z. max (X, Y, X).
Predicate fail
• Thefailpredicatealwaysfails.
• CombinedwiththeCutwegetnegation
is_false(P) :- P, !, fail. is_false(P).
• TheclausePiseithertruethenthegoalis_falsefails. – Subgoal P is true, Cut is true cutting backtracking
off, fail succeeds making the goal is_false(P) fail. – If subgoal P fails, the second rule succeeds.
• Thecombinationiscalledcut-fail.
Simple Example with Negation
single_student(X):- not(married(X)), student(X).
student(joe).
married(jean).
? – single_student (joe). true
? – single_student (jean). false
? - single _student (X).
Negation: not or \+
• Thenegationpredicatenot(F)withFatermcanalso be written with the operator \+F
– Associative prefix operator
• Negationbyfailure
– Prolog proofs the success of a goal not(F) by
showing that it can not satisfy F.
• Remember that Prolog may also fail to proof F for trivial reasons, e.g., it may simply missing facts in its database.
– Prolog’s proof strategy is referred to as closed world assumption.
Negation: not or \+
?- \+ (2 = 4). true.
?- not(2 = 4). true.
http://www.cse.unsw.edu.au/~billw/prologdict.html#negation
The cut-fail
canEnterPolice (P): - aAcriminalFolder (P),!, fail.
Used when demonstrating a condition invalidates all others
2021-03-04
Not Equals or Difference
• Wehaveseentheoperatornotequalsbefore.
• Binarydifferenceoperatoristheoppositeofa successful unification of its’ arguments.
– This operator is equivalent to the following definition
X =\= Y :- not(X = Y).
– expressed with cut- fail X =\= X :- !,fail. X =\= Y.
Interval Predicate Again
• Recall previous definition of a test for an interval and a separate definition of a generator for interval
intervalTest(X,L,H):- X>=L,X=