Dynamic and Static Polymorphism

Preface

In SeqAn algorithms are implemented in a generic way so that they work on different types so long as these fulfill certain requirements. Additionally there are specialized versions of algorithms that can make use of certain features when available, but can default to more generic versions when not. This is often understood as specialization, and the addressing of different types through common interfaces is referred to as polymorphism.

There are different ways of modelling this behaviour, in SeqAn3 we use C++ Concepts to both model interface constraints and also describe common properties of different types. Concepts enable static polymorphism, i.e. the most constrained version of an algorithm (modelling the strongest specialization) is chosen at compile time. OTOH the design pattern most often used in C++, virtual inheritance, does this at run-time so it is slower.

Static polymorphism

Example

This is a small example program, try to figure it out:

template <typename type>
concept bool is_animal = requires (type value)
{
    value.move();
};

template <typename type>
concept bool is_dangerous_animal = requires (type value)
{
    requires is_animal<type>;

    value.bite();
};


struct turtle
{
    void move()
    {}
};

struct wolf
{
    void move()
    {}

    void bite()
    {}
};

template <typename animal_type>
    requires is_animal<animal_type>
void scare(animal_type & animal)
{
    animal.move();
}

template <typename animal_type>
    requires is_dangerous_animal<animal_type>
void scare(animal_type & animal)
{
    animal.bite();
}

int main()
{
    turtle t;
    wolf w;

    // scaring turtle has no consequences for you
    scare(t);

    // scaring wolf gets you the darwin award
    scare(w);
}

• we define two animals: turtle and wolf
  • note that these are distinct and totally independent types, they don't inherit from anything and they don't specialize a common template
  • you may still do either (to save writing some code), but it is orthogonal to the matter of specialization
• we define two concepts: is_animal and is_dangerous_animal
  • the first concept is a subset of the other so the second is regarded as "more constrained"
  • the concepts describe the requirements for types, but the types themselves have no "knowledge" of the concepts
• we define an algorithm scare that works on all animals, but has special consequences for some
• the degree of specialization (choice of function) happens at compile time
• see C++ Concepts for more details

General notes

When you model an algorithm as a free function it is likely that it has some requirements on the input. Either because it requires certain interfaces from it's type, or because it expects certain behaviour (an operation taking constant time to complete for example).

Check whether there are concepts that model these requirements, and if yes, apply them to your template arguments as requirements. If you can provide specialized (faster?) implementations of your algorithm, e.g. for random access ranges in addition to regular forward ranges, do so.

If there are not yet concepts that model these requirement, create your own.

Dynamic Polymorphism

In some cases you need to decide at run-time between two type interfaces. In SeqAn3 we use tag-dispatching to implement this behaviour. With the help of std::variant and std::visit this is quite easy.

Example

struct caterpillar_state
{
    void eat()
    {
        // eat leaves
    }
};

struct butterfly_state
{
    void eat()
    {
        // eat pollen
    }
};

struct aglais_urticae
{
    // start off as caterpillar
    std::variant<caterpillar_state, butterfly_state> state{caterpillar_state{}};

    void morph()
    {
        if (state.index == 0)
            state = butterfly_state{};
    }

    void eat()
    {
        // delegate to state's eat()
        std::visit([] (auto & s) { s.eat(); }, state);
    }
};

TODO describe