Rust: When Empty Isn't Bottom

hc | a day ago

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

tentacloids | 14 hours ago

Yeah I think of it as: empty is impossible, bottom is meaningless. Empty is something the type system can work with (as in the announcement somewhere, Result<T, !> allows you to elide matching Err(_)). Bottom is a hole that leads outside the type system's closed world of understanding (as in your examples); trying to reason with it is not useful, so it might as well be any type.

zesterer | 19 hours ago

Yeah, agreed. It's a bit of a bizarre thing to claim. Bottom doesn't need to automatically coerce to any other type, it just needs to be legally convertable to any other type without diverging control flow, and that's trivially demonstrable with the following, which will always compile no matter what type <lhs> is expected to be.

<lhs> = match panic!() {};

ghoti | 18 hours ago

The word "always" in this comment gives the impression that this is a deliberate property of the language or a guarantee that users can rely on, but this is not the case. For example, the following will fail to compile with the forthcoming type_alias_impl_trait feature.

type ImplsIterator = impl Iterator;
let x: ImplsIterator = match panic!() {}

It is possible that this may become valid sometime after the feature stabilizes, but it is not currently considered a blocker for stabilization.

[OP] ettolrach | 14 hours ago

I probably should have mentioned impl as another big example of where a bottom type would work, but ! won't coerce. Always great to have the example that you can't return ! for an impl Default return type to hand.

zesterer | 12 hours ago

Sure. I think that's rather intentionally misinterpreting what I'm saying though. The point of type theory concepts is not to making specific commentary about the surface behaviour of languages, but about the kinds of statements that sufficiently powerful type systems allow us to make, and Rust's type system is powerful enough to reason about Bottom.

mond | a day ago

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.

[OP] ettolrach | a day ago

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);
}

lyxia | 22 hours ago

One thing that gets in the way of variance is that the representation of a type matters a lot in Rust. For exampe (usize, !) and (usize, usize) don't have the same size, so it takes a bit of work to convert one to the other, while most would expect a subtyping coercion to be a noop.

gignico | a day ago

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?