Lambda Calculus in JavaScript

Today I wanted to write about a really interesting topic that plays a huge role in modern computing. Understanding a bit about it will be a great help when it comes to grasping some advanced JavaScript concepts.

But let’s take it step by step.

What is lambda calculus?

It’s a formal system developed by Alonzo Church (Alan Turing’s advisor) in 1936. He was trying to formalize mathematics, but someone else realized that Church’s work fell into a paradox that prevented him from doing so.

So Church took part of his work and focused on researching the definition of functions, the application of those functions, and recursion.

This gave birth to what many recognize today as the smallest and most universal programming language. Any computable function can be evaluated and expressed using lambda calculus.

Lambda in programming languages

The fundamental requirement for implementing lambda calculus in a programming language is that functions must be treated as first-class citizens.

The first programming language to do this was Lisp, developed by [John McCarthy](http://John McCarthy), who created a theoretical proposal for implementing lambda calculus. But one of his students, seeing the potential, went ahead and built a compiler.

Lisp never achieved great commercial popularity, but it was used by people like Paul Graham, who used it to build his startup ViaWeb. In his book Hackers and Painters, he talks about the benefits of using a language like this for web application development.

After that, it was implemented in languages like Scheme, ML, Haskell, and the one we care about here: JavaScript (let’s thank Brendan Eich for pulling off that implementation in such a short time).

Why is lambda calculus still so valuable?

In a nutshell, basically because:

• Recursion is fundamental to computing.
• It’s a simple model for explaining properties of computation.

But enough history — let’s get into what really matters about lambda calculus.

Functions

First things first, we need to define what a function is. In its most basic form, it’s an association between input values and output values.

We pass in some input values, those values get processed, and we get some output values.

For example:

    function doble(x) {
      return 2 * x;
    }

    //La entrada es un número
    //Se procesa multiplicando por dos
    //La salida es el doble del número ingresado

Functions in lambda calculus

Church established some characteristics of functions, and they are:

The name of the functions doesn’t matter — only what they do matters.

If we have a sum function that takes two numbers and returns their sum:

suma(x,y) = x + y

It would be the same as having:

(x,y) = x + y

This way we can have anonymous functions in a programming language. Following the previous example, it would be the same as having:

const suma2 = x => x + 2;

The names of the input parameters don’t matter.

Using the previous example, a function that receives two numbers and adds them:

(x,y) = x + y

Those numbers could be called anything:

(a,b) = a + b

Thanks to this, when we create a function, the parameter names we define only matter within the function itself.

If a function receives more than one parameter, it can be rewritten as a function that takes one parameter and returns a function, which in turn receives a parameter and returns the result.

Using the previous example, where we receive two numbers and return their sum:

(x,y) = x + y

We could also express it as:

x -> (y -> x + y)

A function that receives x and _returns a function that receives y, returning the sum of both (this process is called currying).

Now, in code, this characteristic lets us do this:

const suma = x => y => x + y;

const suma10 = suma(10);
const suma20 = suma(20);

console.log(suma10(20));
console.log(suma20(20));

As I mentioned earlier, and as you can see in the example above, to use this in programming languages, functions must be first-class citizens, since this allows us to take functions as parameters or, in this case, return functions.

The implementation of lambda calculus is a very powerful concept because, with these characteristics, it allows us to use the functional programming paradigm in any language that implements it.

Understanding this will help us grasp concepts like scopes, closures, currying, function composition, pure functions, and even function factories on a much deeper level.

This is just a basic overview of lambda calculus. I encourage you to try to understand it in greater depth. In upcoming posts, we’ll see how it’s implemented in depth in JavaScript.