Global Moderator

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:

  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
    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!