After my last post I realize that writing pure lambda-calculus directly as JavaScript is a little more complicated than I thought, the main reason is because Lambda-calculus uses a lazy evaluation strategy and JavaScript uses more a early evaluation.

So to keep this post less complicated I am going to cheat ðŸ˜€ a little:

# First Numbers

The best choice to represent natural numbers in lambda-calculus would be Church numerals but instead I will use a simplified version called Peano numbers.

The idea of both representation are mostly the same, I think that basically they both use a inductive definition like this:

1) zero is a number,

2) the function successor(number) is a number and successor(number) > number,

3) Nothing else is a number.

**Example:**

lets call successor function as s, so:

zero = 0,

s(zero) = 1,

s(s(zero)) = 2

…

The JavaScript code looks like this:

// zero definition, var zero = 0; // successor definition, function s(x) { return function () { return x; }; } // A function to convert the numbers to decimal representation, function to_dec (n) { if (n !== zero) { return to_dec (n())+1; } else { return 0; } } // Testing alert(to_dec (zero)); // = 0; alert(to_dec(s(zero))); // = 1; alert(to_dec(s(s(zero)))); // = 2;

Now we can define some numerical functions, like predecessor, multiply, add …

for example add can be defined like this:

function add (a, b) { if (a!==zero) { return s(add (a(), b)); } else { return b; } }; alert(to_dec(add(zero, zero))); // 0+0 = 1 alert(to_dec(add(s(zero), s(s(zero))))) // 1+2 = 2;

# Conditional Code

The problem using Peano numbers with pure lambda-calculus is that there is no way to test number zero, thats why using Church numbers is better, but to simplify things I will just cheat a little and make a JS function to test for zero:

// Lambda True/False definitions, function True (x, y) {return x}; function False (x, y) {return y}; // check if number is zero, function isZero (n) { return (n===0)?True:False; }

# Putting all together as factorial function

The factorial function in JS:

function factorial (n) { if (n === 0) { return 1; } else if (n > 0) { return factorial (n-1) * n; } }

To encode the if … else we just need to use our iszero function like this:

iszero(n) (1, (factorial (n-1) * n) )

Now there is a little problem with this encoding, the “(factorial (n-1) * n)” is a function parameter and so JavaScript will always try to evaluate the expression as soon as possible making this code loop forever, while in lambda-calculus the parameter is lazy evaluated and

so the expression is only evaluated when needed to be.

The expression can be rewritten to be delayed in JS but for simplicity I will just leave it like this.

The iszero is a boolean function that will return lambda functions True or False:

True (1, (factorial (n-1) * n)) // => 1 False (1, (factorial (n-1) * n)) // => (factorial (n-1) * n)

Now the rest of factorial have to be encoded in Peano numbers like 1 should be

s(zero) and operators – and * have to be replaced by Peano operators.

# Conclusion

When I started this Posts series, I really was thinking that it would be easier to demonstrate lambda-calculus using a subset of JavaScript like functions, parameters, return and not much more but the posts just got really confusing because JavaScript and Lambda-calculus don’t work in the same way. I am glad that I have done this exercise because now I can understand a little more about the gap that exists between lambda-calculus and JavaScript.