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%)

9 thoughts on “Lambda-calculus recursion with factorial example (Final Part, numbers and conditions)

  1. Hey there I am so happy I found your blog, I really found you by accident, while I was researching on Digg for something else, Anyhow I am here now and would just like to say cheers for a fantastic post and a all round enjoyable blog (I also love the theme/design), I don’t have time to browse it all at the moment but I have book-marked it and also added your RSS feeds, so when I have time I will be back to read a lot more, Please do keep up the fantastic job.

  2. Greetings from Colorado! I’m bored at work so I decided to browse your website on my iphone during lunch break.
    I enjoy the knowledge you provide here and can’t wait to take a look
    when I get home. I’m shocked at how quick your blog loaded
    on my cell phone .. I’m not even using WIFI, just 3G ..
    Anyways, wonderful site!

  3. Heya are using WordPress for your site platform? I’m new to the blog world but I’m trying to get started and set up my own. Do you require any html
    coding expertise to make your own blog? Any help would be really
    appreciated!

  4. Howdy are using WordPress for your site platform? I’m new to
    the blog world but I’m trying to get started and set up my
    own. Do you need any coding knowledge to make your own blog?

    Any help would be really appreciated!

  5. What you said was very logical. But, what about this?

    what if you composed a catchier post title? I mean, I
    don’t wish to tell you how to run your blog, but suppose you added
    a headline that makes people desire more? I mean Lambda-calculus recursion with factorial example (Final
    Part, numbers and conditions) | fsvieira is a little plain. You could glance at Yahoo’s home
    page and see how they create news titles to grab
    people to open the links. You might add a video or a picture or two to grab readers interested about what you’ve written. Just
    my opinion, it might make your posts a little livelier.

  6. Just desire to say your article is as astonishing.
    The clarity for your submit is simply spectacular and
    that i could assume you are a professional on this subject.
    Fine together with your permission allow me to grasp your feed to keep up to date
    with coming near near post. Thanks a million and please keep up the gratifying work.

  7. Nice post. I was checking continuously this blog and I’m impressed!

    Very useful info specifically the last part :
    ) I care for such information a lot. I was looking for this particular info for
    a very long time. Thank you and best of luck.

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>