CS计算机代考程序代写 prolog .

.
.
.

.

.
.
.

.

.
.
.

.

.
.
.

.

.
.
.

.

.
.
.

.

.
.
.

.

.
.
.

.

.
.
.

.

.
.
.

.

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.