Lisp in an “impossible” language, the most complex Malbolge program to date

https://github.com/kspalaiologos/malbolge-lisp

by palaiologos • 5 years ago

263 73 5 years ago

github.com

linkfee• 5 years ago

Interesting deep-drive into this part of esolangs, I like the mathematic look on it

globular-toast2• 5 years ago

Why do I need to download a 7z file to view the source code?

palaiologos9• 5 years ago

The 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• 5 years ago

Git will compress the objects it stores, so checking in compressed objects is usually redundant.

globular-toast2• 5 years ago

Thanks for the answer. No thanks to the >= 3 people who decided to downvote my question.

razetime• 5 years ago

Obviously someone decided to program in a literal line noise language.

roywiggins• 5 years ago

The difficulty is less in the line noise and more that creating Malbolge programs is more of an exercise in cryptanalysis than programming.

masklinn2• 5 years ago

Looking like line noise is pretty standard for esolangs, especially amongst the brainfuck variants and functional turing tarpits (unlambda, jot).

capableweb• 5 years 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!

pmoriarty2• 5 years 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.

jerf2• 5 years ago

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.

daniel-thompson• 5 years ago

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.

Sharlin• 5 years ago

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]

[1] https://esolangs.org/wiki/Malbolge_programming

[2] http://www.lscheffer.com/malbolge.shtml

palaiologos9• 5 years ago

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.

Thomashuet• 5 years ago

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.

poizan42• 5 years ago

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."

palaiologos9• 5 years ago

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).

AndrewDucker3• 5 years ago

Does the "bf" stand "brainfuck", that being another ridiculously hard language?

jerf2• 5 years ago

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."

SIGBOVIK also take note.

bitwize• 5 years 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• 5 years ago

You know you’ve spent too much time in a chemistry lab when your brain tries to read OTOH as some molecule on first glance.

Causality12• 5 years ago

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.

palaiologos9• 5 years ago

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).

Causality12• 5 years ago

From the HN guidelines:

Otherwise please use the original title, unless it is misleading or linkbait; don't editorialize.

ElijahLynn3• 5 years ago

Would this title be an improvement?

Malbolge Lisp is an "almost impossible" language, ...

staticassertion• 5 years ago

It's in quotes, which I think is appropriate as Malboge is designed to be extremely cumbersome if not impossible to build practical programs in.

kibwen• 5 years ago

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".

lucrtz6• 5 years ago

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."

ElijahLynn3• 5 years ago

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.

lucrtz6• 5 years ago

Malbolge is most definitely not a lisp dialect.

srpablo• 5 years ago

Finally! A Lisp that lets me also interop with the Malbolge ecosystem!

jk jk, super cool

default-kramer• 5 years ago

From 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/10153849081921904...

qw3rty01• 5 years ago

They also made a colonel sanders dating sim: https://store.steampowered.com/app/1121910/I_Love_You_Colone...

spicybright• 5 years ago

Not to mention the marketing in the tv show Community! This was a very good episode too, surprisingly.

https://www.youtube.com/watch?v=CcjW6maPJko

chris_st• 5 years ago

Also worth a look, the KFConsole: https://landing.coolermaster.com/kfconsole/

aasasd3• 5 years ago

I 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• 5 years ago

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

xaedes• 5 years ago

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!"

aasasd3• 5 years ago

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):

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

Y_Y• 5 years ago

Counterfeit Monkey is downright incredible.

imtringued2• 5 years ago

Isn't Starbase [0] basically 0x10c?

[0] https://wiki.starbasegame.com/index.php/YOLOL

crystaln• 5 years ago

Why is there human attention focused on this at this point in time?

MonkeyClub• 5 years ago

Because not everyone is like Aesop's fox -- some grapes can be delicious indeed.

Jerrrry2• 5 years ago

transpiled, boring

lucrtz6• 5 years ago

what do you mean? it's a lisp interpreter, not a transpiler.

lucrtz6• 5 years ago

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.

ElijahLynn3• 5 years ago

This 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.

lucrtz6• 5 years ago

Yes 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• 5 years 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• 5 years ago

What a pointless endeavour

shaunxcode2• 5 years ago

pointless endeavor; a what?

YorickPeterse• 5 years ago

Yeah, how dare people have some fun trying to implement a Lisp in an esoteric language. They should be ashamed!

imtringued2• 5 years ago

From 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.

shaunxcode2• 5 years ago

lisp finds a way.

alphabet9000• 5 years ago

a special shout out to the (nonworking??) malbolge programs on http://c0d3.attorney

Lisp in an “impossible” language, the most complex Malbolge program to date

Related Stories