Lambda Calculus is a formal system in mathematical logic introduced by Alonzo Church in the 1930s.
It’s getting more and more attention these days thanks to the rise of the Functional Programming paradigm in a growing number of languages (Scala, ReasonML etc) and guess what? Functional Programming is all based on Lambda Calculus.
Did you know that JS was build with the goal of embedding the Scheme Programming Language into the Netscape Navigator web browser?
And guess what! Scheme is a Functional language! So JS still has some Functional Programming features that will help us a lot during our everyday work!
As written above, Lambda Calculus is a formal system for expressing computation, and it’s based on the concept of expressing and composing functions.
An expression may be a variable, an abstraction or a function application.
To be more clear, we can summarise these three concept the following way:
A variable is an expression that evaluates to a value:
its Lambda Calculus counterpart is:
An abstraction is an expression that evaluates to an anonymous function:
so, its counterpart is:
As you can see, the greek lambda (λ) represents the “function declaration”,
x is the first argument and everything after the
. is just the function body.
Let’s see another example:
In the example above we’re just returning the square of the variable
x, and it’s pretty straightforward!
Sooo easy! But what if we want to apply a variable to this function?
Let’s learn more about Function Application.
We’re talking about Function Application when we write an expression that applies a value to a function:
and so, in Lambda Calculus:
Let’s try to apply this concept of function application to the example above, where we’re returning the square of a given numeric variable:
Great! In this example,
So, what’s the difference between Abstraction and Application?
The following code represents an Abstraction, ’cause we’re just defining a function, without applying any kind o value to it:
And the following example is an Application, ’cause we’re applying
x to the
Why is it important to understand these three little concepts?
Because they’re the foundation of Lambda Calculus and every other expression is just an abstraction over these!
Functions in Lambda Calculus should have only one argument.
Let’s pretend we have to compute a simple sum of two integers… that seems impossible to do by passing just one argument!
Here comes the concept of Currying.
Just to be clear, the solution above would not work in Lambda Calculus because the
SUM function is receiving two arguments.
But what about this?
Instead of returning the sum of given
y arguments, we’re creating a
SUM function which takes
x and returns an anonymous function that takes
y as its only argument. That anonymous function will return the sum of
As you may have guessed, we just wrote the
SUM Abstraction, so let’s see its Application:
This technique is called Currying and has been introduced by the mathematician Haskell Curry.
So, how would we computate the sum of two integers in Lambda Calculus?
In Lambda Calculus, the function is the only primitive data type.
We can still introduce certain types writing down their expressions in pure Lambda Calculus! Let’s take Booleans as an example:
What’s going on here? We can think of Boolean logic as choosing whether a value is
So we’re declaring a function which takes
TRUE as its argument and returns a function that takes
FALSE as its argument. We then decide if the returning value should be
We’re now missing the condition which decides if a value is
We can summarise the
if/then/else structure the following way:
So this is just a basic example, but as you can see Lambda Calculus can be really modular and can allow us to build complex control structures in just a few lines!
Why Lambda Calculus Matters
We just scratched the surface of Lambda Calculus. Studying it will allow you to understand how to deal with everyday Functional Programming problems, and will also help you to approach them in a different way.
After 80 year, this mathematical notation is still powerful enough to deal with everyday’s challenges.
If you want to learn more about Lambda Calculus, I’d recommend this awesome video by Graham Hutton:
and if you want to train your Lambda Calculus knowledge and skills, I’d recommend you HackerRank, where you can find a lot of problems and get help from other developers.