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 LC writes all computations as functions. 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. In Lua, we would say

squareDistance = function(x, y)
return x*x + y*y
end
print(squareDistance(3, 4)) --> 25

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:

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:

function True(yes, no)
return yes
end
function False(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:

function True(yes)
return function(no)
return yes
end
end
function False(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):

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:

identity = function(x)
return x
end
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:

function False(yes)
return identity
end
function True(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:

function Not(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:

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:

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?

function Zero(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")

function One(f, answer)
return f(answer)
end

What does Two and Three and Four look like?

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

function Four(f, answer)
return f(Three(f, answer))
end

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

function One(f, answer)
return f(Zero(answer))
end
function Two(f, answer)
return f(One(answer))
end
function Three(f, answer)
return f(Two(answer))
end
-- ...
function Twelve(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!

function successor(num)
return function(f, answer)
return f(num(f, answer))
end
end
Zero = function(f, answer)
return answer
end
One = successor(Zero)
Two = successor(One)
Three = successor(Two)
Four = successor(Three)
Five = successor(Four)
-- ...
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:

Zero = function(f)
return identity
end

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

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,

function add(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:

function add(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:

function multiply(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!