That 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."
> 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!
> 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!
"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.
It'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.
"Many people use it as a "hello world" program when learning a new language. Yet it took a decade+ to pop up."
I'm sure this was largely due to not many people even bothering to try to write such a program.
If Malbolge had as many users as, say, Java, I'm sure a hello world would have been written pretty quickly -- especially if these users were as motivated to write Malbolge programs as they are to write Java programs now.
Not to say that programming in Malbolge is not insanely hard, but I'm not convinced that a more difficult language would be impossible to program in.
Have any legendary programmers like John Carmack, Fabrice Bellard, Ken Thompson, Peter Norvig, Xavier Leroy, or Simon Peyton Jones spent much time trying to come up with Malbolge programs? I doubt it. If they did, would we have had a Malbolge hello world a lot sooner? Almost certainly.
One of the main difficulties of esoteric programming languages is getting people to actually spend any significant amount of time trying to program in them. Most people just don't care. Get them to care and there'll be a lot more programs written in them.
Esoteric programming languages are usually created to bend the boundaries of programming language design or prove something, not to be actually used to write software. It is hacker culture.
I 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.
I 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]
Lou 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.
Given 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.
You're free to run this with alternative Malbolge Unshackled interpreters to verify it (although you'd probably be better off using an optimised one, that fixes to some rotation width - otherwise the code will be orders of magnitude slower).
> 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.
For 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
There 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):
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
If 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!"
This 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.
Basically, 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 (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).
... maybe :). A while ago I published a writeup on programming in the Seed language (https://esolangs.org/wiki/Seed) and made the best Mersenne Twister cracking program to date (which is described, alongside source code on my website: https://palaiologos.rocks/posts/mersenne-twister/). It gained somewhat widespread popularity in esoteric-ish circles, but after I posted the writeup and revealed the source code I wrote, everyone seemed to have stopped caring.
Which is mainly why I'll never reveal how my Malbolge tooling exactly works - uncertainity is stronger than reason. Maybe because of the mindset people have that "if an explanation is published, it must be simple" paired together with "it's incredibly long and boring, so i'm not going to read it".
And indeed, there existed a small bug in my generator code, which was discovered after 1.5 years, because that's how long it took for someone to try reading and understanding the entire blog post...
A C compiler that can output Malbolge (among many other esolangs) can be found at 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."
>> 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.
> 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.
Also 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.
exactly, 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.
> 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.
Could you be a little bit less condescending? Simply don't upvote if you think this is trivial or crap content.
In any case this definitely feeds my intellectual curiosity. Even if it's indeed trivial to transpile between languages, I have zero idea how to go about that... and besides, I for one always love reading about Malbolge.
That 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)
Quoting 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.
The 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.
Why 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.
Malbolge 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).
Being 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.
Since you referred to the HN rules, i think your comments itself could fall under:
"Be kind. Don't be snarky. [...]"
(you could have phrased this like "i'd have preferred if the author didn't use clickbaity terms and instead used (...)")
"Please respond to the strongest plausible interpretation of what someone says, not a weaker one that's easier to criticize. Assume good faith."
(you interpreted the "impossible" as something done for attention grabbing, while it's quite clearly simply a shorter and more interesting way to say very difficult)
"Eschew flamebait. Avoid unrelated controversies and generic tangents."
HN limits post titles to 80 characters and your proposed title is 44 characters too long, so it's reasonable to abbreviate "often dubbed the hardest Turing-complete programming language" to something like "'impossible' language".
The title definitely does seem like click bait to me, as I went to the source and looked for where it said that and it does say that the Malbolge language (a Lisp dialect) is "almost impossible to use". Does that mean that Common Lisp is "impossible"? No, it doesn't, therefore that is why I think the title is click bait.
> 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.
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.