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.