Making a Python interpreter in 1024 bytes
austinhenley.com238 points by azhenley 11 hours ago
238 points by azhenley 11 hours ago
The code makes me smile, because it's nasty. This isn't like C4, a tiny but complete C compiler which does error checking on its subset. Instead, this is worse than Sector C, which takes every shortcut and just plain assumes everything in the source is right.
This "Python" just plain assumes for keywords: Any "f" is a "for [x] in range[y]" (exactly that, no other for's). Any "w" is a "while". Any "i" is an "if". Any "d" is a "def". Any "p" is a "print("
Nasty, nasty.
(Also nasty is that the code snippets in the article has more comments than the github copy of the "readable" version. You need the article to understand what's going on.)
This is a just a bit too simple for a "Tiny Python". If somebody is willing to allow a few more K's of bytes, I'd love to see at least lists & dicts here--Lisp can do them!
As they say in TDD, write a test, then write the simplest code that will make it pass.
Clearly supporting multiple functions starting with 'p' would be overengineering.
Reminds me of the good 'ol Apple II BASIC. You can name your variables whatever you want, but only the first two letters matter.
Two letters is luxury, when most BASIC interpreters in those days only recognised 1-letter variables.
If you are willing to sacrifice performance, you can implement dicts via linear lookup in much less code than a proper hash table.
Because Python dicts guarantee iteration order is the same as insertion order (https://docs.python.org/3.7/library/stdtypes.html#typesmappi...) Python dicts aren’t just proper hash tables.
Because of that it wouldn’t surprise me much if that sped up some standard benchmarks, for example ones parsing lots of small json objects into dictionaries.
It’s Python, you’ve already sacrificed performance, what a little bit more?
That's the spirit!
(Slightly less silly: the folks at https://github.com/faster-cpython are doing great work, too.)
> Any "w" is a "while"
Meaning that something as simple as "w = 4" would fail? A little too nasty for my liking. Not a choice I would have made, but admire the amount of work done here and the readability of the article. And it's more human-written code than I've done in a number of months!
But to be honest, I wonder what is the smallest interpretable and practical Turing Complete VM? I would argue that implementing a brainfuck that we lower Python interpreter to, or even say like an interpreter untyped lambda calculus or SKI combinator would be very useful, especially for the hardware bootstrapping.
I'm talking about things like SectorLisp https://justine.lol/sectorlisp/
For those who actually need something like this in production, there is Snek: <https://sneklang.org/> “Snek is a tiny embeddable language targeting processors with only a few kB of flash and ram.”
Yes, but compiling or modifying Snek from source is very challenging. I wish it was one single C file for an example base like Posix, instead of many files for many platforms plus a custom parser in Python (Lola).
Reading the article, I can't believe I just found out Code Golf is a thing. I've been a programmer for more than a decade.
But yes, amazing project! I like that it's human-made :)
The quintessential example is donut.c. I was amazed when I first came across it.
> This was my first attempt at obfuscated C and I feel it's pretty amateurish
I love feelings of inadequacy at 11:07pm on a Sunday.
Here's the judges' remarks and author commentary on the second edition of this from the 2006 results: https://www.ioccc.org/2006/sloane/index.html
This one is my favorite:
https://github.com/ioccc-src/winner/blob/master/2025/ncw1/pr...
Absolute legend
> it’s worked on every system I’ve tried so far though
Still my favorite part of the whole thing. Classic moment of “who among us hasn’t doesn’t this?” lol
Get thee to
Also https://github.com/nanochess
And then if you really want to go large
https://phoboslab.org/log/2021/09/q1k3-making-of
I still have a soft spot for https://www.pouet.net/prod.php?which=1221
To be precise this is 1024 bytes of C, which compiles to a binary many times larger, and implements a very tiny subset of Python.
loops work by jumping backwards and reparsing the source each iteration
This is how the DOS .bat processing works; not sure if Unix-style shells are the same, as I've never had the need to exploit that "feature".
Another comment here has mentioned C4, but another extremely dense (and slightly larger, since it wasn't actually deliberately(!) "code-golfed") interpreter you may want to look at is the J Incunabulum:
https://www.jsoftware.com/ioj/iojATW.htm
More generally, the array programming culture seems to consider this level of density the norm:
Bash lines are buffered, so modifying behind the program position doesn't really work, but you can self-append to the file to keep a script going infinitely.
This is really cool! It's so fun to see what you can achieve and what's optional. I have seen the 'single character variable' limitation in some other minilangs before, but using the source itself as the target of function calls and loops is new to me. It does make a lot of sense but I wouldn't have thought of that.
but using the source itself as the target of function calls and loops is new to me
This was standard practice on interpreters for 8-bit microcomputers; with only a 64K total address space, creating an AST first seems immensely wasteful, so you interpret from the source directly.
I believe shells still do this when you run shell scripts; I know the DOS COMMAND.COM definitely does.
I was very disappointed that this is “interpreting” some tiny made up language.
This is not Python, or even within three orders of magnitude of Python.
Yeah the amount of Python code that would work here is probably not a lot more than this specific FizzBuzz example. Lots of shortcuts taken, which I guess is understandable.
It’s true, the title should have said “Python-like”
TBF the fizzbuzz code works just fine in CPython.
Indeed, for some code, CPython and this interpreter produce identical output. I gave it an upboat.
I like python subset. However, many don't see it that way.
You're right, mathematically it's undeniably true. However...
One could imagine an even smaller subset interpreter. It's an interpreter for a subset of Python, consisting only of the programs that print "Hello World". Since it doesn't do any error checking, for all other programs the output is undefined. Implementing it is very simple: Just ignore the input file, and print "Hello World". As a bonus, it's an interpreter for the subset of "Hello World" programs in all other programming languages too!
</tongue-in-cheek>
It's not a subset of python.
For instance this program works in this interpreter, but not in python:
fxx i in rxxxx(10):
pxxxx(i)This seems to be in the same spirit as Justine Tunney's SectorLISP. Very cool.
SectorLISP makes an important question in its implementation: how much can strip down Lisp before stops being Lisp. Same is not done for submitted interpreter. So, although SectorLISP goal is to be a Lisp-reduced-to-its-essentials implementation, the Python-1024 goal seems to be imitating Python in most minimal code possible.
Good use of free will and well-written. Very nice walkthrough austin!
The condensed version is impressive to be sure, but I'm an even bigger fan of the readable version:
https://github.com/AZHenley/python1024/blob/main/python1024_...
Well done!
well written, looks cool ngl
I hate when they measure the size of source code instead of the size of a binary.
I appreciate .kkrieger much more than this monstrosity
A lot of criticism of python often mentions the whitespace as lexical scope tokens, and that criticism is usually posited by users of the language.
As implementer of an interpreter, did you feel that whitespace for lexical scoping made the job of writing the lexer significantly more complex?
And, there are multiple white space symbols!
<space><space><tab><space>
is different than
<space><tab><space><space>
So you also have to track the actual sequence of counts of white space used for each level, rather than just a simple count.
Or you just forbid mixing spaces and tabs in the same indentation sequence, the way most whitespace-sensitive languages seem to end up doing. Or you make a slightly more reasonable rule: spaces may follow tabs, but no tabs may follow a space. That's at least unambiguous.
Oh, that's really elegant! I've got a whitespace sensitive language of my own, and I think I'll change it to use that rule! Thanks!
(Until now, I went with the standard approach: Remember the leading whitespace of the previous line. Then compare with the new line's leading whitespace: If they are the same, then no change in indentation. If the old one is a prefix of the new one, it's an indent. If the new one is a prefix of the old one, it's a dedent. If neither, it's an error)
That seems like a decent way to handle the mixed-spaces-and-tabs scenario, even between lines: one line starts with `<tab><tab>`, the next line `<tab><tab><sp><sp><sp><sp>`, that's an indent. (Probably someone who likes 4-space indents and 8-space tab characters). Follow that up with `<sp>*12` and that looks like the same indent to someone who uses 4-space tabs, but not the same indent to someone who uses 8-space tabs.
So your proposed prefix-matching rule would correctly flag that scenario, forcing people stop and figure it out.
EDIT to add this P.S.: Actually, my "spaces may follow a tab but tabs may not follow a space" rule, while elegant, is incomplete. Your prefix-matching rule is actually necessary in order to deal with the "two tabs on one line, twelve spaces on the next line" situation. That would be legal under the "spaces may follow a tab but tabs may not follow a space" rule, but it's ambiguous whether that's an indent or a dedent. If tabs mean eight spaces then it's going from 16 to 12, a dedent; if tabs mean four spaces then it's going from 8 to 12, an indent.
But it also feels arbitrary and annoyingly restrictive. On top of that there are at least 25 whitespace codepoints in UTF. Should your language really be opinionated about when, where, and in what order (for example) the "mongolian vowel separator" appears?
I mean, obviously that one should only appear within Mongolian text and not within indentation.
To state explicitly what should be implicitly obvious, there is no valid reason (that I'm aware of, I welcome any non-facetious correction) to use any character except U+0009 and U+0020 within indentation. Horizontal Record Separator? Zero-width joiner? Language-specific whitespace characters like your example? All make sense within human text (well, maybe not HRS), but in programming, they should be eschewed in favor of the characters that can be typed in every single keyboard layout in the world. Even languages that don't put spaces between words, such as Thai, still put spaces between sentences (or comma phrases) and therefore keep the space bar in their keyboard layout.
And since mixing tabs and spaces (even between lines, where some lines are tab-indented and some are space-indented) creates problems for whitespace-sensitive language, there's a reason why every whitespace-sensitive language I'm aware of has tended to either outright forbid, or at least discourage, U+0009 and its ambiguous meaning (since its meaning isn't clear until you know people's editor configurations, which are usually not available to the validation code running in CI or on other people's machines).
> To state explicitly what should be implicitly obvious, there is no valid reason ...
There doesn't need to be an articulable reason. Or rather there's generally no expectation that a central authority will be able to reliably enumerate such. Everything should default to being permitted and only ever be restricted for good reason.
But since you asked. U+2003 for example carries formatting information. Maybe an editor could be written (or even already exists) that would find that useful. Who is any third party to dictate that?
U+00A0 similarly communicates information about the desired formatting and I can see no reason it would be unreasonable for someone to use it nor why its use should pose a technical challenge to a compiler.
> creates problems for whitespace-sensitive langauge
Does it? That seems like an invented problem to me. You have a running prefix composed of arbitrary whitespace characters. Any change in that prefix is a change in the level of indentation. You can add or remove arbitrary amounts from the end of the prefix. In the event you remove from it the result must exactly match the previous stack level. What's so complicated about this?
> outright forbid, or at least discourage, U+0009 and its ambiguous meaning (since its meaning isn't clear until you know people's editor configurations ...
Did you mix up your code points there? It's space that's ambiguous, not tab.
Regardless I think that a compiler worrying about the specifics of text editors or other tooling would be backward information flow and a massive abstraction violation. Semantic meaning is entirely dictated by the compiler, not the other way around. There's no convincing reason (IMO) to impose restrictions that aren't technically necessary or to otherwise needlessly employ solutions that would reduce generalization.
> Did you mix up your code points there? It's space that's ambiguous, not tab.
Space is always the same width, but tab means a variable number of spaces (usually either 4 or 8, but I've seen 3 before) depending on people's editor configuration.
What makes you say that the space character, U+0020, is ambiguous?
A single tab always indicates (AFAIK, in common usage) a single level of indentation. Whereas depending on editor configuration a single level of indentation could be represented by any number of spaces - commonly somewhere between 4 and 8, but who can say?
Tab never "means" any number of spaces. How it gets displayed varies but the meaning (of any character, not just tab) can only ever be determined by usage, not display choices (at least for any sane way of doing things). Otherwise what would you make of escape sequences or binary files? Or constructs such as a nonbreaking space?
What business does a compiler have worrying about display width? As I said earlier worrying about the specifics of the editor or other tooling would be backwards information flow and a massive abstraction violation. What if I choose to program in a variable width font? (For the record writing that left me feeling disgusted.)
Got it. You're looking at the problem from the other direction. Yes, tabs are unambiguous if they're the only thing used for indentation. It's when some people use tabs and others use spaces that ambiguity arises.
But there are other cases where the variable-width nature of tabs can create ambiguity all by itself. Take this example from R7RS small:
(cond ((> 3 3) ’greater)
((< 3 3) ’less)
(else ’equal))
(cond ((> 3 3) ’greater)
<tab>((< 3 3) ’less)
<tab>(else ’equal))
Here, the ambiguity is because the tab character needs to have a width of six characters in order to align with the text `(cond `. If that had been an `(if ` with just two forms (omitting the `(else 'equal)` case) then the tab would have needed to have a width of four characters. A smart editor that reads the Lisp code and can interpret `<tab>` as meaning "indent this form to align with the form on the line above", but any context that isn't syntax-aware, such as a git diff, will not align those tabs correctly.
Which is why I consider tabs to be ambiguous, because I'm looking at it from the perspective of "how many spaces does this correspond to", and spaces to be unambiguous.