Stack limit exceeded prolog with append

Question

I get an error

Stack limit exceeded

in Prolog using append

I am writing a Spanish grammar and need to use append to separate clauses (to separate subject and predicate, get verbs, etc...).

Here I write a simplified use of append that I do not understand why is overflow. I get the answers that I want, but then loops to infinity and beyond!

complejidad(1,0).
complejidad(2,0).
complejidad(2,1).

lista(['A'], 0).
lista(['B'], 0).

lista(Frase, J) :-
    lista(Prefijo, 0),
    lista(Sufijo, Js),
    append(Prefijo, Sufijo, Frase),
    complejidad(J, Js).

If I query:

lista(X,_)

I get:

Y put the comlejidad statement to limit the recursion a 2 steps. But something happens with append.

Here is the live example: https://swish.swi-prolog.org/p/stack-limit-exceeded-with-append.pl

And here is my grammar: https://swish.swi-prolog.org/p/mini-gramatica-castellana.v2.pl

I show my grammar to illustrate why I need append!

Answer 1

As you see the error message shows the totally allocated stack 0.2G, which is smaller than in the standalone version, where one gets 1.0G by default. This is to assure that more pengines can run simultaneously on the SWISH server.

The SWI-Prolog stack needs a window for parameter passing. The error message does not show the window size. This is a hard coded parameter, SWI-Prolog needs to be recompiled. Maybe for SWISH the window size should be also reduced.

The stackover flow happens because Js=2 has no solution in complejidad(J, Js). So its backtracking again and again, producing larger and larger intermediate derivations without showing an answer. Until it gets into a stack overflow.

This is not a problem of append/3, rather of lista/2 and depth first search. Try using a Prolog debugger to see what happens.

Answer 2

To limit depth of recursion programatically I add a number parameter:

lista(['A'], N) :- N>=0.
lista(['B'], N) :- N>=0.

lista(Frase, N) :-
    N > 0,
    N_1 is N-1,
    lista(Prefijo, N_1),
    lista(Sufijo, N_1),
    append(Prefijo, Sufijo, Frase).

In the atomic clauses y put N with N>=0 (that is because I want than the depth was a limit not an exact number; previously I try with N equal to 0).

In the recursive clause y add N>0 and define a N_1 variable to N-1