Polymorphic associated type


#1
trait Foo {
    type Item;
    fn get(&self) -> Self::Item;
}
struct Bar<T>(T);
impl<T> Bar<T> {
    fn new(t: T) -> Self {
        Bar(t)
    }
}
impl<T> Foo for Bar<T> {
    type Item = T;
    fn get(&self) -> Self::Item {
        self.0
    }
}

fn main() {
    let v: Vec<Box<Foo<Item=?>>> = vec![Box::new(Bar::new(1)), Box::new(Bar::new("1"))];
}

Is this kind of polymorphism possible? Is generic associated types going to address this issue?


#2

Sample code for generic associated types.

#![feature(generic_associated_types)]
#![feature(associated_type_defaults)]

trait Foo {
    type Item<T> = T;
    fn get(&self) -> Self::Item;
}
struct Bar<T>(T);
impl<T> Bar<T> {
    fn new(t: T) -> Self {
        Bar(t)
    }
}
impl<T> Foo for Bar<T> {
    type Item = T;
    fn get(&self) -> Self::Item {
        self.0
    }
}

fn main() {
    let v: Vec<Box<Foo<Item=_>>> = vec![Box::new(Bar::new(1)), Box::new(Bar::new("1"))];
}

https://play.rust-lang.org/?gist=4f549ede4bb35d396eb8118455345ffb&version=nightly


#3

I don’t think GAT is going to address this. You need to erase the associated type, so something like Item = Box<Any> or instead of Any, some other trait that unifies the associated types.


#4

I can’t seem to get it to work. Am I on the right track?

https://play.rust-lang.org/?gist=d4e8e112d9181665269740a0840ba6f2&version=nightly


#5

https://play.rust-lang.org/?gist=648acebe4de824044cd900ee08e5e391&version=stable

I had to adjust the trait method signature to return a reference to Self::Item so that it doesn’t try to move out of self.


#6

Thanks a lot. Sorry to bother you but what about this case when cast isn’t directly accessible? Mind you, this is an analog from my actual code.

https://play.rust-lang.org/?gist=7e347a45e9a930020e1db4417f9bd0ad&version=stable


#7

Hmm, that’s a good one. I’m not sure it’ll be possible in this particular case but I’ll try to mull it over.

There’s going to be a second issue, which is:

   type Item = Box<Option<R>>;
    fn get(&self) -> &Self::Item {
        &Box::new(self.2)
    }

is incorrect and won’t compile. This is probably why you were looking into generic associated types.

Taking a step back, perhaps there’s a different/better way to achieve what you’re after? What’s the context to your actual code?


#8

The repo is here:

Basically all I’m trying to do is figuring out a way to hide the associated type in order to make it a trait object to store it so making observe a generic function doesn’t work.


#9

So you don’t need to use the associated type in any way via the trait objects? In other words, using your Foo trait example in this thread, you want to call get(&self) but ignore the return value? Or something else?

EDIT: so assuming the above is correct, here’s an approach: Playground

The gist is you create a wrapper struct (Eraser in the playground) that wraps any other T: Foo generically. It, in turn, implements Foo but “forgets” the associated type - I used type Item = () in the example. Then you box these erasers, and end up with Box<Foo<Item=()>>. The implementation of get(&self) calls into the inner/wrapped type.

Note, as mentioned before, I had to stub out the get() impl for Bar because it cannot return a ref to a temp Box; this is a separate issue though, and we can discuss that separately if you’d like.

If the above is not what you need, let’s refine the requirements and iterate on this.


#10

Actually I do need the return value(allowing Clone for now). I just finished a version that uses type-aware keys to partially circumvent the type erasure issue.

Basically, the architecture is like this:

  1. Kind<Item=?> trait objects with type erased as Box<Any> stored in a Node struct.
  2. During creation, also return type-aware keys that can be used to query the graph which downcasts Node.kind from Box<Any>(by supplying the type information)
  3. Restore the previously erased return value.

Concretely, the associated type in Node trait is erased down to Any and the type is stored in type-aware keys trait Incr that are used to downcast Any (extract). However, since the graph struct itself does not store any type information, there is simply no way to recompute without taking a vector of Box<Incr<Item=??>>(there’s no way to pass the trait objects because the types are, then again, erased). What I want to do is not possible with the Rust type system.

Ideally, there should be a way to unsafely downcast Box<Any> to Box<Trait>.

I’d really appreciate it if you could take a look at the code and get it to compile(I doubt it’s possible): https://github.com/rickyhan/spandex-rs/blob/master/src/lib.rs


#11

So looking at your repo I suspect you’re not going about this the best way. Even if you manage to get it to compile, the amount of boxing and indirection is going to kill performance.

I’d need to think some about the right design here but it shouldn’t look like what you’re attempting. It should be more similar to how you build up Iterator or Future state machines, where the transforms/combinators are all strongly typed with just an occasional sprinkling of erasure. Easier said than done, I know - hence don’t have an immediate suggestion yet.

@frankmcsherry might have some wisdom though given he’s built dataflow graphs.


#12

You are correct. I did some research tonight and discovered that the issue is technically not generic associated type(although it is a form of higher kinded type) but GADT which Rust does not currently support because it doesn’t have higher kinded types unlike most other functional languages. In this case, I need a type parameter that’s parametrized by another type parameter to support higher kinded polymorphism.


#13

For more information please see this SO post: https://stackoverflow.com/questions/41508680/generic-struct-over-a-generic-type-without-type-parameter

That said, if anyone has a better solution please don’t hesitate to comment below.


#14

I’m not entirely sure what your project goals are, but there are other projects doing incremental computation and perhaps you could take a peek at them to see if they abstract their representations differently or more effectively.

Adapton is a memoization-based approach that builds and maintains dependency graphs, which looks perhaps a bit like what you are doing.

Differential dataflow is a change-propagation approach that works with more coarsely grained dataflow graphs, but “scalably” in the big data sense.

Each of these probably finesse the problem you are having somehow, so perhaps it is possible to move towards your goal without solving the specific problem you’ve laid out here?


#15

It’s not immediately clear to me how GADTs would solve your problem.