Tag Dispatching by Type

Tag Dispatching (TD) is a Generic Programming (GP) technique for C++. It is well explained in this blog. Google Hit Number one (GH#1) is this site, where the example of the STL function advance is given. Tag Dispatching is not described a lot; GH#7 is from ggl (= Boost.Geometry), as is GH#8..

Nearly all TD descriptions I know of use the example of STL-advance. But in Boost.Geometry TD is done in another way: not by instance, but by type. The difference is explained in this blog.

Suppose you make a generic program doing something with fruit. An apple is normally being eaten differently than a banana or an orange. So if we program a generic function eat, giving it any type of fruit, it should redirect this to an implementation specific to that kind of fruit, so for apple differently than for a banana.

We first implement the tags. Tags are completely empty structures. But (of course) not completely useless.

struct apple_tag {};
struct banana_tag {};
struct orange_tag {};

We then create some sample implementations. Most properties are not used, it is just to show there are (sometimes completely) different classes which can be handled genericly.

struct apple
{
    double radius;

    std::string name;
    apple(std::string const& n) : name(n) {}
};

struct banana
{
    double length;

    std::string name;
    banana(std::string const& n) : name(n) {}
};

All this is quite simple C++ code, though you have to understand templates (generics) and specialization.

OK, now we implement Tag Dispatching by Instance:

namespace dispatch
{
    void eat(apple const& a, apple_tag)
    {
        std::cout << "bite" << std::endl;
    }

    void eat(banana const& b, banana_tag)
    {
        std::cout << "peel" << std::endl;
    }
}

template <typename T>
void eat(T const& fruit)
{
    typename tag<T>::type the_tag;
    dispatch::eat(fruit, the_tag);
}

The function eat at the bottom first declares an instance of the tag. If an apple is entered in this function, it will be an instance of the apple_tag. If a banana is entered, it is a banana_tag. Then it forwards its call to the eat function in the namespace dispatch. There are two versions (overloads) there, one specified with an apple_tag, one with a banana_tag. The compiler selects, based on the tag the right function. Quite easy, and quite powerful, this tag dispatching system.

As said, within Boost.Geometry it is not applied like this. One of the reasons is that the instance of the tag is not necessary at all. If the dispatch::eat function would be implemented within a struct, as a static method, the tag dispatching can be done by type and not by instance. This is still tag dispatching!

So the piece above can be replaced by this Tag Dispatching by Type:

namespace dispatch
{
    template <typename Tag> struct eat {};

    template <> struct eat<apple_tag>
    {
        static void apply(apple const& a)
        {
          std::cout << "bite" << std::endl;
        }
    };

    template <> struct eat<banana_tag>
    {
        static void apply(banana const& b)
        {
          std::cout << "peel" << std::endl;
        }
    };
}

template <typename T>
void eat(T const& fruit)
{
    dispatch::eat<typename tag<T>::type>::apply(fruit);
}

So no instance at all, type only. Boost.Geometry has this structure everywhere, and all static dispatching methods are called apply.

For completeness we list the main program as well here:

int main()
{
    apple a("my apple");
    banana b("my banana");
    eat(a);
    eat(b);

    return 0;
}

It is the same for the instance-version and the type-version.

More advantages of the Tag Dispatching by Type approach are that arguments can be reversed, so you can call distance(point, polygon) and distance(polygon, point) but there is only one implementation with point_tag, polygon_tag necessary. With instances (and function overloads) this is not possible, or at least not that easy. Furthermore, tag dispatching by type can be used to define types, or define constants, as well. Suppose you need to define a constant value dependant on a type. We approach geometry now and want to define if a specific fruit-type is spherical or not. So we define this structure, specialized by tag:

    template <typename Tag> struct spherical {};

    template <> struct spherical<apple_tag>
    {
        static const bool value = true;
    };

    template <> struct spherical<banana_tag>
    {
        static const bool value = false;
    };

We can create a generic structure, which calls this dispatch, just like the free function eat, but now with a struct (or meta-function):

template <typename T>
struct spherical
{
    static const bool value = dispatch::spherical<typename tag<T>::type>::value;
};

Next blog will handle Tag Dispatching and Inheritance.