Andy Gill:
> >The great news is that STG Hugs shares evaluation technology with
> >GHC. It does not use the C stack, so we can allocate more stack
> >on the fly if needed.
Hans Aberg:
> How do you avoid using the C stack if the compiler is written in C?
>
> I mean, one must use some C function calls to start the program, and then
> the C stack is used. Or is the stack only expanded when there are some
> local function variables, so if one merely is avoiding those, the stack
> does not expand?
The important thing is not the compiler but the runtime system. (I
don't think I've ever seen the compiler run out of stack space -
though if it did, it'd probably be Happy-generated code that did it
:-)).
As you point out, we can't really avoid using the C stack. The
question is whether the size of the stack is (a small) constant no
matter what program/input you use or whether the stack size varies
with the program you're executing.
In Classic Hugs the evaluator is written as a recursive function.
Every time the value of a thunk is required (ie in a primitive
operation or in a case expression), the evaluator is recursively
called to provide the value of that thunk. Obviously, this means that
Classic Hugs' C stack usage is not constant. Also, since there's no
portable way for a C program to check for stack overflow or to request
a particular stack size, it leaves us at the mercy of the C compiler
if a stack overflow occurs and at the mercy of the linker/OS to
determine the maximum stack size.
In STG-Hugs the evaluator is a non-recursive function and probably
uses less than 100 bytes of stack space. Every time the value of a
thunk is required, a return address is pushed onto the STG stack
(which is just a downwards-growing chunk of memory in the STG heap).
Every time a thunk is available, the return address is popped and the
evaluator starts evaluating from there. (More details in Simon
Peyton-Jones' STG paper - the section with the operational semantics
is almost a direct description of how the evaluator works.) Since the
heap/stack are explicitly allocated and manipulated by the STG runtime
system, we have complete control over its size and what to do on
overflow. (There's other benefits too - like being able to do
black-holing and kill threads.)
--
Alastair Reid
