Похоже, вы уже знакомы с некоторыми недостатками и преимуществами.
Некоторые другие:
а) Позволяет поддерживать правильную оптимизацию хвостового вызова, даже если базовая реализация не имеет никакой поддержки
б) Легче создавать такие вещи, как языковой уровень "трассировки стека"
в) Проще добавить правильные продолжения, как вы указали
Недавно я написал простой интерпретатор "Схемы" на C #, который первоначально использовал стек .NET. Затем я переписал его для использования явного стека, так что, возможно, вам поможет следующее:
Первая версия использовала неявный стек времени выполнения .NET ...
Первоначально, это была просто иерархия классов, с различными формами (лямбда, пусть и т. Д.), Являющимися реализациями следующего интерфейса:
// A "form" is an expression that can be evaluted with
// respect to an environment
// e.g.
// "(* x 3)"
// "x"
// "3"
public interface IForm
{
object Evaluate(IEnvironment environment);
}
IEnvironment выглядело так, как вы ожидаете:
/// <summary>
/// Fundamental interface for resolving "symbols" subject to scoping.
/// </summary>
public interface IEnvironment
{
object Lookup(string name);
IEnvironment Extend(string name, object value);
}
Для добавления «встроенных» в мой интерпретатор Scheme у меня изначально был следующий интерфейс:
/// <summary>
/// A function is either a builtin function (i.e. implemented directly in CSharp)
/// or something that's been created by the Lambda form.
/// </summary>
public interface IFunction
{
object Invoke(object[] args);
}
Это было, когда он использовал неявный стек времени выполнения .NET. Определенно было меньше кода, но было невозможно добавить такие вещи, как правильная хвостовая рекурсия, и, самое главное, моему интерпретатору было неловко иметь возможность обеспечить трассировку стека «языкового уровня» в случае ошибки времени выполнения.
Поэтому я переписал его, чтобы иметь явный (выделенный в куче) стек.
Мой интерфейс «IFunction» должен был измениться на следующий, чтобы я мог реализовать такие вещи, как «map» и «apply», которые вызывают обратный вызов в интерпретаторе Scheme:
/// <summary>
/// A function that wishes to use the thread state to
/// evaluate its arguments. The function should either:
/// a) Push tasks on to threadState.Pending which, when evaluated, will
/// result in the result being placed on to threadState.Results
/// b) Push its result directly on to threadState.Results
/// </summary>
public interface IStackFunction
{
void Evaluate(IThreadState threadState, object[] args);
}
И IForm изменился на:
public interface IForm
{
void Evaluate(IEnvironment environment, IThreadState s);
}
Где IThreadState выглядит следующим образом:
/// <summary>
/// The state of the interpreter.
/// The implementation of a task which takes some arguments,
/// call them "x" and "y", and which returns an argument "z",
/// should follow the following protocol:
/// a) Call "PopResult" to get x and y
/// b) Either
/// i) push "z" directly onto IThreadState using PushResult OR
/// ii) push a "task" on to the stack which will result in "z" being
/// pushed on to the result stack.
///
/// Note that ii) is "recursive" in its definition - that is, a task
/// that is pushed on to the task stack may in turn push other tasks
/// on the task stack which, when evaluated,
/// ... ultimately will end up pushing the result via PushResult.
/// </summary>
public interface IThreadState
{
void PushTask(ITask task);
object PopResult();
void PushResult(object result);
}
И ITask это:
public interface ITask
{
void Execute(IThreadState s);
}
И мой главный цикл «событие»:
ThreadState threadState = new ThreadState();
threadState.PushTask(null);
threadState.PushTask(new EvaluateForm(f, environment));
ITask next = null;
while ((next = threadState.PopTask()) != null)
next.Execute(threadState);
return threadState.PopResult(); // Get what EvaluateForm evaluated to
EvaluateForm - это просто задача, которая вызывает IForm. Оценка в определенной среде.
Лично я нашел эту новую версию намного более приятной для работы с точки зрения реализации - легко получить трассировку стека, легко заставить ее реализовывать полные продолжения (хотя ... я не сделал этого как пока - мне нужно создать свои "стеки" постоянных связанных списков, а не использовать C # Stack, и ITask "возвращает" новый ThreadState, а не изменяет его, чтобы у меня могла быть задача "продолжение вызова" ... и т. д. .
По сути, вы просто меньше зависите от базовой языковой реализации.
Единственный недостаток, который я могу найти, это производительность ... Но в моем случае это всего лишь переводчик, так что в любом случае меня не волнует производительность.
Я бы также указал вам на эту замечательную статью о преимуществах переписывания рекурсивного кода в виде итеративного кода со стеком одним из авторов компилятора KAI C ++: Учитывая рекурсию