Counting by lambdas

One of the nice things about functional languages is that you’re closer to the mathematical underpinnings of computer programming. Now, maybe you don’t like maths, but then you’ll have to learn to live with a necessary evil, for trying to be serious about programming without taking the plunge into abstract thinking is like wanting to be an astronomer without writing down a single equation. In my experience, both in the industry and as a CS teacher, the ability of abstraction is the most useful and, unfortunately, hardest to find quality when it comes to programming.

Structure and interpretation of computer programs I entered the functional programming world some years ago through a golden gate: SICP. It was an amazing journey full of magical moments: recursion, higher-order functions, generics, lazy evaluation, metacircular interpreters, compilers… a journey i have reedited many times afterwards… i still watch a SICP lecture now and then instead of taking my TV to the repair shop.

Among those moments, one that i specially recall is my first encounter with Church Numerals. I remember staring blankly for quite a while to the code in exercise 2.6:

(define zero (lambda (f) (lambda (x) x)))

(define (add-1 n)
(lambda (f) (lambda (x) (f ((n f) x)))))

And then something clicked in, and i’ve been amazed ever since. Of course, Church numerals are just the tip of the iceberg: from there i went to learn Lambda Calculus, and realized that there were powerful and deep principles at play underneath that fun hacking hobby of mine.

Things can get pretty hairy from here. If you think that the above lambda tricks are old hat and not worth such a fuss, take a look at the impressive fireworks of Oleg’s with Lambda Calculus, Scheme and Haskell, including negative numbers, substraction and division: i’m sure you will find them much more fun.

But if you’d rather follow a gentler path through this magic, the better introduction i’ve read is Chris Hankin’s An Introduction to Lambda Calculi for Computer Scientists. Or, if you prefer online stuff, this javascript-enabled lambda tutorial. From there, you can go to… well, to many places. For instance, McCarthy’s original paper on Lisp, or any of the Lambda Papers by Steele and Sussman. And of course, if you want to get to the very marrow of it, Barendregt’s Shorter introduction to the lambda calculus (free PDF), and the definitive The Lambda Calculus, its syntax and semantics will keep you busy for quite a while. Enjoy!

Tags: , , , , , , ,

4 Responses to “Counting by lambdas”

  1. kkwoo Says:

    Hi,

    I tried to follow the http://citeseer.nj.nec.com/barendregt94introduction.html link, but I’m unable to reach it. Google searches I made for Barendregt’s paper didn’t find any matches. Are you still able to load http://citeseer.nj.nec.com/barendregt94introduction.html ? If so, that means I picked a bad day to find Barendregt’s paper.

    Regards,

    Kevin

  2. jao Says:

    Hi,

    A copy of Barendregt’s paper is available at this URL:

    http://ling.ucsd.edu/~barker/Lambda/barendregt.94.pdf

    I’m updating the link in the article. Thanks for pointing this out!

    jao

  3. kkwoo Says:

    Thanks for the .pdf link!

    Regards,

    Kevin

  4. programming musings » Blog Archive » As simple as possible… Says:

    […] If you’ve got this far, you already have one of the qualities needed to become a programmer: stamina. You’ll need more. Be prepared to study hard, to learn maths, to live in abstract worlds. If you feel that you have “more important things to do”, well, that’s all very well, but don’t ask the rest of us to dumb down the subject so that everybody can be a programmer. Lisp is not a sin. The sin would be to betray the dreams, ideals and hard work of the people that have taken us this far. We owe that to them, and to ourselves. […]


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: