<p>When implementing an interpreter, there is a choice between implementing function calls either by just recursively evaluating the function body in a different evaluation context ─ essentially piggybacking on the host language's call stack ─ or alternatively, by explicitly representing the call stack as a data structure which the interpreter controls directly.</p>
<p>What are the advantages and disadvantages of these two implementation approaches?</p>

<interpreters><call-stack>
Pros and cons of reifying the stack in an interpreter
<p>I find recursive evaluation (a.k.a. ones that &quot;piggyback&quot; the host language's call stack) to be more readable and much easier to implement. The obvious disadvantage is that, for a large enough program, the evaluator will eventually blow out its call stack and hit a stack overflow or recursion limit. For host languages like Haskell or Scheme which already reify their call stacks on the heap in their implementations, this is much less of an issue.</p>
<p>Interpreters which explicitly maintain the call stack of the implemented language as a data structure generally also compile the source program down to a flat bytecode/intermediate representation, where each instruction can be evaluated with a bounded amount of computation space. Such an approach, while requiring much more labor, makes it much easier to reify the call stack.</p>

CC BY-SA 4.0
2023-05-20T05:31:37.610Z
2023-05-20T05:31:37.610Z
Olive
CC BY-SA 4.0
2023-05-20T05:37:37.487Z
Another thing I wanted to mention but didn't feel qualified to: I believe you could reify the host language's call stack using async/await for languages that otherwise use the OS call stack, such as C++, Rust, and Zig. This would allow you to evaluate recursively without causing a stack overflow. These features are still young and I sorely lack experience on the topic.
Olive
<p>@Olive's answer is exactly correct, but as someone who implemented a non-recursive interpreter, I had one more reason for doing so: the interpreter becomes a simple dispatch loop.</p>
<p>There are a few advantages to this.</p>
<p>The function that implements this loop, if it were called, recursively, would execute the same setup code and exit code on every call and return. If you don't do recursion, you can control that and avoid it.</p>
<p>Compilers can also optimize the dispatch loop more easily.</p>
<p>And for a personal reason, I just find the dispatch loop easier to read. But I am in the minority there.</p>

CC BY-SA 4.0
2023-05-20T05:40:37.020Z
2023-05-20T05:40:37.020Z
Gavin D. Howard
<p>Reifying the stack makes implementing lexical capture significantly easier, but has real performance costs. It can also enable (relatively) easy extension to coroutines or other language constructs that depend on stack manipulations, non-local returns, or tail-call optimisation. I have written interpreters that did both and I'll continue to do so; <strong>neither is fundamentally better than the other</strong>.</p>
<p>For a language that is going to have any of these features, a reified stack and reified stack frames are worthwhile. In a language that doesn't have use for any of these things it is <em>probably</em> not worthwhile. The implementation work is not too complex, but not completely trivial, and probably not going to be a make-or-break factor.</p>
<p>The <strong>run-time costs of this bookkeeping are meaningful</strong>, especially if the interpreter is allocating garbage-collected objects, but even for a flat stack. However, performance often isn't a major concern for interpreters. For a high-performance interpreter tighter coupling with the facilities of the platform is very valuable, and whether that implies a reified stack or not is more specific than this general advice can get.</p>
<p>In cases where you don't have a use for the reified stack, the interpreter code is liable to be easier to follow and maintain if it just leverages the existing call stack of the host language, and so looks and behaves like an ordinary program. <strong>I would only implement reification when one of those properties was desired, but I wouldn't hesitate to do that when the situation arose.</strong></p>
<hr />
<p>The other substantial advantage of reified stack frames is less related to the interpretation or language itself: it's a convenient place for instrumentation. Either for your own debugging of the interpreter, or as a language feature, you can intercept variable assignments or reads in one place, log lifetimes of function scopes, or interfere with returns. This isn't the only way to get those features, but it may be a convenient one.</p>

CC BY-SA 4.0
2023-05-20T05:35:28.773Z
2023-05-20T05:35:28.773Z
Michael Homer
# Pros and cons of reifying the stack in an interpreter
Posted by: username_0 on 2023-05-20
When implementing an interpreter, there is a choice between implementing function calls either by just recursively evaluating the function body in a different evaluation context ─ essentially piggybacking on the host language's call stack ─ or alternatively, by explicitly representing the call stack as a data structure which the interpreter controls directly.

What are the advantages and disadvantages of these two implementation approaches?
**Tags:** interpreters call-stack
---
## 3 answers
### Answer by username_3 on 2023-05-20. Score: 4 | Accepted answer
Reifying the stack makes implementing lexical capture significantly easier, but has real performance costs. It can also enable (relatively) easy extension to coroutines or other language constructs that depend on stack manipulations, non-local returns, or tail-call optimisation. I have written interpreters that did both and I'll continue to do so; **neither is fundamentally better than the other**.

For a language that is going to have any of these features, a reified stack and reified stack frames are worthwhile. In a language that doesn't have use for any of these things it is *probably* not worthwhile. The implementation work is not too complex, but not completely trivial, and probably not going to be a make-or-break factor.

The **run-time costs of this bookkeeping are meaningful**, especially if the interpreter is allocating garbage-collected objects, but even for a flat stack. However, performance often isn't a major concern for interpreters. For a high-performance interpreter tighter coupling with the facilities of the platform is very valuable, and whether that implies a reified stack or not is more specific than this general advice can get.

In cases where you don't have a use for the reified stack, the interpreter code is liable to be easier to follow and maintain if it just leverages the existing call stack of the host language, and so looks and behaves like an ordinary program. **I would only implement reification when one of those properties was desired, but I wouldn't hesitate to do that when the situation arose.**

---

The other substantial advantage of reified stack frames is less related to the interpretation or language itself: it's a convenient place for instrumentation. Either for your own debugging of the interpreter, or as a language feature, you can intercept variable assignments or reads in one place, log lifetimes of function scopes, or interfere with returns. This isn't the only way to get those features, but it may be a convenient one.
---
### Answer by username_1 on 2023-05-20. Score: 4
I find recursive evaluation (a.k.a. ones that "piggyback" the host language's call stack) to be more readable and much easier to implement. The obvious disadvantage is that, for a large enough program, the evaluator will eventually blow out its call stack and hit a stack overflow or recursion limit. For host languages like Haskell or Scheme which already reify their call stacks on the heap in their implementations, this is much less of an issue.

Interpreters which explicitly maintain the call stack of the implemented language as a data structure generally also compile the source program down to a flat bytecode/intermediate representation, where each instruction can be evaluated with a bounded amount of computation space. Such an approach, while requiring much more labor, makes it much easier to reify the call stack.
> **Comments:**
> **username_1** (2023-05-20): Another thing I wanted to mention but didn't feel qualified to: I believe you could reify the host language's call stack using async/await for languages that otherwise use the OS call stack, such as C++, Rust, and Zig. This would allow you to evaluate recursively without causing a stack overflow. These features are still young and I sorely lack experience on the topic.  
---
### Answer by username_2 on 2023-05-20. Score: 2
@Olive's answer is exactly correct, but as someone who implemented a non-recursive interpreter, I had one more reason for doing so: the interpreter becomes a simple dispatch loop.

There are a few advantages to this.

The function that implements this loop, if it were called, recursively, would execute the same setup code and exit code on every call and return. If you don't do recursion, you can control that and avoid it.

Compilers can also optimize the dispatch loop more easily.

And for a personal reason, I just find the dispatch loop easier to read. But I am in the minority there.
---
