Every time a Scheme program makes a call that is not in tail position, it pushes a new frame onto the stack. Returning a value from a function pops the top frame off the stack. Stack frames take up memory, and as nobody has an infinite amount of memory, deep recursion could cause Guile to run out of memory. Running out of stack memory is called stack overflow.
Most languages have a terrible stack overflow story. For example, in C, if you use too much stack, your program will exhibit “undefined behavior”, which if you are lucky means that it will crash. It’s especially bad in C, as you neither know ahead of time how much stack your functions use, nor the stack limit imposed by the user’s system, and the stack limit is often quite small relative to the total memory size.
Managed languages like Python have a better error story, as they are defined to raise an exception on stack overflow – but like C, Python and most dynamic languages still have a fixed stack size limit that is usually much smaller than the heap.
Arbitrary stack limits would have an unfortunate effect on Guile
programs. For example, the following implementation of the inner loop
of map is clean and elegant:
(define (map f l)
(if (pair? l)
(cons (f (car l))
(map f (cdr l)))
'()))
However, if there were a stack limit, that would limit the size of lists
that can be processed with this map. Eventually, you would have
to rewrite it to use iteration with an accumulator:
(define (map f l)
(let lp ((l l) (out '()))
(if (pair? l)
(lp (cdr l) (cons (f (car l)) out))
(reverse out))))
This second version is sadly not as clear, and it also allocates more
heap memory (once to build the list in reverse, and then again to
reverse the list). You would be tempted to use the destructive
reverse! to save memory and time, but then your code would not be
continuation-safe – if f returned again after the map had
finished, it would see an out list that had already been
reversed. The recursive map has none of these problems.
Guile has no stack limit for Scheme code. When a thread makes its first Guile call, a small stack is allocated – just one page of memory. Whenever that memory limit would be reached, Guile arranges to grow the stack by a factor of two. When garbage collection happens, Guile arranges to return the unused part of the stack to the operating system, but without causing the stack to shrink. In this way, the stack can grow to consume up to all memory available to the Guile process, and when the recursive computation eventually finishes, that stack memory is returned to the system.
Of course, it’s still possible to run out of stack memory. The most common cause of this is program bugs that cause unbounded recursion, as in:
(define (faulty-map f l)
(if (pair? l)
(cons (f (car l)) (faulty-map f l))
'()))
Did you spot the bug? The recursive call to faulty-map recursed
on l, not (cdr l). Running this program would cause
Guile to use up all memory in your system, and eventually Guile would
fail to grow the stack. At that point you have a problem: Guile needs
to raise an exception to unwind the stack and return memory to the
system, but the user might have exception handlers in place
(see Raising and Handling Exceptions) that want to run before the
stack is unwound, and we don’t have any stack in which to run them.
Therefore in this case, Guile raises an unwind-only exception that does not run pre-unwind handlers. Because this is such an odd case, Guile prints out a message on the console, in case the user was expecting to be able to get a backtrace from any pre-unwind handler.
Still, this failure mode is not so nice. If you are running an
environment in which you are interactively building a program while it
is running, such as at a REPL, you might want to impose an artificial
stack limit on the part of your program that you are building to detect
accidental runaway recursion. For that purpose, there is
call-with-stack-overflow-handler, from (system vm vm).
(use-module (system vm vm))
Call thunk in an environment in which the stack limit has been
reduced to limit additional words. If the limit is reached,
handler (a thunk) will be invoked in the dynamic environment of
the error. For the extent of the call to handler, the stack limit
and handler are restored to the values that were in place when
call-with-stack-overflow-handler was called.
Usually, handler should raise an exception or abort to an outer prompt. However if handler does return, it should return a number of additional words of stack space to allow to the inner environment.
A stack overflow handler may only ever “credit” the inner thunk with stack space that was available when the handler was instated. When Guile first starts, there is no stack limit in place, so the outer handler may allow the inner thunk an arbitrary amount of space, but any nested stack overflow handler will not be able to consume more than its limit.
Unlike the unwind-only exception that is thrown if Guile is unable to grow its stack, any exception thrown by a stack overflow handler might invoke pre-unwind handlers. Indeed, the stack overflow handler is itself a pre-unwind handler of sorts. If the code imposing the stack limit wants to protect itself against malicious pre-unwind handlers from the inner thunk, it should abort to a prompt of its own making instead of throwing an exception that might be caught by the inner thunk.
It is also possible for Guile to run out of space on the C stack. If you call a primitive procedure which then calls a Scheme procedure in a loop, you will consume C stack space. Guile tries to detect excessive consumption of C stack space, throwing an error when you have hit 80% of the process’ available stack (as allocated by the operating system), or 160 kilowords in the absence of a strict limit.
For example, looping through call-with-vm, a primitive that calls
a thunk, gives us the following:
scheme@(guile-user)> (use-modules (system vm vm)) scheme@(guile-user)> (let lp () (call-with-vm lp)) ERROR: Stack overflow
Unfortunately, that’s all the information we get. Overrunning the C stack will throw an unwind-only exception, because it’s not safe to do very much when you are close to the C stack limit.
If you get an error like this, you can either try rewriting your code to
use less stack space, or increase the maximum stack size. To increase
the maximum stack size, use debug-set!, for example:
(debug-set! stack 200000)
The next section describes debug-set! more thoroughly. Of course
the best thing is to have your code operate without so much resource
consumption by avoiding loops through C trampolines.