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.