TITLE: Just a Course in Compilers
AUTHOR: Eugene Wallingford
DATE: January 14, 2006 3:29 PM
DESC:
-----
BODY:
Soon after I arrived at UNI, my colleague Mahmoud Pegah
and I were given the lead in redesigning the department's
CS curriculum. We were freshly-minted Ph.D.s with big
dreams. We designed a curriculum from scratch based on
the ACM's Computing Curricula 1991 guidelines.
In a move of perhaps subconscious rebellion, we called
one of the upper-level electives "Translation of
Programming Languages". This course sat in the position
usually occupied by the traditional course in compilers,
but at the time we thought that name too limiting.
After all, we were Smalltalkers, and our programming
environment used a blend of compilation of interpretation,
a powerful VM, and all sorts of language processing
elements. We were also Unix guys, and the Unix world
encourages stepwise transformation of data through
pipes made up of simple processors.
Ever since, we have had to explain the name "Translation
of Programming Languages", because no one knows what
it means. When we say, "Oh, that's like a course in
compilers", everyone nods in satisfaction. Most then
say, "Does anyone still write compilers any more?"
But I still think that our name choice better reflects
what that course should be about, and why it is still
important as more than just a great programming experience.
The rise of refactoring as a standard programming practice
over the last 5-7 years has caused a corresponding need
for refactoring tools, and these tools rely well-known
techniques from programming languages and compilers.
I'm certainly glad that someone taught the folks behind
IntelliJ IDEA
and
Eclipse
learned how to write language-processing tools somewhere.
This semester, I am teaching the "compiler course",
Translation of Programming Languages. We finally have
this course back in the regular rotation of courses we
offer, so I get to teach it every so often. (We last
offered it in Fall 2003, but we plan to offer it every
third semester for the foreseeable future.) I am
probably more excited than my students!
I thought long and hard choosing a textbook. To be
honest, I would really have liked to use Niklaus
Wirth's
Compiler Construction.
I love small books with big lessons, and Wirth didn't
waste any words or space writing this book. In 173 pages,
he teaches us how to build a compiler from beginning to
end -- and gives us the full source of his
compiler, describes a RISC architecture of his own design
for which his compiler generates code, and gives us full
source code for a simulator of the architecture. Boom,
boom, boom. Of course, he doesn't have a lot of time
for theory, so he covers many ideas only at a high level
and moves quickly to practical issues.
Why not choose this book? Well, I had two misgivings.
First, I would have to supplement his book with a lot
of outside material, both my own lecture notes and other
papers. That's not a major problem, as I tend to write
up extensive lecture notes, and I rarely follow big
textbooks all that closely anyway. But the real killer
was when I went to Amazon to check out the
book's availability
and saw:
4 used & new available from $274.70
We may be able to get by on four copies, but... $274.70?
The standard text is, of course,
Dragon book.
There are plenty of copies available
at Amazon,
and they run a relatively svelte $95.18. (The price of
textbooks these days is a subject for another blog
entry, another day.) But I have always felt that the
Dragon book is a bit too much for juniors and many
seniors, who are my primary audience in this course.
I do not think that I am contributing to the dumbing
down of our curriculum by not using this classic text;
indeed, I will draw many of my lecture material from
my experiences with this book. But a 15-week course
requires some focus, and I don't think that most of
our undergraduates will get as much from the course
as they might if they get lost in the deep swirls
of some of Aho, Sethi, and Ullman's chapters.
I finally settled on Louden's
Compiler Construction: Principles and Practice,
with which I have had no prior experience. It seems
a better choice for my students, one they might be able
to read and learn something from. We'll see.
I learned a few lessons teaching this course in Fall
2003. One is:
less content.
If I try to cover even a significant fraction of what
we know about scanning, parsing, static analysis, code
generation, and optimization, my students won't get a
chance to experience building a compiler from beginning
to end. This robs them not only of understanding the
compiler material at a deeper level but also of the
occasional pain and ultimate triumph of building a
non-trivial program that works. A 15-week
course requires focus.
A 15-week course in translating programming languages also
requires a relatively small source language. In my previous
offering, the language the students compiled was simply
too big, but in the wrong ways. You don't learn much new
from making your scanner and parser recognize a second or
third repetition construct; you mostly find yourself just
doing more grunt work. I'd rather save that time to get
deeper into a later stage of the compiler, or to discuss
the notion of syntactic abstractions and how o preprocess
a second repetition construct away.
That said, I do want students to do some of the grunt work.
I want them to build their own scanners and parsers. Sure,
we use parser generators to write these components of most
compilers these days, but I want my students to really
understand how some of these techniques work and to see
that they can implement them and make them fly. I remember
the satisfaction I felt when I wrote my first LL parser
and watched it recognize a simple sorting program's worth
of tokens.
Last time I used a source language I home-brewed from a
colleague's course. This time, I am going to have my
students process a subset of Oberon, based in part on
Wirth's now out-of-print book. It strikes a nice balance
between small enough and large enough, and has a nice
enough syntax to work with for a semester.
Now that I have administrative duties, I teach only one
course a semester. The result is that I get even more
psyched about the course, because it is my best chance
to get my hands dirty in real computer science during the
term, to think deeply in the discipline. It is also gives
me a chance to write code. The thing I missed most last
semester in my first semester as head was having more time
to program. This course offers even more: a chance to get
back to a recently-dormant project, a refactoring tool for
Scheme. So, I'm psyched.
-----