Tail-Call Interpreters in Rust

In a recent exploration of various VM dispatch styles, the author applied these techniques to Rust, creating two versions of a stack machine. The first version aimed to emulate Noel's Scala implementation, while the second sought to leverage Rust's strengths through a more traditional register machine approach.

Tail-call interpretation, a method that compiles certain recursions into jumps to reduce stack allocations, is particularly useful for functional languages like Scala. Rust also supports this optimization, which the author utilized by implementing explicit_tail_calls.

The analysis began with a simple stack machine featuring five instructions: Lit (literal), arithmetic operations, and a control switch dispatch. This straightforward strategy involved creating an array of bytecode, looping over it, and executing the instructions using a match statement. This method ensured the recursion wouldn't cause a stack overflow, thanks to the become keyword.

Next, the author experimented with subroutine threading, which replaced the match statement with a struct implementing the Fn() trait. This allowed for dynamic, call-by-reference dispatch of operations, enabling tail-call optimization and potentially reducing function call overhead. The bytecode was adapted accordingly, though the author noted that this approach could benefit from incorporating function passing values, similar to Scala.

Indirect threading was then explored, which kept the match statement but switched to indirect recursion. Operations called the dispatch function instead of returning and invoking themselves recursively. This approach theoretically reduced the number of function returns and allowed for tail-call optimization. However, the author found Rust's Fn() traits, while powerful, were not ideally suited for this technique, leading to a somewhat complex implementation.

The author then considered combining dispatch techniques, leading to direct dispatch. This method involved dispatching within operations while using an array of dyn Fn(). It resulted in a minimal number of function calls, aligning with the goal of utilizing tail-call optimization effectively. This technique proved to be the most efficient in terms of performance, outperforming other methods in the tests conducted.

While these Rust-based techniques provided interesting insights, the author noted they deviated from their planned ternary VM architecture, which was meant to emulate actual hardware with a decoding stage and registers. Despite this, the author proceeded to test a 16-bit register machine, where Switch dispatch, including a larger decode stage, performed as expected, validating the findings from previous experiments.