13 ms·
Show HN: LambdaLisp – A Lisp interpreter that runs on lambda calculus
- lisper 4y agoThis is one of the most mind-blowing things I have ever seen. Words fail me, so I'll appropriate some of the author's: "Lisp has been described by Alan Kay as the Maxwell’s equations of software. In the same sense, I believe that lambda calculus is the particle physics of computation. LambdaLisp may therefore be a gigantic electromagnetic Lagrangian that connects the realm of human-friendly programming to the origins of the notion of computation itself." BTW, if you have no idea what is going on here, eight years ago I took a whack at writing a gentle introduction to this same sort of thing, but done in a more half-assed way, and with a much less ambitious scope: https://flownet.com/ron/lambda-calculus.html https://flownet.com/ron/lambda-calculus.html
- eointierney 4y agoDelightful, thank you
- bobbylarrybobby 4y agoFantastic read, thanks.
- haskellandchill 4y agoThen what is System F?
- invisiblerobot 4y agopolymorphic typed lambda calculus. it's the theoretical basis for ML and Haskell. https://en.wikipedia.org/wiki/System_F https://en.wikipedia.org/wiki/System_F
- invisiblerobot 4y agoOh I see, you were asking rhetorically :)
- haskellandchill 4y agoHa yes, I see it more as a candidate for a maxwell's equations of software engineering than the metacircular interpreter.
- smitty1e 4y ago> Here is a PDF showing its entire lambda term, which is 42 pages long: Elsewhere, Douglas Adams smiles.
- zentr1c 4y agoThis
- somewhereoutth 4y agoAh but this is where it becomes interesting! Because we can then guage how much work this abstraction is doing for us - and indeed whether or not it might stray from the 'one true path' (whatever that might be)
- zentr1c 4y agoMaybe I am stupid but what's the point in reimplementing lisp in lambda? Just to prove how beautiful simple lambda calculus is? The lambda functionality is allready in lisp. And lisp is beautiful simple! () is nothing and (is something) What does the implementation show more beautiful than that?
- tromp 4y agoBinary Lambda Calculus is indeed beautifully simple [1]. LISP is rather complex by comparison, but then it's full-fledged non-esoteric programming language. [1] https://www.ioccc.org/2012/tromp/hint.html https://www.ioccc.org/2012/tromp/hint.html
- jart 4y agoWe do what we must because we can.
- actually_a_dog 4y agoThis is undoubtedly cool, but I'd be really impressed if it wasn't stupidly slow. (I'm not saying it is stupidly slow, because I haven't had a chance to run it, just that I'd be impressed if it wasn't.)
- lisper 4y agoI haven't tried it either, but I would not bet my life savings on it being slow. I tried something similar to this a few years ago (see my top-level comment for a pointer) and was amazed at how fast it turned out to be.
- quickthrower2 4y agoIt has to be slow. Multiplication will be O(N^2)!
- sudosysgen 4y agoMultiplication is generally done in O(n^2) of the number of bits so I'm not sure what you mean to say. Do you mean O(n^2) of the size of the operands?
- quickthrower2 4y agoIn Lambda calculus, numbers are encoded using 0 and successor. So 3 = S(S(S(0))) Adding these would be O(N+M) where N and M are the numbers, not the number of bits. Multiplying is O(N*M) where again it is the numbers. 1000*1000 would require a million operations at least. It takes a million operations just to store/read the number million! See: https://en.wikipedia.org/wiki/Church_encoding https://en.wikipedia.org/wiki/Church_encoding Unless this HN submitted implementation doesn't use church encoding. In which case I am wrong.
- atennapel 4y agoThe page mentions that the implementation has 32 bit signed integers, plus it uses Scott encodings and not Church.
- tromp 4y agoAs author of the Binary Lambda Calculus (BLC), I find this quite fascinating. It implements LISP in 163,654 bits of BLC. For comparison, minimal esoteric languages like BLC itself can be implemented in 232 bits of BLC, and Brainfuck in 893 bits. I'm still reading the document, but one thing that caught my eye is the List encoding with cons and nil, which is claimed to be a Mogensen-Scott one. Rather, cons \x\y\c. c x y is the Scott encoding of infinite lists that have no nil terminator (also known as streams) and thus only one constructor, while nil is the Scott encoding in nil-terminated lists with 2 constructors. Thus the given encoding is some non-standard hybrid of streams and lists that helps BLC achieve its conciseness. In Wikipedia [1] it's described as > Alternatively, with NIL := FALSE, the construct l (λh.λt.λz.deal_with_head_h_and_tail_t) (deal_with_nil) obviates the need for an explicit NULL test [1] https://en.wikipedia.org/wiki/Lambda_calculus#Pairs https://en.wikipedia.org/wiki/Lambda_calculus#Pairs
- lisper 4y ago> It implements LISP in 163,654 bits of BLC. For comparison, minimal esoteric languages like BLC itself can be implemented in 232 bits of BLC, and Brainfuck in 893 bits. That's hardly a fair comparison. LambdaLisp includes a ton of features that BLC and BF do not.
- keithalewis 4y agoSlap yourself and reread the rest of the post.
- lisper 4y agoSorry, I’m going to need you to give me a little more of a clue what you are talking about.
- keithalewis 4y agoYou missed the substantive portion of the post.
- 4y ago
- somewhereoutth 4y agoLambda calculus is mathematically foundational in a way that Lisp of course isn't. The question is what does Lisp give us as an interpretation of those foundations? Or does it admit issues that might be unhelpful? (Are macros a good thing?)
- lisper 4y agoLet's not sell Lisp short here. LC might be mathematically foundational, but I think it's fair to say that Lisp is computationally foundational. Mathematics and computation are related, of course, but they are not identical. Computation is the study of mechanical processes for doing math. As such, Lisp's identification of CONS/CAR/CDR/COND as a sufficient set of primitives for a universal Turing machine is important because it's obvious (or at least it was obvious by 1958) how those primitives can be implemented as a mechanical process. Implementing LAMBDA in all its generality is far less obvious, which is why it took 20 years of further research to go from Lisp 1 to Scheme.
- somewhereoutth 4y agoI'd say that all foundations are mathematical (at least for 'concrete' stuff, and more besides). If lisp was foundationaly interesting presumably mathematicians would have given it more study? (perhaps they did?) I would disagree that computation is process for doing math - it is math in its own right, specifically that for operating over a discrete state space (urgh help needed to tighten this statement up) LC is basically a rewrite engine, so I'm not sure it would be so hard to implement? Probably some plastic bags, in two colours, paper scraps, and a marker pen would do it? (Edit - one colour bag would need 2 ordered compartments - or if you really have lots of spare time you could build it all with just plain bags and some set theory) However as you say perhaps Lisp is a better abstraction over the Turing tape (yuck).
- lisper 4y ago> I would disagree that computation is process for doing math Sorry, but you are mistaken. This is not a matter of opinion, it is a matter of historical fact. There is a reason that the title of McCarthy's original Lisp paper ends with "and Their Computation by Machine." The opening paragraph of Turing's 1936 paper ends with the sentence, "According to my definition, a number is computable if its decimal can be written down by a machine." > specifically that for operating over a discrete state space. Sorry, but you are mistaken about that too. Analog computers and quantum computers are computers but they do not operate over discrete state spaces. They are, however, machines.
- contravariant 4y agoHere I was wondering what a lambda expression implementing lisp would look like. Page 33: >(((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((... Yeah that seems about right.
- somewhereoutth 4y agoYes but isn't it beautiful? But seriously, instead of seeing lots of brackets, see the whole as a texture, a texture that has some importance (per Lisp advocates). See it in context with other textures, indeed all possible textures.
- ducktective 4y agoPage 32 of the pdf...omg the legends were true! https://woodrush.github.io/lambdalisp.pdf https://woodrush.github.io/lambdalisp.pdf