Live data from Hacker News

Writing a C Compiler: Build a Real Programming Language from Scratch

nostarch.com

81–90 of 159 posts

Re: Writing a C Compiler: Build a Real Programming Language from Scratch

#81

Weird that this is about building a C compiler[0] in OCaml . I expected the implementation language to also be C both for consistency but also because i'm willing to bet that there are more people who can read C than OCaml. [0] actually from the readme in the github repo[1] it seems to be a C subset, not all of C [1] https://github.com/nlsandler/nqcc2

There are many disadvantages to writing a compiler in c (and I have done it). For me, the biggest is simply that it is very verbose for the type of things that you do commonly in a compiler. I have written a self-hosting compiler that transpiles to c and the generated code is about 5x as long as the original code. I could go through and clean it up and probably get it down to 2-3x, but there are certain concepts that cannot easily be expressed compactly in c (except possibly with preprocessor abuse that I don't have patience for). A simple example is that if you want to represent a union type you have to manually define 2 structs and an enum. Matching with switch is also verbose as you have to both match and manually assign the value in the match case. Again, you can use macros to do this though at that point you arguably aren't even using c but rather a hybrid language. A language like ocaml, makes it much more straightforward to define and match on unions as well as gives you other nice high level things like gc so you can focus on the compiler itself and not low level details.

Re: Writing a C Compiler: Build a Real Programming Language from Scratch

#82
I uh misread the title and thought someone built a C compiler in Scratch.

On topic, though: wouldn't a simpler language (maybe even a pseudo language) be a better target for a first learning compiler. I understand they don't build a full C compiler, but still. It looks to me like there's a lot of complexity add from choosing such a lofty target.

Re: Writing a C Compiler: Build a Real Programming Language from Scratch

#83
I see many comments saying that the book implements the C compiler in ocaml. In the introduction the author states that the book actually uses pseudo code so you are actually free to implement it in any language. The only recommendation is that you use a language with pattern matching because the pseudo code makes heavy use of it. The reference implementation is in ocaml.

Re: Writing a C Compiler: Build a Real Programming Language from Scratch

#84
I learned how to write a compiler by studying BYTE magazine in the 70's which published the source to a complete Pascal compiler as an article!

https://archive.org/details/byte-magazine-1978-09 (part 1)

All 3 parts of Tiny Pascal:

https://albillo.hpcalc.org/publications/Easter%20Egg%20-%20T...

Re: Writing a C Compiler: Build a Real Programming Language from Scratch

#85

I learned how to write a compiler by studying BYTE magazine in the 70's which published the source to a complete Pascal compiler as an article! https://archive.org/details/byte-magazine-1978-09 (part 1) All 3 parts of Tiny Pascal: https://albillo.hpcalc.org/publications/Easter%20Egg%20-%20T...

[deleted]

Re: Writing a C Compiler: Build a Real Programming Language from Scratch

#86
post #10

Earlier quoted context omitted.

Many compiler related books take inspiration from the "Dragon book" (Compilers: Principles, Techniques and Tools). So with likely lots of books with similar looking covers.

The cover looks nothing like the dragon book however?

Point was more that there are bunch of compiler related books featuring a dragon (and knight/other character). The original also has a different looking dragon & knight themed cover for every edition.

Like if I’d see the book on a shelf I would instantly guess it’s related to compilers. And I bet that’s completely intentional homage to the original.

Re: Writing a C Compiler: Build a Real Programming Language from Scratch

#87
post #78
post #56

Earlier quoted context omitted.

>just a simple case of bad code generation render little compiler into a toy one If you find some time to go through gcc bugzilla you'll find shockingly simple snippets of code that miscompiled (often by optimization passes), with fixes never backported to older versions that production environments like RHEL are using.

Ok, but that’s sw engineering issue. I still insist that a production grade compiler can’t leave performance on table. Which is where the current battlefield is.

I do not agree in the general case. There are very useful DSL compilers which do not consider performance at all, but just compile to a target which does the optimization for them (JVM, LLVM IR or even just C)

Re: Writing a C Compiler: Build a Real Programming Language from Scratch

#88

I see many comments saying that the book implements the C compiler in ocaml. In the introduction the author states that the book actually uses pseudo code so you are actually free to implement it in any language. The only recommendation is that you use a language with pattern matching because the pseudo code makes heavy use of it. The reference implementation is in ocaml.

Useful list considering that feature: https://en.wikipedia.org/wiki/Category:Pattern_matching_prog...

Re: Writing a C Compiler: Build a Real Programming Language from Scratch

#89
post #78
post #56

Earlier quoted context omitted.

>just a simple case of bad code generation render little compiler into a toy one If you find some time to go through gcc bugzilla you'll find shockingly simple snippets of code that miscompiled (often by optimization passes), with fixes never backported to older versions that production environments like RHEL are using.

Ok, but that’s sw engineering issue. I still insist that a production grade compiler can’t leave performance on table. Which is where the current battlefield is.

I think a production grade compiler not only can, but must, leave performance on the table when the cost is correctness (unless the performance gain is incredibly high and the correctness loss is minimal). Correctness is not all important, but it is the most important thing. Unfortunately, compiler writers do not agree and they do silly things like "let's assume UB cannot ever happen and optimize based on that".

Re: Writing a C Compiler: Build a Real Programming Language from Scratch

#90
post #14

So what's different about writing a compiler in 2024 than say 10, 20, or 30 years ago? When I started writing compilers in the 80's and 90's lex/flex and yacc/bison were popular. ANTLR came out but I never had a chance to use it. Everything after lexing and parsing was always hand rolled.

You can use the "classic" tool set and parse many programming languages. The real trick in writing compilers is taking advantage of the hardware (disclaimer: I designed and wrote middle-pass portions for IBM 360/370 processors (and clones), supercomputers from Cray and ETA Systems, and Sun 4 workstations among others, including some RISC systems that just disappeared around the bursting of the dot-com bubble) I tried and failed to optimize MPP systems from all of the "name" players in the 1990's. It kind-of broke my heart...

That "middle-pass" approach that will let you address many targets is still valid; the trick is finding a sufficiently robust and flexible internal representation at the right level. You also have to be able to out-guess the chip vendors where before you could go to the architect or a complete "System" book and get the real scoop, including things you shouldn't do. Oddly enough, there is simultaneously useful and completely worthless documentation scattered about the internet.

You might want to take a look at Muchnick and Jones' _Program_Flow_Analysis_ (yes, it's from 1981) but chapters 4-6 can be applied at code-generation time. How that fits modern Intel processors (for example) is unknown. Idealizing your processor as a RISC-V might be a reasonable way to proceed but in the end, you'll have to translate the code for the target -- it will be reasonably straight-forward if you drive it all from tables but it's not trivial.

Post reply on HN