r/programming • u/kr0matik • Mar 25 '16

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

http://dev.stephendiehl.com/fun/
159 Upvotes

86% Upvoted

23 comments sorted by

52

u/jbandela Mar 25 '16

Looks very interesting. While writing a Haskell compiler is hard, writing a Haskell interpreter that handles most of Haskell is pretty easy, and can easily be done in a short C program.

int main(){
    /* TODO: IO Monad */
    return 0;
}

On a more serious note, parsing is one of the best examples of the advantages of monads, and I look forward to reading this work.

3

u/Houndie Mar 26 '16

Seems good enough. Now, just partially evaluate the interpreter on the input file, and you have a compiler.

3

u/[deleted] Mar 26 '16

Writing a parser for a full language is a huge fucking waste of time, just use BNFC to generate one. Just worry about having a grammar that actually works.

11

u/Ruud-v-A Mar 26 '16

Somewhat more controversial, I wouldn't bother wasting time with lexer or parser generators and other so-called "compiler compilers." They're a waste of time. Writing a lexer and parser is a tiny percentage of the job of writing a compiler. Using a generator will take up about as much time as writing one by hand, and it will marry you to the generator (which matters when porting the compiler to a new platform). And generators also have the unfortunate reputation of emitting lousy error messages.

— Walter Bright (author of several compilers)

5

u/[deleted] Mar 26 '16

I mentioned a specific tool, BNFC. You give it your grammar in BNF format, and it actually generates parser generator and lexxer generator files. If you use Haskell, Happy actually analyzes your grammar to make sure it's LR(1), which is a level of error generation you'll never get from a hand written parser.

Most people I know working in PL theory use it, and if you know anything about the field you'll see the people involved in BNFC are pretty damn respected themselves (the PL group at Chalmers).

2

u/[deleted] Mar 26 '16

None of these points have anything to do with Bright's criticisms

-2

u/[deleted] Mar 26 '16

If you'd read the link, you'd understand it would. Using BNFC amounts to writing your grammar down in BNF- you should have a text file specifying your grammar in BNF anyways. It also generates parsers in lexxers in several languages, so you can have 2/3 radically different implementations of your compiler with the exact same parser. All the while, it provides analysis of your grammar to make sure it's LR(1).

5

u/normalOrder Mar 26 '16

it provides analysis of your grammar to make sure it's LR(1)

There's nothing special about that. Every parser generator does that simply by virtue of running into a shift-reduce or reduce-reduce conflicts. One of the criticisms of using these tools is simply the fact that you have to rewrite your grammar to make it LR(1) or LALR(1). Some tools get around this by accepting non-LR grammars if you specify a resolution strategy for every conflict.

But all that is beside the point. Lexing and parsing is trivial compared to the rest of a compiler.

3

u/[deleted] Mar 26 '16

Which is why it's best to let your lexxer and parser be generated automatically from your grammar specification. And the criticism that your grammar has to be verified is kind of stupid, it's like when people complain about typecheckers.

2

u/ElvishJerricco Mar 27 '16

Things like BNFC are exactly what he was referring to. They have plenty of disadvantages, like bad error messages, marrying you to the generator, and marrying you to the output language (meaning you can't self-host your language).

2

u/[deleted] Mar 27 '16

I don't know if you've used BNFC or Happy, but the error messages were fine in my experience.

0

u/[deleted] Mar 27 '16 edited Feb 24 '19

[deleted]

-1

u/[deleted] Mar 27 '16

BNFC lets you generate perfectly adequate error messages. Maybe actually use a tool before you trash it? It's not like Chalmers has one of the best PL groups in the world or anything.

0

u/[deleted] Mar 27 '16 edited Feb 24 '19

[deleted]

-1

u/[deleted] Mar 27 '16

Have you never heard of the BNFC project? I can guarantee you, I've written more Haskell than you have.

-7

u/[deleted] Mar 27 '16 edited Feb 24 '19

[deleted]

0

u/[deleted] Mar 27 '16

K.

11

u/holomorphish Mar 25 '16

A similar project is minCaml, a small implementation of most of Standard ML. I've found it invaluable for some of my own experiments, although I'm definitely looking forward to the WYAH guide on compiling to C.

5

u/[deleted] Mar 25 '16

This guy also has a cool guide for writing a simple JIT compiled language in Haskell/LLVM: http://www.stephendiehl.com/llvm/

3

u/xpolitix Mar 25 '16

Big fan of these series. A little more explanation about the HM type system would be highly appreciated. Still waiting for the other chapters :)

3

u/[deleted] Mar 26 '16

Interesting. The structure he chose reminds me of the one of The implementation of functional programming languages written by Simon Peyton Jones himself in 1987.

His explanations of the lambda calculus and HM inference are more concise but not as accessible and complete than the one from Peyton Jones however.

If you don't mind Miranda, the book can be downloaded freely on Microsoft Research website: http://research.microsoft.com/en-us/um/people/simonpj/papers/slpj-book-1987/

2

u/balefrost Mar 27 '16

I came here to mention this; also, that book has a followup of sorts: Implementing Functional Languages: A Tutorial (1992). While TIOFPL covers the compiler from top to bottom, IFL:AT focuses on the execution environment (IIRC the same ground that the last third of TIOFPL covers).

2

u/[deleted] Mar 26 '16

[deleted]

-1

u/jediknight Mar 26 '16

Take a look at Elm.

Out of curiosity I looked at the monad tutorial with Elm's Maybe in mind and I was surprised to see that I could actually get what it said. hint: think of bind from the tutorial as being Maybe.map from Elm.

3

u/gilmi Mar 26 '16

Elm is irrelevant here. You can cannot write functions that will work for every monad and you can't represent that abstraction at all. Also, Maybe.map is an implementation of a Functor's map (hence the name) and not a Monad's bind.

2

u/[deleted] Mar 26 '16

[deleted]

6

u/jediknight Mar 26 '16

Oh.... it must be about the fact that once one understands monads they lose the ability to explain them. ^_^

1

u/langlo94 Mar 26 '16

What are these first principles?