10 Commandments (Compiler in Haskell edition)

Dur­ing the spring se­mes­ter of 2018, I took a ba­sic com­pil­ers course – our team chose to write the com­pil­er in Haskell. This is a chron­i­cle/post-mortem/ran­dom hodge­podge of my thoughts.

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

A func­tion­al lan­guage is a do­main-spe­cif­ic lan­guage for cre­at­ing do­main-spe­cif­ic lan­guages.

—Lamb­daMan (a.k.a. Philip Wadler)

  1. Fact: ADTs and ASTs are like peanut but­ter and jel­ly, un­less you’re al­ler­gic to func­tion­al pro­gram­ming, in which case, please ac­cept my con­do­lences.
  2. Fact: Pat­tern match­ing is just nerd­speak for awe­some­ness.
  3. Fact: Func­tion­al pro­gram­ming is ba­si­cal­ly tetris but with a wider range of side ef­fects al­lowed.
  4. Fact: If it type checks, it must be cor­rect.
  5. Fact: Paren­the­ses are evil (ob­vi­ous­ly).

Hope­ful­ly, our team’s choice of us­ing Haskell for the com­pil­er is clear­er now.

Thou shalt have no other gods before me.

Al­most ev­ery­thing in Haskell re­volves around func­tions/ap­pli­ca­tion. Con­se­quent­ly, you can do a lot of things in a sim­i­lar way (bar­ring the fact the Haskell isn’t de­pen­dent­ly typed yet):

  1. Or­di­nary val­ue-lev­el func­tions have types a1 -> a2.
  2. (G)ADT val­ue con­struc­tors can be ap­plied and com­posed like val­ue-lev­el func­tions.
  3. Records fields can be used as val­ue-lev­el func­tions for pro­jec­tion. (This is prob­a­bly a bad de­fault, but hey, at least it is con­sis­tent!)
  4. Val­ues can be grouped and passed around.
  5. Type fam­i­lies (type-lev­el func­tions) have kinds k1 -> k2.
  6. Type con­struc­tors can be ap­plied and com­posed like type-lev­el func­tions (1). They can al­so be ab­stract­ed over.
  7. Type class­es can be used as type lev­el func­tions (via ConstraintKinds).
  8. Con­straints can be grouped and passed around.
  9. Adding a small amount of prim­i­tives gives you Q where you can ma­nip­u­late Haskell code us­ing (you guessed it) the usu­al pat­tern match­ing, func­tions, types and type class­es.

Thou shalt not take the name of the Lambda thy God in vain.

(Au­thor’s note: a more ap­pro­pri­ate sub­ti­tle would be “Thou shalt be smug about hav­ing high­er-rank poly­mor­phism” but I didn’t want to ru­in the theme. 😐)

It’s not of­ten that I think to my­self, “this can­not pos­si­bly work as ad­ver­tised”. Well, you can imag­ine my amaze­ment when I learned about SYB and lens­es. I still don’t ful­ly un­der­stand how ei­ther of them work (or for that mat­ter, the sig­na­tures in Data.Data) but that’s ok. Nat­u­ral­ly, when both of these do a fu­sion dance, you get fire­works:

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 tra­verse stuff in a very flex­i­ble way by just spec­i­fy­ing the types of the things you want. Wow.

Steal­ing from the pa­per Prac­ti­cal type in­fer­ence for ar­bi­trary-rank types:

[..] high­er-rank types are def­i­nite­ly use­ful, oc­ca­sion­al­ly in­dis­pens­able, and much eas­i­er to im­ple­ment than one might guess. Ev­ery lan­guage should have them!

Thou shalt not make unto thee any gratuitous punctuation.

Af­ter us­ing Haskell, near­ly all oth­er main­stream lan­guages seem over­ly rid­dled with punc­tu­a­tion. While I’m guess­ing white­space sen­si­tiv­i­ty must be an­noy­ing for peo­ple writ­ing tool­ing, it does aid read­abil­i­ty a lot.

Case in point - I’ve been writ­ing some C++ late­ly, which in case you don’t know, is a lan­guage best de­scribed as spicy punc­tu­a­tion cur­ry (not the fun kind of cur­ry) plus some al­phanu­mer­ic sea­son­ing sprin­kled on top. I’ve been get­ting a few miss­ing “;” er­rors over the past month, and I haven’t reached the point where I stop telling the com­pil­er “aww, fuck off, why don’t you in­sert it your­self”.

Of course, this doesn’t mean that ev­ery­thing is per­fect – some li­braries de­fine a lot of op­er­a­tors (yes, we all know which one I’m talk­ing about) and while in­ter­nal­is­ing the “log­ic” be­hind the sym­bols can be help­ful while writ­ing code (2), read­ing some­one else’s code writ­ten us­ing them feels like read­ing golfed code with­out the irony.

Thou shalt not unsafeCoerce.

I re­call read­ing some­where that ev­ery time you use unsafeCoerce, a pup­py dies. As much as it shames me to ad­mit it, we killed two pup­pies. RIP good boys.

Thou shalt not over-abstract.

With great pow­er come not-so-great type er­rors/com­pile times.

Us­ing Haskell, it is very easy to get car­ried away and use lots of fan­cy ab­strac­tions with­out (a) a clear-cut pow­er-to-weight ra­tio and (b) the abil­i­ty to dig your­self out of a type-check­ing er­ror when need­ed. Two cas­es in point:

  1. We ini­tial­ly mod­eled our AST as a pair of nest­ed cofree comon­ads – one for ex­pres­sions in­side an­oth­er for state­ments. At some point, we hit this strange type er­ror which we couldn’t fig­ure out how to work around (de­spite be­ing at it for a few hours). Even­tu­al­ly we had to re­write a large chunks of the code and get rid of it en­tire­ly. One of my team-mates did even­tu­al­ly fig­ure out how to get it to work about a week lat­er (rough­ly speak­ing, my mem­o­ry is fuzzy).
  2. Our ap­proach to unit-test­ing in­volved map­ping all the AST an­no­ta­tions to (), and check­ing against the AST by hand. We al­so had some oth­er in­vari­ants, such as in­te­ger lit­er­als be­ing rep­re­sent­ed by Integer while pars­ing and as Int af­ter type­check­ing (the lan­guage on­ly sup­port­ed 64-bit val­ues). While the Trees That Grow ap­proach seemed per­fect for en­forc­ing in­vari­ants stat­i­cal­ly across com­pil­er phas­es, it lead to (a) very long com­pile times once we added in more in­vari­ants, as a large por­tion of the com­pil­er’s mod­ules tran­si­tive­ly de­pend­ed on the AST mod­ule, and (b) a lot of boil­er­plate for de­riv­ing in­stances and re­mov­ing an­no­ta­tions as we couldn’t just do () <$ (type fam­i­lies can­not be par­tial­ly ap­plied).

    In the end, this “fea­ture” was nev­er merged in­to the mas­ter branch.

Oh, I for­got the men­tion the best bit: we bat­tled er­ror mes­sages with rigid skolems, in­fi­nite types, un­touch­able type vari­ables, “sor­ry, we don’t sup­port im­pred­ica­tive poly­mor­phism” (this one was my per­son­al favourite), what have you, and (to top it all off?) in­fre­quent/ran­dom link­er er­rors on one guy’s ma­chine. Brb af­ter writ­ing a pure link­er.

Thou shalt not take performance for granted.

One of the ma­jor road­blocks in writ­ing the com­pil­er was in get­ting the graph-col­or­ing based reg­is­ter al­lo­ca­tor (1) cor­rect and (2) fast enough. While there isn’t much that could be done about (1), us­ing fgl – one of the more pop­u­lar graph li­braries – proved to be a bad choice. It isn’t clear whether we were us­ing the li­brary wrong or whether we had hit a fun­da­men­tal lim­i­ta­tion. Even­tu­al­ly, we bor­rowed ideas from GHC’s own im­ple­men­ta­tion to get the al­lo­ca­tor to work in re­spectable time.

We had al­so con­sid­ered us­ing alga be­fore we de­cid­ed against it be­cause (1) it seemed to have few­er helper func­tions to work with and (2) the bench­marks at the time didn’t give us enough con­fi­dence to try a new­er li­brary over an old­er one. Hope­ful­ly, some­one can use Lin­ear Haskell to come up with a fast, gen­er­al-pur­pose graph li­brary 😅.

Sim­i­lar­ly, al­though pars­er com­bi­na­tors prove to be very read­able (as op­posed to us­ing a lex­er/pars­er gen­er­a­tor), we once hit an is­sue where 1/3rd of the com­pi­la­tion time in the lex­er (!). The prob­lem was that we were care­less­ly us­ing Mega­parsec’s try in sev­er­al places, lead­ing to a lot of un­nec­es­sary back-track­ing and failed at­tempts.

As I wrote ear­li­er, one prob­lem with us­ing fan­cy ab­strac­tions is that it can get hard to rea­son about per­for­mance. The containers li­brary is prob­a­bly one of the best in this re­gard, it clear­ly out­lines what one should ex­pect from dif­fer­ent op­er­a­tions, as well as pro­vides a suf­fi­cient­ly rich and con­ve­nient API to work in a pure­ly func­tion­al set­ting.

P.S. The RTS made pro­fil­ing su­per con­ve­nient here. We used GHC’s json dumps + ghc-aeson-flamegraph + Bren­dan Gregg’s flamegraph.pl to eas­i­ly vi­su­al­ize bot­tle­necks in the code.

Thou shalt not fall in love with laziness, for it is a fickle mistress.

Lazi­ness is awe­some. When it works. And then it doesn’t. And you’re try­ing to de­bug things and putting traceXXX and deepseq ev­ery­where. And things still get print­ed in a weird or­der, be­cause you in­evitably for­got to an­no­tate one of the guys.

Lazi­ness is al­so not good for per­for­mance in a lot of cas­es, apart from the handy fact that it makes pro­grams with in­fi­nite struc­tures ter­mi­nate. When­ev­er you’re deal­ing with fi­nite struc­tures, hav­ing strict­ness for fields is bet­ter in a lot of cas­es. For ex­am­ple, containers us­es strict­ness in sev­er­al places and sev­er­al per­for­mance-ori­ent­ed pre­sen­ta­tions talk about avoid lazi­ness and its part­ner-in-crime boxed fields.

Thou shalt not covet thy neighbour’s package manager.

Haskell has sev­er­al “de­pen­den­cy man­age­ment so­lu­tions” which I guess is some­where in be­tween C++ where you’re sup­posed to lose your hair try­ing to get things to work (and once it does, refuse to up­grade any­thing lest it break) and Rust where you can prob­a­bly do cargo install cargo-haircut && cargo haircut and have it do the ob­vi­ous with­out get­ting your ass off your com­fy so­fa.

In my lit­tle ex­pe­ri­ence, while stack does work most of time, it suf­fers from a lot of bloat which can cause is­sues if stor­age space/pro­ces­sor speed are not avail­able eas­i­ly – I’m guess­ing this is most­ly a stu­dent bud­get/old lap­top is­sue that pro­fes­sion­al Haskellers don’t en­counter (for ref­er­ence, I’ve been us­ing a Thinkpad X230 with a 256GB SSD and at some point had ~/.stack at size 25 GB+). It would be nice if stack of­fered a clean way to unin­stall things – since it doesn’t, the op­tions left are (a) te­dious: use ghc-unregister to unin­stall stuff and cor­re­spond­ing de­pen­den­cies or (b) slow: nuke ~/.stack, re­run stack build and wait for it to re­com­pile the uni­verse (3).

On a more pos­i­tive note, cabal new-build does seem to work bet­ter than cabal sandbox, so I have my fin­gers crossed that healthy com­pe­ti­tion be­tween the projects makes both of them bet­ter in the fu­ture. Or the Nix hip­pies be­come our new over­lords. Not be­ing picky here.

Remember the refactor day, to keep it holy.

Haskell makes refac­tor­ing a breeze. To be more pre­cise, equa­tion­al rea­son­ing makes refac­tor­ing a breeze. Refac­tor­ing is, in essence a process of term rewrit­ing, and be­ing able to quick­ly sub­sti­tute like-for-like with­out wor­ry­ing about state, or fac­tor out com­mon­ly used code pieces is close to ef­fort­less in Haskell. Type in­fer­ence that just works is al­so very handy as you don’t waste your time spell­ing out ev­ery lit­tle de­tail for the com­pil­er (just aut­ofill the in­ferred type!). Some­times, the com­pil­er will tell you that your func­tion is ac­tu­al­ly more gen­er­al than you thought it was. Free the­o­rems, any­one?

Us­ing op­er­a­tors for com­mon op­er­a­tions proves to be handy here. I find that it is eas­i­er to do pat­tern recog­ni­tion and rewrit­ing when you’ve got a mix­ture of op­er­a­tors and iden­ti­fiers, rather than just lots of let­ters and func­tion ap­pli­ca­tion brack­ets.

Honour thy compiler contributors.

There have been sev­er­al oc­ca­sions over the past few months where ei­ther I or one of my team-mates en­coun­tered a “huh, I didn’t re­alise you could do that, that’s so cool!” mo­ment. That is prob­a­bly not what makes Haskell unique in my opin­ion. What does make it stand it out is that I’m fair­ly con­fi­dent that I’ll reg­u­lar­ly keep hav­ing that “aha!” mo­ment even I keep writ­ing Haskell for the next few years. It might be com­ing from blog posts/pa­pers/navel-gaz­ing posts on r/haskell or some­where else, but there’s al­ways go­ing to be in­ter­est­ing stuff to learn.

As Strous­trup once said, “There are on­ly two kinds of lan­guages: the ones peo­ple com­plain about and the ones no­body us­es”. I’ve prob­a­bly made more than my fair share of com­plaints here, but I must say that I’m very grate­ful to all the peo­ple who have con­trib­uted to GHC and the Haskell ecosys­tem more gen­er­al­ly. Over­all, Haskell most­ly feels like an awe­some, co­he­sive whole. Thank you! :D

Closing thoughts

Writ­ing a com­pil­er in Haskell has been a great source of joy. 9/10 would rec­om­mend.

Bonus

One of my big­gest (ノಠ益ಠ)ノ彡┻━┻ mo­ments over the past few months - Trac 8695.

Al­so, I couldn’t fig­ure out how to fit intero, hoogle and hlint in­to the nar­ra­tive here but all of them de­serve a shout-out. intero does its best to pro­vide live type in­for­ma­tion in Spacemacs (un­til some TH heavy code kills its per­for­mance). hoogle is google but for Haskell, search­ing type sig­na­tures is a breeze. hlint does sim­ple equa­tion­al rea­son­ing and pro­vide many help­ful sug­ges­tions for clear­er code. All these tools are awe­some! (5)

Footnotes

1
Here “com­pose” refers to the fact that you can mix and match stuff, not lit­er­al func­tion com­po­si­tion, al­though I guess you could do the lat­ter too.
2
Per­haps li­brary au­thors are tak­ing Wadler’s words a bit too se­ri­ous­ly?
3
Not sure if I was imag­in­ing it but I rec­ol­lect my ter­mi­nal beep­ing when I was tran­si­tive­ly in­stalling lens for the fifti­eth time.
4

I’m not against sub­typ­ing/in­her­i­tance as a con­cept. In my lit­tle ex­pe­ri­ence, the prob­lem is that for high­er-lev­el prob­lems (code or­ga­ni­za­tion etc.) it is eas­i­er to slip in­to the trap of adding just a lit­tle bit of more of mu­ta­tion/state­ful­ness/in­tru­sive­ness etc.

Once you’ve done that, there is in­creased hes­is­tance in chang­ing large amounts of code as many in­vari­ants are not en­cod­ed in the type sys­tem but in com­ments or in lost mem­o­ries. Hav­ing read mul­ti­ple books geared to­wards OO pro­gram­mers re­gard­ing code hy­giene, best prac­tices, and de­sign pat­terns, I’ve found the giv­en ad­vice to be ei­ther triv­ial­ly ob­vi­ous, not re­al­ly mak­ing sense, or over­ly com­pli­cat­ed/time-con­sum­ing to en­force by hand. While these of­ten em­pha­size test­ing, which can cer­tain­ly com­ple­ment refac­tor­ing and give you more con­fi­dence that you’re main­tain­ing in­vari­ants cor­rect­ly, it can­not be a sub­sti­tute for hav­ing strong types – the cost of main­tain­ing that many tests is just too high.

5
I wish we (the Haskell com­mu­ni­ty) would spend more ef­fort in get­ting tool­ing in­to the hands of be­gin­ners right away, not just GH­Ci. It re­al­ly makes for a big qual­i­ty-of-life im­prove­ment. Users from oth­er lan­guages may not even re­al­ize that such tools could/do ex­ist, so they might not go seek them in the first place.