Technospire
Posts
Lambda Calculus

Lambda Calculus

Jidneya Desale
May 24, 2024

Lambda Calculus

I'm sure that we are all familiar with the notion of functions in math. To quickly explain functions at the most basic level they are simply a mapping between the domain (inputs) and the range (outputs). Lambda calculus has functions at its core but the way they are represented is something that will be unfamiliar to most. Developed in the 1930s by Alonzo Church, it is called the world's smallest universal programming language, as any computable function can be expressed and evaluated using this system as we are able to pass functions into other functions. Let us now understand how this language is defined.

Basics of lambda calculus

Normal function in math is represented in the following format:

f(x) = y

In this function we take in an input of x, perform some operations on it, and return an output of y.

In Lambda calculus a function is defined using the lambda symbol(λ)

λx.x

While the notation is unfamiliar do not be scared of it. It simply means that we have defined a function here that is taking in an input of x, and then it returns an output of x in this case.

Let’s define some common terminology using BNF before investigating expressions further:

Now your first question might be how are we going to know the difference between functions, in normal function notation we can just use different letters to define functions e.g. f(x), g(x), but what is the difference between λx.x and λy.y. In reality there is no difference between λx.x and λy.y, both functions do the exact same thing, they output the input, and this λx.x = λy.y = λz.z. Thus now we can see that we don't really care what the input is named, but it also means that we have to write the function in full every time we want to use it.

Now let us see how to call functions. When call functions it is an application and looks like this

(λx.x) y = y

In this example we have our earlier function, except now we have a value ‘y’, and this value is being applied to the function. What we essentially have to do when we apply ‘y’ to our function is get rid of the function call (λx), and then replace every ‘x’ in the body of the function (the part of the function after the dot), with our input which in this case is ‘y’.

One last important point about the basics of lambda calculus before we see some more interesting examples. Specifically we will talk about an application of the form:

(λfx.fx)fx

This is equivalent to:

(λf.λx.fx)fx = fx

This makes simplification and understanding later concepts much easier for us.

Great now you know the basics of the concept and are prepared to dive into the more technical uses of the language:

Logic

We can define logic in lambda calculus, and we shall use the church encoding (simply representing data and logic in lambda calculus) here to define all of our operators. The base of logic are the TRUE and FALSE, so let us define them first:

TRUE: λx.λy.x

This takes in two inputs and returns the first one, e.g. λx. λy. TRUE FALSE = TRUE

FALSE: λx.λy.y

This takes in two inputs and returns the second one, e.g. λx. λy. TRUE FALSE = FALSE

The NOT operator simply takes in one input and reverses it (TRUE to FALSE and vice versa):

λa.a FALSE TRUE

E.g. (λa.a FALSE TRUE) (λx. λy.x) = λx. λy.x(FALSE TRUE) = FALSE

The AND operator will take in two inputs and return TRUE only if both are TRUE:

λa.λb. a b FALSE

E.g (λa.λb. a b FALSE) (λx.λy. x) (λx.λy. y) = (λx.λy. x) (λx.λy. y) FALSE = (λx.λy. y) , and the final output is equivalent to FALSE as per our above rules.

The OR operator will also take inputs but unlike AND it will return TRUE even if only input is TRUE

λa.λb. a TRUE b

E.g (λa.λb. a TRUE b) λx.λy.y λx.λy.x = (λx.λy.y) λx.λy.x TRUE = TRUE

Now you know how basic logical operators work in lambda calculus and you can probably create the other operators. This is useful, but for most people arithmetic in programming is seen to be a fundamental necessity so let us also explore that:

Arithmetic

In lambda calculus because the only thing we have at our disposal are functions we also need to define our numerals in terms of functions, and the way we do this is shown below (we have abbreviated λf.λx to λfx):

0: λfx.x

1: λfx.fx

2: λfx.f(fx)

3: λfx.f(f(fx))

There is a pattern in this system - a number ‘n’ is simply the function ‘f’ applied to some input n number of times.

To achieve addition using this new system of numerals we are going to use the logic behind the numbers and say that to add 2 and 3 we simply have to apply the function ‘f’ 2+3 = 5 times on the input:

M + N = λfxMN. (M f) (N f x)

The above statement is saying that we simply apply ‘fx’ to our number N, which results in the same expression but without the function part. Then we apply f and N to our other number M, so then the total number of times that the function f will be applied is M+N.

Multiplication, despite being repeated addition, does not need recursion. For M * N we apply the number of times the function is applied in N the number of times the function is applied in M. This just means that if M = 2 and N = 3, we apply the 3 function calls from N 2 times:

M * N = λf.M N f

This general statement is similar to addition except we don't apply ‘fx’, instead only ‘f’, so that we are left with a function that we can apply as the second input to our first number M along with the first input of the other number N.

Recursion

Another important aspect of any programming language is the ability to perform recursion and there is a way to achieve this in lambda calculus:

Take into consideration this lambda application

(λx.xx)(λx.xx) = (λx.xx)(λx.xx) = (λx.xx)(λx.xx) = …

We can see that evaluating this application just gives us the same thing over and over again, and thus we are close to our goal of recursion. To achieve this we use a function ‘f’ that takes in ‘xx’:

(λx.f(xx))(λx.f(xx)) = f((λx.f(xx))(λx.f(xx))) = (λx.f(xx))(λx.f(xx)) = (λx.f(xx))(λx.f(xx)) = …

Now we can see that an extra function is being applied every time we evaluate the application. Thus we have created recursion. This is called the Y combinator and is formally written like this:

Y = λf ((λx.f(xx))(λx.f(xx)))

So that we can define our ‘f’ function at the start.

Conclusion
I'm sure that you will have a lot of questions regarding lambda calculus and I suggest some further reading into this topic. Lambda calculus as a language is not supposed to be a practical language,rather it is supposed to be a tool for us to analyze how functions interact and it is the basis for most functional programming, most notably, Haskell. Thank you for reading, I hope that you have gained something valuable from this article.