CODEWITHSUNDEEP
prolog
Jean Hans
Jean Hans

Reputation: 63

How to fix this reverse function so it doesn't stack overflow?

I got this reverse function from http://www.learnprolognow.org/lpnpage.php?pagetype=html&pageid=lpn-htmlse25:

accRev([H|T],A,R):-  accRev(T,[H|A],R). 
accRev([],A,A).

rev(L,R):-  accRev(L,[],R).

This works for things like

?- rev([a,b,c], R).
R = [c,b,a]

But I get a stack overflow with this:

?- rev(L, [c,b,a]).

Why does this cause a stack overflow? Is there a way to make both work?:

Upvotes: 1

Views: 72

Answers (1)

false
false

Reputation: 10102

?- rev(L, [c,b,a]).

Why does this cause a stack overflow?

Sssh... you are revving the Prolog engine.

Actually, two reasons: First, the query does not terminate. And then, it searches solutions in a rather ineffective manner.

Let me "solve" this problem, by addressing the second reason first. Just exchange the two clauses of accRev/3. This changes the answer from:

?- rev(L, [c,b,a]).
   resource_error(_). % ERROR: Out of local stack

to

?- rev(L, [c,b,a]).
   L = [a, b, c]█

nice - or almost. Note that Prolog did not put a . at the end of the solution. That means it says: Want more of this? So by typing ; you get:

?- rev(L, [c,b,a]).
   L = [a, b, c]
;  resource_error(_). % ERROR: Out of global stack

So we "almost" solved the problem. We found a solution, but Prolog still does not terminate. This illustrates nicely one property of pure Prolog programs:

Exchanging clauses may influence how solutions/answers are found, but it does not affect termination.

The best way to ensure that a goal actually terminates is to "switch off" all the answers we get by adding false:

?- rev(L, [c,b,a]), false.
   resource_error(_). % ERROR: Out of global stack

This error now occurs in the very same way no matter how the clauses are arranged. In fact, the cause can be narrowed down to the following :

rev(L,R):-
   accRev(L,[],R), false.

accRev([],A,A) :- false.
accRev([H|T],A,R):-
   accRev(T,[H|A],R), false.

Note the R which is simply passed further on. It thus has no influence on termination whatsoever.

Observe, however, that the length of L and R are the same ...

So maybe consider same_length/2 first, it could solve this directly.

same_length([], []).
same_length([_|L], [_|R]) :-
   same_length(L, R).

rev_better(L, R) :-
   same_length(L, R),
   rev(L, R).

Or, if you are into "efficiency", just observe that same_length/2 can be folded directly:

rev_folded(L, R) :-
   accrev(L, [],R, R).

accrev([], R,R, []).
accrev([E|L], R0,R, [_|Rx]) :-
   accrev(L, [E|R0],R, Rx).

Upvotes: 4

Related Questions