CODEWITHSUNDEEP
prologbacktrackingbacktraceprolog-cut
kbirk
kbirk

Reputation: 4022

Prolog cut behaviour doesn't make sense to me

I've come across very strange behaviour (to me) regarding a particular cut. From what I understood, once the execution passes a cut, it cannot backtrack back above it. But that is exactly what this code does. Can someone explain why it does this?

Here is the code:

example([],[]).
example([X,Y,Z|Tail],[Z|NewTail]) :-
    X < Y,
    example(Tail,NewTail).
example([X,Y,Z|Tail],[X|NewTail]) :-
    Y < Z,  
    example(Tail,NewTail).
example([X,Y,Z|Tail],[Y|NewTail]) :-
    X < Z,  
    example(Tail,NewTail).

Now with no cuts, the output is as follows for this particular input:

example([1,3,2,4,5,6],L).
L = [2, 6] ;
L = [2, 4] ;
L = [2, 5] ;
L = [3, 6] ;
L = [3, 4] ;
L = [3, 5].

Now if I add the following cut:

example([],[]).
example([X,Y,Z|Tail],[Z|NewTail]) :-
    X < Y,
    example(Tail,NewTail).
example([X,Y,Z|Tail],[X|NewTail]) :-
    Y < Z,
    !,                              <---- cut here
    example(Tail,NewTail).
example([X,Y,Z|Tail],[Y|NewTail]) :-
    X < Z,  
    example(Tail,NewTail).

I would expect it to return 

L = [2,6] ;
L - [2,4].

As once it passes the cut on the third clause it can no longer back trace.

Instead it returns:

L = [2, 6] ;
L = [2, 4] ;
L = [3, 6] ;
L = [3, 4]

Why is this happening? It literally jumps back over the cut and begins executing clause 4, why?

Why does it execute clause 4, when if i move the cut up to clause 2:

example([],[]).
example([X,Y,Z|Tail],[Z|NewTail]) :-
    X < Y,
    !,                              <---- cut here
    example(Tail,NewTail).
example([X,Y,Z|Tail],[X|NewTail]) :-
    Y < Z,      
    example(Tail,NewTail).
example([X,Y,Z|Tail],[Y|NewTail]) :-
    X < Z,  
    example(Tail,NewTail).

It only produces:

L = [2, 6].

Why does the cut work in clause 2, but not in clause 3? This makes no sense to me.

Upvotes: 2

Views: 186

Answers (1)

CapelliC
CapelliC

Reputation: 60034

The cut in last code snippet works twice, thus preventing the alternative expected:

?- leash(-all).
true.

?- trace.
true.

[trace]  ?- example([1,3,2,4,5,6],L).
   Call: (6) example([1, 3, 2, 4, 5, 6], _G6183)
   Call: (7) 1<3
   Exit: (7) 1<3
   Call: (7) example([4, 5, 6], _G6267)
   Call: (8) 4<5
   Exit: (8) 4<5
   Call: (8) example([], _G6270)
   Exit: (8) example([], [])
   Exit: (7) example([4, 5, 6], [6])
   Exit: (6) example([1, 3, 2, 4, 5, 6], [2, 6])
L = [2, 6].

Upvotes: 2

Related Questions