9 ms·
Writing a C compiler in 500 lines of Python (2023)
- weregiraffe 1y agoNow write a Python compiler in 500 lines of C.
- wyldfire 1y agoA python VM that consumes bytecode might be doable in not-ludicrous-amounts of C. Not 500 lines I suppose. But something manageable I think? Especially if you targeted the older releases.
- jonjacky 1y agoIn the CPython reference interpreter, that VM can be found at https://github.com/python/cpython/blob/main/Python/ceval.c https://github.com/python/cpython/blob/main/Python/ceval.c It's 3619 lines. It's explained in this 515 line file: https://github.com/python/cpython/blob/main/InternalDocs/ https://github.com/python/cpython/blob/main/InternalDocs/ For comparison, there is a pure Python bytecode interpreter, its VM is here: https://github.com/nedbat/byterun/blob/master/byterun/pyvm2.py https://github.com/nedbat/byterun/blob/master/byterun/pyvm2.... It's 1043 lines.
- bluGill 1y agoI could probably do it - but you wouldn't like it. My dictionaries would be a linked-list, looking for a key becomes a linear search... (if you gave me C++ I'd use std::map) I'm assuming you will allow me to use the C standard library, if I have to implement strlen or malloc in that 500 lines of C I'm not sure I can pull that off. 500 lines is aggressive, but IOCCC gives me plenty of tricks to get the line count down and the language isn't that big. I'm also going to assume 100% valid python code is fed in, if there is a bug or error of any sort that is undefined behavior. Note that most of what makes python great isn't the language, it is the library. I believe that large parts of the python library are also written in C (for speed), and thus you won't be able to use my 500 line python compiler for anything useful because you won't have any useful libraries.
- dekhn 1y agoA hash table in C is about 30 lines of code, so I don't think you have to stick to linked lists for dictionaries.
- ludocode 1y agoIndeed, a decent closed hash table is maybe 30 lines. An open hash table with linear probing is even less, especially if you don't need to remove entries. It's almost identical to a linear search through an array; you just change where you start iterating. In my first stage Onramp linker [1], converting linear search to an open hash table adds a grand total of 24 bytecode instructions, including the FNV-1a hash function. There's no reason to ever linear search a symbol table. [1]: https://github.com/ludocode/onramp/blob/develop/core/ld/0-global/ld.oe.ohx https://github.com/ludocode/onramp/blob/develop/core/ld/0-gl...
- bluGill 1y agoa linear search may be faster because it is cache and branch prediction frienly. Benchmarks on real world data is needed to make a final call.
- bluGill 1y agoSure but a linear search is 5. when my limit is 500 lines of C I don't dare spare those lines.
- threeducks 1y ago9 lines seem to be sufficient (assuming string keys and int values). // Hashtable definition #include <string.h> #define N 1024 int* map_ptr(const char **keys, int *values, const char *key){ size_t h = 0, c = 0, i; for (const char *c = key; *c; c++) h = h * 33 + *(unsigned char*)c; for (i = h % N; c < N && keys[i] && 0 != strcmp(keys[i], key); i = (i + 1) % N, c++); if (!keys[i]) keys[i] = key; return 0 == strcmp(keys[i], key) ? &values[i] : NULL; } // Example usage const char *keys[N]; int values[N]; #include <stdio.h> int main(){ // Set some values *map_ptr(keys, values, "one") = 1; *map_ptr(keys, values, "two") = 2; *map_ptr(keys, values, "three") = 3; // Retrieve values printf("one: %i\n", *map_ptr(keys, values, "one")); printf("two: %i\n", *map_ptr(keys, values, "two")); printf("three: %i\n", *map_ptr(keys, values, "three")); return 0; }
- TZubiri 1y agoNot to be that guy, but Python is an interpreted language. That said, I guess technically you could make something that compiles python to an executable? This is hacker news after all
- vidarh 1y agoA language is not inherently interpreted or compiled. Some languages are more or less easy to compile efficiently and without embedding a JIT compiler, but any language can be compiled. For Python in particular, there are already compilers. If you want a nightmarish language to compile, look at Ruby. There are compilers even for Ruby.
- nurettin 1y agoPython has the same amount of nightmare. Maybe even more. You can add static class and instance accessors at runtime, it supports full monkey patching just like Ruby does. You can meta program modules, classes, objects, you can decorate classes and functions, declare functions and lambdas anywhere. "compilers" usually disallow monkey business and compile only a subset.
- zahlman 1y agoThis isn't even correct for the one specific reference implementation you're presumably thinking of. It is just as much "compiled" as Java or C#, just that the compilation is often done on the fly. (Although IIRC C# does some additional trickery to pretend that its bytecode is "real" executable code, wrapped in a standard .exe format.) Presumably you've noticed the __pycache__ folders containing .pyc files; those are compiled bytecode. When you install Python, typically the standard library will all be precompiled (at least in part, so that those bytecode files can be created by an admin user now, and used by a standard user later). There is an interpretive REPL environment, but that works by doing the same bytecode-compilation each time.
- nickpsecurity 1y agoMaybe 500 lines of Pythonic, macro-heavy C. If the macros' LOC don't count. Maybe.
- tvickery 1y ago[flagged]
- emilbratt 1y agoThat is not a compiler. That is called a wrapper script. But funny none the less.
- amszmidt 1y agoThe original cc was just a wrapper like this Python example around a bunch of external programs, calling c00, c01, until something could be fed to as and then linked using ld. GCC does basically the same thing even today,
- 01HNNWZ0MV43FF 1y agoyeah but c00 and c01 actually do stuff
- TZubiri 1y agoSo does gcc
- deleted 1y ago[deleted]
- rossant 1y agoNow do it without imports.
- tomhow 1y agoPreviously: Writing a C compiler in 500 lines of Python - https://news.ycombinator.com/item?id=37383913 https://news.ycombinator.com/item?id=37383913 - Sept 2023 (165 comments)
- Liftyee 1y agoThis article breaks it down well enough to make me feel like I could write my own C compiler targeting AVR. (I probably could... but it would not be easy.) Never actually looked into how compilers work before, it's surprisingly similar/related to linguistics.
- measurablefunc 1y agoIt's b/c when Chomsky invented the theory of formal grammars he was studying natural languages & the universality of abstract grammar¹. Computer scientists realized later that they could use the same theory as a foundation for formalizing the grammatical structures of programming languages. ¹https://en.wikipedia.org/wiki/Chomsky_hierarchy https://en.wikipedia.org/wiki/Chomsky_hierarchy
- lukan 1y ago"compilers work before, it's surprisingly similar/related to linguistics." Since compilers transform languages with a clearly defined grammar ... the connection to linguistics is maybe not so surprising after all.
- dekhn 1y agoSimilar experience in DNA/genome analysis. A large part of DNA analysis was based on parser theory. This paper was my introduction to DNA analysis as well as Chomsky hierarchy: https://www.jstor.org/stable/29774782 https://www.jstor.org/stable/29774782 (I wasn't able to find a free copy). IIRC, pseudoknots in RNA require context-free grammars to parse.
- userbinator 1y agoYou should study C4, which is a C(subset) compiler in ~500 lines, but more interestingly, it can compile itself: https://news.ycombinator.com/item?id=8558822 https://news.ycombinator.com/item?id=8558822
- TZubiri 1y agoWe've come full circle
- MarsIronPI 1y agoI find it surprising that a single-pass compiler is easier to implement than a traditional lexer->parser->AST->emitter. (I'm not a compiler expert, though.) I'd have expected that generating an AST would be at least as simple, if not simpler. Plus by generating an AST, doing some simple optimization is a lot easier: one can pattern-match parts of the AST and replace them with more efficient equivalents. Maybe I'm overthinking this, though. I tend to like extensible program designs, even when they don't necessarily make sense for the scale of the program… Still a really cool article and an impressive project, though. I especially like the StringPool technique; I'll have to keep it in mind if I ever write a compiler!
- arjvik 1y agoNot sure if fewer LoC necessarily implies easier!
- kragen 1y agoI think this might depend on the language you're writing in. Historically, at least, it's pretty verbose to define a data type in Python compared to languages that are more designed for writing compilers. Consider these definitions from my prototype Bicicleta interpreter, which is written in ML, specifically OCaml: type methods = NoDefs (* name, body, is_positional ... *) | Definition of string * bicexpr * bool * methods and bicexpr = Name of string | Call of bicexpr * string | Literal of string option * methods | Derivation of bicexpr * string option * methods | StringConstant of string | Integer of int | Float of float | NativeMethod of (lookup -> bicobj) Those ten lines of code would be ten classes in Python with an average of 1.6 attributes each. Using dataclasses or attrs, that would be 36 lines of code, and then (if you're doing it the OO way) every function that I defined on one of these OCaml types becomes a method implemented in each class implementing a particular protocol, with a copy of its argument signature in every class. (If you used namedtuple instead, it's no less code, but you write it on less lines.) So, for example, this function on bicexprs let rec freevars = function Name n -> stringset [n] | Integer _ | StringConstant _ | Float _ -> stringset ["prog"] | NativeMethod _ -> stringset [] | Literal (Some selfname, methods) -> StringSet.diff (freevars_methods methods) (stringset [selfname]) | Literal (None, methods) -> freevars_methods methods | Derivation(object_, self, methods) -> StringSet.union (freevars object_) (freevars (Literal(self, methods))) | Call(object_, _) -> freevars object_ becomes six to eight method definitions in the different classes. (You can cut it down to six if you define an abstract base class for the constant classes.) And Literal.freevars needs an if-then-else. So that's another 20 lines of code. Python does support pattern-matching now, so functions like this might not be any more verbose than the ML version if you program them the same way instead of in the OO fashion. I haven't tried using Python pattern-matching, so I don't really know. In general, though, Python is more verbose than ML-family languages for this kind of thing by a factor of about 2–4, and that's before you count the test code you need in Python to get the kind of confidence in correctness that ML's type-checking gives you with no extra code. To my knowledge, Mypy doesn't do the kinds of pattern-matching-exhaustiveness checks that ML compilers do. I've sometimes "cheated" by trying to write code like this in Python using regular tuples rather than named tuples. You can definitely make it work, but it's a real pain to debug. Quoting Andy Chu from https://andychu.net/projects/ https://andychu.net/projects/: > Python is not the right language for [implementing] languages. I will use OCaml for subsequent projects like this. Python does have GC and dynamic dispatch, though, and those count for a lot.
- keyle 1y agoI love that graphic, so many nuggets in there, a very cute depiction of a compiler in general.
- Buttons840 1y agoAfter many years of programming in other languages, I finally learned C, and came to realize that there aren't actually any compilers that implement all of the C spec. Even GCC and Clang have their grey areas and their bugs. Before this, I had thought that C was a simple language. An idea propped up by articles likes this, as well as the oft touted fact that nearly every embedded system has a C compiler; no matter what you'll always have a C compiler. This point was driven home by part of a blog post that simply states "you can't actually parse a C header"[0]. The blog makes a good supporting case for their claim. They link to a paper that says[1]: > There exist many commercial and academic tools that can parse C.... Unfortunately, these parsers are often either designed for an older version of the language (such as C89) or plain incorrect. The C11 parsers found in popular compilers, such as GCC and Clang, are very likely correct, but their size is in the tens of thousands of lines. And sure enough, in the OP linked blog post, they state they are only implementing a subset of the language. Of course, it still has value as a teaching tool; this is just a tangential fact about C I wanted to discuss. [0]: https://faultlore.com/blah/c-isnt-a-language/#you-cant-actually-parse-a-c-header https://faultlore.com/blah/c-isnt-a-language/#you-cant-actua... [1]: https://hal.science/hal-01633123/document https://hal.science/hal-01633123/document
- 1vuio0pswjnm7 1y ago"Before this, I had thought that C was a simple language." It was a simple language. It can still be used that way As hobbyist I write simple programs that can be compiled with -std=c89 I use these programs every day. They are faster than their equivalents in python, smaller than their equivalents in go, and require less resources or dependencies to compile than their equivalents in rust It is easy to take something simple and make it complex Software developers do this consistently; software/language "by committee" faciltates it Generally developers commenting publicly do not like "simple", they prefer "easy" C89 is still useful and there are lots of things that rely on it
- wredcoll 1y agoC the language is simple until you actually have to do something useful with it then you have to memorize the apis of every library you import.
- deleted 1y ago[deleted]
- ceronman 1y agoVery cool. I think Wasm is a nice instruction set, but I agree that its structured control flow is a bit weird and also the lack of instructions to handle the memory stack. But it's much more cleaner than something like x86_64. If you are interesting in learning in more detail how to write a C compiler, I highly recommend the book "Writing a C Compiler" by Nora Sandler [0]. This is a super detailed, incremental guide on how to write a C compiler. This also uses the traditional architecture of using multiple passes. It uses its own IR called Tacky and it even includes some optimization passes such as constant folding, copy propagation, dead code elimination, register allocation, etc. The book also implements much more features, including arrays, pointers, structs/unions, static variables, floating point, strings, linking to stdlib via System V ABI, and much more. [0] https://norasandler.com/book/ https://norasandler.com/book/
- alienbaby 1y agoI thought I had learned a new word reading this, but instead I just have something that seems like it should be a word given the context it was discovered in. Perhaps that in itself should be considered cremement. A word that looks like it should be a word but isn't.
- 1718627440 1y agoHuh? So what is the meaning of the word???