[boost] [Interest] Value Dispatch

15 Aug 2012

      Hi all,

This might be old hat to verteran boosters but I found it nifty.  Maybe
it could make a small addition to Boost.

Inspired by Sean Parent's C++Now! talk and the various articles on
cpp-next, I've been playing around with value semantics and C++11.

I found an interesting use of pack expansion at stackoverflow and
expanded on it in a local project to convert from a traditional
inheritance/virtual function model to a more value-centered approach.

It turns out that with pack expansion one can implement "virtual
functions" without needing inheritance or pointer/reference semantics.
One can consider a vrtual function as "just" a compiler-generated switch
statement.  With that in mind, here's an example:

-----------

#include <iostream>

/// This is a collection of node kinds.  We use it to categorize
/// various kinds of objects and dispatch to the correct routine.
template<typename T, typename T::kind ...I>
class kind_tuple {};

/// This is the "virtual function" dispatch mechanism.  It
/// statically generates a lookup table of routines, one for each
/// kind.
template<typename R, typename D, typename T>
class dispatcher {};

/// This is the actual dispatch implementation.
template<typename R, typename D, typename O, typename O::kind ...I>
class dispatcher<R, D, kind_tuple<O, I...>> {
 private:
  // Call the "virtual function override" via the provided class-level
  // dispatcher.
  template<typename P, typename O::kind K, typename ...Args>
    static R dispatch_handler(P payload, Args ...args) {
    return D::template dispatch<K>(payload, args...);
  }

 public:
  // dispatcher is an object that knows which routine in N to call.
  template<typename P, typename ...Args>
    static R dispatch(P payload, typename O::kind kind, Args ...args) {
    using F = R(P, Args...);

    F *table[] = {
      dispatch_handler<P, I, Args...>
      ...
    };

    return table[kind](payload, args...);
  }
};

class vehicle {
public:
  enum kind {
    Car,
    Bus,
    Boat,
    Train,
    Airplane
  };

  typedef kind_tuple<vehicle,
                     kind::Car, kind::Bus, kind::Boat, kind::Train,
                     kind::Airplane> kinds;

private:
  class drive_dispatcher {
  public:
    template<kind K>
    static void dispatch(vehicle v) {
      v.drive_impl<K>();
    }
  };

  class turn_dispatcher {
  public:
    template<kind K>
    static bool dispatch(vehicle v, std::string direction) {
      return v.turn_impl<K>(direction);
    }
  };

  template<kind K>
  void drive_impl(void) {}

  template<kind K>
  bool turn_impl(std::string direction) {
    return false;
  }

  kind the_kind;

public:
  vehicle(kind k) : the_kind(k) {}

  void drive(void) {
    dispatcher<void, drive_dispatcher, kinds>::dispatch(*this, this->the_kind);
  }

  // Return whether the turn was successfully completed.
  bool turn(std::string direction) {
    return dispatcher<bool, turn_dispatcher, kinds>::
      dispatch(*this, this->the_kind, direction);
  }
};

template<>
void vehicle::drive_impl<vehicle::Car>(void)
{
  std::cout << "Driving a car!\n";
}

template<>
void vehicle::drive_impl<vehicle::Bus>(void) 
{
  std::cout << "Driving a bus!\n";
}

template<>
void vehicle::drive_impl<vehicle::Boat>(void) 
{
  std::cout << "Driving a boat!\n";
}

template<>
void vehicle::drive_impl<vehicle::Train>(void) 
{
  std::cout << "Driving a train!\n";
}

template<>
void vehicle::drive_impl<vehicle::Airplane>(void) 
{
  std::cout << "Flying an airplane!\n";
}

template<>
bool vehicle::turn_impl<vehicle::Car>(std::string direction)
{
  std::cout << "Turning a car " << direction << "!\n";
  return true;
}

template<>
bool vehicle::turn_impl<vehicle::Bus>(std::string direction)
{
  std::cout << "Turning a bus " << direction << "!\n";
  return true;
}

template<>
bool vehicle::turn_impl<vehicle::Boat>(std::string direction)
{
  std::cout << "Turning a boat " << direction << "!\n";
  return true;
}

template<>
bool vehicle::turn_impl<vehicle::Train>(std::string direction)
{
  std::cout << "Turning a train " << direction << "?!?\n";
  return false;
}

template<>
bool vehicle::turn_impl<vehicle::Airplane>(std::string direction)
{
  std::cout << "Turning an airplane " << direction << "!\n";
  return true;
}

template<typename Iterator>
void drive(Iterator start, Iterator end)
{
  for (auto i = start; i != end; ++i)
    i->drive();
}

template<typename Iterator>
void turn(Iterator start, Iterator end, std::string direction)
{
  for (auto i = start; i != end; ++i)
    if (i->turn(direction)) {
        std::cout << "Successfully turned " << direction << "\n";
    }
    else {
        std::cout << "Could not turn " << direction << "\n";
    }
}

int main(void)
{
  vehicle rides[] = {
    vehicle(vehicle::kind::Car),
    vehicle(vehicle::kind::Bus),
    vehicle(vehicle::kind::Boat),
    vehicle(vehicle::kind::Train),
    vehicle(vehicle::kind::Airplane)
  };

  drive(rides, rides + 5);

  std::cout << "\n";

  turn(rides, rides + 5, "left");

  return 0;
}

-----------

The central idea is the creating of a "virtual function table" via pack
expansion.  Not only can we keep value semantics and avoid coupling via
inheritance, we also get virtual function-like behavior for template
functions.

Expanding the idea allows us to implement a completely generic GoF
visitor without using inheritance at all:

-----------

#include <iostream>
#include <tuple>

/// This is a collection of node kinds.  We use it to categorize
/// various kinds of objects and dispatch to the correct routine.
template<typename T, typename T::kind ...I>
class kind_tuple {};

/// This is the "virtual function" dispatch mechanism.  It
/// statically generates a lookup table of routines, one for each
/// kind.
template<typename R, typename D, typename T>
class dispatcher {};

/// This is the actual dispatch implementation.
template<typename R, typename D, typename O, typename O::kind ...I>
class dispatcher<R, D, kind_tuple<O, I...>> {
 private:
  // Call the "virtual function override" via the provided class-level
  // dispatcher.
  template<typename P, typename O::kind K, typename ...Args>
    static R dispatch_handler(P payload, Args ...args) {
    return D::template dispatch<K>(payload, args...);
  }

 public:
  // dispatcher is an object that knows which routine in N to call.
  template<typename P, typename ...Args>
    static R dispatch(P payload, typename O::kind kind, Args ...args) {
    using F = R(P, Args...);

    F *table[] = {
      dispatch_handler<P, I, Args...>
      ...
    };

    return table[kind](payload, args...);
  }
};

class vehicle {
public:
  enum kind {
    Car,
    Bus,
    Boat,
    Train,
    Airplane
  };

  typedef kind_tuple<vehicle,
                     kind::Car, kind::Bus, kind::Boat, kind::Train,
                     kind::Airplane> kinds;

private:
  kind the_kind;

public:
  vehicle(kind k) : the_kind(k) {}

  kind get_kind(void) const {
    return the_kind;
  }
};

// U is to distinguish among different kinds of visitors for the same
// object type.
template<typename O, typename U, typename R, typename ...Args>
class visitor {
private:
  typedef visitor<O, U, R, Args...> This;

  // This dispatcher expects a single object so wrap the visitor and
  // the visited object together.
  typedef std::tuple<This *, O> payload;

  class visit_dispatcher {
  public:
    template<typename O::kind K>
    static R dispatch(payload object, Args ...args) {
      return std::get<0>(object)->
        template visit_impl<K>(std::get<1>(object), args...);
    }
  };

  template<typename O::kind K>
  R visit_impl(O object, Args ...args) {}

public:
  R visit(O object, Args ...args) {
    return dispatcher<R, visit_dispatcher, typename O::kinds>::
      dispatch(std::make_tuple(this, object), object.get_kind(), args...);
  }
};

// Visitor types
class Driving {};
class Turning {};

template<>
template<>
void visitor<vehicle, Driving, void>::visit_impl<vehicle::Car>(vehicle v)
{
  std::cout << "Driving a car!\n";
}

template<>
template<>
void visitor<vehicle, Driving, void>::visit_impl<vehicle::Bus>(vehicle v)
{
  std::cout << "Driving a bus!\n";
}

template<>
template<>
void visitor<vehicle, Driving, void>::visit_impl<vehicle::Boat>(vehicle v)
{
  std::cout << "Driving a boat!\n";
}

template<>
template<>
void visitor<vehicle, Driving, void>::visit_impl<vehicle::Train>(vehicle v)
{
  std::cout << "Driving a train!\n";
}

template<>
template<>
void visitor<vehicle, Driving, void>::visit_impl<vehicle::Airplane>(vehicle v)
{
  std::cout << "Flying an airplane!\n";
}

template<>
template<>
bool visitor<vehicle, Turning, bool, std::string>::
visit_impl<vehicle::Car>(vehicle v, std::string direction)
{
  std::cout << "Turning a car " << direction << "!\n";
  return true;
}

template<>
template<>
bool visitor<vehicle, Turning, bool, std::string>::
visit_impl<vehicle::Bus>(vehicle v, std::string direction)
{
  std::cout << "Turning a bus " << direction << "!\n";
  return true;
}

template<>
template<>
bool visitor<vehicle, Turning, bool, std::string>::
visit_impl<vehicle::Boat>(vehicle v, std::string direction)
{
  std::cout << "Turning a boat " << direction << "!\n";
  return true;
}

template<>
template<>
bool visitor<vehicle, Turning, bool, std::string>::
visit_impl<vehicle::Train>(vehicle v, std::string direction)
{
  std::cout << "Turning a train " << direction << "?!?\n";
  return false;
}

template<>
template<>
bool visitor<vehicle, Turning, bool, std::string>::
visit_impl<vehicle::Airplane>(vehicle v, std::string direction)
{
  std::cout << "Turning an airplane " << direction << "!\n";
  return true;
}

template<typename Iterator>
void drive(Iterator start, Iterator end)
{
  visitor<vehicle, Driving, void> driver;

  for (auto i = start; i != end; ++i)
    driver.visit(*i);
}

template<typename Iterator>
void turn(Iterator start, Iterator end, std::string direction)
{
  visitor<vehicle, Turning, bool, std::string> turer;

  for (auto i = start; i != end; ++i)
    if (turer.visit(*i, direction)) {
        std::cout << "Successfully turned " << direction << "\n";
    }
    else {
        std::cout << "Could not turn " << direction << "\n";
    }
}

int main(void)
{
  vehicle rides[] = {
    vehicle(vehicle::kind::Car),
    vehicle(vehicle::kind::Bus),
    vehicle(vehicle::kind::Boat),
    vehicle(vehicle::kind::Train),
    vehicle(vehicle::kind::Airplane)
  };

  drive(rides, rides + 5);

  std::cout << "\n";

  turn(rides, rides + 5, "left");

  return 0;
}

-----------

Not only is inheritance not required, we only need single dispatch to
implement the visitor.

Because we don't use inheritance at all for these "virtual functions"
and the above visitor we can maintain value semantics throughout any
code that uses the above techniques.

Of course the code above can be cleaned up and beautified.  It's just a
quick proof-of-concept.

I'm sure someone has already posted about this technique somewhere.  Is
there any interest in expanding it into a Boost library?

                          -Dave

[boost] [Interest] Value Dispatch

*smgreened＠obbligato.org