Compiler Construction course using Haskell?

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

Compiler Construction course using Haskell?

Johannes Waldmann
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

signature.asc (265 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: Compiler Construction course using Haskell?

Claus Reinke
>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

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

Re: Compiler Construction course using Haskell?

Norman Ramsey
In reply to this post by 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?

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
_______________________________________________
Haskell mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell
Reply | Threaded
Open this post in threaded view
|

Re: Compiler Construction course using Haskell?

Arnar Birgisson
On Fri, Aug 22, 2008 at 02:46, Norman Ramsey <[hidden email]> 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
_______________________________________________
Haskell mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell
Reply | Threaded
Open this post in threaded view
|

Re: Compiler Construction course using Haskell?

Norman Ramsey
 > On Fri, Aug 22, 2008 at 02:46, Norman Ramsey <[hidden email]> 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

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

Re: Compiler Construction course using Haskell?

Andreas Abel
In reply to this post by Johannes Waldmann
-----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
> [hidden email]
> 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-----
_______________________________________________
Haskell mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell