Preventing StackOverflow in language interpreters

Question

F# as a language is great for writing language interpreters or compilers, however, one thing keeps hitting us where we don't want it: the StackOverflowException.

It's well known that an SO-exception cannot be caught and cannot be recovered from. An obvious technique for preventing such an exception is by counting the depth of the stack as you go along. Overhead, yes, but doable and perhaps not necessary in every function.

With F#, this technique doesn't bring much benefit though. We make a lot of use of tail-call optimization techniques in the on-the-fly generated expressions of the interpreter. The problems we face with SO-exceptions are:

• how can we inform the user of them, instead of crashing the whole current AppDomain?
• if we go for counting the stack-depth, how do we know whether a function is TCO'ed or inlined so we don't have to count up?
• if we go for another approach (like inspecting the stack itself at given depth-intervals), is there any (known) way to do this without seriously impeding performance?

Just increasing the stack-size is not going to help enough, we want to give the user a loggable error, preferably catchable by the calling application. For that we need to be able to hand-throw the exception, which makes it catchable. But how do we determine the right moment?

Update:
Hans Passant correctly suggests predictability here. However, the programmers using this DSL expect that (certain) calls get TCO'ed, hence they don't want a strong stack-limit. They know what they are doing. Still, their programs need to be able to die gracefully, at least to the extend that any calling application (i.e., a C# program using our libraries) is not harmed.

Answer 1

I'm not familiar with F# but I did write an ECMAScript-262 v.5 interpreter in C# so I can relate to some of your issues. As you know, the StackOverFlowException can't be caught in .NET apps since v2.0. There is a fairly reliable workaround though and it's fast.

If you declare a variable on the stack, for instance an int, the address of that variable represents the top of the stack and lets you know how much space is left. So, if you record that variable at startup while the stack is basically empty, you can reference it each time you enter a new execution context.

Here are some exerpts from my interpreter that address this issue.

C#:

These are static variables declared in the main Interpreter class.

private static int TopOfStack;
private const int STACK_SIZE = 1000000;

This is the static constructor of the main Interpreter class.

static Interpreter() {
    InitializeGlobalEnvironment();

    //---------------------------------------------------
    // Get the address of a new variable allocated on the stack 
    // to represent the amount of memory available. Record 
    // the address.
    //---------------------------------------------------
    int stackVariable;
    TopOfStack = (int)&stackVariable;
}

This code gets called before an ECMAScript function is interpreted. If the address of a new stack allocated variable is less than short.Max, I throw the catchable exception. You need to leave some space for the call stack to unwind.

internal static ExecutionContext EnterFunctionContext(IValue thisArg, LIST args, FUNCTION function) {
...
    LexicalEnvironment localEnv = ECMA.NewDeclarativeEnvironment(function.Scope);

    ExecutionContext context = new ExecutionContext() {
        Strict = function.IsStrict,
        VariableEnvironment = localEnv,
        LexicalEnvironment = localEnv
    };

    int remainingStackSpace;

    if (STACK_SIZE - (TopOfStack - (int)&remainingStackSpace) < short.MaxValue) 
            throw new ECMARuntimeException("stack overflow", RuntimeErrorType.RangeError);


    CallStack.Push(context);
    LexicalEnvironment env = CurrentContext.VariableEnvironment;
...
}

When the following code is interpreted, the exception is thrown around iteration 1200.

Update: In release build it is around 4100 iterations.

ECMAScript:

RecursiveCall(0);

function RecursiveCall(counter){
    return RecursiveCall(++counter);
}

Output: RangeError: stack overflow

You could increase the stack size in the Thread using the Thread(ParameterizedThreadStart, Int32) constructor. I just didn't feel the need.

Good luck with your project. I hope this helps.