On types and type schemes

After my recent dalliance in Matters of a Truly Trivial Nature, I’d like to return to Matters Most Deep and Profound. I’m running up against an interesting question with regions that has to do with the nature of function types like fn(&int): up until now, I’ve assumed that this refers to a function that takes an integer pointer in some region that is specified by the caller. That is, it is a kind of shorthand for a type that might be written like fn<r>(&r.int), where the <r> indicates that the function type is parameterized by the region r.

But first, a digression on types and type schemes…

This notation is analogous to a generic function, like:

fn identity<T>(t: T) -> T { ret t; }

However, there is an important distinction. In Rust, as in ML, parameterization only occurs on named items. So, you can have a named function identity defined generically, but you cannot have a type fn<T>(T) -> T.

This is an interesting and subtle point. In fact, all Rust types are monotypes, meaning types that refer to exactly one thing. Now, it may not be known precisely what that thing is, but there must be a name for it. So, the type of the t parameter is T, which is a type variable. This is a monotype, it can only refer to one thing: the type T. It just so happens, however, that we do not know when typechecking identity what that type T is.

The type of the identity function itself, however, cannot be represented as a monotype. We cannot name a specific type for its parameter and return value, it could safely be used with any type. To accommodate this concept, ML introduced the idea of a type scheme, also called a polytype. (at least by Wikipedia, I’ve never heard the term before. but it seems logical.)

A type scheme is basically a type along with a set of bound type variables. A bound type variable is one that is defined within the scheme itself. So, if you have the type scheme fn<T>(T) -> T, then the variable T is said to be bound in this scheme. In a scheme like fn<T>(T, U) -> T, the variable T is bound, but the variable U is called free, as it is not defined in the scheme. Note that in a monotype all variables are free, as monotypes do not define any type variables.

So, in a way, a like fn<r>(&r.T) is really a monotype, although it does not bind type variables. But it can still refer to many concrete types. This entails complexity.

…and now back to regions.

So, the question is, should region variables be bound or free within a function type? It certainly makes life simpler if they are always free, and it still results in a fairly expressive system.

But first let’s examine why bound regions make life complex. To help keep things clear, I will use the explicit “bound region” notation I introduced earlier, even though it’s not an actual Rust type, and I will eschew anonymous regions. This means that the notation for writing function types and so forth will be a bit heavier than it would be in “real life”.

I will use a few conventions: lowercase letters early in the alphabet like a, b, and c refer to bound regions. Lowercase letters late in the alphabet (r, s) refer to free regions. Plus, I generally drop the types of a region pointer if they are not important, so let &r be shorthand for something like &r.int.

Subtyping of bound regions

Renaming of bound regions. Imagine a type A=fn<a>(&a) and a type B=fn<b>(&b). Is A a subtype of B? Clearly, the answer should be yes: they are basically the same type, as you could rename the bound variable a in A to b, and they would be precisely the same. So here we find that we have to consider possible renamings of bound regions when considering subtyping.

Instantiating bound regions. OK, well, now imagine the type C=fn(&r). Here, the region variable r is not bound but rather free. So in this case, is A a subtype of C? I would argue that the answer should be yes: after all, if you instantiate A with the value a for r, you get fn(&r.T), the same as C. So we ought to consider possible instantiations of bound variables as well.

Coallescing bound regions. Finally, one more example:

fn<a,b>(&a, &b)     <:    fn<c>(&c, &c)

Here the subtype is more flexible than the supertype. The subtype accepts two region pointers in any two regions, but the supertype requires that they be in the same region.

…with type variables, too

Now, just to make things more fun, imagine we throw in a type variable X into the mix. Here we play the role of the inference engine, which is trying to find a value for X. So the question becomes, is there any type that I can assign to X which would make the subtype relation true?

Referring to free regions. Let’s start with a simple example. Consider:

fn(&r)    <:    fn(X)

In this case, r is free, so we can assign X the value of &r and everything should be fine.

Bound regions. Ok, what if the subtype refers to a bound region?

fn<a>(&a)    <:    fn(X)

We can still handle this case, but it requires a region variable as well. In other words, if we create a region variable R, then we can substitute that region variable for a and obtain:

fn(&R) <: fn(X)

Now we can assign X to &R and then assume that the inference engine will find a suitable region for R. This will be based on constraints from the rest of the program.

Multiple parameters. Of course, if there are multiple parameters, there may be interactions between them:

fn<a>(&a, &a)    <:    fn(X, &r)

In this case, because r appears free in the supertype, X can be assigned &r. That would mean that a can be instantiated with r and the subtyping relation holds.

Bound regions within the supertype. What if the region in the supertype is bound, not free?

fn<a>(&a, &a)    <:    fn<c>(X, &r)

In this case, there is no value of X which is suitable. This is perhaps not obvious: you might think that &c would be a fine value for X. But that means that the value of X would refer to the region c, which is bound within the type. It’s a scoping violation. The name c has no meaning outside of the supertype, whereas the type X (which appears free) does have meaning. So X cannot refer to regions bound within the supertype.

Woah.

Yeah, it’s complex. I haven’t come up with an elegant implementation for the inference engine that accommodates all of these scenarios. One option is to not handle all of these cases. I also ought to read up in The Literature as well as the implementations of other languages (e.g., Haskell, Scala) to see what they do in similar scenarios. Still, I dislike the idea of having things in our type system that require citations to explain.

So, can we just drop bound type variables in function types?

Actually, I think we definitely could (not yet sure if we should). Most things I’ve thought of will “just work”, and when they won’t, there is workaround via interfaces (more on that later).

First, an example of something that works:

fn iter(v: [T], f: fn(&T)) { 
    uint::range(0, v.len()) { |i|
        f(&v[i]);
    }
}

This function iterates over each item in the slice v and invokes the function f (I am assuming Graydon’s work on slices and vectors is complete). If we fully expand this type to see all the regions involved, you end up with:

fn iter(v: [T]/&a, f: fn/&a(&a.T)) { ... }

This signature is probably a bit confusing. As usual, I find the best way to think about regions is as lifetimes (in fact, I am considering changing my terminology over to use the word lifetime exclusively). So what this notation means is that there is some span of time a in which the vector data and the function closure is valid. The function itself expects a pointer which is also valid for this same span of time (in this case, that pointer will be a pointer into the vector contents, so its lifetime comes from there). This span of time a will generally be the call to iter() itself.

What doesn’t work?

Basically, what doesn’t work is when you want to have a function whose arguments can have lifetimes whose lifetime is not yet known. This most commonly occurs when functions are stored into records. One example that comes to mind is the hash and eq functions that we use to implement hashtables right now.

Currently, our hashtables are defined with a structure something like:

type hash<K,V> = {
    hashfn: fn(&K) -> uint,
    eqfn: fn(&K, &K) -> bool,
    ...
};

Here you see that the hashfn takes a pointer to the key K and returns the hash (a uint). The eqfn takes two keys and returns a boolean if they are equal.

The key point here is that the lifetimes for the key arguments are not known and cannot be known in advance. The data for the hashtable is stored in a structure on the heap and so its lifetime is not stack-based and hence has no region; for any given hashtable operation, the current array will be borrowed and thus tied to the stack of that particular operation, but these future operations cannot be given a name.

Did you say something about a workaround?

Yes, we can use ifaces to work around this problem. Imagine an iface:

iface hash_key_ops<K> {
    fn hash(k: &K) -> uint;
    fn eq(k1: &K, k2: &K) -> bool;
}

I am mildly abusing ifaces here because the “self” would not be a particular key but rather some singleton object representing the hash function itself. For example, I might define:

enum murmur_hash { murmur_hash };
impl of hash_key_ops<str> for murmur_hash {
    fn hash(k: &str) -> uint { ... }
    fn eq(k1: &str, k2: &str) -> bool { k1 == k2 }
}

Now we could define the hashtable like:

type hash<K,V> = {
    ops: hash_key_ops/@<K>,
    ...
};

fn new_hash<K,V>(ops: hash_key_ops/@<K>) { ... }

Now whenever we want to hash a key we can invoke tbl.ops.hash(key). The key point is that the named functions in an iface, just like function items, can have polytypes even though normal function types are monotypes. Then each time we invoke hash() we would instantiate the bound regions with fresh region variables.

Of course, if we were going to use ifaces with hashtables, we might rather define the iface over the key type itself. That raises some interesting issues about instance coherence which I plan to discuss in a blog post Real Soon Now, but if you’re curious about that you may also want to read my mailing list post on the topic as it is still my preferred solution.