Building a Python Interpreter in 1024 Bytes of C Code
A weekend coding challenge to create a minimalist Python interpreter.
1The Challenge
A programmer sets out to create a Python interpreter in just 1024 bytes of C code, without using macros or library tricks. The goal is to implement a subset of Python that looks and feels like the real thing, focusing on core syntax elements like def, colons, and indentation. The initial attempt starts with simple expressions like 1 + 2 and builds up to more complex statements like if x y: z = 3.
2Minimalist Approach
The interpreter uses a fixed-length array to hold the raw Python code and a symbol table for variables. It assumes correct syntax and strips most whitespace, keeping only indentation and spaces in string literals. Variable names are limited to single lowercase characters, allowing direct symbol table lookups. The interpreter maintains minimal state with global variables for the source code, current position, and line starts.
3Parsing and Execution
Expressions are handled with recursive descent parsing, executed on the fly. For example, parse_sum processes addition and subtraction by calling parse_term and combining results. The interpreter assumes keyword correctness and skips over them without full validation. Control flow is managed using the C call stack, with blocks executing until indentation decreases, then returning to the caller.
4Loop Handling
Loops work by jumping backward and reparsing the source each iteration. Both while and for loops track the condition expression position. After executing the body, the interpreter jumps back to this position to continue parsing. Functions operate similarly, saving caller locations and jumping to function bodies, then restoring the caller location upon completion.
5Code Golfing Tricks
To reduce byte count, the programmer employs C golfing techniques like using ASCII values for comparisons and skipping if statements with logical operators. Helper functions are minimized, such as skip_to_eol, which checks for newlines by subtracting 10 from the character code. The final golfed version replaces readable function names with single letters and combines operations to save bytes.
6Stack Overflow Inspiration
The programmer draws inspiration from Stack Overflow's Tips for golfing in C, using unconventional but effective tricks. For example, parse_sum is golfed down to e(){for(z=t();c-43u 3;)y=44-c,z+=y*t();return z;}, leveraging ASCII values and compact syntax. These optimizations shave off significant bytes, though some rely on GNU C89-specific features.
7Final Result
The golfed interpreter fits into 1024 bytes, down from an initial readable version of over 4800 bytes. Features like comparison expressions were cut to save space, relying on truthiness instead. The interpreter can run a fizzbuzz program, demonstrating Python-like syntax with def, colons, and indentation. Further optimizations could potentially reduce the size below 800 bytes for a minimal fizzbuzz implementation.
8Lessons Learned
The project highlights the creativity and constraints of code golfing, pushing the programmer to think differently about syntax and optimization. By focusing on minimalism and leveraging C's quirks, the interpreter achieves its goal within the strict byte limit. The challenge also underscores the trade-offs between readability and size, showcasing the art of extreme code optimization.