We use cookies and other tracking technologies to improve your browsing experience on our site, analyze site traffic, and understand where our audience is coming from. To find out more, please read our privacy policy.

By choosing 'I Accept', you consent to our use of cookies and other tracking technologies.

We use cookies and other tracking technologies to improve your browsing experience on our site, analyze site traffic, and understand where our audience is coming from. To find out more, please read our privacy policy.

By choosing 'I Accept', you consent to our use of cookies and other tracking technologies. Less

We use cookies and other tracking technologies... More

Login or register
to apply for this job!

Login or register to start contributing with an article!

Login or register
to see more jobs from this company!

Login or register
to boost this post!

Show some love to the author of this blog by giving their post some rocket fuel 馃殌.

Login or register to search for your ideal job!

Login or register to start working on this issue!

Engineers who find a new job through Functional Works average a 15% increase in salary 馃殌

Blog hero image

Simple Yet Powerful: Lambda Calculus

Marty Stumpf 30 October, 2018 (3 min read)

I've long since heard of "Lambda Calculus" but I didn't really know what it is about until I saw this video. It got me super excited! What I love about it is that it's built on almost nothing! Only the concept of functions. It's so simple and elegant! Professor Graham Hutton also listed good reasons to learn it:

-Lambda calculus can encode any computation, and any programming language can be encoded in lambda calculus. (I will explain what "encoding" is below.) -It is the basis for functional programming languages, including Haskell and OCaml. -Most major programming languages include it as a major component.

Since it's so simple yet powerful, I must learn it to be a better programmer!

Functions and the Lambda (位) Notation

Lambda Calculus builds on the concept of functions. A function takes in input(s), processes the input(s) and returns an output. E.g., a function can take an input x, and output x+1. Or, a function can take inputs x and y, and output x+y. In lambda calculus, we write these functions as

位x.x+1

位x.位y.x+y

An input is followed by a 位, a dot separates each input, and the last dot is followed by the output of the function. We evaluate a function in the usual manner. In terms of notation, we write the value(s) of the input(s) after we define the function. E.g., when x = 5 in the first function above, we write:

(位x.x+1) 5 = 5 + 1 = 6

Or, when x = 5 and y = 7 in the second function, we write:

(位x.位y.x+y) 5 7 = 5 + 7 = 12

Encoding a Function

Of course, we can name a function. Doing so let us encode functions and operators. We name/encode TRUE as the function that returns the first input of a function that takes two inputs:

TRUE = 位x.位y.x

And FALSE is the function that returns the second input of a function that takes two inputs:

FALSE = 位x.位y.y

Using the functions TRUE and FALSE, we can encode the logical operator NOT, which takes a boolean (i.e., TRUE or FALSE) and returns the opposite:

NOT = 位b.b FALSE TRUE

We read the notation above as: the NOT function takes a b (stands for boolean) as an input, and the output is applying b to the inputs FALSE TRUE.

We can verify that NOT does what it's supposed to do by evaluating the result of NOT when it's given FALSE as the input:

NOT FALSE

= (位b. b FALSE TRUE) FALSE (substitute in the definition of NOT)

= FALSE FALSE TRUE (FALSE is the input to NOT, so it's to be applied to FALSE TRUE)

= TRUE (Applying the function FALSE means returning the second input, i.e., TRUE)

NOT FALSE returns TRUE, as we expected. (See the video for the evaluation of NOT TRUE)

The AND Operator

Professor Hutton gave us the exercise of constructing the AND and OR operators. Here is my attempt:

AND = 位b1.位b2.b1 b2 FALSE

AND takes two boolean inputs, then applied the first input (which is a function of either TRUE or FALSE) to the second input and FALSE.

How did I get this? I know that AND takes in two booleans, so the first part (位b1.位b2) is easy. The AND operator needs to return a boolean (TRUE only when both inputs are TRUE, otherwise, FALSE). So I know that it should take FALSE as an input, because I want it to be able to return FALSE even when there is some TRUE. Also, I know I have to consider both inputs so one of the input has to be applied to the function. So, I applied b1 (i.e., either the function TRUE or FALSE) to the inputs b2 and FALSE.

I've verified that AND behaves correctly in all cases:

AND TRUE TRUE 
= (位b1.位b2.b1 b2 FALSE) TRUE TRUE
= TRUE TRUE FALSE
= TRUE
AND TRUE FALSE
= (位b1.位b2.b1 b2 FALSE) TRUE FALSE
= TRUE FALSE FALSE
= FALSE
AND FALSE TRUE
= (位b1.位b2.b1 b2 FALSE) FALSE TRUE
= FALSE TRUE FALSE
= FALSE
AND FALSE FALSE
= (位b1.位b2.b1 b2 FALSE) FALSE FALSE
= FALSE FALSE FALSE
= FALSE

The OR Operator

The OR operator is obviously analogous to the AND operator in many ways. Here is my first attempt:

OR = 位b1.位b2.b1 b2 TRUE

OR returns FALSE only when both of the inputs are FALSE, otherwise, it returns TRUE. I verify that my encoding of OR behaves correctly by checking each case:

OR TRUE TRUE 
= (位b1.位b2.b1 b2 TRUE) TRUE TRUE
= TRUE TRUE TRUE
= TRUE      (Yes!)
OR TRUE FALSE
= (位b1.位b2.b1 b2 TRUE) TRUE FALSE
= TRUE FALSE TRUE
= FALSE      (Oh no!  But if it's b1 b1 b2, then it'd work.)
OR FALSE TRUE
= (位b1.位b2.b1 b2 TRUE) FALSE TRUE
= FALSE TRUE TRUE
= TRUE      (Yes!)
OR FALSE FALSE
= (位b1.位b2.b1 b2 TRUE) FALSE FALSE
= FALSE FALSE TRUE
= TRUE      (Oh no!  But if it's b1 b1 b2, then it'd work.)

So it doesn't work. But for the cases that wouldn't work, I noticed another encoding that would work:

OR = 位b1.位b2.b1 b1 b2

As you can see, applying this encoding to cases 1 and 3 above still work. Therefore, the encoding works in all cases. I changed it to this encoding because I noticed that I need more elements of an input rather than a fixed TRUE as the last input.

I hope by now you see why I love Lambda Calculus! In the next post, I'll talk about the magical function that lets you do recursion: the Y combinator.

Originally published on thealmarty.com