# What is this article

This article is a foray into abstract computer science, implemented in a language you know - Lua!

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:

- begin with
`p`

as`1`

- if
`y`

is`0`

, the answer is`p`

. otherwise, continue. - multiply
`p`

by`x`

- reduce
`y`

by`1`

- 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
answer = doStuff()
end
print(answer)
```

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!

### Recursion instead of loops

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
return answer
end
-- do some stuff
answer = doStuff(answer, i)
-- increment `i` by one and do the remainder of the loop
return For(i+1, answer, doStuff, finish)
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
return answer
end
-- do some stuff
answer = doStuff(answer, i)
-- increment `i` by one and do the remainder of the loop
return For(i-1, answer, doStuff)
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
return answer
end
-- do some stuff
answer = doStuff(answer)
-- increment `i` by one and do the remainder of the loop
return For(i-1, answer, doStuff)
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
return 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)
return f(answer)
end
```

What does `Two`

and `Three`

and `Four`

look like?

```
local Two = function(f, answer)
return f(f(answer))
end
local Three = function(f, answer)
return f(f(f(answer)))
end
local Four = function(f, answer)
return f(f(f(f(answer))))
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)
return f(Three(f, answer))
end
```

Similarly, we can write `One`

and `Two`

and `Three`

and so on in this way:

```
local One = function(f, answer)
return f(Zero(answer))
end
local Two = function(f, answer)
return f(One(answer))
end
local Three = function(f, answer)
return f(Two(answer))
end
-- ...
local Twelve = function(f, answer)
return f(Eleven(answer))
end
```

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

function!

```
local successor = function(num)
return function(f, answer)
return f(num(f, answer))
end
end
local Zero = function(f, answer)
return answer
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=1, i=1} -- start with i=1, p=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.

### Addition in the LC

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)
return a(add(b))(Zero)
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!