Type Erasure with Merged Concepts

Posted on October 19, 2014

Two days ago, I watched a very in­ter­esting talk by Zach Laine: Prag­matic Type Era­sure: Solving OOP Prob­lems with an El­e­gant De­sign Pat­tern. The ques­tion that Zach Laine ad­dresses is how to pro­vide poly­mor­phic in­ter­faces while, at the same time, ad­hering to value se­man­tics. I do also rec­om­mend the fol­lowing talk by Sean Par­ent, which gives a great in­tro­duc­tion into the con­cept and the ben­e­fits of type-era­sure, and value se­man­tics: In­her­i­tance Is The Base Class of Evil

This post is mo­ti­vated by a ques­tion that came up on Reddit. Namely, how can we merge mul­tiple type-erased in­ter­faces into one single in­ter­face. A sim­ilar ques­tion is also asked in the end of the first talk: How to apply type era­sure to types with over­lap­ping in­ter­faces? The speak­er’s an­swer is to simply re­peat the common parts. I think there has to be a better way. So, in this post I am going to ex­plore how to merge type-erased in­ter­faces. But first, let’s quickly re­vise type-era­sure.

(Note, the C++ code ex­am­ples are sim­pli­fied in favour of read­abil­ity. A link to working code is pro­vided at the end of each sec­tion.)

Type Era­sure

Sup­pose we want to write a func­tion which greets a person named Tom in some way. I.e. could print “Hi Tom”, “Hello Tom”, “Good day Tom”, … you get the idea. The func­tion should ac­cept an ar­gu­ment that spec­i­fies how to greet a per­son. We will call this ar­gu­ment a Greeter. Here is a simple im­ple­men­ta­tion of our func­tion:

void greet_tom(const Greeter &g) {
    g.greet("Tom");
}

A user of this func­tion may now wish to greet Tom in Eng­lish and in French. So, he im­ple­ments two Greeters:

struct English {
    void greet(const std::string &name) const {
        std::cout << "Good day " << name << ". How are you?\n";
    }
};

struct French {
    void greet(const std::string &name) const {
        std::cout << "Bonjour " << name << ". Comment ca va?\n";
    }
};

Now, how can the user pass his Greeters to our func­tion? Clas­si­cally, we could ei­ther de­fine an ab­stract base class and let our user de­rive from it, or we could make greet_tom a func­tion tem­plate in Greeter. Both methods have their down-sides, which are de­scribed in the above men­tioned talks.

With type-era­sure, we will hide the tem­plates, and the in­her­i­tance under the cov­ers. We will de­fine a Greeter class that can be ini­tial­ized with any­thing that pro­vides the ex­pected Greeter in­ter­face. Fol­lowing Sean Par­ent’s pat­tern an im­ple­men­ta­tion could look as fol­lows:

class Greeter {
  public:
    // Constructor: We can stuff anything into a Greeter costume.
    template <class T>
    Greeter(T data) : self_(std::make_shared<Model<T>>(data)) {}

    // External interface: Just forward the call to the wrapped object.
    void greet(const std::string &name) const {
        self_->greet(name);
    }

  private:
    // The abstract base class is hidden under the covers...
    struct Concept {
        virtual ~Concept() = default;
        virtual void greet(const std::string &) const = 0;
    };
    // ... and so are the templates.
    template <class T>
    class Model : public Concept {
      public:
        Model(T data) : data_(data) {}
        virtual void greet(const std::string &name) const override {
            // Forward call to user type.
            // Requires that T can greet.
            data_.greet(name);
        }

      private:
        // The user defined Greeter will be stored here. (by value!)
        T data_;
    };

    // Polymorphic types require dynamic storage.
    // Here we store our pointer to the Model that holds the users Greeter.
    std::shared_ptr<const Concept> self_;
};

Note that we are using a shared-pointer to const to refer to the im­ple­men­ta­tion. The de­tails are ex­plained in Sean Par­ent’s talk. We get copy-on-write and value-se­man­tics out of it for free (Mag­ic!). I chose it here, be­cause it elim­i­nates all the boiler-plate for copy­/­move con­struc­tion/as­sign­ment.

A working ex­ample of the code is avail­able here.

Mul­tiple Con­cepts

The problem arises when we want to merge two ex­isting in­ter­faces. For ex­am­ple, sup­pose there is a second con­cept: A door-opener, short Opener. I.e. a thing that opens doors. In some places of our code an Opener will be suf­fi­cient, in some other places we only need a Greeter, but in some places we need to first open the door for someone and then greet them:

void open_door_and_greet_john(const OpenerAndGreeter &g) {
    g.open();
    g.greet("John");
}

How do we create OpenerAndGreeter? Well, we can just create a whole new class for it and copy-paste the Opener, and Greeter parts into it. Like so:

class OpenerAndGreeter {
  public:
    template <class T>
    OpenerAndGreeter(T data) : self_(std::make_shared<Model<T>>(data)) {}

    void open() const { self_->open(); }
    void greet(const std::string &name) const { self_->greet(name); }

  private:
    struct Concept {
        virtual ~Concept() = default;
        virtual void open() const = 0;
        virtual void greet(const std::string &) const = 0;
    };
    template <class T>
    class Model : public Concept {
      public:
        Model(T data) : data_(data) {}
        virtual void open() const override { data_.open(); }
        virtual void greet(const std::string &name) const override {
            data_.greet(name);
        }

      private:
        T data_;
    };

    std::shared_ptr<const Concept> self_;
};

But this is not ideal. It would be much better if we could take an ex­isting Greeter con­cept, and an ex­isting Opener con­cept, and just merge the two to­gether.

A working ex­ample of the code is avail­able here.

Dis­secting Type-Era­sure

Be­fore we get there we need to un­der­stand what our type-era­sure class ac­tu­ally does. So let’s take the Greeter apart.

First, it de­fines an ab­stract base class Con­cept. This is very spe­cific to the Greeter. But, it has nothing to do with type-era­sure. So, we pull it out.

// Defines the concept of a Greeter.
struct Concept {
    virtual ~Concept() = default;
    virtual void greet(const std::string &name) const = 0;
};

Sec­ond, there is the model of that con­cept. This ac­tu­ally does two things: It holds an ar­bi­trary value, and it passes the con­cept’s in­ter­face through to that value. So, let’s sep­a­rate them.

// Holds a value of arbitrary type.
template <class T>
class Holder {
  public:
    Holder(T obj) : data_(std::move(obj)) {}
    virtual ~Holder() = default;
    const T &get() const { return data_; }

  private:
    T data_;
};

// Passes the Concept's interface through to the held value.
template <class Holder>
struct Model : public Holder, public Concept {
    using Holder::Holder;  // pull in holder's constructor
    virtual void greet(const std::string &name) const override {
        this->Holder::get().greet(name);
    }
};

Next, Greeter is also a con­tainer that refers to a con­cept, and ini­tial­izes it with a model. This is very spe­cific to type-era­sure, but has nothing to do with greeting peo­ple.

template <class Concept, template <class> class Model>
class Container {
  public:
    template <class T>
    Container(T obj)
        : self_(std::make_shared<Model<Holder<T>>>(std::move(obj))) {};

    const Concept &get() const { return *self_.get(); }

  private:
    std::shared_ptr<const Concept> self_;
};

And after all this hacking and slashing there is only one bit left. Namely, the ex­ternal in­ter­face that passes calls through to the con­tainer.

template <class Container>
struct ExternalInterface : public Container {
    using Container::Container;  // pull in container's constructor
    void greet(const std::string &name) const {
        this->Container::get().greet(name);
    }
};

Great! We started out with a per­fectly well func­tioning class and took it apart into tiny pieces. Now we need to re­assemble them and make sure that it still works. But don’t for­get, the goal of this ex­er­cise is to make con­cepts merge­able — au­to­mat­i­cally. Hence, we need an au­to­mated way to as­semble all the pieces that we cre­ated. So, it’s time for some tem­plate magic.

Au­to­mated Type-Era­sure

Above pieces fall into two cat­e­gories: One, there are pieces that de­fine the Greeter’s in­ter­face, and two, there are pieces which de­fine how to hold and call ob­jects of ar­bi­trary types. On the holding and calling side we find Holder, and Container, which are im­ple­men­ta­tion de­tails of our type-era­sure con­tainer; whereas Concept, Model, and ExternalInterface are de­tails of a Greeter. To keep things in order we will col­lect the Greeter parts in a super type that we call GreeterSpec.

At this stage we can write a tem­plate class that as­sem­bles all these pieces to­gether and con­structs a type-era­sure con­tainer for an ar­bi­trary spec. It will take the spec’s ExternalInterface tem­plate, and in­stan­tiate it with a con­tainer for the spec’s con­cept, and model. It will also pull in the base-classes con­struc­tor, so that we can still con­struct it from ob­jects of ar­bi­trary types.

template <class Spec>
struct TypeErasure
    : public Spec::ExternalInterface<Container<Spec::Concept, Spec::Model>> {
    using Base =
        Spec::ExternalInterface<Container<Spec::Concept, Spec::Model>>;
    using Base::Base;
};

using Greeter = TypeErasure<GreeterSpec>;

As the last line demon­strates, the Greeter it­self is nothing but a Type­Era­sure of a cer­tain spec.

Again, a working ex­ample of the code is avail­able here.

Merging Con­cepts

Now, with all that ma­chinery backing us, we can tackle the orig­inal prob­lem: How to merge two con­cepts? We have a tool that cre­ates a type-era­sure class out of an ar­bi­trary spec. And, we as­sume that we al­ready have a GreeterSpec, and an OpenerSpec that de­fine those two con­cepts. What we need is a tool to au­to­mat­i­cally merge two specs into one. Let’s ap­proach this com­po­nent by com­po­nent.

How do we merge Concept classes, i.e. in­ter­faces? In C++ we do this by mul­tiple in­her­i­tance:

struct Concept : public virtual ConceptA, public virtual ConceptB {};

How about the Mod­els? The model is a tem­plate class that takes a holder as a tem­plate pa­ra­meter and then in­herits from said holder, thus be­coming a holder it­self. So, we can take SpecB, and the holder, and merge them into one class. This new class will it­self be a holder. Next, we take SpecA, and that new holder, and merge them to get our final merged Model. There is one nifty de­tail, though: We need to use vir­tual in­her­i­tance for the con­cepts. The reason is that ConceptA, and ConceptB will enter the merged Model through the merged Concept, but also through the models of the two specs.

template <class Holder>
struct Model : public SpecA::Model<SpecB::Model<Holder>>,
               public virtual Concept { /* ... */ };

The ex­ternal in­ter­faces are merged the same way, just without the con­cepts:

template <class Container>
struct ExternalInterface
    : public SpecA::ExternalInterface<SpecB::ExternalInterface<Container>> {
    /* ... */
};

Fi­nally, to con­struct a merged spec we take all the above items and wrap them in a tem­plate class, that takes two specs:

template <class SpecA, class SpecB>
struct MergeSpecs {
    /* ... */
};

With this it is trivial to create a type-era­sure that merges two con­cepts:

using OpenerAndGreeter = TypeErasure<MergeSpecs<OpenerSpec, GreeterSpec>>;

And with just a little bit more of tem­plate magic it is even pos­sible to merge two ex­isting type-era­sure classes. So, with all the above we write the fol­lowing code:

using Opener = TypeErasure<OpenerSpec>;
using Greeter = TypeErasure<GreeterSpec>;
using OpenerAndGreeter = MergeConcepts<Opener, Greeter>;

Done!

And this last code ex­ample is avail­able here.

Con­clu­sion & Out­look

We find that it is in­deed pos­sible to merge two ex­isting type-era­sure classes into one that has a common in­ter­face. And what’s more, we can do it fully au­to­mat­i­cally and in just one line of code. The costly bit is to de­fine the orig­inal type-era­sure classes. For each one we need to de­fine a spec class, and man­u­ally de­fine the in­ter­face. The reason is that C++ does not sup­port in­tro­spec­tion. On the other hand, these specs follow a fairly strict scheme and it should be quite pos­sible to pro­duce them through tool­ing, or pos­sibly even a macro.

An­other pos­sible issue is the in­her­i­tance pat­tern for Model, and ExternalInterface. Due to the chaining of base classes we in­tro­duce user spec­i­fied names into the classes Holder, and Container. The method get could be shad­owed by a user method. The li­brary code does ac­tu­ally con­tain more tem­plate magic to avoid this prob­lem. A tem­plate meta-func­tion peels layers of de­rived classes off until it ar­rives at the ac­tual Holder, or Container class. An ex­ternal getter func­tion is pro­vided for the user, which makes sure to call the cor­rect getter method. An ob­scured name of the in­ternal getter method pro­vides fur­ther pro­tec­tion.

The full code is avail­able here. Please feel in­vited to try it out and give me your feed­back. Also, since this is my first blog post, any crit­i­cism is very wel­come.

Thanks for read­ing!

Com­ments

Un­for­tu­nately, I have not yet fig­ured out how to add com­ments to github pages. For the mo­ment I would like to defer any dis­cus­sion to Reddit. I apol­o­gize for the in­con­ve­nience.