Default methods and negative diffstats
Last week, I made a change to the Rust compiler that I’ve wanted to make for over a year. I was so happy about finally getting this patch in that I couldn’t resist a “Woohoo!” in the commit message. My excitement is due to default methods finally becoming a stable feature of Rust’s trait system.
If you want a good laugh, listen to this talk I gave a year ago, at the end of my second summer working on Rust, in which I promised that default methods were coming to the language “next week” and would surely be in the then-upcoming release 0.4. I gave that talk on a Thursday afternoon. On the following Monday, I got the first Rust program with a default method to compile, run, and produce the result it should have. It was pretty cool.
Unfortunately, default methods were still basically unusable for real programming for a host of reasons, and certainly not ready for Rust 0.4. It took another year of work by a number of people, particularly Sully, to get them to where they are today. Release 0.5 added default methods as an experimental, off-by-default feature, and various improvements landed over the summer in 0.7. Finally, with 0.8 on the way, default methods seem to be at the point where we can enable them by default.
So, what are default methods, and why am I so excited about them?
Traits, briefly
Since default methods are a part of the trait system, I’ll start by saying a bit about how traits work in Rust as of 0.7, the current release. The Rust 0.7 tutorial section on traits covers some of the same ground.
As a first example, let’s look at the ubiquitous Eq trait, which Rust provides in the standard library as std::cmp::Eq. You can go look at the code for yourself, but as of release 0.7, it looks like this:
// The `Eq` trait from the standard library, as of release 0.7.
pub trait Eq {
fn eq(&self, other: &Self) -> bool;
fn ne(&self, other: &Self) -> bool;
}
Eq contains signatures for methods named eq and ne. An actual implementation of the eq method – which is not provided here – would take two arguments of a given type and return a value of type bool, presumably after comparing its arguments for equality. Meanwhile, an implementation of ne would presumably compare its arguments for inequality – but more on that in a bit.
What good does this Eq trait do us? By itself, not much, so let’s first write an implementation of the Eq trait for a type whose values we would like to compare for equality. To return to an old favorite example1, let’s suppose that we’ve defined a data type called Color with four variants:
enum Color { cyan, magenta, yellow, black }
We can write a function that compares two Colors for equality, giving it a signature that matches the signature for eq given in the Eq trait:
fn eq(&self, other: &Color) -> bool {
match (*self, *other) {
(cyan, cyan) => { true }
(magenta, magenta) => { true }
(yellow, yellow) => { true }
(black, black) => { true }
_ => { false }
}
}
Because eq takes both its arguments by reference2, we dereference them with * before pattern-matching against them, and the rest is pretty straightforward.
By putting this definition of eq inside the appropriate impl declaration, we can make it part of an implementation of Eq for the Color type:
impl Eq for Color {
fn eq(&self, other: &Color) -> bool {
match (*self, *other) {
(cyan, cyan) => { true }
(magenta, magenta) => { true }
(yellow, yellow) => { true }
(black, black) => { true }
_ => { false }
}
}
}
Let’s try writing a complete Rust program using the code we’ve written so far.
enum Color { cyan, magenta, yellow, black }
impl Eq for Color {
fn eq(&self, other: &Color) -> bool {
match (*self, *other) {
(cyan, cyan) => { true }
(magenta, magenta) => { true }
(yellow, yellow) => { true }
(black, black) => { true }
_ => { false }
}
}
}
fn main() {
println(fmt!("%?, %?", cyan == yellow, cyan == cyan));
}
In Rust, the == comparison operator is just syntactic sugar for the eq method on the std::cmp::Eq trait. So, we should now be able to compare Colors for equality using ==. In particular, cyan == yellow ought to evaluate to false, while cyan == cyan should evaluate to true.
Unfortunately, the above program doesn’t quite compile under Rust 0.7:
$ rustc rust-default-methods-ex0.rs
rust-default-methods-ex0.rs:3:5: 3:8 error: missing method `ne`
rust-default-methods-ex0.rs:3 impl Eq for Color {
^~~
error: aborting due to previous error
The compiler’s complaint is that we failed to provide an implementation for ne, the inequality method. Since Eq has both eq and ne method signatures, we’ll need to update the impl we wrote to include ne as well.
Happily, this is easy to do: two Colors are ne exactly when they are not eq, so we can just write a one-liner ne by calling eq and then negating the result.
fn ne(&self, other: &Color) -> bool { !self.eq(other) }
The complete program now looks like this:
enum Color { cyan, magenta, yellow, black }
impl Eq for Color {
fn eq(&self, other: &Color) -> bool {
match (*self, *other) {
(cyan, cyan) => { true }
(magenta, magenta) => { true }
(yellow, yellow) => { true }
(black, black) => { true }
_ => { false }
}
}
// Rust 0.7 needs this.
fn ne(&self, other: &Color) -> bool { !self.eq(other) }
}
fn main() {
println(fmt!("%?, %?", cyan == yellow, cyan == cyan));
}
It compiles successfully, and running it produces the result we’d expect:
$ rustc rust-default-methods-ex1.rs
$ ./rust-default-methods-ex1
false, true
What’s the point?
Let’s look at a situation where having an Eq trait comes in handy. Suppose we wanted to write a generic function member that takes an argument elem of some type T, and a vector vec of elements of type T, and tells us whether elem appears in vec. Here’s a first stab at writing a version of member that is parametric over T:
fn member<T>(elem: T, vec: ~[T]) -> bool {
// 0.8 syntax:
for vec_elem in vec.iter() {
if elem == *vec_elem { return true; }
}
return false;
}
Incidentally, the syntax for vec_elem in vec.iter() works against head-of-tree Rust (and will, I think, be standard in 0.8), but to get this code to compile against Rust 0.7, we have to write for vec.iter().advance |vec_elem| instead:
fn member<T>(elem: T, vec: ~[T]) -> bool {
for vec.iter().advance |vec_elem| {
if elem == *vec_elem { return true; }
}
return false;
}
Syntax infelicities aside, this definition of member looks more or less like what we want. But, it fails compilation:
$ rustc rust-default-methods-ex2.rs
rust-default-methods-ex2.rs:26:11: 26:28 error: binary operation == cannot be applied to type `T`
rust-default-methods-ex2.rs:26 if elem == *vec_elem { return true; }
^~~~~~~~~~~~~~~~~
error: aborting due to previous error
What went wrong here? The problem is that, as it stands, member is polymorphic over any type T. Since we don’t know anything at all about what T is, we can’t very well call == on elements of it, since, after all, we have no idea if it makes sense to compare elements of T using equality. The compiler conservatively assumes that == cannot be applied to elements of T, and raises an error.
In fact, if we wanted to, we could derive a so-called “free” theorem about the type of member, which would say that it is impossible for any function of member’s type to make an equality comparison over elements of T (without breaking type safety).
Well, that’s certainly inconvenient.
Fortunately, the Eq trait can help us here. Instead of parameterizing member over any T, we can limit it to only those types on which we know == can be called – that is, the types for which the Eq trait is implemented. That is, traits give us a way to express bounded quantification in Rust. All we have to do is make a small tweak to the type signature of member:
// `T: Eq` says that `member` is polymorphic over any type `T`, so
// long as there is an implementation of `Eq` for that type.
fn member<T: Eq>(elem: T, vec: ~[T]) -> bool {
for vec.iter().advance |vec_elem| {
if elem == *vec_elem { return true; }
}
return false;
}
The compiler is happy with this updated definition of member. Here’s a complete program that uses it:
enum Color { cyan, magenta, yellow, black }
impl Eq for Color {
fn eq(&self, other: &Color) -> bool {
match (*self, *other) {
(cyan, cyan) => { true }
(magenta, magenta) => { true }
(yellow, yellow) => { true }
(black, black) => { true }
_ => { false }
}
}
// Rust 0.7 needs this.
fn ne(&self, other: &Color) -> bool { !self.eq(other) }
}
// A bounded quantification example -- this is where traits are handy.
fn member<T: Eq>(elem: T, vec: ~[T]) -> bool {
// 0.7 syntax:
for vec.iter().advance |vec_elem| {
// 0.8 syntax:
// for vec_elem in vec.iter() {
if elem == *vec_elem { return true; }
}
return false;
}
fn main() {
println(fmt!("%?", member(magenta, ~[black, yellow, magenta, black])));
}
This version of the code compiles without incident, and since magenta is indeed a member of ~[black, yellow, magenta, black], it runs and prints true, as we’d expect:
$ rustc rust-default-methods-ex2.rs
$ ./rust-default-methods-ex2
true
Default methods
As handy as Eq is, there’s something unsatisfying about what we’ve done so far. Recall that our first attempt at a program that implemented Eq for the Color type failed compilation under Rust 0.7, because we forgot to implement the ne method. To make the compiler happy, we had to add a definition of ne to the implementation of Eq for Color:
fn ne(&self, other: &Color) -> bool { !self.eq(other) }
But this definition of ne looks tantalizingly generic. The body of ne refers only to the already-implemented eq method and its own two arguments. Except for one little occurrence of &Color in the type signature, nothing about ne is specific to the Color type as such.
Wouldn’t it be great if, instead of having to implement a version of ne for Color – as well as another version of ne for every type whose elements we want to be able to compare for equality – we could just write a single, type-generic version of ne and use that everywhere? This is, in fact, what default methods let us do.
Earlier, we saw that in Rust 0.7, the implementation of std::cmp::Eq looked like this:
pub trait Eq {
fn eq(&self, other: &Self) -> bool;
fn ne(&self, other: &Self) -> bool;
}
But let’s see what std::cmp::Eq looks like these days:
pub trait Eq {
fn eq(&self, other: &Self) -> bool;
fn ne(&self, other: &Self) -> bool { !self.eq(other) }
}
What happened with ne? It’s no longer merely a signature; now, there’s some code, right there in the trait itself! Moreover, it looks like exactly what we had to write in our own implementation of ne for Color – except that now, its signature is type-generic. In other words, Eq now provides a default implementation of ne, known as a default method.
Because of this change, our original program, the one without an implementation of ne, will now compile as written! The compiler automatically specializes the default implementation of ne to the Color type, so we no longer have to implement ne ourselves. Furthermore, if we have lots of impls of Eq, we’re spared having to write boilerplate versions of ne in all of them. And if we felt like adding a new signature to the Eq trait, we could just throw in a default method for it, then gradually add specialized versions of the method to individual impls, instead of having to update every impl just to get our code to compile again.
You can try the code out yourself in this Rust playpen, which lets you choose whether you want to compile a program against Rust 0.7 or a snapshot of the master branch – try both and compare the results. You can do the same with our program that uses member – it should compile and run fine under “master” with the ne implementation left out, modulo the for ... in ... syntax change.
A case study for default methods
At the beginning of last summer, the Rust type inference system had been recently overhauled by Niko. It made heavy use of the then-still-rather-new iface and impl language features, which hadn’t existed the summer before that. I spent a lot of time puttering around in the type inference code, which was one of the more well-documented parts of the compiler. After all, who can resist ASCII-art docs?
Anyway, at one point during type inference, the compiler performed “type combining”. Without going into what that means, the implementation defined an iface (short for “interface”, and a precursor to trait) called combine (lower-case was the convention back then), and there were impls of combine for the three “type combiner” data types, called lub, glb, and sub. All three impls were required to implement all of the method signatures in the combine trait, even though some of the implementations were identical in two (or in all three!) of the type combiners. For example, combine included a signature called modes whose implementation was the same in all three of the impls. At the time, the code looked something like this:
iface combine {
// ... more method signatures here ...
fn modes(a: ast::mode, b: ast::mode) -> cres<ast::mode>;
// ... more method signatures here ...
}
impl of combine for lub {
// ... more method implementations here ...
fn modes(a: ast::mode, b: ast::mode) -> cres<ast::mode> {
super_modes(self, a, b)
}
// ... more method implementations here ...
}
impl of combine for glb {
// ... more method implementations here ...
fn modes(a: ast::mode, b: ast::mode) -> cres<ast::mode> {
super_modes(self, a, b)
}
// ... more method implementations here ...
}
impl of combine for sub {
// ... more method implementations here ...
fn modes(a: ast::mode, b: ast::mode) -> cres<ast::mode> {
super_modes(self, a, b)
}
// ... more method implementations here ...
}
// Out-of-line method
fn super_modes<C:combine>(
self: C, a: ast::mode, b: ast::mode)
-> cres<ast::mode> {
let tcx = self.infcx().tcx;
ty::unify_mode(tcx, a, b)
}
This year-old code is not even close to being legal Rust anymore, but hopefully, it conveys something about what was going on. Because it wasn’t possible to write down a default method implementation for modes in the trait itself, the workaround was to define a separate out-of-line method super_modes, and have each impl call super_modes. We had to use the same workaround for lots of other methods in combine, as well.
The code was filled with plaintive comments from Niko about how the implementation could have been so much cleaner if only we had something like default methods. In fact, it was this code that convinced me that default methods weren’t some exotic wishlist feature, but something that Rust really needed, and when I wrote up my proposal for default methods last summer, I used the type-combining code as my motivating example.
Once default methods were working, I was finally able to refactor the type-combining code to use them. That’s the reason it took me over a year to put in that pull request – I had to wait until we had default methods! Once we did, though, it was an easy change; I just removed the super_* methods, replaced them as methods on the (now-capitalized) Combine trait instead, and got rid of all the boilerplate methods in the impls. The best part is that my patch removed 217 lines of code, which I think is a nice demonstration of the power of default methods.
Your turn
From time to time, people ask me how they can start contributing to Rust. The answer depends on the individual, but if your motivations are anything like mine, I think default methods make available a fair amount of low-hanging fruit. For example, it looks like there are unnecessary ne methods in various impls of Eq, just hanging out in the standard library, ripe for the deleting.
Although in some cases it makes sense to explicitly implement another version of a method that has a default implementation – say, for performance reasons – falling back to the default method is perfectly reasonable in other cases. Give it a try and see – negative diffstats may await you!
-
My
Colorexample is adapted from one in the chapter on typeclasses in Real World Haskell, by Bryan O’Sullivan et al. If you’re familiar with typeclasses, you might find that traits look familiar, too, if you squint a bit. ↩ -
Actually, it takes them “by borrowed pointer”, which is a Rust-ism that, to a first approximation, means what “by reference” means in C++, except safer. ↩
Comments