Tail-Call Interpreters in Rust – Jimmy Ostler

Tail-Call Interpreters in Rust - Jimmy Ostler

Tail-Call Interpreters in Rust

01 Aug 2026

Jimmy Ostler

Word Count: 1636

Reading Time: 9 Min

Recently, I came across this post about different styles of VM dispatch as I was searching for ways to improve my ternary project. I had heard of tail-call interpretation, though my original source of inspiration took some time for me to re-find. This post, however, gave an excellent breakdown about several different styles of VM dispatch in Scala. I decided to implement these in Rust (including several variations more relevant to my project) as a fun experiment, and benchmark them to measure how they differ. I'll go over 2 versions - one, meant to emulate Noel's Scala, the other, meant to utilize Rust's strengths with a more complicated and traditional register machine.

Tail-Calls

Tail-call interpretation refers to the technique where some recursion can be turned into a jump during compilation, removing the need to allocate a new stack frame. It's extremely useful for functional languages to keep stack sizes down, such as Scala, but most compilers tend to use it. If you want to learn more, I highly recommend checking out Noel's excellent article above. When compiling with high optimization, Rust also performs this, and the unstable feature explicit_tail_calls lets us directly tell the compiler to perform the optimization or error.

Stack Machine (Noel's Machine)

The simplest machine we can easily work with here is a stack machine with 5 instructions, represented in Rust as so:

enum ByteCode { Lit(f64), Add, Sub, Mul, Div Essentially identical to Noel's Scala. Since this is a stack machine, the Lit (literal) instruction pushes a value on the stack; arithmetic instructions pop their operands, and push the resulting value back onto the stack.

Dispatch

As a control, switch dispatch makes the most sense. We simply create an array of bytecode, loop over it in a match statement, and execute it.

NOTE: I decided to use some strange decisions to match up with the Scala. These include the usage of `static mut` and `unsafe` as opposed to manually creating closures, though I did that in a sense anyways. I do NOT endorse writing Rust this way.Switch Dispatch

const STACK_SIZE: usize = 32; // Our stack static mut STACK: &mut [f32] = &mut [0.0; STACK_SIZE];

// The list of instructions to execute static mut INSTRS: &[Instr] = /* { [Lit(4.0), Lit(3.0)... etc] } */;

// We pass the stack pointer and instruction pointer to `dispatch` pub fn dispatch(sp: usize, ip: usize) -> f32 { unsafe { if ip == INSTRS.len() { STACK[sp - 1] } else { match INSTRS[ip] { Instr::Lit(value) => { STACK[sp] = value; become dispatch(sp + 1, ip + 1) }, Instr::Add => { let a = STACK[sp - 2]; let b = STACK[sp - 1]; STACK[sp - 2] = a + b; become dispatch(sp - 1, ip + 1) }, Instr::Sub => { let a = STACK[sp - 2]; let b = STACK[sp - 1]; STACK[sp - 2] = a - b; become dispatch(sp - 1, ip + 1) }, Instr::Mul => { let a = STACK[sp - 2]; let b = STACK[sp - 1]; STACK[sp - 2] = a * b; become dispatch(sp - 1, ip + 1) }, Instr::Div => { let a = STACK[sp - 2]; let b = STACK[sp - 1]; STACK[sp - 2] = a / b; become dispatch(sp - 1, ip + 1) }, Here we can see our entire logic - a large recursive function that calls itself for every instruction. Since we used the become keyword, we know our recursion won't lead to a stack overflow. This is a nice and simple strategy! Nothing too complicated here.

Subroutine Dispatch

We next do subroutine threading, where we replace the match statement. Instead of an enum, we have to implement our instructions as a struct that can be called by implementing the Fn() trait. This means we can call a dynamic &dyn Fn(), regardless of the underlying struct.

Our bytecode now looks like this (some parts omitted for brevity):

// Now, our instructions are `&dyn Fn()`, so we can use dynamic dispatch // to call different instructions without knowing what they are. static mut INSTRS: &[&dyn Fn() -> ()] = /*[&Lit, &Add... etc]*/;

static mut SP: usize = 0; const STACK_SIZE: usize = 32; static mut STACK: &mut [f32] = &mut [0.0; STACK_SIZE];

struct Lit(f32); struct Add; struct Sub; struct Mul; struct Div;

impl Fn()> for Lit { extern "rust-call" fn call(&self, _args: ()) -> Self::Output { unsafe { STACK[SP] = self.0; SP += 1;

impl Fn()> for Add { extern "rust-call" fn call(&self, _args: ()) -> Self::Output { unsafe { let a = STACK[SP - 1]; let b = STACK[SP - 2]; STACK[SP - 2] = a + b; SP -= 1;

impl Fn()> for Sub { extern "rust-call" fn call(&self, _args: ()) -> Self::Output { unsafe { let a = STACK[SP - 1]; let b = STACK[SP - 2]; STACK[SP - 2] = a - b; SP -= 1;

impl Fn()> for Mul { extern "rust-call" fn call(&self, _args: ()) -> Self::Output { unsafe { let a = STACK[SP - 1]; let b = STACK[SP - 2]; STACK[SP - 2] = a * b; SP -= 1;

impl Fn()> for Div { extern "rust-call" fn call(&self, _args: ()) -> Self::Output { unsafe { let a = STACK[SP - 1]; let b = STACK[SP - 2]; STACK[SP - 2] = a * b; SP -=...

Tail-Call Interpreters in Rust – Jimmy Ostler

Related Articles

(no title)

Scientists reverse brain aging, with a nasal spray

NHS apologises and admits Palantir have access to identifiable patient data

AI has torched the market for junior programmers

Al Vigier: Canada's AI strategy shouldn't include secret Palantir bills