Предотвращение StackOverflow в языковых интерпретаторах

F # как язык отлично подходит для написания переводчиков или компиляторов, однако одна вещь продолжает ударять нас, где мы этого не хотим: исключение StackOverflowException.

Хорошо известно, что исключение SO исключено и не может быть восстановлено. Очевидным методом предотвращения такого исключения является подсчет глубины стека по мере продвижения. Накладные расходы, да, но выполнимы и, возможно, не нужны в каждой функции.

С F # этот метод не приносит большой пользы. Мы много используем методы оптимизации хвостовых вызовов в оперативных выражениях интерпретатора. Проблемы, с которыми мы сталкиваемся с SO-исключениями:

  • как мы можем сообщить пользователю о них, а не обрушиться на весь текущий AppDomain?
  • Если мы идем для подсчета глубины стека, откуда мы узнаем, является ли функция TCO'ed или inlined, поэтому нам не нужно подсчитывать?
  • если мы идем на другой подход (например, проверять сам стек при заданных интервалах глубины), существует ли какой-либо (известный) способ сделать это без серьезного затруднения производительности?

Простое увеличение размера стека не поможет, мы хотим дать пользователю ошибку, зависящую от протокола, которая лучше всего улавливается вызывающим приложением. Для этого нам нужно иметь возможность вручную выбросить исключение, что делает его увлекательным. Но как определить правильный момент?

Обновление:
Ханс Пассант правильно предлагает предсказуемость здесь. Тем не менее, программисты, использующие этот DSL, ожидают, что (определенные) вызовы получат TCO'ed, следовательно, они не хотят сильного ограничения стека. Они знают, что делают. Тем не менее, их программы должны быть способны умереть изящно, по крайней мере до такой степени, что любое вызывающее приложение (т.е. Программа С#, использующая наши библиотеки) не пострадает.

Ответы

Ответ 1

Я не знаком с F #, но я написал интерпретатор ECMAScript-262 v.5 на С#, чтобы я мог относиться к некоторым вашим проблемам. Как вы знаете, исключение StackOverFlowException не может быть обнаружено в .NET-приложениях с версии 2.0. Существует довольно надежное обходное решение, хотя и быстро.

Если вы объявляете переменную в стеке, например int, адрес этой переменной представляет верхнюю часть стека и позволяет вам узнать, сколько осталось места. Итак, если вы записываете эту переменную при запуске, в то время как стек в основном пуст, вы можете ссылаться на него каждый раз, когда вы вводите новый контекст выполнения.

Вот несколько примеров из моего интерпретатора, которые решают эту проблему.

С#:

Это статические переменные, объявленные в основном классе 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, я бросаю catchable исключение. Вам нужно оставить некоторое пространство для стека вызовов, чтобы расслабиться.

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). Я просто не ощущал нужды.

Удачи вам в вашем проекте. Надеюсь, это поможет.