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.
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.
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?
@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…
@anon37422618 suggest to add cuts, but that really doesn’t solve the real problem which is “backward compatibility” even with errors…
Ok… @anon37422618 's analysis looks deep…
But what exactly can we do about it?
I would like to understand the coding style implications in order to teach properly to my students…
Eventually, fix it. I’m a bit too involved in other stuff right now. The problem seems to be in the code that decides for GC and stack shifts that keeps doing very small shifts and as the stacks are fairly big this takes a lot of time. This scenario should be recognised and it should enlarge the stacks in much larger increments such that it will run out without wasting too much time on stack shifts (or GC).
If you want to demonstrate stack overflow using last call optimization or not I’d use something simpler, like computing the max of a list as being the max of the head and tail vs. using an accumulator.
Pushed 3a21dce70d7a5f3e8da645dae7b29091ec604e62 to address this. The real bug turned out to be a typo, causing the local stack to be enlarged by a single page (4K) rather than minimally 25% after a stack overflow was detected and the desired total amount of stack is larger than the stack limit. It takes a long time to exceed 1Gb with 4K increments (well, the first steps did use proper increment steps)
