Complete Type Mappings for Evolving Systems
- Eldan Ben Haim
- Sep 10, 2024
- 13 min read
School Games is a project I’ve started around two years ago — hoping it will be of use for my wife in her job as a teacher. It started out as a couple of web-based games / activities for teachers to use in school literacy lessons. The games are run as part of a session (the “lesson”) that involves a central console (operated by the teacher and projected to all other participants) and several terminals (typically a mobile phone or tablet) operated by each of the participants. The thing is written in TypeScript, with a nest.js based backend and an Angular based frontend. These three probably constitute my favorite stack. Of course, once I had the infrastructure in place to realize those multi-participant activities, it was only natural to extend the system by adding more and more games. And so, as of this writing, School Games includes the two original literacy-oriented games, a “Wikipedia Race” game and another recent addition which a rendition of some card game. On top of these, I have a long list of candidate games I would like to implement.
Functionalities and Domain Partitions For Describing Evolving Systems
If we were to describe the system's design, clearly there’s an infrastructure thing going on here (web-based multiple participant lessons) and a set of plugins or applications written on top of that architecture -- one for each game.
Digging a little deeper, each activity in the system is implemented as three software components:
A backend game state object, managing the game state — turns, scoring, allowed actions, …
A frontend console UI component for the game, presenting the shared projected data,
A frontend terminal UI component for the game, presenting the per-participant UI
A set of interfaces and common data models to be shared by the three components above.
These game-specific components collaborate with the infrastructure; the infrastructure has specific expectations that each game will have an associated implementation of each of them. However, the first three components are running in very different runtime environments and contexts (for example, the game state object is running on the backend whereas the console and terminal UI components are running in the frontend). The infrastructure allows the console and terminal frontend components to issue RPC calls to the game state object, and vice versa — the game state object may invoke calls on frontend components to e.g notify them of state changes.
Since the game copmonents are distributed across different parts of the system that use a different techonology stack and implementaiton idioms, there’s a desire to decouple these components and restrict the communication between them to specific well defined interfaces. Specifically, from a deployment perspective they should live in different NPM packages (e.g., frontend vs backend).
This set of games and activities is a very natural hotspot for system evolution (We can easily foresee additional games and activities being implemented). And so, while separation of concerns and decoupling between the components is great in that it leads to manageable and maintainable code, it also means that when implementing a new activity — again, a common evolution transaction — multiple "unrelated" components should be created, and the implementor should somehow know that.
This trait of School Games is by no means unique. Many systems can be viewed as performing a set of functionalities on a problem domain. Often, the problem domain consists of different ‘partitions’, and the set of functionalities that need to be supported for them is common to the different partitions however the implementation of each functionality may be different between partitions. We can imagine a matrix where the rows correspond to problem domain partitions, and the columns to functionalities. Each cell represents the implementation of a specific functionality in the context of a problem domain partition. Here is a simplified matrix for School Games:
Backend State | Terminal <—> Backend Transaction Service | Terminal UI | Console UI | |
Word Pop | ||||
Word Roulette | ||||
Wiki Race | ||||
What’s Your Stand |
And here’s an example for a more evolved system, for designing electronic circuits:
Render | Edit On Diagram | Property Editor | Simulate | Export to BOM | |
Wire | |||||
Resistor | |||||
Capacitor | |||||
Battery | |||||
Diode | |||||
Switch | |||||
Transistor |
In this post we're going to explore a few implementation approaches for maintaining these matrices in a way that will preserve decoupling and cohesion among the components, while still capturing the implementation requirements for adding new functionalities and new domain partitions. If this reminds you of Double Dispatch discussions -- that's because this is clearly a manifestation of double dispatch. A lot of the principles we're discussing can be applicable to more generalized double-dispatch problems.
Note in some cases it may be tolerable to allow some coupling between different "functionalities". For example, for the circuit design system, coupling rendering, editing on a diagram and property editing may not be a big deal as they all typically closely collaborate within a circuit editing experience; whereas the simulation functionality should probably be more decoupled to e.g allow simulation in an interactive and in a batch context, in distributed execution environments, etc. Partitioning the system's implementation to different "functionalities" as the term is used here is a discussion of cohesion, coupling and other design principles — that for this post we’re going to ignore.
Simple Type Maps
A straightforward approach for implementing a functionality/domain partition dispatch mechanism would be maintaining for each functionality a map between a domain partition and an implementation of the functionality. This works like this:
Decide on a representation for the “domain partition”. This could be an enum identifying the partition (e.g “game name”), or a type.
Define an interface that corresponds to the functionality you’re mapping.
Maintain a map that maps from the domain partition representation to an implementation of the functionality interface for that domain partition (or to a factory thereof).
For example, for SchoolGames, this could look like the following.
In a module common to the frontend and the backend:
export type GamesRegistry =
"word-roulette" | "word-pop" |
"wiki-race" | "whats-your-stand”;In the backend:
export const GameToBackendState = {
"word-pop" : () => new WordPopGameState(),
// ...
}In the terminal frontend:
export const GameToTerminalFrontendComponent = {
"word-pop" : WordPopTerminalFrontend,
// ...
}Then, where the application needs to perform a functionality on a specific domain partition — it easily looks up the implementation in the corresponding map.
When adding a new game (new domain partition), we start by adding a literal to the GameRegistry type. That much knowledge can be documented as part of the system’s design. However, we should also document the fact that the GameToBackendState and GameToTerminalFrontendComponent mappings should be updated. This is doable, but for a complex enough system with a big enough team clearly we’d like to have our development tools eliminate the need for us to remember the set of different steps we need to follow to complete the implementation of a game. Realistically, with the approach documented above, it is not common for developers to forget some required implementation steps. In the best case, this makes development and testing cycles longer; in the typical case this impacts quality (missing implementations may be discovered rather late in the development lifecycle which inherently impacts quality; at the extreme case they may not be discovered before shipping).
Complete Type Maps
We can improve the approach portrayed above by employing complete type maps. The complete type map mechanism comprises of two components:
A registry mechanism — keeping track of the domain partitions, much like the GameRegistry type above
A type map mechanism that can be used by the system to lookup an implementation given a domain partition, and guarantees the following early in the development lifecycle — preferably in design- or build-time, less optimally in test-time:
All domain partitions have an entry in the type-map.
The value to which the domain partitions are mapped adheres to constraints set individually for each type-map (e.g it is derived from a specific type).
This is very easy to implement in TypeScript:
// A type map from the domain partition to a type
export type TypeMap<S extends string, T> = { [index in S]: T };And then, in e.g the backend:
export const GameToBackend: TypeMap<GameRegistry, () => GameState> = {
// ...
};And in the terminal frontend:
export const GameToTerminalUi: TypeMap<
GameRegistry,
(terminalUiHost: ITerminalUIHost) => ITerminalUi
> = {
// ...
};Similarly for the the electronic circuit design program, we’d have:
// Domain partition registry
export type ElectronicComponents =
"wire" | "resistor" | "capacitor" |
"battery" | "diode" | "switch" | "transistor";
export const Renderers: TypeMap<
ElectronicComponents,
(component, canvas) => void> = {
// ...
};
export const Simulators: TypeMap<
ElectronicComponents,
(component, simulation) => void> = {
// ...
};Suppose we add a new game, ‘twenty-questions’. The one thing that the system doesn’t guide the developer to do is to add a literal for that game to the GameRegistry type. But once the developer does that (which is a pretty basic thing to require), the system will guide them through the rest of the implementation by breaking the compilation process with clear indication on what’s missing. The IDE and the compiler actually can guide the developer through the steps to implement the new game. Of course, we still need to make sure the different interfaces that the developer needs to implement should are self descriptive, or include inline documentation.
For the circuit design example above note that the targets of the maps (the functions receiving a component as their first argument) are a bit lacking in typing — nothing forces us to match the electronic components to component types. This can be improved easily using some TypeScript type-system-fu:
export type TypedHandlerMap<
S extends string,
TM extends { [index in S]: unknown },
F extends (...a: any) => any
> = {
[index in S]: (subject: TM[index], ...args: Parameters<F>) =>
ReturnType<F>;
};
type ElectronicComponentTypes = {
battery: BatteryComponent;
capacitor: CapacitorComponent;
// Missing types here will cause errors in TypeHandlerMap
// instantiations!
};
const Renderer: TypedHandlerMap<
ElectronicComponents,
ElectronicComponentTypes,
(canvas) => void
> = {
// subject here is typed as BatteryComponent
battery: (subject, canvas) => {},
// subject here is typed as CapacitorComponent
capacitor: (subject, caches) => {},
};Note that subject above is typed as expected for the different functions. Also note that if we want, we don't have to have idependent definitions for ElectronicComponents and ElectronicComponentTypes. We can have only ElectronicComponentsTypes, and define ElectronicComponent as a type based on the keys of ElectronicComponents.
Complete Type Maps in C++
Like most languages, C++ doesn’t directly support mapped types — which was fundamental to our implementation in TypeScript. So we’ll need to resort to a different approach here.
First, recall that C++ supports function overloads. We’re going to try to create our type map as a class that implements an overload of a specific member (or set of members) for each of the types in the type registry. To keep our discussion simple, our complete type maps will always have an overloaded member called createHandler, returning a handler object. However it’s easy to extend this to a more general case — where the type map contains multiple members per mapped type.
Another difference between our implementation in C++ and the TypeScript version is that while in TypeScript we used string literal types to domain partitions (again, a fundamental piece for mapped types) — in the C++ approach we’ll use a type hierarchy to represent these partitions. Again, we could use a different approach here — e.g by using template literals — but trying to keep the discussion simple leads us to this choice.
To illustrate, for our game example, we can conjure up a GameDescriptor hierarchy:
class GameDescriptor
{
};
class GameDescriptorWordPop : public GameDescriptor
{
};
class GameDescriptorWordRoulette : public GameDescriptor
{
};A type map based on method overloads would look something like:
class GameState;
class GameRenderer;
class GameStateProvider
{
public:
GameState *createHandler(const GameDescriptor *);
GameState *createHandler(const GameDescriptorWordPop *);
GameState *createHandler(const GameDescriptorWordRoulette *);
};
class GameRendererProvider
{
public:
GameRenderer *createHandler(const GameDescriptor *);
GameRenderer *createHandler(const GameDescriptorWordPop *);
GameRenderer *createHandler(const GameDescriptorWordRoulette *);
};The type maps above have one overload of createHandler for each concrete type of GameDescriptor, corresponding to each domain partition. But there’s one additional overload: look at createHandler(const GameDescriptor*). The typical use case for type maps is to map an unknown type to a target type. Which means the typical call-site for createHandler will pass a GameDescriptor * rather than a concrete subclass. So the implementation of createHandler should inspect the runtime type of the passed argument, and based on the type dispatch to one of the functions. Something along the lines of:
GameRenderer GameRendererProvider::createHandler(
const GameDescriptor *x) {
if(dynamic_cast<const GameDescriptorWordPop*>(x)) {
return createHandler((const GameDescriptorWordPop*)(x));
} else
if(dynamic_cast<const GameDescriptorWordRoulette*>(x)) {
return createHandler((const GameDescriptorWordRoulette*)(x));
} else {
// Roll over and play dead
}
}We’re left with the question, however, of how to force GameStateProvider and GameRendererProvider to have overloads for all types of GameDescriptor. As a first step — we can define interfaces (abstract classes in C++) for each of the type maps to implement:
class GameStateProviderInterface
{
public:
virtual GameState *createHandler(const GameDescriptor *) = 0;
virtual GameState *createHandler(
const GameDescriptorWordPop *) = 0;
virtual GameState createHandler(
const GameDescriptorWordRoulette *) = 0;
};
class GameStateProvider : public GameStateProviderInterface
{
public:
GameState *createHandler(const GameDescriptor *)
override;
GameState *createHandler(
const GameDescriptorWordPop *) override;
GameState *createHandler(
const GameDescriptorWordRoulette *) override;
};We could centralize all *ProviderInterface definitions in one module / file, which theoretically makes things easier — add the new type overload to each of the interfaces (…), and then all the implementations will have to align. This, however, does mean that there’s one uber-compilation-unit coupled to whatever the different providers need to be coupled with. So a simple improvement would be:
template <class T>
class ProviderInterface
{
public:
virtual T createHandler(const GameDescriptor ) = 0;
virtual T createHandler(const GameDescriptorWordPop ) = 0;
virtual T createHandler(const GameDescriptorWordRoulette ) = 0;
};
class GameStateProvider : public ProviderInterface<GameState>
{
// ...
};
class GameRendererProvider : public ProviderInterface<GameRenderer>
{
// ...
};Here — ProviderInterface is our type registry. It has an overload of createHandler for each domain partition. It’s implemented once in a centralized place. All type maps derive from an instantiation of this interface. So when we want to add a new type partition, we simply add a new overload to ProviderInterface, and whoosh — all providers will shout (assuming they’re in use by the code) about the missing overload.
Well, almost whoosh. Remember createHandler(const GameDescriptor*)? It’s a bit of boilerplate code that we currently force all implementations to more-or-less repeat; what’s more, it should contain code that inspects each mapped type and each of these implementations could omit some of the types as the system evolves. Let’s see if we can make things better:
template <class T>
class ProviderInterface
{
public:
T createHandler(const GameDescriptor );
virtual T createHandler(const GameDescriptorWordPop ) = 0;
virtual T createHandler(const GameDescriptorWordRoulette ) = 0;
};
class GameStateProvider : public ProviderInterface<GameState>
{
public:
GameState *createHandler(const GameDescriptorWordPop ) override;
GameState *createHandler(
const GameDescriptorWordRoulette *) override;
};
class GameRendererProvider : public ProviderInterface<GameRenderer>
{
public:
GameRenderer *createHandler(const GameDescriptorWordPop *)
override;
GameRenderer *createHandler(const GameDescriptorWordRoulette *)
override;
};It turns out we can implement createHandler in the provider interface, and spare specific implementations from implementing it.
So where are we now? We define a single type registry, ProviderInterface, and derive from it any type map we want. When we want to add a new type, we add an override function to the type registry and change the implementation of the type dispatch logic in ProviderInterface::createHandler(GameDescriptor*). That’s much better than where we started, and an OK situation to be at. But still adding a partition is cumbersome, and requires three unrelated edits (create type descriptor class, add override, add dispatching logic) — which is error prone.
We can improve our solution by using a bit of C++ template trickery. Consider the following template definitions:
template <class B, class H, class T, class... TS>
class ETypeMap : public ETypeMap<B, H, TS...>
{
public:
virtual H createHandler(const T &) = 0;
};
template <class B, class H, class T>
class ETypeMap<B, H, T>
{
public:
virtual H createHandler(const T &) = 0;
};
template <class H>
using GameDescriptorProviderInterface =
ETypeMap<GameDescriptor, H,
GameDescriptorWordPop,
GameDescriptorWordRoulette>;
class GameStateProvider2 :
public GameDescriptorProviderInterface<GameState>
{
…
};Let’s analyze what’s going on here:
ETypeMap is a template definition (with specializations) that serves as a generic utility class.
It’s parameterized by the following:
A base class for the domain partition classes (not used here, we’ll see how it’s used later) denoted as B,
the result type for the createHandler function denoted as H,
and a list of of types in the type registry — all are subtypes of B (denoted as TS… in the generic declaration and as T for the specialization for one type).
ETypeMap is defined by induction, with the base of the induction provided by the specialization ETypeMap<B, H, T> — so with a single type in the type list. A specialized one-type type map defines a single overload of createHandler, typed for that type. A type-map with n+1 types derives from a type map with the last n types, and adds an overload of createHandler for the first type. So ultimately, we get a type map with overloads for all of the types in the registry.
Note that ETypeMap is defined once as an “infrastructure” component, and has no coupling to a specific application or problem domain.
GameDescriptorProviderInterface is a type alias that specializes ETypeMap for use with GameDescriptor-based type maps. This is analogous to ProviderInterface<T> in our naive implementation above. It serves as our type registry — as this declaration lists all domain partitions.
Finally GameStateProvider2 is derived from GameDescriptorProviderInterface with a specific returned type handler type.
So this is nicer, getting rid of the boilerplate required to add an overload for each type. Want to add a new domain partition? Great; derive a GameDescriptor and add it to the list in GameDescriptorProviderInterface. But we still don’t have a dispatcher there — that is, a createHandler(const GameDescriptor&). Let’s add some complexity to ETypeMap then ;)
template <class B, class H, class T, class... TS>
class ETypeMap : public ETypeMap<B, H, TS...>
{
public:
H createHandler(const B &b)
{
if (dynamic_cast<const T *>(&b))
{
return createHandler((const T &)(b));
}
else
{
return ETypeMap<B, H, TS...>::createHandler(b);
}
}
virtual H createHandler(const T &) = 0;
};
template <class B, class H, class T>
class ETypeMap<B, H, T>
{
public:
H createHandler(const B &b)
{
if (dynamic_cast<const T *>(&b))
{
return createHandler((const T &)(b));
}
else
{
throw std::runtime_error("I'm rolling over and playing dead");
}
}
virtual H createHandler(const T &) = 0;
};Whew... This adds an implementation of createHandler that receives a parameter of the domain partition base type and dispatches to one of the overloads based on the concrete type of the argument passed to it. This do is defined by induction: for the base ETypeMap we just check if the provided domain partition instance is of the single type in the type list, and dispatch to the single overload based on that. For a list of size n+1 type arguments, we first check for the first type in the list — and if there’s no match we delegate to implementation for an n-sized list, with the suffix of our type list. All this function calling may look inefficient — but note that we’ve deliberately defined the dispatchers as non-virtual, meaning that compilers will typically inline this to a single function similar to the implementation we wrote by hand (I’ve verified that Apple clang-1500.3.9.4 does that with -O3).
And so, with this implementation we’re able to create a complete type map, verified in build time and with zero boilerplate — you just need to register the types in the type registry.
Epilogue
Double dispatch, and specifically the case of matching an implementation of a functionality in a complex system to a specific domain partition, is a very common evolution path for systems. In this post we've presented a few implementation approaches in TypeScript and C++ for implementing mechanisms for dispatching to implementations based on functionality and domain partition that allow the implementations to be decoupled from each other, while still capturing the overall structure of the system and allowing IDEs and compilers to guide developers through adding domain partitions or functionalities.
While we didn't demonstrate this, similar approaches can be easily translated to C# and Java -- using a combination of generics, type hierarchies and reflection. Implementation in dynamic languages such as Python and Ruby should be straightforward as well. If you have implemented similar mechanisms in these languages or any other -- share your experience in the comments!
Comments