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 |
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 |
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 |
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 |
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 |
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 |
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 |
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 |
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 |
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 |
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 |
Free forum by Nabble | Edit this page |