3 ms·
> (Yes, Rust 4ev3r! ;)) Rust has a perfectly nice type system by modern standards, but it's nowhere close to showing you just how deep the rabbit hole goes whe
by tialaramex 4y ago
> (Yes, Rust 4ev3r! ;))
Rust has a perfectly nice type system by modern standards, but it's nowhere close to showing you just how deep the rabbit hole goes when it comes to avoiding bugs at runtime by having stronger type systems.
For example suppose my Rust function takes a slice of clowns (named unimaginatively "clowns") and also a usize integer k. Can we write clowns[k] ? Rust says sure, it will emit a runtime bounds check to confirm that k is inside the bounds of the slice. If there are sixteen clowns, and we ask for k = 20, this Rust code will panic at runtime.
But we can do better, if we are willing to pay for it. Dependent Types. In a language with dependent types and enough inference our type inference system will conclude that k can be 20 here, thus clowns must be a slice of at least 21 clowns, but this slice has only sixteen clowns - type error during compilation, either k or clowns are wrong.
Now, for cases where bounds checking would be the reasonable thing to do, Dependent Types just result in you writing bounds checks, ie in this case checking k < 16, and so it's possible you will just end up doing more work to result in a program that still just says, at runtime, "Nope, not enough clowns" or whatever like in Rust. The type system will require you to write correct bounds checks, but the Rust bounds checks are auto-generated, so they're correct too.
But in cases where bounds checks were not the only sensible approach, or maybe you didn't even realise a bounds check would be emitted because you assumed it was statically correct - this can catch some bugs at compile time which would otherwise survive into a running program, "Shifting left" is I believe the usual phrase to describe this improvement.
If you thought the function is obviously correct, "Of course there are more than k clowns" but it isn't, the type error may cause you to take that extra moment to think about it. "Wait, why can there be fewer clowns than... oh, I didn't mean clowns here, this should say circus_performers. I'm not even using the right slice!".
- creata 4y agoI don't know about this. Even some of the people who use dependently typed proof assistants seem to doubt that they should be used much in the programming part (as opposed to the proving part). Also, some of the examples you give might be addressed well enough by Rust's const generics. https://xenaproject.wordpress.com/2020/07/05/division-by-zero-in-type-theory-a-faq/ https://xenaproject.wordpress.com/2020/07/05/division-by-zer... https://www.cs.ox.ac.uk/ralf.hinze/WG2.8/26/slides/xavier.pdf https://www.cs.ox.ac.uk/ralf.hinze/WG2.8/26/slides/xavier.pd...
- elcritch 4y ago> Rust has a perfectly nice type system by modern standards I disagree -- Rust's type system is pretty weak and very limiting compared to other modern languages like Typescript, Nim, Zig, or even C++. That's without even without getting into dependent type languages. There are so many basic patterns which Rust's type system can't handle, especially when it comes to compile time types. For example, one recent thing I ran into was trying to downcast a dyn Trait into another more specific dyn Trait. It's just not possible, at least on stable. Instead you have to do ugly work like getters that return sub-traits wrapped in optionals. Ick, the visitor pattern was easier. Rust's type system philosophically takes a very strict "closed system" approach too. Meaning one can only really write code that's valid for every known instance. This limits entirely valid and useful subset of programs to programmers using libraries or language features. I'm not talking about runtime dynamism, but compile time dynanism. C++ with concepts provides a much more powerful and adaptive type system. Programming in Rust frustrates me that I can't do any of the compile time checks that I've become accustomed to doing in other languages. It makes doing them at runtime difficult as well. > but it's nowhere close to showing you just how deep the rabbit hole goes when it comes to avoiding bugs at runtime by having stronger type systems. Totally agree on that! Though that's missing how powerful compile time programming in general can be even without the dependent types. Personally I'm excited to see how C++ Concepts can evolve. Though I'm not sure how much that starts overlapping with Dependent Types.
- tialaramex 4y ago> Personally I'm excited to see how C++ Concepts can evolve. So, C++ 20 Concepts is basically what Bjarne Stroustrup proposed for a future version of his C++ language in the early 2000s. Several people proposed and WG21 accepted, a far more capable feature set for Concepts, this is often referred to as C++ 0x Concepts, since it was accepted for C++ 0x, the standard that would eventually (after years of delays) become C++ 11. Bjarne wrote a paper arguing that this more powerful feature set was unnecessary and perhaps unworkable, and WG21 wound up removing Concepts from C++ 11 entirely (and the people behind it mostly got the message and ceased working on C++ altogether). A decade later, something that's close to Bjarne's original proposal became a C++ 20 feature. C++ 0x Concepts was similar to Rust's Trait system in many ways. Particularly notable features of C++ 0x Concepts you might recognise in Rust's Traits: 1. Third parties can implement a C++ 0x Concept for some type which was not originally conceived with this Concept in mind, they just write the implementation and it works. 2. C++ 0x Concepts must be explicitly implemented they're not just a syntactic requirement that could be satisfied by happenstance in a type which is not in fact suitable. 3. As a result of 1 & 2, the C++ 0x Concepts have Semantics which in C++ 20 Concepts are confined to the idea of "modelling" a Concept or else IFNDR.