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.
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: books, computer history, computer science, haskell, lambda calculus, lisp, programming, scheme
January 13, 2006 at 1:38 am
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
January 13, 2006 at 1:45 am
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
January 13, 2006 at 2:24 am
Thanks for the .pdf link!
Regards,
Kevin
February 5, 2006 at 6:39 pm
[...] 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. [...]