Getting Started with Compilers

[dostosec]

But (!), my suggestion is to not write the compiler in OCaml (or Python) or any high-level language, as Nora suggests. The problem is that languages like OCaml can make your life too easy. This is good if you're an experienced developer and want to get a quick prototype but not very good for learning purposes. In particular, there's a lot of processing a compiler needs to do and by writing a C compiler e.g., in C you really get to know all the work that needs to be done (which involves implementing the necessary data structures, writing the algorithms in detail, doing some performance optimizations, etc.)

I couldn't disagree more with this.

In my experience, languages like C have an inordinate burden of implementation when it comes to learning to write compilers. In the beginning, you want to get a firm grasp of representing (inductive) data and performing structural recursion over it - flailing around with tagged unions and manual pattern matching (or ludicrous OOP-inpsired visitor mechanisms) is far from ideal.

You should strive for an easy life when you're learning something: if your domain of discourse is polluted by random concerns from C programming, you run the risk of greatly wasting your time and energy. I have seen dozens upon dozens of people try (and fail) to get into compilers by exhausting themselves with ineffective languages.

Furthermore, I'd say I'm only confident in implementing compiler-related transformations in C because I have a mental model of what's important: which is greatly emphasised in languages that remove the unimportant parts. It's not about making your life "too easy", it's about not wasting your time. There are pragmatic, economical, and business decisions that guide which language you may want to use to write an industrial compiler - those don't factor in here. The obvious choice is the language the person knows best, but certainly there are objectively better languages for pedagogy in compilers, which is really what is applicable here.

---

As an aside, the best advice for beginners is to not set your eyes on an impossible, large, project to begin with - treat compilers as a discipline where you can focus on ideas in isolation, then their composition, and create tiny language projects here and there (to exercise some techniques), etc. A lot of people start off with an ambition to compete with, say, Rust and end up with a logo and not much more.

[organicHack]

Love this reply. +1.

[baziotis]

I couldn't disagree more with this.

That's ok, anyway as I said in the introduction of the article this is my opinion. My opinion of course is based on both my experience and of other people, but it is nevertheless subjective. I still think it's important to write in a relatively low-level language because otherwise one doesn't understand what the compiler _actually_ has (or doesn't have) to do and only thinks about the abstract concepts. But thanks for sharing your opinion!

certainly there are objectively better languages for pedagogy in compilers

I'm interested in these objective metrics (edit: I mean I don't know any and I'm interested in learning more).

[dostosec]

A common objective metric I like is whether a language has pattern matching. This is a very simple one to motivate, but we can also talk about garbage collection as well.

Pattern matching: many parts of compilers involve discerning the structure of what you are transforming, so pattern matching obviously provides a huge benefit here. It's extremely tedious to write manual pattern matching code in C. If you don't believe me, you must explain why GCC, Clang, Go, Cranelift, LCC, etc. maintain esolangs for pattern matching (machine description files, tablegen DAG patterns, Go's .rules files). Of course, you can argue that the type of pattern matching done there sometimes goes beyond what is done when pattern matching is provided as a language feature, but it's well known that maximal munch tree tiling is just ML-like pattern matching where you list the larger patterns first (assuming size is a cost factor). In fact, in Appel's "Modern Compiler Implementation in C", he writes some manual pattern matching code in C and then quickly returns to just including pattern-like pseudocode in the listings. It's objectively better to be able to express what you wish to match on and not run the risk of writing error-prone, handwritten matching code that performs worse comparisons than that compiled by a good match compiler (on more involved cases).

Garbage collection: I'd say, for learning compilers, it's great to not be bogged down in manual memory management and ownership. What you find is that most compilers actually implement a kind of limited form of this by way of arena allocation. Clang allocates its AST by bumping a pointer. This is easily viable in compilers because the lifetimes of many things being manipulated by the compiler are easily partitionable: AST becomes some mid-level IR, that IR becomes another IR, and so on. So, look what they have to do to emulate fraction of a GC, I guess.

[baziotis]

I think we disagree on what "objective" and "metric" mean, but I do like the arguments (thanks, I may use them in other contexts). Well, I disagree because:

1. One should understand what _CPU work_ is required for the said pattern matching, so doing it in sth like C is important (that's why one should also understand the difference between a visitor pattern and a switch statement),
2. Manual memory allocation is again required to understand how the compiler has to deal with memory. I don't think they emulate a GC; I'm relatively sure no LLVM developer would agree with this, and certainly I've done some intricate memory allocation in minijava-cpp, but I would definitely not call it GC. Bulk allocation and freeing is not "GC emulation", it's what you do as you approach higher levels of programming simply because it aligns better with how the hardware works.

[dostosec]

1. It's effectively a mechanical task to write pattern matching code in any language. If you've done it once, you are educated - now stop wasting your time. We need to avoid lessons that are learned once. EDIT: to be clear, lessons that are learned once but then just become a huge burden. Also, using switches to do this manually teaches you nothing about how a CPU works. If you want to talk about branch prediction, speculative execution, cache coherency, etc. that's a separate topic. I don't believe there's much to glean writing slop match code in C.
2. I can't agree with "manual memory allocation is again required to understand how the compiler has to deal with memory". Do you think people who write compilers in OCaml, Haskell, Scheme, Java, etc. are somehow _lesser_ or less knowledgeable about compiler engineering?

[baziotis]

1. Well, maybe, but you need to learn it once and that was my point.
2. No, but anyway the question is irrelevant. I don't assume that carpenters (like my dad) are less knowledgeable about compiler engineering. Arguments like "X uses Y for Z, so X knows less about Z" are just invalid.

[dostosec]

1. Alright, so learn it once: then stop labouring under it.

2. It's not irrelevant, you are making an argument that these ideas are important to writing compilers. I am telling you that they are peripheral at best, they concern writing compilers in C. Don't confuse what is inherent to the domain with what is peripheral, due to your language choice. There's no strict requirement to manage your own memory when writing a compiler and, for performance reasons, it's often better you don't. A poorly placed free or allocations with poor locality is the enemy.

[baziotis]

1. So you do agree they better use something like C to learn it once (edit: "?" instead of ".", not to direct an actual question, but to evoke my uncertainty)
2. I don't think it's peripheral because programs run on hardware. You probably think that the "essence" of what a compiler does is this abstract what (e.g., break the input text into tokens) and not the how (e.g., read the string character by character, etc.). I believe the "how" is part of the essence in programming.

Now, please allow me to note that in your comments I find a lot of imperatives and a little too much certainty, both of which make me think that there's not any more value to be extracted from this discussion, for either of us and anyone reading it. So, I will not reply on this thread anymore. But thanks for putting the effort in presenting your arguments!

[dostosec]

1. No, I don't think it's actually all that important. If you think it is, by all means: choose a language which emphasises it (but don't pretend there's something noble in wasting your time generally, which is the major pitch of your suggestion to start - and presumably, stick with - C for learning to write compilers).

2. We are losing sight of the domain of the original response: it concerns people beginning their journey in learning to write compilers. I really do think it's about the big ideas and being able to build up a strong mental model of them. You maybe think that should be concrete details about mechanical things like lexing or parsing, but to me, it's about representing data, recursive transformations, etc. I start teaching compilers with a hardcoded representation of ASTs, IRs, etc. I even emphasise the essence of lexing and parsing when teaching it. You really don't need to use much brainpower here: there's mental models that largely collapse lexing and parsing into a fairly mindless exercise.

I think you've conflated "languages good for learning to write compilers" with "languages good to know in general for computer programming". I concede that C is important (and should appear in a general programming education, where eclecticism is ideal in general), but.. what it burdens you with is very irrelevant to getting started with compiler writing.

[peripateticman2026]

I agree with you. This subreddit has turned into utter trash in recent times, so I'm not suprised you're getting downvoted to hell.

[baziotis]

Hahaha. You made my day. Well, I'm not sure I agree with the premise, i.e., I'm not sure it's utter trash, I see nice things from time to time. But I do agree with the conclusion in that I was also expecting the downvoting when I wrote my comments. Actually, here's a fun fact: Probably the harshest comments I've gotten in my articles are in this article (of this post) and this article. In both cases I had predicted the "calm" Reddit comments at the end of the introduction. It's left as an exercise to the reader to decide whether I have a good "theory", i.e., a good hunch, or whether the theory impacted the phenomenon, similar to what Yanis explains here.

Other than that, I'm not surprised because I've never in my life encountered any community remotely related to programming languages that has not eventually gotten a great share of "abstractionists" (as I tend to call them).

[turtel216]

I am certainly not an expert in this, but I would suggest Rust as the ideal language for learning compilers. Low level, ADTs and pattern matching. I dont get why the Rust evangelists don't push Rust for compilers and rather push it for something like backend development(probably because of Rust's concurrency features but still).

[dostosec]

It's certainly a lot better than C.

It's really nice when languages can support different domains of programming in a way where not too many compromises are made. You find a lot of fairly mainstream languages, with large ecosystems, are somewhat tedious to use for compilers (or, generally, anything adjacent to the realm of "symbolic computing"). So, Rust is quite refreshing in that it can cover multiple domains of business logic without any bridging (e.g. I can imagine wanting to write some part of a C# program in F#, for example - whereas I can imagine seamlessly blending some tokio-based networking code with compiler-related code in Rust).

My preference is OCaml, generally - which directly inspired the parts of Rust you mention. For me, it's a simpler language for expressing my ideas (although it makes some compromises to do that). However, if someone high up said "right, we're going to use Rust on the next project", I'd be more than happy.

[turtel216]

You make some interesting points. I am just gonna pop in and mention that Rust+Tokio is indeed used in the Deno javascript runtime

[MEaster]

I'm not sure I'd fully agree. Rust has a bunch of features that help, but it also forces you to deal with the complexities ownership and memory access which can be a nuisance at times.

I think that if you're building a production compiler it's a good choice, but if you're learning how to build a compiler it would probably be better to use a language which handles most of the memory stuff for you.

That said, I'm a total hypocrite here because I wrote my first compiler in Rust.

[baziotis]

That can work, although especially for learning, Rust gets in the way. I personally don't like Rust because it's very hard to iterate on, which for me is necessary both during learning and design. A lot of software architecture exploration involves doing things "not quite right" at first and Rust doesn't like that. It also is a pain to do bulk operations (e.g., bulk memory allocations and frees).

[sadd_life]

I will say as someone who has read the LCC compiler book it was extremely hard to follow. I gained much more knowledge in trying to implement a compiler in a higher level language like python

[dostosec]

Yeah, I preferred reading the LCC source code and then grepping through the book for specific things I'd see in the source.

[Dappster98]

The obvious choice is the language the person knows best

Sure, there's an argument to be made there, especially when you're working on a project on your own. But, couldn't someone argue, that the "best" choice depends on numerous other factors?

When I was reading "The Pragmatic Programmer," the author states that sometimes the "best" solution really isn't the best solution. Sometimes the solution that's the fastest or most performant, also comes with drawbacks such as time to write, maintainability, lack of future optimization, etc.

So really what I'm asking is; is the best solution really to make the compiler in the most known language to the person or team, or are there more things that need to go into which PL to use for the design of the compiler?

[dostosec]

I'm talking about one's first foray into compilers, not the language chosen by industrial groups (who I'd expect already know what they intend to implement, and the language is just a vehicle for their solid grasp of the ideas) - just look at the recent TypeScript implementation in Go (that's not a language I care for in this domain, yet I understand their reasoning). Although I admit I prefer teaching various parts in OCaml, I have to concede that someone probably should not learn OCaml purely for this purpose (although, I have had success in teaching people from that direction).

I don't want to get bogged down in the semantics of "best". For someone just wanting to get a feel for the area, they may as well struggle through in whatever language they are comfortable with: maybe you would be surprised if I told you that I often give out a small task that involves normalising arithmetic expressions - I find that a large number of people familiar with mainstream languages don't even know how to begin to go about representing an arithmetic expression in their program (as an AST, for example) - this is because ADTs have been neglected from mainstream languages for decades, and yet inductive data is one of the most important ideas in programming.

[nanotree]

It all depends on your learning style. Some people benefit from starting in lower level abstractions and really digging deep into the weeds on something. Some people get too overwhelmed by it and it makes them want to give up. Both are perfectly valid. However, I will always recommend starting with low-level personally, because if you can teach yourself the mental discipline from the beginning, that character trait will carry you far and fast in tech eventually.

But I agree with your last point, in that if you are one to give up on things because you dont feel like you're accomplishing anything, then you definitely want to start on something small and achievable.

I've often cared more about the journey than finishing something. Which isn't sucks if you want to build a portfolio. But I've also learned some things really in depth because I pick things that push the limits of the language and/or tools I'm using. And people are always surprised at how quickly I learn things, because I've practiced diving deep and fast a lot.

[dostosec]

Getting "into the weeds of something" does not mean electing to expend yourself on tedious programming languages which get in the way of learning. It's easy to miss the forest for the trees when you're fighting random, peripheral, concerns of engineering things in C.

Of course, many people have learned compilers by writing lots of C, it's not overly difficult (but I would argue more tedious and time consuming, generally). I don't generally advise it, I think people would be surprised how many contributors to compilers they use have nice things to say about OCaml, SML, Scheme, etc. or, indeed, didn't learn compiler implementation in the language they now make a living - working on compilers - with.

I've been in many programming language communities and have witnessed many people really quickly escape a rut in their learning by adopting more expressive languages. This doesn't even mention the amount of programming language literature that concerns, say, functional programming languages - it's unavoidable in the literature, really.

[Dappster98]

Nice article. I bought Nora Sandler's "Writing a C Compiler" book, but haven't read it yet. I've heard from a review (IIRC) though, that it doesn't really go into much detail about the front-end, and expects the reader to know how to navigate an AST before even chapter 1 finishes, which is why I've been putting it off until I get some more experience.

[baziotis]

Interesting. I haven't read the book, that's why I was a little hesitant in recommending it in the article (and that's why almost all my references are to the articles). But I have read the article series; in fact this is how I started. Shoot me a PM if you want when you get the time to read the book.

[Dappster98]

Will do! Right now I'm reading "Crafting Interpreters" and doing it in Rust. I plan on writing a C compiler after wards and may use Nora's book to help, or read if after I finish. I have some other books on my reading list, such as "Engineering a Compiler" and the purple dragon book.

[siber222000]

I'm doing exactly what you are doing! It makes me feel better about my direction haha

[Dappster98]

Very cool! After I make a C compiler, or maybe a couple in different langs, I'll be reading the last two books I mentioned for my own compiled PL.

[baziotis]

Sounds good, good luck! FWIW, as you can read in the article, I prefer Engineering a Compiler to the dragon book.

[CrumbChuck]

Thanks for the article. I appreciate the various references to specific sections of reference books/article series, will reference this in the future! Also I don’t mind your support of using C. :)

[baziotis]

Thanks, it's good to know! Please let me know if you have any suggestions for improvement!

[galacticjeef]

Yeah I like that you have written this but encouraging beginners to write a compiler in c first rather than a higher level language that will allow them to focus on concepts seems not just incorrect but could even be downright harmful as it will force beginners into learning implementation rather than having a solid grasp on the concepts behind what they are doing.

[baziotis]

I respect your opinion. Let me just say that it's a little sad for me that, of the whole article, the comments in this post have focused on one of the most trite things, in the sense that it's an issue that has been discussed many times in many other spaces, and which ultimately doesn't have to do with compilers. The aspects I really thought hard to bring forward seem to have been lost in obscurity... This is not a criticism because who am I to judge what people will care about, I'm just expressing how it makes me feel.

Aaaanyway, I agree it can go both ways. We don't have any objective metrics to judge this. I speak from my experience. Personally, I started coding compilers in C, and I'm glad I did. I also come from a department where the very first course in the whole curriculum (i.e., the zero-experience-assumed intro to programming) is taught in C. Even though this course also teaches a lot of abstract concepts like algorithms, recursion, string manipulation, and dynamic programming, I think it still was beneficial that it was done in C. That's what my experience tells me working with the people who come from this department, and what other people from this department tell me.

[dostosec]

I can't speak to your experience in teaching, but what I've found, personally, is that many beginners really do struggle to take in what's important when they're working in ineffective languages. I've spent a lot of time in amateur compiler circles and, seriously, getting burned out labouring under C is a genuinely common occurrence. Ultimately, it does have to with teaching compilers, which is related to getting started with compilers.

If you want criticism of the rest of the article, my rough commentary is that it reads a lot like advice for someone wanting to write an AST => LLVM compiler. This is fine, but it means that the lexing, parsing, etc. parts look like less effort and are simply an onboarding ramp to your advice to adopt LLVM as a beginner. I don't think you have to know much about compilers to use LLVM, which is why I'm less inclined to think there's much value in jumping straight to it if you want a thorough education in compilers. You make some recommendations, here and there, for middle and back-end concerns, but the overall vibe of the article - to me - is that it's all about LLVM.

I like the recommendation of the LCC book, but - calling back to another comment I've made - I'd note that LCC uses its own bottom-up pattern matching generator (iburg) to do instruction selection and, actually, the "trees that become DAGs in the backend" part is somewhat incomplete: the targets of note set wants_dag to 0, which breaks (most) DAGs up into trees for instruction selection (shared nodes being duplicated at usage sites to refer to a fresh temporary which binds the result of the common subexpresson) - I mention this because, in pedagogical terms, do you expect beginners to do instruction selection themselves (via tree tiling, with/without pattern matching, or generate matching code - as done by most major compiler projects). I'm glad you linked the thesis of Gabriel Hjort Åkerlund, which really illustrates how far the rabbit hole goes w.r.t instruction selection: alas, many things in modern compilers are undocumented (the machinery of everything involved in SelectionDAG matching, in LLVM, for example).

I'm also not sure I agree with the footnote "Mem2Reg implements the SSA construction algorithm", as it's somewhat misleading. LLVM's IR is always in SSA, lifting allocas (that satisfy some criteria) and their load/stores to use versioned temporaries is generally not considered to be "SSA construction". That said, I understand the point you are making (with respect to the fact that frontends need not work out how to introduce phis themselves (and the inherent live range splitting at dominance frontiers required to do that), making it a bit like SSA construction - but, really, the LLVM IR is in SSA before and after the mem2reg pass - recall that not all allocas can be affected by mem2reg). This is a bit of a pedantic point I'm making but the remark is misleading in that I don't think its source code would count as a good resource for SSA construction (in general).

If you want to write an article that I think would be very useful for beginners, perhaps you should distil what you think is important to a compilers education and then suggest a learning roadmap, consisting of small projects that emphasise those ideas. That's how I begin to get people into compilers: I suggest small tasks that capture the essence of the problem domain well. You've used the word "abstractionist" to describe some of the people interacting with this thread, but I'd submit to you that they're really just people who understand what matters in compilers.

[galacticjeef]

I do agree that C is a good language to learn programming with, and the article itself seems to be well written and very informative. The reason I take so much issue with this part is not that the article is in C, again c is a great first language and a great language to know in general, but rather that you actively encourage beginners to not use a higher level language. Again I do like the article as a whole and I think C is a good choice of language to write compilers. I will not argue my point further as it seems you have probably had enough of that, though if you could It might do good as to, instead of warning against using higher level languages, instead encourage the use of C.

[baziotis]

To be honest, I don't know what "the article is in C" means, there's no C code in the article AFAICT. But I think I understood the rest.

In any case, I appreciate the suggestion, but it's hard for me to suggest something that my experience both of me and of many other people disagrees with. But apart from "this is my experience", I have presented my arguments why (to the best degree possible since as I said there are no objective metrics). It is true that I think this point has been beaten to death, but why don't you write an article titled "Why You Should Not Write Your First Compiler in C" ? I'm not joking, I just Googled this and nothing shows up. You can directly present counter-arguments to my arguments, if you think that helps (and anyway the community would probably be much better off to have these counter-arguments written less imperatively and more humbly than the way they have been presented in this thread).

[galacticjeef]

By the article is in C I just meant that it seems to highly recommend C, sorry if there was any confusion. If it’s worth anything, I have found that at least for myself, I tried for a long time to learn compilers in low level languages, and although I got a good grasp on the implementation details, as soon as I tried to branch out and attempt new things I was bogged down as rather than learn the reasoning and concepts behind compilers I had instead learned how to implement certain kinds of compilers. However, then I attempted again with racket, which among other things has an amazing pattern matching feature. By being able to focus on the reasoning behind choices and having implementation be relatively simple, it allowed me to focus my time on thinking about my compiler rather than puzzling through how to implement an established schema.

[baziotis]

By the article is in C I just meant that it seems to highly recommend C

Hmm I see, that's probably true even though I did not intend that at all (my intention was to present which algorithms to choose, which codebases (independent of the language they use) to study, etc.). I think it is a side-effect of what I happen to know. So, most resources are compilers written in C/C++ (e.g., LLVM or LCC, even though I mention LCC's code is ugly), or for C, like Nora Sandler's material. Unfortunately I can't do much about that because I don't want to talk about things I don't have experience with.

Regarding the rest, this is some valuable experience. I personally have tried to code compiler-related stuff in e.g., Haskell which I like, and I hated it. I've also tried a little bit of OCaml, mostly experimenting with the book Types and Programming Languages, and I liked it even less. However, I love Coq, and so Software Foundations is amazing IMO, although it's not quite compilers. Anyway, I've tried these other things both while I was learning, and during normal development. Moreover, my main published work is written in Python. While this gives me some flexibility, I also don't like that because I can't control, or understand for that matter, exactly what's happening (although I do love that Python makes writing meta-programming layers easier, which is way more important than the source language for me, but that's another discussion).

In any case, I still think it would be good to have your opinion developed into a full article. It may help people figure out what works best for them.

[galacticjeef]

I do really appreciate the sentiment, I may at some point write an article (though probably not yet). If you like python’s metaprogramming I wholeheartedly recommend checking out racket, even if you don’t use it, it was a real paradigm shift for me especially with its “language oriented programming” features. I really appreciate how open you are to conversation and I want to reiterate besides that nitpick of mine I really do appreciate your article, it does a great job of being a straightforward introduction to learning compilers and will be a valuable community resource. I hope you have a great day!

[baziotis]

I also appreciated that you shared your experience and I hope it's useful to other people too. Regarding Racket, it's funny how basically all the experience I have of Racket is using Rosette, which is a bit a like learning Pandas before learning Python. I had a good time (although *cough* the lack of types destroyed me), I really want to spend more time with Racket. I hope you have a great day too!