What Are C++ Run-Time Concepts?

Question

I've been looking around on the web for details on C++ concepts lately and have found several references to what several papers call 'run-time concepts.' How exactly do they differ from compile-time concepts, why were they introduced in the first place, how will they be implemented, and why are they important for the future of C++? From glancing at the papers, I get the general idea that run-time concepts are intended to alleviate the current tension that currently exists between object-oriented and generic code, but I don't get much else out of them.

Answer 1

This is my understanding of what is going on. It starts from a different angle: type erasure.

std::function<void()> is an example of a type-erasure class. It takes the concepts of "invocation with no arguments, and returning nothing", together with the helper concepts of "copy construct" and "destroy", and wraps it into a neat little package.

So you can do

void groot () { std::cout << "I am groot!\n"; }
std::function<void()> f = groot;
f();

and groot is invoked. Or we can pass a lambda, or a function object, or a std::bind expression, or a boost::function to a std::function and invoke it.

All of those types can be copied, destroyed and invoked: so std::function can consume them and produce a single run-time interface. Other than the operations that they support, the types that std::function can store and execute are unrelated. There is no class hierarchy that relates the function groot to a lambda, or to boost::function.

The constructor of std::function<void()> that takes things that aren't std::functions type-erases its argument under the concepts of copy, destroy and invoke with signature void().

We start with this:

template<class Sig>
struct func_type_eraser;

template<class R, class... Args>
struct func_type_eraser<R(Args...)> {
  // invoke:
  virtual R operator()(Args...) const = 0;
  // copy:
  virtual func_type_eraser* clone() const = 0;
  // destroy:
  virtual ~func_type_eraser() {};
};
template<class Sig, class T>
struct func_type_eraser_impl; // TODO!

Here we have the 3 concepts of copy, destroy and invoke, each represented as a pure-virtual function.

template<class Sig>
struct function;
template<class R, class... Args>
struct function<R(Args...)> {
  std::unique_ptr<func_type_eraser<R(Args...)>> pImpl;
  // invoke:
  R operator()( Args... args ) const {
    return (*pImpl)( std::forward<Args>(args)... );
  }
  // destroy:
  ~function() = default;
  // copy:
  function(function const& o) : pImpl( o.pImpl ? o.pImpl->clone() : nullptr ) {}
  // move:
  function(function&&) = default;
  // TODO: operator=

  // technical issues, ignore:
  function(function& o) : function(const_cast<function const&>(o)) {}
  function(function const&& o) : function(o) {}

  // type erase:
  template<class T>
  function(T&& t) : pImpl( new func_type_eraser_impl<R(Args...), std::decay_t<T>>{std::forward<T>(t)} )
  {}
};

Here, we wrap the concepts up we want to support into what is known as a Regular type -- a value-type type. We have an underlying pointer and virtual hierarchy (a small one, as yet unseen), but the type function looks just like an int -- you can copy, assign, etc it.

Each of the concepts -- invoke, copy, move, destroy -- is forwarded to the pImpl (except move, which we can implement efficiently at this layer).

Only half of the type erasure work is done here. This part lets us assign anything to our function class instances. We can do a bit better by testing that T passes the concept requirements -- that it can be copied, destroyed, and invoked with the required signature -- before admitting it to our constructor. (The current C++ std::function fails to do this, to much annoyance).

The last part of the type erasure is…:

template<class R, class... Args, class T>
struct func_type_eraser_impl<R(Args...), T> : func_type_eraser<R(Args...)> {
  // type erase storage:
  T t;
  // invoke:
  virtual R operator()(Args... args) const override {
    return t( std::forward<Args>(args)... );
  }
  // copy:
  virtual func_type_eraser_impl* clone() const override {
    return new func_type_eraser_impl{t};
  }
  // destroy:
  virtual ~func_type_eraser_impl() {}
};

…where we implement the concept interfaces exposed in func_type_eraser for a particular type T.

Now we have 4 concepts, 3 of which are type erased, and one handled by our regular type wrapper, and we can store anything that supports those 3 concepts.

We can go a step further:

We can even support anything that the client can supply functions to support those concepts.

The easiest way of doing this is to invoke a free function, like std::begin, in a context that allows for ADL (argument dependent lookup).

Have our type erasure implementation that instead of directly interacting with the object, instead invokes the free function in the ADL context.

Provide a default implementation of that function that does anything from "fails" to "checks for a method .begin() and invokes it" or "does an inefficient version" or "examines the properties of the type passed, and determines a reasonable way to do the task".

With this technique, we can allow clients to extend our type erasure, and use broader concepts.

As a concrete example, imagine we had the concept printable. Something is printable if it has ostream << X overloaded, or if it has print(X) overloaded.

We add print_it to our type erasure interface. It using impl_namespace::print, then does a print(t).

impl_namespace::print(X) simply does a cout << X.

This is all decoupled. You can take a type that someone else wrote with no concept of printing, add the print concept via a free function in its namespace, and then pass it to our type erasure system and the type erasure system hooks it up.

See this channel 9 video for an example of someone using similar techniques to build a toy document with infinite undo and display that can be extended to an arbitrary number of types, including built-in types.

Now, imagine language support for this. Being able to describe a set of concepts you want to type erase, and say "build a Regular type that erases these types".

If you have an algorithm that is supported by said other concepts, you could then say "type erase support for this algorithm". Any clients that are aware of the algorithm type erasure and they have better support for it can automatically have a custom-created one added to your interface. Those that don't can use the type erased concepts you provided to implement it.

At the point of type erasure, where your concepts are being taken from understood at compile time to virtual and run time, the type-erasure support for your algorithm can be very efficient, even if the support for concepts on your type was concept-map based (ie, custom functions where provided to solve the problems. Your type is not naively copyable, but there is a clone function that copies it to suitable storage, say). The algorithm concept type-erasure can take into account the full compile time concept mapping instead of the runtime virtual concept mapping, giving performance gains even if there isn't a fundamentally faster algorithm.

If done with extreme care, you can take a type erasure object with fewer concepts and extend it to one with more concepts if the new concepts are supported by the fewer concepts. Clients who "did not know" you wanted a fast binary search (say) would end up supporting it from their run-time interface: those that did would provide you with a fast binary search customized for your type.

Taking another step, you could have optional concept support in your type erasure class. As an example, a type erased iterator might optionally support random access iteration. Algorithms that accept iterators might test for random access iteration, and if so create a better implementation. The concept of binary searching on a range might check if the range has binary search concept support, and if not if it has random access support, and failing that use foward iterator version of binary search (O(n) advances, O(lg(n)) comparisons). In each case it could use the "more specialized" implementation.

All of this parallels how concepts work at compile time. Except, it occurs at run time, and has that extra type erasure system.