[Haskell-cafe] I want to write a compiler

Loup Vaillant loup.vaillant at gmail.com
Sat Mar 7 18:32:48 EST 2009

This is a homework question. I am mainly looking for guidance or
pointers. Source code, even. (Not GHC's, though, it is too complicated
for me right now. The AST of STG is fine, but the rest kinda scares

Ideally, I would very much like to compile to C.

The requirements are easily stated. My language must
-> be lazy by default,
-> support algebraic data types and case expressions (unless I can get
away with encoding them as functions),
-> have some kind of FFI with C (I suppose it imply some support for
unboxed values).

There is also the first class functions thing, but lambda lifting is okay.

I don't care about any kind of execution efficiency. I just want my
compiler to be As Simple As Possible. Eventually, I intend to
bootstrap. Then, I will start dreaming about doing better than the
Mighty Simons. (I can dream, right?)

I figured I would start by the back-end. I began to write 15 pathetic
lines of code to start an STG machine. Needles to say, I am stuck. I
don't know where to start.

I am already familiar with some papers. In particular, [1] (on
template instantiation), [2] and [3]. I once wrote a simple graph
reducer using template instantiation (about 20 lines at most).

I have chosen the STG machine because I thought i would be easier to
get an FFI and case exprs out of it. Maybe I am wrong, and template
instantiation is really easier. There is also the BRISK machine, and
GRIN. But the paper I read were less readable to me than the three

So, If any of you can give me some pointer or guidance or advice about
where to start, I would be very grateful.


[1] http://www.cs.otago.ac.nz/cosc459/books/pjlester.pdf
[2] http://research.microsoft.com/~simonpj/Papers/spineless-tagless-gmachine.ps.gz
[3] http://research.microsoft.com/~simonpj/Papers/eval-apply/index.htm

More information about the Haskell-Cafe mailing list