[Haskell-cafe] Re: [Haskell] Compiler Construction course using Haskell?

[Derek Elkins]

On Wed, 2008-08-20 at 16:03 +0200, Johannes Waldmann wrote:
> Hello.
> 
> 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?

[I've replied to Haskell-Cafe which is a better list for this
discussion.]

2 & 3 are going to have different trees so using the same tree traversal
code would require some finesse, though the code for 2 should only need
extension not change.

One thing you may want to look at is attribute grammars which can be
cast into a monadic framework and gives a natural example of using the
backward state monad and allows you to connect to other formalisms used
for compiler construction.

Another possibility is abstract interpretation.  Both code generation
and type checking can be viewed as examples of abstract interpretation
(as well as, of course, actual interpretation.)  Also many analyses fit
into the model of abstract interpretation.

I'd also recommend transforming the initial AST to some intermediate
form before doing 2-5.  Not only is this a virtually universal practice,
but it will the later stages, particularly the interpreter and the code
generator easier to write and, in the code generator's case, able to
produce better output.

Ultimately, trying to have the same code produce all of these is going
to lead to some compromises.  You are either going to have to forsake
some quality in the output, or you are going to have unnatural or, at
least, non-trivial implementations of some the functions.  The
recommendation to for the use of a intermediate language mitigates this
somewhat.