# 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

Ycombinator. Many have heard of it, but few have mastered its mysteries. Although fairly useless in real-world software, understanding how theYcombinator 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:

Examples:

## Higher-order functions

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

- Takes one or more functions as arguments.
- Returns another function as its result.

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))
)
)
```