process

Deriving Y Combinator

Deriving Y Combinator that makes recursive functions without assignments possible.

This is how one can start with factorial function and avoid using assignment operator by deriving and using Y Combinator function. This is based on the excellent and mind bending presentation by Jim Weirich at ScotlandJS. I highly recommend watching the video. This blog post only summarizes the code snippets I was writing as I was following along.

I am skipping the prerequisites and start at the recursive factorial problem, approximately at minute 26 of the video.

Let us start with recursive factorial and compute factorial of 5 to make sure it works.

1
2
3
const fact = n => n === 0 ? 1 : n * fact(n - 1)
console.log(fact(5))
// should be 120

Let us just print the returned value

1
2
3
4
5
console.log((() => {
  const fact = n => n === 0 ? 1 : n * fact(n - 1)
  return fact(5)
})())
// should be 120

Great. But why do we need the intermediate assignment const fact = ... inside? All it does is wait for fact(5) call, which we can do right away, right?

1
2
3
console.log((() =>
  (n => n === 0 ? 1 : n * fact(n - 1))(5)
)())

Oops, this does not work because the recursive call is using fact which is no longer defined

1
2
3
4
5
console.log((() =>
  (n => n === 0 ? 1 : n * fact(n - 1))(5)
  //                      ^^^^
  //                   no longer exists!
)())

So we need to somehow make a recursive call to itself inside the unnamed function. Hmm. That is the crux of the matter: can we write recursive functions without named functions (using just function expressions) and without assignment operator? Everything should be just an expression: a function applied to its arguments.

First attempt: let us deal with small values of n. In fact, let us deal with the simplest case - a factorial of 0. In that case, the recursive call would never happen we can literally pass anything just to make sure variable fact is defined (but it will never be used).

1
2
3
4
5
6
7
8
console.log((() => {
  function step(fact) {
    return n => n === 0 ? 1 : n * fact(n - 1)
  }
  const factorial = step('foo')
  return factorial(0)
})())
// should be 1

See how we pass string foo as fact, but it was never used and so everything was ok?

Whatever the value we passed as argument fact to function step better know how to compute factorial of n - 1 whenever we are computing the factorial of n. Let us say we want factorial of 1. What function should we pass to step that knows how to compute factorial of 0? Hint: we just saw it above - it is factorial(0), aka step('foo')!!! Just pass it to itself, and we then call the returned result function to compute factorial of 1.

1
2
3
4
5
6
7
8
console.log((() => {
  function step(fact) {
    return n => n === 0 ? 1 : n * fact(n - 1)
  }
  const factorial = step(step('foo'))
  return factorial(1)
})())
// should be 1

And if we want to compute factorial of 5 (or 4 or 3 or 2) we should keep nesting step(step(... calls.

1
2
3
4
5
6
7
8
console.log((() => {
  function step(fact) {
    return n => n === 0 ? 1 : n * fact(n - 1)
  }
  const factorial = step(step(step(step(step(step('foo'))))))
  return factorial(5)
})())
// should be 120

Note the above code does NOT need assignment operator (and const factorial = is only there for clarity). We might as well write the expression

1
2
3
4
5
6
7
console.log((() => {
  function step(fact) {
    return n => n === 0 ? 1 : n * fact(n - 1)
  }
  return step(step(step(step(step(step('foo'))))))(5)
})())
// should be 120

Ok, this is nice, but does not really scale to larger numbers. We somehow need to avoid manually creating this nested call chain and instead create it on demand.

Observation: if the very first argument to nested step(step(... calls does NOT matter (and we even have used foo string instead of the function), we can just pass step itself as first value

1
2
3
4
5
6
7
console.log((() => {
  function step(fact) {
    return n => n === 0 ? 1 : n * fact(n - 1)
  }
  return step(step(step(step(step(step(step))))))(5)
})())
// should be 120

We can also move the nested series of calls step(step(... from the end and pass it as argument to step(fact).

1
2
3
4
5
6
7
8
console.log((() => {
  return function (s) {
    return s(s(s(s(s(s(s))))))
  }(function step(fact) {
    return n => n === 0 ? 1 : n * fact(n - 1)
  })(5)
})())
// should be 120

Interesting. We are passing function step(fact){...} as argument s to this weird function, which in turn just calls it multiple times! The result of calling it multiple times goes back into step(fact) as fact argument. Kind of a "I will call you, you will call me" circle.

Hmm, so many nested s(s(s(s(... calls! All we need really is to call s(s) in order to teach the algorithm how to recursively call itself. Let us remove almost all calls, except for one s(s).

1
2
3
4
5
6
7
8
console.log((() => {
  return function (s) {
    return s(s)
  }(function step(fact) {
    return n => n === 0 ? 1 : n * fact(n - 1)
  })(5)
})())
// should be NaN

Hmm, we are missing something - and that something is the fact that fact(n) no longer is so simple. Instead it needs to call itself again in order to call s(s) again, which will call step(fact), and so on, until the recursion stops at n === 0 check. The only difference on the code below from the code above is the recursive call: fact was replaced with fact(fact) expression.

1
2
3
4
5
6
7
8
console.log((() => {
  return function (s) {
    return s(s)
  }(function step(fact) {
    return n => n === 0 ? 1 : n * fact(fact)(n - 1)
  })(5)
})())
// should be 120

Now we have a recursive expression without using assignment operator which can compute factorial of any number. We can refactor the above code for clarity because we want to be able to write recursive functions easily.

Start with renaming s and fact arguments gen because it is the same.

1
2
3
4
5
6
7
8
console.log((() => {
  return function (gen) {
    return gen(gen)
  }(function step(gen) {
    return n => n === 0 ? 1 : n * gen(gen)(n - 1)
  })(5)
})())
// should be 120

I don't like calling gen(gen) inside the "simple" factorial function step, so we should try getting rid of it. We can start by moving the n argument up into its own wrapper function

1
2
3
4
5
6
7
8
9
10
11
12
console.log((() => {
  return function (gen) {
    return gen(gen)
  }(function step(gen) {
    return function (n) {
      return function () {
        return n === 0 ? 1 : n * gen(gen)(n - 1)
      }()
    }
  })(5)
})())
// should be 120

Ok, still works. Now let us create another function around the simple factorial without any arguments for a moment.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
console.log((() => {
  return function (gen) {
    return gen(gen)
  }(function step(gen) {
    return function (n) {
      return function () {
        return function () {
          return n === 0 ? 1 : n * gen(gen)(n - 1)
        }()
      }()
    }
  })(5)
})())
// should be 120

And now let us supply arguments to these two inner functions. The outer one - we can pass gen(gen), which is what we wanted to do anyway.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
console.log((() => {
  return function (gen) {
    return gen(gen)
  }(function step(gen) {
    return function (n) {
      return function (code) {
        return function () {
          return n === 0 ? 1 : n * code(n - 1)
        }()
      }(gen(gen))
    }
  })(5)
})())
// should be 120

And for the inner function, the simple factorial, we can do the same, but for clarity I will rename the argument from n (which stays outside) to k.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
console.log((() => {
  return function (gen) {
    return gen(gen)
  }(function step(gen) {
    return function (n) {
      return function (code) {
        return function (k) {
          return k === 0 ? 1 : k * code(k - 1)
        }(n)
      }(gen(gen))
    }
  })(5)
})())
// should be 120

The inner part looks like a curried function with two applications though, so we can refactor from this

1
2
3
4
5
6
7
function (n) {
  return function (code) {
    return function (k) {
      return k === 0 ? 1 : k * code(k - 1)
    }(n)
  }(gen(gen))
}

to this

1
2
3
4
5
6
7
function (n) {
  return function (code) {
    return function (k) {
      return k === 0 ? 1 : k * code(k - 1)
    }
  }(gen(gen))(n)
}

But even better would be to extract this anonymous function cleanly, because this is the essence of recursive factorial algorithm; all the other code around it is just our extra machinery to avoid using the assignment operator. Literally, rip the above factorial and pass it as an argument! I will call the argument "algo" to make it clear.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
console.log((() => {
  return function (algo) {
    return function (gen) {
      return gen(gen)
    }(function step(gen) {
      return function (n) {
        return algo(gen(gen))(n)
      }
    })
  }(
    // recursive factorial
    function (code) {
      return function (k) {
        return k === 0 ? 1 : k * code(k - 1)
      }
    }
  )(5)
})())
// should be 120

The code might be a little better written if we separate calling it and printing the result.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
const F = function (algo) {
  return function (gen) {
    return gen(gen)
  }(function step(gen) {
    return function (n) {
      return algo(gen(gen))(n)
    }
  })
}(
  // recursive factorial
  function (code) {
    return function (k) {
      return k === 0 ? 1 : k * code(k - 1)
    }
  }
)
console.log(F(5))
// should be 120

Finally, separating the of the algorithm code, we can write generic "Y combinator" function that can make any function recursive without using assignment operator

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// Y combinator function
function Y(algo) {
  return function (gen) {
    return gen(gen)
  }(function step(gen) {
    return function (n) {
      return algo(gen(gen))(n)
    }
  })
}
// a particular function - note how it does NOT call itself, yet it will
// become recursive thanks to Y combinator
function factorial(partial) {
  return function (k) {
    return k === 0 ? 1 : k * partial(k - 1)
  }
}
// Magic: plain function + Y combinator => recursive factorial function
const F = Y(factorial)
console.log(F(5))
// should be 120

Interesting observation: the function factorial is very forgiving to what partial can be. For example, you can pass the computed Y(factorial) back to factorial and get the same result!

1
2
console.log('factorial(Y(factorial))(5) =', factorial(Y(factorial))(5))
// should be 120

This is because all factorial expects from partial is the ability to correctly compute factorials of smaller values.

Also, interesting to note that the computed value F = Y(factorial) can be passed back to factorial(F) and we get it back again: factorial(Y(factorial)) = Y(factorial). In math, this special value is called the fixed point of a function: f(x) = x. In our case f is function factorial and x is Y(factorial). So the Y combinator computes the fixed point of a given function!

Links

A few alternative derivations in JavaScript