TITLE: More on Forth and a New Compilers Course
AUTHOR: Eugene Wallingford
DATE: October 13, 2007  6:01 PM
DESC: 
-----
BODY:
<P ALIGN="right">
   <EM>Remember this as a reader--whatever you are reading<BR/>
   is only a snapshot of an ongoing process of learning   <BR/>
   on the part of the author.  <BR/>
   -- Kent Beck</EM>  </P>

Sometimes, learning opportunities on a particular topic seem
to come in bunches.  I wrote recently about
<A HREF="http://www.cs.uni.edu/~wallingf/blog/archives/monthly/2007-10.html#e2007-10-08T20_05_36.htm">
   revisiting Forth</A>
and then this week ran across an article on Lambda the
Ultimate called
<A HREF="http://lambda-the-ultimate.org/node/2452">
   Minimal FORTH compiler and tutorial</A>.
The referenced compiler and tutorial are an unusually nice
resource: a "literate code" file that teaches you as it
builds.  But then you also get the discussion that follows,
which points out what makes Forth special, some implementation
tricks, and links to several other implementations and articles
that will likely keep me busy for a while.

Perhaps because I am teaching a compilers course right now,
the idea that most grabbed my attention came in a discussion
near the end of the thread (as of yesterday) on teaching
language.
<A HREF="http://www.ccs.neu.edu/home/dherman/">
   Dave Herman</A>
wrote:

<BLOCKQUOTE><EM>
This also makes me think of how compilers are traditionally
taught: lexing &rarr; parsing &rarr; type checking &rarr;
intermediate language &rarr; register allocation &rarr;
codegen.  I've known some teachers to have success in going
the other way around: start at the back end and move your
way forward.  This avoids giving the students the impression
that software engineering involves building a product,
waterfall-style, that you hope will actually do something at
the very, *very* end -- and in my experience, most courses
don't even get there by the end of the semester.
</EM></BLOCKQUOTE>

I have similar concerns.  My students will be submitting
their parsers on Monday, and we are just past the midpoint
of our semester.  Fortunately, type checking won't take long,
and we'll be on to the run-time system and target code soon.
I think students do feel satisfaction at having accomplished
something along the way at the end of the early phases.  The
parser even give two points of satisfaction: when it can
recognize a legal program (and reject an illegal on), and then
when it produces an abstract syntax tree for a legal program.
But those aren't the feeling of having compiled a program
from end to end.

The last time I
<A HREF="http://www.cs.uni.edu/~wallingf/blog/archives/monthly/2006-05.html#e2006-05-17T15_10_03.htm">
   debriefed teaching this course</A>,
I toyed with the idea making several end-to-end passes
through compilation process, inspired by a paper on
<A HREF="http://portal.acm.org/citation.cfm?id=1121372&coll=Portal&dl=ACM">
   15 compilers in 15 weeks</A>.
I've been a little reluctant to mess with the traditional
structure of this course, which has so much great history.
While I don't want to be one of those professors who teaches
a course "the way it's always been done" just for that sake,
I also would like to have a strong sense that my different
approach will give students a full experience.  Teaching
compilers only every third semester makes each course
offering a scarce and thus valuable opportunity.

I suppose that there are lots of options...  With a
solid framework and reference implementation, we could
cover the phases of the compiler in any order we like,
working on each module independently and plugging them
into the system as we go.  But I think that there needs
to be some unifying theme to the course's approach to
the overall system, and I also think that students learn
something valuable about the next phase in the pipeline
when we build them in sequence.  For instance, seeing the
limitations of the scanner helps to motivate a different
approach to the parser, and learning how to construct
the abstract syntax tree sets students up well for type
checking and conversion to an intermediate rep.  I
imagine that similar benefits might accrue when going
backwards.

I think I'll ask Dave for some pointers and see what a
backwards compiler course might look like.  And I'd still
like to play more with the agile idea of growing a working
compiler via several short iterations.  (That sounds like
an excellent research project for a student.)

Oh, and the quote at the top of this entry is from Kent's
<A HREF="http://www.threeriversinstitute.org/TwoMoreImplementationPatterns.htm">
   addendum</A>
to his forthcoming book,
<A HREF="http://www.amazon.com/dp/0321413091">
   Implementation Patterns</A>.
I expect that this book will be part of my ongoing process
of learning, too.
-----