Compiling to lambda-calculus: Turtles all the way down (matt.might.net) |
Compiling to lambda-calculus: Turtles all the way down (matt.might.net) |
No, the other direction requires simulating a Turing machine with lambda calculus.
But, those are exactly the language features that make it easy to implement a Turing machine.
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.
Thank you very much!
I'm also relying on two higher-level combinators L and R to reduce the size of the combinatorial forms, e.g.:
The bottom line is that the entire Fexl parser is defined in terms of the two primitive combinators S and C.
Went to buy the book and its beyond my budget at the moment ($215 on Amazon).
You'll get a stack overflow in a strict language, but not a lazy one.
WTF?!??
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...
Never saw him lecture though.
Still, I give a big "WTF?!??" to the idea of paying $597 for any version of this book. I mean, I'm sure it's a good book, but $597 worth????
Heck, even $215 seems a bit crazy.
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 tweaked the abstract a bit to reflect your point.
I'll do a follow-on post on how to explicitly reduce the lambda calculus to Turing machines and vice versa.
Most of the hard work is done with this post.