7 ms·
Show HN: My C compiler compiled itself
One of the most challenging projects of my life :)
- jesse__ 2y agoCongratulations!
- keyvank 2y agotnx!
- pjdkoch 2y ago/me claps and cheers
- keyvank 2y agotnx!
- ajxs 2y agoAwesome work!
- anyfoo 2y agoCongratulations! That's no small feat.
- disqard 2y agoThank You For Making And Sharing!
- yjftsjthsd-h 2y ago> Then run ./build.py. This will use the bootstrapped 30cc-compiler to compile 30cc itself. It then again uses the 30cc-compiled compiler to compile 30cc once again. The final compiler is then stored as ./30cc. Why isn't that also done by the Makefile? The only catch I could see is that you'd need to have it build to different output names, but that seems fine for what it is? --- Also, I'm curious - did you find yourself having to constrain your use of C in order to make sure that the compiler could compile itself? Or does it implement everything you would use naturally anyways? (And of course, congrats/bravo; super impressive:])
- __alexander 2y ago> Why isn't that also done by the Makefile? My guess is that some people would rather write Python code than dig into Make’s documentation. That said, ChatGPT is excellent at creating valid make files.
- anyfoo 2y agoOr just take a few moments to learn the basics about Makefiles. The thing about Makefiles is that simples ones at least are really easy to write, and read. Much simpler and quicker than a cumbersome python script, that will most likely do less with much more boilerplate code (e.g. dependencies), and be much harder to read. Of course, you may hit a point where you stretch your Makefile so much beyond its common capabilities that that no longer becomes true, but in my experience that point is pretty far away.
- aleph_minus_one 2y ago> The thing about Makefiles is that simples ones at least are really easy to write, and read. Much simpler and quicker than a cumbersome python script, that will most likely do less with much more boilerplate code (e.g. dependencies), and be much harder to read. Whether this is true or not depends a lot on from which programming culture/background you come.
- anyfoo 2y agoI honestly don't think so, and I think this is here is a prime example for proving that. For example, a Makefile that does the same job as the build.py script in this project would be significantly smaller, simpler, and easier to read in several metrics that I'd reasonably call "objective" to a certain degree. In fact, contrast the Makefile in that project: https://github.com/keyvank/30cc/blob/main/Makefile https://github.com/keyvank/30cc/blob/main/Makefile With the build.py script: https://github.com/keyvank/30cc/blob/main/build.py https://github.com/keyvank/30cc/blob/main/build.py You need to know very little about Makefiles to make immediate sense of what that Makefile is doing, whereas you need to know much more about python to still not immediately see what the build.py script is doing. In fact, you will probably just "guess" that the python script is supposed to do a similar job only from its name before that. And then the python script still does not do incremental builds at all! Again, if it gets more complex that can change, but this is far away from that. It takes 10 or so minutes to learn enough about Makefiles to be productive with them, from scratch.
- hasheddan 2y agoawesome! keep up the great work!
- michael-online 2y agoWhat a fun project, thanks for sharing. I've dreamed of projects like this. What did you expect to learn from this project? Did you learn anything unexpected?
- keyvank 2y agoi learnt that building a c compiler isn't that hard, just takes time :)
- jheriko 2y agonice work. if you want more of a challenge try a compiler compiler that can compile itself... :) i got pretty far with this myself, although it doesn't work for weirdo languages like Python that need an exceptional lexer. i keep meaning to revisit this problem, since the tools in this space are pretty much non-existent or trash quality. https://github.com/semiessessi/cp2 https://github.com/semiessessi/cp2
- anyfoo 2y ago> if you want more of a challenge try a compiler compiler that can compile itself... :) Is that not what OP did?
- Koshkin 2y agoNo (if the parent really meant ‘compiler compiler’ which, I think, would be what yacc/bison is).
- anyfoo 2y agoAh, thanks. My brain actually did not see that second "compiler" when reading, now it makes sense.
- downboots 2y agoHow could you tell the difference between missing it and your brain filtering it out?
- anyfoo 2y agoIsn’t that the same now? By the way, I dislike the term “compiler compiler”, because that’s not really what it does. I like “parser generator” for tax/bison, and “lexer generator” for flex.
- ModernMech 2y agoyacc calls it's a compiler compiler, but it's a parser compiler.
- DrNosferatu 2y agoWhy not use WASM to bootstrap your compiler?
- anyfoo 2y agoElaborate, why use WASM?
- DrNosferatu 2y agoLike Zig did - then you could bootstrap in whatever environment that can interpret WASM. PS: Why all the downvotes? Just another perspective.
- mananaysiempre 2y agoUnlike any real machine (and most virtual ones), WASM is impossible to target with a simple single-pass C compiler. The reducible control flow requirement means you have to build a full control-flow graph and do graph algorithms to it before you can start emitting code. So IMO it makes for a bad starting point.
- anyfoo 2y agoIf you want to have "fun", generate code in a WASM-representation of Hoare's WHILE language, i.e. a program that only consists of a single outer while loop (in WASM a "loop" block), and conditionally decide for every single instruction in the loop whether it should be executed during a given pass. I think that could be done with a single-pass C compiler. In a very trivial (and terrible) case, you could keep a running "line_counter" variable that every statement in the loop is predicated with, which either gets incremented at the end of the loop, or set to an arbitrary value for representing branches. It would of course be a horrible (but very amusing) mess, and rather enforces your actual point.
- ksk23 2y agoReminds me of what I understand from the „Usagi Electric“ Bendix rotating drum -memory-computer execution :)
- teo_zero 2y agoNice job! But why 3 steps of compilation? The first step merely shows that you wrote valid C code that gcc can compile. It doesn't prove that the program actually does what promised. For example, if you missed to implement 'for' loops, this step would still produce a compiler, which could still work for a subset of C. Here comes the second step: it proves that it implements enough features to at least recompile itself. Now, this is still not a guarantee that all C constructs and features work, but we can reason that even if it only implements a subset of C, it's a large enough subset to build such a substantial app as a compiler. How likely is it that a compiler doesn't use a 'for' loop, not even once? But what is the reason for the third step? It doesn't add anything, it doesn't trigger any code path that was excluded in the first one. After all, if you did miss 'for' loops, and the 2nd step hasn't detected it, it must be because there are no 'for' loops in the source, so you will never detect it this way, no matter how many steps of recompilation you run.
- keyvank 2y agoThanks! The third step proves that the assembly code generated by the second-step compiler is valid even when compiling a big C project.
- atq2119 2y agoThe 3rd step can flush out compiler bugs, as follows. The 1st step uses gcc, so it's not going to find any bugs in this compiler. The 2nd step uses the compiler as compiled by gcc. That will find some bugs, such as crash bugs or missing features (like your for loop example). However, it does not find bugs that lead to generating incorrect code. The 3rd step uses the compiler compiled by itself. If there is a bug in code generation that led to the stage-2 compiler being compiled incorrectly, that is likely to lead to some error during stage-3 compilation, such as a crash. And if it doesn't crash outright, it is very likely to cause the resulting executable to differ between steps 2 and 3. The incorrectly compiled compiler is surely even worse at compiling correctly than the compiler that was presumably compiled correctly (using gcc)! So, this 3-step process is a pretty good way of finding bugs, especially if you compare the stage-2 result against the stage-3 result.
- 2y ago
- unwind 2y agoVery cool, congratulations! I took a 2-second peek at the code, and just wanted to offer a small piece of advice that I think makes it better. Or two, really. Counting is hard. Instead of (this is from parser.c): apply_result *ret = (apply_result*)malloc(sizeof(apply_result)); apply the two common principles of DRY [1] and "don't cast the return value of malloc()" [2] and you get: apply_result *ret = malloc(sizeof *ret); I think the latter is way better. [1]: https://en.wikipedia.org/wiki/Don%27t_repeat_yourself https://en.wikipedia.org/wiki/Don%27t_repeat_yourself [2]: https://stackoverflow.com/a/605858 https://stackoverflow.com/a/605858
- keyvank 2y agothanks man! yes that makes sense. unfortunately 30cc is not able to compile that syntax, and will probably give type-checker errors when passing a void* to pointer of another type. but will implement it sometime soon!
- unwind 2y agoAha, so it doesn't know about void* being compatible with all (object) pointers, but so far just requires the pointers to match exactly? I see. Not sure why I was down-voted, I think that is ... not nice. :(
- nar001 2y agoI don't think you can be downvoted, there's no downvote button
- hollerith 2y agoUsers with enough karma can downvote comments.
- quuxplusone 2y agoA beautiful example of Cunningham's Law! :)
- 2y ago
- p0w3n3d 2y agoCongratulations. You compiled yourself.
- peterfirefly 2y agoWas the linked list approach inspired by rui314's compiler?
- mizzao 2y agoOut of curiosity: would ./30cc_gcc (30cc complied by gcc-hosted 30cc) and ./30cc (30cc complied by self-hosted 30cc) be identical binary files, if 30cc was operating as expected?
- actionfromafar 2y agoNo, gcc optimizes code output and can make code shorter and faster. A compiler can make many, many decisions which will show up as differences in the binary output.
- mizzao 2y agoIn my question above, both compilers are 30cc, except one of the 30cc's was compiled by gcc and the other self-hosted.
- actionfromafar 2y agoAh, sorry. In that case, my guess is, probably yes. The outputs of both of these are probably the same. But not for certain - see: https://www.cs.cmu.edu/~rdriley/487/papers/Thompson_1984_ReflectionsonTrustingTrust.pdf https://www.cs.cmu.edu/~rdriley/487/papers/Thompson_1984_Ref...
- keyvank 2y agothe asms should be identical, so the binaries should be identical too, unless the linker is undeterministic
- euroderf 2y agoSimilar: "A Small-C Compiler", by James E Hendrix (not Jim E, not Jimi). Modify source, compile self, repeat. This repo claims to have the code: https://github.com/DosWorld/smallc https://github.com/DosWorld/smallc
- rangerelf 2y agoCongrats!!
- pabs3 2y agoSounds like you might be someone interested in the Bootstrappable Builds project: https://bootstrappable.org/ https://bootstrappable.org/ https://lwn.net/Articles/983340/ https://lwn.net/Articles/983340/
- keyvank 2y agothat’s why i love HN. tnx for the links!