A step-by-step explanation: From self-referencing function to fixed-point combinator

self2fpc.js

/* A step-by-step explanation (with generating Fibonacci Number): 
   From naïve self-referencing function to fixed-point combinator 
 */

// test runner
const t = (i => f => console.log(`v${i++}`, [1,2,3,4,5].map(f)))(1)

// 1 naïve approach
var fib = n => n < 2 ? 1 : fib(n - 2) + fib(n - 1)
t(fib)

// 2 add an extra parameter,
// so we formally pass in the function name instead of referencing itself
var fib = (f, n) => n < 2 ? 1 : f(f, n - 2) + f(f, n - 1)
var run = n => fib(fib, n)
t(run)

// 3 change into high order function
var fib = f => n => n < 2 ? 1 : f(f)(n - 2) + f(f)(n - 2)
var run = fib(fib)
t(run)

// 4 use longform function for fib
var fib = f => {
  return n => {
    return n < 2 ? 1 : f(f)(n - 2) + f(f)(n - 1)
  }
}
var run = fib(fib)
t(run)

// 5 formally create a seperate function for fixed-point
var fib = g => {
  return n => {
    var f = g(g)
    return n < 2 ? 1 : f(n - 2) + f(n - 1)
  }
}
var run = fib(fib)
t(run)

// 6 move fixed-point to outer layer
// which will break the code
// fix it by replacing it with lazy fixed-point variant
var fib = g => {
  // var f = g(g) // this breaks because of eager evaluation
  var f = n => g(g)(n)
  return n => {
    return n < 2 ? 1 : f(n - 2) + f(n - 1)
  }
}
var run = fib(fib)
t(run)

// 7 name the inner function
var fib = g => {
  var f = n => g(g)(n)
  var ret = n => {
    return n < 2 ? 1 : f(n - 2) + f(n - 1)
  }
  return ret
}
var run = fib(fib)
t(run)

// 8 wrap the newly named function so it looks like original `fib`
var fib = g => {
  var fn = n => g(g)(n)
  var _fib = f => n => {
    return n < 2 ? 1 : f(n - 2) + f(n - 1)
  }
  return _fib(fn)
}
var run = fib(fib)
t(run)

// 9 rename related functions since the `_fib` is what we ultimately want, 
// while `fib` is merely a wrapper
var wrap = g => {
  var fn = n => g(g)(n)
  var fib = f => n => {
    return n < 2 ? 1 : f(n - 2) + f(n - 1)
  }
  
  return fib(fn)
}
var run = wrap(wrap)
t(run)

// 10 the newly named `fib` has no implied contextual dependency
// so we can move it outside of its wrapper
var fib = f => n => n < 2 ? 1 : f(n - 2) + f(n - 1)
var wrap = g => {
  var fn = n => g(g)(n)
  return fib(fn)
}
var run = wrap(wrap)
t(run)

// 11 the `fn` is in fact a lazy fixed-point function
// we wrap this function so to remove its contextual dependency
var fib = f => n => n < 2 ? 1 : f(n - 2) + f(n - 1)
var wrap = g => {
  // lfp stands for lazy fixed-point
  var lfp = f => n => f(f)(n)
  
  var fn = lfp(g)
  return fib(fn)
}
var run = wrap(wrap)
t(run)

// 12 move the fixed-point function outside its wrapper
var fib = f => n => n < 2 ? 1 : f(n - 2) + f(n - 1)
var lfp = f => n => f(f)(n)
var wrap = g => {
  var fn = lfp(g)
  return fib(fn)
}
var run = wrap(wrap)
t(run)

// 13 use a shorter version of wrap, we will use its lamdba form later
var fib = f => n => n < 2 ? 1 : f(n - 2) + f(n - 1)
var lfp = f => n => f(f)(n)
var wrap = g => fib( lfp(g) )
var run = wrap(wrap)
t(run)

// 14 rewrite `run` function so we only use `wrap` once
var fib = f => n => n < 2 ? 1 : f(n - 2) + f(n - 1)
var lfp = f => n => f(f)(n)
var wrap = g => fib( lfp(g) )
var run = (f => f(f))(wrap)
t(run)

// 15 realize `run` contains a eager evalution fixed-point function
// we can (not necessary but more compliant) rewrite it into a lazy evaluation variant
var fib = f => n => n < 2 ? 1 : f(n - 2) + f(n - 1)
var lfp = f => n => f(f)(n)
var wrap = g => fib( lfp(g) )
var run = lfp(wrap)
t(run)


// 16 merge `wrap` and `run` into a single function
var fib = f => n => n < 2 ? 1 : f(n - 2) + f(n - 1)
var lfp = f => n => f(f)(n)
var run = lfp( g => fib( lfp(g) ) )
t(run)

// 17 wrap the new `run` so we can pass in actual computation `fib`
var fib = f => n => n < 2 ? 1 : f(n - 2) + f(n - 1)
var lfp = f => n => f(f)(n)
var runner = f => lfp( g => f( lfp(g) ) )
var run = runner(fib)
t(run)

// END
// the runner is our fixed-point combinator!
var lfp = f => (...n) => f(f)(...n)
const fpc = f => lfp( g => f( lfp(g)) )