A glimpse at lambda calculus

 

Problem Description

In the 2015 CS1101S mid-term quiz, it asks whether the following functions exhaust time and/or space resources.

const C = (x => x(x))(x => x(x));
const D = (x => (x(x))(x))(x => x(x));
const E = (x => x(x(x)))(x => x(x));
const F = (x => x(x))(x => x(x(x)));

Background

I had no idea how this works until I read something on Lambda Calculus, so I’ll briefly introduce how it works:

Some basic Lambda Calculus

Consider the one of the simplist lambda expression: λx. x+1. It means in a blackbox function, it receives one parameter named x and outputs the result x+1. The λ sign along with the . after the variable name indicates a declaration of lambda function.

So, how do we pass parameter(s) to a lambda function? We write it(or them) right next to the lambda function (, which makes it important to add parentheses at the start and end of a lambda function, because otherwise you may not be able to tell it is a parameter or a part of the function). For instance, (λx. x+1) 1 will output 2 because the lambda function would replace all x after λx. and evaluate the expression.

Connect to Source

Now you find that x => x + 1 is the equivalence Source expression for lambda function (λx. x+1). Moreover, (x, y) => x + y is equivalent to (λx.λy. x+y); a => b => a + b is equivalent to (λa. (λb. a + b)). Notice that a in (λb. a + b) is what we call irrelavent variable because it is not declared at the beginning of this function.

My experience

So, why was I confused with the problem? I thought too much about such a function! Since it is a blackbox function, it merely does substitution, which means it replaces everything x on the rightside of => with the value obtained from the parameter. And the parameter is always the “thing” right next to the function. More importantly, the compiler reads from left to right. When it finishes reading a function, it would look for its parameters immediately. This is the reason why in the following problem D, the first part (((x => x(x))(x => x(x)))) never gets longer. Since (x => x(x)) is the first function compiler reads, the second (x => x(x)) naturally is considered as its parameter and the substitution happens immediately.

Solution

//------------------------------------------------------------
const C = (x => x(x))(x => x(x));
//1. (x => x(x))(x => x(x))
//It is exactly the same as the original one
//Yes and No
//------------------------------------------------------------
const D = (x => (x(x))(x))(x => x(x));
//1. ((x => x(x))(x => x(x)))(x => x(x))
//2. ((x => x(x))(x => x(x)))(x => x(x))
//Then the function never gets longer
//Yes and No
//------------------------------------------------------------
const E = (x => x(x(x)))(x => x(x));
//1. (x => x(x))((x => x(x))(x => x(x)))
//2. ((x => x(x))(x => x(x)))((x => x(x))(x => x(x)))
//3. ((x => x(x))(x => x(x)))((x => x(x))(x => x(x)))
//Then the function never gets longer
//Yes and No
//------------------------------------------------------------
const F = (x => x(x))(x => x(x(x)));
//1. (x => x(x(x)))(x => x(x(x)))
//2. (x => x(x(x)))((x => x(x(x)))(x => x(x(x))))
//Notice the first part of the function remains the same
//This ensures that the tail of the function gets to increase
//infinitely, unlike D and E where the function
//expansion is limited to a fixed-length expansion
//of the first part of the function
//Yes and Yes
//------------------------------------------------------------

Side Notes

In problem D and E, there is a function I referred to as a fixed-length expansion. In lambda expression this can be written as (λx. x x)(λx. x x). (It is slightly different than (x => x(x))(x => x(x)) becuase of parentheses but you can also write it as ((x) => (x)(x))((x) => (x)(x))) to mimic the format of lambda expression, right?) This is an infinite loop that does nothing, and it is the building block to Y-combinatior λf. ((λx. f(x x))(λx. f(x x))) and you may do the simple but tedious substitution job to see that Y-combinatior leads to f(f(f(f(...)))). (You only need to evaluate (λx. f(x x))(λx. f(x x)) part because we have not yet provided value to parameter f)

One more thing

This part is not finished, yet!!!

In the previous blog post, we wrote:

((function(f){return f(f);})(
    (function(make_factorial){
        return function(n){
            return (n===0) ? 1 : n * make_factorial(make_factorial)(n-1);
        };
    })))(5);

After simplification, it looks like (x => x(x))(f => (x => x * f(f)(x-1))).

Recall Y-combinatior, it should look like


Notice: Instead of writing x => f(x(x)) we write x => y => f(x(x))(y)) because we want to use the function! x itself is a function, we we don’t write that way, the return function of Y(f) never expects a number

function Y(f){
    return (x => 
                y => f(x(x))(y))
           (x => 
                y => f(x(x))(y));
}

which is quite different from above. What’s the key? Let me do a quick breakdown:

(x => y => f(x(x))(y))(x => y => f(x(x))(y)) basically applies (x => y => f(x(x))(y)) to itself. If we replace it with a shorter name p, then (x => y => f(x(x))(y))(x => y => f(x(x))(y)) is equivalent to p(p). Then the whole thing can be treated as the result of (g => g(g))(p). Furthermore, f => (p)(p) can be treated as (g => g(g))(f => p).

Notice: I moved f => from the outside to the inside because variable f is only used in p. This change does not affect the generality of our solution.

Next we look at (x => y => f(x(x))(y)) itself. Note that y is the number we receive, so we shall define our “base case” and “inductive step” on with respect to y.

Base case: f(x(x))(0) = 1, which means when y=0 it should return 1

Inductive step: f(x(x))(y) = y * f(x(x))(y-1), which means otherwise it should return y * f(y-1)

What f is? We don’t care! It is a blackbox anyways. We assume we already have such a function f as our parameter(wishful thinking). Then we can start to define what (x => y => f(x(x))(y)) should look like:

function x(f){
    return y => y === 0
                    ? 1
                    : y * f(y-1);
}