{{ message }}

Instantly share code, notes, and snippets.

# houtianze/on.y.combinator.md

Last active Nov 23, 2020
On Y Combinator

Hopefully this may speed your groking of the forking torturing Y Combinator a little bit.

Disclaimer: I don't assert what I say here is accurate, or even correct (I'm not authorative, obviously), but it's my understanding and I'm sharing in the hope that someone who also struggles on the Y Combinator may benefit a tad.

## Prerequisite Understandings

• In Lambda Caculus, everything is a Lambda Caculus (Anonymous function that takes one parameter). And the best thing is that, ... drump roll ..., it's Turing Complete. So theoretically, it can caculate anything a computer can.
• In this note, I use the term `function`, which (I think) means Lambda Caculus, to sound (at least to myself) more accustomed.

## What does Y Combinator do?

• Given a function `f` that:

• takes a function and returns another. (So it's a high-order function (at least order or 2?))
• has at least one `fixed point` function `g`: `g == f(g)`
• can be applied to the Y Combinator

Then the Y Combinator, when applied to function `f`, will find one of its `fixed point`: i.e. `let g = Y(f); then g == f(g)`

## How does Y Combinator gets a function's fixed point

• Refer to Wikipedia again for the proof. (Again, quite technical）

## What is Y Combinator useful for?

• (The only main usage I know of) It can implement recursive functions in Lambda Caculus, in which recursive function is not natively supported (Becasue Lambda Caculus is anonymous function, thus it can't directly call itself (no name given to be called)). Apply Y Combinator to a factory/generator/seeding function will give you the normally recursively-defined fucntion.

### Illustration

(Using pseudo Javascript syntax) Recursive function `rf`:

```rf = function(x) {
y = logicA()
ret = rf(y)
logicB(ret)
}```

Its factory:

```rff = function(f, x) {
return function(f) {
function(x) {
y = logicA()
ret = f(y)
logicB(ret)
}
}
}```

Then `rf` is equivalent to `Y(rff)`, but `Y(rff)` is not recursively written.

### Explanations and the trick

• `rff` is a "wannabe" no-recursive factory for recursive function `rf`, it will truely be the factory `rff` only when the `f` parameter passed in is the same as the function it returns: i.e. when `f == rff(f)`. So this parameter (function) `f` is its fixed point. `Y(rff)` will return such a fix point (function), and this fixed point is the equivalence of the recursive function `rf` (`rff` now generates the fixed point, which is the recursive function). Amazing right?

### How does Y Combinator magically transform this factory function `rff` to the recursive function `rf`?

(My explanation) It first creates 2 "normal" factory functions (let's name them to refer) `rfa` and `rfb`, then it puts `rfa` as the input parameter `f` of `rfb` and returns this new function (the recursive function `rf`'s equivalence) `rfc`. When `rfc` is called, it performs the logic and call the function `f`, which is just itself, recursion thus comes alive.