[Haskell-cafe] I want to write a compiler

Jeremy Shaw jeremy at n-heptane.com
Sat Mar 7 20:20:54 EST 2009


This book is pretty good IMO:


It does not cover STG, but it does cover a ton of useful stuff and is
very well written.

I can say from experience that the spineless-tagless-gmachine paper
you referenced does contain all the information needed to implement an
STG->C compiler. But, you should expect to spend a lot of time
alternating between trying to implement the thing and rereading the

Also, you may find that it is easier to do STG->Assembly at first (via
harpy or something). With assembly it is easier to express exactly
what you want to happen. With C you have to try to figure out how to
trick the C compiler into doing your bidding.

Also, maybe it is more satisfying to output assembly, because then you
really feel like you are writing a compiler ;)

I am sure others will say that LLVM is a better option than C or
assembly. I know almost nothing about LLVM, so they may be right.

-- jeremy

At Sun, 8 Mar 2009 01:32:48 +0200,
Loup Vaillant wrote:
> 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
> me.)
> 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
> mentioned.
> So, If any of you can give me some pointer or guidance or advice about
> where to start, I would be very grateful.
> Loup
> [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
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe

More information about the Haskell-Cafe mailing list