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

Larry Evans cppljevans at suddenlink.net
Wed Aug 20 13:55:32 EDT 2008

On 08/20/08 11:43, Derek Elkins wrote:
> 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.

Could you give some examples or links or references?

> 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.

Links or references?

I'd also would like to see First and Follow sets:


calculated in haskell.  I'd think it would be natural since,
AFAICT, the calculation of the First sets is a homomorphism
on the algebra of grammar expressions.  IOW

   FIRST( x <|> y ) = set_union(FIRST(x),FIRST(y))

and I *think* maybe a similar definition can be made
for the sequencing operator.  Since I've seen haskell
associated with algebras and expecially monads, I guess
haskell would be especially adept at this.

WARNING: I've not written a line of haskell code.


More information about the Haskell-Cafe mailing list