4 ms·

I would love to know more about what the author found difficult regarding type checking. As long as you don't screw up your semantics to the point of needing a

I would love to know more about what the author found difficult regarding type checking. As long as you don't screw up your semantics to the point of needing a full blown constraint solver there should be no issues. Edit: by "screwing up semantics" I mostly mean the combination of overloading and implicit conversions, which is known to cause issues in Java, C++, etc.

YorickPeterse 3y ago
The problem for me was that I had a rough idea of how to implement (essentially it's similar to a recursive-descent parser), but I had a difficult time finding appropriate resources to confirm or deny whether my idea was solid, as well as tips and what not. Basically, the existing material is a bunch of existing incredibly complicated implementations, the odd blog post that just throws a bunch of code your way without really explaining the why/thought process behind it, and books that aren't worth the money. The result is that you can of course piece things together (as I did), but it leaves you forever wondering whether you did it in a sensible way, or if you constructed some weird monstrosity. To put it differently: you can probably build a garden by digging some holes and throwing a few plants around, but without the right resources it can be difficult to determine what the impact of your approach may be, and whether there are better ways of going about it. Oh and I'm aware there are resources on gardening, it's just a metaphor :)
- Q6T46nT668w6i3m 3y ago
  As someone who has written many compilers and type checkers, I agree. There’s very little information online about the subject. I think part of the issue, for me, was psychological: I felt like I was missing some implementation theory that was presented alongside other compiler subjects (e.g., LALR) when the reality is that you’re mostly implementing very simple Boolean operations.
- ww520 3y ago
  While helping a bit, it's difficult to learn or reverse engineer from existing type checking code because a lot of them are mundane repetitive code implementing some high level theory and algorithms. The actual code is too far remote from the theory. You really want to start from the theory and the overall picture. The Dragon book has a chapter on type checking. It gives explanations on many topics. It has plenty of examples. It has type treatments on different areas of a language, like expression, array, struct, function, pointer, etc. Despite being really old, its ideas and explanation on the topic are still relevant.
- mabster 3y ago
  I think the larger writings like books are generally going to be written by academics so they'll be rigorous and hard to read. So that leaves blog posts for most developers actually implementing this stuff. But the solution here is that when you finally figure out a good strategy to deal with something muddy like this is to write that better blog post :)
  - YorickPeterse 3y ago
    I'm planning on doing something similar to what I did for pattern matching [1]: basically building something entirely standalone that fits in 2k LOC or so, and explains the basics (i.e. nominal typing plus basic sub-typing), hopefully such that people can then take that and extend it. As for _when_ I'll do that, that depends on when I can convince my inner critic to actually commit to the idea :) [1]: https://github.com/yorickpeterse/pattern-matching-in-rust https://github.com/yorickpeterse/pattern-matching-in-rust
paulddraper 3y ago
TypeScript type-checking is quite complicated. I'm sure no human being on earth could pass a test of "does this compile" But that's an exception, and deliberately decided to be complex.
alex_lav 3y ago
I know nothing about how one would make a type checker, but it sort of feels like your comment is "As long as you don't encounter any issues, there won't be any issues", no?
brundolf 3y ago
I've been implementing a language with a TypeScript-like type system, and while the core system is pretty intuitive (values combining with other values, determining whether basic value types fit into others), some of the fringes have been challenging: - Generics, especially inferring generic type params - Recursive types - Deeply mutable vs immutable types - Type refinement based on checks/usage - Giving good error messages for deep type mismatches (though I'm not sure TypeScript itself has figured this one out yet, lol) etc. And even the stuff I've figured out, I figured out almost all from scratch (sometimes having to bail and take a totally new approach midway through). I would love to read a book giving me a proper bottom-up walkthrough of the current landscape of type system implementation
nicoburns 3y ago
Would type-inference also "screw up the semantics"? My understanding is that this generally operates via some kind of constraints solving.
- orthoxerox 3y ago
  Depends on how much type inference you want. If you want ML-style total type inference when you expect the compiler to deduce the parameter and the return types of your functions, then yes. Local variable type inference isn't hard at all, unless you want to do stuff like Rust: declare a variable without an initial value and infer its type from the first assignment downcode.

YorickPeterse 3y ago

The problem for me was that I had a rough idea of how to implement (essentially it's similar to a recursive-descent parser), but I had a difficult time finding appropriate resources to confirm or deny whether my idea was solid, as well as tips and what not. Basically, the existing material is a bunch of existing incredibly complicated implementations, the odd blog post that just throws a bunch of code your way without really explaining the why/thought process behind it, and books that aren't worth the money. The result is that you can of course piece things together (as I did), but it leaves you forever wondering whether you did it in a sensible way, or if you constructed some weird monstrosity. To put it differently: you can probably build a garden by digging some holes and throwing a few plants around, but without the right resources it can be difficult to determine what the impact of your approach may be, and whether there are better ways of going about it. Oh and I'm aware there are resources on gardening, it's just a metaphor :)

Q6T46nT668w6i3m 3y ago
As someone who has written many compilers and type checkers, I agree. There’s very little information online about the subject. I think part of the issue, for me, was psychological: I felt like I was missing some implementation theory that was presented alongside other compiler subjects (e.g., LALR) when the reality is that you’re mostly implementing very simple Boolean operations.
ww520 3y ago
While helping a bit, it's difficult to learn or reverse engineer from existing type checking code because a lot of them are mundane repetitive code implementing some high level theory and algorithms. The actual code is too far remote from the theory. You really want to start from the theory and the overall picture. The Dragon book has a chapter on type checking. It gives explanations on many topics. It has plenty of examples. It has type treatments on different areas of a language, like expression, array, struct, function, pointer, etc. Despite being really old, its ideas and explanation on the topic are still relevant.
mabster 3y ago
I think the larger writings like books are generally going to be written by academics so they'll be rigorous and hard to read. So that leaves blog posts for most developers actually implementing this stuff. But the solution here is that when you finally figure out a good strategy to deal with something muddy like this is to write that better blog post :)
- YorickPeterse 3y ago
  I'm planning on doing something similar to what I did for pattern matching [1]: basically building something entirely standalone that fits in 2k LOC or so, and explains the basics (i.e. nominal typing plus basic sub-typing), hopefully such that people can then take that and extend it. As for _when_ I'll do that, that depends on when I can convince my inner critic to actually commit to the idea :) [1]: https://github.com/yorickpeterse/pattern-matching-in-rust https://github.com/yorickpeterse/pattern-matching-in-rust

paulddraper 3y ago

TypeScript type-checking is quite complicated. I'm sure no human being on earth could pass a test of "does this compile" But that's an exception, and deliberately decided to be complex.

alex_lav 3y ago

I know nothing about how one would make a type checker, but it sort of feels like your comment is "As long as you don't encounter any issues, there won't be any issues", no?

brundolf 3y ago

I've been implementing a language with a TypeScript-like type system, and while the core system is pretty intuitive (values combining with other values, determining whether basic value types fit into others), some of the fringes have been challenging: - Generics, especially inferring generic type params - Recursive types - Deeply mutable vs immutable types - Type refinement based on checks/usage - Giving good error messages for deep type mismatches (though I'm not sure TypeScript itself has figured this one out yet, lol) etc. And even the stuff I've figured out, I figured out almost all from scratch (sometimes having to bail and take a totally new approach midway through). I would love to read a book giving me a proper bottom-up walkthrough of the current landscape of type system implementation

nicoburns 3y ago

Would type-inference also "screw up the semantics"? My understanding is that this generally operates via some kind of constraints solving.

orthoxerox 3y ago
Depends on how much type inference you want. If you want ML-style total type inference when you expect the compiler to deduce the parameter and the return types of your functions, then yes. Local variable type inference isn't hard at all, unless you want to do stuff like Rust: declare a variable without an initial value and infer its type from the first assignment downcode.