Re: [Haskell-cafe] Re: [Haskell] Compiler Construction course using Haskell?
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 Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: [Haskell] Compiler Construction course using Haskell?
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 Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: [Haskell] Compiler Construction course using Haskell?
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 Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: [Haskell] Compiler Construction course using Haskell?
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 Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: [Haskell] Compiler Construction course using Haskell?
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 Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: [Haskell] Compiler Construction course using Haskell?
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 [EMAIL PROTECTED]: 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 [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: [Haskell] Compiler Construction course using Haskell?
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 [EMAIL PROTECTED]: 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 [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: [Haskell] Compiler Construction course using Haskell?
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 Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: [Haskell] Compiler Construction course using Haskell?
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 Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: [Haskell] Compiler Construction course using Haskell?
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. -- [EMAIL PROTECTED] 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 Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: [Haskell] Compiler Construction course using Haskell?
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 Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
