Reflections on Companion Type Systems

TLDR: When manipulating a sealed trait and its subclasses, it can be useful to define a dual type hierarchy on their companion objects. We can use reflection to test this “Companion Type System” and safely gather all of its members.

That was short, now keep this post so that you can read it later!

Example: Polymorphic Serialization in a Persistent Event Queue

In a previous post, we described how database updates had to be propagated through our system in order to be indexed with Lucene.

Now, in a similar way, we want to use a persistent event queue in order to propagate some updates from one storage system (e.g. database) to others (e.g. graph, feature extraction engine…). The queue needs to support several types of events:

Assuming we use Json to get our events in and out of the queue, we have to define a Json formatter for Event. For it to work in a polymorphic fashion, some information about the event subtype has to be serialized together with the actual instance. In this way, at deserialization, we can read that type information before picking up a deserializer that will instantiate the proper event subtype.

In short, we need two components for each subtype:
— a Json formatter able to translate a subclass instance to/from a serialized value.
— some sort of header that serves as a serializable identifier of the subtype.

Companion objects are a natural home for these helpers and here’s what our solution looks like:

In order to write our polymorphic Event formatter, each event subtype’s companion object had to define the proper serialization helpers. Thus we ended up creating an EventCompanion trait that every companion inherits from.

Introducing Companion Type Systems

Now, it is sometimes desirable for the companion objects of these classes to share some common interface as well. We can achieve that in a similar fashion, having each companion object extend some common superclass. This set of typed companion objects is referred to as the “Companion Type System” of the class (yes, we have just made that up).

In short, the Companion Type System makes it possible to take advantage of polymorphism not only when manipulating dynamic instances (thanks to the main class hierarchy), but also when no instance is around (thanks to the static companion hierarchy).

This situation often arises in the context of serialization / deserialization of some class hierarchy. At FortyTwo, we rely on this pattern in several places: persistent event queues, storage and retrieval of vertex and edge data in our graph, conversion of typed database ids to global ids…

Companion Type Systems even use F-Bounded Types

F-bounded types are also known as self-recursive types, though while this name makes sense for the main trait (Event), it does not for the companion trait (EventCompanion). Indeed in both cases, E refers to the subclasses of Event, thus we can only qualify it as “self-recursive” in Event. So we’ll stick with “F-bounded type” here, plus it sounds smart enough.

An F-bounded type can be introduced either as a type parameter (cf. EventCompanion) or as an abstract type member (cf. Event). We won’t discuss the advantages of one over the other in general. However, we found it hard to make the compiler happy when both F-bounded types are type parameters, mainly because of mutually dependent wildcards showing up here and there. In order to avoid this, it seems best to have the self-recursive type be a type member, like in our example. Besides, it is usually useful to make the F-bounded type of the companion trait a type parameter for it to be a part of the companions’ type signatures, as you may end up passing them around implicitly (again, like in our example).

Final Reflections

Now let’s say someone wants to define a new event AddHostility? There are two main risks:
— not setting up F-bounded type E properly in the AddHostility subclass or its companion object
— forgetting to explicitly register AddHostility in the set of all companion objects in EventCompanion

Thanks to the bounds on E and the companion accessor defined in the Event trait, the compiler should actually catch most issues related to the first point. Regarding the second point, we would like to use reflection in order to gather all companion objects in EventCompanion and rewrite it as follows:

Now as we reflect on the class hierarchy to collect each companion object, we may as well check a few assumptions on our companion type system and make sure that all F-bounded types have been set up correctly. These tests can provide useful specifications anytime we design a new companion type system.

Our implementation of CompanionTypeSystem is a good opportunity to explore the Scala reflection API.

Let’s outline the logic of:

As a reminder, in our example, this method is called with SealedClass = Event, Companion = EventCompanion[_ and fBoundedType = “E”.

In a first step, we reflect on the top level classes (traits) SealedClass and Companion in order to figure out whether fBoundedType is introduced as a type parameter or as an abstract type member. In both cases, we want to check assumptions on its upper bound and on whether or not it has been set up as a self-recursive type (only expected in SealedClass). This happens in:

In a second step, for each of SealedClass‘s child, we must check that fBoundedType has been assigned with the subclass’ own type, both in the subclass itself and in its companion object. While checking the value of an abstract type member is pretty straightforward, checking the value of a type parameter reduces to checking inheritance after setting the type argument. This is why getTypeWithTypeParameterOrElseCheckTypeMember returns a function if fBoundedType actually is a type parameter. That function enables us to substitute type parameter fBoundedType with a valid type argument and use the resulting type in inheritance checks.

We want to iterate over all the children of SealedClass. This is where sealing the main class/trait is coming handy, even though our experience suggests that this is something that you want anyway wherever a companion type system seems like a good idea.

Note that nothing requires the Companion trait to be sealed, even though EventCompanion is in our example and each object is a case object. This comes for free since a companion object has to be declared next to its class anyway. It provides extra convenience in pattern matching as we find ourselves passing these companions around, regarding them as rich type representatives of their class at runtime.

And that’s it, we test our assumptions on abstract type members and/or type parameters for each subclass and collect all the companion objects, which end up forming our Companion Type System.

Editor’s Note: Any convenient bending of theoretical concepts in the context of this post is the author’s sole responsibility and does not necessarily represent the views of FortyTwo. Check out Kifi!

Originally published at eng.kifi.com on April 11, 2014.