value-polymorphism

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

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

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

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

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

info.select(ty)

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

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

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

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

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

pub fn ty<E: HasTy>() -> &'static Rel<E, E::V> { E::ty_col() }

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

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

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

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

fn select<B: IntoRel<K = Self::V>>(self, b: B) -> Select<Self::K, Self::V, B::V> {
    Select(self.into(), b.into())
}

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

And there you have it! Two critical points of Rust's design made this possible. First, type inference allows propagating typing constraints from the context inwards, which fills in the type parameter of the generic ty() function. Second, we can call methods on and implement traits for functions, which allowed us to define the into_rel method on the relation-returning functions.

We haven't yet merged this into mainline Prela, however, because this still feels a little too magical. Maybe that's inevitable, as we are trying to get a feature explicitly not supported by Rust, namely value polymorphism. In any case, I would love to know if there are less magical ways to do all of this.

Value Polymorphism in Rust