Hacker News Reader

Comment by tromp | Hacker News Reader

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

View on HN

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

Reply on news.ycombinator.com