24 ms·
Writing a C compiler in 500 lines of Python
- rhabarba 3y agoFinally, one can have inefficient C.
- MaxBarraclough 3y agoThere's always the CINT interpreter for C and C++. https://root.cern.ch/root/html534/guides/users-guide/CINT.html https://root.cern.ch/root/html534/guides/users-guide/CINT.ht...
- brnt 3y agoA PTSD trigger for me. Only half joking. Funny thing is, I never checked out Cling to see if it was at long last the real deal.
- wiseowise 3y agoWhy would language choice of compiler make any difference for efficiency of final output?
- NeuroCoder 3y agoThey didn't say the language was the issue. It doesn't support the full C spec. But if you want a reason why language might be an issue for a compiler, it could make compilation time slower. But I think the point of this project is not real world use but fun demonstration of skill
- vgel 3y agoMaybe not the language choice, but the codegen of this compiler is terrible because of the single-pass shortcuts (for example, it unconditionally loads the result of all assignment operations back to the stack just in case you want to write `a = b = 1`, even though 99% of the time that load is immediately thrown away.)
- deleted 3y ago[deleted]
- deleted 3y ago[deleted]
- folmar 3y agoAlways remember _bashcc_.
- tptacek 3y agoA time-honored approach! https://www.blackhat.com/presentations/win-usa-04/bh-win-04-aitel.pdf https://www.blackhat.com/presentations/win-usa-04/bh-win-04-... (minus directly emitting opcodes, and fitting into 500 lines, of course.)
- fan_of_yoinked 3y agoI love the graphic - would go see the worlds largest chomsky
- deleted 3y ago[deleted]
- brundolf 3y ago> Instead, we'll be single-pass: code generation happens during parsing IIRC, C was specifically designed to allow single-pass compilation, right? I.e. in many languages you don't know what needs to be output without parsing the full AST, but in C, syntax directly implies semantics. I think I remember hearing this was because early computers couldn't necessarily fit the AST for an entire code file in memory at once
- kazinator 3y agoIn C, nothing you have not parsed yet (what it to the right) is necessary for what you've already parsed (what lies to the left). (Necessary for type checking it or translating it.) E.g. to call a function later in the file, you need a prior declaration. Or else, an implicit one (possibly wrong) will be assumed from the call itself. This is not true in some C++ situations, like class declarations. In a class definition there can be functions with bodies. Those are inline functions. The functons can freely refer to each other in either direction. Type checking a class declaration therefore requires all of it to be parsed. A one pass language is advantageous even if you're building a serious multi-pass compiler with optimization. This is because that exercise doesn't require an AST! Multi-pass doesn't mean AST. Building an AST doesn't require just more memory, but more code and development work: more complexity in the code to build the abstraction and to traverse it. It's useful if you need to manipulate or analyze the program in ways that are closely related to the source language. If the language cannot be checked in one pass, you might need one; you wouldn't want to be doing the checking on an intermediate representation, where you've lost the relationship to the code. AST building can be reused for other purposes, like code formatting, refactoring, communicating with an IDE for code completion and whatnot. If the only thing you're going to do with an AST is walk it up and down to do some checks, and then to generate code, and you do all that in an order that could have been done without the AST (like a bottom-up, left to right traversal), then it was kind of a waste to construct it; those checks and generation could have been done as the phrase structure rules were parsed.
- speps 3y agoLinked from another thread: http://cm.bell-labs.co/who/dmr/chist.html http://cm.bell-labs.co/who/dmr/chist.html It explains the memory limits and what happened :) > After the TMG version of B was working, Thompson rewrote B in itself (a bootstrapping step). During development, he continually struggled against memory limitations: each language addition inflated the compiler so it could barely fit, but each rewrite taking advantage of the feature reduced its size. For example, B introduced generalized assignment operators, using x=+y to add y to x. The notation came from Algol 68 [Wijngaarden 75] via McIlroy, who had incorporated it into his version of TMG. (In B and early C, the operator was spelled =+ instead of += ; this mistake, repaired in 1976, was induced by a seductively easy way of handling the first form in B's lexical analyzer.)
- marcodiego 3y agoIt is interesting to think that 500 lines of code is something one can write in one or two days. But, writing a C compiler in 500 of comprehensible code (even in python) is challenge in itself that may take months after a few years of solid learning. I wonder if is this a good path to becoming an extremely productive developer. If some one spends time developing projects like this, but for different areas... A kernel, a compressor, renderer, multimedia/network stack, IA/ML... Will that turn a good dev into a 0.1 Bellard?
- Barrin92 3y agoat the very least it'll remove a lot of 'magic' from programming. Today a lot of people seem to be not so fond of university education but I'm personally very glad it made me go through implementing a shell, a compiler, a little toy kernel and so on. The feeling that you write code somewhere in the skies and have no idea how something works underneath has always really bugged me when I've used something.
- chaxor 3y agoYou don't need a university education to do those things, just some curiosity. The function of the university in the near future will probably just be to have like-minded curious people to discuss ideas with, and to get a better grasp of what problems need to be solved (specifically scientific ideas, rather than just applying engineering). The prestige element (specifically of certain universities over others, perhaps not university over high school) is dwindling, and hopefully will be abolished with this new generation.
- convolvatron 3y agoI'm largely taught outside the academic world. so I sympathize with your position. however, the engineering culture which took the time to tell me about all these cool things and let me grow into being an expert in them seems to be largely gone.
- jabits 3y agoA university degree is much more than this, and I think most people who view its value as “dwindling” have not had the experience…
- mati365 3y agoI made similar project in TypeScript[1]. Basically multipass compiler that generates x86 assembly, compiles it to binary and runs it. The worst thing were register allocator, designing IR code and assembler. [1] https://github.com/Mati365/ts-c-compiler https://github.com/Mati365/ts-c-compiler
- vgel 3y agoOoh, this is cool! Using WASM let me avoid writing a register allocator (though I probably would have just used the stack if I had targeted x86/ARM since I wasn't going for speed).
- amedvednikov 3y agoNice project!
- kaycebasques 3y agoIs there a C compiler written in Python that aims for maximum readability rather than trying to get as much done under X lines of code?
- muth02446 3y agoNot quite a C compiler but arguably better: http://cwerg.org http://cwerg.org
- vgel 3y agoI think the code is fairly readable! It's formatted with Black (and therefore limited to reasonable line lengths) and well-commented. IMO, being under X lines of code is part of the readability—10,000 lines of code is hard to approach no matter how readable it otherwise is.
- teddyh 3y agoFor some value of “C”: > Notably, it doesn't support: > structs :-( would be possible with more code, the fundamentals were there, I just couldn't squeeze it in > enums / unions > preprocessor directives (this would probably be 500 lines by itself...) > floating point. would also be possible, the wasm_type stuff is in, again just couldn't squeeze it in > 8 byte types (long/long long or double) > some other small things like pre/post cremements, in-place initialization, etc., which just didn't quite fit any sort of standard library or i/o that isn't returning an integer from main() > casting expressions
- deleted 3y ago[deleted]
- spease 3y agoC--23 (Respect to the author for doing this, I just couldn’t resist the obvious joke)
- vgel 3y agoI actually almost made it a C-- (https://www.cs.tufts.edu/~nr/c--/download/ppdp.pdf https://www.cs.tufts.edu/~nr/c--/download/ppdp.pdf) compiler, but IIRC the `goto`s made me go with the regular C subset instead.
- vgel 3y agoWell, I set the 500 line budget up front, and that was really as much as I could fit with reasonable formatting. I'll be excited to see your 500 line C compiler supporting all those features once it's done ;-)
- pjmlp 3y agoBasically like many C compilers outside UNIX during the 1980's. RatC did not need 500 lines for its preprocessor support, by the way.
- nn3 3y agoJust for comparison the LOCs for some other small C or C like compilers. It's not that far away from Ritchie's C4x86 | 0.6K (very close) small C (x86) | 3.1K Ritchie's earliest struct compiler | 2.3K v7 Unix C compiler | 10.2K chibicc | 8.4K Biederman's romcc | 25.0K
- vgel 3y agoOh, C4 is neat—technically it has me beat since it also implements the VM to run the code—though their formatting definitely takes advantage of long lines :-)
- deleted 3y ago[deleted]
- userbinator 3y agoThis one is certainly stretching the definition of "C like", but it's just under 512 bytes : https://news.ycombinator.com/item?id=36064971 https://news.ycombinator.com/item?id=36064971
- WalterBright 3y agoThis looks a lot like the Tiny Pascal compiler that BYTE published a listing of back in 1978. http://www.trs-80.org/tiny-pascal/ http://www.trs-80.org/tiny-pascal/ I figured out the basics of how a compiler works by going through it line by line.
- vgel 3y agoOh, that's neat (funny that they skipped out on similar things to me, like GOTO and structs :-) I didn't see a link to the source in the article, but this seems to be it: https://sourceforge.net/p/tiny-pascal/code/HEAD/tree/NorthStar%20Horizon/pascomp.bas https://sourceforge.net/p/tiny-pascal/code/HEAD/tree/NorthSt...
- dugmartin 3y agoI think Borland’s Turbo Pascal was also a single pass compiler that emitted machine code as COM files.
- kwhitefoot 3y agoSurely it is a feature of all Pascal compilers that they are single pass. I thought that it was part of the specification of the language that it be possible to compile in a single pass.
- deleted 3y ago[deleted]
- eru 3y agoThere's a bunch of LLVM-based Pascal compilers these days. I doubt they are single pass, given how LLVM works. (And in general, any optimizing compiler is most likely doing multiple passes.) You are right about Pascal's original design. Though I'm not sure if that's still true about modern versions of the language?
- pjmlp 3y agoNot even old ones, if we taken optimising compilers like VMS Pascal into account.
- rcarmo 3y agoI have to wonder if there's a Scheme to WASM compiler out there someplace right now I haven't found yet.
- vgel 3y agoLooks like Schism (https://github.com/schism-lang/schism https://github.com/schism-lang/schism) got part of the way there, but it unfortunately seems to be dead.
- cnity 3y agoHave you seen Guile Hoot? https://gitlab.com/spritely/guile-hoot https://gitlab.com/spritely/guile-hoot
- rcarmo 3y agoNo, thanks! Had a look, doesn’t seem to be ready to support WASI, but it’s active.
- cnity 3y agoWASI support is more a property of the host, no? If I compile some guile to WASM and it imports things from WASI, the compiler doesn't need to do anything to support it. The WASM host simply has to provide those imports according to the WASI spec. Unless I'm misunderstanding you.
- jll29 3y agoWriting your own compiler - demystifies compilers, interpreters, linkers/loaders and related systems software, which you now understand. This understanding will no doubt one day help in your debugging efforts; - elevates you to become a higher level developer: you are now a tool smith who can make their own language if needed (e.g. to create domain specific languages embedded in larger systems you architect). So congratulations, on top of other forms of abstraction, you have mastered meta-linguistic abstraction (see the latter part of Structure and Interpretation of Computer Programs, preferably the 1st or 2nd ed.).
- glouwbug 3y agoTook me seven years to do my own dynamic one that ended up being very similar to python2 with curly braces. Every programmer should try it
- Waterluvian 3y ago“Crafting Interpreters” is a phenomenal place to start. It’s very accessible. If you think you’re “not good enough” to write a programming language, it will show you just how wrong you are. Really boosted my confidence. (Hi Bob!)
- glouwbug 3y agoYeah that's where I started
- eru 3y agoWriting your own interpreter can be a lot of fun. Not sure if most people will get much extra out of writing their own compiler, too?
- mighmi 3y agoHow do later editions of SICP differ? I have no idea which I used.
- stevage 3y agoI dunno. I did a compiler writing course once, writing a compiler for a subset of Pascal in Ada, generating a kind of quasi assembly. It was a team project. I did most of the codegen and static optimisation. It was super fun and interesting. But I wouldn't say it was a terribly useful exercise that has greatly enriched me as a programmer. And somehow I have ended up with a very strong bias against DSLs.
- aldousd666 3y agoThis is crazy cool! Esolangs have been a hobby of mine, (more just an interest lately, since I haven't built any in a while,) so this is like a fun code golf game for compilation. Nice work, and even better, nice explanation article!
- golemarms 3y agoCool. Now try writing a Python compiler in 500 lines of C.
- _chu1 3y agoThe fact this is hidden says something about the disparity here.
- Uptrenda 3y ago[flagged]
- deleted 3y ago[deleted]
- Gibbon1 3y agoThe new Detect UB instruction is great.
- moomin 3y agoInevitably we have to ask: and how many lines of C in library functions?
- deleted 3y ago[deleted]
- hamilyon2 3y agoSo, given the python is an interpreter and very well understood, can we say that we are sure this compiler does not include Thompson virus?
- pyinstallwoes 3y agoNo
- deleted 3y ago[deleted]
- ForOldHack 3y agoThe *point* of a compiler is to compile itself.
- deleted 3y ago[deleted]
- HumblyTossed 3y agoIs it?
- ak_111 3y agoSomewhat unrelated question, but I think one of the second most difficult things of learning C for coders who are used to scripting languages is to get your head around how the various scaler data types like short, int, long,... (and the unsigned/hex version of each) are represented and how they relate to each other and how they relate to the platform. I am wondering if this complexity exists due to historical reasons, in other words if you were to invent C today you would just define int as always being 32, long as 64 and provide much more sane and well-defined rules on how the various datatypes relate to each other, without losing anything of what makes C a popular low-level language?
- PartiallyTyped 3y agoIf we were to write C today, we would never have such cases.
- ricardo81 3y agoI learnt C about a decade ago (after using scriping languages 10 years prior) and just stuck with using the uint values, no second thoughts about how big a uint32_t is.
- mfgs 3y agoExplicit variable size is useful for limited memory space envs like microcontrollers.
- foldr 3y ago>if you were to invent C today you would just define int as always being 32, long as 64 and provide much more sane and well-defined rules on how the various datatypes relate to each other, without losing anything of what makes C a popular low-level language? You'd lose something because those decisions would be impractical for 8-bit and 16-bit targets (which still exist in the world of embedded programming).
- ak_111 3y agoWould it be possible to create two versions of the language: microC for embedded C programs where these decisions matter, and standard C for PC/servers which basically all use the same representation for these scalers? My main point is that a C programmer today is forced to learn dozens of rules just to cater for many niche platforms that they will probably never target, so if you were to separate those two use cases you can get a much more neat C that targets modern 64 bit architectures with all the power of traditional C but a bit less portability.
- MrYellowP 3y agoI am really confused by what people call compilers nowadays. This is now a compiler that takes input text and generates output text, which then gets read by a compiler that takes input text and generates JIT code for execution. This is more of a transpiler, than an actual compiler. Am I missing something?
- traes 3y agoTo quote the great Bob Nystrom's Crafting Interpreters, "Compiling is an implementation technique that involves translating a source language to some other — usually lower-level — form. When you generate bytecode or machine code, you are compiling. When you transpile to another high-level language, you are compiling too." Nowadays, people generally understand a compiler to be a program that reads, parses, and translates programs from one language to another. The fundamental structure of a machine code compiler and a WebAssembly compiler is virtually identical -- would this project somehow be more of a "real" compiler if instead of generating text it generated binary that encoded the exact same information? Would it become a "real" compiler if someone built a machine that runs on WebAssembly instead of running it virtually? The popular opinion is that splitting hairs about this is useless, and the definition of a compiler has thus relaxed to include "transpilers" as well as machine code targeting compilers (at least in my dev circles).
- mananaysiempre 3y ago> [Building parse trees] is really great, good engineering, best practices, recommended by experts, etc. But... it takes too much code, so we can't do it. It takes too much code in Python. (Not a phrase one gets to say often, but it’s generally true for tree processing code.) In, say, SML this sort of thing is wonderfully concise.
- Jake_K 3y agoInteresting stuff
- jokoon 3y agoI don't see he use match case... while it's clearly a good use case.
- varispeed 3y agoI wrote a C compiler back in the day as a learning exercise. It was the most fun and rewarding project.
- Joker_vD 3y agoI am pretty certain the following is a valid "for"-loop translation: block ;; code for "i = 0" loop ;; code for "i < 5" i32.eqz br_if 1 i32.const 1 loop if ;; code for "i = i + 1" br 2 else end ;; code for "j = j * 2 + 1" i32.const 0 end end end It doesn't require cloning the lexer so probably would still fit in 500 lines? But yeah, in normal assembly it's way easier, even in one-pass: ;; code for "i = 0" .loop_test: ;; code for "i < 5" jz .loop_end jmp .loop_body .loop_incr: ;; code for "i = i + 1" jmp .loop_test .loop_body: ;; code for "j = j * 2 + 1" jmp .loop_incr .loop_end: Of course, normally you'd want to re-arrange things like so: ;; code for "i = 0" jmp .loop_test .loop_body: ;; code for "j = j * 2 + 1" .loop_incr: ;; code for "i = i + 1" .loop_test: ;; code for "i < 5" jnz .loop_body .loop_end: I propose the better loop syntax for languages with one-pass implementations, then: "for (i = 0) { j = j * 2 + 1; } (i = i + 1; i < 5);" :)
- vgel 3y agoOh, interesting--I remember messing around with flags on the stack but was having issues with the WASM analyzer (it doesn't like possible inconsistencies with the number of parameters left on the stack between blocks). I think your solution might get around that, though!
- meitham 3y agoActually with SLY (https://sly.readthedocs.io https://sly.readthedocs.io) now dead, what is the recommended Lexer/Parser library in Python?
- bfLives 3y agoI’m partial to the Python port of parsec. (https://pythonhosted.org/parsec/ https://pythonhosted.org/parsec/)
- Shocka1 3y agoThese kinds of posts are one of the things that keeps me coming back to HN. Right when I start thinking I'm a professional badass for implementing several features with great well tested code in record time, I stumble along posts like this that set me in my place.