TMI: Fun with polymorphism

[tim]

I didn't get to writing a blog post on Friday, since I had a couple of interruptions and didn't get that much code written anyway. The main news from Friday is that classes can now implement parameterized interfaces! This was a pretty minor fix. That is to say, I can write:

class cat implements map<int, str> {
... }

which says that the type cat supports table- or map-like operations mapping integer keys onto string variables. Why a cat would support that, I don't know, but it's just an example. I went on to write a test like this:

class cat<T: copy> implements map<int, T> {
... }

in which a class implements a parameterized interface (in this case, map -- the interface describing types that support map- or table-like operations) and the class is itself parameterized, with class type parameters ("ty params" from here on, since that's less typing) that appear as type arguments to the interface type. (The syntax T: copy means that this class is parametric, or boundedly polymorphic, over all types that can be copied, rather than all types.) This was not so easy.

The snag had to do with an old bug, or perhaps infelicity, in how the Rust compiler handles parameterized classes that contain parameterized methods. Suppose the same class contains a method that's also parameterized over a completely distinct type:

class cat<T: copy> implements map<int, T> {
      fn meow<U>() {
         ...
      }
}

I'm not sure why meowing would be parametric either, but it's just an example. Now suppose we use cat in the following way:

 let kitty = cat(...); /* constructor arguments */
kitty.meow();

We haven't supplied either the type argument for the class cat, or the type argument for the method meow; these types are optional in Rust, so in this case, the compiler infers them. In contrast, we could have written them explicitly:

 let kitty = cat<int>(...); /* constructor arguments */
 kitty.meow<str>();

In the type-free example, the compiler first instantiates the missing types to fresh type variables; though it doesn't actually do this by rewriting the AST, you can think of it as rewriting the program like:

 let kitty = cat<V>(...); /* constructor arguments */
 kitty.meow<W>();

where V and W are fresh type variables.

The confusing bit of code comes in like this: does meow have one ty param, or two? Well, since the type parameter for kitty should be known when typechecking kitty.meow(), arguably it has one; on the other hand, in the compiler back-end it's easier to think of it has having two (since a monomorphized copy of meow gets made for every pair of types it's instantiated at). It's not too important which answer the compiler chooses so long as it handles the types consistently. But the typechecker (and other) code currently concatenates the class ty params for a given method with the method's own type params, which is confusing and error-prone.

Some of the confusion arises from the Rust compiler's handling of ty params in a positional, rather than nominal way: that is, inside the compiler, classes, methods, and other items refer to (effectively) "my second type parameter" rather than "the type parameter in scope whose name is T". That is pretty clearly not quite the right thing, so rewriting that part of the compiler so that ty params (like most other things in the AST) have identifiers corresponding to their definitions and uses -- rather than just indexing into a list of params -- is the right answer. Once that happens (which Niko volunteered to do), a fix for this bug will just fall out.

It was still tempting to fix the old crufty code so that this test case will work, even knowing that all the same code is about to be rewritten... I want the thrill of committing another working test case! But I decided that would just be wasted effort, so I annotated issue 2288 explaining which test case was working, and which wasn't yet, as well as that making ty params non-positional is a blocker for #2288.

While I was waiting for test cases to run, I filed #2366, which may be asking for the impossible, but is something that's been annoying me for a while.

Then I started working on allocating classes in the heap (currently they're always stack-allocated), which is much deeper than the other bugs and gets its tentacles into the back-end more. I'm having to think harder, since type systems are my breakfast cereal and codegen is so not. But, I'm leaving compile errors unfixed for now as I have to bike to Redwood City. Continued tomorrow...