Prolog lists Error: out of global stack
Question
I'm trying to write a rule in prolog
adjacent(X,Y,Zs)
, as true
if X
and Y
are adjacent to each other in the list Zs
.
I currently have:
append([],L,L).
append([H|T],L,[H|LT]):-append(T,L,LT).
sublist(S,L):-append(_,S,P),append(P,_,L).
adjacent(X,Y,Zs):-sublist([X,Y],Zs).
test:
1 ?- sublist([1,2],[1,2,3,4]).
true .
2 ?- sublist([1,3],[1,2,3,4,5]).
ERROR: Out of global stack
3 ?-
Do you guys have any ideas? Thanks in advance.
Solution
adjacent(X,Y, [X,Y|_]).
adjacent(X,Y, [Y,X|_]). % remove this if you want just Y after X
adjacent(X,Y, [_|T]) :- adjacent(X,Y,T).
that should work.
also, you have a predicate in the lists library called nextto(?X, ?Y, ?List)
that will do the same (but keep in mind that the semantics of this predicate is that Y
follows X
in the list, not just plain adjacent in any order).
OTHER TIPS
Using DCGs will represent the problem in the most graphical way possible:
... --> [] | [_], ... .
adjacent(X,Y,Seq) :- phrase((...,[X,Y],...), Seq).
Edit: Thanks to @fortran's comment, another definition might be:
adjacent(X,Y,Seq) :- phrase((...,( [X,Y] | [Y,X] ),...), Seq).
The behaviour of your program it's rather complex. The bug is in the sublist/2.
To trace I've renamed the predicates adding 1 to the names, but the definition it's taken verbatim from your code.
You can see that there are calls to append1 (labelled 9,10,11,...) that progressively expand the unbound first argument.
?- trace,sublist1([1,3],[1,2,3,4]).
Call: (8) sublist1([1, 3], [1, 2, 3, 4]) ? creep
Call: (9) append1(_G377, [1, 3], _G379) ? creep
Exit: (9) append1([], [1, 3], [1, 3]) ? creep
Call: (9) append1([1, 3], _G378, [1, 2, 3, 4]) ? creep
Call: (10) append1([3], _G378, [2, 3, 4]) ? creep
Fail: (10) append1([3], _G378, [2, 3, 4]) ? creep
Fail: (9) append1([1, 3], _G378, [1, 2, 3, 4]) ? creep
Redo: (9) append1(_G377, [1, 3], _G379) ? creep
Call: (10) append1(_G374, [1, 3], _G377) ? creep
Exit: (10) append1([], [1, 3], [1, 3]) ? creep
Exit: (9) append1([_G373], [1, 3], [_G373, 1, 3]) ? creep
Call: (9) append1([_G373, 1, 3], _G384, [1, 2, 3, 4]) ? creep
Call: (10) append1([1, 3], _G384, [2, 3, 4]) ? creep
Fail: (10) append1([1, 3], _G384, [2, 3, 4]) ? creep
Fail: (9) append1([_G373, 1, 3], _G384, [1, 2, 3, 4]) ? creep
Redo: (10) append1(_G374, [1, 3], _G377) ? creep
Call: (11) append1(_G380, [1, 3], _G383) ? creep
Exit: (11) append1([], [1, 3], [1, 3]) ? creep
Exit: (10) append1([_G379], [1, 3], [_G379, 1, 3]) ? creep
Exit: (9) append1([_G373, _G379], [1, 3], [_G373, _G379, 1, 3]) ? creep
Call: (9) append1([_G373, _G379, 1, 3], _G390, [1, 2, 3, 4]) ? creep
Call: (10) append1([_G379, 1, 3], _G390, [2, 3, 4]) ? creep
Call: (11) append1([1, 3], _G390, [3, 4]) ? creep
Fail: (11) append1([1, 3], _G390, [3, 4]) ? creep
Fail: (10) append1([_G379, 1, 3], _G390, [2, 3, 4]) ? creep
Fail: (9) append1([_G373, _G379, 1, 3], _G390, [1, 2, 3, 4]) ? creep
Redo: (11) append1(_G380, [1, 3], _G383) ? creep
Call: (12) append1(_G386, [1, 3], _G389) ? creep
Exit: (12) append1([], [1, 3], [1, 3]) ? creep
Exit: (11) append1([_G385], [1, 3], [_G385, 1, 3]) ? creep
Exit: (10) append1([_G379, _G385], [1, 3], [_G379, _G385, 1, 3]) ? creep
Exit: (9) append1([_G373, _G379, _G385], [1, 3], [_G373, _G379, _G385, 1, 3]) ? creep
Call: (9) append1([_G373, _G379, _G385, 1, 3], _G396, [1, 2, 3, 4]) ? creep
...
Anyway, I think that you have taken the right path to learn Prolog. It's correct to master usage of builtins, that behind deceptively simple definition often hide complex behaviour.