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