Lambda Calculus, Recursion and loop

Loop or iteration needs mutation of at least one variable in a loop body and of course, Lambda Calculus doesn't let you do it! It means iteration is impossible in functional languages but we can somehow simulate it with using recursion.

Infinite Loop
Let us define a term (abstraction) like the following:

T = λx.x x

What if we try to evaluate the application T T, let us see:

T T  →  (λx.x x) (λx.x x)  →  (x x) [x := λx.x x]  →  (λx.x x) (λx.x x)  →  T T

As you see, if we try to get the result of this application we get the application itself, in fact, it is kind of an infinite loop, T T is kind of self-applications which usually lead to recursion. This kind of infinite loop is shown by Ω symbol, so you may say that:



Ω = (λx.x x) (λx.x x) 

Finite Loop
OK, we saw that T T represents a recursion but it can be also interpreted as an infinite loop. As we have seen in programming since we have a logical comparison, we can easily define applications which do have some form of T T  but with some controlled counter as passed argument we can not let he recursion continues forever.

The typical simple recursive application is the calculation of n! let's name this function  f. Before writing the application, remember how we had an if statement in lambda calculus:

λpxy.p x y

Which means "if (p == 0) then x else y", now let us see how we can write a factorial abstraction:

f  =  λn.(λnxy.(n-1)  1  (n *  (f)  n-1)) 

It seems a bit complex, but it is not. First remember we assumed before that we use infix notation for mathematical expressions, so n-1 means - n 1.

f is an abstraction if you use it as an application it accepts one argument n and calculates the factorial of it. It first evaluates (n-1) and if finds it zero returns 1 otherwise calls f with n-1 and multiplies the result to n and returns it, sounds right, no? By (f)  n-1 we mean function application that accepts n-1 as its argument.

Now suppose we want to calculate 3! we have:

(λn.(λnxy.(n-1)  1  (n *  (f)  n-1))) 3 → 
3 *  (λn.(λnxy.(n-1)  1  (n *  (f)  n-1))) 2  → 
3 * 2 * (λn.(λnxy.(n-1)  1  (n *  (f)  n-1))) 1  → 
3 * 2 * 1  = 6