Introduction

The Lambda Calculus, invented by Alonzo Church back in the 1930s, can be referred to as the smallest universal programming language. It’s Turing complete, meaning everything which is computable, can be computed in it.

It has only a few basic constructs, like – anonymous – functions and function application. These are the primitives. By adding Church Numerals, representation of Booleans, conditionals, lists and recursion with the help of combinators, we get a fully usable language.

Functional programming was born to Lambda Calculus. Functional programming is getting more and more attention nowadays, because it makes parallel programming so much easier.

Recursion

Recursion is amazing, since it enables us to compute and process self-similar structures in a natural way. It also helps to solve a more complex problem by breaking it down into similar, but simpler problems to be solved separately. Finally recursion can be thought of an alternative to iteration.

Side note. The conventional programming languages are equipped with looping-constructs like, while, for, etc. The interesting thing is that it turns out these are unnecessary, since the same can be accomplished by using functions and function-application. By adding Tail Call Optimisation (TCO for short) and having the underlying system translate them to primitive loops in the machine language, we can achieve the same performance as we were using the usual looping-constructs to express iteration.

To get recursion working, we need to have a “handle” on the function itself. But functions in Lambda Calculus are anonymous. (Meaning, we cannot really refer to them by their names.) So how can we make it work then? Well, we can bind expressions to function parameters. That’s all what’s offered by Lambda Calculus. But as you will see shortly, it’s sufficient to make it work. U and Y combinators to the rescue!

The U combinator is a higher-order function, that applies its parameter to its parameter. It provides a way to get a handle on the function through parameter binding, hence making recursion possible.

Side note. The smallest non-terminating program can be written using the U combinator like this: U(U)

The Y combinator is a bit more complicated compared to the U combinator, and it’s better-known too.

The funny thing is that today’s programming languages, which are functional, or multi-paradigm but supporting the functional paradigm as well, are capable of this kind of programming. That’s because they are descendants of the Lambda Calculus.

Next let’s see how to do recursion with anonymous functions in some mainstream programming languages. And, also in Scheme for those who are not afraid of this beautiful, minimalistic LISP dialect.

Code Examples

Side note. While in Lambda Calculus we bind the name (parameter of the function) to the expression to which the function is applied, they’re bound to the values of the expressions in the following examples, since they use applicative order evaluation. That’s why it’s better to call these combinators applicative order combinators.

function (f) { return f(f); }

(function (f) {
  return f(f);
}(function (h) {
  return function(n) {
    return n <= 1 ? 1 : n * h(h)(n - 1);
};
}))(5);

 -> f { f.call(f) }

-> f { f.call(f) }.call(
  lambda do |h|
    lambda do |n|
      n <= 1 ? 1 : n * h.call(h).call(n - 1)
    end
  end
).call(5)

(lambda (f) (f f))

(((lambda (f) (f f))
  (lambda (h)
    (lambda (n)
      (if (<= n 1)
        1
        (* n ((h h) (- n 1)))))))
  5)

References

1. Lambda Calculus
2. Anonymous function
3. Church Encoding, U combinator
4. Y Combinator