Lambda Calculus in JavaScript — Part 1

This tutorial is for those who want to understand lambda calculus without having to use the original syntax.

It is based in JavaScript. You need to know Arrow Functions in JavaScript. You can try the examples in the browser console, or NodeJS REPL.

Lambda Calculus is a simple but powerful language based on pure abstraction.

It is made up of three types of expressions.

  1. Variables, that evaluate to a value
  2. Abstractions, that evaluate to an anonymous function
  3. Applications i.e. application of the anonymous functions.

This is not so hard to understand, if you consider abstractions to be functions, and applications to be function applications.

Examples of lambda expressions in JavaScript are:

x                      // A variable name
x => x // An anonymous function
(x => x)(5) // Function application. Number
// 5 applied to the function.

The equivalent of the above expressions in lambda calculus are:

x                      // A variable name
λx.x // A Lambda function
λx.x 5 // Function application. Number
// 5 applied to the function.

These are the three basic expressions in lambda calculus. Everything else is an abstraction over these.

The identity function

x => x 

The identity function returns the only argument applied to it as is. `x` is known as the bound variable. It is bound to the `x` in the body expression. In this case the body expression is also `x` itself.

We can apply a value to the identity function.

(x => x)(5)               // Evaluates to 5

We can apply the identity function to itself!

(x => x)(y => y)          // Evaluates to y => y

Notice that the variable name does not matter. x => x and y => y are the same function.

Self application function

s => s(s)

The self application function applies its argument to its argument. So its argument must itself be a function. Lets us apply the identity function to it.

(s => s(s))(x => x)

The above function evaluates

s(s)

Replace `s` with (x => x)

(x => x)(x => x)

As we saw earlier this reduces to the identity function.

x => x

Now apply the self application function to itself!

(s => s(s))(s => s(s))

Try this is in the node REPL or browser console. You will get

> (s => s(s))(s => s(s))
RangeError: Maximum call stack size exceeded
at s (repl:1:13)
at s (repl:1:18)
at s (repl:1:18)
at s (repl:1:18)
at s (repl:1:18)
at s (repl:1:18)
at s (repl:1:18)
at s (repl:1:18)
at s (repl:1:18)
at s (repl:1:18)
>

Oops what happened?

When the function body

s(s)

is evaluated, we get

(s => s(s))(s => s(s))

Which is the self adjusting function applied to itself again! i.e. what we started with! And this creates an infinite recursion.

Function application function

f => x => f(x)

The function application function, takes a function `f` as its argument and returns a nested function. The nested function takes a variable `x` as its argument, and applies the variable to the first function.

Now let us use the function application function, to apply the identity function, to the self application function.

(f => x => f(x))(x => x)(s => s(s))

The function being called is

f => x => f(x)

f is replaced by x => x.

x is replaced by s => s(s)

The expression reduces to

(x => x)(s => s(s))

The identity function just returns its argument. So the above reduces to

s => s(s)

Turns out what you learned so far is the core of lambda calculus. Everything else is an abstraction or syntactic sugar over the above.

Syntactic Sugar

Syntactic sugar is the addition of constructs to a language syntax, to make it more readable. If you noticed, our venture into lambda calculus was getting progressively complex.

To start with, let us give names to our lambda functions, so that our code henceforth, is easier to read.

const id = x => x
const selfApply = s => s(s)
const apply = f => x => f(x)

Important to note here that defining variables as above are not part of the core of lambda calculus.

Also functions take a single argument. For multiple arguments nested functions are used, as seen in the apply function.

Arguments selection functions

first => second => first

The function above will return the first of the two arguments given.

const selectFirst = first => second => first
selectFirst(2)(4) // returns 2

Similarly we can define selectSecond.

const selectSecond = first => second => second
selectSecond(2)(4) // returns 4

Notice that the nested function returned by selectSecond given the first argument is

second => second

Which is the identity function. We could just as well have written

const selectSecond = first => id

Making pairs from two arguments

Consider the function

first => second => func => func(first)(second)

It takes a bounded variable `first`. Returns a nested function that takes `second`. Which in turn returns a nested function that takes a function `func` as its argument. In the body `func` is called with `first`, and the returned function is called with `second`.

Let us call this function makePair.

const makePair = first => second => func => func(first)(second)

And the make a pair.

const pair = makePair(1)(2)

When we apply selectFirst to pair we should get 1.

pair(selectFirst)            // returns 1

When we apply selectSecond to pair we should get 2.

pair(selectSecond)           // returns 2

In the next tutorial, we will use what we learned so far, to add more features to our lambda calculus language. We will use the above functions to create boolean logic, integer arithmetic and list data structures.

For those who want to learn the “real thing”, this tutorial is based on the book An Introduction to Functional Programming through Lambda Calculus.