[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?
[snip]
I'd also would like to see First and Follow sets:
http://www.jambe.co.nz/UNI/FirstAndFollowSets.html
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.
-regards
Larry
More information about the Haskell-Cafe
mailing list