A few years ago I attended a talk at a Lambda World Conference about Lambda Calculus. Although not an eye-opener (in fact that level of abstraction is rarely needed, nor advisable, in everyday programming), it was thought-provoking. By wisely crafting mathematical functions you could describe algorithms, fully equivalent to the good old recipe-like imperative programming code.
The point is that those lambda functions are really twisted.
Reading some anecdotes about Alonzo Church it is immediately clear he was quite a guy. And devising lambda calculus required quite a mind.
Since lambda calculus is just functions, no statement, it came to my mind I could use it to devise a solution to my “if-less” programming quiz.
The solution I prepared was too complex to be explained in my previous post, so I decided to write this post.
First I’d like to stress once more that this is not the way functional programming requires you to write code. As for imperative programming, you are not required to reason in terms of Turing’s machine.
There’s a notable difference, though – stemming from lambda calculus you can build directly, abstraction layer after abstraction layer, a usable language. The same does not apply to Turing’s machine which is a conceptual device that cannot be evolved into imperative statements.
As trigonometry is the mathematics that lets you deal with angles, lambda calculus is the mathematics that lets you deal with lambda terms. So now, what is a lambda term? As a first approximation, we can say that a lambda term is either a variable or a lambda function, i.e. a function that accepts a lambda term as an independent variable and produces a lambda term as a result of its evaluation.
You can notice the recursive definition of the concept possibly, as claimed by Douglas Hofstadter in his Godel, Escher, and Bach is the base for intelligent behavior.
Now that you have somewhat familiarized with lambda calculus, let’s get back to the if-less programming riddle solution.
I intended to employ C++ for the solution, but I found so many problems in getting it working that I resorted to Scala. By having a look at rosetta code, you can see that you can actually write lambda calculus expressions in many languages, so there’s nothing special in Scala (maybe there’s something special in C++…). If you are not familiar with Scala, do not worry, I’ll try to describe all the constructs I’ll use. In this case, Scala is just a suitable tool to present something else.
Let’s start from the blueprint of a lambda function –
trait Lambda {
def apply( x: Lambda ) : Lambda
}
For those not familiar with Scala:
traitis a pure virtual class, used to declare interfacesapplyis a special method that is invoked when an instance of Lambda is followed by parenthesis (i.e. it looks like a function call). You may think of this as a C++operator().
The easiest function is the identity function which can be written like this:
val identity: Lambda = x => x
(for those that need a translation from Scala, val is the prefix for a variable declaration: val variable : Type = …; x => x is a function that accepts a variable ‘x’ (on the left of =>) and returns it (on the right of =>)).
The first problem is …. hey, I read the lambda stuff definition a couple of times, but nobody’s talking about numbers? In fact, there are no numbers, but by invoking the power of conventions, I can find a convention that lets me encode numbers. Well, not me, good old Church took care of this and invented the Church numerals.
Church numerals are functions that applies a given number of times a function f to the variable x. Read this a couple of times to let it sink down and then observe the following table –
- 0 – does not apply function f:
val zero: Lambda = f => x => x. - 1 – applies function f just once:
val one: Lambda = f => x => f(x) - 2 – applies f twice:
val two: Lambda = f => x => f(f(x)) - … and so on
Computing the successor of a number n is a matter of finding a way to invoke f once more on n. It can be done like this
val succ : Lambda = (n) => (f) => x => f(n(f)(x))
n is the given number and we want to compute n+1 (this looks like another riddle 🙂 ). n(f) is a function composed of n nested invocations. n(f)(x) translates to applying f nested n times to x. Since we want one more application, we wrap n(f)(x) into a call to f: f(n(f)(x)).
So we now have a set of purposefully crafted functions that represent integers. Since we live in a world that has different conventions about numeric encoding we need a function to go from Int to Church numerals (of course, if we want to write other computations, we need also the reverse function, but this is not needed to find the minimum of two numbers).
The function can be written like this:
val zero: Lambda = f => x => x
def toChurch(n: Int ) : Lambda = {
if( n == 0 )
zero
else
succ(toChurch(n-1))
}
(translation from Scala – def introduces a function, such as in def functionName( arg: Type ) : ReturnType = function body)
The function is recursive – we know how zero is encoded, so, if the number is 0, then we return the constant we defined above. Otherwise, the encoding will be the successor of the recording of the number minus one. Soon or later, keeping decreasing the number I’ll reach zero and I’ll be done.
Next, I need a way to encode the if statement (in C++ it would be the ternary operator since we want a result from the if). The trick used is strongly base on the lambda encoding for true and false values:
val aTrue: Lambda = (x) => (y) => x val aFalse: Lambda = (x) => (y) => y
True takes two variables and returns the first, while false takes two variables and returns the second. At this point writing the if, is just a matter of getting parts in the right order:
val aIf : Lambda = c => (t) => (f) => c(t)(f)
The first argument is the condition (that can be either true or false), then we take the value to return if the condition is true and then the value for the else branch and eventually we leave the job to the condition that will return the first argument if true, or the second if false.
The missing brick is to code a function, let’s call it leq (as in less or equal), that compares two numbers and produces true if the first is less than (or equal to) the second and false otherwise.
This is the hardest part. I found several ways on the internet to perform the comparison, and resorted to the one that was less convoluted, nonetheless is way hard.
In order to compare two numbers, we can subtract one from the other and check the sign of the result. This is not exactly what we are going to do, but a direction for investigating.
If we can manage to write a predecessor, then we can implement the subtraction m–n, by applying the n times the predecessor function to m. This is easily done:
val sub : Lambda = (m) => (n) => n( pred )(m)
There’s only a minor hiccup in my reasoning – we can encode zero and positive numbers using the Church Numerals, but not negatives. So we can either decide whether to find a negative encoding for Church Numerals, and implement an isNegative function, or we can pick a predecessor function that yields 0 when trying to find a predecessor to 0. In this case, we would need an isZero function.
This latter approach seems somewhat simpler since no change in the number representation is needed. Also, isZero function is really straightforward since zero is encoded as the identity function, we can provide a function that always returns false regardless of the argument and a true as the argument:
val isZero : Lambda = (n) => n( (x) => aFalse )( aTrue )
If the number is non-zero, then f is called, the argument is ignored by f and false is returned, on the other hand, if the argument is zero, then the function is ignored and the argument (true) is returned.
Now we can write the comparison function:
val leq : Lambda = (m) => (n) => isZero( sub(m)(n) )
The only missing block to implement is the predecessor lambda… I left it for last since it is all but trivial (and, of course, I found it on the internet):
val pred : Lambda = (n) => (f) => (x) => n((g) => (h) => h(g(f)))((u) => x)((u) => u)
This is mindboggling, and it is pretty normal to stare at it wondering what is. Basically, this function needs to transform fn(x) (i.e. f applied n times to x) into fn-1(x). I guess, that the h(g(f)) part is the core that peels off one f, but if you want to dig deeper into the working of this expression, I’ll point you to this StackOverflow QA, which includes several good answers.
And this is enough to solve the riddle of finding the lesser of two integers without using the “if” statement. You may wonder if lambda calculus offers something similar to loops. In fact, it does, but it is a bit counterintuitive. You can actually implement recursion, which offers the building block for loops. But, since lambda functions are anonymous and therefore there is no way to reference them, how can this be done?
If you feel stuck it may be of relief, knowing that in the beginning, even Church considered that recursion couldn’t be implemented in lambda calculus. It was one of his students – Curry Haskell – the demonstrated that this was possible and the tool invented for this purpose is the Y-Combinator. I think that this post is already quite dense without the need of delving into this mechanism. If you are happy knowing that it exists, then you can stop here, if you want to investigate further, this blog post may provide an explanation more accessible than the Wikipedia page.