Emulating RFC 1598, less or… more?!

Emulating RFC 1598, less or… more?!

type-systems, rust, haskell, hkt, gat, rfc-1598

2019-11-25 15:50:00 UTC, by Dimitri Sabadie


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.

The context

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:

pub struct Event<T> {
  code: i64,
  msg: String,
  // …
}

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.

The problem

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:

pub trait System {
  type Event<T>;

  // …

  fn emit_event<T>(&mut self, event: Self::Event<T>);
}

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?

pub trait System<EventType> {
  type Event;

  fn emit_event(&mut self, event: Self::Event);
}

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.

Faking higher-kinded types

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:

The last point is the hack key. Without Self: Trait, it would be way harder or more convoluted to achieve the same result.

A simple implementor

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));
}

Polymorphic use

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.

Rationale

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:

Conclusion

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!