Re: [Haskell] Compiler Construction course using Haskell?

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
11 messages Options
Reply | Threaded
Open this post in threaded view
|

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.

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: [Haskell] Compiler Construction course using Haskell?

Larry Evans-3
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


_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

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

Chris Eidhof
In reply to this post by Derek Elkins
>> 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?

At Utrecht University, they teach excellent courses on exactly this  
subject, using Haskell. The course webpage [1] is probably a useful  
resource for you, as it shows exactly what we were thought (I  
participated in the course last year). We made heavy use of Utrecht's  
Attribute Grammar Compiler [2], which is a pre-processor for Haskell  
that allows you to very easily build programs using an attribute  
grammar. This proved to be a really nice way to do the tree  
transformations. I very much liked the idea of attribute grammars, but  
I personally don't like pre-processors very much.

Also, we targeted Simple Stack Machine as a platform. This is an  
assembly-like language that has a graphical interpreter, so you can  
actually see your code, do single-stepping, see your stack, etc. It  
proved to be quite useful. As a student, I it added a lot of  
educational value, but a real language would also be cool (e.g. Harpy  
[4]).

HTH,
-chris

[1]: http://www.cs.uu.nl/docs/vakken/ipt/
[2]: http://hackage.haskell.org/cgi-bin/hackage-scripts/package/uuagc
[3]: http://people.cs.uu.nl/atze/SSM/index.html
[4]: http://uebb.cs.tu-berlin.de/harpy/
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

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

Don Stewart-2
chris:

> >>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?
>
> At Utrecht University, they teach excellent courses on exactly this  
> subject, using Haskell. The course webpage [1] is probably a useful  
> resource for you, as it shows exactly what we were thought (I  
> participated in the course last year). We made heavy use of Utrecht's  
> Attribute Grammar Compiler [2], which is a pre-processor for Haskell  
> that allows you to very easily build programs using an attribute  
> grammar. This proved to be a really nice way to do the tree  
> transformations. I very much liked the idea of attribute grammars, but  
> I personally don't like pre-processors very much.
>
> Also, we targeted Simple Stack Machine as a platform. This is an  
> assembly-like language that has a graphical interpreter, so you can  
> actually see your code, do single-stepping, see your stack, etc. It  
> proved to be quite useful. As a student, I it added a lot of  
> educational value, but a real language would also be cool (e.g. Harpy  
> [4]).

And Language.C

    http://hackage.haskell.org/cgi-bin/hackage-scripts/package/language-c
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: [Haskell] Compiler Construction course using Haskell?

Krasimir Angelov-2
In reply to this post by Derek Elkins
Hi Johannes,

There is a similar course in Chalmers. The home page is here:

http://www.cs.chalmers.se/Cs/Grundutb/Kurser/progs/current/

There students were required to implement full parser, partial
typechecker and partial interpreter for C++ in either C++, Java or
Haskell. We used BNFC for the parser:

http://www.cs.chalmers.se/Cs/Research/Language-technology/BNFC/

which was easier for most students I think. In any way I would
recomend Happy+Alex or BNFC instead of Parsec but this is only my
personal preference.

Best Regards,
  Krasimir



2008/8/20 Johannes Waldmann <[hidden email]>:

> 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?
>
> If I really decide to do it,
> then slides (in German) will be made available.
>
> Best regards, J.W.
>
>
> _______________________________________________
> Haskell mailing list
> [hidden email]
> http://www.haskell.org/mailman/listinfo/haskell
>
>
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

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

Don Stewart-2
Similar course at UNSW,

    http://www.cse.unsw.edu.au/~cs3161/

type checker, type inference and interpreter + proofs.

kr.angelov:

> Hi Johannes,
>
> There is a similar course in Chalmers. The home page is here:
>
> http://www.cs.chalmers.se/Cs/Grundutb/Kurser/progs/current/
>
> There students were required to implement full parser, partial
> typechecker and partial interpreter for C++ in either C++, Java or
> Haskell. We used BNFC for the parser:
>
> http://www.cs.chalmers.se/Cs/Research/Language-technology/BNFC/
>
> which was easier for most students I think. In any way I would
> recomend Happy+Alex or BNFC instead of Parsec but this is only my
> personal preference.
>
> Best Regards,
>   Krasimir
>
>
>
> 2008/8/20 Johannes Waldmann <[hidden email]>:
> > 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?
> >
> > If I really decide to do it,
> > then slides (in German) will be made available.
> >
> > Best regards, J.W.
> >
> >
> > _______________________________________________
> > Haskell mailing list
> > [hidden email]
> > http://www.haskell.org/mailman/listinfo/haskell
> >
> >
> _______________________________________________
> Haskell-Cafe mailing list
> [hidden email]
> http://www.haskell.org/mailman/listinfo/haskell-cafe
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

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

Johannes Waldmann
Thanks for all the pointers. This is very useful.

On parsers: yes, LL/LR theory and table-based parsers have been
developed for a reason and it's no easy decision to throw them out.
Still, even Parsec kind of computes the FIRST sets?

And - I positively hate preprocessors.
I really want my domain specific languages embedded
because I want to use Haskell's types, functions, modules etc.
for the domain specific objects (parsers, AST walkers, etc.)

Best regards, J.W.



_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: [Haskell] Compiler Construction course using Haskell?

Johannes Waldmann
In reply to this post by Derek Elkins

> This has me worried slightly: do you intend to showcase
> monads, or do you intend to teach compiler construction?

The subject is Compiler Construction ...

Doing tree traversals via monads would, in OO-Speak,
just correspond to using some Visitor pattern for the AST.
The students know about these patterns.

J.W.


_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

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

Philippa Cowderoy
In reply to this post by Johannes Waldmann
On Wed, 20 Aug 2008, Johannes Waldmann wrote:

> On parsers: yes, LL/LR theory and table-based parsers have been
> developed for a reason and it's no easy decision to throw them out.
> Still, even Parsec kind of computes the FIRST sets?
>

No, it doesn't. That's not actually possible for monadic parsers as they
support context-sensitive languages and have no means of telling them from
context-free ones.

--
[hidden email]

"I think you mean Philippa. I believe Phillipa is the one from an
alternate universe, who has a beard and programs in BASIC, using only
gotos for control flow." -- Anton van Straaten on Lambda the Ultimate
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: [Haskell] Compiler Construction course using Haskell?

Johannes Waldmann
In reply to this post by Derek Elkins
Martin Erwig wrote (on a similar course he taught):

> * Many students did not know Haskell before, so I had to teach some
> Haskell and was forced to avoid some more advanced features, such as
> type classes and monads.

Yeah, in my case I know they don't know Haskell...

Still, I trust them to pick it up quickly, and understand type classes
(by analogy to interfaces in Java) and - they have to learn monads.
These are master students, they should be open to a challenge ...

NB: The course is declared "optional".
As a prerequisite, there is a (mandatory) course
in Principles of Programming Languages.

J.W.

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

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

Johan Jeuring
In reply to this post by Johannes Waldmann
Dear Johannes,

Besides the IPT course, we also teach a course hat used to be called
grammars and parsing. This course is taken before the compiler
construction course. In this course we deal with parser combinators,
datatypes, folds, first and follow, LL(1), and some more stuff, all
in Haskell. The lecture notes are available from the webpage for the
course:

http://www.cs.uu.nl/docs/vakken/gont/literatuur.html

The web page is in Dutch, but the lecture notes are in English.

All the best,

Johan

On 20 Aug 2008, at 21:47, Johannes Waldmann wrote:

> Thanks for all the pointers. This is very useful.
>
> On parsers: yes, LL/LR theory and table-based parsers have been
> developed for a reason and it's no easy decision to throw them out.
> Still, even Parsec kind of computes the FIRST sets?
>
> And - I positively hate preprocessors.
> I really want my domain specific languages embedded
> because I want to use Haskell's types, functions, modules etc.
> for the domain specific objects (parsers, AST walkers, etc.)
>
> Best regards, J.W.
>
>
>
> _______________________________________________
> Haskell-Cafe mailing list
> [hidden email]
> http://www.haskell.org/mailman/listinfo/haskell-cafe

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe