from Hacker News

Compiling to lambda-calculus: Turtles all the way down

by budu on 1/17/11, 4:11 PM with 25 comments

  • by sb on 1/17/11, 10:00 PM

    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)

  • by shasta on 1/17/11, 5:10 PM

    "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.

  • by joshrule on 1/17/11, 8:08 PM

    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.

  • by fexl on 1/17/11, 9:25 PM

    I've been working on a combinatoric approach with Fexl, "compiling" all the way down to my two turtles S and C, e.g.:

    http://fexl.com/blog/9

    I'm also relying on two higher-level combinators L and R to reduce the size of the combinatorial forms, e.g.:

    http://fexl.com/blog/10

    The bottom line is that the entire Fexl parser is defined in terms of the two primitive combinators S and C.

  • by binarymax on 1/17/11, 5:14 PM

    I don't fully understand lambda calculus, but i inferred a stack overflow from his tattoo?

    Went to buy the book and its beyond my budget at the moment ($215 on Amazon).

  • by joelhaasnoot on 1/17/11, 5:14 PM

    "Barendregt is a helluva drug."

    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...

  • by iam on 1/18/11, 6:12 AM

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