Idea: dyn modifier over type parameters to allow type erasure for parameterizd types/values

Currently, we can use universal quantifier for lifetime, for example:

struct Foobar {
  val: i32
}

fn foobar<'a>(get_val: &for<'b> fn(&'b Foobar) -> &'b i32, x: &'a Foobar) -> &'a i32 {
  get_val(x)
}

And it's impossible for now if we want to write this code, because here it need universal quantifier for types in a dyn context.

fn foobar<'a, T>(id: &for<'b, U> fn(&'b U) -> &'b U, x: &'a T) -> &'a T {
  id(x)
}

Currently we can only use universal quantifier in compile time scope.

#![feature(non_lifetime_binders)]

trait HKT {
    type Item<T>;

    fn get<T>(self) -> Self::Item<T>;
}

fn foobar<H, T>(x: H, vec: &Vec<T>) -> usize
    where 
        H: HKT,
        for<A> <H as HKT>::Item<A>: Fn(&Vec<A>) -> usize
{
    let f = x.get::<T>();
    f(vec)
}

In other language which supports universal quantifier for types, they perform type erasure, so values can still be parameterized because there will only be one implementation of the callee interface, no need to generate different codes for different types.

We can add a dyn modifier over type parameters to tell compiler that, this parameter doesn't decide how the type/function should be compiled.

For example we can create a container for different types, but the runtime implementation stays the same for all types.

#[repr(C)]
struct Box<dyn T> {
  val: *mut (),
  layout: std::mem::Layout
}

its memory representation should all be [usize, Layout]. We don't need additional PhantomMarker for such type constructor.

If we write a function to compute length for different Vec<Box>

fn len<dyn T>(vec: &Vec<Box<T>>) -> usize {
  vec.len()
}

then we only need a single compiled function for every different type

fn len(vec: &Vec<struct{*mut (), std::mem::Layout}>) -> usize {
  vec.len()
}

so it will enables us to write such code

fn foobar<'a, dyn T>(f: &for<'s, dyn U> dyn fn(&'s Vec<Box<U>>) -> usize, vec: &'a Vec<Box<T>>) -> usize {
  f(vec)
}

as the f should only have a single runtime interface:

fn (vec: *const Vec<Box>) -> usize

I think it will be useful if someone really need parametric polymorphism.

And of course, to make it more useful we might need bounded qualification. It's not a easy problem to solve.

It really feels odd how switching from static dispatch to dynamic dispatch in C++ is just changing a keyword (virtual) but in Rust requires a whole program refactoring (remove type parameters in multiple places and turn things into trait objects)

I think this makes trait objects underused in practice. People start with static dispatch by default and don't bother with refactoring if they can avoid it. So it would be awesome if we could do dynamic dispatch by just adding a dyn into a type parameter.

So this

fn f<dyn T: Trait>() -> Box<T> { ... }

Is the same as this

fn f() -> Box<dyn Trait> { .. }

Just like

fn f<T: Trait>() -> Box<T> { ... }

is the same as

fn f() -> Box<impl Trait> { ... }

So the current trait object syntax (dyn Trait in types) would be like impl Trait, but for dyn generics


But I think this new syntax would also open up another thing: being able to statically assert that two trait objects actually refer to the same runtime type. So this

fn f() -> Box<(dyn Trait, dyn Trait)> { .. }

Would be written like this

fn f<dyn T: Trait, dyn U: Trait>() -> Box<(T, U)> { ... }

But if we had a single T, the compiler would force the two values to have the same vtable or if that's not possible, fail compilation

fn f<dyn T: Trait> -> Box<(T, T)> { ... } // not possible to express in current Rust
1 Like

The code is not fully the same I think

fn f<dyn T: Trait>() -> Box<T> { ... }

and

fn f() -> Box<dyn Trait> { .. }

The later one is the version after type erasure.

We have a chance to get the original type back in some cases.

fn foo<T: Trait>(vec: &mut Vec<Box<T: dyn Trait>>) -> T {
  pop::<T>(vec).into_inner::<T>()
}

fn pop<T: dyn Trait>(vec: &mut Vec<Box<T: dyn Trait>>) -> Box<T: dyn Trait> {
  vec.pop().unwrap()
}

But I don't know when people need to do this through. LOL.

And indeed switching to dynamic dispatch is a little trouble in Rust, have to write a lot of verbose codes.

Then I misunderstood your proposal, can you elaborate on what would be the difference?

(a generic T: Trait and impl Trait aren't also exactly the same, but mostly the same for most purposes)

It's just syntax problem, I write the dyn in a different place. I don't know which is better:

fn foo<T: Trait>(vec: &mut Vec<Box<T: dyn Trait>>) -> T {
  pop::<T>(vec).into_inner::<T>()
}

fn pop<T: dyn Trait>(vec: &mut Vec<Box<T: dyn Trait>>) -> Box<T: dyn Trait> {
  vec.pop().unwrap()
}

or

fn foo<T: Trait>(vec: &mut Vec<Box<dyn T: Trait>>) -> T {
  pop::<T>(vec).into_inner::<T>()
}

fn pop<dyn T: Trait>(vec: &mut Vec<Box<dyn T: Trait>>) -> Box<dyn T: Trait> {
  vec.pop().unwrap()
}

The idea is the same as you thought.

Box<dyn T: Trait> has the same runtime implementation as Box<dyn Trait>, just it carries type information with it so we can use statical type info to retrieve the value with the actual type.

1 Like

Well, assuming you already pass by reference or pointer everywhere. Pass-by-value gives you an often-silent footgun instead (slicing)! But yeah, Rust requires more ceremony partly because it stores the vptrs in &T, not T itself. This makes T smaller, but more pertinently it allows (local) traits to be implemented for foreign types, which is a really important part of the Rust object model.

10 Likes

I'm thinking about dyn Any, what is the different?

dyn Any is just a boxed object which can be anything, like interface{} of Golang. My idea is about quanlification which gives Rust the ability of implementing universal types. Rust already have compile time universal types which is generic method

struct Foo {}

impl Foo {
  fn foo<T>(t: T) -> T { t }
}

However we can't have a polymorphic value of which method can still be parameterized, you can't made a trait object from the following trait:

trait Bar {
  fn bar<T>(t: T) -> T;
}

Alternative way is to just use compile time polymorphic:

fn foobar<X: Bar, T>(x: X, t: T) -> T {
  x.bar::<T>(t)
}

But this is not always working, for example, if you want to put x into a runtime container, you can't infer which version of Bar::bar should be generated for type X, because the type parameter could be anything.

fn put<X: Bar>(self: &mut Container, x: X)  {

}

fn event_loop(container: &mut Container) {
   container.put<Foo>(make_foo());
  container.put<Bar>(make_bar());
}

fn consume<T>(container: &mut Container, t: T) {
  container.iter().for_each(|x| { x.bar::<T>(t); });
}

One way is try to bind the possible types to the instance which is either similar to type enum or requires a huge changes to the type system. (cpp have a tricky way called STMT which is regarded as illformed program can do the similar thing) Another way is just using type erasure to support dynamic quanlification, so you can have a trait object which support generic method.