Hacker News Reader

Comment by xigoi | Hacker News Reader

Does anyone know of a good resoucce for creating a statically typed language with stuff like parametric polymorphism and basic type inference?

View on HN

People have asked me to write something like this many times and one of the main reasons I haven't is because it's so open-ended.

With Crafting Interpreters, I felt like there was a reasonably small self-contained language I could come up with that covered almost all of the concepts I wanted to teach: variable scope, functions, closures, classes and dynamic dispatch, control flow, etc.

With type systems, there are a lot of forks in the design space and no clear "best" path:

* Does the language have subtyping or not?

* Are generics erased or reified?

* Is generic code specialized at compile time or not?

* Is type inference local or Hindley-Milner?

Any choice I make here would miss out on a lot of important material from the unchosen branch and disappoint readers who wanted me to take the other path.

Maybe the right answer is a broader survey-style book that tries to cover a bunch of different options (like Types and Programming Languages). But then you lose the fun of building one coherent thing.

Personal opinion, I'd rather you build a specific thing, with perhaps brief periods where you talk about the pros and cons of the most notable options and then why you chose what you did. As you said there's a joy in a complete system, and at least to me there would be value in discussing your set of whys because that can show people less used to system design the types of considerations involved.

I will not fault you if you don't get to any such project (I remember discovering Crafting Interpreters around the time you were like... halfway through part one? and seeing how long it took you to get through the rest of the book. The care you take to both give useful technical information and make your writing clear takes a great deal of work), but I would certainly read it as I've read much of CI if it ever exists (I need to finish going through part 2, I'm up to Closures).

How about the Zig type system?

Modern compiler implementation in ML by A. W. Appel

There are (inferior) versions of the same in C and Java. I'd use them together with the ML version.

The main crux of parametric polymorphism and type inference is just implementing Algorithm W. Just find a toy implementation online and poke at it.

For me, when I learned it myself, I simply took the toy implementation at https://github.com/wh5a/Algorithm-W-Step-By-Step/blob/master... realized that it was written in an extremely outdated style, modernized it, cleaned up, and ended up with https://gist.github.com/kccqzy/fa8a8ae12a198b41c6339e8a5c459... Then I proceeded to change various things to "break" the algorithm and see how they are broken.

It’s a bit more theoretical, but working my way (slowly, with many re-watches of certain videos) through the Coursera compilers course was a major milestone for me: I highly recommend finding an accessible way to do one of the CS things you think only Wizards can do: once you tackle one or two such projects, and realize that it’s hard, but mostly just slogging your way through it, it can be an enormous confidence boost :-)

I’m always happy to help anyone going down this path: zellyn@(most things) if anyone reading this wants to try but is feeling nervous.

One additional note: the provided code for that course is (or was a decade+ ago!) either C++ or Java, but the tests and test scaffolding are fairly straightforward.

I opted to translate into Go as I went, which meant:

- a lot more work/time

- slower progress

- no “if you fill in this missing piece, we’ve provided the rest so your compiler will work end-to-end”

- an annoying amount of trying to print ASTs exactly like the C++/Java code for validation purposes

But I got to use Go instead of those other languages! ;-)

Reply on news.ycombinator.com