CODEWITHSUNDEEP
prologfailure-slice
iiMouad
iiMouad

Reputation: 35

why prolog is entering infinite loop?

I made this code so basically, it detects if the array in the first argument is the reverse array in the second argument, it works well but when I want to have the reversed array for a giving array, first it gives me the right answer than if I do ";" to have another answer I expect to get false which is normal, but Prolog just enters an infinite loop.

here is my code :

rev([],[]).
rev([X|A],B):- append(C,[X],B), rev(A,C) .

and this is a test to explain the problem: enter image description here


?- rev([4,3,9,9],[9,9,3,4]).
true ;
false.

?- rev([4,3,9,9],[4,2,1,4]).
false.

?- rev([4,3,9,9],Result).
Result = [9, 9, 3, 4] ;
.
.
.

Waiting for Prolog. Close again to force termination.

Upvotes: 2

Views: 367

Answers (3)

false
false

Reputation: 10102

First of all, is this such a big problem? From time to time you do not get a clear response from Prolog but instead it just loops. So sometimes it behaves like a runaway engine. Certainly not ideal. But it could be worse! In particular, if it would produce an incorrect answer. Like failing, when there are solutions.

To understand why Prolog loops in your case, it helps to put some falsework into your program. By adding goals false. In this manner we will see just the real reason:

rev([],[]) :- false.
rev([X|A],B):- append(C,[X],B), false, rev(A,C).

?- rev([4,3,9,9],Result), false.
   loops.

Such a program is called a . The nice property here is that if this failure slice loops, also your original program will loop. But often this slice is much smaller, so the error is easier to detect.

In order to get rid of that looping, you need to modify something in the visible part. One possibility would be to exchange the two goals. This would make this query terminate. But then,

rev([],[]) :- false.
rev([X|A],B):- rev(A,C), false, append(C,[X],B).

?- rev(L, [9,9,3,4]), false.
   loops.

So by just exchanging goals, things are not solved in general.

To solve this for both cases, both lists have to be taken into account prior to the first goal.

rev(Xs, Ys) :-
   rev(Xs, Ys, Ys).

rev([], [], []).
rev([X|Xs], Ys, [_|Zs]) :-
   rev(Xs, Xsr, Zs),
   append(Xsr,[X],Ys).

So a third argument was added, which ensures that the length of Ys may influence termination.

There are actually better more efficient ways to express this. But conceptually this solution is simpler to understand.

Upvotes: 3

CapelliC
CapelliC

Reputation: 60014

I liked the creative approach of your code... then I dare to suggest a fix, in plain old style, instead of a rewrite:

rev([],[]).
rev([X|A],B):- append(C,[X],B), rev(A,C), !.

Upvotes: 0

Nicholas Carey
Nicholas Carey

Reputation: 74257

Your rev/2 is invoking append/3 with two unbound variables. On backtracking, it's generating unbound lists of ever-increasing length:

SWI-Prolog Swish screenshot

That's a feature of append/3.

The "classic" reversal of a list is this:

rev( [] , [] ) .
rev( [X|Xs] , Ys ) :- rev(Xs,X1), append(X1,[X],Ys) .

It runs on O(N2) time. And it will blow the stack given a list of sufficient length. And if the 1st argument to rev/2 is unbound, you'll go into a recursive loop (until the stack overflows).

Instead, use a helper predicate with an accumulator. It's a common Prolog idiom to have a "public" predicate that does little more than invoke a "private" helper predicate of the same name, but with different arity, where the extra arguments carry the necessary state to accomplish the task at hand.

rev( []     , Ys , Ys ) .
rev( [X|Xs] , Ts , Ys ) :- rev(Xs,[X|Ts],Ys).

Now you have something that is (1) tail recursive, and (2) runs in O(n) time and space.

Once you have that, the "public" rev/2 is just this:

rev( Xs, Ys ) :- rev(Xs,[],Ys) .

where we seed the accumulator with the empty list.

Note however, that this rev/2 is not bi-directional. Invoking rev(Xs,[a,b,c]) will work successfully, but backtracking into it will result in an infinite recursive loop.

To fix that, simply add some type checking into rev/2. To successfully reverse a list, at least one of Xs or Ys must be bound. That gives us this:

rev( Xs , Ys ) :- nonvar(Xs), !, rev( Xs, [] , Ys ) .
rev( Xs , Ys ) :- nonvar(Ys),    rev( Ys, [] , Xs ) .

Putting it all together, you get:

https://swish.swi-prolog.org/p/RdhuxIlF.pl

rev( Xs , Ys ) :- nonvar(Xs), !, rev( Xs, [] , Ys ) .
rev( Xs , Ys ) :- nonvar(Ys),    rev( Ys, [] , Xs ) .

rev( []     , Ys , Ys ) .
rev( [X|Xs] , Ts , Ys ) :- rev(Xs,[X|Ts],Ys).

Upvotes: 1

Related Questions