Lisp in an “impossible” language, the most complex Malbolge program to date
github.com
github.com
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.
OTOH, the Electron team now has a new KPI. Whoops, did I just say that out loud!
> 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!
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.
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.
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.
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.
> 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.
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.
> 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/10153849081921904...
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
"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!"
E.g. (I myself haven't gotten around to any of them):
For a Change https://ifdb.org/viewgame?id=t61i5akczyblx2zd
Bad Machine https://ifdb.org/viewgame?id=3a9rb059miw9fc9h
Counterfeit Monkey 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
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."
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).
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...
jk jk, super cool
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.
After all if it were truly impossible do you think someone could have written anything in it?
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.
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.
It compresses well (down to, if i remember correctly, 3 megabytes), so this is the preferred way of distributing the program.
Only when they get packed, and it doesn't exactly help when github will reject individual objects larger than 100MB inflated.
The only thing I have to say is, enjoy not enjoying something someone else enjoys. i.e. the freedom to have differing preferences.
That should be the submission title, per HN rules.
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).
Otherwise please use the original title, unless it is misleading or linkbait; don't editorialize.
> Malbolge Lisp is an "almost impossible" language, ...
"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."
> 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.