pyMalbolge

English | 中文

Write Python. Get a running Malbolge program.

pyMalbolge is a pure-Python compiler from a subset of Python to Malbolge20, bundled with interpreters for both Malbolge variants and a full-featured debugger. No C++, flex, bison or Perl build dependencies — pip install malbolge and the whole toolchain is there.

def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

putchar(48 + fib(6))

$ python3 -m malbolge compile fib.py --backend=direct -o fib.mb
$ python3 -m malbolge --variant=malbolge20 fib.mb
8

Malbolge was designed in 1998 by Ben Olmstead to be as close to unprogrammable as a language can get: every instruction is self-modifying, the opcode depends on the instruction's own address, and arithmetic is a lookup-table "crazy" operation on ternary digits. The first Malbolge program was not written but found, by beam search, two years after the language appeared. This project is about the other end of that history — compiling ordinary code into it.

• Compiler — Python subset → Malbolge20, two independent backends, fully deterministic output
• Interpreters — original Malbolge (10 trits) and Malbolge20 (20 trits, sparse memory)
• Debugger — breakpoints, watchpoints, step-back, memory inspection, disassembly; CLI and TUI
• Verified — the toolchain ports are byte-exact against the reference C++/Perl tools; 441 tests
• Zero runtime dependencies — textual only if you want the TUI debugger

Installation

pip install malbolge          # compiler + interpreters + CLI debugger
pip install malbolge[tui]     # adds the TUI debugger (textual)

Requires Python 3.8+.

Compiling Python to Malbolge20

Command line

# Compile and run
python3 -m malbolge compile examples/hello.py -o hello.mb
python3 -m malbolge --variant=malbolge20 hello.mb

# Direct backend: skips the C layer, roughly half the output size on
# programs with control flow or functions, native double recursion
python3 -m malbolge compile examples/fib.py --backend=direct -o fib.mb

# Dump the intermediate stages
python3 -m malbolge compile prog.py --emit-c prog.c --emit-mg prog.mg --emit-mc prog.mc

Python API

from malbolge.compiler import compile_python_to_mb
from malbolge import eval20

mb = compile_python_to_mb('print("Hello, world!")')                   # 'c' backend
mb = compile_python_to_mb('print("Hello, world!")', backend="direct") # direct backend
print(eval20(mb))                                                     # Hello, world!

# Every stage is exposed individually:
from malbolge.compiler import (
    compile_python_to_c,    # Python subset -> Nagoya C subset
    compile_python_to_mg,   # Python subset -> .mg          (direct backend)
    translate_mg_to_mc,     # .mg -> .mc (LAL)              (port of nagoya-ternary)
    assemble_mc_to_mb,      # .mc -> .mb (Malbolge20)       (port of nagoya-lowass)
)

Supported Python subset (v1)

Accepted: int variables and arithmetic (+ - * // %, constant-folded mod 3^20), while / if / elif / else, for i in range(...), break / continue, chained comparisons, short-circuit and / or / not, conditional expressions (a if c else b, lazily evaluated), function definitions and calls including mutual recursion, global, putchar() / getchar() I/O, ord(), and print() with compile-time-constant arguments (string literals, constant ints, all-constant f-strings, sep= / end=). Docstrings are tolerated.

Rejected, with line-numbered CompileErrors: negative literals and unary minus (the value ring is unsigned mod 3^20), true division, runtime-valued print() arguments, chr, runtime strings and f-strings, floats, bool, lists / dicts / sets, classes, import, lambda, comprehensions, nested functions, tuple unpacking and keyword arguments.

The normative specification covers the accepted-AST whitelist, all seventeen documented divergences from CPython semantics, and the diagnostic contract.

How the pipeline works

             py2c                c2mg            mg2mc            mc2mb
Python  ──────────► Nagoya C ──────────► .mg ──────────► .mc ──────────► .mb
subset      │        subset             pseudo-        LAL low-      Malbolge20
            │                            instrs         level asm
            └──────────────────────────►
                  py2mg (direct backend)

Every port is checked byte-for-byte against the original tools on a fixture corpus, and the two front-ends are cross-checked end to end: the same source compiled through both backends must produce identical program output.

Compared to the Nagoya toolchain

Obfuscation was a design goal upstream — the pseudo-instruction layer is supposed to emit something different each time. Trading that for determinism is what makes reproducible builds and byte-exact conformance testing possible, and it is the one place where this project deliberately diverges from the original behaviour rather than reproducing it.

Performance

Malbolge20 has no instructions in the usual sense. Addition alone is a twenty-step loop over ternary digits, every cell rewrites itself after being executed, and control flow is carried in a register. Compiled programs are therefore enormous relative to their source and run slowly — this is inherent to the target, not an artifact of this implementation.

Measured on an M-series Mac, CPython 3.9:

Output size. The direct backend is no help on straight-line code — the two hello builds differ by under a kilobyte — but roughly halves anything with control flow or function calls. Size is driven by call sites and loops, not by the input's numeric values: a bootstrap of about 91 KB plus a few hundred KB per putchar call site is typical.

Compilation is dominated by the final assembly stage, which runs at roughly 0.5 s per MB of output and is effectively linear in it. It did not start that way: the address search in mc2mb was recursing without memoization, which made assembly superlinear at about 40 s/MB and turned multi-MB programs into multi-minute builds. Caching that search on (d, pos, depth) made it about 100x faster with byte-identical output.

Execution runs at roughly 240,000–320,000 instructions per second under CPython, measured end to end including startup and parsing the .mb. The debugger is another 2–2.4x slower, because step-back records execution history. Wall-clock time is superlinear in recursion depth even though .mb size is not — deep recursion touches more of the address space, and the sparse memory materializes blocks lazily as it goes.

Practically: small programs are fine, and anything with real recursion is a patience exercise. Both are expected.

Against the reference toolchain

Compiling the same print("Hello, world!") — identical C input, identical .mg and .mc intermediates — through the Nagoya tools and through this port:

The Python port is about 2x faster end to end, which is not a statement about Python. Assembly dominates the pipeline, and its inner address search is memoized here and is not upstream — the same change that took this stage from roughly 40 s/MB to 0.5 s/MB. Everything else is fast enough that the language gap never shows up.

Both toolchains emit exactly 3,467,473 bytes. About 69% of those bytes differ, and all of them are padding: cells the program never executes, which upstream fills from srand(time(NULL)) and this port fills deterministically. The two binaries behave identically, and each one runs correctly on the other project's interpreter.

Where the reference implementation does win decisively is execution. On the same .mb:

That is a 19x gap, and it is the honest reason the end-to-end tests reach for ref/nagoya-malbolge20-interpreter when it is available. If you are running large compiled programs rather than debugging them, use the C interpreter; if you want breakpoints, step-back and a memory view, use this one.

Running Malbolge programs

python3 -m malbolge hello.mal                        # original Malbolge
python3 -m malbolge --variant=malbolge20 program.mb  # Malbolge20
python3 -m malbolge cat.mal -i "Hello World"         # feed stdin

from malbolge import eval, eval20

eval('''(=<`#9]~6ZY32Vx/4Rs+0No-&Jk)"Fh}|Bcy?`=*z]Kw%oG4UUS0/@-ejc(:'8dc''')
# 'Hello World!'

eval('''(=BA#9"=<;:3y7x54-21q/p-,+*)"!h%B0/.~P<<:(8&66#"!~}|{zyxwvugJ%''', "abc123")
# 'abc123'

eval20(malbolge20_source, input_data)

Malbolge20 is not backward compatible. Its crazy() operates on 20 trits and produces different results than the 10-trit original, so programs written for one variant will not run correctly on the other.

Debugger

python3 -m malbolge debug hello.mal                     # CLI, GDB-like
python3 -m malbolge debug --tui hello.mal               # TUI (needs textual)
python3 -m malbolge debug --variant=malbolge20 prog.mb

(maldbg) break 10       # Set breakpoint at address 10
(maldbg) run            # Run until breakpoint
(maldbg) step 5         # Step 5 instructions
(maldbg) back 2         # Step back 2 instructions
(maldbg) examine 0 20   # Examine memory at address 0
(maldbg) disassemble    # Show disassembly
(maldbg) registers      # Show register values

TUI keys: ↓ step, ↑ step back, r run, b toggle breakpoint, ←/→ scroll memory, 0 recentre on D, h/? help, q quit.

from malbolge import MalbolgeDebugger
from malbolge.core import MalbolgeConfig

dbg = MalbolgeDebugger(source, input_data, config=MalbolgeConfig.malbolge20())
dbg.add_breakpoint(10)
state = dbg.step()       # one instruction
state = dbg.step_back()  # undo it
state = dbg.run()        # until the next breakpoint
print(dbg.registers, dbg.output)
print(dbg.disassemble(0, 10))

The Malbolge landscape

Malbolge programming has followed two largely separate lines, and this project sits at the end of the second one.

Search, then hand-assembly (original Malbolge). For years programs were generated rather than written: Andrew Cooke's 2000 hello world came out of a beam search, and Lou Scheffer's cryptanalysis — which found the 2-cycle in the encryption table and showed systematic programming was possible at all — is still the foundation everything else rests on. Because the original variant has only 59,049 memory cells, printing fixed text remains the practical ceiling for generators such as zb3/malbolge-tools. Matthias Lutter's HeLL assembly language and its LMAO assembler (GPL-3) lifted that line to something writable by hand, and LMFAO targets Malbolge Unshackled, Ørjan Johansen's Turing-complete unbounded-memory variant. The most complex Malbolge program in existence, Kamila Szewczyk's MalbolgeLISP — a LISP interpreter of roughly 350 MB — was hand-written in that dialect.

Compilation (Malbolge20). Nagoya University worked the problem from the other direction across roughly a decade, publishing on Turing-completeness, SAT-assisted synthesis of trit-wise operations, and code-allocation decision procedures, and in 2013 introducing Malbolge20: a 20-trit variant whose larger word and address space make a real compiler feasible. Their toolchain (MIT-licensed) is a three-stage descent — a C subset compiles to a pseudo-instruction language, which lowers to the LAL low-level assembler, which assembles to Malbolge20. Notably, the pseudo-instruction layer treats obfuscation as a feature: the same input is meant to produce different output on each compile.

What this project adds. The Nagoya stack is C++/flex/bison/Perl and needs a local build; its last commit was in 2021. pyMalbolge reimplements all three stages in pure Python, verified byte-for-byte against the originals, and puts a Python front end on top — including *, // and %, which the upstream C subset does not have, plus for-loops, chained comparisons, short-circuit booleans and line-numbered diagnostics. The direct backend bypasses the C layer entirely. Output is made deterministic rather than obfuscated, which is what makes reproducible builds and byte-exact conformance testing possible in the first place. Alongside that, it is a maintained modern runtime for both variants with a real debugger.

Documentation

Design notes and reverse-engineered language specifications live in docs/. Every document exists in English (<name>.md) and Chinese (<name>.zh.md).

• python-subset-spec — normative spec for the accepted Python subset
• py2mg-backend — design of the direct py → .mg backend
• highlevel-to-malbolge — why the pipeline looks like this
• mg-spec — the .mg pseudo-instruction language, reverse-engineered from ternary
• hell-spec / lmao-internals — HeLL and the LMAO assembler's algorithms
• perf-baseline — profiling and the two hotspots that were fixed
• toolchain-guide — building the reference tools, for conformance work

Development

pip install -e .[dev]
python3 -m pytest test/           # 441 tests
python3 -m pytest test/ -n auto   # ~2.6x faster with pytest-xdist

The reference tools under ref/ are optional. When present, the end-to-end tests build through them for speed and cross-check the results; when absent, everything falls back to the pure-Python pipeline.

Roadmap

• Malbolge20 variant support (20 trits, sparse memory)
• Debugger (CLI + TUI, with step-back)
• Pure-Python port of the full Nagoya toolchain, byte-exact
• Python front end, plus a direct py → .mg backend
• Compiler v2: signed integers, decimal print() / input(), arrays and strings via IND_OPR
• Malbolge Unshackled support (3-adic integers, variable rotation width, Unicode I/O)

References

The language

• Malbolge — Esolang · Wikipedia
• Malbolge Unshackled — Esolang — the Turing-complete variant
• Lou Scheffer, Introduction to Malbolge — the cryptanalysis that made programming possible

Malbolge20 and the Nagoya toolchain (MIT)

• Project page — papers, online assemblers and interpreter
• Toolchain sources — highlevel (C subset → .mg), ternary (.mg → LAL), lowass (LAL → Malbolge20), and the reference interpreter. Mirrored under ref/ here for conformance testing only.
• Kato et al. (2013), Malbolge with 20trits word length and its programming support tool, IEICE — introduces Malbolge20
• Kanbe et al. (2016), An intermediate language for a compiler generating highly obfuscated Malbolge codes, IEICE SS2016 — the .mg layer
• Sakanashi et al. (2017), A compiler that translates to Malbolge from a C-language subset containing recursive calls, IEICE SS2017-18 — the C front end

HeLL / LMAO line (GPL-3)

• lutter.cc/malbolge — HeLL, LMAO, LMFAO, HeLL-IDE and online tools
• MalbolgeLISP — a LISP interpreter running on Malbolge Unshackled

Generators

• zb3/malbolge-tools — three generation strategies plus a web GUI
• lutter.cc/unshackled — Unshackled reference implementation

This project

• Started as a fork of Avantgarde95/pyMalbolge. The interpreter has since been rewritten from scratch and none of the original source remains; the .mal examples and Ben Olmstead's public-domain reference interpreter under ref/ are all that carried over.

License

MIT. The HeLL fixtures under test/fixtures/hell/ come from the GPL-3 LMAO distribution and carry their own notice; they are used for conformance testing only and are not part of the shipped package.