在语言解释器中防止StackOverflow

Question

F#作为一种语言非常适合编写语言解释器或编译器,但是,有一件事情让我们不知所措:StackOverflowException.

众所周知,无法捕获SO异常,无法从中恢复.防止这种异常的一种显而易见的技术是在你进行时计算堆栈的深度.开销,是的,但是可行,也许在每个功能中都没有必要.

使用F#,这种技术虽然没有带来太多好处.我们在解释器的动态生成表达式中大量使用尾调用优化技术.我们在SO异常中遇到的问题是:

• 我们如何通知用户,而不是崩溃整个当前的AppDomain？
• 如果我们计算堆栈深度,我们如何知道函数是TCO还是内联,所以我们不必计算？
• 如果我们采用另一种方法(比如以给定的深度间隔检查堆栈本身),是否有任何(已知的)方法可以在不严重影响性能的情况下执行此操作？

只是增加堆栈大小不会有足够的帮助,我们希望给用户一个可记录的错误,最好是由调用应用程序捕获.为此,我们需要能够手动抛出异常,这使它可以捕获.但我们如何确定合适的时机？

更新:
Hans Passant在这里正确地提出了可预测性.但是,使用此DSL的程序员期望(某些)调用获得TCO,因此他们不希望有强大的堆栈限制.他们知道自己在做什么.尽管如此,他们的程序仍然需要能够优雅地消亡,至少在任何调用应用程序(即使用我们的库的C#程序)都不会受到损害的情况下.

Answer 1

我不熟悉F#,但我确实在C#中编写了一个ECMAScript-262 v.5解释器,所以我可以解决你的一些问题.如您所知,自v2.0起,无法在.NET应用程序中捕获StackOverFlowException.虽然有一个相当可靠的解决方法,但速度很快.

如果在堆栈上声明变量,例如int,则该变量的地址代表堆栈的顶部,并让您知道剩余多少空间.因此,如果在堆栈基本为空时在启动时记录该变量,则每次输入新的执行上下文时都可以引用该变量.

以下是我的口译员解决此问题的一些例外情况.

C#:

这些是在主Interpreter类中声明的静态变量.

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

这是主Interpreter类的静态构造函数.

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;
}

在解释ECMAScript函数之前调用此代码.如果新堆栈分配变量的地址小于short.Max,则抛出可捕获的异常.您需要为调用堆栈留出一些空间来放松.

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;
...
}

解释以下代码时,将在迭代1200周围抛出异常.

更新:在发布版本中,它大约是4100次迭代.

ECMAScript中:

RecursiveCall(0);

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

输出: RangeError: stack overflow

您可以使用Thread(ParameterizedThreadStart, Int32)构造函数增加Thread中的堆栈大小.我只是觉得不需要.

祝你的项目好运.我希望这有帮助.