CSc 372 - Comparative Programming Languages
22 : Prolog -- Negation

Christian Collberg

Department of Computer Science

University of Arizona

The Cut

1 Cuts & Negation

The cut (!) is is ued to affect Prolog's backtracking. It can be used to

reduce the search space (save time).
tell Prolog that a goal is deterministic (has only one solution) (save space).
construct a (weak form of) negation.
construct if_then_else and once predicates.

2 Cuts & Negation

The cut reduces the flexibility of clauses, and destroys their logical structure.
Use cut as a last resort.
Reordering clauses can sometimes achieve the desired effect, without the use of the cut.
If you are convinced that you have to use a cut, try using if_then_else, once, or not instead.

3 The Cut

The cut succeeds and commits Prolog to all the choices made since the parent goal was called.

Cut does two things:

commit:: Don't consider any later clauses for this goal.
prune:: Throw away alternative solutions to the left of the cut.

4 The Cut

Cut1

5 The Cut

Cut2

The Boxflow Model

6 The Boxflow Model

Boxflow1

7 The Boxflow Model

Boxflow2

8 The Cut

Boxflow-Cut

Classifying Cuts

9 Classifying Cuts

grue

No effect on logic, improves efficiency.

green

Prune away

irrelevant proofs
proofs which are bound to fail

blue

Prune away

proofs a smart Prolog implementation would not try, but a dumb one might.

red

Remove unwanted logical solutions.

10 Green Cuts - Merge

Produce an ordered list of integers from two ordered lists of integers.

1#1

11 Green Cuts - Merge

Merge1

12 Green Cuts

Still, there is no way for Prolog to know that the clauses are mutually exclusive, unless we tell it so. Therefore, Prolog must keep all choice-points (points to which Prolog might backtrack should there be a failure) around, which is a waste of space.
If we insert cuts after each test we will tell Prolog that the procedure is deterministic, i.e. that once one test succeeds, there is no way any other test can succeed. Prolog therefore does not need to keep any choice-points around.

13 Green Cuts - Merge

2#2

14 Green Cuts - Merge

Merge2

15 Red Cuts - Abs

3#3

16 Red Cuts - Abs

4#4

17 Red Cuts - Intersection

Find the intersection of two lists A & B, i.e. all elements of A which are also in B.

5#5

18 Red Cuts - Intersection

6#6

19 Red Cuts - Intersection

Intersect1

20 Red Cuts - Intersection

Intersect2

21 Red Cuts - Intersection

Intersect3

22 Red Cuts - Intersection

7#7

23 Red Cuts - Intersection

Intersect4

24 Blue Cuts

First clause indexing will select the right clause in constant time:

8#8

First clause indexing will select the right clause in linear time:

9#9

25 Blue Cuts

10#10

26 Red Cuts - Once

11#11

27 Red Cuts - Once

Red cuts prune away logical solutions. A clause with a red cut has no logical reading.

12#12

28 Red Cuts - Abs

13#13

29 IF-THEN-ELSE

14#14

15#15

30 IF-THEN-ELSE

16#16

Negation

31 Open vs. Closed World

How should we handle negative information?

Open World Assumption:

If a clause P is not currently asserted then P is neither true nor false.

Closed World Assumption:

If a clause P is not currently asserted then the negation of P is currently asserted.

32 Open vs. Closed World

17#17

Open World Assumption:

Dahlin, Thern, and Andersson are strikers, but there may be others we don't know about.

Closed World Assumption:

X is a striker if and only if X is one of Dahlin, Thern, and Andersson.

33 Negation in Prolog

Prolog makes the closed world assumption.
Anything that I do not know and cannot deduce is not true.
Prolog's version of negation is negation as failure.
not(G) means that G is not satisfiable as a Prolog goal.

18#18

34 Prolog Execution - Not

Some Prolog implementations don't define not at all. We then have to give our own implementation:
19#19
Some implementations define not as
- the operator not;
- the operator 20#20;
- the predicate not(Goal).
gprolog uses 20#20.