# Compiling Turpentine to Malbolge **Written, and bounded by the language rather than by us.** The backend is [`Langlib/Languages/Turpentine/Compile/Malbolge.lean`](../../Langlib/Languages/Turpentine/Compile/Malbolge.lean); its tests are in [`Langlib/Tests/CompileMalbolge.lean`](../../Langlib/Tests/CompileMalbolge.lean); the artifacts it produces live in [`Langlib/Examples/Malbolge/compiled/`](../../Langlib/Examples/Malbolge/compiled/) and are regenerated by [`scripts/gen-mal-examples.sh`](../../scripts/gen-mal-examples.sh). ``` lake exe turpentine compile --to malbolge -o out.mal prog.turp ``` This page used to say *not planned*, and gave a good reason. The reason is still good, and it is worth restating before anything else, because it is the shape of everything below. ## The bound is real, and it does not go away Malbolge has 59049 words of 59049 values, shared by code and data. That is a finite state space, which is why the language is not Turing complete — `Langlib/Computability/Malbolge/Main.lean` proves it — and it has a direct consequence for compilation: **no total translation from a Turing-complete source language into Malbolge can exist.** Any backend accepts a fragment, and the fragment is bounded by Malbolge's storage rather than by our effort or ingenuity. The old page concluded that a backend could therefore only ever be a demonstration, and that the work was not worth it. The first half is correct. What changed is the second: the demonstration turns out to be cheap, because a compiler that gives up on looping in the target buys itself an enormous simplification, and what it buys is enough to fit the whole of *99 bottles of beer* into the machine with 1535 words to spare. So this backend does not pretend to be total. It has one refusal nothing can lift, and it reports it in the only units that mean anything here: ``` the program prints 25592 bytes, and Malbolge does not have room for them. Its 59049 words hold a code row and a data row of equal length plus the prologue, which leaves 29157 cells of code -- enough for the first 15191 bytes. This is the language's bound and not the compiler's: Malbolge is finite, and no backend into it can be total. ``` Every other backend in LangLib refuses a program because of something we have not written yet. This one refuses because of Ben Olmstead. ## The trick: do not loop Three properties, all deliberate on Olmstead's part, defeat direct code generation: 1. **Executed code encrypts itself.** After the instruction at cell `c` runs, `mem[c]` is replaced through a fixed permutation. A cell means something different the second time control reaches it, so a naive loop executes different instructions on its second pass. 2. **Opcodes are position-dependent**: the instruction at `c` is `(mem[c] + c) mod 94`, so code is not relocatable. 3. **The data operations are hostile.** No addition; a ternary rotate-right (`rotR`) and the tritwise "crazy" operation (`crz`). The known way through all three is a **VM inside Malbolge**: hand-write an interpreter whose bytecode lives in *data* cells, which are never executed and so never encrypt. That is how every substantial Malbolge program has been produced, and it is a large project. This backend does something much lazier, and gets away with it because of the bound. **It never runs a cell twice.** Every instruction it emits is executed exactly once, in address order, and then never again — so property 1 costs nothing (who cares what a cell becomes if nothing reads it again?) and property 2 costs nothing either, because the assembler picks each cell's contents *after* it knows the address. Only property 3 is left, and it turns out to be soft. The price is that all control flow has to be settled before the target runs. So the backend runs the source program on Turpentine's own reference interpreter with an empty input stream, takes the byte string that comes out, and compiles **a straight-line program that prints exactly those bytes**. Loops, arrays, recursion, arithmetic and `assert` are all in the fragment — they are simply resolved at compile time. What is out is anything whose behaviour depends on the input stream, and the section [Why input is out](#why-input-is-out) says why that is not laziness either. ## Position independence is free The one thing hand-written Malbolge fights hardest is placement, and this compiler never feels it: > For every opcode `q` and every address `a` there is a printable word `w` > with `(w + a) mod 94 = q` — namely `(q - a) mod 94`, lifted into > `33..126` by adding 94 when it falls short. So **every instruction is available at every address**, and the code generator never has to move a gadget to suit its residue. `wordFor` is that one-liner. A hand-written cell has no such luxury, because it must also survive re-execution; nothing here does. ## The data channel is a byte The compiler feeds the crazy operation constants that it chooses. Those constants live in memory, so they have to be *loadable*, and Malbolge's loader has a famous oversight — [spec decision 5](spec.md#semantic-decisions-in-langlib) — that decides the whole cost model: * a source character in `33..126` is checked against its address and must decode to one of the eight opcodes: **8 values per address**; * a character outside that range is stored **unchecked**: any byte at all. That second line is the compiler's data channel, and it is the same one Lou Scheffer's cat program uses. Excluding NUL and the six bytes the loader skips as whitespace, it leaves **163 usable constants at every address**: 26 below 33, 8 printable, 129 above 126 — and the count is the same at every address, because the eight printable ones move but never change in number. 163 and not 59049, because a source character is a byte. That matters more than the count suggests. A byte occupies the bottom six trits of a ten-trit word, so **every constant this compiler can write has its top four trits zero** — and against a zero trit the crazy operation is the fixed map `0 ↦ 1, 1 ↦ 0, 2 ↦ 0`. The accumulator's top four trits are therefore not steerable at all. They alternate, and the compiler is only in charge of trits 0 to 5. That sounds fatal and is not, because of what the output instruction does. ## `out` writes `a mod 256`, and that is the whole cost model Malbolge's `<` writes the low byte of the accumulator. So the code generator never has to hit a *value* — it has to hit a **residue**, and 230 or 231 of the 59049 words end in any given byte (59049 is not a multiple of 256, so it depends on the byte). That is a target some 230 words wide, and against 163 candidate constants per step it is usually hit immediately. `planByte` is a shortest-path search over accumulator values with two kinds of move: `crz a k` for a constant `k`, and `rotR k`, which discards the accumulator entirely and is sometimes the cheapest way to land. Depths 0, 1 and 2 are open-coded and allocate nothing; past that there is a deduplicating breadth-first search, which is there for completeness and has never been needed: over the output of every Turpentine example in the tree, plus all 256 byte values in both directions, depth 2 has always sufficed. In practice, on the text of the song: | depth | what it means | share of bytes | |---|---|---| | 0 | the accumulator already ends in this byte — a repeat | 9% | | 1 | one crazy operation, or one rotation | 35% | | 2 | two | 56% | Add one cell for the `out` itself and a byte costs **about 2.5 cells of code**. A byte that repeats the one before it costs exactly one. ## The layout: two rows, and a rotation to separate them `c` and `d` advance together, one per instruction, always. So once they are a fixed distance apart they stay that way, and the image is two parallel rows: a **code row** that `c` walks and a **data row** that `d` walks beneath it, holding the constants. Code cell `codeBase + j` executes with `d` on `dataBase + j`. Getting them apart is the one genuinely awkward step, and it is awkward for a reason that does not arise in Malbolge Unshackled. Both pointers start at 0. To move `d` you need `movd`, which sets `d := mem[d]` — and `mem[d]` is a loaded cell, so it holds **at most 255**. No loaded cell can name an address in the data row. `rotR` is the way out. It is a *cyclic* rotation of the ten-trit word, so it does not make a number larger or smaller so much as move its trits around the circle — and rotating a byte carries its low trits over the top and manufactures a large value from a small one. Rotating 202 four times gives 29162. That is the whole prologue: | address | holds | effect | |---|---|---| | 0 | 40 (`movd`) | `d := mem[0] = 40`; both advance, so `c = 1`, `d = 41` | | 1 | 39 (`movd`) | `d := mem[41] = 30`; `c = 2`, `d = 31` | | 2 | 96 (`jmp`) | `c := mem[31] = 125`; `c = 126`, `d = 32` | | 31 | 125 | the jump target | | 32 | the seed | the cell that gets rotated into an address | | 33 | 31 | walks `d` back to 32 between rotations | | 41 | 30 | where the second `movd` sends `d` | Address 0 is forced: `movd` at address 0 *is* the word 40, so `d` lands on 40 and the second `movd` reads address 41 whatever else the compiler wants. From 126 the prologue alternates `rotr` at `d = 32` with a `movd` through address 33 that puts `d` back, as many times as the seed needs; two closing `movd`s then load the rotated value `V` into `d`. Execution reaches `codeBase = 127 + 2k` with `d` on `V + 1` and the accumulator holding `V`. The `jmp` at address 2 is what makes the rest possible. It moves `c` past addresses 3..125, so those cells are **never executed** and are free to hold data — without it, the rotation seed and the two pointers would have to double as instructions, and the arithmetic has no solution. `seeds` tabulates every `(V, w, k)` with `V = rotR^k w` for every seed `w` the loader will accept at address 32; ten rotations return a word to itself, so that table is the complete set of addresses this prologue can reach. The compiler picks the smallest one that fits, which is why a program printing 19 bytes emits 247 cells rather than 59049. ## Where the wall is The code row and the data row have the same length, because `d` advances whether or not the instruction reads memory — an `out` consumes a data cell and ignores it. So two words of memory go per word of code, and: > **`maxCodeRow = 29157`.** The longest code row Malbolge has room for, > squeezed between the prologue below it and the data row above, with the > data row's far end pressed against word 59048. At about 2.5 cells a byte that is **roughly 11 800 bytes of output**, and more when the text repeats itself: the refusal quoted at the top of this page fits 15 191 bytes of decimal digits into the same 29 157 cells, because digits recur and a repeat is free. *99 bottles of beer* is 11 459 bytes. It fits, with 1535 words of the machine unused: | artifact | output | code row | image | disk | steps to halt | |---|---|---|---|---|---| | `compiled/hello.mal` | 19 B | 50 | 247 | 257 | 74 | | `compiled/sort.mal` | 12 B | 25 | 197 | 203 | 45 | | `compiled/primes.mal` | 26 B | 52 | 251 | 265 | 72 | | `compiled/sieve.mal` | 41 B | 82 | 308 | 327 | 102 | | `compiled/99bottles.mal` | 11 459 B | 28 351 | 57 514 | 63 188 | 28 363 | That last row is the demonstration this page exists for. 57 514 of 59 049 words — 97.4% of the machine — and it halts in 28 363 cycles, one per code cell, because nothing runs twice. Iizawa et al.'s hand-written `99bottles.mal` does the same job in about fifteen *million* cycles and 22 561 instructions, because it has real loops and conditionals and this one has none at all. **The two print the same 11 459 bytes**, which `Langlib/Tests/CompileMalbolge.lean` checks by running both and comparing digests. The image is larger than the file on disk. Data cells above code point 126 are written as UTF-8, so they take two bytes each; our loader reads the file as text and sees one character per word, which is the same convention `scheffer-cat.mal` is stored under and is recorded in [the language README](../../Langlib/Languages/Malbolge/README.md). A byte-oriented reference interpreter reads such a file differently. ## Why input is out Not laziness, and not the bound either. It is the same obstruction that stops the Malbolge Unshackled backend, and it survives the removal of every size limit: **The crazy operation is tritwise.** A chain of them against compiled-in constants computes `resultᵢ = fᵢ(aᵢ)` — each output trit sees only the input trit at its own position. Such a chain can produce a *uniform* value, but never one that *depends* on the accumulator in a way a jump could read, since two inputs differing at one position agree at every other, while `...000` and `...222` differ everywhere. Branching on an unknown value needs an instruction that moves a trit between positions, and `rotr` is the only one; using it for that needs a cell that can be re-entered, which needs a loop, which is exactly what this backend gives up. `docs/malbolge-unshackled/compiler.md` works the argument through properly, and its `inputProbe` shows the one thing a straight line *can* do with an unknown byte: use it as an address and jump through a table. That mechanism transplants to Malbolge in principle. In practice its jump table would have to live in the first 128 words, every branch would have to start there too, and the whole thing would compete for the same 59 049 words the output already fills. It is not written. ## The fragment, in one list Accepted: every Turpentine program that * does not read input (`readInt`, `readByte`, and their indexed forms), * halts within `evalFuel = 500 000` statements when run on empty input, * does not trap or fail an assertion, and * prints little enough to fit. Not restricted at all: loops, `while`, arrays, `if`, short-circuit `&&` and `||`, division, modulo, negative numbers, `assert`. Those are resolved before Malbolge ever runs. One thing this backend can do that the Unshackled one cannot: **emit any byte**. Malbolge's `out` writes `a mod 256`, so bytes 128..255 are reachable; Unshackled's output is Unicode, and its backend has to refuse anything above 127. ## Trying it Compile the hello example and look at how little there is of it. ``` lake exe turpentine compile --to malbolge -o /tmp/hello.mal Langlib/Examples/Turpentine/hello.turp ``` Output (on stderr): ``` turpentine: wrote 247 bytes to /tmp/hello.mal [bespoke, hand-written and unverified] ``` Run the result on Malbolge's own interpreter. ``` lake exe malbolge /tmp/hello.mal ``` Output: ``` Hello, Turpentine! ``` Compile and run in one step, which is the differential test: the output must match `turpentine run` exactly. ``` lake exe turpentine exec --via malbolge Langlib/Examples/Turpentine/sieve.turp ``` Output: ``` 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 ``` The song, from the checked-in artifact. It halts on its own; no fuel bound is needed, because 28 363 cycles is nothing. ``` lake exe malbolge Langlib/Examples/Malbolge/compiled/99bottles.mal | tail -4 ``` Output: ``` 1 bottle of beer, Take one down, pass it around, No more bottles of beer on the wall. ``` Ask for more than the machine holds. First write a program that prints 25 592 bytes. ``` printf 'var i : int;\nwhile i < 3000 { println(i * 7919); i := i + 1; }\n' > /tmp/big.turp ``` Then compile it, and read the refusal. ``` lake exe turpentine compile --to malbolge -o /tmp/big.mal /tmp/big.turp ``` Output (on stderr, wrapped here): ``` turpentine compile: the program prints 25592 bytes, and Malbolge does not have room for them. Its 59049 words hold a code row and a data row of equal length plus the prologue, which leaves 29157 cells of code -- enough for the first 15191 bytes. This is the language's bound and not the compiler's: Malbolge is finite, and no backend into it can be total. See docs/malbolge/compiler.md. turpentine: nothing written to /tmp/big.mal ``` Regenerate every compiled example and verify each against its source. ``` scripts/gen-mal-examples.sh ``` Output: ``` hello.mal: 257 bytes on disk, output verified sieve.mal: 327 bytes on disk, output verified primes.mal: 265 bytes on disk, output verified sort.mal: 203 bytes on disk, output verified 99bottles.mal: 63188 bytes on disk, output verified ``` ## What would come next In rough order of how much they would buy: * **Input by jump table.** The `inputProbe` mechanism, ported. It would make `cat.turp` and the truth-machine compilable and would cost most of the low memory. * **A lookahead in `planByte`.** The search returns the first shortest path it finds; choosing *which* of the 230-odd landing values to stop on, with an eye on the next byte, should shave the depth-2 cases and buy perhaps 10% more output. * **Reusing data cells.** A `movd` can send `d` back over a stretch of the data row that has already been consumed. The values there are no longer the compiler's choice, but they are still *computable*, so a second pass could be planned against them. This is the only idea here that would move the ceiling rather than the constant, and it trades code cells for data cells at a bad rate. None of them changes the headline, which is that the ceiling exists. ## Credit The techniques this backend uses are elementary compared with the prior art, and the prior art is why anyone knows the language is programmable at all: **Lou Scheffer**'s cryptanalysis, and the loader oversight his cat program exploits, which is this compiler's data channel; **Hisashi Iizawa, Toshiki Sakabe, Masahiko Sakai, Keiichirou Kusakari and Naoki Nishida** (Nagoya, 2005), who published a programming method and an assembler and whose 99 bottles is the yardstick above; and **Matthias Lutter**, whose HeLL language and LMAO assembler produced the first Malbolge quine in 2012. Everything here is written from scratch. See `CONTRIBUTING.md` on respecting copyright. ## Turing completeness Settled and negative: 59049 words of 59049 values is finite, so the halting problem is decidable and Malbolge is not Turing complete (`Langlib/Computability/Malbolge/Main.lean`, and [docs/malbolge/computability.md](computability.md)). The bound is lifted by Lou Scheffer's Malbolge-T, in which a program may re-read its own output, and by Ørjan Johansen's Malbolge Unshackled (2007), which makes values and addresses unbounded. Unshackled is Turing complete — settled in 2020 by MalbolgeLisp — and LangLib implements it and compiles to it; see [docs/malbolge-unshackled/compiler.md](../malbolge-unshackled/compiler.md). That backend is the one with a future. This one has a ceiling, and the point of it is to show you exactly where the ceiling is.