6 ms·

Write You a Haskell: Building a modern functional compiler from first principles

472 points by tenslisi 12y ago

mijoharas 12y ago
Wow, I've been looking for something just like this. Absolutely fantastic!
tenslisi 12y ago
It looks like the author of this (Stephen Diehl) is looking for a job in Boston. Maybe HN can help him out? https://twitter.com/smdiehl/status/538494839189700608 https://twitter.com/smdiehl/status/538494839189700608
- Kiro 12y ago
  He surely must be getting headhunted a lot.
  - hardwaresofton 12y ago
    If this guy isn't getting headhunted, I have no idea what headhunting is. It's pretty rare for people to be able to write correct and easy-to-read guides to such low level concepts.
    - seanmcdirmid 12y ago
      Finding a job is easy, finding the right job is hard for people like this.
      - thirdtruck 12y ago
        Part and parcel of "There are not enough programmers [willing to work long hours for low pay]!"
        seanmcdirmid 12y ago
        For that talent, it might even be that the work is too boring regardless of the hours or pay.
        thirdtruck 12y ago
        Very true. I'm running into that right now: humdrum legacy CRUD apps, where the only challenge lies in being allowed* to refactor the code into decent shape. *I wish I could put that in sarcastic quotes.
- StavrosK 12y ago
  Huh, I just realized I inherited a JS codebase from him in a previous job. The code was ingenious, perhaps too ingenious to maintain.
tel 12y ago
To pull this forward, the author is also the author of "Implementing a JIT Compiled Language in Haskell and LLVM" [0]. [0] http://www.stephendiehl.com/llvm/ http://www.stephendiehl.com/llvm/
- tdees40 12y ago
  If you haven't spent time with this, you need to stop everything and look at it. It's wonderful.
  - zerr 12y ago
    Wonderful regarding learning using LLVM? I mean, isn't the heavy lifting (most interesting part?) done by LLVM, so you're just using it? I haven't read it, that's why I'm asking this.
    - tdees40 12y ago
      So there is a basic introduction to generating LLVM in Haskell there, but what's so great about it is that generating a lexer/parser/(interpreter|compiler) is almost magic in Haskell. The total code of that project is remarkably small. For that reason, it's a pretty standard Haskell workflow to do everything in Haskell and then have it emit LLVM/Cuda/whatever to do the heavy-lifting, and then you get to reason in Haskell and your back-end takes care of the rest. As much as that sounds complicated, it's really, really not.
    - tel 12y ago
      Think of it as a template for this new essay. Of all of the hard optimization work occurring, most of it is embedded in LLVM. But the process of going from stringly syntax to intermediate language to back-end compilation is an important journey and doing it as Steven does using Haskell is an elegant way to scope out those steps.
exDM69 12y ago
Now this is very interesting! There are plenty of compiler writing tutorials for conservative, imperative programming languages with a straightforward static type system (like C). I did study a little bit of compilers for functional languages from Simon Peyton-Jones' old book "The Implementation of Functional Programming Languages" [0]. It predates the Haskell programming language and uses a contemporary research language called Miranda as the target as well as the "host" language. ... which brings me to another topic: Monads. The SPJ book has a few chapters on implementing a Hindley-Milner -style type inference algorithm. It's written in Miranda without any Monads and uses a clever trick for coming up with unique temporary type names. There's an infinite list of integers [0..], which is "split" when traversing the syntax tree so that the left branch of the recursion tree gets the even numbers and the right branch gets the odd numbers. The method works fine and is indeed very clever but try comparing that code to the same algorithm re-implemented (by me) with Monads (State and Error monads + transformer) [1]. The original algorithm is rather long and hard to follow (because lists of unique integers are passed to all functions). I had a blast writing this algorithm, and I wanted to share it. It's been a few years since I last worked with it. It was my first non-trivial use of monads and I really like how it turned out in the end. [0] http://research.microsoft.com/en-us/um/people/simonpj/papers/slpj-book-1987/ http://research.microsoft.com/en-us/um/people/simonpj/papers... [1] https://github.com/rikusalminen/funfun/blob/master/FunFun/TypeChecker.hs https://github.com/rikusalminen/funfun/blob/master/FunFun/Ty...
- thu 12y ago
  I think the online version of that book actually uses Haskell (but the text still refers to Miranda).
  - exDM69 12y ago
    I don't think so, but Miranda and Haskell are very alike so it's easy to be mistaken.
  - pselbert 12y ago
    That seems like an easy mistake to make from what I remember in reading the origin of Haskell. They had issue with the licensing and cost of Miranda and struck out to build upon it. Here's the original article, "A History of Haskell: Being Lazy With Class"[0] [0]: http://research.microsoft.com/en-us/um/people/simonpj/Papers/history-of-haskell/history.pdf http://research.microsoft.com/en-us/um/people/simonpj/Papers...
kachnuv_ocasek 12y ago
As a sidenote, Stephen is also the author/maintainer of "What I Wish I Knew When I Was Learning Haskell"[0] which is a great resource both for those who are learning and for slightly advanced programmers. [0] http://dev.stephendiehl.com/hask/ http://dev.stephendiehl.com/hask/
- JasonFruit 12y ago
  Your comment implies that programmers stop learning once they are slightly advanced.
  - psykotic 12y ago
    No, it doesn't imply that, at all. My least favorite thing on the Internet nowadays are shallow fault-finding comments like yours from people who just want to interject themselves into discussions where they have nothing substantive to say. I used to be that guy and still have to actively resist the temptation. Don't be that guy.
    - JasonFruit 12y ago
      Oh, man — not being that guy, at least in the fault-finding sense; just apparently failing to make an obvious joke. Very strictly, grammatically speaking, it does say that, and it was a humorous implication to me, since I have known so many programmers who apparently did stop learning once they were very slightly advanced. But I'm completely aware that the implication was accidental.
      - juliangregorian 12y ago
        No, it actually doesn't even say that; in no way does it preclude the existence of a third group. Not only are you unfunny, you fail logic.
aidanf 12y ago
This looks really interesting! But I can't see any way to subscribe to book updates. A mailing list (my preferred means of subscribing to this kind of stuff these days) or an rss feed to get notified when new chapters are ready would be really handy.
- reeze_xia 12y ago
  You could `watch` the repository on Github to get notified when there is update
sanxiyn 12y ago
I'd like to recommend The Programming Language Zoo by Andrej Bauer. It is a collection of programming language implementations, small and clear, written in OCaml. http://andrej.com/plzoo/ http://andrej.com/plzoo/
- girvo 12y ago
  Oh, wow. I've been learning OCaml lately, specifically to dive into Hack, Facebook's new statically-typed PHP derivative. This will really help with that, thanks so much for the link!
anaphor 12y ago
I recommend Lisp In Small Pieces (LISP) by Christian Queinnec and Compiling with Continuations by Andrew Appel if you're interested in writing a functional compiler. Also: http://matt.might.net/articles/cps-conversion/ http://matt.might.net/articles/cps-conversion/ http://lucacardelli.name/Papers/BasicTypechecking.pdf http://lucacardelli.name/Papers/BasicTypechecking.pdf http://library.readscheme.org/page1.html http://library.readscheme.org/page1.html https://research.microsoft.com/pubs/67083/spineless-tagless-gmachine.ps.gz https://research.microsoft.com/pubs/67083/spineless-tagless-... http://www.pipeline.com/~hbaker1/CheneyMTA.html http://www.pipeline.com/~hbaker1/CheneyMTA.html
- thu 12y ago
  For the interested, I have implemented Cardelli's paper here: https://github.com/noteed/mojito/blob/master/Language/Mojito/Inference/Cardelli/Cardelli.hs https://github.com/noteed/mojito/blob/master/Language/Mojito...
- sonyandy 12y ago
  In addition to Compiling with Continuations, I found Compiling with Continuations, Continued by Andrew Kennedy very useful, as well. http://research.microsoft.com/pubs/64044/compilingwithcontinuationscontinued.pdf http://research.microsoft.com/pubs/64044/compilingwithcontin...
niix 12y ago
This is awesome. I look forward to following the progression.
wtetzner 12y ago
This is really cool! I'm excited to read the section on row polymorphism.
1ris 12y ago
I was just looking at the fay compiler because i wanted to learn more how haskell is compiled. This looks awesome.
shriphani 12y ago
On the subject of compiler tutorials, there's a really sweet tutorial I found a while back by Abdulaziz Ghoulom (http://scheme2006.cs.uchicago.edu/11-ghuloum.pdf http://scheme2006.cs.uchicago.edu/11-ghuloum.pdf) It simplifies some things (for example tiling while producing the final asm).
rtpg 12y ago
Very interested in seeing how he'll deal with lexing Haskell. It's a major pain, tools like Parsec are very good out of the box with whitespace insensitivity, but not whitespace sensitive stuff.
- dllthomas 12y ago
  I suppose using haskell-src-exts is cheating...
  - rtpg 12y ago
    "I will build haskell by taking the source code and running it" I jest, but this is an issue I've thought about idly for a while. Maybe it's possible to write a two-step parser: one that turns chars into tokens (and cheat a little bit by stripping spaces in some contexts to make it context free), and then you have a nice CFG that you can do easily.
    - eru 12y ago
      See eg http://michaeldadams.org/papers/layout_parsing/ http://michaeldadams.org/papers/layout_parsing/
    - dllthomas 12y ago
      I once took a compiler design course where the instructor said we could use whatever language we wanted (it was a tiny class - I think there were 8 of us?). I asked whether I could use bash, and consider gcc a feature of the language. I was informed that would be cheating.
- cfallin 12y ago
  IIRC, Haskell has a well-defined mapping of whitespace to explicit braces and semicolons -- I suppose one could perform that transform first to desugar, then parse the resulting token stream normally...
  - cardiffspaceman 12y ago

472 points by tenslisi 12y ago

Wow, I've been looking for something just like this. Absolutely fantastic!

It looks like the author of this (Stephen Diehl) is looking for a job in Boston. Maybe HN can help him out? https://twitter.com/smdiehl/status/538494839189700608 https://twitter.com/smdiehl/status/538494839189700608

Kiro 12y ago
He surely must be getting headhunted a lot.
- hardwaresofton 12y ago
  If this guy isn't getting headhunted, I have no idea what headhunting is. It's pretty rare for people to be able to write correct and easy-to-read guides to such low level concepts.
  - seanmcdirmid 12y ago
    Finding a job is easy, finding the right job is hard for people like this.
    - thirdtruck 12y ago
      Part and parcel of "There are not enough programmers [willing to work long hours for low pay]!"
      - seanmcdirmid 12y ago
        For that talent, it might even be that the work is too boring regardless of the hours or pay.
        thirdtruck 12y ago
        Very true. I'm running into that right now: humdrum legacy CRUD apps, where the only challenge lies in being allowed* to refactor the code into decent shape. *I wish I could put that in sarcastic quotes.
StavrosK 12y ago
Huh, I just realized I inherited a JS codebase from him in a previous job. The code was ingenious, perhaps too ingenious to maintain.

tel 12y ago

To pull this forward, the author is also the author of "Implementing a JIT Compiled Language in Haskell and LLVM" [0]. [0] http://www.stephendiehl.com/llvm/ http://www.stephendiehl.com/llvm/

tdees40 12y ago
If you haven't spent time with this, you need to stop everything and look at it. It's wonderful.
- zerr 12y ago
  Wonderful regarding learning using LLVM? I mean, isn't the heavy lifting (most interesting part?) done by LLVM, so you're just using it? I haven't read it, that's why I'm asking this.
  - tdees40 12y ago
    So there is a basic introduction to generating LLVM in Haskell there, but what's so great about it is that generating a lexer/parser/(interpreter|compiler) is almost magic in Haskell. The total code of that project is remarkably small. For that reason, it's a pretty standard Haskell workflow to do everything in Haskell and then have it emit LLVM/Cuda/whatever to do the heavy-lifting, and then you get to reason in Haskell and your back-end takes care of the rest. As much as that sounds complicated, it's really, really not.
  - tel 12y ago
    Think of it as a template for this new essay. Of all of the hard optimization work occurring, most of it is embedded in LLVM. But the process of going from stringly syntax to intermediate language to back-end compilation is an important journey and doing it as Steven does using Haskell is an elegant way to scope out those steps.

exDM69 12y ago

Now this is very interesting! There are plenty of compiler writing tutorials for conservative, imperative programming languages with a straightforward static type system (like C). I did study a little bit of compilers for functional languages from Simon Peyton-Jones' old book "The Implementation of Functional Programming Languages" [0]. It predates the Haskell programming language and uses a contemporary research language called Miranda as the target as well as the "host" language. ... which brings me to another topic: Monads. The SPJ book has a few chapters on implementing a Hindley-Milner -style type inference algorithm. It's written in Miranda without any Monads and uses a clever trick for coming up with unique temporary type names. There's an infinite list of integers [0..], which is "split" when traversing the syntax tree so that the left branch of the recursion tree gets the even numbers and the right branch gets the odd numbers. The method works fine and is indeed very clever but try comparing that code to the same algorithm re-implemented (by me) with Monads (State and Error monads + transformer) [1]. The original algorithm is rather long and hard to follow (because lists of unique integers are passed to all functions). I had a blast writing this algorithm, and I wanted to share it. It's been a few years since I last worked with it. It was my first non-trivial use of monads and I really like how it turned out in the end. [0] http://research.microsoft.com/en-us/um/people/simonpj/papers/slpj-book-1987/ http://research.microsoft.com/en-us/um/people/simonpj/papers... [1] https://github.com/rikusalminen/funfun/blob/master/FunFun/TypeChecker.hs https://github.com/rikusalminen/funfun/blob/master/FunFun/Ty...

thu 12y ago
I think the online version of that book actually uses Haskell (but the text still refers to Miranda).
- exDM69 12y ago
  I don't think so, but Miranda and Haskell are very alike so it's easy to be mistaken.
- pselbert 12y ago
  That seems like an easy mistake to make from what I remember in reading the origin of Haskell. They had issue with the licensing and cost of Miranda and struck out to build upon it. Here's the original article, "A History of Haskell: Being Lazy With Class"[0] [0]: http://research.microsoft.com/en-us/um/people/simonpj/Papers/history-of-haskell/history.pdf http://research.microsoft.com/en-us/um/people/simonpj/Papers...

kachnuv_ocasek 12y ago

As a sidenote, Stephen is also the author/maintainer of "What I Wish I Knew When I Was Learning Haskell"[0] which is a great resource both for those who are learning and for slightly advanced programmers. [0] http://dev.stephendiehl.com/hask/ http://dev.stephendiehl.com/hask/

JasonFruit 12y ago
Your comment implies that programmers stop learning once they are slightly advanced.
- psykotic 12y ago
  No, it doesn't imply that, at all. My least favorite thing on the Internet nowadays are shallow fault-finding comments like yours from people who just want to interject themselves into discussions where they have nothing substantive to say. I used to be that guy and still have to actively resist the temptation. Don't be that guy.
  - JasonFruit 12y ago
    Oh, man — not being that guy, at least in the fault-finding sense; just apparently failing to make an obvious joke. Very strictly, grammatically speaking, it does say that, and it was a humorous implication to me, since I have known so many programmers who apparently did stop learning once they were very slightly advanced. But I'm completely aware that the implication was accidental.
    - juliangregorian 12y ago
      No, it actually doesn't even say that; in no way does it preclude the existence of a third group. Not only are you unfunny, you fail logic.

aidanf 12y ago

This looks really interesting! But I can't see any way to subscribe to book updates. A mailing list (my preferred means of subscribing to this kind of stuff these days) or an rss feed to get notified when new chapters are ready would be really handy.

reeze_xia 12y ago
You could `watch` the repository on Github to get notified when there is update

sanxiyn 12y ago

I'd like to recommend The Programming Language Zoo by Andrej Bauer. It is a collection of programming language implementations, small and clear, written in OCaml. http://andrej.com/plzoo/ http://andrej.com/plzoo/

girvo 12y ago
Oh, wow. I've been learning OCaml lately, specifically to dive into Hack, Facebook's new statically-typed PHP derivative. This will really help with that, thanks so much for the link!

anaphor 12y ago

I recommend Lisp In Small Pieces (LISP) by Christian Queinnec and Compiling with Continuations by Andrew Appel if you're interested in writing a functional compiler. Also: http://matt.might.net/articles/cps-conversion/ http://matt.might.net/articles/cps-conversion/ http://lucacardelli.name/Papers/BasicTypechecking.pdf http://lucacardelli.name/Papers/BasicTypechecking.pdf http://library.readscheme.org/page1.html http://library.readscheme.org/page1.html https://research.microsoft.com/pubs/67083/spineless-tagless-gmachine.ps.gz https://research.microsoft.com/pubs/67083/spineless-tagless-... http://www.pipeline.com/~hbaker1/CheneyMTA.html http://www.pipeline.com/~hbaker1/CheneyMTA.html

thu 12y ago
For the interested, I have implemented Cardelli's paper here: https://github.com/noteed/mojito/blob/master/Language/Mojito/Inference/Cardelli/Cardelli.hs https://github.com/noteed/mojito/blob/master/Language/Mojito...
sonyandy 12y ago
In addition to Compiling with Continuations, I found Compiling with Continuations, Continued by Andrew Kennedy very useful, as well. http://research.microsoft.com/pubs/64044/compilingwithcontinuationscontinued.pdf http://research.microsoft.com/pubs/64044/compilingwithcontin...

niix 12y ago

This is awesome. I look forward to following the progression.

wtetzner 12y ago

This is really cool! I'm excited to read the section on row polymorphism.

1ris 12y ago

I was just looking at the fay compiler because i wanted to learn more how haskell is compiled. This looks awesome.

shriphani 12y ago

On the subject of compiler tutorials, there's a really sweet tutorial I found a while back by Abdulaziz Ghoulom (http://scheme2006.cs.uchicago.edu/11-ghuloum.pdf http://scheme2006.cs.uchicago.edu/11-ghuloum.pdf) It simplifies some things (for example tiling while producing the final asm).

rtpg 12y ago

Very interested in seeing how he'll deal with lexing Haskell. It's a major pain, tools like Parsec are very good out of the box with whitespace insensitivity, but not whitespace sensitive stuff.

dllthomas 12y ago
I suppose using haskell-src-exts is cheating...
- rtpg 12y ago
  "I will build haskell by taking the source code and running it" I jest, but this is an issue I've thought about idly for a while. Maybe it's possible to write a two-step parser: one that turns chars into tokens (and cheat a little bit by stripping spaces in some contexts to make it context free), and then you have a nice CFG that you can do easily.
  - eru 12y ago
    See eg http://michaeldadams.org/papers/layout_parsing/ http://michaeldadams.org/papers/layout_parsing/
  - dllthomas 12y ago
    I once took a compiler design course where the instructor said we could use whatever language we wanted (it was a tiny class - I think there were 8 of us?). I asked whether I could use bash, and consider gcc a feature of the language. I was informed that would be cheating.
cfallin 12y ago
IIRC, Haskell has a well-defined mapping of whitespace to explicit braces and semicolons -- I suppose one could perform that transform first to desugar, then parse the resulting token stream normally...
- cardiffspaceman 12y ago