Hacker News Reader

Comment by leifmetcalf | Hacker News Reader

I'm a bit confused, how did you implement let, if, else etc.? I don't really know much about the lambda calculus except for what I learned from a short youtube video.

View on HN

There's a good elaboration of it in Tom Stuart's "Programming With Nothing" talk[0], in which he does a lambda calculus implementation of FizzBuzz in what's left of Ruby if you leave everything out except the things strictly necessary to do lambda calculus - with the exception of what you could call C-style macros (basically text search-and-replace, so you can call a section of code FOO and just type FOO everywhere you would have typed that section of code). There's also the little matter of output - you need to translate the resulting Church numerals into readable form for those who can't see that you've obviously produced correct FizzBuzz. There's a good enough explanation that what needs to be sort of hand-waved for brevity (things that are shown but not really explained in detail) aren't entirely opaque - you will be able to figure it out.

Keep in mind, too, that the lambda calculus is a lot like machine language in one respect - the same little bit of "code" can have more than one meaning to the programmer even if the "machine" is doing exactly the same thing.

[0] https://www.youtube.com/watch?v=VUhlNx_-wYk

You can name things like

    (\id. ...) (\x. x)

This names the identity function id. You can make this slightly prettier like

    (\let. ...) (\def body. body def)

Which lets you do

    let (\x. x) \id. ...

Booleans are also functions

    let (\t f. t) \true.
    let (\t f. f) \false.
    let (\x. x) \then.
    let (\x. x) \else.
    let (\b thenLit ift elseLit iff. b ift iff) \if.

Which lets you write

     if true then foo else bar

Where then and else are thrown away, without them it is basically lisp syntax. You could make this slightly fancier - translate into cps to support `else if` and require `end` at the end.

Tl;dr: with hacks

Reply on news.ycombinator.com