Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Show HN: My C compiler compiled itself

github.com

Post reply on HN
Print view View original

81–90 of 130 posts

Re: Show HN: My C compiler compiled itself

#81

Post by mbreese »

williamdclt wrote: post #78
dbcurtis wrote: post #13

Earlier quoted context omitted.

> 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? That would be the "bootstrapping" process. Nearly a half-century ago I took a compiler lab class where we were given a working, but slightly lame, compiler, and were tasked with adding new, less lame, language featu…

I guess the full bootstrapping process would start with writing a basic compiler in assembly?

Assembly? Ha! In my day, we would have considered ourselves lucky to have had assembly, let alone a C compiler. No, we had to bootstrap our computers using switches and paper tape. You probably want a terminal too!

In all seriousness, the bootstrap process is fascinating to me. At some point, it did all start with switches and manually loading commands directly into memory. And over time, we’ve slowly kept this thing going and growing. Also… I’m old enough to have seen a Altair with toggle switches, but I’m not old enough to have had to toggle in a boot loader on one. :)

Re: Show HN: My C compiler compiled itself

#82

Post by ijustlovemath »

dbcurtis wrote: post #13
yjftsjthsd-h wrote: post #8

> 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 your…

> 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? That would be the "bootstrapping" process. Nearly a half-century ago I took a compiler lab class where we were given a working, but slightly lame, compiler, and were tasked with adding new, less lame, language featu…

Sounds a lot like the kernel class at UIUC! Fun stuff

Re: Show HN: My C compiler compiled itself

#83

Post by atq2119 »

teo_zero wrote: post #43

Nice 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 itsel…

The 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.

Re: Show HN: My C compiler compiled itself

#84

Post by peterfirefly »

anyfoo wrote: post #26
unclad5968 wrote: post #23

Earlier quoted context omitted.

As someone that learned C# and python before C and C++, to this day I couldn't explain to you how make rules work. Make is so unlike build tools from other languages that it doesn't surprise me someone would rather use python to bootstrap their compiler.

It is so trivial, it takes you 10 minutes to learn. Less even, here is an attempt: foo.o: foo.c clang -c -o foo.o foo.c This builds a file called foo.o, if foo.c is newer than foo.o. Imagine that there is an identical bar.o as well, that builds it from bar.c. fooexec: foo.o bar.o clang -o fooexec foo.o bar.o This links together foo.o and bar.o into a file called fooexec, if at least one of foo.o or bar.o is newer (wh…

This is an amazingly good 2-minute introduction to makefiles. It would have been better without the last two sentences (and most of your comments on the topic).

---

Something skipped over by your introduction (and most guides to makefiles) which very quickly either makes makefiles less short or much more complicated is header files.

C files often depend on one or more header files that aren't system headers (this C compiler certainly does).

They could be added to each individual rule by hand:

  codegen/codegen.o: codegen/codegen.c codegen/codegen.h linked_list.h libc.h
       $(CC) -c -o $@ $
or they could be put into a variable:

  HEADERS = codegen/codegen.h parser/parser.h parser/goto.h linked_list.h libc.h 

  codegen/codegen.o: codegen/codegen.c $(HEADERS)
       $(CC) -c -o $@ $
which causes too much code to be recompiled every time a header file is changed.

Or we could do something really fancy and get only the right header files added as dependencies for each compilation unit. That requires using a feature of the gcc/clang compilers (their preprocessors, really) that causes them to output a small makefile snippet that lists the exact header dependencies for a compilation unit (the '-MD' option). These snippets can then be included in the makefile. To make this look relatively clean requires some fancy macro use that is waaaay beyond what people can learn in ten minutes.

This is an extremely common use case and it is a bit of an embarrassment that GNU make doesn't handle it better.

Re: Show HN: My C compiler compiled itself

#86

Post by keyvank »

atq2119 wrote: post #83
teo_zero wrote: post #43

Nice 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 itsel…

The 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 c…

perfect explanation, tnx!

Re: Show HN: My C compiler compiled itself

#87

Post by norir »

williamdclt wrote: post #78
dbcurtis wrote: post #13

Earlier quoted context omitted.

> 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? That would be the "bootstrapping" process. Nearly a half-century ago I took a compiler lab class where we were given a working, but slightly lame, compiler, and were tasked with adding new, less lame, language featu…

I guess the full bootstrapping process would start with writing a basic compiler in assembly?

It depends on definition of full bootstrapping process. At some point, someone has to bootstrap in raw assembly but we don't need to do that in 2024. If I write a bootstrap compiler in c on a machine that can run c, I can write an alternate backend for any assembly language (that supports the necessary compilation features) and thus produce a compiler implemented in any assembly language without directly writing any assembly.

Taking this process to the extreme, no one could ever bootstrap anything because eventually you're bootstrapping mineral extraction.

Re: Show HN: My C compiler compiled itself

#88

Post by ksk23 »

anyfoo wrote: post #24
mananaysiempre wrote: post #21

Earlier quoted context omitted.

Unlike 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.

If 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…

Reminds me of what I understand from the „Usagi Electric“ Bendix rotating drum -memory-computer execution :)

Re: Show HN: My C compiler compiled itself

#89

Post by exe34 »

CJefferson wrote: post #29
anyfoo wrote: post #26

Earlier quoted context omitted.

It is so trivial, it takes you 10 minutes to learn. Less even, here is an attempt: foo.o: foo.c clang -c -o foo.o foo.c This builds a file called foo.o, if foo.c is newer than foo.o. Imagine that there is an identical bar.o as well, that builds it from bar.c. fooexec: foo.o bar.o clang -o fooexec foo.o bar.o This links together foo.o and bar.o into a file called fooexec, if at least one of foo.o or bar.o is newer (wh…

Saying this is an 'incremental makefile' isn't really correct, as changes to header files aren't going to lead to rebuilding. So, either you need to manually keep references to which .h files you include in your Makefiles up to date, or start worrying about M / MM / MG / MP, and of course you'd like those to be re-run when you change your files, and suddenly your Makefile is an awful lot less simple. This is the main…

You could have taught them `make clean` whenever there's any issues. I work with software engineers and I still have to remind them to try rm -rf ./build/* now and again, which always seems to solve the problem.

Re: Show HN: My C compiler compiled itself

#90

Post by swiftcoder »

atq2119 wrote: post #80
williamdclt wrote: post #78

Earlier quoted context omitted.

I guess the full bootstrapping process would start with writing a basic compiler in assembly?

The full bootstrapping process starts with entering instructions in binary (or hex or octal) to build an assembler in the first place :)

The full bootstrapping process starts with a soldiering iron and a reel of copper wire.
Post reply on HN