While this is a nice article on compiling to lambda calculus, the uninitiated might find Barendregt's "Introduction to Lambda Calculus" (ftp://ftp.cs.ru.nl/pub/CompMath.Found/lambda.pdf) an invaluable resource. (IMHO, it's the best work for groking lambda calculus, at least it was for me and my learning prefernece/style)
"The other direction requires more thought: how do you coax such a simple language into providing the features we expect of a modern programming language, such as numbers, Booleans, conditionals, lists and recursion? "
No, the other direction requires simulating a Turing machine with lambda calculus.
Just a quick little note to thank you for your series of posts, not just this one. I've been trying to get my head wrapped around the lambda calculus and your posts have been by far the most enlightening ones on the subject.
That really is a strange paragraph. Turing machines only consist of a line of memory cells, a pointer to the current cell, and a CRUD mechanism for the cells.
Sure, but the otherwise excellent OP isn't about that. It's about building higher level concepts out of the lambda calculus. Nothing to do with Turing machines.
Turing machines and lambda calculus are both foundational languages on top of which those higher level concepts can be constructed.
How to translate back and forth from Turing machine to lambda calculus is something I really want to understand actually. I've been meaning to sit down and figure it out but haven't done it yet.
I'm always a bit awed when recognizable functions like 'if' and 'let' start emerging from a mess of lambdas and Xs. It amazing how simple items and simple rules can combine to create fantastically intricate systems (i.e. the entire space of computable functions). Thanks for sharing, Matt.
I was confused a while till I saw you talking about Moses Schönfinkel. From everything I've seen people usually refer to those as SK combinators not SC combinators.
Right, that's "K" as in "Konstanzfunktion" in the original German. The book "From Frege to Gödel" uses "C" as in "Constancy Function" in English, and I got in the habit of using that.
Not sure I agree: his lectures are quite sleep inducing these days. Though reducing programming to something so simple and mathematical does open lots of possibilities...
He teaches classes at the Radboud University in Nijmegen, the Netherlands, specifically my "Languages and automata/machines" class. He has a "zen" something going on with lots of interesting comments.