News for hackers. Stuff that matters.
Re:Generics and Compile-Time in Rust by saghm on Tuesday June 16, 2020 @12:27AM (#23535944)
> This is generally fine and has worked out well for the language, but there are plenty of use cases where more advanced trait objects could reduce code size and compile times with very small impact on performance, while also enabling some interesting new patterns

To elaborate a bit on the part about new patterns, I've encountered issues where trait objects allow me to define APIs that otherwise wouldn't be possible. One example is when developing something like a database driver, you might define a trait EventHandler with the methods `handle_start_event` and `handle_completion_event`, where users can pass in values of types that implement EventHandler, and you call their handling methods whenever you start or complete an operation. The most straightforward way to specify this would be to have your client type have an internal vector of EventHandlers that you can iterate over and call the corresponding event handling methods whenever needed. If you use generics for this, then your client type will need to be generic over the type of EventHandler it can contain, which means you can't specify EventHandlers with different concrete types. The best way to get around this is to use something like `Vec<Box<dyn EventHandler>>`.

I understand the sentiment behind favoring generics over trait objects in the Rust ecosystem, as strongly preferring compile time costs to runtime costs when there's a choice between them is one of the more fundamental guiding principles to the Rust ecosystem (and is one of the things I really like about Rust), but there are patterns that trait objects allow that just can't be expressed with generics, and when you need to use one of them, it can be frustrated to hit some of those sharp edges you mentioned.

Re:Generics and Compile-Time in Rust by kccqzy on Tuesday June 16, 2020 @04:25AM (#23536991)
> The best way to get around this is to use something like `Vec<Box<dyn EventHandler>>`.

That's exactly the right solution to your problem. It's not a workaround. It is what you need.

What you need is a heterogenous collection of objects that implement a common interface. And the exact type isn't available to you because it's provided by the client. So you need to go through virtual (or dynamic) dispatch.

Just imagine how you might write this in C++: you just define an EventHandler abstract class and ask that clients inherit from it. Then you take pointers to EventHandler and store them.

Or imagine how you might write it in Haskell: simple existential types. The type class dicts are stored by the compiler into your data type to enable dynamic dispatching.

This is object-oriented polymorphism 101. I think Rust's anti-OO pendulum has swung so far that people can't even see that what they need is basic OO.

Re:Generics and Compile-Time in Rust by gpderetta on Tuesday June 16, 2020 @07:20AM (#23537815)
It is not even OO, as the Haskell example shows.

But I understand completely the mindset. If you think that you can implement your solution with full static dispatching and no pointer indirection, having to add these "ugly workarounds" feels like surrendering.

But there is a continuum between full static dispatch and boxing and indirection everywhere. Adding a few carefully chosen "dynamic joints" can add a lot of runtime flexibility at a minimal cost.

Re:Generics and Compile-Time in Rust by saghm on Tuesday June 16, 2020 @11:48AM (#23540569)
> That's exactly the right solution to your problem. It's not a workaround. It is what you need

Yep, I agree! To clarify, the issue for me isn't having to use trait objects like this, it's the ergonomic issues that my parent comment brought up, e.g. not being able to require `EventHandler: Clone`. I'm not opposed to trait objects themselves; I just wish they were easier to use.

Re:Generics and Compile-Time in Rust by couchand on Tuesday June 16, 2020 @01:12AM (#23536111)
I'm confused. In that example, what's wrong with `Vec<Box<dyn EventHandler>>`?
Re:Generics and Compile-Time in Rust by saghm on Tuesday June 16, 2020 @11:53AM (#23540634)
Nothing is wrong with `Vec<Box<dyn EventHandler>>` itself; the issues are around the ergonomics of using trait objects in general (e.g. with regards to requiring that types that implement EventHandler also implement Clone, as mentioned in the parent comment).
Re:Generics and Compile-Time in Rust by kelnos on Tuesday June 16, 2020 @02:59AM (#23536607)
I'm not an expert on this, but my guess would be that it's slow because it requires at too much indirection.

Instead of the Vec holding concrete instances of EventHandler, it holds pointers to them (because of the Box). And then because of the dyn, the compiler can't generate static-dispatch code when you later inevitably want to call functions on the EventHandler, so those function calls have to be resolved at runtime.

Re:Generics and Compile-Time in Rust by masklinn on Tuesday June 16, 2020 @04:28AM (#23537005)
Having dynamic dispatch of boxed structures seems like a logical consequence of wanting dispatch on arbitrary user-provided non-coherent (not the right word but I can’t remember the proper one) types?
Re:Generics and Compile-Time in Rust by orf on Tuesday June 16, 2020 @04:24AM (#23536989)
Is it even possible to do it without indirection? The type parameter of a struct can change its shape hugely, so what you’re asking for is “vectors with variable sized entries” which is typically done with indirection.
Re:Generics and Compile-Time in Rust by jcelerier on Tuesday June 16, 2020 @04:39AM (#23537058)
In C++ we have things like Boost.PolyCollection to improve that specific case : https://www.boost.org/doc/libs/master/doc/html/poly_collecti...

With some metaclass / reflection magic maybe one could come up with an additional scheme that would save the per-object vtable pointer through creation of a "duplicate" structure - e.g. given

    struct Event {
      virtual ~Event();
      virtual bool whateverAPI();
      pair<double,double> globalPosition();
      pair<double,double> localPosition();
    private:
      double x{}, y{};
      Widget& widget;
    };

    struct MyEvent : Event { 
        // or whatever, just an example
        bool whateverAPI() override;

      private:
        MouseButtons button{};
    };
one would get a sub-array of things with a layout similar as

    struct synthesized_MyEvent {
      double x{}, y{};
      Widget& widget;
      MouseButtons button{};

      pair<double,double> globalPosition() { /* potentially UB magic */ }
      pair<double,double> localPosition() { /* potentially UB magic */ }
      bool whateverAPI() { /* potentially UB magic */ }
    };
("potentially UB" being something like copying all the non-vtable things into a stack-allocated concrete MyEvent and calling the virtual function on that which could be worth it for small objects in terms of cache usage if the vtable is 8 bytes and the custom data something like 16 bytes and there's 350000 objects)
Re:Generics and Compile-Time in Rust by clappski on Tuesday June 16, 2020 @07:04AM (#23537723)
In C++ you could do this with std::tuple and variadic templates, if you know all the event handlers at compile time. There would be zero indirection, although depending on how you implement the indexing into the std::tuple (i.e. by treating it as a std::variant and using std::visit) you could still inadvertently generate a vtable.
Re:Generics and Compile-Time in Rust by gpderetta on Tuesday June 16, 2020 @07:22AM (#23537833)
this requires the set of all possible types to be known statically at the point the tuple is defined. True "virtual concepts" are an open set.
Re:Generics and Compile-Time in Rust by gpderetta on Tuesday June 16, 2020 @05:40AM (#23537331)
Sometimes you do not need the vector to be runtime sized, then you can use tuples. In C++ variadic templates make it easy to work with compile time sized collections of objects. I'm sure you could do something similar with rust macros.
Re:Generics and Compile-Time in Rust by lmm on Tuesday June 16, 2020 @04:29AM (#23537010)
That's what a trait object would have to be anyway though? You're going to have to have a vector of virtual function tables at runtime, one way or another.
Re:Generics and Compile-Time in Rust by dllthomas on Tuesday June 16, 2020 @12:53AM (#23536041)
This sounds like the Existential Antipattern, from Haskell land. I don't know to what degree it translates to this setting.

https://lukepalmer.wordpress.com/2010/01/24/haskell-antipatt...

Re:Generics and Compile-Time in Rust by zenhack on Tuesday June 16, 2020 @01:22AM (#23536165)
The difference is that the author's suggestion as to what to do instead doesn't work in Rust. In Haskell there's no need to use a type class/trait here at all; you can just use a record. We could try to do the same thing in Rust with a struct:

struct EventHandler { handle_start_event: fn(), handle_completion_event: fn(), }

...but this differs in a key way from the haskell example: Rust's `fn` is not a closure, it's just a pointer to some code, and you can't construct them dynamically. If you want to pass around a _closure_, you need ...a trait object.

Something like:

struct EventHandler { handle_start_event: Box<dyn impl Fn()>, handle_start_event: Box<dyn impl Fn()>, }

...but that's exactly the pattern the author of that post is suggesting getting away from.

I agree with the author's point, but it doesn't really apply to Rust because there isn't actually a simpler way to do it. And I think that's part of what the OP was getting at -- Trait objects are the closest thing Rust has to proper closures, and they're a bit awkward.

Note that I'm still something of a newbie at Rust, and don't feel like I can really say much about the day to day experience of using (or avoiding) trait objects due to limited experience.

Re:Generics and Compile-Time in Rust by dllthomas on Wednesday June 17, 2020 @02:46AM (#23548505)
Great context, thanks! My intent was not to say "this is bad in Haskell so it might be bad here", but more to hope that suggested alternatives might prove interesting - particularly if running into limitations with the current approach.
Re:Generics and Compile-Time in Rust by eptcyka on Tuesday June 16, 2020 @03:35AM (#23536788)
Closures are the closest thing to closures Rust has.
Re:Generics and Compile-Time in Rust by zenhack on Tuesday June 16, 2020 @04:07AM (#23536924)
I was mostly talking about the type level; I certainly didn't mean to imply that Rust didn't have lambdas if that's what you're getting at. But there is no general type of Rust lambdas that take an A and return a B other than the trait object type `dyn impl Fn(A) -> B` (Or FnMut or FnOnce); the concrete type will depend on what variables it captures.

Also, there's a lot of disagreement about exactly what the distinctions between `lambda`, `closure`, `anonymous function` and friends mean. The interpretation of `closure` I'm interested in is basically a bundle of code and data, which can be treated abstractly in a first class way. That could be something that appears as a lambda capturing variables in the text of your program or as an object in a more OO setting which, albeit more verbose for a single function, has a similar level of power of abstraction.

Either way, part of that power is being able to write code that can work with the interface (irrespective of the shape of the enclosed data), and do things like store differing implementations in lists/vecs etc. The only mechanism Rust provides to do that is trait objects.

Re:Generics and Compile-Time in Rust by gpderetta on Tuesday June 16, 2020 @06:38AM (#23537590)
> there is no general type of Rust lambdas that take an A and return a B other than the trait object type `dyn impl Fn(A) -> B` (Or FnMut or FnOnce);

I don't understand the issue (and I know very little of rust), but isn't `dyn impl Fn(A) -> B` exactly that type? Any language with first class function parameters and objects, but type erases them (unlike rust and c++) would implement them pretty much like the dyn impl above under the hood.

Re:Generics and Compile-Time in Rust by zenhack on Tuesday June 16, 2020 @12:41PM (#23541165)
The comment I originally replied to linked to a blog post arguing that in Haskell, the practice of wrapping type classes (which Rust calls traits) in an existential is an antipattern, because rather than using fancy type system features, you could just use a record with some functions in it, which is simpler and more direct.

But dyn impl is a trait wrapped in an existential. There's no concrete type a -> b, only a trait for types that can be 'called.' So to pass an arbitrary function around in a record/struct you need to do the very thing the post is saying is an antipattern (in Haskell). So the argument doesn't really apply to Rust because there isn't a simpler more direct way to achieve the same thing.

Re:Generics and Compile-Time in Rust by gpderetta on Tuesday June 16, 2020 @02:25PM (#23542408)
Right, I completely failed to understand your point. You are completely right of course.
Re:Generics and Compile-Time in Rust by ImprobableTruth on Tuesday June 16, 2020 @06:15AM (#23537482)
The existential 'antipattern' is the only way to get close to a good notion of subtyping. In my experience it also tends to be faster.
Re:Generics and Compile-Time in Rust by dllthomas on Tuesday June 16, 2020 @11:27AM (#23540275)
FWIW, I think "antipattern" is an overstatement, but it's what the community has been calling it. I do think some of the discussion around it is interesting and possibly valuable.