The premise of this tutorial is the same as this article that uses Ruby but will proceed differently.

The Lambda Calculus has no direct, practical applications. However, it's fundamental in computer science research, and viewing practical methods through the lens of theory sometimes reveals some underlying structure that just makes everything make more sense.

In other words, I think it's pretty neat.

# Effectively Calculable & The Lambda Calculus

When we're programming, we think about lots of different things: tables, variables, numbers, Vector3s, objects, strings, iteration, loops.

A long time ago, computers were just beginning. "Which problems can we use computers to solve?" the world wanted to know.

If you give a human a sheet of paper with a bunch of instructions on it, you can expect the person to (slowly) follow all of the instructions to end up at a result. For example, to explain to a human-computer how to compute `x` to the power of `y`. you could give the following instructions:

1. begin with `p` as `1`
2. if `y` is `0`, the answer is `p`. otherwise, continue.
3. multiply `p` by `x`
4. reduce `y` by `1`
5. go back to step (2)

Computers were different from simple calculators in that you could give them any set of instructions. While a pocket calculator can compute `2 * sqrt(3 * 4 - 8/9)`, it cannot search for the first prime larger than 1000; it cannot compute derivatives; it cannot do many things. This is because it doesn't have the primitives that allow these things.

In programming languages, those important primitives are loops and recursion. However, before programming languages, we needed a way to explain what makes a calculator different from a computer.

The tasks that could be solved by a human-computer (but not a calculator) were called effectively calculable. In the landmark Church-Turing Thesis, effectively calculable was shown to be equivalent to two formal methods that came from math: the Lambda Calculus and Turing Machines.

That is, any set of instructions can be executed by the Lambda Calculus.

COMING SOON: Can computers do everything? Are there problems that aren't effectively calculable? What can't the Lambda Calculus do?

# What is the Lambda Calculus?

The Lambda Calculus writes all computations as pure mathematical functions of one argument.

You're familiar with functions from Lua:

``````function squareDistance(x, y)
return x*x + y*y
end

print(squareDistance(3, 4)) --> 25
``````

You may also be familiar with functions from math: `squareDistance(x, y) = x*x + y*y`.

The LC doesn't give names to functions. Thus we would right in math simply `(x, y) ↦ x*x + y*y`.

As a convenience, in Lua, we could say

``````local squareDistance = function(x, y)
return x*x + y*y
end

print(squareDistance(3, 4)) --> 25
``````

(we don't allow definitions of functions to refer to themselves or in cycles; `local` accomplishes this)

The LC also doesn't use functions that have more than one argument. That seems like a problem -- how can we write `squareDistance`? The answer is by writing the function as a function that returns another function that depends on `x`:

``````local squareDistance = function(x)
return function(y)
return x*x + y*y
end
end

print(squareDistance(3)(4)) --> 25
``````

Rewriting multiple-argument functions like this is called currying (after Haskell Curry, not the spicy food). Calling a function like this is called partial application.

In math notation, we might write `x ↦ (y ↦ x*x + y*y)`. We can also leave off the parenthesis and say `x ↦ y ↦ x*x + y*y`.

One more detail about the LC: we don't allow any objects other than functions to be used (directly) by the LC. That means no strings, no booleans, no numbers, no `+`, no `*`, no `..`, no `math.sqrt`, no `string.find`.

So what do I mean by "any set of instructions can be executed by the LC" if we can't even do arithmetic?

# How to do everything (with the LC): Booleans

First, let's come up with a way to define `true` and `false`. (Remember: we're not allowed to use `true` and `false` themselves -- the only values we may use are functions!)

How do we use `true` and `false` in Lua? We basically use them for `if` and for `while`. Let's just look at `if`.

`if` needs to take a boolean and decide what to do -- should it execute the `then` branch, or should it execute the `else` branch?

An if-true takes the then-branch; an if-false takes the else-branch.

Consider the following code:

``````if condition then
return yes
else
return no
end
``````

In the LC, we can only use functions. If we squint a bit, this looks like the function call `If(condition, yes, no)`. Because "if" and "condition" only mean something together, we'll merge them into the function: `condition(yes, no)`.

Now, let's compare the two forms by inserting `true` and `false` into them:

``````if true then
return yes -- outputs `yes`
else
return no
end
``````

So we expect `True(yes, no)` to be `yes`. Similarly,

``````if false then
return yes
else
return no -- outputs `no`
end
``````

So we expect `False(yes, no)` to be `no`.

These are very straightforward to implement:

``````local True = function(yes, no)
return yes
end

local False = function(yes, no)
return no
end
``````

Finally, remember that the LC doesn't use functions of multiple arguments. Instead, we have to return a function that takes the second argument:

``````local True = function(yes)
return function(no)
return yes
end
end

local False = function(yes)
return function(no)
return no
end
end
``````

We have booleans!

As a syntactic convenience, we can write the `If` function to look a little more familiar. Really, it just applies its second and third arguments to its first (the boolean):

``````local If = function(condition)
return function(thenBranch)
return function(elseBranch)
return condition(thenBranch)(elseBranch)
end
end
end

print( If(True)("Yes!")("No.") ) --> Yes!
print( If(False)("Yes!")("No.") ) --> No.
``````

An aside: look at the values that `True` and `False` return. `False` returns a function that just spits out what it was given. We call that function `identity` because it doesn't change anything about the thing you give it. `True` returns a function that ignores the object its given, and instead returns some other value. Since that value is constantly the same, we can make a constant function that returns whatever value we want:

``````local identity = function(x)
return x
end

local constant = function(c)
return function(_)
return c
end
end

print(identity(5)) --> 5

local oneMaker = constant(1)
print(oneMaker(5)) --> 1 (ignored the value it was given)
``````

If you wanted, `True` and `False` can be written in terms of the `identity` and `constant` helper functions:

``````local False = function(yes)
return identity
end

local True = function(yes)
return constant(yes)
end
``````

We can turn these special function-booleans into regular Lua booleans with a function like this:

``````function TO_BOOLEAN(boolean)
-- the "then-branch" is "true"
-- the "else-branch" is "false"
return If(boolean)(true)(false)
end

print(TO_BOOLEAN(True)) --> true
print(TO_BOOLEAN(False)) --> false
``````

How else do we use booleans? We should be able to write functions like `Not`, `And`, and `Or`.

### Writing `Not`

`Not` is straightforward. We want a `True` to produce a `False`, and a `False` to produce a `True`. We can easily write this using the `If` function we created:

``````local Not = function(boolean)
-- like the opposite of the 'TO_BOOLEAN' function
return If(boolean)(False)(True)
end
``````

### Writing `And`

Here's a definition of the `And` function in regular Lua:

``````function LuaAnd(a, b)
if a then
return b
else
return false
end
end

-- curried,
function LuaAnd(a)
if a then
return function(b) -- identity!
return b
end
else
return function(b) -- constant(false) !
return false
end
end
end
``````

It's easy to write this using our `If` function:

``````local And = function(bool)
return If(bool)( identity )( constant(False) )
end

print(TO_BOOLEAN(  And(False)(False)  )) --> false
print(TO_BOOLEAN(  And(False)(True)  ))  --> false
print(TO_BOOLEAN(  And(True)(False)  ))  --> false
print(TO_BOOLEAN(  And(True)(True)  ))   --> true
``````

### Writing `Or`

`Or` is very similar. `Or(True)` is just `constant(True)` and `Or(False)` is just `identity`:

``````local Or = function(bool)
return If(bool)( constant(True) )( identity )
end

print(TO_BOOLEAN(  Or(False)(False)  )) --> false
print(TO_BOOLEAN(  Or(False)(True)  ))  --> true
print(TO_BOOLEAN(  Or(True)(False)  ))  --> true
print(TO_BOOLEAN(  Or(True)(True)  ))   --> true
``````

# How to do everything (with the LC): Counting

How do we use numbers in Lua, other than arithmetic?

We use numbers in lists' indices, but we're not there yet.

What about `for` loops? `for` loops usually look like this:

``````answer = ...
for i = 1, n do
end

``````

If `n` is `0`, then we don't do anything. If `n` is `1`, we "do stuff" once. If `n` is `2`, we "do stuff" twice.

First, let's try to write a `for` loop using only functions!

A `for` loop of the above form has a few important parameters; the initial value of our `answer` (what we'll return), the function to `doStuff`, the start value for `i` and the `finish` for `i`:

``````function For(i, answer, doStuff, finish)
-- If `start` is bigger than `finish`, we're done: just output `answer`
if i > finish then
end

-- do some stuff

-- increment `i` by one and do the remainder of the loop
end
``````

Here's an example of how to use the above `For` function to compute factorials, factorial(5) = 1 * 2 * 3 * 4 * 5:

``````print(For(
1, -- initial value of `i`
1, -- initial output value (what to output if we do no iterations)
function(x, i) return x*i end, -- how to update output value
5 -- final value of `i`
)) --> 120
``````

If we count backwards, we can get rid of the `finish` parameter:

``````function For(i, answer, doStuff)
-- If `start` is bigger than `finish`, we're done: just output `answer`
if i == 0 then
end

-- do some stuff

-- increment `i` by one and do the remainder of the loop
end

print(For(
5, -- initial value of `i`
1, -- initial output value (what to output if we do no iterations)
function(x, i) return x*i end -- how to update output value
)) --> 120
``````

Let's also simplify a lot and don't provide `i` to `doStuff`. Instead, it would have to be manually managed by `answer`:

``````function For(i, answer, doStuff)
-- If `start` is bigger than `finish`, we're done: just output `answer`
if i == 0 then
end

-- do some stuff

-- increment `i` by one and do the remainder of the loop
end

print(For(
5, -- how many iterations
{p=1, i=1}, -- p: current product. i: current value of i (starts at 1)
function(a) return {p=a.p*a.i, i=a.i+1} end -- multiply p by i; increase i by 1
).p) --> 120
``````

### Counting Iterations

Let's say we want to make the particle `For(0, ...)` into its own function that we'll call `Zero`. What does it look like?

``````local Zero = function(doStuff, answer)
-- do no iterations. just output the initial answer
end
``````

This does the iteration exactly 0 times.

What does `One` look like? I'll abbreviate `doStuff` to `f` from now on (short for "some _f_unction")

``````local One = function(f, answer)
end
``````

What does `Two` and `Three` and `Four` look like?

``````local Two = function(f, answer)
end

end

end
``````

This is getting repetitive. In fact, there's a nicer way to write `Four`. Since `Three(f, answer)` is `f(f(f(answer)))`, we can write `Four` as the following:

``````local Four = function(f, answer)
end
``````

Similarly, we can write `One` and `Two` and `Three` and so on in this way:

``````local One = function(f, answer)
end

end

end

-- ...

end
``````

Notice that the pattern between successive numbers is the same. We could write this as a `successor` function!

``````local successor = function(num)
end
end

end

local One = successor(Zero)
local Two = successor(One)
local Three = successor(Two)
local Four = successor(Three)
local Five = successor(Four)
-- ...
local Twelve = successor(Eleven)
``````

Does it actually work? Let's try it out with factorial again:

``````print( Five(function(a) return {p=a.p*a.i, i=a.i+1} end, {p=1, i=1}).p ) --> 120
``````

Yes, it does!

### Writing Numbers in the LC

We aren't quite to the form that the LC requires: we're still using multiple arguments. We should curry our number functions, starting with `Zero`:

``````local Zero = function(f)
return identity
end
``````

The only other function that needs to be fixed is `successor`:

``````local successor = function(num)
return function(f)
return function(value)
return f(num(f)(value))
end
end
end
``````

And this does in fact work!

``````print(
Five( -- do the following function 5 times
function(a) return {p=a.p*a.i, i=a.i+1} end -- multiply p by i; increase i by 1
)(
).p -- get the final product
) --> 120
``````

### Converting LC numbers to Lua Numbers

We should build a `TO_NUMBER` function (akin to the `TO_BOOLEAN` function) to convert these special function-numbers into regular Lua numbers.

We know that `ZERO` will just give us its second argument; thus the second argument has to be `0`.

We know that `ONE` will give us `f(0)`, which should be `1`. We know `TWO` will give us `f(f(0))` which should be `2`. We know `THREE` will give us `f(f(f(0)))` which should be `3`.

What can we make `f` be? `f(0) = 1`; `f(1) = 2`; `f(2) = 3`; ... so we can say `f(x) = x+1`!

``````function TO_NUMBER(num)
return num(function(x) return x+1 end)(0)
end

print(TO_NUMBER(ZERO)) --> 0
print(TO_NUMBER(ONE)) --> 1
print(TO_NUMBER(TWO)) --> 2
print(TO_NUMBER(THREE)) --> 3
print(TO_NUMBER(FOUR)) --> 4
print(TO_NUMBER(FIVE)) --> 5
``````

# How to do Arithmetic with the LC

We have numbers, and we have already defined one basic operation on them: `successor`, which adds one to any number.

Numbers have many more operations: addition, multiplication, subtraction, division, etc.

What if we want to add two numbers together?

We want to define an `add(a, b)` function that produces the addition of two numbers.

We know that `add(0, b)` should be `b`. We know that `add(1, b)` should be the successor of `b`. We know that `add(2, b)` should be 2+b, or, the successor of the successor of `b`.

That is, `add(a, b)` is just `b` with `successor` applied `a` times. Written in code,

``````local add = function(a, b)
return a(successor)(b)
end

print(TO_NUMBER(  add(One, Two)  )) --> 3
print(TO_NUMBER(  add(Five, Zero)  )) --> 5
print(TO_NUMBER(  add(Five, Two)  )) --> 7
print(TO_NUMBER(  add(Three, One)  )) --> 4
``````

We should curry `add` of course:

``````local add = function(a)
return function(b)
return a(successor)(b)
end
end
``````

Here is a good time to point out that currying can be useful. Normally, we use functions by giving them all of their arguments:

`add(Five)(One)`

However, we don't need to give all of the arguments. For example, what is the meaning of this?

`local p5 = add(Five)`

`p5` becomes the function that adds five to its argument.

You can observe that `add(One)` is the same as `successor` and that `add(Zero)` is the same as `identity`.

### Multiplication in the LC

What if we want to add two numbers together?

We want to define `multiply(a)(b)`.

We know that `multiply(Zero)(b)` should produce `Zero`.

We know that `multiply(One)(b)` should produce `b`.

We know that `multiply(Two)(b)` should produce `add(b)(b)`

We know that `multiply(Three)(b)` should produce `add(add(b)(b))(b)`.

Notice that `b` is the same as `add(Zero)(b)`. Notice that `add(b)(b)` is the same as `add(add(Zero)(b))(b)`.

In other words, in order to multiply `a` and `b`, we want to `add(b)` `a`-times to `Zero`:

``````local multiply = function(a)
return function(b)
end
end

print(TO_NUMBER(  multiply(Three)(Five)  )) --> 15
print(TO_NUMBER(  multiply(Four)(One)  )) --> 4
``````

# Next Time

I'll continue this adventure in another post -- with more general loops, predecessors, subtraction, and division.

Please leave feedback about what should be made clearer and any things that you need to understand before being able to understand this post!

This is most likely not the best place to start; I will write more articles that flesh out how to use functions effectively that will hopefully make all of this make a lot more sense!