Programming Advanced: Lambdas and Continuations

Let's start by talking about maths, specifically the expression 1 + 2 + 3. It's obvious that this resolves to 6, but how do we get there? We add the numbers, but in which order do we add them?

1 + 2 + 3 | 1 + 2 + 3 | 1 + 2 + 3
-> 3 + 3  | -> 1 + 5  | -> 4 + 2
-> 6      | -> 6      | -> 6

The thing with addition is that it doesn't really matter what order you do the addition in. In math terms we say addition is "transitive". If we wanted to force a specific order we can still do that:

1 + (2 + 3)
-> 1 + 5
-> 6

Brackets let us force maths to do something in the order we want. The rule is that you do everything in the brackets first, and then everything outside it after. For a transitive action like addition this doesn't make a difference, but it does matter when we mix addition and multiplication

5 * 3 + 10 | (5 * 3) + 10 | 5 + (3 + 10)
-> 15 + 10 | -> 15 + 10   | ->  5 * 13
-> 25      | -> 25        | -> 65

In math we use brackets to force something to be done in order

How else can we force something to be done in order?

As far as normal maths is concerned we can just say that brackets are brackets, and never look further into it. There is a branch of maths that cares about the order in which we do things, and we're going to look at this further.

lambda x . x + 1

This is a "lambda function". Normally they're referred to with the greek symbol but my keyboard doesn't have that, so we'll just spell "lambda" in full. This is a math construct from a branch of maths called "Lambda Calculus".

lambda x . x + 1
"Give me a value and I will return it + 1"

"Give me a value and I will return it + 1", "Do this with 3"
(lambda x . x + 1) 3
-> 3 + 1
-> 4

"Give me a value and I will return it + 1", "Do this with 10"
(lambda x . x + 1) 10
-> 10 + 1
-> 11

"Give me a value and I will return it multiplied by itself", "Do this with 5"
(lambda x . x * x) 5
-> 5 * 5
-> 25

If you're familiar with programming you might think this looks like a function. Programming functions as they appear in modern languages are based on lambda functions.

Lambda calculus
(lambda x . x + 1) 3

// JavaScript
function(x) { return x + 1 }(3);
(x => x + 1)(3)

# Python
(lambda x : x + 1)(3)

So what does this have to do with brackets?

5 * (3 + 10)
-> 5 * 13
-> 65

5 * (3 + 10)
-> (lambda x . 5 * x) (3 + 10)
-> (lambda x . 5 * x) 13
-> 5 * 13
-> 65

Let's take this to an extreme so we understand what's going on here:

To convert a number from Celsius to Fahrenheit, do the following:
- multiply by 9        (lambda x . x * 9)
- divide by 5          (lambda x . x / 5)
- add 32               (lambda x . x + 32)

Remember that lambdas are calculated right-to-left, so this will look like it's in the wrong order
Here's what it looks like to do convert 10 degrees Celsius to Fahrenheit:

(lambda x . x + 32) (lambda x . x / 5) (lambda x . x * 9) 10
-> (lambda x . x + 32) (lambda x . x / 5) (10 * 9)
-> (lambda x . x + 32) (lambda x . x / 5) 90
-> (lambda x . x + 32) (90 / 5)
-> (lambda x . x + 32) 18
-> 18 + 32
-> 40

Is there anything I can do with this now?

The programming languages that provide lambdas usually have a way to use them on lists

let doubleLambda = (x) => x * 2;

let mylist = [10, 20, 30, 40];
mylist.map(doubleLambda); // returns [20, 40, 60, 80]

In JavaScript, map is a method on lists which allows you do do something to every value in the list. The "something" is provided in the form of a lambda. The above code does something like this:

[10, 20, 30, 40].map(x => x * 2);
[(x => x * 2)(10), (x => x * 2)(20), (x => x * 2)(30), (x => x * 2)(40)]; // apply the lambda to each value in the list
[10 * 2, 20 * 2, 30 * 2, 40 * 2];
[20, 40, 60, 80];

Break time!

Let's stop here for now. This is a lot of info to take in, and the implications of lambdas take a while to really understand. Let's recap:

Sometimes we need to do one thing, and then we need to do another thing. In normal math we use brackets.
There's a math structure that lets us capture "give me a thing and I'll do something with it". These are called lambda functions, and the math around this is called Lambda Calculus
We can use lambdas to force certain things to happen in an order we want.
We can break algorithms like the Celsius to Fahrenheit into individual steps using lambdas

In the next lesson we'll look into lambdas more and see what we can do with them.