value-polymorphism

Value Polymorphism in Rust

If you enjoy our work, please consider supporting our research lab!

Polymorphism is one of the most powerful ideas in programming<br>languages. It allows us to write code in an abstract and compositional<br>way. Many modern languages now support polymorphic functions, but very<br>few implement value polymorphism where a piece of data can have<br>a polymorphic type. Chris Done has a good post<br>explaining value polymorphism in Haskell. One example I'm stealing is<br>the def (default) value: def + 1 evaluates to<br>1, while def : "bc" evaluates to<br>"abc" (you can guess what values def takes in<br>each case).

While working on Prela, I was<br>really itching for value polymorphism in Rust, which does not exist, so<br>I had to make my own. For a bit of context, Prela is a column-oriented,<br>embedded query language based on a new foundation of Tarski's Relation<br>Algebra (not Relational Algebra!). To a first<br>approximation, you can pretend it's an ORM that lets you write this kind<br>of queries directly in Rust:

movie.with(info.with(Info::ty.eq("countries")<br>.and(Info::text.is_in(["Germany", "USA"]))))<br>.select(title)

Which will return the titles of American and German movies. Under the<br>hood, each of movie, info,<br>Info::ty, Info::text, and title<br>is a table column, represented with a binary relation mapping each row<br>to the column value. For example, title maps each movie to<br>its title (a string), and Info::ty maps each<br>Info entity/object to its type. We write<br>Info::ty instead of just ty, because other<br>tables also have a ty column, e.g.<br>Company::ty. The same applies to Info::text.<br>However, we shouldn't have to do that, because it should be clear from<br>the context that we are looking at info types and not company types -<br>Info::ty appears inside info.with(). It would<br>be nice if we could just write info.with(ty.eq(...)) and<br>let Rust figure out which ty we mean! But it doesn't work<br>that way, because in Rust, only functions can be polymorphic, not<br>values.

Wait, let's repeat that last sentence: "in Rust, only functions can<br>be polymorphic, not values". Ta da! So we'll just make ty a<br>function! After all, a value is not so different from a constant<br>function returning the value. But there's a problem: can we call methods<br>on functions like f.eq("countries")? No problem. Luckily,<br>functions are first-class values in Rust, and to call a method on a<br>function, we just need to define that method on its type.

To see how this works, let's focus on a very simple example:

info.select(ty)

We first declare a HasTy trait which is implemented by<br>all table types that have a ty column.

pub trait HasTy: Sized + 'static {<br>type V: 'static;<br>fn ty_col() -> &'static RelSelf, Self::V>;<br>impl HasTy for Company { type V = &'static str; fn ty_col() -> ... }<br>impl HasTy for Info { type V = &'static str; fn ty_col() -> ... }

The ty_col() method returns the binary relation<br>representing the ty column. Intuitively,<br>Rel is a column of table T<br>storing values of type T::V. Concretely, a relation is<br>columnar data indexed by table rows:

pub struct RelK: 'static, V: 'static> { /* an array of V, indexed by rows of K */ }

The key type K records which table the column belongs<br>to. In particular, Rel and<br>Rel are different types even<br>though both are just arrays of strings. A column with an unambiguous<br>name is just a function returning the relation, e.g.<br>fn info() -> &'static Rel. For<br>ty, we define a generic function taking a type argument<br>E which should be one of the tables implementing<br>HasTy. It simply retrieves the ty column by<br>calling E::ty_col():

pub fn tyE: HasTy>() -> &'static RelE, E::V> { E::ty_col() }

We also implement an IntoRel trait for<br>relation-returning functions to automatically convert each such function<br>into a relation:

trait IntoRel: Sized {<br>type K;<br>type V;<br>fn into(self) -> &'static RelSelf::K, Self::V>;

implF: FnOnce() -> &'static RelK, V>, K: 'static, V: 'static> IntoRel for F {<br>type K = K;<br>type V = V;<br>fn into(self) -> &'static RelK, V> { self() }

All we had to do is to call self(). Finally, we define<br>each combinator as a method on IntoRel, which calls<br>.into() on its arguments:

fn selectB: IntoRelK = Self::V>>(self, b: B) -> SelectSelf::K, Self::V, B::V> {<br>Select(self.into(), b.into())

The returned Select is a query node in the AST; I<br>describe how they are interpreted in another post.

Let's watch what happens when we call<br>info.select(ty):

info returns<br>&'static Rel, so on the left of<br>.select, Self::V = Info.

The bound on select then requires ty's key<br>type to be Info.

ty is passed unapplied, so its type parameter is an<br>inference variable ?E, and its key type is ?E.<br>The bound forces ?E = Info.

The compiler checks Info: HasTy, and ty is<br>now Info's ty column.

And there you have it! Two critical points of Rust's design made this<br>possible. First, type inference allows propagating typing constraints<br>from the context inwards, which fills in the type parameter of the<br>generic ty() function. Second, we can call methods on...