.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Declarative Programming
More Non-logical Features of Prolog
Geraint A. Wiggins
Professor of Computational Creativity
Department of Computer Science
Vrije Universiteit Brussel
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Commit operators
▶ In logic programming, a commit operator allows us to
choose a particular proof of a predicate over all others –
we commit to a particular choice
▶ Warning: commits are generally very difficuly to account
for logically, and it is usually wise to avoid their use.
▶ Prolog has two commit operators,
! cut – prevents backtracking within the predicate in
which it appears;
-> local cut – prevents backtracking into and within the
goal to its left.
▶ Oddly, we write ! as though it were a literal in Prolog,
and not an operator
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Cut
▶ Example
p(a). p(a) :- !.
p(b). p(b).
?- p(X). ?- p(X).
X = a ? ; X = a ? ;
X = b ? ; false
false
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Cut (2)
▶ Example 2:
p(a). p(a).
p(b) :- !. p(b).
p(c). p(c) :- !.
?- p(X). ?- p(X).
X = a ? ; X = a ? ;
X = b ? ; X = b ? ;
false X = c ? ;
false
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Cut (3)
▶ Example 3:
p(a). p(a).
p(b) :- !. p(b) :- !.
p(c). p(c).
?- p(c). ?- ( X=b; X=c ), p(X).
true X = b ? ;
X = c ? ;
false
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Guarded commit
▶ We can use ! in a logically friendly way, by building
clauses of this general form:
p(X) :- guard1(X),!,call1(X).
p(X) :- guard2(X),!,call2(X).
…
p(X) :- guardN(X),!,callN(X).
where the guardI predicates are mutually exclusive.
▶ This is the commonest form of use of what we call a
“green” cut
▶ As usual, green means “go on, it’s OK”
▶ So a red cut is not acceptable
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Red & Green Cuts
▶ A green cut is one which can be removed without
changing the logical behaviour of the program
▶ For example,
max( X, Y, X ) :- X > Y, !.
max( X, Y, Y ) :- X =< Y.
▶ The effect here is purely procedural;…
▶ …we don’t need to test the =< condition if > has
succeeded
▶ So we save some processing power
Be careful when using green cuts!
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Red & Green Cuts (2)
▶ A red cut is one which can not be removed without
changing the logical behaviour of the program
▶ For example,
max( X, Y, X ) :- X > Y, !.
max( X, Y, Y ).
▶ If we remove the !, we can get an incorrect result on
backtracking, because the logical semantics of the
program does not match the intended interpretation
Do not use red cuts!
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Local Cut
▶ Local cut -> can be even more unfriendly than !
▶ In some circumstances, -> behaves exactly like logical
implies
▶ In others, it has false proper logical interpretation
▶ Example:
p( X ) :- ( q( X ) -> r( X )).
logically should mean “p(X) is true if r(X) is true
whenever q(X) is true”
▶ In fact, it means “find the first solution for q(X), and
then try to prove r(X); if there is false solution for q(X),
fail”
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Local Cut (2)
▶ Because of local cut’s procedural behaviour, incorrect
results can be obtained
▶ Example:
p(a). p(b).
p(b). p(a).
q(b). q(b).
?- p(X) -> q(X). ?- p(X) -> q(X).
false X = b ? ;
false
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Local Cut (3)
▶ Local cut is commonly used to implement an
“if-then-else” construction
?- ( p(X) -> q(X); r(X) ).
which is supposed to mean “if p(X) is true, prove q(X);
otherwise, prove r(X)”.
▶ However, this is only guaranteed to be correct if p(X) is
fully instantiated when the call is made.
In SWI Prolog, -> ; is a special operator, which
means (roughly) if-then-else.
In some Prologs, backtracking on ; can give
incorrect answers.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Implementing negation as failure
▶ Once we have !, we can implement NAF
\+ Goal :- call( Goal ),
!,
fail.
\+ _Goal.
call/1 attempts prove the goal given as its argument;
fail/0 is always false.