logoalt Hacker News

munificentyesterday at 5:09 PM1 replyview on HN

An anecdote about how a toy project _really_ helped me out:

I work on Dart professionally. I've also been tinkering on a toy programming language that may never see the light of day. My toy language has gone through several incarnations but a while back I was working on adding algebraic datatypes, pattern matching, and exhaustiveness checking to it.

The canonical algorithm for exhaustiveness checking is this paper by Luc Maranget: http://moscova.inria.fr/~maranget/papers/warn/warn.pdf

When I first started dabbling in programming languages over a decade ago, I tried to understand that paper for weeks and just could not wrap my head around it. I don't have much of a formal CS background and that paper was impenetrable to me.

So here I am tinkering on my toy programming language and I run into again. I give it another try and laboriously implement it in my interpreter, basically doing a straight translation. I don't understand the code, but it seems to sort of work. So then I start refactoring it a tiny bit at a time into a style that fits the way I think about code. Eventually the algorithm sort of folds into itself and before I know it, I finally understand how it works. The end result was only a page or so of code, but my toy language had real exhaustiveness checking work.

Meanwhile, at work, I am working on adding pattern matching and exhaustiveness checking to Dart [1]. Exhaustiveness checking here is a much harder proposition because Dart has subtyping, unlike my toy language and the ML languages that Maranget's paper works on.

I'd been hacking away at an exhaustiveness algorithm for Dart based on a couple of papers about Scala's approach but they were sort of approximative and inelegant (in my opinion, maybe they are a great fit for Scala).

But once I understood Maranget's algorithm from implementing it in my toy project, it finally clicked for me how it could be adapted to work with subtyping in a sound, coherent way. I wrote it up as quickly as I could and (with a lot of additional help from a teammate to handle generics), that became the algorithm we shipped:

https://github.com/dart-lang/language/blob/main/accepted/3.0...

It wouldn't have happened if I hadn't coincidentally been working on a toy pattern matching implementation at home.

[1]: https://dart.dev/language/patterns


Replies

zestereryesterday at 10:47 PM

I love this, this is exactly the sort of thing I've experienced too: building the toy project gave me an on-ramp to something similar but much more complicated in the future.