Rust: When Empty Isn't Bottom
7 points by ettolrach
7 points by ettolrach
maybe i'm thinking about this in a way that type theorists don't
but i think of the bottom type in rust (and other languages) as being a subtype of every other type whether you have subtyping or not, because you can write an infinite loop that the compiler can't tell is infinite. or you can unplug it during execution. so, "never returns" is an outcome for every type
but the named empty type (!), or the multiple named types that are empty (in rust, any enum with no cases), are not necessarily subtypes of every type
for structural typing, they'd be the same thing. any uninhabited type is structurally identical
Excellent post, thank you.
Is it generally true that type coercion only works at "the top level", i.e. has no support for variance? Maybe even "the difference between subtyping and type coercion is that subtyping has to support variance"?
That's probably completely wrong, I just always found it hard to explain (on a technical level) why these two concepts are different from each other.
No, at least not in Rust! Coercion happens with variance and subtyping, too. While it's true that Box<!> is not a subtype of Box<i32>, any two types with lifetimes will have a subtype relation. That's becuase Rust does have subtyping for types which have lifetimes. So for a generic T, we have that &'static T a subtype of &'a T for some lifetime 'a because 'static is the "bottom lifetime". And lifetimes follow the normal, common variance rules. So for example:
fn f() -> for<'a> fn(&'a str) -> &'a str {
|s| s.trim()
}
fn g() -> for<'a> fn(&'a str) -> &'static str {
|_| "a static string"
}
fn main() {
// works even though g's return type is 'static, not 'a!
let func: for<'a> fn(&'a str) -> &'a str = g();
}
The reason why this works but the example in the post doesn't is that there's no subtyping between types without lifetimes, or maybe if it's easier to conceptualise: there is no subtyping between generics. We can only compare them if they have lifetimes. There's a page in the Rust Reference about it: Subtyping and variance.
If I had to explain the difference between coercion and subtyping, it's that coercion is a list of when the language can convert from one type to a different type which is more convenient (or rather, correct) at the point where it's being used. Subtyping is when you can literally treat the type as if it's a different one according to rules as defined by some preorder (for example, take an OO language like Java. Because ArrayList is a subtype of AbstractList, a function can treat an ArrayList just like AbstractList. It will look for the pointer to the vtable (like Rust's dyn), then looks up the function pointer for a method called clear, for instance, and then calls it. The language treats both of those types the same, even if they give different results). One may actually convert the value while the other treats the one type as if it's the other without actually doing anything different.
And yes, Rust's coercions are not necessarily no-ops! For example:
use std::ops::Deref;
struct S(String);
impl Deref for S {
type Target = i32;
fn deref(&self) -> &Self::Target {
&45
}
}
fn main() {
let s = S(String::from("meow"));
// coerces from &S to &i32, but is not what we would usually call
// a "typecast"! we actually change the value from <reference to
// struct containing a string> to <reference to i32 of value 45>.
let derefed: &i32 = &s;
assert_eq!(45, *derefed);
}
The Haskell example makes use of laziness but what if I use strictness annotations? If I have an enum with !Void as the payload, do I still have to pattern match on that variant or does it behave like Rust where the variant is considered impossible?