[Haskell-cafe] Learning about haskell compilers

[John Meacham]

On Tue, Dec 20, 2005 at 10:36:36AM -0600, Creighton Hogg wrote:
> I was wondering where I should get started in learing about 
> how to implement a haskell compiler?

Well, the way I learned was by just making the decision that one way or
another, I was going to write a haskell compiler and then reading and
reading and coding and tossing code and recoding until I succeeded. :)
it is sort of how I learn, choose something I have no idea how to do,
and do it anyway learning what I need to along the way out of neccesity.

in any case, assuming you know something about basic compilers, lexing,
parsing, and code generation and are interested in how you get parsed
haskell source into a form that you can generate code from, I'd highly
recommend the following (in order) (of course, this is just my
experience)


* The haskell report itself: this will give the rules on how to desugar
'complicated' haskell into simple haskell. things like getting rid of list
comprehensions and do notation and turning complicated pattern matching
into simple pattern matching (the most complicated of the desugaring
transformations). I'd recommend desugaring and expanding type synonyms
as soon as possible for your first attempt even though it gives worse
error messages because it _greatly_ simplifies the later steps and you
will likely go through several iterations of the typechecker before you
get one you are happy with. you can always extend your typechecker later
and postpone certain desugarings until you reach a balance of good error
messages you are comfortable with.

* typing haskell in haskell:
http://www.cse.ogi.edu/~mpj/thih/
this will tell you how to go from haskell source to explicitly typed
haskell source, which is now in a form suitable for transforming into an
intermediate language. the explicitly typed, desugared haskell can be
converted directly to core. It may take several readings to fully
understand and looking at the source to hatchet could help considerably
(it did for me)

* then you have a couple choices, basically, You want to learn about ghc
core. there are a lot of papers on ghc optimizations that are great
because they give examples of how core is used which really helps get an
intuitive understanding of why core is a good intermediate language:

recommend are:
Secrets of the GHC inliner.
http://www.research.microsoft.com/~simonpj/Papers/inlining/index.htm
this is by far the most important, the simplifier is the key to any
other optimizations and this paper goes into a lot of the details other
things leave out.

http://haskell.org/ghc/docs/papers/unboxed-values.ps.gz
very good paper. my main regret about jhc development is that I didn't
incorperate unboxed values right from the start thinking of them as an
optimization rather than an essential part of expressing program
properties. I just accumulated hack-after-hack which would have gone
away with unboxed values in the core.

http://research.microsoft.com/copyright/accept.asp?path=/users/simonpj/papers/float.ps.gz&pub=ACM
let floating, not only an important optimization, but will get you
thinking about what it means to preserve lazyness and some of the
trickiness of not breaking performance by accident.

http://research.microsoft.com/copyright/accept.asp?path=/users/simonpj/papers/comp-by-trans.ps.gz&pub=18
great overview, either read this, or all of the above. (or ideally
everything) starting out with this one is probably the best idea because
it will give you an idea what you are in for.


* next you have your simplified optimized core and you want to turn it
into machine code, there are various choices you can make, 

the most well understood is G-machine based implementations like nhc or
the more advanced STG machine used in ghc. the lester book mentioned in
another email is a great introduction and highly recommended even if the
source  there is a lot of practical
info out there on how to implement these and you have pretty much a
straight shot from core to G-machine code either to be compiled directly
or interpreted. 

for jhc I used boquist's GRIN:
http://www.cs.chalmers.se/~boquist/phd/
which is not the simplest way of getting things working right away, but
could be very interesting.

there are various other abstract machines out there, the Lazy Virtual
Machine used by Helium described in Daan Leijen's Phd thesis is quite
interesting, and might make a better first target than G-machine code.

so, I'd recommend, at least _understand_ the G-machine, enough to write
an interpreter for it. (if you already have core, translating and
interpreting G-machine code shouldn't be more than a few hundreds of
lines of code). then read about the LVM, STG, and GRIN, and any other
ones anyone recommends? and decide where you want to go from there.
whichever one inspires you.


Hopefully this helps you, this is just the route I would recommend based
on my experience with jhc, I read a whole lot of papers and books, and
there are a ton more great ones out there but I think this would be the
easiest path to a simple haskell compiler that is based on concepts
extensible to a full-scale non-toy implementation. I left out details
that should be covered in any traditional compiler book and just
mentioned the issues specific to a haskell compiler. I am sure someone
can fill in the holes if needed. 

I wish you good luck, I started jhc a month after hearing about haskell
and boy was it a great crash course in the language having to learn how
to program in it and its details at the same time. The great news is
that Haskell is a _superlative_ language to write compilers for any
language in and is quite fun to boot. writing a compiler you won't find
anywhere that haskell itself is lacking so can concentrate on the task
at hand.

        John 





-- 
John Meacham - ⑆repetae.net⑆john⑈