5 ms·
Lambda Calculus in 383 Bytes (2022)
- memming 2y ago"our 521 byte virtual machine is expressive enough to implement itself in just 43 bytes" whaat!
- johnisgood 2y agoThe 43-byte implementation might define only a subset of the functionality provided by the full VM, enough to "bootstrap" into the full implementation, most likely. In fact, if the VM is Turing complete, it can theoretically emulate any computation, including its full implementation, even from a small subset of operations. The point is that the 43-byte implementation does not need to encode the entire VM explicitly. For example, if the VM has built-in primitives for looping, branching, and memory management, the minimal implementation can leverage these to rebuild the remaining functionality.
- tromp 2y agoMy IOCCC entry [1] explains exactly what the 43-byte program is. It's a self-interpreter for BLC8, the byte based version of Binary Lambda Calculus. The 521 byte interpreter on the other hand is written in x86 assembly, a language much less suitable for writing BLC8 interpreters than BLC8 itself. Btw, with my latest lambda compiler, the BLC8 self interpreter is only 42 bytes: λ 1 ((λ 1 1) (λ (λ λ λ 1 (λ λ λ 2 (λ λ λ (λ 7 (10 (λ 5 (2 (λ λ 3 (λ 1 2 3))) (11 (λ 3 (λ 3 1 (2 1))))) 3) (4 (1 (λ 1 5) 3) (10 (λ 2 (λ 2 (1 6))) 6))) 8) (λ 1 (λ 8 7 (λ 1 6 2)))) (λ 1 (4 3))) (1 1)) (λ λ 2 ((λ 1 1) (λ 1 1)))) [1] https://www.ioccc.org/2012/tromp/ https://www.ioccc.org/2012/tromp/
- johnisgood 2y agoYeah, I just took a real look now. It uses a metacircular evaluator? I didn't look at the link provided just yet though! :D
- cess11 2y ago"For example, its metacircular evaluator is 232 bits. If we use the 8-bit version of the interpreter (the capital Blc one) which uses a true binary wire format, then we can get a sense of just how small the programs targeting this virtual machine can be." From TFA. I think it's a very good article.
- Dansvidania 2y agothanks, this is helping me understand the whole article a bit better.
- rizky05 2y agoDoes not work on mac: > { printf 0010; printf 0101; } | ./lambda.com; echo zsh: done { printf 0010; printf 0101; } | zsh: segmentation fault ./lambda.com
- tromp 2y agoIt doesn't work on modern Apple Silicon macs with M1-4 chips (although Rosetta [1] might be able to handle it somehow), but it works fine on my older x86 based iMac. [1] https://en.wikipedia.org/wiki/Rosetta_(software) https://en.wikipedia.org/wiki/Rosetta_(software)
- freehorse 2y agoNo it does not (I opened the x86 version of the terminal with rosetta and run the commands and get the same error).
- exikyut 2y agoI've been attracted to this - along with 2D cellular automata - a bit like a moth to a flame for some time. I find the little machine visualisations mesmerising, the heavily parenthesized Greek representation charming (they look like standing orders written in an alien language, looking for all the world like space invaders) and the tiny code sizes magical. But I can't quite wrap my mind around the core concepts and internalize them into a mental model. It's too different from the simple world of imperative C or scripting languages I guess I call home. So I'm left watching das blinkenlights from the outside, as my attention span chokes on the layers of computer science incorporated into typical explanations. *shrug* I'd be very interested if anyone knows of an ELI5-style alternate path I could walk to break each of the concepts down one at a time. (I ask because I think this is (currently) the kind of thing I think ChatGPT would struggle to present as effectively as a human.)
- joseda-hg 2y agoIt's too basic for what you need but the video from eyesomorphic [1], is a wonderful conceptual introduction [1] https://www.youtube.com/watch?v=ViPNHMSUcog https://www.youtube.com/watch?v=ViPNHMSUcog
- tromp 2y ago> Whilst it certainly isn't a contender for modern programming languages Yet all that separates the λ-calculus from one modern programming language, Haskell, is a layer of syntactic sugar on top, and a runtime that effectuates its pure IO actions. We can in fact compile Haskell programs using just stdin/stdout for IO into terms of the untyped lambda calculus, as wonderfully demonstrated in Ben Lynn's IOCCC entry [1], or equivalently, into BLC programs. [1] https://www.ioccc.org/2019/lynn/index.html https://www.ioccc.org/2019/lynn/index.html
- JadeNB 2y ago> Yet all that separates the λ-calculus from one modern programming language, Haskell, is a layer of syntactic sugar on top, and a runtime that effectuates its pure IO actions. We can in fact compile Haskell programs using just stdin/stdout for IO into terms of the untyped lambda calculus, as wonderfully demonstrated in Ben Lynn's IOCCC entry [1]. That's what Turing completeness means, though; you can do the same thing with C, with the same provisos. (Conal Elliott has an amusing satire on this: http://conal.net/blog/posts/the-c-language-is-purely-functional http://conal.net/blog/posts/the-c-language-is-purely-functio... .) It's not that the lambda calculus isn't sufficiently expressive, just that it's not a language in which humans want to write.
- bjourne 2y agoDoes it handle alpha-renaming? Most of the golfed interpreters I've seen over the years does not and hence does not handle the full untyped lambda calculus.
- tromp 2y agoBinary Lambda Calculus uses de-Bruijn indices [1], thereby avoiding the need for alpha renaming. [1] https://en.wikipedia.org/wiki/De_Bruijn_index https://en.wikipedia.org/wiki/De_Bruijn_index
- deleted 2y ago[deleted]
- Joker_vD 2y agoDoes anyone have a gentle introduction on binary λ-calculus? I've tried reading other pages on this site but it goes a bit too fast for me understand what the hell is going on with it.
- shayansm1 2y agoI found this helpful https://brilliant.org/wiki/lambda-calculus/ https://brilliant.org/wiki/lambda-calculus/
- lucasoshiro 2y agoI don't know if it will work for you, but I wrote a Quicksort using lambda calculus in Python, and I explained the process of writing it here: https://lucasoshiro.github.io/software-en/2020-06-06-lambdasort/ https://lucasoshiro.github.io/software-en/2020-06-06-lambdas... Please note that I'm not an expert in lambda calculus, just a curious nerd and it won't explain everything, like the reductions, combinators and so on. But there I explain how to implement simple types (int, boolean, pairs and lists) using Church encoding, let expressions and recursion using the Y combinator (yay, I finally used the expression "Y combinator" on HN!). Everything that we need to implement a quicksort (which is a relatively complex algorithm) using the almost nothing that we have in lambda calculus. Another point is that it's all implemented in Python, using the Python notation instead of the lambda calculus notation, so you can run the code in your machine and play with the examples
- Joker_vD 2y agoSorry, I meant binary λ-calculus specifically. I can't quite wrap my head around what the hell it even does with its I/O.
- tromp 2y agoIf the IOCCC description [1] doesn't make it clear enough, perhaps this explanation [2] does it better? I also link to a Pi Day 2023 talk trying to explain it on my lambda playground page [3]. [1] https://www.ioccc.org/2012/tromp/ https://www.ioccc.org/2012/tromp/ [2] https://gist.github.com/tromp/86b3184f852f65bfb814e3ab0987d861 https://gist.github.com/tromp/86b3184f852f65bfb814e3ab0987d8... [3] https://tromp.github.io/cl/cl.html https://tromp.github.io/cl/cl.html
- stackghost 2y agoI feel like I've accidentally stumbled into /r/VXJunkies with some of the terminology being thrown around in here.
- dang 2y agoDiscussed at the time (but before it shrank): Lambda Calculus in 400 Bytes - https://news.ycombinator.com/item?id=30493713 https://news.ycombinator.com/item?id=30493713 - Feb 2022 (63 comments)
- jart 2y agoAuthor here. If anyone wants to see an example of an awesome program you can run on the 520 byte version of my lambda calculus virtual machine (Blc) then check out https://github.com/woodrush/lambdalisp https://github.com/woodrush/lambdalisp If you run the command in that project, it'll download my VM from the blog post, build a 20kb lambda expression you can pipe into it, and BOOM a fully object-oriented LISP REPL will appear in your terminal. It's like magic. For an example expression, try typing (+ 2 3) and hit enter. Then type (let ((a 2) (b 3)) (+ a b)) and hit enter. You need an x86 linux machine to do this right now.
- troad 2y agoJustine - thanks so much for all these amazing projects. You're an inspiration. One thing I saw you write recently is that chasing the newest fads is a distraction. That makes sense, but if you don't mind me asking, what do you think one should focus on instead? Which are the classic languages, tools, mindsets, and CS concepts that one must master?
- jart 2y agoHi troad, I read your book: https://justine.lol/sectorlisp2/troades.html https://justine.lol/sectorlisp2/troades.html I don't remember saying that. You might be thinking about https://justine.lol/ape.html https://justine.lol/ape.html where I said we should be focusing on the old things that matter which aren't going away, like UNIX magic numbers, C libraries, and computer science. But I've got nothing against the new. I think AI for example is exciting. Ultimately you should focus on whatever summons your passion and curiosity. Since if you're tapped into that divine energy within, then you can make anything work, and others will agree. Even if it's just boring old numbers.
- troad 2y agoYou're the first person to correctly recognise the nick as anything other than T + Road. Great answer! I appreciate it.
- deleted 2y ago[deleted]
- jsmo 2y agoMoar upboats plz!
- jkrubin 2y agoAnytime i see a Justine post it’s a banger — i had not read this one.
- kgeist 2y ago>nine="λλ [1 [1 [1 [1 [1 [1 [1 [1 [1 0]]]]]]]]]" Looks like Brainfuck in disguise :)
- octagen 2y agoVery interesting. Is it possible to imagine implementing an OS based on this ? I have been interested by lambda calculus for a while (implemented a lambda calculus interpreter in haskell) and was always wondering if people were working on "functional computers" and if it makes sense Cheers,