10 Commandments: Compiler in Haskell Edition

I am Lambda thy God, which have brought thee out of the land of OO, out of the house of bondage.

A functional language is a domain-specific language for creating domain-specific languages.

– LambdaMan (a.k.a. Philip Wadler)

1. Fact: ADTs and ASTs are like peanut butter and jelly, unless you’re allergic to functional programming, in which case, please accept my condolences.
2. Fact: Pattern matching is just nerdspeak for awesomeness.
3. Fact: Functional programming is basically tetris but with a wider range of side effects allowed.
4. Fact: If it type checks, it must be correct.
5. Fact: Parentheses are evil (obviously).

Hopefully, our team’s choice of using Haskell for the compiler is clearer now.

Thou shalt have no other gods before me.

Almost everything in Haskell revolves around functions/application. Consequently, you can do a lot of things in a similar way, barring the fact the Haskell isn’t dependently typed yet:

1. Ordinary value-level functions have types a1 -> a2.
2. (G)ADT value constructors can be applied and composed like value-level functions.
3. Records fields can be used as value-level functions for projection. (This is probably a bad default, but hey, at least it is consistent!)
4. Values can be grouped and passed around.
5. Type families (type-level functions) have kinds k1 -> k2.
6. Type constructors can be applied and composed like type-level functions.Here “compose” refers to the fact that you can mix and match stuff, not literal function composition.
   
   They can also be abstracted over.
7. Type classes can be used as type level functions (via ConstraintKinds).
8. Constraints can be grouped and passed around.
9. Adding a small amount of primitives gives you quasiquotation. Now you you can manipulate Haskell code using (you guessed it) pattern matching, functions, types and type classes.

Thou shalt not take the name of Lambda in vain.

(A more appropriate subtitle would be “Thou shalt be smug about having higher-rank polymorphism” but I didn’t want to ruin the theme. 😐)

It’s not often that I think to myself, “this cannot possibly work as advertised”. Well, you can imagine my amazement when I learned about SYB and lenses. I still don’t fully understand how either of them work (or for that matter, the signatures in Data.Data) but that’s ok. Naturally, when both of these do a fusion dance, you get fireworks:

  Data.Data.Lens.template ::
    forall s a. (Data s, Typeable a) => Traversal' s a

Yup, you read that right. Just slap some deriving (Typeable, Data) on your AST nodes and you get to traverse your structure in a very flexible way by simply specifying the types of the things you want. Wow.

Stealing from the paper Practical type inference for arbitrary-rank types:

[..] higher-rank types are definitely useful, occasionally indispensable, and much easier to implement than one might guess. Every language should have them!

Thou shalt not make unto thee any gratuitous punctuation.

After using Haskell, nearly all other mainstream languages seem overly riddled with punctuation. While I’m guessing whitespace sensitivity must be annoying for people writing tooling, it does aid readability a lot.

Case in point - I’ve been writing some C++ lately, which in case you don’t know, is a language best described as spicy punctuation curry (not the fun kind of curry) plus some alphanumeric seasoning sprinkled on top. I’ve been getting a few missing “;” errors over the past month… And I haven’t yet reached the point where I stop telling the compiler “aww, piss off, why don’t you insert it yourself”.

Of course, this doesn’t mean that everything is perfect. Some libraries define a LOT of operators (yes, we all know which one I’m talking about). While internalising the “logic” behind the symbols can be helpful while writing code,Perhaps library authors are taking Wadler’s words a bit too seriously?

reading someone else’s code written using them feels like reading golfed code.

Thou shalt not unsafeCoerce.

I recall reading somewhere that every time you use unsafeCoerce, a puppy dies. As much as it shames me to admit it, we killed two puppies. RIP good boys.

Thou shalt not over-abstract.

With great power come not-so-great type errors/compile times.

– Ancient Haskell proverb.

Using Haskell, it is very easy to get carried away and use lots of fancy abstractions without (a) a clear-cut power-to-weight ratio and (b) the ability to dig yourself out of a type-checking error when needed. Two cases in point:

1. We initially modeled our AST as a pair of nested cofree comonads, one for expressions inside another for statements. At some point, we hit this strange type error which we couldn’t figure out how to work around (despite being at it for a few hours). Eventually we had to rewrite a large chunks of the code and get rid of it entirely. One of my team-mates did eventually figure out how to get it to work about a week later (roughly speaking, my memory is fuzzy).

2. Our approach to unit-testing involved mapping all the AST annotations to (), and checking against the AST by hand. We also had some other invariants, such as integer literals being represented by Integer while parsing and as Int after typechecking (the language only supported 64-bit values). While the Trees That Grow approach seemed perfect for enforcing invariants statically across compiler phases, it lead to (a) very long compile times once we added in more invariants, as a large portion of the compiler’s modules transitively depended on the AST module, and (b) a lot of boilerplate for deriving instances and removing annotations as we couldn’t just do () <$ (type families cannot be partially applied).

   In the end, this “feature” was never merged into the master branch.

Oh, I forgot the mention the best bit: we battled error messages with rigid skolems, infinite types, untouchable type variables, “sorry, we don’t support impredicative polymorphism” (this one was my personal favourite), what have you and (to top it all off?) infrequent/random linker errors on one guy’s machine. BRB after writing a pure linker.

Thou shalt not take performance for granted.

One of the major roadblocks in writing the compiler was in getting the graph-coloring based register allocator (1) correct and (2) fast enough. While there isn’t much that could be done about (1), using fgl – one of the more popular graph libraries – proved to be a bad choice. It isn’t clear whether we were using the library wrong or whether we had hit a fundamental limitation. Eventually, we borrowed ideas from GHC’s own implementation to get the allocator to work in respectable time.

We had also considered using alga before we decided against it because (1) it seemed to have fewer helper functions to work with and (2) the benchmarks at the time didn’t give us enough confidence to try a newer library over an older one. Hopefully, someone can use Linear Haskell to come up with a fast, general-purpose graph library 😅.

Similarly, although parser combinators prove to be very readable (as opposed to using a lexer/parser generator), we once hit an issue where 1/3rd of the compilation time in the lexer (!). The problem was that we were carelessly using Megaparsec’s try in several places, leading to a lot of unnecessary back-tracking and failed attempts.

As I wrote earlier, one problem with using fancy abstractions is that it can get hard to reason about performance. The containers library is probably one of the best in this regard, it clearly outlines what one should expect from different operations, as well as provides a sufficiently rich and convenient API to work in a purely functional setting.

P.S. The RTS made profiling super convenient here. We used GHC’s json dumps + ghc-aeson-flamegraph + Brendan Gregg’s flamegraph.pl to easily visualize bottlenecks in the code.

Thou shalt not lust for laziness, for it is a fickle mistress.

Laziness is awesome. When it works. And then it doesn’t. And you’re trying to debug things and putting traceXXX and deepseq everywhere. And things still get printed in a weird order, because you inevitably forgot to annotate something.

Laziness is also not good for performance in a lot of cases, apart from the handy fact that it makes programs with infinite structures terminate. Whenever you’re dealing with finite structures, having strictness for fields is better in a lot of cases. For example, containers uses strictness in several places and several performance-oriented presentations talk about avoiding laziness and its partner-in-crime boxed fields.

Thou shalt not covet thy neighbour’s package manager.

Haskell has several “dependency management solutions” which I guess is somewhere in between C++ where you’re supposed to lose your hair trying to get things to work (and once it does, refuse to upgrade anything lest it break) and Rust where you can probably do cargo install cargo-haircut && cargo haircut and have it do the obvious without getting your bum off your comfy sofa.

In my little experience, while stack does work most of time, it suffers from a lot of bloat which can cause issues if storage space/processor speed are not available easily. I’m guessing this is mostly a student budget/old laptop issue that professional Haskellers don’t encounter (for reference, I’ve been using a Thinkpad X230 with a 256GB SSD and at some point had ~/.stack at size 25 GB+). It would be nice if stack offered a clean way to uninstall things. Since it doesn’t, the options left are (a) tedious: use ghc-unregister to uninstall stuff and corresponding dependencies or (b) slow: nuke ~/.stack, rerun stack build and wait for it to recompile the universe.Not sure if I was imagining it but I recollect my terminal beeping when I was transitively installing lens for the fiftieth time.

On a more positive note, cabal new-build does seem to work better than cabal sandbox, so I have my fingers crossed that healthy competition between the projects makes both of them better in the future. Or the Nix hippies become our new overlords. Not being picky here.

Remember the refactor day, to keep it holy.

Haskell makes refactoring a breeze. To be more precise, equational reasoning makes refactoring a breeze. Refactoring is, in essence a process of term rewriting; being able to quickly substitute like-for-like without worrying about state, or factor out commonly used code pieces is close to effortless in Haskell. Type inference that just works is also very handy as you don’t waste your time spelling out every little detail for the compiler (just autofill the inferred type!). Sometimes, the compiler will tell you that your function is actually more general than you thought it was. Free theorems, anyone?

Using operators for common operations proves to be handy here. I find that it is easier to do pattern recognition and rewriting when you’ve got a mixture of operators and identifiers, rather than just lots of letters and function application brackets.

Honour thy compiler contributors.

There have been several occasions over the past few months where either I or one of my team-mates encountered a “huh, I didn’t realise you could do that, that’s so cool!” moment. That is probably not what makes Haskell unique in my opinion. What does make it stand it out is that I’m fairly confident that I’ll regularly keep having that “aha!” moment even if I keep writing Haskell for the next few years. It might be coming from blog posts/papers/navel-gazing posts on r/haskell or somewhere else, but there’s always going to be interesting stuff to learn.

As Stroustrup once said, “There are only two kinds of languages: the ones people complain about and the ones nobody uses.” I’ve probably made more than my fair share of complaints here, but I must say that I’m very grateful to all the people who have contributed to GHC and the Haskell ecosystem more generally. Overall, Haskell mostly feels like an awesome, cohesive whole. Thank you! 😄

Closing thoughts

Writing a compiler in Haskell has been a great source of joy. 9/10 would recommend.

Bonus

One of my biggest (ノಠ益ಠ)ノ彡┻━┻ moments over the past few months - Trac 8695.

Also, I couldn’t figure out how to fit intero, hoogle and hlint into the narrative here but all of them deserve a shout-out. intero does its best to provide live type information in Spacemacs (until some TH heavy code kills its performance). hoogle is google but for Haskell: searching type signatures is a breeze. hlint does simple equational reasoning and provides many helpful suggestions for clearer code. All these tools are awesome! I wish we (the Haskell community) would spend more effort in getting tooling into the hands of beginners right away, not just GHCi. It really makes for a big quality-of-life improvement. Users from other languages may not even realize that such tools could/do exist, so they might not go seek them in the first place.