On the rust-dev mailing list, someone pointed out another
“BitC retrospective” post by Jonathon Shapiro concerning typeclasses.
The Rust object system provides interesting solutions to some of the
problems he raises. We also manage to combine traditional
class-oriented OOP with Haskell’s type classes in a way that feels
seamless to me. I thought I would describe the object system as I see
it in a post. However, it turns out that this will take me far too
long to fit into a single blog post, so I’m going to do a series.
This first one just describes the basics.
One caveat: I think that these techniques are novel, at least in
some parts. However, I am not well-versed in the Haskell literature
and it’s possible that the techniques we aim to implement have been
explored already. If so, I’d appreciate it if someone would point me
in the right direction! There are some links in his post that I
haven’t read, for example, but I will definitely put them on my
reading list.
EDIT: It’s a bit unclear what I precisely think is novel. In
fact, when I wrote the previous paragraph, I was referring to our
proposed technique for enforcing instance coherence. However, I
didn’t even describe this problem in this post, because I realized
there was a lot of background to cover. So, to be clear, I don’t
think that the basics in this post are terribly novel—with the
exception of our use of the same interfaces to unify Haskell-style
type-classes (or C++ concepts, if you prefer) with OOP-style
existential (sub)typing. That particular part works out quite well, I
think.
The building block: ifaces
The fundamental building block of Rust’s OOP system is the iface
(interface). As in Java and other languages, an iface is just a set
of methods without implementations. Let’s use the example of a
hashable value, which might be suitable for use as the key in a
hashtable:
iface hashable {
fn hash() -> uint;
fn eq(t: self) -> bool;
}
This interface provides two methods. The first, hash(), computes a
hash of the value and the second compares for equality. You see that
an iface can use the special type self. The type self means “the
same type as the receiver”. A later post will demonstrate that this
type—while extremely useful!—introduces some complications.
Classes
Classes are like a pared down version of the classes you will find in
other languages. As in C++, they have fields, methods, constructors
and an optional destructor. However, they do not inherit from one
another (we will see how to do polymorphism in a bit). You can define
a class like so:
class a_class {
let x: int, y: uint;
new(x: int, y: uint) {
self.x = x;
self.y = y;
}
fn get_x() -> int { self.x }
}
The precise syntax will probably change (I am not fond of the
definition of constructors, in particular), but the basic idea will
remain the same: a class combines a set of fields with various
methods. Members can be defined as private or public with the usual,
C++- or Java-like definition. Fields can be immutable (the default)
or mutable (let mut x: int).
Polymorphism using classes and ifaces
There is no subtyping between classes. However, sometimes you would
like to have a routine that operates on multiple types. The canonical
example is to have an interface for “drawable” things like:
iface draw {
fn draw(gfx: graphics_context);
}
Along with various drawable shapes like:
class square { fn draw(gfx: graphics_context) { ... } }
class circle { fn draw(gfx: graphics_context) { ... } }
...
Rust then offers you two ways to work with these drawable things. The
first, interface types, is more like C++ or Java. The second, bounded
type parameters, is more like Haskell’s type classes. As we will see,
each technique is useful for different scenarios.
Interface types
As in Java, an interface like draw also has a corresponding type
(simply written as draw). In fact, it has a family of types
(draw@, draw~, draw&, and draw) just as with function
pointers, but for now there is no need to get into the full details.
The type draw will suffice.
The type draw means “some value which implements the drawable
interface”. We can use the draw type to write a function which
takes a vector of drawable things and draws them all:
fn draw_all(gfx: graphics_context, drawables: [draw]) {
for drawables.each {|drawable|
drawable.draw(gfx)
}
}
This looks pretty close to Java or C++. However, what happens at
runtime is somewhat different in some pretty important ways. For one
thing, the draw type in Rust is represented as the pair of a pointer
to the instance data along with a vtable. Invoking the draw
method, therefore, is simply a matter of extracting the function
pointer from the vtable and invoking it with the instance data as the
(implicit) first argument.
This representation is somewhat different from Java or C++, both of
which would have a single pointer to the object and would embed the
vtable in the object itself. There are a variety of reasons that we
take a different approach which I will cover later.
The reason I am talking about how draw instances are represented at
runtime is that it is not the same as the way that a @circle
instance (for example) is represented. The type @circle is just a
pointer to the a block of memory containing the fields for the class
circle. There is only a single pointer and there is no vtable. So we
cannot simply interpret the type @circle as a draw instance
without doing some conversion.
In Rust, this conversion is accomplished by casting the @circle
instance to the draw type. So, an example of using the draw_all
method might look like:
fn draw_a_square_and_a_circle(gfx: graphics_context) {
let s = @square(...);
let c = @circle(...);
let objs = [s as draw, c as draw];
draw_all(gfx, objs);
}
Here you can see that to construct the vector of drawables, we first
casted s and c to the type draw. This cast constructs the pair
of the s and c pointers along with the appropriate vtable (in the
first case, one for square, in the second case, one for circle).
Why is it designed this way?
There are a variety of reasons that we took a different approach from
that used in Java or C++. First, we wished to preserve the nice
quality of C++ that all virtual calls are implemented using simple
vtables: this is an efficient technique with reliable performance. In
Java, in contrast, the precise implementation of interface calls can
vary. Of course the JIT is able to generally produce efficient code
(typically using PICs or similar things) but we want to be able
to statically compile Rust without the need for just-in-time
techniques.
However, we also did not want to require that classes be pre-declared
as “implementing” a particular interface (or, in the case of C++,
extending the given abstract class). In C++, the subtyping
relationship is used to guide the construction and layout of the
vtables (and, in some cases, multiple such vtables may be needed,
meaning that there is no unique pointer to the object data itself).
Without having that pre-declared relationship, we cannot pre-compute
the vtable(s) for an object in advance.
Therefore, we instead wait and lazilly construct the vtable at the
point of the cast (actually, there will be one vtable for each
class-iface pair that appears within a crate). By representing the
draw instance as the pair of the instance data with the vtable, we
can easily have one class instances associated with any number of
vtables.
Type classes
There are two fundamental approaches to writing polymorphic functions
(in general, not just for interface types). The Java and C++
technique, which we illustrated in the previous section, is to use
subtyping. Another approach, pioneered in functional languages
(though it is also available in OOP languages) is to use parametric
(or “generic”) functions. For example, we could write a function
draw_many like so:
fn draw_many<D:draw>(gfx: graphics_context, drawables: [D]) {
for drawables.each {|drawable|
drawable.draw(gfx)
}
}
draw_many() looks very similar to draw_all. It declares a type
parameters D and says that the type D must implement the draw
iface. This draw interface is called the bound of the type
parameter D, because it bounds (or “puts a limit”) on what types can
be used for D: they must be types for which the interface draw is
available. It then takes a vector of D instances and iterates over
its contents, invoking the draw() method on each value.
There is in fact a subtle different between draw_all() and
draw_many(). draw_all() took a vector of type [draw]: this
means that each entry in the vector may in fact correspond to a
distinct kind of drawable thing. For example, the vector might have a
square and a circle, as we saw. draw_many(), in contast, takes a
vector of type [D]. This means that the type D could be a square
(which is drawable) or it could be a circle (which is also drawable),
but you cannot have a vector containing both a square and a circle.
To see more closely why this is, consider that at runtime we implement
generic functions like draw_many() by following the C++ approach:
that is, we duplicate the function for each type that it is used with.
Therefore, we can easily create a version of draw_many() for
squares by substituting square for each use of the type D:
fn draw_many<square>(gfx: graphics_context, drawables: [square]) {
for drawables.each {|drawable|
drawable.draw(gfx)
}
}
We can also create a similar one for circles, but there is no type
(other than draw) that we could use to create a version that accepts
a vector containing both circles and squares. In fact, there can be
no such vector: all vectors must contain instances of a single type.
Using the type-class style of implementation is generally more
efficient than the traditional OOP-style, because it produces no
vtables at all (but it does produce more code, which has its own
inefficiencies). This efficiency comes at the price of less
flexibility, because the style cannot deal with heterogeneous
collections.
Actually, this is not strictly true: it is (usually) allowed to
instantiate the type D with an iface type, so we could still invoke
draw_many() with a vector of draw instances, just as we did with
draw_all(). This would be equally (in)efficient as the OOP version,
because all method calls would still go through a vtable.
Code reuse via traits
Inheritance is often used as a means of achieving code reuse in OOP
languages. While it can be convenient, this is generally regarded as
unfortunate, because it ties together the subtyping relationship
with details about code reuse. A more modern approach is to make use
of traits. Rust offers traits but I won’t go into detail here. In
effect, traits allow you to factor out common method implementations
in a much more flexible way than inheritance, without introducing the
complications of traditional multiple inheritance.
Impls
So far, the only way to define a value with a method is to define a
class and include the method in the class definition. This is too
limiting, however, in two ways. First, sometimes we want to define
methods outside the class body—for example, to extend a class
defined in one crate or module from somewhere else. Second, not all
types in Rust are classes (for example, ints and vectors) and we don’t
want them to be, for efficiency reasons and C compatibility.
To address these two needs we allow you to define methods for a given
type using the keyword impl. For example, suppose we want to add a
method bounds() that computes a bounding rectangle for a shape. You
might do something like this:
impl bounds for square {
fn bounds() -> rect;
}
Here the syntax impl N for T defines a suite of methods named N
for the type T. You can also associate an impl with an iface
like so:
iface bounds {
fn bounds() -> rect;
}
impl of bounds for square {
fn bounds() -> rect;
}
In this case, the name of the method suite is (by default) the name of
the iface. The full syntax is impl N of I for T.
Using an impl, we can generalize interfaces to apply to arbitrary
types. For example, we could implement the draw interface for a
uint (whatever that means):
impl of draw for uint {
fn draw(gfx: graphics_context) { ... }
}
Then a [uint] could be passed to draw_many(). Similarly, we could
cast a uint to draw.
Scoping of impls
In order to make use of the methods in an impl, you must bring the
impl into scope using an import statement. This is where the impl
name comes into play. So, to use the bounds method from another
module, I must include something like:
import B::bounds;
where B is the module containing the impl declarations. The same
visibility rules apply when trying to cast a type to an iface or use
the type as the value for a bounded generic type parameter.
Mismatches
To some extent, the class and impl system were independently designed,
and there are a few mismatches (mostly in code that has not been fully
implemented). The main one is that interfaces are duck-typed (not
declared) and impls declared when they implement an iface. We will
align these to be the same (for the moment, probably initially by
adding the ability to declare an interface when you declare a class).
