I am the 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)
- Fact: ADTs and ASTs are like peanut butter and jelly, unless you’re allergic to functional programming, in which case, please accept my condolences.
- Fact: Pattern matching is just nerdspeak for awesomeness.
- Fact: Functional programming is basically tetris but with a wider range of side effects allowed.
- Fact: If it type checks, it must be correct.
- 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):
- Ordinary value-level functions have types
a1 -> a2.
- (G)ADT value constructors can be applied and composed like value-level functions.
- Records fields can be used as value-level functions for projection. (This is probably a bad default, but hey, at least it is consistent!)
- Values can be grouped and passed around.
- Type families (type-level functions) have kinds
k1 -> k2.
- Type constructors can be applied and composed like type-level functions (1). They can also be abstracted over.
- Type classes can be used as type level functions (via
- Constraints can be grouped and passed around.
- Adding a small amount of primitives gives you
Qwhere you can manipulate Haskell code using (you guessed it) the usual pattern matching, functions, types and type classes.
Thou shalt not take the name of the Lambda thy God in vain.
(Author’s note: 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
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 stuff in a very flexible way by just
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 reached the point where I stop telling the compiler “aww, fuck 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) and while internalising the “logic” behind the symbols can be helpful while writing code (2), reading someone else’s code written using them feels like reading golfed code without the irony.
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.
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:
- 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).
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
Integerwhile parsing and as
Intafter 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
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 fall in love with 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
deepseq everywhere. And things still get
printed in a weird order, because you inevitably forgot to annotate one of the guys.
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 avoid 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 ass 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
to uninstall stuff and corresponding dependencies or (b) slow: nuke
stack build and wait for it to recompile the universe (3).
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, and 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 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! :D
Writing a compiler in Haskell has been a great source of joy. 9/10 would recommend.
One of my biggest (ノಠ益ಠ)ノ彡┻━┻ moments over the past few months - Trac 8695.
Also, I couldn’t figure out how to fit
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 provide many helpful suggestions
for clearer code. All these tools are awesome! (5)
- Here “compose” refers to the fact that you can mix and match stuff, not literal function composition, although I guess you could do the latter too.
- Perhaps library authors are taking Wadler’s words a bit too seriously?
- Not sure if I was imagining it but I recollect my terminal beeping when I was transitively
lensfor the fiftieth time.
I’m not against subtyping/inheritance as a concept. In my little experience, the problem is that for higher-level problems (code organization etc.) it is easier to slip into the trap of adding just a little bit of more of mutation/statefulness/intrusiveness etc.
Once you’ve done that, there is increased hesistance in changing large amounts of code as many invariants are not encoded in the type system but in comments or in lost memories. Having read multiple books geared towards OO programmers regarding code hygiene, best practices, and design patterns, I’ve found the given advice to be either trivially obvious, not really making sense, or overly complicated/time-consuming to enforce by hand. While these often emphasize testing, which can certainly complement refactoring and give you more confidence that you’re maintaining invariants correctly, it cannot be a substitute for having strong types – the cost of maintaining that many tests is just too high.
- 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.