Why take a compiler course? (2010)

Taking the compiler course changed my career from day 1.

In my first job, back in the late 90s, I was working for a company that, having taken their biggest customer yet, had to split a very large C monolith into chunks that could run on separate servers. The architecture team of the company found all the places where the system should be cut, but that let them with hundreds of functions that had to be replaced with asynchronous calls relying on a queuing system. I was hired into the team that had to stub those hundreds of functions, type up serialization and deserialization for all the hundreds of data structures involved, and gluing it all together. So they had budgeted for 6 months of typing from a team of relatively new developers.

As you might expect, that's not how anyone wants their career to go, but I had taken the compiler class. So I knew I could parse all the header files for the functions we needed to replace, parse the data structures along with it, and just generate all the boilerplate away. My dev lead thought there's no way we could do this, but his manager decided that, at works, giving me two weeks to try it would be a great opportunity to teach the new hire the limit of his knowledge. But as anyone that has taken the compiler course knows, parsing boring C structs and header files isn't magic. So two weeks later, the project was done, and it was working.

As you might imagine, the dev lead, in his 40s, couldn't handle the results all that well, and left quickly. So I went from being stuck writing boilerplate from month to a quick promotion to team lead in under a quarter, all thanks to the compiler course.

I'm a self-taught programmer, starting in the mid-70s, and learned how to write compilers in a way that probably wouldn't work nowadays, but was great fun back then.

The first thing I'd usually do when starting on a new architecture was write a disassembler. In the late 70s, I was mostly programming in 6809 assembly, usually in Microware's OS-9 operating system. Microware released a Pascal compiler, so I ran my disassembler over that. Turns out the compiler was self-hosting, written in Pascal, and the compiler output was almost completely unoptimized. So I decompiled the compiler back to Pascal by hand, just to see how it worked. I obviously had waaaaay more free-time back then.

I eventually read the green Dragon book (Aho & Ullman, Principles of Compiler Design), and ended up at Microsoft on the C/C++ team in 1991. Over the years, I've written several domain-specific languages (DSLs), small languages for some limited purpose. That early exposure to lexing, parsing, and error detection was invaluable.

I was in grad school, 77-83. The first year was part time at NYU, and then I went back full time elsewhere, for a PhD.

In that one year at NYU, I took two compiler courses, from RBK Dewar, of Spitbol and Ada fame. My specialty is not languages or compilers, but those courses were incredibly fascinating, and the exposure to the topics I learned has been useful throughout my career.

- I learned about lexing and parsing. I no longer remember the details of LALR, for example. But I understand the basic ideas well enough to construct lexing/parsing software whenever I need it, often using parser generator tools, but also rolling my own on occasion.

- I learned about code optimization, which is a fascinating topic. At the time, Dewar was working on SETL, a set-oriented language. And I remember the power of having sets as a builtin type, and how powerful that was for expressing flow analysis, for example. Those ideas combined nicely with what I later learned about relational algebra, and query optimization. (Codd's paper on the relational model was only seven years old when I started grad school!)

- Exposure to the ideas of interpreters and code generators, and even more fundamentally, the idea of code as a thing that can be manipulated programatically, has been useful throughout my career.

- Oh, and by the way, Dewar was a great teacher.

My unexpected side benefit: some compiler error messages became comprehensible.

Oh, an lvalue is required? Since I now actually know WTF that means, I can deal with it.

It also cleared up a situation that had always confused the hell out of me: sometimes I'd compile and get 1 or 2 errors, so I'd make corrections and try compiling again, but then I'd get 8 or 10 errors! Seeing that whatever I did made everything much worse, I'd conclude those most not be the right corrections, and I'd feel lost and maybe even get stuck.

After taking compilers, I finally understood why: compilers have phases, and my corrections allowed the parsing phase to complete, which meant the semantic analysis phase could happen and give me errors. So for example, if I finally fix enough syntax errors that the compiler can tell I've written a function with some variables in it, then it can start giving me errors that they're not the right types.

The big value I got from taking compilers as an undergrad was that it brought everything together. It's basically where computer architecture, theoretical CS, and software engineering (and a hint of systems security) collide in a very practical manner. Compilers make it very clear how all those seemingly disparate topics apply in real non-trivial systems.

We use gcc/javac/etc almost daily and having some understanding of what your toolchain is likely to be very beneficial. Here are a few things I've done with my compiler knowledge:

1. Wrote a simulator of sorts for a 68xx CPU. User passed in assembly files and I simulated the execution and spat out cycle counts. The real-time application had a fixed time window it could not exceed. I did this in my first year out of college with compilers fresh on my mind.

2. Wrote an automated test tool for a proprietary protocol. The protocol had the usual opcodes but they could only be played in a certain order (cannot send B before C or can send B any number of times and have it be idempotent). The QA engineers were doing this by hand. I asked them if they could automated the test case generation and they looked at me as though I was an idiot. I developed a tool with its own simplified grammar that they could use to build test cases which exercised all combinations/permutations of the opcodes. Saved us a ton of time and made the developers more productive.

3. My hackiest project was an SGML parser that was used to generate hypertext documents. Tech writer wrote docs in FrameMaker. My hacky parser found the places where the TOC and the Index could be linked and inserted hypertext links. Net result is we had a document that could be printed and viewed online. Think 1993/1994.

I've sat with a number of engineers who thought the compiler was wrong and sat down and looked at the assembly with them and mapped it back to C only for them to realize the bug was in their code.

Compilers are fun. You should take a compiler course just for that!

Compiler construction is a part of practical computer science that includes

- formal languages, Chomsky hiearchy and automata (DFAs, NFAs)

- algorithms & data structures (syntax trees, symbol tables & hashing)

- parsing algorithms

- asymptotic complexity (of automata recognition/acceptance and parsing algorithms)

- software architecture (single pass versus multi-pass, abstractions)

- operations research (graph coloring based register allocation)

- assembler & automatic code generation

- virtual machines & interpreters

It is a field where theory and practice come together beautifully (and works like the Aho et al. ¨Dragon Book¨ or Wirths ¨Compilers¨ are masterpieces that lucidly lay things out so after reading Chapter 2 of the former, or all of the latter short volume (barely 100 pages), a compiler is basically demystified to any undergrad).

While one may not be interested in writing compilers, the techniques are applicable elsewhere.

For example, I once wrote a date/time "compiler" that could read dates and times in various human formats and construct a time_t from it. It's a giant mess if you approach it in an ad-hoc fashion. But if you approach it from a lexing then parsing standpoint, things work a lot better.

I see too many attempts at reading a textual data format that are done ad-hoc. Even worse are the attempts to design a data format where the designer clearly had no awareness of lexing and parsing - the format is just one ad-hoc kludge after another.

Uni CS lecturer here. One of my mentors in grad school was the compiler professor, and I learned a lot from him. I also got a chance to actually teach compilers for the fist time last year and it was one of the most difficult courses I have ever taught. Used the dragon book and had my students create their own lexer/parser based on an invented language that I came up with.

Compilers is one of the few topics that none of my colleagues seem care about, but IMHO it's so very important to learn how to do. In my Uni, the course only gets taught once every few years (it didn't help that our last department chair didn't care for the course at all and never scheduled it).

I count the day that I finished my LL(1) parser and lexer for my own compiler course as a student as the day I "earned" my chops.

Edit: Since there seems to be some discussion on this thread, I'll throw in the actual project that I gave my students (warts and all). https://github.com/agiacalone/cecs-444-semester-project

I've had the chance to build parsers for work.

Once for a templating engine for SQL (taking values from the environment and using them queries). This was really nice for productivity and an intern could churn out dozens of reports a day. That was written with javacc.

Another time by using a parser (written with Antlr) to extract bits of PLSQL packages (procedures, functions) and move them from one environment to another without having to send the whole package.

Although this type of job is rare, it can be really useful when it shows up.

If you are interested in modern compiler infrastructure that subsumes a lot of recent PhD level research topics, I can highly recommend MLIR.

It's under the LLVM Foundation umbrella.

If you just want to deal with lexing, parsing, and interpretation (from scratch) for a reasonably complex class-based language, I recommend doing the (free) online book Crafting Interpreters.

The second half of that book re-implements the same language in C with garbage collection and a fast byte code interpreter.

IMO compilers are a bit like kernel development in that the real learning was the friends you made along the way, rather than actually being able to understand how a compiler works, which is a nice side effect. For example, when you write an OS you learn a lot about how code interfaces with hardware. A compiler is many people's first and only introduction to soundness and formal analysis. Being able to put on the hat of a compiler author can be useful in many fields that have nothing to with compiler development, and that's even if you go beyond "I just want to see what my code is being transformed into".

If you're interested in compilers and language implementation, it may not be obvious, but one needn't be a university student or devote a semester to the topic.

Taking a four-day compiler course[1] (now five days) whetted my appetite for implementing languages and learning new ones, and led to a number of toy language projects. Also mentioned here, the book Crafting Interpreters is wonderful.

The world may not need many more programming languages, but making your own is a heck of a lot of fun. I find it especially satisfying when tests written in the new language start to surprise me by already passing, because enough of the language is working.

[1] http://www.dabeaz.com/compiler.html

I did not take a compilers class when I was in college. Many years later, feeling the lack, I bought the Dragon book. I didn't make it past Chapter 4 because I was inspired to write a new library and tool, which then brought me a modicum of career success.

Regehr is right on the money here: parsers and interpreters are everywhere. Once you learn how approachable and applicable they are, you can solve problems faster and better.

I now always recommend to college interns that they take their CS department's compilers course their senior year (along with their English department's Shakespeare course).

I did not have a compiler course at university but I talked on r/programminglanguages discord and eatonphil's discord and I learned how to create a simple expression compiler in Python.

You can run the code here:

https://replit.com/@Chronological/Compiler3

It's ~400 lines of code and it compiles the following AST

  program = Main(
    [
      Assign("a", LiteralNumber(5)),
      Assign("b", LiteralNumber(6)),
    
      Println("Value is %d",
              Mul(Add(Reference("a"), LiteralNumber(7)), 
              Add(LiteralNumber(8), Reference("b")))),
    Println("Hello world %d", LiteralNumber(10))])

Or in other words, the following expression:

   a = 5
   b = 6
   (a + 7) * (8 + b)

If you run

   python3 main.py > assembly.S
   gcc -o assembled assembly.S
   ./assembled

You should see

  Value is 168Hello world 10

It's barebones but I think it's the basis for a compiler.

Compilers also show an application of pipelines which can be used architecturally at all levels.

I’m a happy coder if I can translate my problem to a pipeline problem. Each pipeline step can be modelled as a pure function. Each artifact between each step can be inspected and cached. Pipeline failures can be resumed at the last valid artifact

Despite the fact that my algorithms course was ostensibly about learning how to come up with efficient solutions to various problems, the two courses I took that have helped me the most with writing performant code in my career were my compilers course and my architecture course. The compilers course gave me a much stronger understanding of what actually happens when running a line of code I wrote and helped me understand better what types of optimizations could potentially be performed based on the way I write an algorithm, and the architecture course taught me about how a modern CPU actually works with regards to caching, out-of-order processing, branch prediction, etc.

On the other hand, the types of things we discussed in my algorithms course felt very hit-or-miss with regards to whether they actually felt useful or not. I'm not just talking about high-level abstractions that can miss important details in the real world like "memory can be accessed in constant time" either, but solving problems that were so contrived to the point of being almost implausible. The example I always remember is that in one of our problems sets, we were asked to write an algorithm that sorted an array of size N with each element within K indices of the correct sorted position in O(n*log(k)) time. I can't think of any situation where I'd have data so large with a small enough strict upper bound on K that such an algorithm would be necessary, but even if I did find myself in that situation, that's the exact type of input that the naive quicksort implementation would perform more efficiently on!

Maybe someday we'll have powerful enough tools that we can generate code that's performant without needing to do it ourselves, but at least for now, writing code that a computer executes efficiently is much easier when you actually understand what's being run on the computer and how it runs it, and a compilers course is a great way to start learning about the first half of that.

I really enjoy low level development... things like OS and compiler design. Emulation, simulation, etc. It's sad there's very little place for these "hobbies" anymore, other than that, a hobby.

I have done my share of compilers work a long time ago, my masters thesis was on this topic.

The article mentioned a very important but not well known aspect right at the end which is compilers is not a homogeneous topic but has a fairly independent parts. Front end, optimizers, and target code generation. I dabbled little bit in optimizers and a lot in target code generation. It was quite fun to figure out how to produce optimal machine instructions, or use as few registers as possible etc. Along the way I also got to learn a bit about the OS because one has to know an executable file’s layout, how to utilize heap, make sure not to over run stack etc.

And some fun algorithms too, such as a smart way to traverse tree by pointer reversal to avoid recursion as one can’t use recursion (extra space) while garbage collection.

I think it’s completely insane that you can get a computer science degree without both a compilers course and a computer architecture course. It’s entirely normal for a developer to start their career without really knowing how code becomes assembly or how a computer processes assembly. That’s wack.

My two answers - based also on personal experience - would be:

1. If you are ever concerned with code performance, you need to know what the compiler (/interpreter) is doing with your code. With a compiler course, you'll get a basic understanding - enough to later actually look at what the compiler is doing with your real-life code.

2. If you write a software system which can handle computation tasks that are not fully known at compile-time - such as user queries in some domain-specific language - then you are likely to end up implementing a compiler in your software system. If you haven't learned about compilers, you'll (a.) may fail to realize that and (b.) are likely to do it more poorly than if you have.

---

My beef with compiler courses, though, is the excessive focus on parsing. Text parsing, look-ahead grammars etc may be interesting in themselves, but IMHO they're mostly self-contained and not what you will be concerned with in the life-scenarios I've described above. I would have liked, in hindsight, to have more time devoted to optimization selection, passes and what goes in each of them, optimization work on the AST vs work on the IR etc.

>why the hell should I take an electromagnetism course as a physics undergrad? I want to work in fluid dynamics dammit!

unfortunately there are too many people who think a CS curriculum should be an advanced coding bootcamp instead of a place where you actually explore how your software works

I took the compiler class at Harvard extension school, after being a developer for a long time. I learned so freaking much. It’s such a hard course since you write a C compiler basically from scratch but it was without a doubt the best learning investment I ever made.

Compilers are like puzzles to be solved. They are so deeply coupled internally and so grounded in pure logic that in many cases, features of the languages implement themselves as the logical consequence of the way the compiler it's constructed.

Learning them also teaches some skills on how to subdivide the solution to a really complex class of problems into comprehensible chunks.

Heck, there are many seemingly unrelated problem domains that can borrow solution strategies from compiler design and implementation.

It definitely is a nice tool to have in your tool belt.

In lieu of this, Nand2Tetris [1] is an absolutely great online, free course where one can go through all of a computer's abstractions - logic gates to an assembler to a bytecode compiler to a stack based virtual machine with an interpreter and an operating system with display, I/O, etc, building everything along the way yourself.

The hardware stuff is in a simulator of course, but that doesn't take away from the gold mine of revelations one gains from going through this course.

The community is great as well, so many people did amazing things like build entire ray tracers in their own computer. Although I stopped at a sudoku game, seeing all of that is so good.

[1] https://nand2tetris.org

As a Mathematics undergraduate I am not allowed by my university to officially take (and receive credit for taking) most non-beginner Computer Science courses, including Compilers. At least I'm allowed to attend the lectures and cram it in alongside my other pure math classes!

In terms of cost/benefit, I think it makes way more sense to learn to think in terms of "algebras", and how to create both internal and external DSLs in a host language. I've found it incredibly helpful to have an algebra-first approach as I model a (complex) domain and service interactions. Being able to write business logic as the composition of algebraic actions in several lower-level services, along with interpreters just feels great.

Of course this overlaps strongly with particular aspects of compilers, but I find that external DSLs, which is where the overlap is greatest, are the tool that I reach for least often and that elicit the greatest resistance from fellow engineers.

I have noticed that the best developers I have ever worked with knows how to write a compiler. And the not-so-great developers don’t. It might just be a random correlation of course. But perhaps not?

How can a compiler course not be requeried for a comp.sci degree? We had that. And i’m surprised others do not.

See also https://steve-yegge.blogspot.com/2007/06/rich-programmer-foo...

I’m currently in a part time masters program for fun and taking the compilers course. I’m sure John’s experience is different than mine, but it seems the question should be put to universities. The professor of my course, by his own admission, hasn’t studied compilers other than his undergrad decades ago and as far as I can tell was assigned the course to teach. As a result the syllabus is relatively dates. I think I’m 8 weeks in and we’ve only discussed parsing theory. As far as I can tell there won’t be time for detailed study of code gen, optimizations, type checking, etc.

It wasn’t until I took a compiler course that I truly understood how important Noam Chomsky is.

I’d love to learn about compilers. I’m a self taught programmer; what books or online courses would folks here recommend ?

I think there is a more general argument to be made than the one about predicting compiler optimisations. Being familiar with how a compiler typically works allows me to use one more fluently in various ways. For example, predicting and fixing compile errors, because I know roughly what the compiler will be looking for.

It will teach most of the good programming and software engineering practices that apply to any nearly any project.

I've written a compiler that people actually use[1]!

Studying compilers at university was highly beneficial. Before that course the code was a mess…

[1] https://ltworf.github.io/relational/

(2010), though as relevant as ever

Anyone has suggestions for taking such course (books, websites etc.)? During my studies there was no compiler course on my university (which is saddening). I would also like to find some reputable OS internals course or book...

Let’s be honest, there is little benefits to take a compiler course in 2023 (best one is to satisfy curiosity).

1/ there isn’t much to know about parsing and any good compiler course won’t spend too much time on it anyway

2/ and 3/ these points are not really about compilers in general and more about C compilers. You can also learn that trivia independently.

Compilers are easy. The concurrent garbage collector is where the challenge begins, nowadays.

Shameless plug for my compiler class, fully available on YouTube: https://norswap.com/compilers/

Some of the best programmers have come across had their origins in OS and compilers. This is where the real programming and fundamentals are built.

just make a compiler. same result, less time, more learning.

yes you should be able to "just do it" nothing involved is hard, everything i needed i had by age 14 in the 1990s without the internet. this means you have it too.

Anyone know of any good free courses?