7
$\begingroup$

It seems to me that coroutines and derived abstractions like the iterators and generators are implemented the following way:

  • When returning
    1. Move the function's stack frame to the heap
    2. Save a pointer to the exact instruction that the function was executing
  • When resuming
    1. Reactivate the stack frame
    2. 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?

$\endgroup$
4
  • 4
    $\begingroup$ The simplest answer is meta-circularly: make the "eval" function a coroutine, which yields when the interpreted code yields. $\endgroup$
    – kaya3
    Feb 13 at 20:01
  • $\begingroup$ You might want to check out the chapter on streams in SICP. $\endgroup$
    – Barmar
    Feb 13 at 23:47
  • $\begingroup$ If the language has closures, you can use the same mechanism you use to save the bindings of a closure. $\endgroup$
    – Barmar
    Feb 13 at 23:48
  • $\begingroup$ 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. $\endgroup$ Feb 19 at 1:07

1 Answer 1

2
$\begingroup$

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, "<coroutine>"),
        }
    }
}

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

trait Cont = FnOnce(Value) -> Value;

enum Value {
    Number(usize),
    Coroutine(Box<dyn Cont>),
}


fn eval(e: Expr, cont: Box<dyn Cont>) -> 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)));
}
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .