Designing with Duality
Noel Welsh
Inner Product
Systematic program design
Duality
Interpreters
Interpreters
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
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
a and b |
true | false |
|---|---|---|
| true | true | false |
| false | false | false |
a or b |
true | false |
|---|---|---|
| true | true | true |
| false | true | false |
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?
A Dual 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
Conclusions
Duality relates AST and stack machine
Duality can explain interpreter dispatch
| Direct | CPS | |
|---|---|---|
| Data | AST | Indirect threaded |
| Codata | Subroutine | Direct threaded |
Duality gives systematic relationships between concepts
For example, relate FP and OO implementation techniques
Thanks!
Imperial photo by Chengxin Zhao on Pexels.
Questions?
@noelwelsh
noel@noelwelsh.com