8 ms·
Lisp in an “impossible” language, the most complex Malbolge program to date
- linkfee 5y agoInteresting deep-drive into this part of esolangs, I like the mathematic look on it
- globular-toast 5y agoWhy do I need to download a 7z file to view the source code?
- palaiologos 5y agoThe source code is 150 megabytes, so you wouldn't be able to read it without downloading it either way. It compresses well (down to, if i remember correctly, 3 megabytes), so this is the preferred way of distributing the program.
- Null-Set 5y agoGit will compress the objects it stores, so checking in compressed objects is usually redundant.
- spijdar 5y agoThat may be so, but GitHub has an individual file limit of 100MB, and practically speaking, most people don't want/expect to open a 150 MB text file in their browsers, so I think this is a good compromise (though it might be worth being extra clear in the readme that the malbolge source is in the archive)
- palaiologos 5y agoQuoting the readme: > What is inside the zip file? > The release bundle includes interpreter binaries [...]. malbolgelisp-v1.1.mb is the source code for the interpreter.
- spijdar 5y agoThe way I parsed that when I first read it, I took it to mean that the filename of the lisp interpreter was "malbolgelisp-v1.1.mb" and was somewhere else in the repo, not in the 7zip archive with the interpreter binaries. I see what it means now, but the two ideas felt disjointed on my first reading.
- masklinn 5y ago> Git will compress the objects it stores Only when they get packed, and it doesn't exactly help when github will reject individual objects larger than 100MB inflated.
- globular-toast 5y agoThanks for the answer. No thanks to the >= 3 people who decided to downvote my question.
- razetime 5y agoObviously someone decided to program in a literal line noise language.
- roywiggins 5y agoThe difficulty is less in the line noise and more that creating Malbolge programs is more of an exercise in cryptanalysis than programming.
- masklinn 5y agoLooking like line noise is pretty standard for esolangs, especially amongst the brainfuck variants and functional turing tarpits (unlambda, jot).
- capableweb 5y ago> Malbolge Unshackled - Malbolge Unshackled is a dialect of Malbolge from 2007 by Ørjan Johansen. It attempts to remove the arbitrary memory limits of Malbolge in order to create a language that is hopefully Turing complete, while keeping closely to the spirit of Malbolge in most ways. > Malbolge - Malbolge, invented by Ben Olmstead in 1998, is an esoteric programming language designed to be as difficult to program in as possible. The first "Hello, world!" program written in it was produced by a Lisp program using a local beam search of the space of all possible programs. More practical programming methods have been found later. It is modelled as a virtual machine based on ternary digits. Seems like a lot of fun to try to program a lisp in these languages, although I'm nowhere near as crazy as the author to actually sit down and do it. Kudos author!
- pmoriarty 5y ago"an esoteric programming language designed to be as difficult to program in as possible" As difficult to program in as possible? It seems like it would be easy to make a language that is even more difficult to program in. For example, instead of storing only ternary numbers in memory, each subsequent memory address could store a number in a different base. Also, instead of having a static lookup table for the encryption, it could create a table based on its own program representation instead, resulting in a different lookup table for every program (while remaining deterministic). Speaking of determinism, all sorts of non-determinism could of course be easily added to the language, making it even harder to program. Naturally, all sorts of complex mathematical operations could be used instead of simple arithmetic operations as well... etc.. I'm sure it wouldn't be difficult for any creative programmer to tweak this language in many other ways to make it harder to program. In fact, after a certain language complexity is reached, I'm not sure how one would judge that one "extremely difficult" language is actually harder to program in than another, making the claim that a given language is "as difficult to program as possible" hard to prove.
- jerf 5y agoIt's no trick to make something so hard that it's impossible. It's riding the line that is interesting. Clearly, in the direction that Malbolge is hard, it is very nearly maximally hard. A LISP interpreter of this kind is, in general, not that hard. There are some conceptual challenges to implementation, but once your brain has absorbed those, it's not hard to implement. It's generally considered to be a good student project. Many people use it as a "hello world" program when learning a new language. Yet it took a decade+ to pop up. Much harder and you're not going to get anything, ever. Presumably, there are other directions that you could make programming hard in.
- daniel-thompson 5y agoI would like to know what techniques the author used to build the interpreter. Was it done by hand? Was it semi-automated? The reason I ask is, the Wikipedia article mentions the extreme difficulty of writing even a simple Hello World program (to the point where a brute-force automated search was required to "find" one).. a working Lisp interpreter seems to me to be many orders of magnitude more difficult than that.
- Sharlin 5y agoI believe writing Malbolge programs became easier (in a very relative sense) once Lou Scheffer published his cryptanalysis (!) of the language (specifically, the instruction encryption scheme) in 2004. [1][2] [1] https://esolangs.org/wiki/Malbolge_programming https://esolangs.org/wiki/Malbolge_programming [2] http://www.lscheffer.com/malbolge.shtml http://www.lscheffer.com/malbolge.shtml
- palaiologos 5y agoLou Scheffer's cryptanalysis is still fairly shallow. It seems like Lou themselves weren't too sure about Malbolge's capabilities (see below); their website remains mostly theoretical the entire time. > The day that someone writes, in Malbolge, a program that simply copies its input to it's output, is the day my hair spontaneously turns green. It's the day that elephants are purple and camels fly, and a cow can fit through a needle's eye.
- boomer_joe 5y agoGiven the amount of time people spent trying to implement something interesting in Malbolge (unshackled), I would also be very interested in a detailed explanation, perhaps a blog post, of how you achieved this. Otherwise I am inclined to believe that this must be the result of exploiting a loophole, perhaps the interpreter not implementing the malbolge specification or something.
- palaiologos 5y ago
- Thomashuet 5y agoThis interpreter was obviously not written by hand, the author has likely written a compiler from a sane language to malbolge and used it to obtain this result. It would be much more interesting to see the source for this compiler to malbolge or have an explanation of how it works.
- poizan42 5y agoA C compiler that can output Malbolge (among many other esolangs) can be found at https://github.com/shinh/elvm https://github.com/shinh/elvm - dunno if it has any relation to this work. Note that the Malbolge (or rather LMAO/HeLL) backend was added back in July 2019, so I'm not so sure about their claim that "It's as of 2020 and 2021, the most advanced, usable Malbolge program ever created."
- palaiologos 5y agoBasically, my toolchain is built on two separate projects. The first one is a low level assembler (that lays out code on instruction cycles, handles restoring things, etc.. - generally, very similar to how Malbolge works, except with the incredibly annoying parts such as manually encrypting the code or finding instruction cycles is), and the second one is a high level assembler. I used my existing project called asm2bf: https://github.com/kspalaiologos/asmbf https://github.com/kspalaiologos/asmbf (feel free to check it out), as a base for the high level assembler. And the original Lisp has been written in a tweaked version of it. Once I was done, I optimised the high level version, and then took the asm2bf compiler output and did a few optimisations manually on it (everything that my peephole optimisation didn't catch).
- deleted 5y ago[deleted]
- AndrewDucker 5y agoDoes the "bf" stand "brainfuck", that being another ridiculously hard language?
- 5y ago
- jerf 5y agoThat is like... ENIAC levels of performance. I want to say at least the interpreter has more RAM available to it than an ENIAC would, but I'm not sure enough of how malbolge works to be sure about that! On behalf of the HN gestalt, I award this program the official Hacker News Bloatiest Bloat award for 2021. HN commentators are now invited to derail the perennial bloat arguments with constant observations that "At least it's not as bloated as that Lisp interpreter written in Malbolge." SIGBOVIK also take note.
- bitwize 5y ago> HN commentators are now invited to derail the perennial bloat arguments with constant observations that "At least it's not as bloated as that Lisp interpreter written in Malbolge." OTOH, the Electron team now has a new KPI. Whoops, did I just say that out loud!
- suifbwish 5y agoYou know you’ve spent too much time in a chemistry lab when your brain tries to read OTOH as some molecule on first glance.
- Causality1 5y agoWhy add clickbait bullshit like "impossible" to the title? The article title is A lightweight (150MB) Lisp interpreter in Malbolge Unshackled, often dubbed the hardest turing complete programming language. That should be the submission title, per HN rules.
- palaiologos 5y agoMalbolge has been considered theoretically impossible to program for a longer time; a Lisp interpreter in Malbolge is a big breakthrough in Malbolge's history which proves that in reality, Malbolge isn't really "impossible" :) - hence I wouldn't call it a clickbait. Also, the title you proposed is exactly 45 bytes too long, so I couldn't submit it. In fact, many relatively credible places I've seen, like my national-language Wikipedia use the word "impossible" - I just want to break the myth :). BTW: In the rules, I can only see "Please don't do things to make titles stand out, like using uppercase or exclamation points, or saying how great an article is. It's implicit in submitting something that you think it's important." - I don't think my submissions breaks this rule (please let me know if it does!). To adress the other point, the original title/name is in the README (and it's MalbolgeLisp v1.1, or the repo name, as you wish - malbolge-lisp), not in the Github description. I felt like it's not descriptive enough and might be misleading (since you could interpret it as a malbolge interpeter _in_ lisp).
- Causality1 5y agoFrom the HN guidelines: Otherwise please use the original title, unless it is misleading or linkbait; don't editorialize.
- lucrtz 5y agoBeing a github project one could argue the title of the post should have been the repository description, which is too long for HN's limit, unless you expect people to change their repository descriptions just so they fit on hacker news i think it's fair to "editorialize" the title.
- ElijahLynn 5y ago
- srpablo 5y agoFinally! A Lisp that lets me also interop with the Malbolge ecosystem! jk jk, super cool
- default-kramer 5y agoFrom the linked Wikipedia article > In the soap opera General Hospital, Colonel Sanders of KFC makes a guest appearance because someone is trying to kill him to obtain the secret recipe of 11 herbs and spices. He knows Malbolge and is able to disarm the destruct sequence. I didn't realize General Hospital was willing to get this silly. Kudos to the KFC marketing team though; they do some outrageous stuff. https://twitter.com/generalhospital/status/1015384908192190464 https://twitter.com/generalhospital/status/10153849081921904...
- qw3rty01 5y agoThey also made a colonel sanders dating sim: https://store.steampowered.com/app/1121910/I_Love_You_Colonel_Sanders_A_Finger_Lickin_Good_Dating_Simulator/ https://store.steampowered.com/app/1121910/I_Love_You_Colone...
- spicybright 5y agoNot to mention the marketing in the tv show Community! This was a very good episode too, surprisingly. https://www.youtube.com/watch?v=CcjW6maPJko https://www.youtube.com/watch?v=CcjW6maPJko
- chris_st 5y agoAlso worth a look, the KFConsole: https://landing.coolermaster.com/kfconsole/ https://landing.coolermaster.com/kfconsole/
- aasasd 5y agoI mean, GH's first, and so far only, TV run is from April 1, 1963 to the present day. I guess they wanted to spice things up at some point.
- brundolf 5y agoFor years I've wanted a video game that lets you play the part of a wizard in the D&D sense: painstakingly decoding the threads of arcane reality, looking for ways they can be utilized. This always sort of felt adjacent to code, but of course code isn't very hard to figure out and being able to freely command the game world via anything like normal code would quickly become overpowered and uninteresting But now I'm imagining some sort of Malbolge-based magic system (ascii characters mapped to runic symbols for flavor, of course), where getting it to do the simplest of tasks really is an accomplishment
- xaedes 5y agoIf you are into this you might want to check out the Wizardry book series by Rick Cook: "It all began when the wizards of the White League were under attack by their opponents of the Black League and one of their most powerful members cast a spell to bring forth a mighty wizard to aid their cause. What the spell delivered was master hacker Walter "Wiz" Zumwalt. The wizard who cast the spell was dead and nobody— not the elves, not the dwarves, not even the dragons—could figure out what the shanghaied computer nerd was good for. But spells are a lot like computer programs, and, in spite of the Wiz's unprepossessing appearance, he was going to defeat the all-powerful Black League, win the love of a beautiful red-haired witch, and prove that when it comes to spells and sorcery, nobody but nobody can beat a Silicon Valley computer geek!"
- aasasd 5y agoThere are multiple text adventure games where you have to figure out the game's mechanics before you can do anything, and of course you can't just wave the mouse around and click on some targets. E.g. (I myself haven't gotten around to any of them): For a Change https://ifdb.org/viewgame?id=t61i5akczyblx2zd https://ifdb.org/viewgame?id=t61i5akczyblx2zd Bad Machine https://ifdb.org/viewgame?id=3a9rb059miw9fc9h https://ifdb.org/viewgame?id=3a9rb059miw9fc9h Counterfeit Monkey https://ifdb.org/viewgame?id=aearuuxv83plclpl https://ifdb.org/viewgame?id=aearuuxv83plclpl This is somewhat similar to the game 0x10c, where apparently a virtual computer was to be one of the central features, and you would use it to do advanced stuff. But, echoing your sentiment, the author said that it's not fun and dropped the project: https://en.wikipedia.org/wiki/0x10c https://en.wikipedia.org/wiki/0x10c
- crystaln 5y agoWhy is there human attention focused on this at this point in time?
- MonkeyClub 5y agoBecause not everyone is like Aesop's fox -- some grapes can be delicious indeed.
- Jerrrry 5y agotranspiled, boring
- lucrtz 5y agowhat do you mean? it's a lisp interpreter, not a transpiler.
- deleted 5y ago[deleted]
- lucrtz 5y agoAlso of course this was not written entirely by hand, but with a toolchain as the author says somewhere else, it's not exactly feasible to write this by hand.
- Jerrrry 5y agoexactly, but this audience knows anything can be trivially transpiled to any turing-complete language regardless of the "difficulty" of the language once basic operators are established. the entire sadistic point of the esoteric exercise is to dwell in the agony of unaccomplishment, not roll it up using a toolchain.
- yladiz 5y agoWho are you to be the gatekeeper of what is or isn't an acceptable way to use Malbolge, or any esoteric language?
- palaiologos 5y agoI think that you never touched Malbolge yourself. > anything can be trivially transpiled to any turing-complete language regardless of the "difficulty" of the language once basic operators are established Yes! It already was. There exists the Nagoya toolchain which I'm aware of, but it's generated code simply is too inefficient and unstable (from my testing) to be ran on contemporary machines. To write efficient Malbolge programs, like I just did, you'd need to implement a good chunk of "basic" operations in Malbolge (or, for the record, low level assembly which maps really well to Malbolge itself). > the entire sadistic point of the esoteric exercise is to dwell in the agony of unaccomplishment, not roll it up using a toolchain. It's easy to program assembly, it's hard to write a compiler that targets good assembly. As humans we've been striving to make good compilers for ages, yet still we're not even close. So, I'd say, the fact that I made it _using_ a toolchain makes it even more impressive. > this audience knows anything can be trivially transpiled to any turing-complete language This is the definition of Turing-completeness and I'd be surprised if this audience didn't know it. But I wouldn't be so sure about it being trivial. Two questions: 1) How do you "obviously" target cyclic tag systems and the Rule 110 automation? 2) How do you make it efficient? If we assume the simplest way of transpiling, we'll get nowhere near _actual usability_ (to some degree) which MalbolgeLisp exhibits.
- ElijahLynn 5y agoThis title seems misleading, the actual quote is: > Malbolge is a public domain esoteric programming language. It was specifically designed to be almost impossible to use, via a counter-intuitive 'crazy operation', trinary arithmetic, and self-modifying code.
- lucrtz 5y agoYes and as many other people have said in this thread, that's why impossible is between quotes. After all if it were truly impossible do you think someone could have written anything in it?
- YeGoblynQueenne 5y ago>> Do you want your code featured? Please open a pull request. I'll have to keep an eye on that repository. I would like to be the first to know when, inevitably, someone makes a pull request for a Malbolge Unshackled interpreter written in MalbolgeLisp.
- BlissWaves 5y agoWhat a pointless endeavour
- shaunxcode 5y agopointless endeavor; a what?
- YorickPeterse 5y agoYeah, how dare people have some fun trying to implement a Lisp in an esoteric language. They should be ashamed!
- imtringued 5y agoFrom an objective perspective everything is pointless. From a subjective perspective nothing is. The only thing I have to say is, enjoy not enjoying something someone else enjoys. i.e. the freedom to have differing preferences.
- shaunxcode 5y agolisp finds a way.
- alphabet9000 5y agoa special shout out to the (nonworking??) malbolge programs on http://c0d3.attorney http://c0d3.attorney