A developer has packed a working Python interpreter into 1024 bytes of C code. The project, titled “Making a Python interpreter in 1024 bytes,” was discussed on Hacker News, Reddit, and Lobste.rs.
The interpreter does not break the source into pieces ahead of time, build a tree of instructions, or turn the code into a middle step of instructions the way CPython does. Instead, it reads the source again on each pass, using the call stack of the host C code to manage the flow of the code. The result looks like a piece of Python that a reader would know on sight, built without concealed tricks that put in other text in place of the original or outside libraries.
The FizzBuzz Test
The developer’s benchmark for looking like Python was a FizzBuzz piece of code, complete with the keyword that starts a definition, punctuation marks after conditions, spacing that shows how the code is arranged, and no parentheses around if checks. Getting that FizzBuzz-style syntax to actually run was the whole point of the effort.
A Difficult Start
The first attempt fell short. The developer, who has written this kind of parser before — one that works by breaking expressions down piece by piece — including a project called Teeny Tiny, expected the work to go easily. Early tests handled simple number work and setting a value to a name, then simple if checks, but the code kept growing past budget.
It turned into something that only computes numbers.
Starting Over
The fix was to stop trying to make the code small first. The developer switched approach: get a working version first, then cut it down after. That meant listing which Python features would actually make the code look like Python, since fitting the whole language into 1024 bytes was never going to happen.
The final interpreter keeps its state in a small number of shared values, including a fixed array for the original source and a symbol table limited to 256 spots. Names are limited to a single small letter, which lets the symbol table be looked up directly by the letter’s value. There is no error handling. The parser assumes the code it is given is correct — keywords, spacing, and all.
How the While and For Statements Work
Because nothing gets turned into machine instructions ahead of time, repeated parts of the code work by moving back to an earlier point in the source and reading it again. Both while and for statements keep track of the position of their condition, then return to that spot after each pass.
Named pieces of code that run when called work the same way. The parser remembers where such a piece sits in the source, then moves there when it is called, running the body before restoring the earlier position where the call was made.
Shrinking the Code
The readable version of the interpreter ran past 4,800 bytes. Getting it down to 1024 meant serious code golf, guided in part by a Stack Overflow post called “Tips for golfing in C.” Some of the tricks rely on the way GNU C89 handles certain code, which the developer said was not against the rules, just unusual.
Several changes made the difference:
- A piece of code that handles addition was cut down to a short line that checks the character’s number value directly instead of comparing it letter by letter. Every character has a number assigned to it, and that number is what the code uses to tell one operator apart from another.
- A piece of code that skips ahead to the end of a line was reduced to a single short line. It checks for the number 0 and takes away 10 from a character’s value to find a line break.
Two smaller changes trimmed the code further:
- The same skip-ahead code also trades two separate calls for one call placed inside another, saving a character in the process.
- Comparison operators nearly got cut entirely, since Python’s rule that most values count as true or false on their own means a line like
if n%15:can take the place of a full equality check.
What Got Left Out
Several features did not remain in the final version. Comparison expressions were nearly cut for good, for the same reason listed above. The developer noted that a version built only to run FizzBuzz, with no other goal, could likely get below 800 bytes.
The project shows how far a small, easily recognized piece of Python can go when built by hand in C, without a single library call — proof that a weekend project and a strict byte count can still produce something that runs real code.
Source: austinhenley.com