h LENGTH <~~> LENGTH
-Replacing `h` with its definition, we have
+Replacing `h` with its definition, we have:
(\xs. (empty? xs) 0 (succ (LENGTH (tail xs)))) <~~> LENGTH
have a function we can use to compute the length of an arbitrary list.
All we have to do is find a fixed point for `h`.
-The strategy we will present will turn out to be a general way of
+Let's reinforce this. The left-hand side has the form:
+
+ (\body. Φ[...body...]) LENGTH
+
+which beta-reduces to:
+
+ Φ[...LENGTH...]
+
+where that whole formula is convertible with the term `LENGTH` itself. In other words, the term `Φ[...LENGTH...]` contains (a term that convertible with) itself --- despite being only finitely long. (If it had to contain a term *syntactically identical to* itself, this could not be achieved.)
+
+The key to achieving all this is finding a fixed point for `h`. The strategy we will present will turn out to be a general way of
finding a fixed point for any lambda term.
+<a id=deriving-y></a>
## Deriving Y, a fixed point combinator ##
How shall we begin? Well, we need to find an argument to supply to
h h <~~> \xs. (empty? xs) 0 (succ (h (tail xs)))
-The problem is that in the subexpression `h (tail list)`, we've
+The problem is that in the subexpression `h (tail xs)`, we've
applied `h` to a list, but `h` expects as its first argument the
length function.
Shifting to `H` is the key creative step. Instead of applying `u` to a list, as happened
when we self-applied `h`, `H` applies its argument `u` first to *itself*: `u u`.
-After `u` gets an argument, the *result* is ready to apply to a list, so we've solved the problem noted above with `h (tail list)`.
+After `u` gets an argument, the *result* is ready to apply to a list, so we've solved the problem noted above with `h (tail xs)`.
We're not done yet, of course; we don't yet know what argument `u` to give
to `H` that will behave in the desired way.
## Fixed-point Combinators Are a Bit Intoxicating ##
-[[tatto|/images/y-combinator-fixed.jpg]]
+[[tatto|/images/y-combinator-fixed.png]]
There's a tendency for people to say "Y-combinator" to refer to fixed-point combinators generally. We'll probably fall into that usage ourselves. Speaking correctly, though, the Y-combinator is only one of many fixed-point combinators.
For those of you who like to watch ultra slow-mo movies of bullets
piercing apples, here's a stepwise computation of the application of a
recursive function. We'll use a function `sink`, which takes one
-argument. If the argument is boolean true (i.e., `\x y. x`), it
+argument. If the argument is boolean true (i.e., `\y n. y`), it
returns itself (a copy of `sink`); if the argument is boolean false
-(`\x y. y`), it returns `I`. That is, we want the following behavior:
+(`\y n. n`), it returns `I`. That is, we want the following behavior:
sink false <~~> I
sink true false <~~> I
sink true true false <~~> I
sink true true true false <~~> I
-Evidently, then, `sink true <~~> sink`. So we want `sink` to be the fixed point
+To get this behavior, we want `sink` to be the fixed point
of `\sink. \b. b sink I`. That is, `sink ≡ Y (\sb.bsI)`:
1. sink false