Compiler Construction course using Haskell?
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.
I plan to give a course in compiler construction, using Haskell as the implementation language (not as source or target language).
This might be of interest: http://www.cs.nott.ac.uk/~nhn/G52CMP/index.html
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.
This has me worried slightly: do you intend to showcase monads, or do you intend to teach compiler construction? Just wondering, Claus
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?
In Fall 2006 I gave a graduate course in advanced functional programming in which the default project was a compiler from a functional language of the student's own design to the 2D circuit language invented by the Cult of the Bound Variable. The project was primarily an excuse to read papers about parsing combinators, polymorphic typed defunctionalization, A-Normal Form, generics for the masses, linear types, and so on, and to implement all that stuff in Haskell. This all worked out tolerably well but would need a lot of polishing before I would want to use the project again. However I can say that I found it very pleasant to write the compiler in Haskell. Prepare for your students to have difficulty figuring out exactly what monad to use where and also to have difficulty exploiting type classes. Also, it's not clear what you plan for register allocation or what machine you're intending to target. Also not clear how you plan to deal with memory management---if you have first-class, nested functions in the source language, you pretty much have to have a garbage collector. If I were in your shoes, these are the questions I'd be thinking about. Norman
On Fri, Aug 22, 2008 at 02:46, Norman Ramsey <nr@eecs.harvard.edu> wrote:
In Fall 2006 I gave a graduate course in advanced functional programming in which the default project was a compiler from a functional language of the student's own design to the 2D circuit language invented by the Cult of the Bound Variable. The project was primarily an excuse to read papers about parsing combinators, polymorphic typed defunctionalization, A-Normal Form, generics for the masses, linear types, and so on, and to implement all that stuff in Haskell.
As a student, I find this very interesting. Would you happen to have a syllabus or other course material (list of papers, assignments, etc.) available online? cheers, Arnar
On Fri, Aug 22, 2008 at 02:46, Norman Ramsey <nr@eecs.harvard.edu> wrote:
In Fall 2006 I gave a graduate course in advanced functional programming in which the default project was a compiler from a functional language of the student's own design to the 2D circuit language invented by the Cult of the Bound Variable...
.... Would you happen to have a syllabus or other course material available online?
Yes: http://www.cs.tufts.edu/~nr/cs252r/ Norman
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 Dear Johannes, Hans-Wolfgang Loidl and I have given a course on compiler construction using Andrew Appel's book. There was free choice of the implementation language, and we had Java (2 teams and Hans-Wolfgang), python (one team), and Haskell (me). http://www.tcs.ifi.lmu.de/lehre/WS07-08/Compiler/schedule.html (German) I found Haskell very pleasent to use. However, one traversal of the abstract syntax tree did not suffice to generate Intel code. We used an intermediate language on which one can perform optimizations, a greedy instruction selector, and then liveness analysis and graph coloring for register allocation. We developed some tools to support the compiler development, such as an interpreter for the intermediate language and one for a relevant subset of the 386 assembly language (all programmed in Haskell). Cheers, Andreas 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?
If I really decide to do it, then slides (in German) will be made available.
Best regards, J.W.
------------------------------------------------------------------------
_______________________________________________ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
- -- Andreas Abel <>< Du bist der geliebte Mensch. Theoretical Computer Science, University of Munich http://www.tcs.informatik.uni-muenchen.de/~abel/ -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.6 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org iD8DBQFIuvmMPMHaDxpUpLMRAuPSAJwMsgSyBGVxC70Gj47EWxmsb1EYXwCg2HFl HD5fFSn3LatfBPCztguZ+tg= =/5lz -----END PGP SIGNATURE-----
participants (5)
-
Andreas Abel -
Arnar Birgisson -
Claus Reinke -
Johannes Waldmann -
Norman Ramsey