Compiling to lambda-calculus: Turtles all the way down

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? "<p>No, the other direction requires simulating a Turing machine with lambda calculus.

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've been working on a combinatoric approach with Fexl, "compiling" all the way down to my two turtles S and C, e.g.:<p><a href="http://fexl.com/blog/9" rel="nofollow">http://fexl.com/blog/9</a><p>I'm also relying on two higher-level combinators L and R to reduce the size of the combinatorial forms, e.g.:<p><a href="http://fexl.com/blog/10" rel="nofollow">http://fexl.com/blog/10</a><p>The bottom line is that the entire Fexl parser is defined in terms of the two primitive combinators S and C.

I don't fully understand lambda calculus, but i inferred a stack overflow from his tattoo?<p>Went to buy the book and its beyond my budget at the moment ($215 on Amazon).

"Barendregt is a helluva drug."<p>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...

Nothing like posting a picture of the y-combinator on a ycombinator.com site :)