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 their 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: short iterations and small releases. 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 Yacc, JavaCC, or SableCC. 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 Fifteen Compilers in Fifteen Days (also available from the ACM Digital Library). 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. -----