TITLE: Fifteen Compilers in Fifteen Weeks
AUTHOR: Eugene Wallingford
DATE: May 17, 2006  3:10 PM
DESC: 
-----
BODY:
Our semester ended a couple of weeks ago.  It was busier
than usual, for a variety of reasons, but my compiler
course was one of the enjoyable experiences.  Of course,
my students will say that my compiler course was one of
the major reasons that <EM>their</EM> semester was busier
than usual.

A compiler is usually the largest piece of software an
undergraduate CS student will write.  Some of my students
may have written other large programs, in other senior
project courses, but I doubt they've written larger, and
certainly not in smaller teams.  (Most worked in pairs.)
Several commented that they learned more just trying to
write such a large program than they had in any of my
courses.  That doesn't surprise...  It's one of the main
reasons that I think it's essential for every undergrad
to take a project course of this sort.  There is no
substitute.

After watching my students struggle to meet deadlines
and to deliver assigned functionality, I've been thinking
about using agile methods to write a compiler.  Even with
occasional suggestions from me for how to manage their
projects, students fell behind.  It is just too easy for
students to fill their time with other, more immediate
demands and watch project deadlines such as "table-driven
parser, due in three weeks" get closer and closer.

Then there were times when students made a good-faith
effort to estimate how long a task would take them, only
to be off by an order of magnitude.  The code for the
table-driven parser isn't so bad, but, boy, does that
table take a long time to build!!

Throughout the semester, I made several common suggestions,
ones that will sound familiar: take small steps through
the spec; have unit tests for each element you build, so
that you won't be so afraid to make changes.  But next
time, I think I may go one step farther and make two other
agile practices cornerstones of the course: <EM>short
iterations</EM> and <EM>small releases</EM>.  How about
a deliverable every week!?

Figuring out how best to define the stories and then
order them for implementation will be the challenge.  In
my mind's eye, I'd like for each release to create a
complete compiler, for some linguistically meaningful
definition of "complete".  Start with such a subset of
the language that we can build a compiler for it with
little or no overhead.  Then, add to the language grammar
bit by bit in ways that slowly introduce the ideas we
want to study and implement.  Eventually we need a more
principled form of scanning; eventually, we need a parser
that implements a derivation explicitly.  The issues
would not have to arise in the traditional front-to-back
order of a compiler course; why do we necessarily have to
build a fancy parser before implementing a rudimentary
run-time system?

Can this work for something like the parsing table?  Adding
grammar elements to the language piecemeal can have odd
effects on the parsing rules.  But I think it's possible.

And if I seem stuck on the table-driven parser in all of
my examples, this may be a result of the fact that I still
like for students to implement their parsers by hand.  I
know that we could go a lot farther, and do a lot more
with code generation and optimization, if we built our
parsers using a tool such as
<A HREF="http://dinosaur.compilertools.net/">
   Yacc</A>,
<A HREF="https://javacc.dev.java.net/">
   JavaCC</A>,
or
<A HREF="http://sablecc.org/">
   SableCC</A>.
But I can't shake the feeling of the value that comes
from implementing a non-trivial parser by hand.  Maybe
I'm a dinosaur; maybe my feelings will change in the
next eighteen months before I teach the course again.

Though I've been thinking some of these thoughts since
last summer, I have to give credit to Jeremy Frens and
Andrew Meneely of Calvin College, who presented a paper
at this year's SIGCSE called
<A HREF="http://www.cs.uni.edu/~wallingf/blog-multimedia/15-compilers-15-days.pdf">
   Fifteen Compilers in Fifteen Days</A>
(also available from the
<A HREF="http://portal.acm.org/citation.cfm?id=1121372&coll=Portal&dl=ACM">
   ACM Digital Library</A>).
I'm not sure I'd want to follow their course outline
very closely, but they do have some experience in
sequencing the stories for the project in a way that
introduces complexities in an interesting way.  And the
idea is just what I think we need: fifteen compilers in
fifteen weeks.
-----