Notes on "Y Not"

My notes on the talk “Y Not – Adventures in Functional Programming”, given by Jim Weirich at Ruby Conf 2012:

One of the deepest mysteries in the functional programming world is the Y combinator. Many have heard of it, but few have mastered its mysteries. Although fairly useless in real-world software, understanding how the Y combinator works and why it is important gives the student an important insight into the nature of functional programming.

I’ve translated all examples to JavaScript, using the arrow syntax introduced with ES2015.

The problem

const fact = (n) => (n === 0 ? 1 : n * fact(n - 1))

fact(5)
// 120

In lambda calculus we cannot assign things like this. We have to create a lambda expression and call it directly:

(
  (n) => (n === 0 ? 1 : n * fact(n - 1))
)(5)
// Uncaught ReferenceError: fact is not defined

We are using fact in the definition of the function we’re defining. In lambda calculus all functions are anonymous, so how can we define fact without referring to itself?

Fixpoints

A fixpoint is any value that, when given to a function, returns the same value:

$$ x = f(x) $$

Examples:

$$ \begin{aligned} 0 & = \sin 0 \\ 0 & = \sqrt 0 \\ 1 & = \sqrt 1 \end{aligned} $$

Higher-order functions

A higher-order function is a function that does at least one of the following:

Examples of higher-order functions:

const makeAdder = (x) => (
  (n) => (n + x)
)

const compose = (f, g) => (
  (n) => f(g(n))
)

const add3 = compose(makeAdder(1), makeAdder(2))

add3(7)
// 10

Functional refactorings

Tennent’s correspondence principle

If we have an expression x and we surround it by a lambda, and then immediately call that lambda, we get x back:

add3(7)
// 10

add3((() => (7))())
// 10

Introduce binding

If we have a lambda, we can add a new argument binding to it, and it will have no effect:

add3((() => (7))())
// 10

add3(((n) => (7))(123456))
// 10

Wrap function

If we have an expression that is a function of one argument, we can wrap that in a lambda of one argument, and then call the function inside that lambda and pass the argument down to the call site:

add3(((n) => (n + 1))(6))
// 10

add3(((v) => ((n) => (n + 1))(v))(6))
// 10

Inline definition

We can take any definition of a function, and replace invocations of that function with its definition:

add3(7)
// 10

compose(makeAdder(1), makeAdder(2))(7)
// 10

Back to the problem

We want to write a factorial function that’s recursive, but we can’t because we can’t refer to fact inside the definition of fact, as these functions have no name:

(
  (n) => (n === 0 ? 1 : n * fact(n - 1))
)(5)
// Uncaught ReferenceError: fact is not defined

Arguments do have a name though, so we could wrap that in a lambda:

const makeFact = (fact) => (
  (n) => (n === 0 ? 1 : n * fact(n - 1))
)

const fact = makeFact(/* ??? */)

That won’t work, as we still need to pass the definition of the factorial function.

Instead of having a makeFact function that takes the definition of the factorial function, let’s have a factImprover function that takes a partial definition of factorial, i.e. a function that acts like factorial over a subset of the possible inputs. Our factImprover will improve any factorial definition by one step, so if we pass it a factorial definition that works from 0 to 10, it will return a new definition that works from 0 to 11.

Let’s start with 0:

const error = () => {
  throw new Error("SHOULD NEVER BE CALLED")
}

const factImprover = (partial) => (
  (n) => (n === 0 ? 1 : n * partial(n - 1))
)

const f0 = factImprover(error)

f0(0)
// 1

f0(1)
// Uncaught Error: SHOULD NEVER BE CALLED

If we can calculate the factorial of 0, we can calculate the factorial of 1:

const f0 = factImprover(error)
const f1 = factImprover(f0)

f1(1)
// 1

f1(2)
// Uncaught Error: SHOULD NEVER BE CALLED

And if we can calculate the factorial of 1, we can calculate the factorial of 2:

const f0 = factImprover(error)
const f1 = factImprover(f0)
const f2 = factImprover(f1)

f2(2)
// 2

f2(3)
// Uncaught Error: SHOULD NEVER BE CALLED

Ok, let’s inline some of these things, and rename f2 to fx:

const fx = factImprover(factImprover(factImprover(error)))

fx(2)
// 2

fx(3)
// Uncaught Error: SHOULD NEVER BE CALLED

If we keep nesting calls maybe we’ll get somewhere?

const fx = factImprover(factImprover(factImprover(factImprover(factImprover(factImprover(error))))))

fx(5)
// 120

fx(6)
// Uncaught Error: SHOULD NEVER BE CALLED

That won’t get us the real factorial function though.

Let’s wrap our improver in a lambda again, to avoid the assignment:

const error = () => {
  throw new Error("SHOULD NEVER BE CALLED")
}

const fx = (
  (improver) => improver(improver(error))
)(
  (partial) => (
    (n) => (n === 0 ? 1 : n * partial(n - 1))
  )
)

fx(1)
// 1

fx(2)
// Uncaught Error: SHOULD NEVER BE CALLED

If we get rid of that error function, we should get a function that works for the factorial of 0:

const fx = (
  (improver) => improver(improver)
)(
  (partial) => (
    (n) => (n === 0 ? 1 : n * partial(n - 1))
  )
)

fx(0)
// 1

fx(1)
// NaN

The problem is in that n * partial(n - 1) operation, as partial is an improver, and improver expects a function, not a number. We may see it clearer by renaming partial to improver:

const fx = (
  (improver) => improver(improver)
)(
  (improver) => (
    (n) => (n === 0 ? 1 : n * improver(n - 1))
  )
)

If improver expects a function, we’ve got one for it:

const fx = (
  (improver) => improver(improver)
)(
  (improver) => (
    (n) => (n === 0 ? 1 : n * improver(improver)(n - 1))
  )
)

fx(1)
// 1

fx(2)
// 2

fx(5)
// 120

If we get rid of the assignment, we’ll have a pure lambda expression that calculates a factorial:

(
  (improver) => improver(improver)
)(
  (improver) => (
    (n) => (n === 0 ? 1 : n * improver(improver)(n - 1))
  )
)(5)
// 120

Let’s rename improver, as it’s no longer taking a partial definition. We’ll call it gen, as it’s some kind of generator that produces a recursive function when it swallows itself:

(
  (gen) => gen(gen)
)(
  (gen) => (
    (n) => (n === 0 ? 1 : n * gen(gen)(n - 1))
  )
)(5)
// 120

The improver approach was easier to reason about, so let’s try to get back to it. We’re going to take the inner lambda, and apply Tennent’s correspondence principle to it:

(
  (gen) => gen(gen)
)(
  (gen) => (
    (() => (
      (n) => (n === 0 ? 1 : n * gen(gen)(n - 1))
    ))()
  )
)(5)
// 120

Now let’s introduce a new binding, code:

const error = () => {
  throw new Error("SHOULD NEVER BE CALLED")
}

(
  (gen) => gen(gen)
)(
  (gen) => (
    ((code) => (
      (n) => (n === 0 ? 1 : n * gen(gen)(n - 1))
    ))(error)
  )
)(5)
// 120

Instead of error, let’s pass gen:

(
  (gen) => gen(gen)
)(
  (gen) => (
    ((code) => (
      (n) => (n === 0 ? 1 : n * gen(gen)(n - 1))
    ))(gen)
  )
)(5)
// 120

What if we pass gen(gen)?

(
  (gen) => gen(gen)
)(
  (gen) => (
    ((code) => (
      (n) => (n === 0 ? 1 : n * gen(gen)(n - 1))
    ))(gen(gen))
  )
)(5)
// Uncaught RangeError: Maximum call stack size exceeded

Before, we were only calling gen(gen) when n !== 0, so we had no issues. Now we’re calling gen(gen) even when n === 0, so it’s recursing infinitely.

Well, we can delay evaluation by wrapping thing in a function:

(
  (gen) => gen(gen)
)(
  (gen) => (
    ((code) => (
      (n) => (n === 0 ? 1 : n * gen(gen)(n - 1))
    ))((v) => gen(gen)(v))
  )
)(5)
// 120

If we apply the same refactoring to the inner lambda:

(
  (gen) => gen(gen)
)(
  (gen) => (
    ((code) => (
      (n) => (n === 0 ? 1 : n * ((v) => gen(gen)(v))(n - 1))
    ))((v) => gen(gen)(v))
  )
)(5)
// 120

Then we can replace that thing with code:

(
  (gen) => gen(gen)
)(
  (gen) => (
    ((code) => (
      (n) => (n === 0 ? 1 : n * code(n - 1))
    ))((v) => gen(gen)(v))
  )
)(5)
// 120

Let’s rename code to partial:

(
  (gen) => gen(gen)
)(
  (gen) => (
    ((partial) => (
      (n) => (n === 0 ? 1 : n * partial(n - 1))
    ))((v) => gen(gen)(v))
  )
)(5)
// 120

Hey, we’ve got our improver function back! But it’s buried under a ton of stuff, so let’s try to pull it out. We’ll start by applying Tennent’s correspondence principle to the entire body of the function:

(() => (
  (
    (gen) => gen(gen)
  )(
    (gen) => (
      ((partial) => (
        (n) => (n === 0 ? 1 : n * partial(n - 1))
      ))((v) => gen(gen)(v))
    )
  )
))()(5)
// 120

Let’s introduce a new binding, code, like last time:

const error = () => {
  throw new Error("SHOULD NEVER BE CALLED")
}

((code) => (
  (
    (gen) => gen(gen)
  )(
    (gen) => (
      ((partial) => (
        (n) => (n === 0 ? 1 : n * partial(n - 1))
      ))((v) => gen(gen)(v))
    )
  )
))(error)(5)
// 120

If instead of error we pass our improver function, we can pull it out:

((code) => (
  (
    (gen) => gen(gen)
  )(
    (gen) => (
      code((v) => gen(gen)(v))
    )
  )
))(
  (partial) => (
    (n) => (n === 0 ? 1 : n * partial(n - 1))
  )
)(5)
// 120

Now let’s rename code to be improver:

((improver) => (
  (
    (gen) => gen(gen)
  )(
    (gen) => (
      improver((v) => gen(gen)(v))
    )
  )
))(
  (partial) => (
    (n) => (n === 0 ? 1 : n * partial(n - 1))
  )
)(5)
// 120

Now that we’ve got a complete lambda expression, let’s pull the pieces out and name them, so that we can reason about them:

const factImprover = (partial) => (
  (n) => (n === 0 ? 1 : n * partial(n - 1))
)

const y = (improver) => (
  ((gen) => gen(gen))(
    (gen) => improver((v) => gen(gen)(v))
  )
)

const fact = y(factImprover)

fact(5)
// 120

If we try to improve fact, we’ll get the same function:

const fact = y(factImprover)
const improvedFact = factImprover(fact)

improvedFact(5)
// 120

So fact is the fixpoint of factImprover. Higher-order functions have fixpoints as well.

The function y calculates the fixpoint of an improver function. It is the famous Y combinator! Mathematicians don’t like intention-revealing names, so you may see it in this form:

const y = (f) => (
  ((x) => x(x))(
    (x) => f((v) => x(x)(v))
  )
)

This, in particular, is the applicative-order Y combinator, also known as Z combinator. JavaScript is an applicative language. In other words, it evaluates its arguments before it passes the arguments down into functions.

An example of a language that’s not applicative would be Haskell. Haskell is lazy, it will evaluate its arguments only at the point it really needs them. The normal-order Y combinator just removes the wrapping lambda we introduced to delay execution.

You may see the Y combinator expressed slightly differently. If we call our improver function f with x(x), that’ll be a no-op:

const y = (f) => (
  ((x) => f(x(x)))(
    (x) => f((v) => x(x)(v))
  )
)

If we now wrap that thing in a lambda, we’ll get a nice simmetry:

const y = (f) => (
  ((x) => f((v) => x(x)(v)))(
    (x) => f((v) => x(x)(v))
  )
)

Related readings