Monthly Archives: January 2014

Lambda-calculus recursion with factorial example (Final Part, numbers and conditions)

What do you think of this post?
  • Awesome (0.0%)
  • Interesting (0.0%)
  • Useful (0.0%)
  • Boring (0.0%)
  • Sucks (0.0%)

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.

What do you think of this post?
  • Awesome (0.0%)
  • Interesting (0.0%)
  • Useful (0.0%)
  • Boring (0.0%)
  • Sucks (0.0%)

JavaScript code riddle

What do you think of this post?
  • Awesome (100.0%)
  • Interesting (0.0%)
  • Useful (0.0%)
  • Boring (0.0%)
  • Sucks (0.0%)

Today I was talking to a friend about some codding “riddles” and I remembered a riddle in C code that I saw long time ago.

The riddle is like this: having the following JS code

var c;

// YOU CAN NOT CHANGE THE FOLLOWING CODE
if (c===c) {
    alert ("YOU LOSE!");
}
else {
    alert ("YOU WIN!");
}

By changing only the c value you have to make the code display the “YOU WIN!” message.

Leave you answer in the comments… :)

What do you think of this post?
  • Awesome (100.0%)
  • Interesting (0.0%)
  • Useful (0.0%)
  • Boring (0.0%)
  • Sucks (0.0%)