<p>It seems to me that coroutines and derived abstractions like the iterators and generators are implemented the following way:</p>
<ul>
<li>When returning
<ol>
<li>Move the function's stack frame to the heap</li>
<li>Save a pointer to the exact instruction that the function was executing</li>
</ol>
</li>
<li>When resuming
<ol>
<li>Reactivate the stack frame</li>
<li>Jump to the saved instruction pointer</li>
</ol>
</li>
</ul>
<p>This makes sense to me but deals with a linear code structure which implies a bytecode interpreter. How does it work in a tree-walking interpreter?</p>
<pre class="lang-lisp prettyprint-override"><code>(a (b (c (yield))))
</code></pre>
<p>I was not able to find any example code to study. All popular programming languages apparently use bytecode interpreters which work as I described above. I also found <a href="https://langdev.stackexchange.com/q/820/2098">this question</a> but the answer seems to be conceptually the same as the linear jump case, only using <code>switch</code> instead.</p>
<p>So how would one implement coroutines in a tree-walking interpreter? How can progress through the evaluation of an expression tree be saved?</p>

<implementation><iterators><generators><coroutines><tree-walker>
How are coroutines implemented in a tree-walking interpreter?
CC BY-SA 4.0
2024-02-13T20:01:11.700Z
The simplest answer is meta-circularly: make the "eval" function a coroutine, which yields when the interpreted code yields.
kaya3
CC BY-SA 4.0
2024-02-13T23:47:25.647Z
You might want to check out the chapter on streams in SICP.
Barmar
CC BY-SA 4.0
2024-02-13T23:48:45.887Z
If the language has closures, you can use the same mechanism you use to save the bindings of a closure.
Barmar
CC BY-SA 4.0
2024-02-19T01:07:30.487Z
To expand on @kaya3's excellent comment: I'll note that "save the execution environment somewhere and make a note of the instruction to resume on later" is also how "normal" (non-co-call) calls work. You're just used to working in languages where you get that "for free". What if you didn't? It's character-building to consider what mechanisms you'd have to build to bootstrap interpreting language with subroutines in a language that lacked them.
Eric Lippert
<p>If you express your interpreter in <a href="https://en.m.wikipedia.org/wiki/Continuation-passing_style" rel="nofollow noreferrer">continuation-passing style</a>, then the continuation of evaluating one node in your expression tree represents the same information as a recursive stack frame, but instead stored as a closure. Coroutine <code>suspend</code> is then an expression that returns a value that will call the continuation when you <code>resume</code> it, instead of evaluating the continuation immediately.</p>
<p>Here is an implementation in Rust, for example:</p>
<pre class="lang-rust prettyprint-override"><code>#![feature(trait_alias)]

use core::fmt::{Debug, Formatter};
impl Debug for Value {
    fn fmt(&amp;self, fmt: &amp;mut Formatter&lt;'_&gt;) -&gt; Result&lt;(), std::fmt::Error&gt; {
        match self {
            Value::Number(u) =&gt; write!(fmt, &quot;{}&quot;, u),
            Value::Coroutine(c) =&gt; write!(fmt, &quot;&lt;coroutine&gt;&quot;),
        }
    }
}

#[derive(Debug)]
enum Expr {
    Number(usize),
    Add(Box&lt;Expr&gt;, Box&lt;Expr&gt;),
    Suspend,
    Resume(Box&lt;Expr&gt;, Box&lt;Expr&gt;),
}

trait Cont = FnOnce(Value) -&gt; Value;

enum Value {
    Number(usize),
    Coroutine(Box&lt;dyn Cont&gt;),
}


fn eval(e: Expr, cont: Box&lt;dyn Cont&gt;) -&gt; Value {
    println!(&quot;{:?}&quot;, e);
    match e {
        Expr::Number(u) =&gt; cont(Value::Number(u)),
        Expr::Add(l, r) =&gt; {
            cont(eval(*l, Box::new(|l_val| {
                if let Value::Number(l_num) = l_val {
                    eval(*r, Box::new(move |r_val| {
                        if let Value::Number(r_num) = r_val {
                            Value::Number(l_num + r_num)
                        } else {
                            panic!(&quot;can't add non-number right operand&quot;);
                        }
                    }))
                } else {
                    panic!(&quot;can't add non-number left operand&quot;);
                }
            })))
        },
        Expr::Suspend =&gt; {
            Value::Coroutine(Box::new(|v| cont(v)))
        },
        Expr::Resume(c, r) =&gt; {
            cont(eval(*c, Box::new(|coro_val| {
                if let Value::Coroutine(coro) = coro_val {
                    eval(*r, Box::new(|r_val| {
                        coro(r_val)
                    }))
                } else {
                    panic!(&quot;can't resume non-coroutine&quot;);
                }
            })))
        }
    }
}


fn main() {
    println!(&quot;{:?}&quot;, eval(Expr::Add(
        Box::new(Expr::Number(1)),
        Box::new(Expr::Number(2))),
        Box::new(|v| v)));
    println!(&quot;{:?}&quot;, eval(Expr::Resume(
        Box::new(Expr::Add(
            Box::new(Expr::Suspend),
            Box::new(Expr::Number(2)))),
        Box::new(Expr::Number(1))),
            Box::new(|v| v)));
    println!(&quot;{:?}&quot;, eval(Expr::Resume(
        Box::new(Expr::Add(
            Box::new(Expr::Number(1)),
            Box::new(Expr::Suspend))),
        Box::new(Expr::Number(2))),
            Box::new(|v| v)));
}
</code></pre>

CC BY-SA 4.0
2024-02-16T01:57:45.573Z
2024-02-16T09:55:41.483Z
2024-02-16T09:55:41.483Z
chc4
# How are coroutines implemented in a tree-walking interpreter?
Posted by: username_0 on 2024-02-13
It seems to me that coroutines and derived abstractions like the iterators and generators are implemented the following way:

When returning

Move the function's stack frame to the heap
Save a pointer to the exact instruction that the function was executing


When resuming

Reactivate the stack frame
Jump to the saved instruction pointer



This makes sense to me but deals with a linear code structure which implies a bytecode interpreter. How does it work in a tree-walking interpreter?
(a (b (c (yield))))

I was not able to find any example code to study. All popular programming languages apparently use bytecode interpreters which work as I described above. I also found this question but the answer seems to be conceptually the same as the linear jump case, only using switch instead.
So how would one implement coroutines in a tree-walking interpreter? How can progress through the evaluation of an expression tree be saved?
**Tags:** implementation iterators generators coroutines tree-walker
> **Comments:**
> **username_1**: The simplest answer is meta-circularly: make the "eval" function a coroutine, which yields when the interpreted code yields.  
> **username_2**: You might want to check out the chapter on streams in SICP.  
> **username_2**: If the language has closures, you can use the same mechanism you use to save the bindings of a closure.  
> **username_3**: To expand on @kaya3's excellent comment: I'll note that "save the execution environment somewhere and make a note of the instruction to resume on later" is also how "normal" (non-co-call) calls work. You're just used to working in languages where you get that "for free". What if you didn't? It's character-building to consider what mechanisms you'd have to build to bootstrap interpreting language with subroutines in a language that lacked them.  
---
## 1 answers
### Answer by username_4 on 2024-02-16. Score: 2
If you express your interpreter in continuation-passing style, then the continuation of evaluating one node in your expression tree represents the same information as a recursive stack frame, but instead stored as a closure. Coroutine suspend is then an expression that returns a value that will call the continuation when you resume it, instead of evaluating the continuation immediately.
Here is an implementation in Rust, for example:
#![feature(trait_alias)]

use core::fmt::{Debug, Formatter};
impl Debug for Value {
    fn fmt(&self, fmt: &mut Formatter<'_>) -> Result<(), std::fmt::Error> {
        match self {
            Value::Number(u) => write!(fmt, "{}", u),
            Value::Coroutine(c) => write!(fmt, ""),
        }
    }
}

#[derive(Debug)]
enum Expr {
    Number(usize),
    Add(Box, Box),
    Suspend,
    Resume(Box, Box),
}

trait Cont = FnOnce(Value) -> Value;

enum Value {
    Number(usize),
    Coroutine(Box),
}


fn eval(e: Expr, cont: Box) -> Value {
    println!("{:?}", e);
    match e {
        Expr::Number(u) => cont(Value::Number(u)),
        Expr::Add(l, r) => {
            cont(eval(*l, Box::new(|l_val| {
                if let Value::Number(l_num) = l_val {
                    eval(*r, Box::new(move |r_val| {
                        if let Value::Number(r_num) = r_val {
                            Value::Number(l_num + r_num)
                        } else {
                            panic!("can't add non-number right operand");
                        }
                    }))
                } else {
                    panic!("can't add non-number left operand");
                }
            })))
        },
        Expr::Suspend => {
            Value::Coroutine(Box::new(|v| cont(v)))
        },
        Expr::Resume(c, r) => {
            cont(eval(*c, Box::new(|coro_val| {
                if let Value::Coroutine(coro) = coro_val {
                    eval(*r, Box::new(|r_val| {
                        coro(r_val)
                    }))
                } else {
                    panic!("can't resume non-coroutine");
                }
            })))
        }
    }
}


fn main() {
    println!("{:?}", eval(Expr::Add(
        Box::new(Expr::Number(1)),
        Box::new(Expr::Number(2))),
        Box::new(|v| v)));
    println!("{:?}", eval(Expr::Resume(
        Box::new(Expr::Add(
            Box::new(Expr::Suspend),
            Box::new(Expr::Number(2)))),
        Box::new(Expr::Number(1))),
            Box::new(|v| v)));
    println!("{:?}", eval(Expr::Resume(
        Box::new(Expr::Add(
            Box::new(Expr::Number(1)),
            Box::new(Expr::Suspend))),
        Box::new(Expr::Number(2))),
            Box::new(|v| v)));
}
---
