3 ms·

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

by xigoi 2y ago

rscho 2y ago
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.
zellyn 2y ago
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.
- zellyn 2y ago
  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! ;-)
kccqzy 2y ago
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/AlgorithmW.lhs 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/fa8a8ae12a198b41c6339e8a5c45978a https://gist.github.com/kccqzy/fa8a8ae12a198b41c6339e8a5c459... Then I proceeded to change various things to "break" the algorithm and see how they are broken.
munificent 2y ago
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.
- runevault 2y ago
  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).
- childintime 2y ago
  How about the Zig type system?

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

by xigoi 2y ago

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

rscho 2y ago

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.

zellyn 2y ago

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.

zellyn 2y ago
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! ;-)

kccqzy 2y ago

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/AlgorithmW.lhs 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/fa8a8ae12a198b41c6339e8a5c45978a https://gist.github.com/kccqzy/fa8a8ae12a198b41c6339e8a5c459... Then I proceeded to change various things to "break" the algorithm and see how they are broken.

munificent 2y ago

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.

runevault 2y ago
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).
childintime 2y ago
How about the Zig type system?