A lightweight Lisp interpreter in Malbolge | Hacker News Reader

A lightweight Lisp interpreter in Malbolge

github.com

114 pointsnoteness20 comments

Some rather full featured LISP interpreter has already been implemented in 163654 bits (under 20KB) of binary lambda calculus [1] (previous HN discussion at [2]). Wouldn't it be far simpler to implement binary lambda calculus in Malbolge and obtain a LISP interpreter running on Malbolge that way?

[1] https://woodrush.github.io/blog/lambdalisp.html

[2] https://news.ycombinator.com/item?id=32879848

Perusing the author's about page [1], I see that after making malbolge-lisp in 2020-2021, in 2022 she made blc-mb [2], a Binary Lambda Calculus evaluation engine written in Malbolge. So now the simpler implementation path is available too. But the BLC engine is still a whopping 46MB! This is what the first 320 bytes of its Malbolge code looks like:

    bCBA@?>=<;:9876543210/.-,I*)(E~%$#"RQ}={
    zyxwvutsrD0|nQl,+*)(f%dF"a3_^]\[ZYXWVUTS
    RQJmNMLKJIHGFEDCBA@?>=<;:9876543210/.-,+
    *)('&%$#dc~}|_^yrwZutsrqpinPlOjihgf_dcEa
    D_^]\UZYX:V9TSRQPONGLK.IHGF?DCB$@#>=<;49
    87w/v3210/.-,+$k('&%|#"!~w`{zyxwputslUpo
    nmlkjiKgf_Hcba`_^]\[ZYXWP9TSRQPONMFKJCHA
    *EDCBA@?>=<|:98y6543210).-,%*#j'&%$#"!~}

I'd love to hear about the tools used to construct this monster of code. My hat off to this programming wizard! Btw, it's shocking to see how much better bzip3 by this same author [3] compresses than bzip2:

     46M blc.mb
    1.6M blc.mb.bz2
    1004K blc.mb.bz3

[1] https://palaiologos.rocks/about/

[2] https://github.com/kspalaiologos/blc-mb

[3] https://news.ycombinator.com/item?id=31324439

Thank you for the kind comments! Unfortunately, the BLC interpreter is much slower than MalbolgeLISP, even when using fast20 (with a lot of optimisations coined by dzaima). My memory is a bit hazy, but one of the main roadblocks that made BLC barely feasible was the (comparably...) large ROM that it requires. Executing simple instructions in Malbolge generally incurs similar kind of latency as the more complicated ones, hence to slightly improve performance (not nearly enough - notice that the Lisp still has a "loading bar"!), I have decided that a complicated set of primitives for a language to run on top of Malbolge would be a necessity. This is further supported by some issues with Malbolge regarding the code placement and loading a code image, previously solved by e.g. Matthias Lutter (and subsequently used in my Malbolge code) in his very simple (and if I remember correctly, slower than the LISP) brainfuck interpreter. Another venue to explore is University of Nagoya's Malbolge toolchain, which is functional and probably a very good starting point - https://www.trs.css.i.nagoya-u.ac.jp/projects/Malbolge/. Once you jump this hoop, you can now start synthesizing basic operations using Nop/MovD;Jmp flags and Malbolge instructions - e.g. have the interpreter code set a flag, jump to a single routine which does a complex operation; based on the state of all flags the routine can then decide where to return. The more complex the instruction set, the more complex the primitive operations, and hence the better is the performance you may get. Assuming that you do not exactly want to write an optimising compiler in Malbolge which does something akin to mop-fusion of RISC CPUs, of course :-). Most of MalbolgeLisp was written when I was 16, then I have moved onto KamilaLisp (Java), as the codebase written in Malbolge grew in size and became more annoying to add interesting features to. Unfortunately due to job and university requirements I no longer have the time (and motivation) for these kinds of amusement.

As for the compression: probably an artifact of a bigger block size and a closer-to-optimal entropy coding stage in bzip3 (simple model + binary arithmetic coding; fast suffix sorting due to research of Ilya Grebnov) vs bzip2's suboptimal implementation of what could have been Package-Merge that currently assigns excessively long Huffman codes (as I discovered while doing research for my data compression book); also probably the RLEs everywhere that Seward considers a mistake, small BWT blocks, etc. You could try the tool https://pastebin.com/6DUKs4q9, which eliminates the redundancy associated with the Malbolge encoding (which bzip3 kind of catches on without any preprocessing, while bzip2 not entirely) and drastically improves performance of all other compressors:

    % ./a d <blc.mb >blc.n
    % bzip3 -vfb50 blc.n
      blc.n:  48175489 -> 647179 bytes, 1.34%, 0.11 bpb
    % bzip3 -vfb50 blc.mb
      blc.mb: 48175489 -> 1025582 bytes, 2.13%, 0.17 bpb

You're right; performance of the current blc runtimes leaves much to be desired. I'm hoping to rectify this in the future with a combinator based runtime in the style of the ION machine [1]. But that provides only limited relief when you're still partly bound by the shackles of Malbolge.

[1] https://crypto.stanford.edu/~blynn/compiler/ION.html

The Lisp-Malbolge relationship is complicated. Quoting Malbolge wikipedia page:

"The first program was not written by a human being; it was generated by a beam search algorithm designed by Andrew Cooke and implemented in Lisp"

So now Malbolge repays the favor by implementing a Lisp interpreter.

If one takes the "19yo" claim at face value, this is a prodigious feat.

I think this is a prodigious feat at any age. I remember trying to write Hello World in Malbolge as a teen, I think I was able to do "He".

Obscene stuff like this seems perfect for the young. Not quite at the same level, but I wrote a custom tiling GUI in befunge when I was 19 (well, the befunge program output draw instructions which were rendered by a traditional C program).

Now, 19 years of professional software engineering later, I don't think my actual code-outputting skills are much better than they were at 19 - all I have now is more knowledge about the process and human side of software engineering and some extra esoteric facts and histories stored in my head. In fact, maybe I'm even worse, because I wouldn't have the time or patience to actually sit down and write something like that in befunge any more, because my priorities have changed.

Yeah, I can kind of relate, actually! Now I am 19, have a job and attend a somewhat demanding university, outside of (more useful?) real world research I am currently doing. I wrote the code when i was c.a. 15 - 16, I could definitely improve upon my Lisp - it's within my range of current capabilities, but I would not have the motivation to :-).

She has also developed KamilaLisp with many APL-derived features:

https://github.com/kspalaiologos/kamilalisp

Lisp in an “impossible” language, the most complex Malbolge program to date - https://news.ycombinator.com/item?id=28048072 - Aug 2021 (73 comments)

While I'm at it:

Malbolge - A programming language designed to be almost impossible to use - https://news.ycombinator.com/item?id=37863289 - Oct 2023 (2 comments)

Malbolge - https://news.ycombinator.com/item?id=37854603 - Oct 2023 (3 comments)

KFC Mascot Col. Sanders Talks Malbolge Programming on General Hospital - https://news.ycombinator.com/item?id=25835971 - Jan 2021 (83 comments, and yes this is real)

Malbolge: Intentionally difficult to reason about esoteric language - https://news.ycombinator.com/item?id=24549737 - Sept 2020 (1 comment)

A visualization of Malbolge programs, try playing with the m parameter - https://news.ycombinator.com/item?id=18849392 - Jan 2019 (1 comment)

Malbolge: Esoteric Programming Language - https://news.ycombinator.com/item?id=10559814 - Nov 2015 (1 comment)

Show HN: Web based interactive Malbolge interpreter, generator and a crackme - https://news.ycombinator.com/item?id=9478038 - May 2015 (1 comment)

Malbolge - https://news.ycombinator.com/item?id=7051732 - Jan 2014 (1 comment)

Malbolge (programming language) - https://news.ycombinator.com/item?id=4042148 - May 2012 (16 comments)

Malbolge - https://news.ycombinator.com/item?id=920546 - Nov 2009 (1 comment)

The peculiarity of Malbolge is that it was designed to be the worst possible programming language - https://news.ycombinator.com/item?id=162096 - April 2008 (3 comments)

At 19 she says she is "an expert programmer", but in the words of pitcher Dizzy Dean, "It Ain't Braggin' If You Can Back It Up". Her github looks like she's backing it up.

All you startups hanging out on here, shouldn't you be hiring her?

She indeed worked as an intern at Dyalog last summer [1].

[1] https://www.dyalog.com/blog/2023/10/dyalog-23-day-5-the-end-...

lightweight (350MB)

I see the author considers this a competitor to Electron. </s>

I love how he has chosen GPLv3 considering this code is never going to be reused with different autorship

She : https://github.com/kspalaiologos

Is this the computer equivalent of carving "Killroy was here " into Mona Lisa?

No, it's more like using a million dickbutts in different colors as pixels to make a Mona Lisa copy.

if they're animated gifs, I'd like to commission one, it would make my smile more enigmatic

Wow! I'm impressed. It wouldn't surprise me if you need medical and psychological help after this feat!

Reply on news.ycombinator.com