5 ms·

GHC Parser Principles

110 points by jasim 8y ago

danharaj 8y ago
I have a commit on GHC (a very modest one). The compiler is written in a mix of somewhat old Haskell style and new which makes sense since it's one of the oldest and largest codebases in the language. There is a constant drive to modernize it and some new techniques come out of GHC architectural changes [0]. I didn't work with the parser, mostly the constraint solver in the type checker. Still, I browsed quite a bit of code. It's one of the most pleasant and well documented codebases I've worked in in any language. In particular, the [note] system is an excellent way to embed long form documentation that touches many components without using fancy doc tools: grep suffices. If you want to see what a large, old, industrial grade Haskell project looks like I think GHC is a good place to look. And if you ever run into trouble with GHC then I encourage you not to be afraid to hack on it. The code won't bite and the maintainers have no shortage of patience for newcomers. [0] https://arxiv.org/abs/1610.04799 https://arxiv.org/abs/1610.04799
- piinbinary 8y ago
  I appreciate the pun in that paper: Algebraic Data Types (ADTs) and pattern matching in functional languages lay a fertile ground to conveniently define and process data types as tree-like structures. However, in these grounds, trees often cannot grow; once a data type is defined and compiled, its definition cannot be extended.
- endgame 8y ago
  Can you go into more detail about the [note] system?
  - ufo 8y ago
    Simon Marlow and Simon Peyton-Jones wrote a chapter about GHC for the Architecture of Open Source Applications ebook and they talk about the note system there. Skip to section 5.6. http://www.aosabook.org/en/ghc.html http://www.aosabook.org/en/ghc.html
FullyFunctional 8y ago
That's neat; parser working hard to make the language look simple. The success sword of GHC is dual edged; it's made Haskell effectively synonymous with "Language accepted by a recent GHC". The upside is an amazing language with great many advanced features. The downside is an enormous language in a monoculture. It's nearly the antithesis of C (small language that grew little and slowly, but for which there are 100s of implementations).
- sevensor 8y ago
  It's funny, you could also say this of Ruby and MRI, which is in so many other respects the polar opposite of Haskell. Edit: Spelling.
  - FullyFunctional 8y ago
    I don't know either, but FWIW, there _are_ many (ok, several) Haskell implementation, but they only implement the language defined in the standard, and nobody has been able or willing to chase all the extensions in GHC. Does Ruby and MRI have specs detailed enough that you could implement the entired language from just those? Few languages do, but Scheme and Haskell are among them.
    - lobster_johnson 8y ago
      Ruby is actually an ISO standard. Admittedly, it's frozen at Ruby 1.8 and it doesn't count for much.
- tathougies 8y ago
  Haskell 98 is a very simple language. Modern GHC Haskell is to Haskell 98 as C++ is to C.
harpocrates 8y ago
I have very mixed feelings about using parser generators instead of hand written parsers. I've contributed to GHC's parser grammar and spent a lot of time reading Rust's hand-written parser. On one hand, a grammar is an invaluable tool. It helps keep you honest about ambiguities when you start thinking about adding language features. I think languages should always keep some reference grammar up to date. That said, I don't think it is a good idea for compilers to use parser generators. A hand-written parser can have better error recovery and more helpful error messages. GHC's parser has some pretty bad parse error message. Some work was merged into Happy a while ago to support better messages (enabling you to see the expected tokens along with the bad token), but using that in GHC itself is blocked by how complex GHC's tokenizer has become.
- kazinator 8y ago
  Grammars don't keep you entirely honest about ambiguities, because parser generators resolve some ambiguities like shift in favor of reduce in Yacc. It's possible to massage a Yacc grammar into working and then not entirely understand it. > A hand-written parser can have better error recovery and more helpful error messages. A hand-written parser lets you put a breakpoint on the function which handles a given phrase rule, and when the execution stops there, you get a call stack which more or less corresponds to the top-to-bottom derivation, with arguments you can examine at every level.
  - ufo 8y ago
    The difference is that the bottom up parser is able to detect the ambiguity and complain about it at all. And anyone who wants to keep their sanity won't rely on the default yacc behavior and will take care to get rid of all the shift-reduce conflicts.
- willtim 8y ago
  Since GHC was created, we now have some very good parser combinator libraries such as Parsec and uuparsing-lib. Haskell is a very good language with which to write a parser by hand. But no doubt it would be a big project to move off happy and success isn't guaranteed.
arturogoosnargh 8y ago
I'm writing a Haskell compiler in C as a hobby. I didn't take a look at GHC code but now I find the way they deal with optional indentation interesting. Nonetheless I implemented the same thing in a simpler way having a function in my parser that checks for the presence or absence of curly braces and sets some state on the parser. My implementation: https://github.com/angel-manuel/schc/blob/c1fa77b332a765b4767822bc90314bc62aebac33/src/parser.c#L216-L260 https://github.com/angel-manuel/schc/blob/c1fa77b332a765b476...
- kreetx 8y ago
  Out of curiosity, do you have a mathemathics background? I.e for me the scaryest part of this is type inference and type checking.
sfvisser 8y ago
Similar to what I'm noticing just right now in VSCode where the IDE warns you comments are not allowed in a JSON file. This means the parser happily parses comments and performs a separate check afterwards. Beats a "unexpected symbol '/' at 12:4" Great UX!
- evincarofautumn 8y ago
  One thing I’ve learned in my years of working on compilers & programming language tech, which at first is counterintuitive, is that for the best user experience in a compiler, often you want your parser to be “total”, and not to reject any inputs. Instead of bailing out at the first error, you parse invalid portions of the input and sync up to the next point where you can recover and keep parsing, annotating the resulting token stream or parse tree with error indicators such as “invalid number literal token” or “missing bracket”. This lets you report all errors in a source file at once, so they can all be highlighted in an IDE for example, regardless of errors earlier in the file. The more semantic information you have about the correct parts of the program, the better error messages you can produce about the incorrect parts. You can extend this to all areas of the compilation pipeline—for example, proceeding to resolve names and typecheck the definitions in a program that are syntactically correct, while ignoring the others and leaving them as error markers.
  - Zalastax 8y ago
    This philosophy is an integral part to the good error reports in TypeScript: https://www.infoq.com/news/2016/05/anders-hejlsberg-compiler https://www.infoq.com/news/2016/05/anders-hejlsberg-compiler
  - tom_mellior 8y ago
    > Instead of bailing out at the first error, you parse invalid portions of the input and sync up to the next point where you can recover and keep parsing People like saying that, but I've never seen it work well or provide any benefits. Because these tools are necessarily imperfect, you will get false positives, i.e., an earlier error will confuse the system sufficiently to generate later errors that aren't really errors in the program. So you have to fix errors in order anyway. So there is no benefit to producing further messages. You just risk producing several pages of spurious diagnostics for a simple typo. Of course this is not completely true, but it's true enough. Or if it isn't, I'd like to hear about examples of systems that never produce such false positives, and where for some reason it makes sense (and is actually beneficial) to change something later in the file first. Until then, just give me the first error. I won't look at the rest anyway, so no need for the compiler to be "clever" about it.

110 points by jasim 8y ago

I have a commit on GHC (a very modest one). The compiler is written in a mix of somewhat old Haskell style and new which makes sense since it's one of the oldest and largest codebases in the language. There is a constant drive to modernize it and some new techniques come out of GHC architectural changes [0]. I didn't work with the parser, mostly the constraint solver in the type checker. Still, I browsed quite a bit of code. It's one of the most pleasant and well documented codebases I've worked in in any language. In particular, the [note] system is an excellent way to embed long form documentation that touches many components without using fancy doc tools: grep suffices. If you want to see what a large, old, industrial grade Haskell project looks like I think GHC is a good place to look. And if you ever run into trouble with GHC then I encourage you not to be afraid to hack on it. The code won't bite and the maintainers have no shortage of patience for newcomers. [0] https://arxiv.org/abs/1610.04799 https://arxiv.org/abs/1610.04799

piinbinary 8y ago
I appreciate the pun in that paper: Algebraic Data Types (ADTs) and pattern matching in functional languages lay a fertile ground to conveniently define and process data types as tree-like structures. However, in these grounds, trees often cannot grow; once a data type is defined and compiled, its definition cannot be extended.
endgame 8y ago
Can you go into more detail about the [note] system?
- ufo 8y ago
  Simon Marlow and Simon Peyton-Jones wrote a chapter about GHC for the Architecture of Open Source Applications ebook and they talk about the note system there. Skip to section 5.6. http://www.aosabook.org/en/ghc.html http://www.aosabook.org/en/ghc.html

FullyFunctional 8y ago

That's neat; parser working hard to make the language look simple. The success sword of GHC is dual edged; it's made Haskell effectively synonymous with "Language accepted by a recent GHC". The upside is an amazing language with great many advanced features. The downside is an enormous language in a monoculture. It's nearly the antithesis of C (small language that grew little and slowly, but for which there are 100s of implementations).

sevensor 8y ago
It's funny, you could also say this of Ruby and MRI, which is in so many other respects the polar opposite of Haskell. Edit: Spelling.
- FullyFunctional 8y ago
  I don't know either, but FWIW, there _are_ many (ok, several) Haskell implementation, but they only implement the language defined in the standard, and nobody has been able or willing to chase all the extensions in GHC. Does Ruby and MRI have specs detailed enough that you could implement the entired language from just those? Few languages do, but Scheme and Haskell are among them.
  - lobster_johnson 8y ago
    Ruby is actually an ISO standard. Admittedly, it's frozen at Ruby 1.8 and it doesn't count for much.
tathougies 8y ago
Haskell 98 is a very simple language. Modern GHC Haskell is to Haskell 98 as C++ is to C.

harpocrates 8y ago

I have very mixed feelings about using parser generators instead of hand written parsers. I've contributed to GHC's parser grammar and spent a lot of time reading Rust's hand-written parser. On one hand, a grammar is an invaluable tool. It helps keep you honest about ambiguities when you start thinking about adding language features. I think languages should always keep some reference grammar up to date. That said, I don't think it is a good idea for compilers to use parser generators. A hand-written parser can have better error recovery and more helpful error messages. GHC's parser has some pretty bad parse error message. Some work was merged into Happy a while ago to support better messages (enabling you to see the expected tokens along with the bad token), but using that in GHC itself is blocked by how complex GHC's tokenizer has become.

kazinator 8y ago
Grammars don't keep you entirely honest about ambiguities, because parser generators resolve some ambiguities like shift in favor of reduce in Yacc. It's possible to massage a Yacc grammar into working and then not entirely understand it. > A hand-written parser can have better error recovery and more helpful error messages. A hand-written parser lets you put a breakpoint on the function which handles a given phrase rule, and when the execution stops there, you get a call stack which more or less corresponds to the top-to-bottom derivation, with arguments you can examine at every level.
- ufo 8y ago
  The difference is that the bottom up parser is able to detect the ambiguity and complain about it at all. And anyone who wants to keep their sanity won't rely on the default yacc behavior and will take care to get rid of all the shift-reduce conflicts.
willtim 8y ago
Since GHC was created, we now have some very good parser combinator libraries such as Parsec and uuparsing-lib. Haskell is a very good language with which to write a parser by hand. But no doubt it would be a big project to move off happy and success isn't guaranteed.

arturogoosnargh 8y ago

I'm writing a Haskell compiler in C as a hobby. I didn't take a look at GHC code but now I find the way they deal with optional indentation interesting. Nonetheless I implemented the same thing in a simpler way having a function in my parser that checks for the presence or absence of curly braces and sets some state on the parser. My implementation: https://github.com/angel-manuel/schc/blob/c1fa77b332a765b4767822bc90314bc62aebac33/src/parser.c#L216-L260 https://github.com/angel-manuel/schc/blob/c1fa77b332a765b476...

kreetx 8y ago
Out of curiosity, do you have a mathemathics background? I.e for me the scaryest part of this is type inference and type checking.

sfvisser 8y ago

Similar to what I'm noticing just right now in VSCode where the IDE warns you comments are not allowed in a JSON file. This means the parser happily parses comments and performs a separate check afterwards. Beats a "unexpected symbol '/' at 12:4" Great UX!

evincarofautumn 8y ago
One thing I’ve learned in my years of working on compilers & programming language tech, which at first is counterintuitive, is that for the best user experience in a compiler, often you want your parser to be “total”, and not to reject any inputs. Instead of bailing out at the first error, you parse invalid portions of the input and sync up to the next point where you can recover and keep parsing, annotating the resulting token stream or parse tree with error indicators such as “invalid number literal token” or “missing bracket”. This lets you report all errors in a source file at once, so they can all be highlighted in an IDE for example, regardless of errors earlier in the file. The more semantic information you have about the correct parts of the program, the better error messages you can produce about the incorrect parts. You can extend this to all areas of the compilation pipeline—for example, proceeding to resolve names and typecheck the definitions in a program that are syntactically correct, while ignoring the others and leaving them as error markers.
- Zalastax 8y ago
  This philosophy is an integral part to the good error reports in TypeScript: https://www.infoq.com/news/2016/05/anders-hejlsberg-compiler https://www.infoq.com/news/2016/05/anders-hejlsberg-compiler
- tom_mellior 8y ago
  > Instead of bailing out at the first error, you parse invalid portions of the input and sync up to the next point where you can recover and keep parsing People like saying that, but I've never seen it work well or provide any benefits. Because these tools are necessarily imperfect, you will get false positives, i.e., an earlier error will confuse the system sufficiently to generate later errors that aren't really errors in the program. So you have to fix errors in order anyway. So there is no benefit to producing further messages. You just risk producing several pages of spurious diagnostics for a simple typo. Of course this is not completely true, but it's true enough. Or if it isn't, I'd like to hear about examples of systems that never produce such false positives, and where for some reason it makes sense (and is actually beneficial) to change something later in the file first. Until then, just give me the first error. I won't look at the rest anyway, so no need for the compiler to be "clever" about it.