[HN Gopher] Lisp in an "impossible" language, the most complex M...
___________________________________________________________________
Lisp in an "impossible" language, the most complex Malbolge program
to date
Author : palaiologos
Score : 212 points
Date : 2021-08-03 11:44 UTC (1 days ago)
(HTM) web link (github.com)
(TXT) w3m dump (github.com)
| Thomashuet wrote:
| 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 wrote:
| 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."
| palaiologos wrote:
| 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).
| [deleted]
| linkfee wrote:
| Interesting deep-drive into this part of esolangs, I like the
| mathematic look on it
| Jerrrry wrote:
| transpiled, boring
| lucrtz wrote:
| what do you mean? it's a lisp interpreter, not a transpiler.
| [deleted]
| lucrtz wrote:
| 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.
| Jerrrry wrote:
| 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.
| palaiologos wrote:
| I 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.
| yladiz wrote:
| Who are you to be the gatekeeper of what is or isn't an
| acceptable way to use Malbolge, or any esoteric language?
| isoprophlex wrote:
| 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.
| srpablo wrote:
| Finally! A Lisp that lets me also interop with the Malbolge
| ecosystem!
|
| jk jk, super cool
| razetime wrote:
| _Obviously_ someone decided to program in a literal line noise
| language.
| roywiggins wrote:
| The difficulty is less in the line noise and more that creating
| Malbolge programs is more of an exercise in cryptanalysis than
| programming.
| masklinn wrote:
| Looking like line noise is pretty standard for esolangs,
| especially amongst the brainfuck variants and functional turing
| tarpits (unlambda, jot).
| default-kramer wrote:
| 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...
| aasasd wrote:
| 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.
| chris_st wrote:
| Also worth a look, the KFConsole:
| https://landing.coolermaster.com/kfconsole/
| qw3rty01 wrote:
| They also made a colonel sanders dating sim:
| https://store.steampowered.com/app/1121910/I_Love_You_Colone...
| spicybright wrote:
| 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
| YeGoblynQueenne wrote:
| >> 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.
| jerf wrote:
| 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 wrote:
| > 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!
| brundolf wrote:
| 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
| aasasd wrote:
| 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
| xaedes wrote:
| 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!"
| capableweb wrote:
| > Malbolge Unshackled - Malbolge Unshackled is a dialect of
| Malbolge from 2007 by Orjan 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 wrote:
| _" 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 wrote:
| 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.
| pmoriarty wrote:
| _" 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.
| ollran wrote:
| 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.
| crystaln wrote:
| Why is there human attention focused on this at this point in
| time?
| daniel-thompson wrote:
| 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 wrote:
| 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
| palaiologos wrote:
| 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.
| boomer_joe wrote:
| 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.
| palaiologos wrote:
| 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).
| Causality1 wrote:
| 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.
| ElijahLynn wrote:
| 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.
| staticassertion wrote:
| 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 wrote:
| 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".
| lucrtz wrote:
| 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."
| palaiologos wrote:
| 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).
| ElijahLynn wrote:
| Would this title be an improvement?
|
| > Malbolge Lisp is an "almost impossible" language, ...
| Causality1 wrote:
| From the HN guidelines:
|
| _Otherwise please use the original title, unless it is
| misleading or linkbait; don 't editorialize._
| lucrtz wrote:
| 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.
| BlissWaves wrote:
| What a pointless endeavour
| shaunxcode wrote:
| pointless endeavor; a what?
| YorickPeterse wrote:
| Yeah, how dare people have some fun trying to implement a Lisp
| in an esoteric language. They should be ashamed!
| shaunxcode wrote:
| lisp finds a way.
| globular-toast wrote:
| Why do I need to download a 7z file to view the source code?
| palaiologos wrote:
| 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 wrote:
| Git will compress the objects it stores, so checking in
| compressed objects is usually redundant.
| spijdar wrote:
| 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)
| palaiologos wrote:
| 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.
| spijdar wrote:
| 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.
| masklinn wrote:
| > 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 wrote:
| Thanks for the answer. No thanks to the >= 3 people who
| decided to downvote my question.
| ElijahLynn wrote:
| 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.
| lucrtz wrote:
| 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?
___________________________________________________________________
(page generated 2021-08-04 23:01 UTC)