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?