Disclaimer: I’m not a computer scientist or mathematician. This post is about what I’ve learnt so far about Lambda Calculus. Most of the resources I’ve come across seem to assume either prior knowledge of advanced maths notation or extensive practical experience of lambda functions in software engineering. I’ve tried to avoid this and explain things step by step, but have no doubt made assumptions and mistakes of my own. Corrections (or questions) are welcome. I’ll include a list of the resources I’ve used to piece this together in a later post.
What is Lambda Calculus?
Lambda Calculus is a system of notation for defining procedures. It’s very simple, but is ‘Turing Complete’ – that is, it could (theoretically) be used to express any computation that can be done by any computer anywhere, either now or in the future (but at pen-and-paper speed).
I’m interested in it because the structure of the LISP programming language used in SICP is almost entirely based on Lambda Calculus (and, therefore, is just as simple and just as powerful)… and because it’s an illustration of how complex things like enormous software programs or even human organisations are built out of primitive parts (more on this in a future post).
Some history please
History – about Alonzo Church and how the lambda symbol (λ) came to be involved in all this – here.
What does it look like?
A lambda calculus expression begins with a lambda (λ), followed by the name of any variables used in the expression, followed by its output. For example:
λx. x + 1
is a complete expression. It says:
“λ” -> this is the beginning of a lambda calculus expression (expression, process and procedure are special words in Lambda Calculus and I may be using them incorrectly here but for our purposes it’s probably okay)
λx -> the variable x is ‘bound’ in this expression (i.e. it will be in input for this procedure). Whenever we see “x” in the expression, we’ll replace it with the input of the same name (we’ve used x in this case, but it could be any symbol).
” . ” -> what follows next is the output of the expression.
To “run” this program, we just need to input a value, like this:
(λx. x + 1) 3
(Note that simple arithmetic operations – and even integers – like these aren’t actually allowed in formal Lambda Calculus, so addition is pretty complicated. For now, just imagine any arithmetic is an abstraction for the functions that encode numbers and arithmetic procedures. See Part 4 of this series for links to explanations of Church Numerals and addition.
And we evaluate the expression by substituting 3 for x wherever it appears, and throwing away the first lambda part:
(λx. x + 1) 3 -> 3 + 1 -> 4
At the simplest level, that’s more or less it. An expression that takes in two variables (or ‘arguments)’, in which case (this video says) the left most lambda expression takes the innermost argument first:
(λx.λy. x + 1 + 2y) 3 4 -> (λy. 3 + 1 + 2y) 4 -> 3 + 1 + (2×4) -> 4 + 8 -> 12
This can also be written as (λxy.x+1+2y) rather than having the repeated lambda symbols at the start.
Ambivalent about means
One of the main points about the lambda calculus is that it’s ambivalent or agnostic about means. Each procedure is like a little black box that does something, and most of the time we only really care about the output and not about how the procedure does it as long as it gives us what we want.
This is kind of true of how we all operate anyway: if I ask you to tell me the value of (2 x 5) I don’t really care if you look it up in a table in your head (or on paper), or do (5 + 5) or (2 + 2 + 2 + 2 + 2) or hold five one one hand and count on another five. One or the other method might be more efficient, but what I care about most of the time (and certainly for now) is the answer, not the method. We can worry about computational efficiency later.
This approach is called “black box abstraction” (it will feature in an upcoming extract from the SICP lectures) and it allows us to manage complexity by ignoring details like these so that we can focus on the bigger picture.
What makes Lambda Calculus interesting is that the input to a function can be another function.
(λx. x 2y)(λz. z * z) -> (λz. z * z) 2y -> 2y * 2y -> 2y2
Note that things don’t have to resolve to numbers – we could be left with a procedure.
I wrote a lengthy example of this involving a function for calculating the time needed to cook chicken that could be substituted for another function for cooking beef, but it got rather messy so I’ll save it for another time. Suffice to say that the ability of functions to operate on other functions (or themselves) – essentially to re-write themselves depending on their inputs – is what makes the Lambda Calculus (and computer programming languages) so powerful.
The identity function (“I am what I am.”)
The simplest example of a function processing another function starts with:
You can think of this as a function that takes x as its input (or argument) and outputs the very same thing. So:
(λx.x) 3 -> 3
(λx.x) z -> z
This seems unremarkable, but we can think of it as asking a question: “What is the input?” So this is valid:
(λx.x) “banana” -> “banana”
What is 3? It’s 3. What is z? It’s z. What is the “banana”? You get the idea. Each time in some sense this tells us the “identity” of the input.
But what is the identity… of the identity function? It goes like this:
(λx.x) (λx.x) -> λx.x
So the identity of the identity function is… itself. The identity of “identity” is (of course) “identity”. Nice.
We’ll look at how this simple notation can be used to operate Boolean logic (NOT / AND / OR etc) before finishing with a final post on recursive functions and the elusive Y Combinator.