Prolog Ignoring Goal Ordering?

Question

I can't quite seem to wrap my head around some of the behaviour of prolog (gprolog). As some background, rotate is supposed to compare two lists and see if they have been shifted (As below).

?- rotate(1,[4,1,2,3],[1,2,3,4]).

should return true. However, prolog doesn't seem to be respecting the rule ordering when the above question is asked.

rotate(0,[],[],[]).     
%base case

rotate(0,[],[H|T1],[H|T2]):- rotate(0,[],T1,T2).        
%recurse over the remainder list (the first list from S to the end)

Prolog will ignore the predicate directly below when

rotate(S,[H|T1],[H|T2],L):-S=:=0,rotate(0,T1,T2,L).         
%recurse over the elements from S to the end of list1

backtracking from this other predicate (directly below).

rotate(S,[H|T1],L,T2):-S > 0,S1 is S - 1,rotate(S1,T1,L,[H|T2]).        
%add elements 1 to S into the remainder list

rotate(S,L1,L2):-len(L1,Len),S1 is S mod Len,!,rotate(S1,L1,L2,[]). 
%ensure the shift is not out of bounds, call rotate/4

%utility function because couldn't use length
len([],Ret,Ret).
len([_|T],Len,Ret):-Len1 is Len+1,len(T,Len1,Ret).
len(L,Len):-len(L,0,Len).

I discovered this behaviour by tracing it, and am frankly perplexed as to why it won't backtrack and hit the next predicate, instead it fails and returns false.

I'm also open to better ways to do this, since it's practise for a midterm.

Maybe this answer is interesting for you. The predicate describes arbitrary rotations and is a true relation (works in all directions). — tas

CapelliC CapelliC · Accepted Answer · 2017-10-26T04:39:50

Sorry I don't have an answer for your primary question. Tracing the execution to nail down the backtracking behaviour is a kind of 'last chance' when debugging Prolog, you're better to trust the engine - also because it happens the debugger is buggy sometime :)

When you have N alternatives for a predicate, you could place the cut immediately after the test for every of the first N-1 clauses, and then you could (eventually) avoid the test in the last one.

The purpose is clear: commit the execution to the successful path. Instead, you did the inverse, placing the cut in the last rotate/4 clause, where it is useless. So, this should not be the culprit, just a nuance indicating you have not yet the Prolog programming model at hand...

I would also suggest to avoid to 'early optimize' your assignment: when the logic is correct, the program should work independently of the S being larger than the list length. Instead, maybe you should think what could happen if a negative S is given as argument.

If you debug 'declaratively', your predicate doesn't seem to work:

?- rotate(2,[4,1,2,3],R). 
R = [2, 3, 1, 4] ;
false

I would instead expect [2, 3, 4, 1], i.e. the outcome of this simpler definition

rotate(N, L, R) :- N > 0, N1 is N-1, rotate(L, T), rotate(N1, T, R).
rotate(0, L, L).

rotate([X|Xs],R) :- append([Xs,[X]],R).

rotate/2 uses the handy append/2 helper, to 'send to back' the head. I'm sure you will have no problem to replace it with append/3 or your own definition...

Prolog Ignoring Goal Ordering?

1 Answers