For the next edition of Scala with Cats: Writing a section on implementing interpreters. Went deep into optimizations related to virtual machine dispatch. Discovered duality helps relate different dispatch approaches. Realized going deep into optimization is not suitable for the book, so writing here instead.

• Duality: In mathematics, it means making a direct correspondence between one structure and another. In programming, it allows seeing different code structures as alternative implementations. For example, function calls are dual to function returns. Tail calls are function calls that don't consume a stack frame. There is another duality between data and functions.
• Bytecode Interpreters and Virtual Machines: Two common ways to implement an interpreter are tree-walking interpreter and bytecode interpreter. Bytecode interpreter describes actions of a virtual machine, which can be a register machine or a stack machine. Stack machines are simple to implement but have inefficiencies in moving values.
• Interpreter Dispatch: The core of a bytecode interpreter is instruction dispatch, which has three components: instruction fetch, actual dispatch, and a loop. Switch dispatch is the most common form, but there are other alternatives like direct threading, indirect threading, etc.
• Dispatch Through the Lens of Duality: Different dispatch methods can be understood through the dualities between data and functions and calls and returns. For example, replacing bytecode instructions with functions gives subroutine threading. Using tail calls gives direct threaded dispatch. Keeping bytecode and using tail calls gives indirect threaded dispatch.