Recursion optimization and stack overflow from version 10.0.0

Discussion
1

Greetings,

I was teaching a student how to transform code with stack recursion to tail recursion and then I noticed that version 10.0+ has a somewhat different recursion optimization than version 9.0+

Goals that used to cause a “Stack limit(1.0Gb) exceeded” error in version 9.0+ now cause no error in version 10.0+, but just hang in an infinite loop. Maybe due to some sort of optimization that balances the amount of stack memory versus runtime.

Could someone please explain this mechanism?

The irony of the matter is that if there is no stack overflow error, then it becomes difficult to identify errors and debug the code. So personally, I don’t see the advantage of avoiding the tripping of the stack overflow error.

Is there a way to configure that behavior?

Thanks in advance.

2

Nothing changed to the stack overflow handling, but some things did change that may may cause programs that used to run out of stack to run in finite stack space. So, please share the code.

3

Well, for a simple example, take this specific form of coding the Fibbonacci numbers:

%=== stack recursion =========

fibonacci01(0,1).
fibonacci01(1,1).
fibonacci01(N, Fibonacci) :-
N > 1,
N1 is N-1,
N2 is N-2,
fibonacci01(N1, Fib1),
fibonacci01(N2, Fib2),
Fibonacci is Fib1 + Fib2.

%===========================

When run in version 9.0.4 it yields:

?- fibonacci01(36,Fib).
ERROR: Stack limit (1.0Gb) exceeded
ERROR: Stack sizes: local: 0.8Gb, global: 0.1Gb, trail: 50.1Mb
ERROR: Stack depth: 35, last-call: 3%, Choice points: 3,285,897
ERROR: In:
ERROR: [35] user:fibonacci01(1, _32874220)
ERROR: [34] user:fibonacci01(3, _32874240)
ERROR: [33] user:fibonacci01(4, _32874260)
ERROR: [32] user:fibonacci01(6, _32874280)
ERROR: [31] user:fibonacci01(7, _32874300)
ERROR:
ERROR: Use the --stack_limit=size[KMG] command line option or
ERROR: ?- set_prolog_flag(stack_limit, 2_147_483_648). to double the limit.
?-
But when run in version 10.0+ it does not yield such error. It just hangs forever…
Does that help?

4

Seems it is looping doing many small stack expansions. Looks like a bug.

5

For large stack, version 10.0+ looks like it hangs. But you can
still force a stack overflow by using a small stack:

fibonacci02(0,1) :- !.
fibonacci02(1,1) :- !.
fibonacci02(N, Fibonacci) :-
   N > 1,
   N1 is N-1,
   N2 is N-2,
   fibonacci02(N1, Fib1),
   fibonacci02(N2, Fib2),
   Fibonacci is Fib1 + Fib2.

This will give you:

/* SWI-Prolog 10.1.8 */
?- set_prolog_flag(stack_limit, 1073741).
true.

?- fibonacci01(36,Fib).
ERROR: Stack limit (1.0Mb) exceeded
ERROR:   Stack sizes: local: 0.5Mb, global: 0.1Mb, trail: 29Kb
ERROR:   Stack depth: 45, last-call: 7%, Choice points: 1,893

?- fibonacci02(36,Fib).
Fib = 24157817.
6

:fearful: @jan “A bug”? Maybe a bug in version 10.0+ but not in 9.3+

My concern is that if a stack error does not appear in 10.0+ more complex code could be more difficult to debug. Errors are important and teach us about our code…

@Johnny_Rotten suggest to add cuts, but that really doesn’t solve the real problem which is “backward compatibility” even with errors…