Universal properties for types

With recent-ish proposals to add a trait for dynamically sized types to Rust (rfc2984, rfc3396), as well as long-standing issues with the language such as size == stride, I’ve been thinking of the concept of the set of properties that hold for any type of a language. These can be explicit (in that they’re tied to specific operations) or implicit (in that they’re not).

For Rust, these properties include the following:

1. You can take a reference to a value of any type. (Therefore, types are always stored in byte-sized chunks.)
   • Additionally, the address of a reference is stable. (Therefore, you can’t store a reference as the contents of the referee in the case of small types.)
2. A type’s alignment is always known at compile time can always be determined at run time. (Thanks to /u/OnTheSideOfDaemons for mentioning trait objects.)
3. A type’s size can always be determined at run time.
4. A type’s size is always a multiple of its alignment.
5. A value of type T located at address A owns the entire region of memory [A, A + sizeof(T)) (i.e. interior padding bytes can’t be repurposed for something else).
6. A value of any type can be moved by copying its bytes.

This is complicated by the presence of implicit Sized bounds on type parameters in some places, creating a subset of “non-weird” types that have an additional set of properties.

What do we do when we want to relax some of these assumptions? Some of them, such as (3) or (4), can only be taken advantage of by calling certain functions^[1], so we can lock them behind a certain trait and things at least won’t silently break. To avoid errors in previously compiling code, we can add an implicit bound on that trait in old editions. This means that some existing code will have superfluous trait bounds, but we can infer which of these are truly necessary and, for instance, lint the bounds that could be removed.

Assumptions such as (5) or (6) are implicit, and there are many ways to rely on them using unsafe code that can’t be detected in general. We could still add an opt-out trait for these, but we have to be conservative with infering when bounds on those traits can be removed – we shouldn’t remove them for functions that are unsafe or use unsafe code, for instance.

While relaxing some of the properties mentioned above can make it easier to interoperate with code in other languages (e.g. extern types and C) or achieve more compact data layouts (e.g. size != stride), it has the downside of adding a new implicit trait. This increases the mental load for programmers, especially those who write libraries or use unsafe code, which is why the lang team has been reluctant to do this.^[2]

Alternatively, we can let users opt out of these assumptions on the field level. Rust already does this for #[repr(packed)] structs, which relaxes alignment requirements for fields. Since references must always be aligned in Rust, you can’t take a reference to a field of a packed struct, and this restriction would follow for other ways to opt out of the usual layout requirements for a field.

For (5) (size == stride), we can provide an attribute for fields that lets Rust reuse a field’s padding or even break a field of a struct type into its components. Like with fields in packed structs, fields with this attribute would not be referenceable. Such an attribute would be akin to C++’s [[no_unique_address]] and has been mentioned by the Rust Language Design Team’s Frequently Requested Changes, as well as at least one proposal on IRLO.

Another option is to provide a wrapper type that prevents you from taking an advantage of a given assumption. For example, Rust provides the Pin type, which wraps “some kind of pointer” and restricts moving an object out of the pointer. This gives a way to deal with non-trivially movable types without forcing the rest of the programmers to deal with types that break assumption (6). On the other hand, it’s conceptually more complicated than a Move trait and the ergonomics around things such as pin projection aren’t there yet.

Other languages

The set of universal properties for types is different in different languages.

In C++, not all types are moveable by moving their bytes, making this a universal property that is present in Rust but absent in C++. On the other hand, all types in C++ have a size of at least 1, in contrast to Rust, which has zero-sized types.

Another language I use often is Java because funny block game go brr. There are few properties that hold for all types because Java distinguishes between primitive types and classes. The ones I can think of that don’t hold in Rust are that:

• You can create local variables of any type
• You can make fields of any type
• You can compare instances of any type with ==
• Every type has a default value

The first two properties don’t hold for !Sized types in Rust (for fields, only the last field of a struct can be dynamically sized). In effect, you can think of Java having only sized types. The third property doesn’t hold because the distinction between == and equals doesn’t have a close equivalent in Rust, which lets you have values of any type directly rather than references. Finally, the fourth property is just a Java design fail.

For everything except for the eight special types, you can call any method in Object. This currently means that:

• You can compare ‘by value’ using equals (needs the PartialEq trait in Rust)
• You can compute a hash code (needs the Hash trait in Rust)
• You can convert an instance to a string (needs the Display or Debug trait in Rust. Java doesn’t distinguish between a “display” representation and a “debug” representation.)
• You can use an instance as a lock

And also:

• An instance created using a new call will compare != with an instance created using a different new call

Note that unlike in Rust, these are semantic properties rather than memory layout-related ones. Having (value) equality or hash code calculation available for every class is problematic because these operations don’t make sense for certain classes (java.io.FileReader?).^[3] Arguably, toString doesn’t either, but Rust’s approach also has a small annoyance: while you can #[derive(Debug)] so easily that you might as well always do it, you can’t debug-print a generic type unless it has a Debug bound.

There are efforts to relax some of these baseline-ish assumptions; namely, the semantics of == currently prevents objects from being stored inline for performance. The who-knows-how-long-it’s-been-running-for Project Valhalla aims to add ‘value types’ that opt out of certain properties that all objects used to have.

So what does this all mean?

The idea of universal properties that hold for all types in a programming language could turn out to be powerful. It gives us a new way of thinking about various proposals to evolve a language, namely by relaxing one or more of them. Given the need for types that lack a given universal property, we have several ways of fulfilling this need:

• Provide a wrapper type that provides access to a value without exposing the property, as in Rust’s Pin.
• Provide a way to opt out of the property on the level of variables (fields, parameters, or locals).
• Add a trait encoding the property, and add a bound on that trait to generic parameters by default.

The first two methods are more suitable for properties that rarely need to be broken. The third method is suitable for properties that more than rarely fail to hold, or for those where the decision to follow an assumption is usually consistent for a given type. For example, it would be possible to add value semantics to Java using an annotation on variables that want to opt into it, but given a class like Vec3 that you’d almost always prefer to avoid a heap allocation for, you’d have to put that annotation on every variable of that type.^[4]

The trait approach, however, has its own disadvantages. Once the trait is added, many generic items will have stricter requirements on their type parameters than necessary, and adjusting these bounds will lead to code churn. Adapting to a formerly universal property being relaxed is especially difficult if it is implicit or if relying on it was pervasive. Adding a new trait also adds cognitive complexity to the language.

Aside from describing language evolution, the idea of universal properties gives an area for comparing different programming languages. It can also guide the development of new languages by providing insight on which assumptions are likely to be beneficial or problematic for achieving goals such as performance or interoperability with other languages.