Hacker News Reader

Comment by semisight | Hacker News Reader

I wish I had a professor like you. When I asked why there was no compiler class, the answer I was given was: "compilers are a solved problem; there's no point in teaching them anymore."

Maybe it's just my school though.

View on HN

My high school guidance counsellor tried to dissuade me from taking a computer science undergraduate degree, stating that all the programs that are useful had already been written.

I can only imagine what he told the kids who wanted to become civil engineers.

That's jaw-dropping really... every student should have to experience the horrors of the dragon book.

*edit: I say that firmly tongue in cheek. The Dragon book is one of the most important pieces of CS literature ever written. It's a fine book, the subject matter is just difficult:)

I was taught compilers by one of the authors of the Dragon Book. It was one of the best courses I ever took.

Agreed. I'm taking a class right now with the dragon book (taught by Aho, actually - one of the authors of the book), and it's easily the best and most important CS class I've taken[1]. The main project for the class is to design a language and write a working compiler/interpreter for it - in all the years he's taught the class, apparently no group has failed to do this. The really tricky part is making a language that other students in your class will want to use, though, and that goes beyond the 'simple' issue of compiler structure!

I half-wish that there would be a way to teach a compilers class as the second class in a CS track (ie, right after the intro class), but the problem is that it just requires too much familiarity with the details in order to impose upon most beginner/intermediate students, even if a few really interested ones could potentially handle it.

It might be easier if you started off with Scheme and then went from there (a la SICP), but even then, you'd miss a lot of the more fundamental concepts assumed in the Dragon book that really just need a lot of time to be digested.

[1] Alright, there's probably a three-way tie for 1st, but it still counts. My education would not have been complete without it; I highly recommend the Dragon book to anybody who has the time and interest.

I interviewed Professor Aho a few years back; I'm a little jealous I was never fortunate enough to take that class. It's likely to be one of the most practical classes in all of computer science anywhere.

(I won't give away the punchline for the class. I don't know how far along you are on the project.)

My compilers class was a nightmare (and we used the Dragon book). I had hoped a compilers course would actually teach about the full process by which a text file becomes executable 1s and 0s. Instead it was a months-long torture of parsing text. Regex to NFA, NFA to regex, regex to DFA, NFA to DFA, DFA minimization, LL(1), LR(0), SLR(1), LR(1), LALR(1), along with memorizing all the rules governing which grammars are amenable to which parser, and working through all of the preceding by hand. And then finally about a week of teach-yourself-LLVM.

I don't know if "compilers are a solved problem", but I'm pretty damned sure that the only people who need to know that much about text parsing know who they are, and would be able to reference it when needed. As an undergraduate course, it was utterly worthless.

I took that class from the other instructor, who had us use OCaml instead of Java (as I presume Aho still uses.) The Dragon book was interesting, but, for the most part, we were able to get on from the in-class slides.

I don't think there's anything wrong with having Discrete Math, Data Structures or Computer Science Theory as pre-requisites for PLT or a compiler class. However, I doubt the necessity of OO Programming & Design and (so-called) Advanced Programming.

The Dragon book may be a fine book but it is mainly a book on parsing, not on compilers. You first learn about control flow graphs in chapter 9! Most courses probably won't even get that far. The parts that are about compilation are very old fashioned, essentially a book about "how to compile Fortran to inefficient code like they did in the '60ies".

It would be great if there was a book on modern compiler techniques, including SSA, abstract interpretation, compiling high level languages, pointer analysis, compiling dynamic dispatch, garbage collection and closures, etc. Probably the closest are Appel's compiler books.

Some bigger schools now teach with their own set of materials that the professors put together. I think it might be precisely because of this reason.

http://www.cs.princeton.edu/~appel/modern/ml/

http://store.elsevier.com/product.jsp?isbn=9780120884780

Two of the most important books I own.

Also, thank you for tearing down the dragon book -- I was going to do the same myself.

The dragon book is outdated on parsing, too. It's from a time where single-pass parsing and compilation was sometimes necessary because you didn't have enough memory (or time) to do multiple passes. It certainly doesn't have anything on packrat parsing. It is a historical book -- I would recommend it for no serious purpose (even pedagogical) these days.

I have been using Kenneth Louden's book on compiler construction and as a beginner I find it extremely helpful so far.

> http://store.elsevier.com/product.jsp?isbn=9780120884780

I don't trust this book; it has an error that I reported to the authors twice but never heard a word back (or any note of the error in their list of errata).

Here's what I wrote to them:

  Subject: Errata for "Engineering a Compiler"
  Date: Sat, May 26, 2007 at 8:12 PM

  Hello,

  I noticed that your section on DFA minimization is labeled
  "Hopcroft's Algorithm," but doesn't seem to describe the
  algorithm explained by Hopcroft in his 1971 paper [0]. Your
  algorithm appears to be n^2, where Hopcroft's is n log n. David
  Gries gave a somewhat more digestible presentation of the same
  algorithm in a follow-up paper in 1972 [1].

  Hope this information is useful!

  Sincerely, <me>

  [0] John E. Hopcroft. An n log n algorithm for minimizing states
  in a finite automaton. Technical Report: CS-TR-71-190, 1971.
  Available online at
  ftp://reports.stanford.edu/pub/cstr/reports/cs/tr/71/190/CS-TR-71-190.pdf

  [1] David Gries. Describing an algorithm by Hopcroft. Acta
  Informatica, 2(2):97-109. Online reference:
  http://www.springerlink.com/content/r5631549671g6251/

> The dragon book is outdated on parsing, too. It's from a time where single-pass parsing and compilation was sometimes necessary because you didn't have enough memory (or time) to do multiple passes. It certainly doesn't have anything on packrat parsing.

I'm pretty sure that all production compilers do one-pass parsing even now because of efficiency concerns. I would be very surprised if any production compiler used packrat parsing which takes O(n) memory.

I did not like the Dragon book either. I feel like it taught me nothing and was difficult to read and comprehend. I had to find other sources of explanation at times when I was doing this. It seemed to be more a thought and theory book if I remember.

This was at least 6 years ago though, so my memories are a little cloudy.

Pretty sure that's just your school.

In the article, he mentions that the students don't get to compilers till 4th year. I find that a little strange. Some elementary understanding of how a high-level programming language translates to executable code is quite useful in other courses in a standard CS curriculum. At my school, in 2nd year we write a compiler for a tiny subset of C++ to MIPS assembly, and in 4th year you write a compiler for Java with a great deal of optimization.

They get some basic understanding about the compilation process at some classes through the first two years.

When I attended my CS course, in the 3rd years I got some understanding about programming language structure and learned about compilers at the end. It's cool that you can learn about that earlier.

We have a class on compilers at my university, but it's on the 4rd year. Creating a compiler/interpreter when you are just starting programming would be a big challenge.

@dovyski: it's nice to see this coming from a brazilian university -- I'm from UFABC, São Paulo

It's a big challenge indeed. About the compiler course, it's the same at UFFS: 4th year.

Thanks and nice to see a brazilian fellow around here :)

Whoaa that's pretty bad. I'm currently taking a computer architecture class in which we have to design and implement a working superscalar out of order processor in HDL. Even in that class, which is strictly focused on computer architecture, our professor stresses how important compilers are. Sure compilers have become pretty good at optimizing code but there is so much room for improvement especially as we increasingly move to multicore systems. Your professor really must be living under a rock...

Which school do you go to?

Compilers seems like a pretty standard CS course at most schools.

How the PLsy courses are split varies a lot. Where I went (Harvey Mudd), compilers was optional and not taken by most students, but there were two required Programming Languages courses, which involved parsing, ASTs, interpreters, tree transformations, and some other things you might otherwise find in a compilers course, but with less of a low-level flavor (no code-gen) and more of a PLs flavor.

The content of such a course also varies by university. I recently came across some university that did offer a compiler course, but it was all theory. Being a geek, I didn't really like that.

Most UK universities don't teach compilers for CS.

Thank you!

Sounds like a terrible place to be honest. With that mentality, in 60 years (when current compile designers are dead), nobody will know anything about compiler architecture.

On the third year at my university, there's a course centered around writing a Java compiler.

In 60 years, the best compiler writers will be computers. The singularity is near.

Reply on news.ycombinator.com