Lately, I’ve been working on a huge feature that’s coming to luminance soon. While working on it, I’ve been facing several design problems I think are interesting to talk about.
Imagine you want to expose a trait that defines an interface. People know about the interface and can use provided types to switch the implementation. That’s a typical use case of traits.
// This trait is pub so that users can see and use it
pub trait System {
type Err;
fn do_something(&mut self) -> Result<(), Self::Err>;
}You can have a type SimpleSystem that implements
System and that will do something special in
do_something, as well as a type
ComplexSystem doing something completely
different.
Now imagine that your System trait needs to expose
a function that returns an object that must be typed. What it
means is that such an object’s type is tagged with another type.
Imagine a type Event that is typed with the type of
event it represents:
That type must be provided and implemented by systems, not by the actual interface code. How would we do this?
Furthermore, we might want another trait to restrict what
T can be, but it’s off topic for our current problem
here.
Let’s try a naive implementation first:
pub trait System {
type Event;
type Err;
fn do_something(&mut self) -> Result<(), Self::Err>;
fn emit_event(&mut self, event: Self::Event);
}That implementation allows SimpleSystem to
implement Event as a single type and then implement
emit_event, taking its Event type.
However, that event is not typed as we wanted to. We want
Event<T>, not Event.
However, Rust doesn’t authorize that per-se. The following is currently illegal in Rust:
RFC 1598 is ongoing and will allow that, but until then, we need to come up with a solution.
The problem is that associated types, in Rust, are completely
monomorphized when the trait impl is monomorphized,
which is, for instance, not the case for trait’s functions.
emit_event will not have its F type
variable substituted when the implementor is monomorphized — it
will be sank to a type when it’s called. So what do we really want
to express with our Event<T> type?
That would work but that’s not exactly the same thing
as our previous trait. The rest of the trait doesn’t really depend
on EventType, so we would duplicate code every time
we want to support a new type of event. Meh.
Event<T> is a higher-kinded type (HKT).
Event, here, is what we call a type
constructor — as opposed to data constuctor, like
associated new functions. Event takes a
type and returns a type, in the type-system world.
As I said earlier, Rust doesn’t have such a construct yet. However, we can emulate it with a nice hack I came across while trying to simulate kinds.
See, when a HKT has its type(s) variable(s) substituted, it
becomes a regular, monomorphized type. A
Vec<T>, when considered as
Vec<u32>, is just a simple type the same way
u32 is one. The key is to decompose our trait into
two distinct yet entangled interfaces:
The first trait is implemented on systems and means “[a type] knows how to handle an event of a given type.” The second trait is implemented on systems, too, and means “can handle all events.”
pub trait SystemEvent<T>: System {
type Event;
fn emit_system_event(&mut self, event: Self::Event) -> Result<(), Self::Err>;
}
pub trait System {
type Err;
fn do_something(&mut self) -> Result<(), Self::Err>;
fn emit_event<T>(
&mut self,
event: <Self as SystemEvent<T>>::Event
) -> Result<(), Self::Err>
where Self: SystemEvent<T> {
<Self as SystemEvent<T>>::emit_system_event(self, event)
}
}The idea is that the SystemEvent<T> trait
must be implemented by a system to be able to emit events of type
T inside the system itself. Because the
Event type is associated in
SystemEvent<T>, it is the monomorphized version
of the polymorphic type in the actual implementation of the trait,
and is provided by the implementation.
Then, System::emit_event can now have a
T type variable representing that
Event<T> we wanted. We use a special
type-system candy of Rust here: Self: Trait, which
allows us to state that in order to use that
emit_event<T> function, the implementor of
System must also satisfy
SystemEvent<T>. Even better: because we already
have the implementation of emit_system_event, we can
blanket-implement emit_event<T>!
Several important things to notice here:
System, to work as a system, obviously.SystemEvent<T>, to handle events of type
T. The actual type is defined by the system
itself.SystemEvent<T> if it doesn’t know how to handle
events of type T. That opt-in property is interesting
for us as it allows systems to implement only what they support
without having to make our design bleed to all systems.
Neat.Self: Trait allows to introduce a
form of polymorphism that is not available without it.emit_event, the
implementor of System doesn’t even have to implement
emit_event.SystemEvent<T> has System has
super-trait to share its Err type.The last point is the hack key. Without
Self: Trait, it would be way harder or more
convoluted to achieve the same result.
Let’s see a simple implementor that will just print out the
event it gets and does nothing in do_something.
struct Simple;
#[derive(Debug)]
struct ForwardEvent<T>(pub T);
impl System for Simple {
type Err = ();
fn do_something(&mut self) -> Result<(), Self::Err> {
Ok(())
}
}
impl<T> SystemEvent<T> for Simple where T: std::fmt::Debug {
type Event = ForwardEvent<T>;
fn emit_system_event(&mut self, event: Self::Event) -> Result<(), Self::Err> {
println!("emit: {:?}", event.0);
Ok(())
}
}As you can see, it’s really simple and straight-forward. We can
select which events we want to be able to handle: in our case,
anything that implements Debug.
Let’s use it:
fn main() {
let mut system = Simple;
system.emit_event(ForwardEvent("Hello, world!"));
system.emit_event(ForwardEvent(123));
}The idea is that, given a type S: System, we might
want to emit some events without knowing the implementation. To
make things even more crunchy, let’s say we want the error type to
be a ().
Again, it’s quite simple to do:
// we need this to forward the event from the outer world into the system so that we don’t have to
// know the actual type of event used by the implementation
impl<T> From<T> for ForwardEvent<T> {
fn from(t: T) -> Self {
ForwardEvent(t)
}
}
fn emit_specific_event<S, E>(
system: &mut S,
event: E
) -> Result<(), S::Err>
where
S: System<Err = ()> + SystemEvent<E>,
S::Event: From<E>,
{
system.emit_event(event.into())
}
fn main() {
let mut system = Simple;
system.emit_event(ForwardEvent("Hello, world!"));
emit_specific_event(&mut system, "Hello, world!");
}We could event change the signature of
System::emit_event to add that
From<E> constraint to make the first call
easier, but I’ll leave you with that. The important aspect of this
code snippet is the fact that the implementor will handle a type
of event Event<T> while the interface uses
T directly. We have injected a HKT
Event.
Why do I care about such a design? It might seem complex and hard, but it’s actually a very useful use of a typeclass / trait type system — especially in luminance, where I use type-system concepts a lot; after all, it’s based on its Haskell version! If you compare my solution to the next-to-come HKT proposal from RFC 1598, we have:
type Event<T>;
as associated types, which will allow to remove our
SystemEvent<T> trait.T here is the same for all
implementors: an implementor cannot restrict T, it
must be implemented for all of them. If you want to restrict the
type of events your type can receive, if I understand the RFC
correctly, you’re handcuffed. That RFC will authorize the
author of the trait to restrict your T, not
the author of the implementor. That might have some very
useful advantages, too.T by applying constraints on
emit_event.In the quest of emulating HKT, I’ve found myself with a
type-system toy I like using a lot: equality
constraints and self-constraints (I don’t know how those
Self: Trait should be named). In Haskell, since we
don’t implement a typeclass for a type but we provide
an instance for a typeclass, things are slightly
different. Haskell doesn’t have a Self type alias,
since a typeclasses can be implemented with several types
variables (i.e. with the MultiParamTypeClasses and
FlexibleInstances GHC extensions), only equality
constraints are needed.
In the end, Rust continues to prove that even though it’s a systems programming language, I can express lots of powerful abstractions I miss (a lot) from Haskell with a bit more noise. I think the tradeoff is worth it.
I still haven’t completely made up my mind about GAT / RFC 1598 (for sure I’m among the ones who want it on stable ASAP but I’m yet to figure out exactly how it’s going to change my codebases).
As always, have fun, don’t drink and drive, use condoms, keep the vibes and don’t use impl Trait in argument position. Have fun!