Existential Types in Rust

This article brought to you by LWN subscribers

Subscribers to LWN.net made this article — and everything that surrounds it — possible. If you appreciate our content, please buy a subscription and make the next set of articles possible.

By Daroc Alden
April 24, 2024

For several years, contributors to the Rust project have been working to improve support for asynchronous code. The benefits of these efforts are not confined to asynchronous code, however. Members of the Rust community have been working toward adding explicit existential types to Rust since 2017. Existential types are not a common feature of programming languages (something the RFC acknowledges), so the motivation for their inclusion might be somewhat obscure.

The benefits of static type systems are well-known, but they do have some downsides as well. Type systems, especially complex type systems, can make writing type signatures painful and produce complicated error messages. A recent comment on Hacker News showed an example of types added to the popular SQLAlchemy Python library, lamenting: "Prior to the introduction of types in Python, I thought I wanted it. Now I hate them."

These complaints are hardly new; they drove C++ and Java to adopt auto and var keywords for variable declarations, respectively, in order to save programmers from having to actually write down the lengthy types assigned to values in their programs. Both of these features reduce the burden associated with complex types by letting the compiler do some of the work and infer the relevant types from context. These mechanisms don't represent a complete solution, and cause their own set of problems, however. Using them, it is easy to accidentally change the inferred type of a variable in a way that breaks the program. And the resulting error messages still refer to the full, unreadable types. Additionally, local type inference doesn't help with types in function signatures.

There are solutions to all of these problems — the C++ committee introduced concepts, which can help simplify some complex types behind an interface, partially to address this — but Rust has been trying to avoid falling into the trap altogether, despite an increasingly complex type system of its own. Existential types are one mechanism intended to make dealing with complex types easier. Unfortunately, they are also currently not well-explained or well-understood outside a few specific niches. The RFC calls this out as one problem with the current status quo:

The problem stems from a poor understanding of what "existential types" are — which is entirely unsurprising: existential types are a technical type theoretic concept that are not widely encountered outside type theory (unlike universally-quantified types, for instance). In discussions about existential types in Rust, these sorts of confusions are endemic.

Existential types get their name from mathematical logic via the existential quantifier, but the realization of the concept in an actual programming language like Rust is a good deal less abstract. Simply put, existential types are types that exist, but which cannot be directly manipulated outside of their scope. Normal generic types (referred to as universally-quantified types in the quote above) let the caller of a function decide what concrete type the function should be called with. In this circumstance, the function can only interact with values of this type as opaque values, because it doesn't know what type the caller will choose. Existential types invert the direction of that control, letting the function itself decide what concrete type should be used, while the caller of the function must now treat the values as being of an unknown type.

Existential types today

Rust actually already has a limited form of existential types, just not by that name. Instead, the Rust documentation refers to them as impl Trait types. They allow the programmer to say that a function takes or returns some type that implements a trait, without actually saying what that type is. For example, the caller of this function can use the return value as an iterator, but cannot see what type it has (in this case, a Range):

fn example() -> impl Iterator<Item = u8> { 0..10 }

impl Trait types are useful for abstracting away API details without introducing any kind of runtime indirection. At compile time, the compiler knows the specific concrete type that underlies an impl Trait type, but it doesn't need that type explicitly written out, nor does it need to complicate error messages by showing it. In contrast to a mechanism like auto, changing the body of the function in a way that results in returning a type incompatible with the type signature (in this case, one that is not an Iterator) still causes a type error.

Abstracting away the inferred type like this is especially useful for asynchronous functions, which are syntactic sugar for functions that return impl Future. Since asynchronous functions return existential types under the hood, any limitations or improvements to existential types affect asynchronous functions as well. Existential types are also useful for returning closure types, which do not actually have names in Rust. (A design decision made for efficiency reasons that C++ actually shares — it permits better inlining of anonymous functions.)

In 2018, Rust gained the ability to have impl Trait types as the argument to a function as well. However, these types still remain quite constrained compared to full existential types. For example, they can't appear in type aliases, or be stored inside structures. It's only in December 2023 with Rust 1.75 that they were allowed as return values from trait methods.

Existential types in the future

But there is one more subtle restriction on impl Trait types — every occurrence in the program refers to a different concrete type. Two functions that both return impl Debug, for example, could very well return two entirely different types. This makes it hard to write a collection of functions (such as implementations of the same interface for different configurations or architectures) that are all guaranteed to return the same type, without explicitly writing out that type.

There is a workaround for that use case, but it involves a layer of run-time indirection by making functions return a trait object — a heap-allocated structure full of function pointers that presents an opaque interface to a value. Using trait objects is a poor substitute for existential types for a few reasons. For one, it has a noticeable performance overhead because it prevents static method resolution and function inlining. For a language that prides itself on providing zero-cost abstractions, requiring programs to use runtime indirection is unacceptable. For another, returning trait objects can't quite express the same guarantees that existential types can.

The next step on the road toward full existential types is allowing them to be used in type aliases, which would make their use more consistent with other types in Rust. That change would allow programmers to write things like this:

type Foo = impl Debug; fn function1() -> Foo { 'a' } fn function2() -> Foo { 'b' }

Critically, these functions are now guaranteed to return values of the same type, which lets programmers express patterns that were not previously possible. This is also the missing piece to allow impl Trait types to be stored in structures. In current Rust, the concrete type underlying an impl Trait type is only inferred when processing a function's arguments or return types — which is sufficient for the existing uses of existential types, but not for full existential types. When support for existential types in Rust is fully complete, the compiler should be able to infer the type of a member of a structure from how it's used. For now, permitting existential types in type aliases as the RFC does provides a workaround:

struct Bar { item: impl Debug, // Error, can't infer underlying type } // Code using the RFC: type Quux = impl Debug; struct Bar { item: Quux, } // Later uses of 'Quux' let the compiler infer a concrete type. fn function3 -> Quux { 42 }

This should cover a number of use cases, because the most common reason to want to store a value of an existential type in a structure is because it is produced by some method, and not otherwise storable except by converting it to a trait object.

This work is the last major step toward existential types that can be used in all the same ways as Rust's existing types. The RFC points out the confusion the current piecemeal solution causes as one reason to want a version of existential types that can be used everywhere: "it is valuable from documentation and explanatory angles to unify the uses of impl Trait so that these types of questions never even arise."

Glen De Cauwsemaecker commented on the work in November 2023, saying that he had tried to use asynchronous functions in some of his networking code, but had run into serious usability problems when combining asynchronous functions with traits. After struggling to express the interface he wanted, he ended up using the experimental feature for existential type aliases:

The feature and RFC tracked in this issue works beautifully. It has none of the ergonomic pitfalls, requires no breaking changes in existing future code, in general plays very nice with Rust and the way it handles async code through futures. It just works.

Despite positive endorsements like that, work on bringing full existential types to Rust has not exactly been smooth. In keeping with the Rust community's approach to building complex features, extensions to impl Trait types have trickled in over time as small chunks of the whole feature. For example, programmers can now write trait methods that return an impl Trait type, which is internally de-sugared to an associated existential type alias — but writing an associated existential type alias by hand is not yet supported. Rust 2024 is also expected to change how impl Trait types capture lifetime information.

This piecemeal approach means that there are still design questions about how existential types should interact in some cases with the rest of Rust's increasingly complicated type system. Another feature currently in development is "associated type defaults", which would permit specifying a default value for a trait's associated type. How this would interact with existential type aliases is still up in the air.

Even though the road to bringing existential types to Rust has been long, it does seem likely that the last remaining design problems will be sorted out in the near future. Existential types would, among their ancillary benefits, make writing asynchronous functions in certain contexts (such as storing their returned impl Future values in a structure, among other uses) a good deal more ergonomic. Polishing Rust's story for asynchronous programming is one of the roadmap goals for Rust 2024, and the focus of substantial effort by Rust's contributors.

---