I was working to derive the Z-Combinator by starting with the factorial function and ended up deriving a different fixed-point combinator. What did I derive? Did I make a subtle mistake?
Here are the steps I performed (in JavaScript)
1. Declare factorial function
let fact = n => n < 2 ? 1 : n * fact(n - 1) 2. Convert to combinator (closed expression)
let fact = (self, n) => n < 2 ? 1 : n * self(n - 1) 3. Thread self call
Based on signature fact(?, 7), passing fact as first argument seems reasonable fact(fact,7). So thread the parameter through the tail call:
let fact = (self, n) => n < 2 ? 1 : n * self(self, n - 1) Usage is now fact(fact,7) → 5040
4. Refactor to curried form
let fact = self => n => n < 2 ? 1 : n * self(self)(n - 1) 5. Move self application to local declaration
let fact = self => { let f = n => self(self)(n) return n => n < 2 ? 1 : n * f(n - 1) } 6. Convert let declaration to lambda expression
let fact = self => (f => n => n < 2 ? 1 : n * f(n - 1) )( n => self(self)(n) ) Usage is still fact(fact)(7) → 5040
7. Separate the factorial expression
let _fact = f => n => n < 2 ? 1 : n * f(n - 1) let fact = self => ( _fact )( n => self(self)(n) ) 8. Move self-application from caller to body
let _fact = f => n => n < 2 ? 1 : n * f(n - 1) let fact = (() => { let innerFact = self => ( _fact )( n => self(self)(n) ) return innerFact(innerFact) })() Usage is now fact(7) → 5040
9. Convert let declaration to lambda expression
let _fact = f => n => n < 2 ? 1 : n * f(n - 1) let fact = (() => { return ( innerFact => innerFact(innerFact) )( self => (_fact)(n => self(self)(n)) ) })() 10. Simplify expression
let _fact = f => n => n < 2 ? 1 : n * f(n - 1) let fact = (innerFact => innerFact(innerFact)) (self => (_fact)(n => self(self)(n))) Sanity check. Usage is still fact(7) → 5040
11. Rename variables
The usage of innerFact and self look suspiciously similar. Rename to the same variable to discover a pattern. Separate lexical scopes so safe to do:
let _fact = f => n => n < 2 ? 1 : n * f(n - 1) let fact = (u => u(u)) (u => (_fact)(n => u(u)(n))) 12. Abstract _fact usage and rename fact
Rename fact to setup and abstract _fact in body by replacing with parameter f
let _fact = f => n => n < 2 ? 1 : n * f(n - 1) let setup = f => (u => u(u)) (u => (f)(n => u(u)(n))) let fact = setup(_fact) No need for separate _fact declaration so inline:
let setup = f => (u => u(u)) (u => (f)(n => u(u)(n))) let fact = setup( f => n => n < 2 ? 1 : n * f(n - 1) ) 13. Rename setup
Rename it to what? What combinator is this? According to Wikipedia The Z combinator is:
let Z = f => (u => f(v => u(u)(v))) (u => f(v => u(u)(v))) But what I’ve derived is:
let setup = f => (u => u(u)) (u => (f)(n => u(u)(n))) Defining fact in terms of either seems equivalent in behavior. Did I make a mistake? Did I accidentally rediscover another well-known combinator?
