Chapter 5: Fixed Points and Recursion

Fixed Points

In regular mathematics, a fixed point $x_0$ of a function $f$ is a point that maps back to itself, i.e.

$$f(x_0)=x_0$$

In regular mathematics, not all functions have a fixed point. But in lambda calculus, everything is a function and has a fixed point.

Fixed-point Combinators

How to solve fixed points of a function? It may surprise you that there is a kind of functions called fixed-point combinators capable to generate fixed points from arbitrary function by applying it with the function. I will introduce two of them.

$$\begin{array}{} \text{Curry's Paradoxical Combinator:}&Y&=&\lambda f.(\lambda x.f(xx))(\lambda x.f(xx))\\ \text{Turing Combinator:}&\Theta&=&(\lambda xy.y(xxy))(\lambda xy.y(xxy)) \end{array}$$

For arbitrary function $F$, it has two fixed points $(YF)$ and $(\Theta F)$, i. e. $F(YF)=YF$ and $F(\Theta F)=\Theta F$.

Proof:

$$\begin{array}{} YF&=&(\lambda f.(\lambda x.f(xx))(\lambda x.f(xx)))F\\ &=&(\lambda x.F(xx))(\lambda x.F(xx))\\ &=&F((\lambda x.F(xx))(\lambda x.F(xx)))\\ &=&F(YF) \end{array}\\ \begin{array}{} \Theta F&=&(\lambda xy.y(xxy))(\lambda xy.y(xxy))F\\ &=&F((\lambda xy.y(xxy))(\lambda xy.y(xxy))F)\\ &=&F(\Theta F) \end{array}$$

Infinity

What if I apply fixed-point combinator with succussor function $S$?

$$YS=S(YS)=S(S(YS))=\cdots=S(S(S(\cdots)))=\infty$$

Let's call it infinity. And it still meet requirement of a fixed point, since

$$S(\infty)=\infty$$

is reasonable and acceptable.

Recursion

To implement certain algorithms, recursion is often needed. Let's take $\text{factorial}$ for example:

$$\text{factorial}=\lambda n.(\text{is-zero }n)1(\text{mul }n(\text{factorial}(\text{pred }n)))$$

Since functions are anonymous, the name of the function is not assigned until the full definition of the function, So $\text{factorial}$ is actually used before its full definition, which is a hideous logical defect! Don't panic, let's take advantages of fixed points!

Take an inverse $\beta$ reduction on the right:

$$\text{factorial}=(\lambda f.\lambda n.(\text{is-zero }n)1(\text{mul }n(f(\text{pred }n))))\text{factorial}$$

Observe this carefully. It states that $\text{factorial}$ is a fixed point of

$$(\lambda f.\lambda n.(\text{is-zero }n)1(\text{mul }n(f(\text{pred }n))))$$

Which means, the definition of $\text{factorial}$ could be rewritten as:

$$\text{factorial}=\Theta(\lambda f.\lambda n.(\text{is-zero }n)1(\text{mul }n(f(\text{pred }n))))$$

Perhaps you did never associate fixed points and recursion together before this fantastic journey. Mathematical consequence may be far beyond our imagination.

Division, Remainder and Logarithm

With the help of recursion, the decrement of church numerals speeds up.

$$\text{div}=\Theta(\lambda f.\lambda mn.(\text{lt }mn)0(\text{add }1(f(\text{sub }mn)n)))\\ \text{rem}=\Theta(\lambda f.\lambda mn.(\text{lt }mn)m(f(\text{sub }mn)n))\\ \text{log}=\Theta(\lambda f.\lambda mn.(\text{lt }mn)0(\text{add }1(f(\text{div }mn)n)))$$

Recursive Algorithms and Data Structures

Recursive algorithms work well with recursive data structures such as linked list. A typical reduction function could be defined as:

$$\text{reduce}=\Theta(\lambda f.\lambda lr.(\text{is-nil }(\text{pop-front }l))(\text{get-front }l)(r(\text{get-front }l)(f(\text{pop-front }l)r)))$$

With $l=(1,3,5)$, you could get:

$$\text{reduce }l\text{add}=9\\ \text{reduce }l\text{mul}=15$$

With the powerful weapon of recursion, now it is not difficult to implement arbitrary computational task via lambda calculus.