[Haskell] Compiler Construction course using Haskell?
Johannes Waldmann
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.
Derek Elkins
> 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
Haskel...@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Chris Eidhof
>> 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/
Larry Evans
> 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
Don Stewart
Krasimir Angelov
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 <wald...@imn.htwk-leipzig.de>:
> _______________________________________________
> Haskell mailing list
> Has...@haskell.org
> http://www.haskell.org/mailman/listinfo/haskell
Don Stewart
http://www.cse.unsw.edu.au/~cs3161/
type checker, type inference and interpreter + proofs.
kr.angelov:
Claus Reinke
>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
Johannes Waldmann
> 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.
Philippa Cowderoy
> 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.
"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
Johannes Waldmann
> * 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.
Norman Ramsey
> 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
Norman Ramsey
> > 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
>
> .... Would you happen to have a
> syllabus or other course material available online?
Yes:
http://www.cs.tufts.edu/~nr/cs252r/
Johan Jeuring
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.
Andreas Abel
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
> ------------------------------------------------------------------------
>
> _______________________________________________
> Haskell mailing list
> Has...@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-----