Is this prolog sort program overflowing the stack simply because of its complexity--or because it's wrong?

Question

In a previous post, I eventually figured out how to write gprolog program that checks whether one list is a permutation of another. As far as I know, it works.

Now, I am creating a mysort predicate that combines the permutation predicate with this one (also working, as far as I can tell):

sorted([]).   
sorted([L]) :- !.  
sorted([L|[T|TT]]) :- L @=< T, sorted([T|TT]).

Since my original perm predicate was designed to terminate with ! as soon as it reached an answer, I made some modifications to allow mysort to check through possibilities. Here is mysort, its special backtrack_perm, and the overlap with the old perm (which I simply modified as a slight change to backtrack_perm):

perm([],[]).
perm([LH|LT],R) :-
   backtrack_perm([LH|LT],R),
   !.

perm_recurse([],X). 
perm_recurse([LH|LT],R) :-
   member(LH,R),
   select(LH,[LH|LT],X),
   select(LH,R,Y),
   perm_recurse(X,Y),
   !. 

mysort(L,M) :-
   backtrack_perm(L,M),
   sorted(M),
   !.  

backtrack_perm([],[]).
backtrack_perm([LH|LT],R) :-
   length([LH|LT],A),
   length(R,B),
   A == B,
   member(LH,R),
   select(LH,[LH|LT],X),
   select(LH,R,Y),
   perm_recurse(X, Y).  

Though its components appear to work fine as mentioned, mysort causes a stack overflow on some inputs, such as mysort([5,3,2],X). In an already-sorted list, such as mysort([2,3,5],X), or even a partial one like mysort([3,2,5],X), the trace can be long, but it does get the answer. Because of this--and since a smaller completely-backwards list like [2,1] works fine--I'm thinking the problem is just that the process itself is too space/time consuming with all of those permutations.

Without stepping too deeply into the longer traces, would it be safe to assume that this is the case? Or should Prolog/the computer be able to handle this without trouble, meaning I need to rethink the algorithms?

Answer 1

@Will Ness already gave you a fine definition for perm/2. But let's look at your program. In fact, you have very odd behavior: sometimes it seems to work, and sometimes not. How can we narrow that down? Tracing does not seem to be an option, as you have experienced yourself.

Here is a particular debugging technique, called slicing. I will modify your program a bit to see what is going on, by inserting goals false. The resulting program is called a failure slice. And I will use the query:

?- mysort([1],[2|_]).
Fatal Error: global stack overflow

Clearly, a list with a single 1 as element cannot correspond to a list starting with 2. So ideally, this should fail. And it cannot be that complex. Can it?

@larsmans gave you already a hint, but I will try it out myself. I will add the following goals false into your program. In this manner certains parts will never be called, they are striked through. And certain predicates will not be called at all, so I will no longer show them:

?- mysort([1],[2|_]).

mysort(L,M) :-
   backtrack_perm(L,M), false,
   sorted(M),
   !.  

backtrack_perm([],[]) :- false.
backtrack_perm([LH|LT],R) :-
   length([LH|LT],A),
   length(R,B), false,
   A == B,
   member(LH,R),
   select(LH,[LH|LT],X),
   select(LH,R,Y),
   perm_recurse(X, Y).  

This failure slice is in a sense, as bad as your program: Again, it does not terminate. But it is smaller. To fix the problem you have to do something in that fragment. For, as long as that part remains as is, the problem will persist.

In this case, it is the goal length(R,B) which is the culprit: The variable B occurs here for the first time, so it is uninstantiated. And also R is uninstantiated. What are the answers for the goal length(R, B). Try it out!

?- length(R, B).
   B = 0 R = []
;  B = 1, R = [_]
;  B = 2, R = [_,_]
;  B = 3, R = [_,_,_]
;  B = 4, R = [_,_,_,_]
;  B = 5, R = [_,_,_,_,_]
;  ... .

So there are infinitely many answers. Therefore your program does not terminate.

This problem can be easily fixed by replacing length(R, B), A == B by length(R, A).

?- mysort([9,1,2,3,4,5,6,7,8],L).
   L = [1,2,3,4,5,6,7,8,9]
(21841 ms) yes

Some more remarks: The ! in your programs are red cuts, they might cause you a lot of trouble. And then, the execution time is not that great: 21 seconds for sorting 9 elements does not sound very cool. But please keep in mind that your description essentially says: I want a permutation, that is ascending. You do not say more than that. Given that very scarce information, Prolog is at least capable of finding the right answers. And it is even quite space efficient.

How to turn this program into a more efficient one, see this answer.