Esoterica?

Combinator libraries

Regular Expressions

val pattern = "Sca(la)+"
pattern.matches("Scalalalalala") // true

Atoms: "S", "c", etc.

Combinators: concatentation, bracketing, +

Interpreter: matches

Graphics

val image = Picture.circle(100).beside(Picture.square(100))
picture.draw()

Atoms: Picture.circle(100), Picture.square(100)

Combinators: beside

Interpreter: draw

Arithmetic

val expr = Expr.literal(1) + Expr.literal(2)
expr.eval() // 3

Atoms: Expr.literal(1), Expr.literal(2)

Combinators: +

Interpreter: eval

Arithmetic Interpreter

enum Expr:
  case Lit(value: Double)
  case Add(l: Expr, r: Expr)
  case Sub(l: Expr, r: Expr)
  case Mul(l: Expr, r: Expr)
  case Div(l: Expr, r: Expr)
 
  def +(that: Expr): Expr = Add(this, that)
  def -(that: Expr): Expr = Sub(this, that)
  def *(that: Expr): Expr = Mul(this, that)
  def /(that: Expr): Expr = Div(this, that)
object Expr:
  def literal(value: Double): Expr = Expr.Lit(value)

enum Expr:
  case Lit(value: Double)
  case Add(l: Expr, r: Expr)
  case Sub(l: Expr, r: Expr)
  case Mul(l: Expr, r: Expr)
  case Div(l: Expr, r: Expr)
 
  def +(that: Expr): Expr = Add(this, that)
  def -(that: Expr): Expr = Sub(this, that)
  def *(that: Expr): Expr = Mul(this, that)
  def /(that: Expr): Expr = Div(this, that)
object Expr:
  def literal(value: Double): Expr = Expr.Lit(value)

enum Expr:
  // ...
  def eval(): Double =
    this match
      case Lit(value) => value
      case Add(l, r) => l.eval() + r.eval()
      case Sub(l, r) => l.eval() - r.eval()
      case Mul(l, r) => l.eval() * r.eval()
      case Div(l, r) => l.eval() / r.eval()

Performance

Calculate fibonacci(25)

~2750 iterations per second

Walking the AST is slow

enum Expr:
  // ...
  def eval(): Double =
    this match
      case Lit(value) => value
      case Add(l, r) => l.eval() + r.eval()
      case Sub(l, r) => l.eval() - r.eval()
      case Mul(l, r) => l.eval() * r.eval()
      case Div(l, r) => l.eval() / r.eval()

Convert to a stack machine

Arguments for combinators are popped from a stack

Results are pushed to a stack

enum Expr:
  case Lit(value: Double)
  case Add(l: Expr, r: Expr)
  case Sub(l: Expr, r: Expr)
  case Mul(l: Expr, r: Expr)
  case Div(l: Expr, r: Expr)
 
enum StackInstr:
  case Lit(value: Double)
  case Add
  case Sub
  case Mul
  case Div

enum Expr:
  case Lit(value: Double)
  case Add(l: Expr, r: Expr)
  case Sub(l: Expr, r: Expr)
  case Mul(l: Expr, r: Expr)
  case Div(l: Expr, r: Expr)
 
enum StackInstr:
  case Lit(value: Double)
  case Add
  case Sub
  case Mul
  case Div

enum Expr:
  // ...
  def compile(): Array[StackInstr] =
    this match
      case Lit(value) => Array(StackInstr.Lit(value))
      case Add(l, r) =>
        l.compile() ++ r.compile() ++ Array(StackInstr.Add)
      case Sub(l, r) =>
        l.compile() ++ r.compile() ++ Array(StackInstr.Sub)
      case Mul(l, r) =>
        l.compile() ++ r.compile() ++ Array(StackInstr.Mul)
      case Div(l, r) =>
        l.compile() ++ r.compile() ++ Array(StackInstr.Div)

enum Expr:
  // ...
  def compile(): Array[StackInstr] =
    this match
      case Lit(value) => Array(StackInstr.Lit(value))
      case Add(l, r) =>
        l.compile() ++ r.compile() ++ Array(StackInstr.Add)
      case Sub(l, r) =>
        l.compile() ++ r.compile() ++ Array(StackInstr.Sub)
      case Mul(l, r) =>
        l.compile() ++ r.compile() ++ Array(StackInstr.Mul)
      case Div(l, r) =>
        l.compile() ++ r.compile() ++ Array(StackInstr.Div)

object StackInstr:
  def eval(ins: Array[StackInstr]): Double =
    val stack: Array[Double]
    def loop(sp: Int, ip: Int)
      if ip == ins.size then stack(sp - 1)
      else ins(ip) match
        case Lit(value) =>
          stack(sp) = value
          loop(sp + 1, ip + 1)
        case Add =>
          val a = stack(sp - 1)
          val b = stack(sp - 2)
          stack(sp - 2) = (a + b)
          loop(sp - 1, ip + 1)
        // ...

object StackInstr:
  def eval(ins: Array[StackInstr]): Double =
    val stack: Array[Double]
    def loop(sp: Int, ip: Int)
      if ip == ins.size then stack(sp - 1)
      else ins(ip) match
        case Lit(value) =>
          stack(sp) = value
          loop(sp + 1, ip + 1)
        case Add =>
          val a = stack(sp - 1)
          val b = stack(sp - 2)
          stack(sp - 2) = (a + b)
          loop(sp - 1, ip + 1)
        // ...

Tree walking: ~2750 iterations per second

Stack machine: ~3550 iterations per second

How?

Read the literature

Tied to low-level implementation techniques. E.g. GCC extensions.

Doesn't generalize

Learn general principles to derive these concepts

Wide applicability

Duality is such a principle

Duality informally

Two concepts are duals

we can relate one to the other

understanding one helps understand the other

symmetries, opposites, complements

and and or

Tree walking is dual to stack machine

case Add(l, r) => l.eval() + r.eval()

Parameters are explicit

Stack is implicit

case Add =>
  val a = stack(sp - 1)
  val b = stack(sp - 2)
  stack(sp - 2) = (a + b)

Parameters are implicit

Stack is explicit

Systematically transform one to the other

Data is dual to Codata

Codata means a function or object

Data

enum Expr:
  case Lit(value: Double)
  case Add(l: Expr, r: Expr)
  case Sub(l: Expr, r: Expr)
  case Mul(l: Expr, r: Expr)
  case Div(l: Expr, r: Expr)

Data is extensional, defines what it is

Codata

trait Op:
  def eval: Double

Codata is intensional, defines what it can do

(BTW, we just related FP to OO)

Can we apply this duality to our interpreter?

enum StackInstr:
  case Lit(value: Double)
  case Add
  // ...
object StackInstr:
  def eval(ins: Array[StackInstr]): Double =
    val stack: Array[Double]
    def loop(sp: Int, ip: Int)
      if ip == ins.size then stack(sp - 1)
      else ins(ip) match
        case Lit(value) =>
          stack(sp) = value
          loop(sp + 1, ip + 1)
      // ...

enum StackInstr:
  case Lit(value: Double)
  case Add
  // ...
object StackInstr:
  def eval(ins: Array[StackInstr]): Double =
    val stack: Array[Double]
    def loop(sp: Int, ip: Int)
      if ip == ins.size then stack(sp - 1)
      else ins(ip) match
        case Lit(value) =>
          stack(sp) = value
          loop(sp + 1, ip + 1)
      // ...

Data becomes functions

private final var sp: Int = 0
private final var ip: Int = 0
 
sealed abstract class Op extends Function0[Unit]
final case class Lit(value: Double) extends Op:
  def apply(): Unit =
    stack(sp) = value
    sp = sp + 1
case object Add extends Op:
  def apply(): Unit =
    val a = stack(sp - 1)
    val b = stack(sp - 2)
    stack(sp - 2) = (a + b)
    sp = sp - 1
// ...

enum StackInstr:
  case Lit(value: Double)
  case Add
  // ...
object StackInstr:
  def eval(ins: Array[StackInstr]): Double =
    val stack: Array[Double]
    def loop(sp: Int, ip: Int)
      if ip == ins.size then stack(sp - 1)
      else ins(ip) match
        case Lit(value) =>
          stack(sp) = value
          loop(sp + 1, ip + 1)
      // ...

Dispatch carries out operation and advances instruction pointer

private final var sp: Int = 0
private final var ip: Int = 0
 
sealed abstract class Op extends Function0[Unit]
// ...
 
final def eval(program: Array[Op]): Double =
  @tailrec def loop(): Double =
    if ip == program.size then stack(sp - 1)
    else
      val ins = program(ip)
      ins()
      ip = ip + 1
      loop()
  loop()

Dispatch calls function and advances instruction pointer

Known as subroutine threading

Tree walking: ~2750 iterations per second

Stack machine: ~3550 iterations per second

Dualized stack machine: ~542,000,000 iterations per second

Other dualities?

Returns are dual to calls

val a = someFunction()
anotherFunction(a)
 
someFunction((a) => anotherFunction(a))

Direct style and continuation-passing style

Direct threading

Another performance improvement

Duality relates AST and stack machine

Duality can explain interpreter dispatch

Duality gives systematic relationships between concepts

For example, relate FP and OO implementation techniques

Imperial photo by Chengxin Zhao on Pexels.

Questions?

@noelwelsh

noel@noelwelsh.com

https://noelwelsh.com/posts/understanding-vm-dispatch/