Stack limit exceeded prolog with append

0
votes

I get Stack limit exceeded in Prolog using append

I'am writing a spanish grammar and need to use append to separate clausules (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: Stack limit exceeded. Stack sizes: local: global: trail: Stack depth:last-call: 0%, Choice points: Possible non-terminating recursion:

Y put the comlejidad statement to limit the recursion a 2 steps. But something happends 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 ilustrate why I need append!

2
prolog
Would you mind using text a place of pictures? - false
In my opinion an image to show the results is not bad. And it is clear not the code. The code is in text, there are links to live examples. I would think that is enough except for one aspect. The error message is not searchable by a search engine. I'm going to fix it. - Emilio Platzer

2 Answers

0
votes

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.

0
votes

To limit depth of recursion programaticaly 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 clausules y put N with N>=0 (that is because I want than te depth whas a limit not an exact number; previously I try with N equal to 0).

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