Hex Casting compiler ideas

0_initial_brainstorming.md

Basic Control Flow

Given an arbitrary program:

@main def lcm(a: Int, b: Int): Int =
  if(a < b) (a * (b / gcd(b, a))
  else (b * (a / gcd(a, b))

def gcd(a: Int, b: Int): Int =
  if(b == 0) a
  else gcd(b, a % b)

Convert into typed closures, one closure for each branch:

@main def lcm = // a b -- lcm(a, b)
  dup2() // a b -- a b a b
  less() // a b -- a b (a<b)
  'lcm_alessb // a b (a<b) -- a b (a<b) 'lcm_alessb
  'lcm_ageqb // a b (a<b) 'lcm_alessb 'lcm_ageqb
  augur() // a b (branch)
  hermes()

def lcm_alessb = // a b -- lcm(a, b) // given a < b
  dup2() // a b -- a b a b
  swap() // a b a b -- a b b a
  'gcd // a b b a -- a b b a 'gcd
  hermes() // a b b a 'gcd -- a b gcd(b, a)
  division() // a b gcd(b, a) -- a (b / gcd(b, a))
  floor() // a (b / gcd(b, a)) -- a (b // gcd(b, a))
  multiply() // a (b // gcd(b, a)) -- (a * (b // gcd(b, a)))

def lcm_ageqb = // a b -- lcm(a, b) // given a >= b
  swap() // a b -- b a
  dup2() // b a -- b a b a
  swap() // b a b a -- b a a b
  'gcd // b a a b -- b a a b 'gcd
  hermes() // b a a b 'gcd -- b a gcd(a, b)
  division() // b a gcd(a, b) -- b (a / gcd(a, b))
  floor() // b (a / gcd(a, b)) -- b (a // gcd(a, b))
  multiply() // b (a // gcd(a, b)) -- (b * (a // gcd(a, b)))

def gcd = // a b -- gcd(a, b)
  dup() // a b -- a b b
  reflection(0) // a b b -- a b b 0
  equal() // a b b 0 -- a b (b==0)
  'gcd_beqz // a b (b==0) -- a b (b==0) 'gcd_beqz
  'gcd_bnez // a b (b==0) 'gcd_beqz -- a b (b==0) 'gcd_beqz 'gcd_bnez
  augur() // a b (branch)
  hermes()

def gcd_beqz = // a b -- gcd(a, b) // given b == 0
  drop() // a b -- a

def gcd_bnez = // a b -- gcd(a, b) // given b != 0
  undertake() // a b -- b a b
  modulo() // a b -- b (a%b)
  'gcd // b (a%b) -- b (a%b) 'gcd
  hermes()

Convert each closure to one that allocates the dependency list of its dependencies and releases its own dependencies, the @main function is the only one doing introspection:

@main def lcm = // a b -- lcm(a, b)
  'gcd_beqz
  rotate2()
  'gcd_bnez
  rotate2()
  'gcd
  rotate2()
  'lcm_alessb
  rotate2()
  'lcm_ageqb
  rotate2()
  'lcm_entry
  hermes()

def lcm_entry = // gcd_beqz gcd_bnez gcd lcm_alessb lcm_ageqb a b -- lcm(a, b)
  // the combined dependencies of this closure have a dependency list of [gcd_beqz gcd_bnez gcd]
  reflection(6) // gcd_beqz gcd_bnez gcd lcm_alessb lcm_ageqb a b --
  fisherman2()
  rotate2() // rotate2() is a special case of reflection(-2) fisherman()
  reflection(6)
  fisherman2()
  rotate2()
  reflection(6)
  fisherman2()
  rotate2() // -- gcd_beqz gcd_bnez gcd lcm_alessb lcm_ageqb gcd_beqz gcd_bnez gcd a b

  dup2() // ... a b -- ... a b a b
  less() // ... a b a b -- ... a b (a<b)
  reflection(7) // ... a b (a<b) -- ... a b (a<b) 7
  fisherman2() // gcd_beqz gcd_bnez gcd lcm_alessb lcm_ageqb gcd_beqz gcd_beqz gcd a b (a<b) 7 -- ... a b (a<b) lcm_alessb
  reflection(7) // ... a b (a<b) lcm_alessb -- ... a b (a<b) lcm_alessb 7
  fisherman2() // ... a b (a<b) lcm_alessb 7 -- ... a b (a<b) lcm_alessb lcm_ageqb
  augur() // ... gcd_beqz gcd_bnez gcd a b (branch)
  hermes()
  bookkeeper("vvvvv-") // gcd_beqz gcd_bnez gcd lcm_alessb lcm_ageqb lcm(a, b) -- lcm(a, b)

def lcm_alessb = // gcd_beqz gcd_bnez gcd a b -- lcm(a, b) // given a < b
  // we use the rest of the stack
  dup2() // ... a b -- ... a b a b
  swap() // ... a b a b -- ... a b b a
  
  // then prepare the arguments for the sub-call
  // gcd's dependency list is [gcd_beqz gcd_bnez gcd]
  reflection(6)
  fisherman2()
  rotate2()
  reflection(6)
  fisherman2()
  rotate2()
  reflection(6)
  fisherman2()
  rotate2() // -- gcd_beqz gcd_bnez gcd a b gcd_beqz gcd_bnez gcd b a
  
  reflection(7) // ... b a -- ... b a 7
  fisherman2() // gcd_beqz gcd_bnez gcd a b gcd_beqz gcd_bnez gcd b a 7 -- ... a b ... b a gcd
  hermes() // gcd_beqz gcd_bnez gcd a b gcd_beqz gcd_bnez gcd b a gcd -- gcd_beqz gcd_bnez gcd a b gcd(b, a)
  division() // ... a b gcd(b, a) -- ... a (b / gcd(b, a))
  floor() // ... a (b / gcd(b, a)) -- ... a (b // gcd(b, a))
  multiply() // ... a (b // gcd(b, a)) -- ... (a * (b // gcd(b, a)))
  bookkeeper("vvv-") // gcd_beqz gcd_bnez gcd lcm(a, b) -- lcm(a, b)

def lcm_ageqb = // gcd_beqz gcd_bnez gcd a b -- lcm(a, b) // given a >= b
  // store what we need for later
  swap() // ... a b -- ... b a
  dup2() // ... b a -- ... b a b a
  
  // set up the stack for the sub-call
  // gcd's dependency list is [gcd_beqz gcd_bnez gcd]
  reflection(6)
  fisherman2()
  rotate2()
  reflection(6)
  fisherman2()
  rotate2()
  reflection(6)
  fisherman2()
  rotate2() // -- gcd_beqz gcd_bnez gcd b a gcd_beqz gcd_bnez gcd b a
  
  swap() // ... b a -- ... a b
  reflection(7) // ... a b -- ... a b 7
  fisherman2() // gcd_beqz gcd_bnez gcd b a gcd_beqz gcd_bnez gcd a b 7 -- ... a b gcd
  hermes() // gcd_beqz gcd_bnez gcd b a gcd_beqz gcd_bnez gcd a b gcd -- gcd_beqz gcd_bnez gcd b a gcd(a, b)
  division() // ... b a gcd(a, b) -- ... b (a / gcd(a, b))
  floor() // ... b (a / gcd(a, b)) -- ... b (a // gcd(a, b))
  multiply() // ... b (a // gcd(a, b)) -- ... (b * (a // gcd(a, b)))
  bookkeeper("vvv-") // gcd_beqz gcd_bnez gcd lcm(a, b) -- lcm(a, b)

def gcd = // gcd_beqz gcd_bnez gcd a b -- gcd(a, b)
  // the union of gcd_beqz's and gcd_bnez's dependency list is [gcd_beqz gcd_bnez gcd]
  reflection(4)
  fisherman2()
  rotate2()
  reflection(4)
  fisherman2()
  rotate2()
  reflection(4)
  fisherman2()
  rotate2() // -- gcd_beqz gcd_bnez gcd gcd_beqz gcd_bnez gcd a b

  dup() // ... a b -- ... a b b
  reflection(0) // ... a b b -- ... a b b 0
  equal() // ... a b b 0 -- ... a b (b==0)
  reflection(8) // ... a b (b==0) -- ... a b (b==0) 8
  fisherman2() // gcd_beqz gcd_bnez gcd gcd_beqz gcd_bnez gcd a b (b==0) 8 -- ... a b (b==0) gcd_beqz
  reflection(8) // ... a b (b==0) gcd_beqz -- ... a b (b==0) gcd_beqz 8
  fisherman2() // ... a b (b==0) gcd_beqz 8 -- ... a b (b==0) gcd_beqz gcd_bnez
  augur() // ... a b (branch)
  hermes()
  bookkeeper("vvv-") // ... -- gcd(a, b)

def gcd_beqz = // gcd_beqz gcd_bnez gcd a b -- gcd(a, b) // given b == 0
  drop() // a b -- a
  bookkeeper("vvv-") // ... -- a

def gcd_bnez = // gcd_beqz gcd_bnez gcd a b -- gcd(a, b) // given b != 0
  // gcd's dependency list is [gcd_beqz gcd_bnez gcd]
  reflection(4)
  fisherman2()
  rotate2()
  reflection(4)
  fisherman2()
  rotate2()
  reflection(4)
  fisherman2()
  rotate2() // -- gcd_beqz gcd_bnez gcd gcd_beqz gcd_bnez gcd a b

  undertake() // a b -- b a b
  modulo() // a b -- b (a%b)
  reflection(5) // ... b (a%b) -- ... b (a%b) 5
  fisherman2() // gcd_beqz gcd_bnez gcd gcd_beqz gcd_bnez gcd b (a%b) 5 -- ... b (a%b) gcd
  hermes()
  bookkeeper("vvv-") // ... -- gcd(a, b)

This leads to the Hex-Studio code

{
    Bookkeeper's Gambit: v
    Bookkeeper's Gambit: vvv-
}
Rotation Gambit II
{
    Numerical Reflection: 4
    Fisherman's Gambit II
    Rotation Gambit II
    Numerical Reflection: 4
    Fisherman's Gambit II
    Rotation Gambit II
    Numerical Reflection: 4
    Fisherman's Gambit II
    Rotation Gambit II
    Undertaker's Gambit
    Modulus Distillation
    Numerical Reflection: 5
    Fisherman's Gambit II
    Hermes' Gambit
    Bookkeeper's Gambit: vvv-
}
Rotation Gambit II
{
    Numerical Reflection: 4
    Fisherman's Gambit II
    Rotation Gambit II
    Numerical Reflection: 4
    Fisherman's Gambit II
    Rotation Gambit II
    Numerical Reflection: 4
    Fisherman's Gambit II
    Rotation Gambit II
    Gemini Decomposition
    Numerical Reflection: 0
    Equality Distillation
    Numerical Reflection: 8
    Fisherman's Gambit II
    Numerical Reflection: 8
    Fisherman's Gambit II
    Augur's Exaltation
    Hermes' Gambit
    Bookkeeper's Gambit: vvv-
}
Rotation Gambit II
{
    Dioscuri Gambit
    Jester's Gambit
    Numerical Reflection: 6
    Fisherman's Gambit II
    Rotation Gambit II
    Numerical Reflection: 6
    Fisherman's Gambit II
    Rotation Gambit II
    Numerical Reflection: 6
    Fisherman's Gambit II
    Rotation Gambit II
    Numerical Reflection: 7
    Fisherman's Gambit II
    Hermes' Gambit
    Division Distillation
    Floor Purification
    Multiplicative Distillation
    Bookkeeper's Gambit: vvv-
}
Rotation Gambit II
{
    Jester's Gambit
    Dioscuri Gambit
    Numerical Reflection: 6
    Fisherman's Gambit II
    Rotation Gambit II
    Numerical Reflection: 6
    Fisherman's Gambit II
    Rotation Gambit II
    Numerical Reflection: 6
    Fisherman's Gambit II
    Rotation Gambit II
    Jester's Gambit
    Numerical Reflection: 7
    Fisherman's Gambit II
    Hermes' Gambit
    Division Distillation
    Floor Purification
    Multiplicative Distillation
    Bookkeeper's Gambit: vvv-
}
Rotation Gambit II
{
    Numerical Reflection: 6
    Fisherman's Gambit II
    Rotation Gambit II
    Numerical Reflection: 6
    Fisherman's Gambit II
    Rotation Gambit II
    Numerical Reflection: 6
    Fisherman's Gambit II
    Rotation Gambit II
    Dioscuri Gambit
    Minimus Distillation
    Numerical Reflection: 7
    Fisherman's Gambit II
    Numerical Reflection: 7
    Fisherman's Gambit II
    Augur's Exaltation
    Hermes' Gambit
    Bookkeeper's Gambit: vvvvv-
}
Hermes' Gambit

which gives the proper result.

1_next_day.md

Closures and General Recursion via Fixed Point Combinators

@main def curried(x: Int)(y: Int): Int =
  x + y

// What we can do is represent closures as List(capture1, ..., captureN, code)
// Then `splat` (Flock's Disintegration) followed by `hermes` will run a closure exactly
@main def curried = // x -- [y -- (x+y)]
  'curried2 // x -- x 'curried2
  empty_list() // x 'curried2 -- x 'curried2 [Nil]
  swap() // x 'curried2 [Nil] -- x [Nil] 'curried2 // not technically needed if we empty_list() before 'curried2
  construct() // x [Nil] 'curried2 -- x ['curried2 : Nil]
  swap() // x ['curried2 : Nil] -- ['curried2 : Nil] x
  construct() // ['curried2 : Nil] x -- [x : 'curried2 : Nil]

def curried2 = // y {x}-- (x+y)
  swap() // y x -- x y // not technically needed because addition is commutative
  add() // x y -- (x+y)

Then curried(2)(3) looks something like

Numerical Reflection: 2

{
    Jester's Gambit
    Additive Distillation
}
Vacant Reflection
Jester's Gambit
Speaker's Distillation
Jester's Gambit
Speaker's Distillation

Numerical Reflection: 3
Jester's Gambit
Flock's Disintegration
Hermes' Gambit

A more general example, both accepting and returning closures. We may want to represent a non-capturing closure (function pointer) as List(code) in most cases for compatibility. (Perhaps two different types should be used?)

@main def uncurry(f: Int => Int => Int): (Int, Int) => Int =
  (x, y) => f(x)(y)

@main def uncurry = // [x -- [y -- z]] -- [x y -- z]
  // Essentially, we create a new closure that captures f
  'uncurry2 // f -- f 'uncurry2
  empty_list() // f 'uncurry2 -- f 'uncurry2 [Nil]
  swap() // f 'uncurry2 [Nil] -- f [Nil] 'uncurry2
  construct() // f [Nil] 'uncurry2 -- x ['uncurry2 : Nil]
  swap() // f ['uncurry2 : Nil] -- ['uncurry2 : Nil] f
  construct() // ['uncurry2 : Nil] f -- [f : 'uncurry2 : Nil]

def uncurry2 = // x y {f}-- z
  rotate() // x y f -- y f x
  swap() // x y f -- y x f
  splat() // y x [x -- [y -- z]] -- y x captures... code
  hermes() // y x captures... code -- y g
  splat() // y [y -- z] -- y captures... code
  hermes() // y captures... code -- z

Say we try uncurry(curried). curried has no captures, so we can construct a closure via a singleton list:

{
    {
        Jester's Gambit
        Additive Distillation
    }
    Vacant Reflection
    Jester's Gambit
    Speaker's Distillation
    Jester's Gambit
    Speaker's Distillation
}
Single's Purification
{
    Rotation Gambit
    Jester's Gambit
    Flock's Disintegration
    Hermes' Gambit
    Flock's Disintegration
    Hermes' Gambit
}
Vacant Reflection
Jester's Gambit
Speaker's Distillation
Jester's Gambit
Speaker's Distillation

We can call this with (2, 3) by pushing 3 onto the stack, pushing 2, and then rotating the closure to the top before calling it:

Numerical Reflection: 3
Numerical Reflection: 2
Rotation Gambit
Flock's Disintegration
Hermes' Gambit

Let's try to use this to implement a general recursion combinator:

@main def Z(f: (Int => Int, Int) => Int, x: Int): Int =
  f(v => Z(f, v), x)

@main def Z = // f x -- y
  // First we need to make a recursive closure that captures f
  prospect() // f x -- f x f
  'zfClosure // f x f -- f x f 'zfClosure
  empty_list() // f x f 'zfClosure -- f x f 'zfClosure [Nil]
  swap() // f x f 'zfClosure [Nil] -- f x f [Nil] 'zfClosure
  construct() // f x f [Nil] 'zfClosure -- f x f ['zfClosure : Nil]
  swap() // f x f ['zfClosure : Nil] -- f x ['zfClosure : Nil] f
  construct() // f x ['zfClosure : Nil] f -- f x [f : 'zfClosure : Nil]
  // Then we call f with the closure and x
  swap() // f x [f : 'zfClosure : Nil] -- f [f : 'zfClosure : Nil] x
  rotate() // f [f : 'zfClosure : Nil] x -- [f : 'zfClosure : Nil] x f
  splat() // [f : 'zfClosure : Nil] x f -- [f : 'zfClosure : Nil] x captures... code
  hermes() // [f : 'zfClosure : Nil] x captures... code -- y

def zfClosure = // v {f}-- Z(f, v)
  swap() // v f -- f v
  'Z // v f -- f v 'Z
  hermes() // f v -- Z(f, v)

As these depend on each-other we have to do the stack trickery from last time:

@main def Z_entry = // f x -- y
  'zfClosure
  rotate2() // shortcut for pushing `zfClosure to the back, as {f x} is 2 stack slots
  'Z
  rotate2()
  // Duplicate Z to the front and run it
  reflection(2)
  fisherman2()
  hermes()

def Z = // zfClosure Z f x -- y
  prospect() // zfClosure Z f x -- zfClosure Z f x f
  reflection(4) // zfClosure Z f x f -- zfClosure Z f x f 4
  fisherman2() // zfClosure Z f x f -- zfClosure Z f x f zfClosure
  empty_list() // ... f x f zfClosure -- ... f x f zfClosure [Nil]
  swap() // ... f x f zfClosure [Nil] -- ... f x f [Nil] zfClosure
  construct() // ... f x f [Nil] zfClosure -- ... f x f [zfClosure : Nil]
  swap() // ... f x f [zfClosure : Nil] -- ... f x [zfClosure : Nil] f
  construct() // ... f x [zfClosure : Nil] f -- ... f x [f : zfClosure : Nil]
  reflection(3) // ... f x [f : zfClosure : Nil] -- ... f x [f : zfClosure : Nil] 3
  fisherman2() // zfClosure Z f x [f : zfClosure : Nil] 3 -- zfClosure Z f x [f : zfClosure : Nil] Z
  construct() // ... f x [f : 'zfClosure : Nil] Z -- ... f x [Z : f : zfClosure : Nil]
  reflection(4)
  fisherman2()
  construct() // -- ... f x [zfClosure : Z : f : zfClosure : Nil]
  // Then we call f with the closure and x
  swap() // ... f x [zfClosure : Z : f : zfClosure : Nil] -- ... f [zfClosure : Z : f : zfClosure : Nil] x
  rotate() // ... f [zfClosure : Z : f : zfClosure : Nil] x -- ... [zfClosure : Z : f : zfClosure : Nil] x f
  splat() // ... [zfClosure : Z : f : zfClosure : Nil] x f -- ... [zfClosure : Z : f : zfClosure : Nil] x captures... code
  hermes() // ... [zfClosure : Z : f : zfClosure : Nil] x captures... code -- ... y
  bookkeeper("vv-") // zfClosure Z y -- y

def zfClosure = // v {zfClosure Z f}-- Z(f, v)
  reflection(4) // v zfClosure Z f -- v zfClosure Z f 4
  fisherman() // v zfClosure Z f 4 -- zfClosure Z f v
  reflection(2) // zfClosure Z f v -- zfClosure Z f v 2
  fisherman2() // zfClosure Z f v 2 -- zfClosure Z f v Z
  hermes() // f v -- Z(f, v)

{
    Numerical Reflection: 4
    Fisherman's Gambit
    Numerical Reflection: 2
    Fisherman's Gambit II
    Hermes' Gambit
}
Rotation Gambit II
{
    Prospector's Gambit
    Numerical Reflection: 4
    Fisherman's Gambit II
    Vacant Reflection
    Jester's Gambit
    Speaker's Distillation
    Jester's Gambit
    Speaker's Distillation
    Numerical Reflection: 3
    Fisherman's Gambit II
    Speaker's Distillation
    Numerical Reflection: 4
    Fisherman's Gambit II
    Speaker's Distillation
    Jester's Gambit
    Rotation Gambit
    Flock's Disintegration
    Hermes' Gambit
    Bookkeeper's Gambit: vv-
}
Rotation Gambit II
Numerical Reflection: 2
Fisherman's Gambit II
Hermes' Gambit

Let's define a factorial function that can be used with this:

def factPart(me: Int => Int, x: Int): Int =
  if(x == 0) 1
  else x * me(x - 1)

def factPart = // me x -- x!
  dup() // me x -- me x x
  reflection(0) // me x x -- me x x 0
  equal() // me x x -- me x (x==0)
  'exitCase // me x (x==0) -- me x (x==0) 'exitCase
  'recursiveCase // me x (x==0) 'exitCase -- me x (x==0) 'exitCase 'recursiveCase
  augur() // me x case
  hermes() // x!

def exitCase = // me x -- x! // given x == 0
  bookkeeper("vv")
  reflection(1)

def recursiveCase = // me x -- x! // given x != 0
  dup() // me x -- me x x
  reflection(-1) // me x x -- me x x -1
  add() // me x x -- me x (x-1)
  rotate() // me x (x-1) -- x (x-1) me
  splat() // x (x-1) me -- x (x-1) captures... code
  hermes() // x (x-1) captures... code -- x me(x-1)
  multiply() // x me(x-1) -- (x*me(x-1))

Due to this function not being directly recursive, we can express it with no further issue, and we wrap it once due to Z expecting a closure:

{
    Gemini Decomposition
    Numerical Reflection: 0
    Equality Distillation
    {
        Bookkeeper's Gambit: vv
        Numerical Reflection: 1
    }
    {
        Gemini Decomposition
        Numerical Reflection: -1
        Additive Distillation
        Rotation Gambit
        Flock's Disintegration
        Hermes' Gambit
        Multiplicative Distillation
    }
    Augur's Exaltation
    Hermes' Gambit
}
Single's Purification

And we'll push a number to the stack to operate on, say 5:

Numerical Reflection: 5

(The order of the symbols here is the factPart definition, then the 5 push, then the Z definition, resulting in an output stack of [120].)

Let's verify that this works with non-linear recursion:

def fib(me: Int => Int, x: Int): Int =
  if(x < 2) x
  else me(x - 1) + me(x - 2)

def fibPart = // me x -- fib(x)
  dup()
  reflection(2)
  less() // -- me x (x<2)
  '{ bookkeeper("v-") }
  'recursiveCase
  augur()
  hermes()

def recursiveCase = // me x -- fib(x)
  dup2() // me x -- me x me x
  reflection(-1)
  add() // -- me x me (x-1)
  swap() // -- me x (x-1) me
  splat()
  hermes() // -- me x fib(x-1)
  rotate2() // -- fib(x-1) me x
  reflection(-2)
  add()
  swap()
  splat()
  hermes()
  add()

{
    Gemini Decomposition
    Numerical Reflection: 2
    Minimus Distillation
    {
        Bookkeeper's Gambit: v-
    }
    {
        Dioscuri Gambit
        Numerical Reflection: -1
        Additive Distillation
        Jester's Gambit
        Flock's Disintegration
        Hermes' Gambit
        Rotation Gambit II
        Numerical Reflection: -2
        Additive Distillation
        Jester's Gambit
        Flock's Disintegration
        Hermes' Gambit
        Additive Distillation
    }
    Augur's Exaltation
    Hermes' Gambit
}
Single's Purification

Z(fib, 10) reduces to 55 in 9,000-ish steps:

2_day3_ir.md

Day 3: IR?

We can develop an alternative, but less edge-cased grammar:

program
    : block
    ;

block
    : statement* expression
    ;

statement
    : defStatement
    | ...
    ;

expression
    : ifExpression
    | blockExpression
    | ...
    ;

And rather than a @main entry-point, our programs instead just have result expressions, due to the block rule:

def someFunction(x: Int) = ...

someFunction(5)

Consider the program:

def fib(n: Int): Int = {
  def go(a: Int, b: Int, n: Int): Int =
    if(n <= 0) a
    else go(b, a + b, n - 1)
  
  go(0, 1, n)
}

fib(10)

We end up with an AST (not parse-tree) like so:

graph TD;
    root[Program];
    root_block[Block];
    root-->root_block;
    fib_def[DefStatement];
    root_block-->fib_def;
    fib_id["Identifier #quot;fib#quot;"];
    fib_argument_list[BindingList];
    fib_def-->fib_id;
    fib_def-->fib_argument_list;
    fib_argument_n[Binding];
    fib_argument_list-->fib_argument_n;
    fib_argument_n_id["Identifier #quot;fib#quot;"];
    fib_argument_n_type["Type"];
    fib_argument_n_type_id["Identifier #quot;Int#quot;"];
    fib_argument_n-->fib_argument_n_id;
    fib_argument_n-->fib_argument_n_type;
    fib_argument_n_type-->fib_argument_n_type_id;
    fib_return_type[Type];
    fib_def-->fib_return_type;
    fib_return_type_id["Identifier #quot;Int#quot;"];
    fib_return_type-->fib_return_type_id;
    fib_result_expression[BlockExpression];
    fib_def-->fib_result_expression;
    fib_go_def[DefStatement];
    fib_result_expression-->fib_go_def;
    fib_go_id["Identifier #quot;go#quot;"];
    fib_go_def-->fib_go_id;
    fib_go_argument_list[BindingList];
    fib_go_def-->fib_go_argument_list;
    fib_go_a[Binding];
    fib_go_argument_list-->fib_go_a;
    fib_go_a_id["Identifier #quot;a#quot;"];
    fib_go_a-->fib_go_a_id;
    fib_go_a_type["Type"];
    fib_go_a-->fib_go_a_type;
    fib_go_a_type_id["Identifier #quot;Int#quot;"];
    fib_go_a_type-->fib_go_a_type_id;
    fib_go_b[Binding];
    fib_go_argument_list-->fib_go_b;
    fib_go_b_id["Identifier #quot;b#quot;"];
    fib_go_b-->fib_go_b_id;
    fib_go_b_type["Type"];
    fib_go_b-->fib_go_b_type;
    fib_go_b_type_id["Identifier #quot;Int#quot;"];
    fib_go_b_type-->fib_go_b_type_id;
    fib_go_n[Binding];
    fib_go_argument_list-->fib_go_n;
    fib_go_n_id["Identifier #quot;n#quot;"];
    fib_go_n-->fib_go_n_id;
    fib_go_n_type["Type"];
    fib_go_n-->fib_go_n_type;
    fib_go_n_type_id["Identifier #quot;Int#quot;"];
    fib_go_n_type-->fib_go_n_type_id;
    fib_go_type["Type"];
    fib_go_def-->fib_go_type;
    fib_go_type_id["Identifier #quot;Int#quot;"];
    fib_go_type-->fib_go_type_id;
    fib_go_expr[IfExpression];
    fib_go_def-->fib_go_expr;
    fib_go_expr_cond[LteqExpression];
    fib_go_expr-->fib_go_expr_cond;
    fib_go_expr_cond_l["Identifier #quot;n#quot;"];
    fib_go_expr_cond-->fib_go_expr_cond_l;
    fib_go_expr_cond_r["IntegerLiteral 0"];
    fib_go_expr_cond-->fib_go_expr_cond_r;
    fib_go_expr_ift["Identifier #quot;n#quot;"];
    fib_go_expr-->fib_go_expr_ift;
    fib_go_expr_iff[ApplyExpression];
    fib_go_expr-->fib_go_expr_iff;
    fib_go_expr_iff_id["Identifier #quot;go#quot;"];
    fib_go_expr_iff-->fib_go_expr_iff_id;
    fib_go_expr_iff_args["ArgumentList"];
    fib_go_expr_iff-->fib_go_expr_iff_args;
    fib_go_expr_iff_b["Identifier #quot;b#quot;"];
    fib_go_expr_iff_args-->fib_go_expr_iff_b;
    fib_go_expr_iff_ab[AddExpression];
    fib_go_expr_iff_args-->fib_go_expr_iff_ab;
    fib_go_expr_iff_ab_l["Identifier #quot;a#quot;"];
    fib_go_expr_iff_ab-->fib_go_expr_iff_ab_l;
    fib_go_expr_iff_ab_r["Identifier #quot;b#quot;"];
    fib_go_expr_iff_ab-->fib_go_expr_iff_ab_r;
    fib_go_expr_iff_n1[SubtractExpression];
    fib_go_expr_iff_args-->fib_go_expr_iff_n1;
    fib_go_expr_iff_n1_l["Identifier #quot;n#quot;"];
    fib_go_expr_iff_n1-->fib_go_expr_iff_n1_l;
    fib_go_expr_iff_n1_r["IntegerLiteral 1"];
    fib_go_expr_iff_n1-->fib_go_expr_iff_n1_r;
    fib_block_result["ApplyExpression"];
    fib_result_expression-->fib_block_result;
    fib_block_id["Identifier #quot;go#quot;"];
    fib_block_result-->fib_block_id;
    fib_block_args["ArgumentList"];
    fib_block_result-->fib_block_args;
    fib_block_arg0["IntegerLiteral 0"];
    fib_block_args-->fib_block_arg0;
    fib_block_arg1["IntegerLiteral 1"];
    fib_block_args-->fib_block_arg1;
    fib_block_argn["Identifier #quot;n#quot;"];
    fib_block_args-->fib_block_argn;
    result_expr[ApplyExpression];
    root_block-->result_expr;
    result_id["Identifier #quot;fib#quot;"];
    result_expr-->result_id;
    result_args["ArgumentList"];
    result_expr-->result_args;
    result_arg_10["IntegerLiteral 10"];
    result_args-->result_arg_10;

Loading

We can perform type-checking and renaming:

def fib(n_0) = {
  def go(a_1, b_1, n_1) =
    if(n_1 <= 0) a_1
    else go(b_1, a_1 + b_1, n_1 - 1)

  go(0, 1, n_0)
}

fib(10)

And compile down to a 3-address-like intermediate language:

val fib = function {
  val n_0 = allocateArgument()
  val go = closure {
    val a_1 = allocateArgument()
    val b_1 = allocateArgument()
    val n_1 = allocateArgument()
    val literal_0 = allocateLiteral(0)
    val condition = allocateOp(Op.Lteq, n_1, literal_0)
    val true_branch = closure {
      a_1
    }
    val false_branch = closure {
      val nextb = allocateOp(Op.Add, a_1, b_1)
      val literal_1 = allocateLiteral(1)
      val nextn = allocateOp(Op.Subtract, n_1, literal_1)
      call(go, b_1, nextb, nextn)
    }
    if(condition, true_branch, false_branch)
  }
  val literal_0 = allocateLiteral(0)
  val literal_1 = allocateLiteral(1)
  call(go, literal_0, literal_1, n_0)
}

call(fib, 10)

This IR is easily rewritable into spells.

Some things to figure out:

1. true_branch and false_branch do not need to capture themselves, but go does. Why? Is it because true_branch and false_branch aren't used by name within themselves, while go is?
2. go is marked as a closure yet does not capture anything defined in fib. This means that the optimizer should rewrite go to be a function rather than a closure.
3. How does call work in regards to registers, and how do output registers work?

Let's give a few more examples:

def uncurry(f: Int => Int => Int): (Int, Int) => Int =
  (x, y) => f(x)(y)

uncurry

val uncurry = function {
  val f = allocateArgument()
  val result = closure {
    val x = allocateArgument()
    val y = allocateArgument()
    val g = call(f, x)
    call(g, y)
  }
  result
}

uncurry

The capture of f in result is determinable at compile time.

Some things to figure out:

4. How to distinguish between calling functions (hermes) vs calling closures (splat, hermes) at the IR level?
5. Should (can?) we support functions that store multiple values on the stack? (Unboxed tuples?)
6. With the above question, how does call result in a virtual register?

3_polymorphism_closure_captures.md

Parametric Polymorphism

We can introduce a pi-type TypeList '~>' Type that allows binding type variables.

val Nil: [A] ~> List[A]

val Z: [A, B] ~> ((A => B, A) => B, A) => B =
  [A, B] ~> (f: (A => B, A) => B, x: A) =>
    f((v: A) => Z[A, B](f, v), x)

For all well-typed expressions, without monomorphization we can instantiate these variables with any type of stack size 1. This includes most types except for tuples and unboxed structs.

Closures, Captures

Consider that it's important to know whether a def needs captures or not. Let's remove defs entirely, and define value function types TupleType -> TupleType for "pointers" and TupleType => TupleType for closures. (A => B is implicitly (A) => (B), and all tuples are unboxed. Two birds, one stone)

val isEven: Int => Boolean =
  (n: Int) =>
    if(n == 0) true
    else isOdd(n - 1)

val isOdd: Int => Boolean =
  (n: Int) =>
    if(n == 0) false
    else isEven(n - 1)

For closures that are in a cycle of captures:

graph TD;
    isEven-->isOdd;
    isOdd-->isEven;

Loading

Any capture of said closure needs to capture the cycle as function pointers rather than closures themselves. That is, because the lists isEven = [isOdd, isEvenPtr], isOdd = [isEven, isOddPtr] are obviously not constructable in a strict immutable context, we need to settle for something non-recursive: isEven = [isEvenPtr, isOddPtr, isEvenPtr], isOdd = [isOddPtr, isEvenPtr, isOddPtr].

A closure will always know the way it will be called externally (by being represented as [args..., code]). However, isEven has to manually reconstruct [isOddPtr, isEvenPtr, isOddPtr] to get the isOdd closure. This means that any closure that is a part of mutual recursion needs to know all of its mutual recursion buddies.

This solves the following questions from Day 3:

1. true_branch and false_branch do not need to capture themselves as they are not captures of go. Strictly speaking, they only need to capture the go closure, which itself reconstructs true_branch and false_branch as part of its own code.
2. This is easy to check if we have a graph system in place for captures to detect cycles anyways.
3. call can expect an input and output arity, and return a list of output VRs.
4. This does not need to be done manually at the IR level if we have separate types (and thus separate IR generation paths) for fptrs and closures.
5. With unboxed tuples, we can support almost every primitive operation. Ones that dynamically affect stack size are still an issue (splat, etc) but as those are solely stack manipulation primitives and have no outstanding useful properties, we do not need to codify them. (The Hex Casting stack is an implementation detail of our higher-level language.)

Question (6) is still an issue. I'll have to relearn how to bind output VRs of the callee to intermediate VRs of the caller.

4_unified_functions_closures.md

Unifying Functions and Closures

One can unify functions and closures under the same type. Introspection, when executed, can create a list of iotas on the stack, not just patterns.

We can use this like so:

val isEven: Int => Boolean =
  (n: Int) =>
    if(n == 0) true
    else isOdd(n - 1)

val isOdd: Int => Boolean =
  (n: Int) =>
    if(n == 0) false
    else isEven(n - 1)

isEven

def isEvenPtr = // number isEvenPtr isOddPtr -- boolean
  rotate // -- isEvenPtr isOddPtr number
  dup // -- isEvenPtr isOddPtr number number
  0 // -- isEvenPtr isOddPtr number number 0
  eq // -- isEvenPtr isOddPtr number (number==0)
  { // isEvenPtr isOddPtr number --
    bookkeeper's: vvv // --
    true // -- true
  }
  { // isEvenPtr isOddPtr number --
    1
    subtract
    rotate2 // -- number-1 isEvenPtr isOddPtr
    swap
    prospectors // -- number-1 isOddPtr isEvenPtr isOddPtr
    hermes
  }
  augur's exaltation
  hermes

def isOddPtr = // number isOddPtr isEvenPtr -- boolean
  rotate // -- issOdPtr isEvenPtr number
  dup // -- isOddPtr isEvenPtr number number
  0 // -- isOddPtr isEvenPtr number number 0
  eq // -- isOddPtr isEvenPtr number (number==0)
  { // isOddPtr isEvenPtr number --
    bookkeeper's: vvv // --
    false // -- false
  }
  { // isOddPtr isEvenPtr number --
    1
    subtract
    rotate2 // -- number-1 isOddPtr isEvenPtr
    swap
    prospectors // -- number-1 isEvenPtr isOddPtr isEvenPtr
    hermes
  }
  augur's exaltation
  hermes

def isEven = // -- [number -- boolean]
  { { disintegrate } } // -- [intro, disintegrate, retro]
  disintegrate // -- intro disintegrate retro
  isEvenPtr // -- intro disintegrate retro isEvenPtr
  dup // -- intro disintegrate retro isEvenPtr isEvenPtr
  isOddPtr // -- intro disintegrate retro isEvenPtr isEvenPtr isOddPtr
  377
  swindle  // -- isEvenPtr intro isEvenPtr isOddPtr retro disintegrate
  5
  Flock's Gambit // -- isEvenPtr [intro, isEvenPtr, isOddPtr, retro, disintegrate]
  swap
  combination // -- captures ++ code

We get Introspection, Flock's Disintegration, and Retrospection on the stack using { { disintegrate } }. We need the extra Flock's Disintegration as Introspection ends up creating a list on the stack (while our functions expect raw stack slots to be used).

{
    {
        Flock's Disintegration
    }
}
Flock's Disintegration
{
    Rotation Gambit
    Gemini Decomposition
    Numerical Reflection: 0
    Equality Distillation
    {
        Bookkeeper's Gambit: vvv
        True Reflection
    }
    {
        Numerical Reflection: 1
        Subtractive Distillation
        Rotation Gambit II
        Jester's Gambit
        Prospector's Gambit
        Hermes' Gambit
    }
    Augur's Exaltation
    Hermes' Gambit
}
Gemini Decomposition
{
    Rotation Gambit
    Gemini Decomposition
    Numerical Reflection: 0
    Equality Distillation
    {
        Bookkeeper's Gambit: vvv
        False Reflection
    }
    {
        Numerical Reflection: 1
        Subtractive Distillation
        Rotation Gambit II
        Jester's Gambit
        Prospector's Gambit
        Hermes' Gambit
    }
    Augur's Exaltation
    Hermes' Gambit
}
Numerical Reflection: 377
Swindler's Gambit
Numerical Reflection: 5
Flock's Gambit
Jester's Gambit
Combination Distillation

Essentially, we create a list of captures, but with Introspection and Retrospection on each end, and this way we can prepend the captures to the code instead of nesting them, allowing for a regular Hermes' Gambit to be used (thus unifying functions and closures under one interface).

5_statically_constructible.md

Live and let rec Die

We have a time travel problem. Consider the case of

val x = { y; numberAroundMe(SheepType) }
val y = killAroundMe(SheepType)

The current syntax rules don't disallow this, nor do the current evaluation rules define what behavior it should have. We can take a look at OCaml for inspiration:

let x = y; numberAroundMe(SheepType)
let y = killAroundMe(SheepType)

In let x =, we yet have no y binding, and as such this program fails to compile. If we mark x and y as mutually recursive,

let rec x = y; numberAroundMe(SheepType)
and y = killAroundMe(SheepType)

let rec x = still fails to compile, because the right-hand side references y in a way that is not "statically constructible".

Our new rules for binding names are non-rec:

[previous scope]
(* e1, e2, etc. only know about [previous scope]'s bindings *)
let x = e1 [and y = e2 [and z = ...]]
(* x, y, etc. are only available by [next scope] *)
[next scope]

(* due to these rules, these bindings cannot be recursive, but we can i.e. swap names *)
let x = 1
let y = 2

let x = y and y = x
(* x = 2, y = 1 *)

And rec:

let rec x = e1 [and y = e2 [and z = ...]]
(* the major difference here is e1, e2, etc. are allowed to reference x, y, etc. *)
(* however, variables are not allowed to be referenced "strictly" *)

In this language, our only "non-strict" context is the right-hand-side of a function. This gives us a framework to define things like

let rec foo = [random(), () -> foo, () -> bar]
and bar = [random(), () -> foo, () -> bar]

Where the two random values are not re-evaluated, i.e. the () -> foo lambda returns the same random number every time.

"Partial Construction" and "Construction Procedures"

Here's what we know:

• foo references foo and bar on its right-hand side, so foo has a "partially constructed" form that does not reference foo or bar and has a construction procedure that includes the captures
• Likewise for bar
• This means the code that constructs foo (the outermost code) and the code that references foo (the function () -> foo) must both perform the construction procedure (likewise for bar)

This ends up looking like

def partialFoo = // -- partialFoo
  random
  {
    { - - } disintegrate
    prospectors
    constructFoo
  }
  {
    { - - } disintegrate
    dup
    constructBar
  }
  3
  makeList

def constructFoo = // partialFoo partialBar partialFoo -- foo
  // replace partialFoo(1) by inserting partialFoo and partialBar
  dup // -- pfoo pbar pfoo pfoo
  1
  select // -- pfoo pbar pfoo partialLambdaFoo
  // partialLambdaFoo is of the form [ { - - } disintegrate ... ]
  1 // -- pfoo pbar pfoo pLfoo 1
  4
  fish2 // -- pfoo pbar pfoo pLfoo 1 pfoo
  surgeon // -- pfoo pbar pfoo [ { pfoo - } disintegrate ... ]
  2 // -- pfoo pbar pfoo pLfoo 2
  3
  fish2 // -- pfoo pbar pfoo pLfoo 2 pbar
  surgeon // -- pfoo pbar pfoo Lfoo
  // reinsert
  1
  swap
  surgeon

  // now replace partialFoo(2)
  dup // -- pfoo pbar pfoo pfoo
  2
  select // -- pfoo pbar pfoo partialLambdaBar
  1 // -- pfoo pbar pfoo pLbar 1
  5
  fish // -- pbar pfoo pLbar 1 pfoo
  surgeon // -- pbar pfoo [ { pfoo - } disintegrate ... ]
  2 // -- pbar pfoo pLbar 2
  4
  fish // -- pfoo pLbar 2 pbar
  surgeon // -- pfoo Lbar
  // reinsert
  2
  swap
  surgeon

def fooBar =
  partialFoo
  partialBar
  dup2
  prospectors
  constructFoo
  rotate2
  dup
  constructBar
  swap

As a size optimization, we could pass Construction Procedures around as pattern lists:

def partialFoo = // 'constructFoo 'constructBar -- partialFoo
  random
  rotate
  {
    { - - } disintegrate
    prospectors
  }
  swap
  concat
  rotate
  {
    { - - } disintegrate
    dup
  }
  swap
  concat
  3
  makeList

def fooBar =
  'constructFoo
  'constructBar
  dup2 // -- cf cb cf cb
  partialFoo // -- cf cb pf
  rotate2
  dup2 // -- pf cf cb cf cb
  partialBar // -- pf cf cb pb
  3
  fish2 // -- pf cf cb pb pf
  dup2 // -- pf cf cb pb pf pb pf
  153
  swindle // -- pf pb cb pf pb pf cf
  hermes // -- pf cb pb foo
  prospect // -- pf cb pb foo pb
  75
  swindle // -- foo pf pb pb cb
  hermes // -- foo bar

partalBar and constructBar are not shown as they happen to be identical here if we order the captures to always be foo bar. I use this optimization for constructFoo being duplicated in the hexpattern:

{
    Gemini Decomposition
    Numerical Reflection: 1
    Selection Distillation
    Numerical Reflection: 1
    Numerical Reflection: 4
    Fisherman's Gambit II
    Surgeon's Exaltation
    Numerical Reflection: 2
    Numerical Reflection: 3
    Fisherman's Gambit II
    Surgeon's Exaltation
    Numerical Reflection: 1
    Jester's Gambit
    Surgeon's Exaltation
    Gemini Decomposition
    Numerical Reflection: 2
    Selection Distillation
    Numerical Reflection: 1
    Numerical Reflection: 5
    Fisherman's Gambit
    Surgeon's Exaltation
    Numerical Reflection: 2
    Numerical Reflection: 4
    Fisherman's Gambit
    Surgeon's Exaltation
    Numerical Reflection: 2
    Jester's Gambit
    Surgeon's Exaltation
}
Gemini Decomposition
Dioscuri Gambit
Entropy Reflection
Rotation Gambit
{
    {
        Bookkeeper's Gambit: -
        Bookkeeper's Gambit: -
    }
    Flock's Disintegration
    Prospector's Gambit
}
Jester's Gambit
Combination Distillation
Rotation Gambit
{
    {
        Bookkeeper's Gambit: -
        Bookkeeper's Gambit: -
    }
    Flock's Disintegration
    Gemini Decomposition
}
Jester's Gambit
Combination Distillation
Numerical Reflection: 3
Flock's Gambit
Rotation Gambit II
Dioscuri Gambit
Entropy Reflection
Rotation Gambit
{
    {
        Bookkeeper's Gambit: -
        Bookkeeper's Gambit: -
    }
    Flock's Disintegration
    Prospector's Gambit
}
Jester's Gambit
Combination Distillation
Rotation Gambit
{
    {
        Bookkeeper's Gambit: -
        Bookkeeper's Gambit: -
    }
    Flock's Disintegration
    Gemini Decomposition
}
Jester's Gambit
Combination Distillation
Numerical Reflection: 3
Flock's Gambit
Numerical Reflection: 3
Fisherman's Gambit II
Dioscuri Gambit
Numerical Reflection: 153
Swindler's Gambit
Hermes' Gambit
Prospector's Gambit
Numerical Reflection: 75
Swindler's Gambit
Hermes' Gambit

If we get the first item out of bar on the top of the stack, and execute it, it should be equivalent to foo:

Numerical Reflection: 1
Selection Distillation
Hermes' Gambit
Equality Distillation

Results in True.

6_embedded_z.md

Embedded Z

let rec Z: [A, B] ~> ((A -> B, A) -> B, A) -> B =
  [A, B] ~> (f: (A -> B, A) -> B, x: A) ->
    f((v: A) -> Z[A, B](f, v), x)

def zLambdaPtr = // v — Z(f, v)
  { - - } disintegrate // — v Z f
  rotate2 // — f v Z
  hermes

def constructZLambda = // Z f ‘zLambdaPtr — zLambda
  2
  rotate
  surgeon
  1
  rotate
  surgeon

def partialZ = // ‘constructZ — partialZ
  {
    { - } disintegrate // — f x partialZ
    dup
  }
  swap
  concat
  { // f x Z —
    rotate
    dup // — x Z f f
    rotate2 // — x f Z f
    ‘zLambdaPtr
    constructZLambda // — x f zLambda
    rotate2
    hermes
  }
  concat

def constructZ = // partialZ partialZ — Z
  /*
  partialZ = [ Intro, Bookkeeper -, Retro …]
  */
  1
  swap
  surgeon
  /*
  Z = [ Intro, partialZ, Retro …]
  */

def Z = // — Z
  ‘constructZ
  dup
  partialZ
  dup
  rotate
  hermes

{
    Numerical Reflection: 1
    Jester's Gambit
    Surgeon's Exaltation
}
Gemini Decomposition
{
    {
        Bookkeeper's Gambit: -
    }
    Flock's Disintegration
    Gemini Decomposition
}
Jester's Gambit
Combination Distillation
{
    Rotation Gambit
    Gemini Decomposition
    Rotation Gambit II
    {
        {
            Bookkeeper's Gambit: -
            Bookkeeper's Gambit: -
        }
        Flock's Disintegration
        Rotation Gambit II
        Hermes' Gambit
    }
    Numerical Reflection: 2
    Rotation Gambit
    Surgeon's Exaltation
    Numerical Reflection: 1
    Rotation Gambit
    Surgeon's Exaltation
    Rotation Gambit II
    Hermes' Gambit
}
Combination Distillation
Gemini Decomposition
Rotation Gambit
Hermes' Gambit

7_compiling_callcc.md

Compiling call/cc

Now that Hex Casting is equipped with call/cc, one might wonder if it's possible to compile down Scheme-like call/ccs in an FFI-compatible way.

A Refresher on Closures

When we create a "function" in Hex Casting, it's actually encoded as a list of instructions pushed to the stack. The code

A
{
  B
}
C

Will first execute A, then push (cons B nil) to the stack, then execute C. This pushing behavior applies to non-instruction iotas as well, allowing us to create closures:

// push a (list "{" "-" "}" "Flock's Disintegration")
{
  { - }
  Flock's Disintegration
}
// choose 1 as our insertion index
Numerical Reflection: 1
// create some sort of value
...
// "embed" the value into the closure
Surgeon's Exaltation

This code produces a list (list "{" theValue "}" "Flock's Disintegration"). This is a list that can be passed around like any other function, and when executed will place theValue on the stack.

For a more in-depth view, see note 4 (function/closure unification) and note 5 (recursive bindings).

A Primer on Iris' Gambit

The Hex Casting VM at a very basic level (missing some functionality) looks like this:

type Iota =
  | INumber : Double                   -> Iota
  | IVec    : (Double, Double, Double) -> Iota
  | IList   : (List Iota)              -> Iota
  | IInstr  : Instruction              -> Iota

type VM = {
  stack : List Iota,
  continuation : List Iota,
  ravenmind : Iota
}

Hermes' Gambit is our bog-stanard eval operation, popping a list of instructions from the stack and prepending it to the current continuation. Iris' Gambit is the eval/cc equivalent of that. Iris' Gambit does operations in the following order:

1. Pop an instruction list from the stack
2. Push the current continuation to the stack
3. Prepend the instruction list to the current continuation

So we can translate some example Scheme:

(define (f return)
  (return 2)
  3)

(f (lambda (x) x))
=> 3

(call/cc f)
=> 2

Into Hex Casting:

// define f
{
    Numerical Reflection: 2 // push 2 to the stack
    Jester's Gambit         // swap the top two stack values
    Hermes' Gambit          // call the top stack value
    Bookkeeper's Gambit: v  // drop the top stack value
    Numerical Reflection: 3 // push 3 to the stack
}

// call f with (lambda (x) x)
{}              // push a function that does no instructions to the stack
Jester's Gambit // swap the top two stack values
Hermes' Gambit  // call the top stack value

// or, call/cc f
Iris' Gambit

When a continuation is called, the current continuation in the VM is entirely replaced by the called continuation.

Hex Casting lacks a standard notion of Environment

The continuations created by Iris' Gambit do not affect the stack at all. This means we have to be careful when writing programs that may jump "down" the call stack. For example, we can write such a program in Scheme:

; the Ravenmind is a special side register in the Hex Casting VM
(define ravenmind '())
(display (+
  2
  (call/cc (lambda (x)
    (set! ravenmind x)
    1))))
; => 3
(ravenmind 5)
; => 7

The naive conversion of this program into Hex Casting would be:

// store null into the ravenmind
Nullary Reflection // push null to the stack
Huginn's Gambit    // pop from the stack and store in ravenmind

// first argument
Numerical Reflection: 2 // push 2 to the stack

// second argument's argument, the lambda
{
  // set ravenmind to the argument (a continuation)
  Huginn's Gambit
  
  // just push 1 as a return value
  Numerical Reflection: 1
}
// call/cc this function
Iris' Gambit

// Add the two values
Additive Distillation

// Display and consume the result
Reveal
Bookkeeper's Gambit: v // pops the top stack value

// Push the argument (5) to the stack
Numerical Reflection: 5
// Recall the value in the ravenmind
Muninn's Reflection
// And call the continuation
Hermes' Gambit

However, the continuation created by Iris' Gambit only contains the instructions from Additive Distillation to the end of the program. The stack only has a 5 on it when we call this continuation, because we consumed the first operand (the 2) in the previous addition, meaning the Additive Distillation in the continuation fail due to not having enough arguments. In this simple case, we know that we need to create a closure that first restores the 2 and only then calls the continuation:

// store null into the ravenmind
Nullary Reflection // push null to the stack
Huginn's Gambit    // pop from the stack and store in ravenmind

// first argument
Numerical Reflection: 2 // push 2 to the stack

// second argument's argument, the lambda
{
  // the continuation is the top value on the stack here, and we need to embed it into a closure
  // so we make a closure with two "embed slots" (captures)
  {
    { - - }
    // and destruct the list that's created here so that the values are dumped on the stack
    Flock's Disintegration
    // now that both the first argument for addition and the closure are on the stack,
    // we can actually call the closure with the argument restored
    Hermes' Gambit
  }
  // The first item we embed is the stack value we need to capture
  Numerical Reflection: 1
  // duplicate the item at a certain index down, in this case the first argument for addition
  Numerical Refleciton: 3
  Fisherman's Gambit II // pop a number, go N elements down in the stack, copy that element and push to the top
  Surgeon's Exaltation  // embed our argument
  // and we do the same for the continuation, but we can consume it instead of needing to copy it for the embedding
  Numerical Reflection: 2
  Numerical Reflection: 3
  Fisherman's Gambit // peek a number, go N elements down in the stack, remove that element from the stack and replace the top with it
  Surgeon's Exaltation
  // set ravenmind to this closure, which is essentially
  //   {
  //     restore first argument
  //     restore continuation
  //     call continuation with first argument now on stack
  //   }
  Huginn's Gambit
  
  // just push 1 as a return value
  Numerical Reflection: 1
}
// call/cc this function
Iris' Gambit

// Add the two values
Additive Distillation

// Display and consume the result
Reveal
Bookkeeper's Gambit: v // pops the top stack value

// Push the argument (5) to the stack
Numerical Reflection: 5
// Recall the value in the ravenmind
Muninn's Reflection
// And call the continuation
Hermes' Gambit

However, we make some pretty heavy assumptions here. We know that 2 is the only value that needs to be restored by the rest of the program, but what if we're returning to a function we can't introspect? We might have 1000 values on the stack when the continuation is created, and then 0 when it's called. All of those need to be properly restored.

An Aside

One might say that Scheme is a CEK language (for which I have been graciously sent https://kmicinski.com/cis400-f21/assets/slides/cek.pdf to study) while Hex Casting is a CK language (I can't seem to find this term used anywhere).

Hex Casting is taxonomically a "concatenative" language, like Factor or Forth. It is most similar to Factor in terms of how to write closures and higher-order functions.

My (Incorrect) Stack-Size Based Solution

My first solution to this was to:

1. back up the entire working stack into the closure
2. check the stack size the closure was restored with a. if the working stack is larger, just cut values until the stack size matches our restored stack b. if the working stack is smaller, restore values from the embedded stack to make up the difference

This solution has two glaring issues:

Horizontal Calls

Consider the following function:

(define (A)
  (let ((b (B)))
    (C b)))

Or in pseudo-ML

let A =
  let b = B()
  C(b)

Consider the case where B

1. pushes a bunch of things to the stack
2. creates a continuation
3. uses a bunch of things on that stack

And then C

1. pushes a bunch of different things to the stack
2. calls the continuation

Suddenly, we have returned to B with the wrong values on the stack, as C pushed their own to make up the difference, leading B to believe it didn't need to restore any of its values.

Completely Replacing the Stack

Consider the following two programs.

(define a 1)
(define b (let ()
  (define c #f)
  (display (+ a (call/cc (lambda (x) (set! c x) 1))))
  c))

(if (= a 1)
    (let ()
      (set! a 5)
      (b 2)))

(display a)

This prints 235:

• the 2 comes from initialization of b, where first a evaluates to 1, the call/cc evaluates to 1, and then they're added
• the 3 comes from (b 2), where a has already evaluated to 1 as it's an argument on the left of the call/cc, and the call/cc evaluates to 2
• the 5 comes from the final display to prove that a is not 1, even though 235 was printed instead of 275

(define a 1)
(define b (let ()
  (define c #f)
  (display (call/cc (lambda (x) (set! c x) 1)))
  (display a)
  c))

(if (= a 1) (let ()
              (set! a 5)
              (b 2)))

This prints 1125:

• the first and second 1s come from the setup, where call/cc evaluates to 1 and then a evaluates to 1
• the 2 comes from (b 2)
• the 5 comes from a being re-evaluated as its evaluation happens after call/cc

If the old value of a on the stack is stored in the closure, and the stack is completely replaced, the second program will incorrectly produce 1121, rather than re-evaluating a.

My Second Solution

...doesn't exist. I'm well and truly stuck.

Good Test Cases for Translation

Apart from the cases already mentioned, good cases to test a specific strategy for translation from Scheme to Hex Casting include:

• ((call/cc call/cc) display) should be equivalent to (display display)
• ((call/cc call/cc) (call/cc call/cc)) should be nonterminating in a finite amount of memory
• (define a #f) (define b (call/cc (lambda (x) (set! a x)))) (a a) (b 1) (display b) should display 1
• (let () (define x #f) (list (call/cc (lambda (c) (set! x c))) x)) should result in a list where the second element is a setter for the first element

These assume no following code, so they are best run in a REPL.