CODEWITHSUNDEEP
prolog
aioobe
aioobe

Reputation: 421150

Prolog: reverse([], A) vs reverse(A, [])

I can't make any sense out of this: If I give Prolog reverse([], A). it works fine, if I give it reverse(A, []). and answer ; on first suggestion it hangs!

Why? (Same result for both GNU Prolog and SICStus Prolog!)

aioobe@r60:~$ prolog
GNU Prolog 1.3.0
By Daniel Diaz
Copyright (C) 1999-2007 Daniel Diaz
| ?- reverse([], A).

A = []

yes
| ?- reverse(A, []).

A = [] ? ;

Fatal Error: global stack overflow (size: 32768 Kb,
environment variable used: GLOBALSZ)

aioobe@r60:~$

Upvotes: 3

Views: 1744

Answers (2)

irvins
irvins

Reputation: 1

My reverse did the same, because I assumed argument 1 would be instantiated (i.e. reverse(+,?), as above), knowing that my Prolog would index on it. Here:

reverse(L, R) :- reverse_1(L, [], R).

reverse_1([], X, X).      % <-- doesn't loop on unbound arg #1 if this clause cuts
reverse_1([A|As], X, R) :-
   reverse_1(As, [A|X], R).

Upvotes: 0

Sage Mitchell
Sage Mitchell

Reputation: 1583

Looks like an overzealous optimization for a built-in predicate to me. The same problem occurs regardless of the contents of the list in the second argument. Based on the GProlog manual this is a bug. Notice that the template for reverse is

reverse(?list, ?list)

And further that ? means "the argument can be instantiated or a variable."

SWI-Prolog version 5.6.64 gives the expected result.

?- reverse([], A).
A = [].

?- reverse(A, []).
A = [] ;
false.

Upvotes: 4

Related Questions