[Haskell] Compiler Construction course using Haskell?

Norman Ramsey nr at eecs.harvard.edu
Thu Aug 21 22:46:00 EDT 2008

 > I plan to give a course in compiler construction,
 > using Haskell as the implementation language
 > (not as source or target language).
 > Something along these lines:
 > 1. combinator parsers (Parsec),
 > 2. simple interpreter (arithmetical expressions)
 > 3. add algebraic data types, functions
 > 4. type checker
 > 5. code generator.
 > Ideally, 2..5 would be using the very same tree traversal code
 > and just change the monad for evaluation.
 > Any comments appreciated. Have you given such a course? Taken?

In Fall 2006 I gave a graduate course in advanced functional
programming in which the default project was a compiler from a
functional language of the student's own design to the 2D circuit
language invented by the Cult of the Bound Variable.  The project was
primarily an excuse to read papers about parsing combinators,
polymorphic typed defunctionalization, A-Normal Form, generics for the
masses, linear types, and so on, and to implement all that stuff in Haskell.

This all worked out tolerably well but would need a lot of polishing
before I would want to use the project again.  However I can say that
I found it very pleasant to write the compiler in Haskell.

Prepare for your students to have difficulty figuring out exactly what
monad to use where and also to have difficulty exploiting type
classes.   Also, it's not clear what you plan for register allocation
or what machine you're intending to target.  Also not clear how you
plan to deal with memory management---if you have first-class, nested
functions in the source language, you pretty much have to have a
garbage collector.  If I were in your shoes, these are the questions
I'd be thinking about.


More information about the Haskell mailing list