Description
It's been dead for a while, but I'd like to propose starting to think about TCE again. The discussion that I saw before was mostly centred around certain algorithms being more convenient to implement using recursion, but I'd like to give an example that's impossible to implement without TCE and that I actually genuinely do have a personal need for. To create a fast interpreter with 100% safe code, one possible implementation is like so:
pub struct Instruction(pub fn(&mut Stack, &[Instruction]) -> Result<Value, Error>);
pub fn convert(instructions: &[OpCode]) -> Vec<Instruction> {
instructions
.iter()
.map(|i| match i {
OpCode::Add => Instruction(instructions::add),
// ...
})
.collect()
}
mod instructions {
use super::{Error, Instruction, Stack, Value};
pub fn add(stack: &mut Stack, next: &[Instruction]) -> Result<Value, Error> {
let (a, b) = (
stack.pop().ok_or(Error::new())?,
stack.pop().ok_or(Error::new())?,
);
let out = a.checked_add(b).ok_or(Error::new())?;
if let Some((next, rest)) = next.split_first() {
stack.push(out);
return (next.0)(stack, rest);
} else {
Ok(out)
}
}
// ...
}
This can compile to excellent assembly, with similar performance to a naive compiler modulo the worse instruction cache usage and jump for each instruction, but you can see in this toy implementation that it compiles to call
+ret
using current Rust. With proper TCE error handling should just be the cost of creating the error plus a ret
. Unfortunately, it is impossible to express this in Rust right now, since TCE is not guaranteed and there's no way to assume that it will happen in debug mode. Another issue is that recursive fn
definitions aren't allowed, but that doesn't prevent this from being written, it just prevents it from being safe.