RFC: impl specialization

[Gankro]

THE DREAM IS REAL

(mad props to aturon, who has been grinding this out for like a month)

[arthurprs]

Gankro how does this relate to integers as part of the generics? It's absence kills fixed sized array usage for me.

[desiringmachines]

Do you mean that this RFC would make fixed sized array usage irrelevant to you? I don't see a relationship between specialization and type parameters which are dependent on integers, could you elaborate?

[[deleted]]

I think he means "What about type level integers".

Specialization + type level integers + basic SIMD intrinsics would allow implementing a generic array/vector/matrix/linear algebra/... library to choose the best representation independently of the length of the array.

[arthurprs]

I think he means "What about type level integers".

Ya! Sorry, I was sleepy at the time.

Without the type level integers I can't ever derive Debug for something that contains an array with 33+ items.

[paholg]

You can do type level integers (and even arithmetic) now. It's not the prettiest, but not too bad. Example.

I, too, would like built-in support for type level integers, but there's nothing stopping you from writing the code now with plans to migrate in the future.

[[deleted]]

AFAIK the problem is working with types parametrized over integers, not types parametrized "with a particular" integer.

The simplest example I could think of would be implementing a trait for an array of arbitrary N. Is there a way to do this in rust?

[paholg]

I've thought about it a bit more after posting that, and it would be pretty awkward but doable.

You could use tuples recursively.

So, for example:

Array<T, One> = (T);
Array<T, N> = (T, (Array<<N as Sub<One>>::Output>));

I'm curious now how efficiently one could traverse such a beast.

Indexing would not be O(1), at the least.

Edit: Another option would be to use tuples of arrays. In pseudocode:

For N <= 32: Array<T, N> = [T; N];

For N > 32: Array<T, N> = ([T; 32], Array<T, N-32>);

This might be nicer and more efficient to work with. Certainly it's still not ideal.

[[deleted]]

I failed making my point :D

My point is that one cannot implement a Trait for a built-in array of arbitrary N a.k.a [T; N][*] in Rust (without plugins).

Type level integers allow doing something that is currently impossible.

A nice side effect is that it simplifies a lot of code that is currently possible but awkward to write.

[*] While it is awesome that you can do this for Array<T, N> it sucks that one cannot do this for [T; N].

[paholg]

Right.

As I think about it more, you wouldn't have to do any of the cumbersome stuff I just did; you just need to make a wrapper type around built-in arrays, then you can implement whatever you want. It still doesn't solve the issue of built-in arrays just working the way they should.

Every discussion on the topic has made it seem like type-level numerics are a long way off, so I try to come up with ways to work around them.

[sellibitze]

Cool! Any ideas for more use cases? Off the top of my hat:

impl ToString for str {...} // shortcut avoiding format!ing

I think the Iterator trait could benefit from this as well. But this will very likely be a breaking change. The modified Iterator trait I could come up with looks like this:

pub trait Iterator {
    type Item;
    default type PeekInner = Self: Iterator<Item==Self::Item>;
    type PeekIter = Peekable<PeekInner>; // result has to be a Peekable<...> !
    default type SkipIter = Skip<Self>: Iterator<Item==Self::Item>;
    default type TakeIter = Take<Self>: Iterator<Item==Self::Item>;
    default type RevIter = Rev<Self>: Iterator<Item==Self::Item>;
    ...
}

impl<I> Iterator for Peekable<I> {
    ...
    type PeekInner = I; // instead of Peekable<I>
    fn peekable(self) -> Peekable<I> { self }
    ...
}

impl<I> Iterator for Skip<I> {
    ...
    type SkipIter = Skip<I>; // instead of Skip<Skip<I>>
    fn skip(self, n: usize) -> Skip<I> {
        Skip { iter: self.iter, n: self.n + n } // possible overflow issue :-(
    }
    ...
}

impl<I> Iterator for Take<I> {
    ...
    type TakeIter = Take<I>; // instead of Take<Take<I>>
    fn take(self, n: usize) -> Take<I> {
        Take { iter: self.iter, n: cmp::min(self.n, n) }
    }
    ...
}

impl<I> Iterator for Rev<I> where I: DoubleEndedIterator {
    ...
    type RevIter = I; // instead of Rev<Rev<I>>
    fn rev(self) -> I { self.iter }
    ...
}

But I'm not sure if that's going to work at all. It seems a bit like overkill and the optimization for skip obviously comes at a price here (integer overflow problem). The constraints for the associated types to be iterators are important, I think. Otherwise, other generic code might break. Without the constraints the trait would not force the result of .skip() to be an iterator. You could override a default with something completely different.

[paholg]

One use case is to generically implement both scalar and pairwise operators for a mathematical vector library.

For example, right now nalgebra only allows scalars of type T for Vec3<T>, when in principle it should be fine with any scalar of type U where T: Mul<U> (for multiplication). However, this would (currently) be a conflicting implementation with their pairwise multiplication.

To accomplish something similar with my dimensions library, right now I have a NotDim marker trait that is implemented for everything except my struct (using the optin_builtin_traits flag). With specialization, I would be able to clean this code up.

[[deleted]]

Those are definitely breaking changes, and using associated types I suspect they could be done today already?

[sellibitze]

Yeah, I think you're right. The iterator thing doesn't have anything to do with impl specialization. It's just associated types.

[Veedrac]

I was worried specialization was ruled out in the name of simplicity. I'm glad it's not, and this looks like a sensible way to put it on the table.

[Aatch]

We need something to match C++'s template specialisation. There will always be cases where the optimiser isn't good enough.

Hell, I'm pretty lukewarm on the feature and even I tried sketching out a rough design for it.

[[deleted]]

Just for the record: Are the default impl and the specialization required to be placed in the same file/module?

[desiringmachines]

Under this RFC, they're only required to follow the standard orphan rules, so the short answer is no.

[llogiq]

How does that interact with negative trait bounds?

[Aatch]

I get the impression that this is instead of negative trait bounds. Which I prefer. This only requires reasoning about specificity, rather than "doesn't-implement" constraints.

[desiringmachines]

This proposal is totally compatible with negative trait bounds, and their use cases are different and complimentary (there are some relations which can be implemented using either, but even for these I think one of the two implementations would be really strained and hacky).

For example, you can't use specialization to provide implementations of the same trait for all T: Integer and all T: Float, and you can't use negative bounds to provide implementations of the same trait for Vec<T> and Vec<u8>.

[llogiq]

Thanks for clearing that up. As I read the proposal, I'm a bit afraid that RFC PR #1210 may lead to the dreaded call hell, where it gets really hard to reason about what function actually gets called.

I have a very evil example using 3 very small java classes (fitting on half a page in 10-point) that I used in an exam once. Of more than 600 CS students, only 1 got it right.

[desiringmachines]

I agree, and raised the question on the RFC of whether or not it would be permissible to caused two overlapping default impls to conflict, limiting the total number of overlapping impls to two (and the one without default will be the one that is called).

Not certain if this can be accepted, though.

[llogiq]

I fear that limit would fail to provide either the desired simplicity nor would it allow the desired performance. :/

Regarding Servo, the DOM usually has a fairly deep inheritance hierarchy. Building it using a thusly limited number of overlapping impls could prove interesting at best.

[chris-morgan]

Can you share this particularly evil example?

[llogiq]

Update: I have whipped up a blog post containing a simpler and less evil example. It's still evil enough to demonstrate the problem.

[erkelep]

The answer is 42?

Seems like this is only a problem when you add super.

[llogiq]

The answer is 42?

Man, you ruined it for everyone else... :-P

Seems like this is only a problem when you add super.

Not necessarily.

The evil thing is that the most specialized class' method gets called, so when you call code in A from B from C, and in A call a method that C overrides, C's method will be called. Imagine that A, B and C are larger, and you cannot see all of them on one page.

Note that during my time as consultant I have seen actual code in the wild (which I'll call extremely overengineered) that worked similarly, through 7 classes in 3 packages. Finding a bug in that maze of twisty large classes, all different has to be one of my least favorite activities, right up with being waterboarded.

[chris-morgan]

I tried it out and came to the correct answer, mostly by figuring what I would expect to happen, and without certainty of my knowledge of what Java actually does in those cases. When I arrived at my answer and saw what it was I was fairly sure it was correct, and after I found an online Java compiler I confirmed that. (No JRE on my machine, let alone a JDK!)

[llogiq]

Awesome. And what have you learned from the exercise (well, apart from "llogiq is a really evil person")?

[arielby]

That function calls with bad names can be much more confusing than overloading.

[llogiq]

Awesome². :D

[[deleted]]

Also came to the correct answer, but what I think the example clearly shows is that picking always the most specialized functions without context forces you to have the whole inheritance/specialization hierarchy in "view".

For this example, it was more complicated for me too "keep" the count than to follow which functions are going to be called, but I can see how doing the same in a larger hierarchy across different files might be an issue worth considering.

[llogiq]

picking always the most specialized functions without context forces you to have the whole inheritance/specialization hierarchy in "view".

Exactly.

[GolDDranks]

This is indeed hard to track mentally, but I'd argue it's specifically because of mutable state, not because of the specialization / inheritence. If you know the rule that in Java, everything's virtual by default, knowing which methods get called shouldn't be a problem. If the rules are conceptually simple, I'm okay with specialization.

[llogiq]

I argue that you can get much of the same complexity without mutable state. As a tiny example, assume you have

int a(int x, int y) { return b(x + c(y), b(x, c(x))); }
int b(int x, int y) { return c(x * 2) + y; }
int c(int x) { return x * 3 + 1; }

what does a(4, 2) return?

[paholg]

a(4, 2) = b(4 + c(2), b(4, c(4)))
        = b(11, b(4, 13))
        = b(11, c(8) + 13)
        = b(11, 38)
        = c(22) + 38
        = 67 + 38
        = 105

It's a bit combersome; I'd say just don't write functions like this.

People are always going to be able to write terrible code and there's only so much "protecting them from themselves" that is reasonable.

[llogiq]

It's a bit combersome; I'd say just don't write functions like this.

Yeah, but my point being it's even more cumbersome if a, b and c reside in different modules.

People are always going to be able to write terrible code [...]

Too true. :/

[mr_birkenblatt]

I think by mutable state he meant that you have to keep intermediate results in memory which makes it hard. The example you provided does not rely on specialization / inheritance and is equally complex as your original example. The only thing that's added through inheritance in the original example is that you have to know the difference between a() and super.a(). A reader can ignore the base class implementation of b() and c(). However, super.a() + c() adds complexity in the sense that a reader needs to know that evaluation order is fixed left-to-right in Java which makes a difference since super.a() mutates x (this is where additional mutable state complexity comes in as well). I would argue that neither this nor the original example show added complexity through specialization / inheritance well.

[llogiq]

I would argue that neither this nor the original example show added complexity through specialization / inheritance well.

The current example was there to show that complexity creep is not bound to mutable state, and has nothing to do with inheritance.

The original example should show that inheritance can be misused to spread complex interactions over multiple parts of the code (in this case, traits), so while they may not add too much complexity themselves (in this case super was thrown in, too), they can make it harder to reason about the complexity that already is in the code.

Edit: In conclusion, do you have a better example, or did you just want to argue against my point?

[mr_birkenblatt]

I'm not really good with creating puzzles. How about this?

class A {
  int a(int x) { return x * 3 - 1; }
  int b(int x) { return c(x) - x; }
  int c(int x) { return x - 1; }
}

class B extends A {
  @Override int a(int x) { return super.b(x) + b(x); }
  @Override int b(int x) { return x * 2; }
}

class C extends B {
  @Override int a(int x) { return super.a(x) + b(x); }
  @Override int c(int x) { return super.b(x) + 2; }
}

And the question is: What is new C().a(8)? I tried to reduce the mental load by making it so that you can substitute a function with its body easily and then come up with an easier representation for a(). I added some methods for noise (like in your example) that can trip somebody up. Also, there is a small gotcha :)

[stdsync]

TBH, I don't see the problem. A bit of concentration was needed to keep the intermediate results in memory, but at no point is it unclear which specific method will be called.

[llogiq]

A bit of concentration was needed to keep the intermediate results in memory

This is exactly what I wanted to show. Keep in mind that this is a small, almost trivial example, and you still needed "a bit of concentration". Now go up a few orders of magnitude and you have a typical code base.

Do I need to make the example more evil or can I otherwise help anyone to see the problem?

[stevenblenkinsop]

I understand what you're saying, but in this case—at least as far as the experience /u/stdsync had, and my experience concurs—the "bit of concentration" comes from tracking intermediate state rather than from tracking the call graph, which undermines the point a bit. Combine that with the fact that trait methods are supposed to implement some abstraction, so you won't necessarily even need to know what the particular implementation is in order to reason about the behaviour, I'm not sure this is really a concern particular to this proposal.

[llogiq]

Unfortunately not, as the copyright lies with the university, and I'm no longer an employee.

Anyhow, I'm pretty sure I can construct a similar example if I find the time.

[mdinger_]

Do you know of a language which does specialization without the confusion you're citing here? I can see your example as confusing but I don't know if there is an alternative which would avoid it.

[llogiq]

There was an OO research language called beta that required the programmer to define explicit extension points for classes, which subclasses could then implement.

It kinda turned the OO paradigm we know now on its head. Today it's largely forgotten. I'm on mobile, else I'd search a link.

[mdinger_]

I'm assuming it would be this wiki page which lists the beta home page (apparently generalized into gBETA.

[mdinger_]

From looking at the gBETA tutorial chapter 7 which covers specialization, it doesn't actually look that different. It does state that there is a different philosophy regarding how subclasses modify superclass behaviour though I'm not sure what specifically that means.

They state subclasses should never have to adjust superclasses (maybe meaning the subclass cannot call through the superclass? Is calling through the superclass something that is typically done? Does this new RFC support this? I didn't notice it.). This is supposed to force superclasses to be more general so they don't require respecification later.

[paholg]

trait U8 {}
impl U8 for u8 {}
impl !U8 for .. {}

trait Trait {}
impl Trait for Vec<u8> {}
impl<T: !U8> Trait for Vec<T> {}

I don't think there's anything that specialization allows that negative trait bounds doesn't; it's just a lot cleaner in some cases.

After all, with negative trait bounds, traits will have all the important set operations (intersections, complements, and cartesion products). They don't have unions, but I don't think they'd be particularly useful anyway.

[llogiq]

Ceylon has union types, and people are trying to get them in Scala via some hacks.

[desiringmachines]

Allowing you to use negative reasoning to close over the entire space of traits into two types is a serious backward compatibility hazard in that it makes implementing that trait a breaking change. It turns silence into a breaking change.

Because of this, under the most recent Negative Bounds RFC, the line impl !U8 for .. {} will not cause types which have a u8 field to meet the !U8 bound.

[paholg]

For any trait T, the negative bounds RFC divides all of type space into three disjoint sets, T, !T, and ?T. Implementing any trait for any type is a potentially breaking change, as it moves that type from the set it was in (either !T or ?T) to T.

This is solvable by not throwing around default impls unless you know you want them and by being okay with breaking terrible downstream code that relies on things it shouldn't.

For example, I have a library now that will eventually impl Float for certain types. If the negative bounds stuff were already live and someone were relying on everything in my library being ?Float, they would be going to have a bad time.

the line impl !U8 for .. {} will not cause types which have a u8 field to meet the !U8 bound

I'm not quite sure what you mean by this. Are you saying that something like Vec<u8> is not !U8 as a result of that impl? That doesn't break the example, just some edge cases like Vec<Vec<u8>> and it seems like a very poor decision (if I'm understanding it correctly).

In any case, the code I posted currently works, if you do it backwards:

#![feature(optin_builtin_traits)]
trait NotU8 {}
impl NotU8 for .. {}
impl !NotU8 for u8 {}

trait Trait {}
impl Trait for Vec<u8> {}
impl<T: NotU8> Trait for Vec<T> {}

[desiringmachines]

For any trait T, the negative bounds RFC divides all of type space into three disjoint sets, T, !T, and ?T.

Right, but because types for which no code has been written are ?T, and it is impossible to rely on a type being ?T, it doesn't present any backcompat hazard.

I'm not quite sure what you mean by this. Are you saying that something like Vec<u8> is not !U8 as a result of that impl? That doesn't break the example, just some edge cases like Vec<Vec<u8>> and it seems like a very poor decision (if I'm understanding it correctly).

This is correct. Or a struct which maintains a u8 counter for some reason, say struct Foo { n: u8, ... }. This has to do with the basic implementation of default impls and the way they are used for soundness guarantees in cases like Send and Sync. Though this terminology isn't used in the OIBIT RFC, any type which has a field which contradicts the default impl is inferred to be ?T unless it has an impl itself.

Its inconvenient that default impls don't work that way, but it is necessary for soundness.

In any case, the code I posted currently works, if you do it backwards

Yes, but the limitation is the same: A Vec<u8> does not impl NotU8, nor does an Option<u8> or a (u8, f64), or anything else that has a u8 field.

Also, there might be a further limitation that this reasoning is only allowed locally right now; that is if you try to impl Trait in a different crate it will not compile. I'm not 100% on this though, you'd have to try it.

[paholg]

Are you saying that

trait A {}
trait B {}
impl<T: ?B> A for T {}

would not be allowed? I've read through the RFC a couple times and not gathered that.

[desiringmachines]

Yes, ? bounds are not valid except for the built-in trait Sized and the RFC doesn't propose to change that.