A Python Interpreter in 1024 Bytes of Pure C

Austin Henley spends his weekends writing code by hand — “to feel human.” His latest challenge to himself: cram a Python interpreter into 512 bytes of good old C, with no macros and no library tricks. The 512-byte bar turned out to be out of reach, so he raised it to 1024.

The goal isn't to support the whole language, but to make something that convincingly looks like Python. FizzBuzz serves as the benchmark: it has def, colons, indentation, and if without parentheses. It looks like Python — and that's enough.

How it works

Real CPython tokenizes the source, builds a syntax tree, optimizes, generates bytecode, and executes it. There's none of that here. The state is held in a handful of global variables, the entire program text sits in a fixed-length array, and variable names are limited to a single lowercase letter — which lets you index into the symbol table directly.

Expressions are parsed by ordinary recursive descent and evaluated on the fly as they're parsed. There's no error handling whatsoever: the interpreter blindly trusts that the code is correct, doesn't even check that keywords are spelled right, and simply “skips over” the requisite number of characters. Loops, since nothing is compiled, work by re-parsing the source: after the body, the parser jumps back to the condition. Functions work the same way — the position of the body is remembered, and the caller's address is saved and restored on return. The author notes with some pride just how much can be done with no intermediate representation at all.

Byte golfing

Trimming names and whitespace is the obvious move, but the big savings came from tricks off “an ancient, forgotten Stack Overflow site,” where, in the author's words, “the code wizards of the past shared their knowledge.” Into play went the quirks of GNU C89: implicit int type, zero-initialization of globals, function parameters as scratch variables on the stack, ASCII codes instead of character literals, the ternary operator and the comma, bitwise operations instead of logical ones. That's how the sum-parsing function was squeezed down to e(){for(z=t();c-43u<3;)y=44-c,z+=y*t();return z;}.

The readable version takes over 4800 bytes; to hit the coveted figure, quite a few features had to be thrown out — comparisons, for example, since truthiness works without them via if n%15:. The final result is exactly 1024 bytes.

For all its austerity, the interpreter fits in integer variables and arithmetic with operator precedence, comparisons, if/else branching, while and for x in range(y) loops (even with an else block), definitions and recursive calls of argument-less functions, indentation-based blocks, print, and comments.

The author swears off repeating anything like this anytime soon: the process, by his account, is exhausting — you have to dart back and forth between “mid-golf” and the original version to remember what you changed a couple of minutes ago. Both versions are posted on GitHub, and the note closes with a question for the reader: what would your Python in 1024 bytes look like?

Source: Lobsters