Please explain the cut in the Bubblesort Prolog program?

Question

I'm currently working trough the Bratko Prolog book and I am looking at the bubble-sort Program. I can't seem to figure out why the cut(!) is necessary. Say the cut isn't there, and Prolog would backtrack, how could it possibly find bad answers? Because if I leave the cut out of it, Prolog begins by giving me the correct answer but then also gives alternative bad answers.

As I see it, how can swap ever return a non sorted list? And how is it possible that a non sorted list ever hits the goal bubblesort(Sorted, Sorted).

Unless of course the first List is also being changed... Can't get my head around it.

Prolog BubbleSort program:

gt(X,Y) :- X > Y.

bubblesort(List, Sorted) :-
  swap(List, List1), !,           % A useful swap in List?
  bubblesort(List1, Sorted).
bubblesort(Sorted, Sorted).       % Otherwise list is already sorted

swap([X,Y|Rest], [Y,X|Rest]) :-   % Swap first two elements
  gt(X,Y).
swap([Z|Rest], [Z|Rest1]) :-      % Swap elements in tail
  swap(Rest, Rest1).

Leaving the cut of out it gives me:

?- bubblesort([5,7,3,6,8,9,2,6], Sorted).

Sorted = [2, 3, 5, 6, 6, 7, 8, 9] ;

Sorted = [2, 3, 5, 6, 7, 6, 8, 9] ;

Sorted = [2, 3, 5, 6, 7, 8, 6, 9] ;

Sorted = [2, 3, 5, 6, 7, 8, 9, 6] ;

I think that somehow I get it, but I am not sure. Could it be that at a certain moment, it backtracks over swap(List, List1) going to the second bubble-sort predicate and hitting the goal, meaning the two lists Sorted are equal?

In English, does this mean that bubble-sort needs to continue doing swaps until no more swaps are possible, but then needs to terminate? Or does it mean that every-time a successful swap has been done, there's no use backtracking over that success?

Answer 1

There are several possibilities to make the goal swap(List, List1) fail. Either List is a list of length 0 or 1 ; or it does not contain two immediately succeeding elements where the second is smaller than the first.

The cut is placed in such a manner that it both cuts swap/2 and the alternative of bubblesort/2.

This is a good example, where a "deep cut" (cutting deep into swap/2) still works somewhat nicely. However, such situations are very rare. Most of the time, the cut cuts too much. The largest majority of such programs is very brittle to use, even more so, if the second argument is given already. They are often not steadfast.

Ah, I almost missed it: Even in this program, we have bubblesort(nonlist,L) succeeding, or bubblesort([1|nonlist],L) which probably is not intended and leads to subtle programming errors.

There is also another reason why this program does not present the ideal logic programming style: The second rule of bubblesort/2 when read alone says: Everything is a sorted list`. To understand this, we have to read both rules at the same time and narrow it down to Everything but ....

In English, does this mean that bubble-sort needs to continue doing swaps until no more swaps are possible, but then needs to terminate? Or does it mean that every-time a successful swap has been done, there's no use backtracking over that success?

It is the first procedural meaning that applies here. And certainly, backtracking over the success to the second clause of bubblesort/2 would be an error.

A further quite unintuitive detail which is not specific to the cut, is that in addition to numbers, the program also succeeds for expressions like bubblesort([1,1+1],L) which again might lead to subtle differences.

Answer 2

I just want to add that if-then-else is a far more appropriate language construct than !/0 to express the intention (and I know you did not choose !/0 on your own here):

bubblesort(List0, List) :-
        (   swap(List0, List1) ->
            bubblesort(List1, List)
        ;   List0 = List
        ).

You can change the -> to *-> to see alternative solutions of swap/2 as well, i.e., if you change this to:

bubblesort(List0, List) :-
        (   swap(List0, List1) *->
            bubblesort(List1, List)
        ;   List0 = List
        ).

Then you get for example:

?- bubblesort([5,7,3,6,8,9,2,6], Ascending).
Ascending = [2, 3, 5, 6, 6, 7, 8, 9] ;
Ascending = [2, 3, 5, 6, 6, 7, 8, 9] ;
Ascending = [2, 3, 5, 6, 6, 7, 8, 9] .

As you see, all of these lists are non-decreasing, as you already expected.