Integrated run-time concepts for c++0x
Hello. First of all, this idea is based on these papers:
http://www.emarcus.org/papers/MPOOL2007-marcus.pdf
http://www.emarcus.org/papers/oops2008-marcus.pdf
I want to explain an idea which would be a great feature to have in
the next standard. There is an idea to be able to use concepts at
runtime in the papers above. The solution is to create a library which
generates the runtime-concept of a c++0x concept. I think it would be
desirable to have a mechanism to instantiate a run-time concept once
you have a c++0x concept automatically by the compiler.
My thoughts until now are these. (There is an example for better
understanding). This code won't compile. It's just an example of the
idea. I'll try to explain the idea first, and then you can see the
code below.
With C++0x you can have concept checking for algorithms. These
requirements are expressed with documentation in C++98. In C++0x you
can express these requirements directly in the compiler with concepts.
The problem (and a good thing too, for the sake of performance and
compile-time checking) is that you can express them, but it would be
great to have a class which can hold objects that the concept
describes. For example (simplified for the explanation):
concept Forward_Iterator<typename T> {
//...
}
There are sometimes (many times, in fact, where it is desirable to be
able to do this:
// l is a list and v is a vector
forward_iterator it = l.begin();
forward_iterator it2 = v.begin();
We could store all iterators in a container, without knowing if the
iterators are bidirectional or random or whatever, as long as they are
concepts of Forward_Iterator.
This can be done with a library called the poly library (from adobe).
But the problem is that it is just too difficult to use, and I think
that this could be better handled by the compiler, since the compiler
knows which code to generate once it knows the concept. It would be a
great idea to be able to do something in the lines of:
runtime_concept<std::Forward_Iterator> forward_iterator;
This would generate something similar to what the poly library
generates for runtime-concepts. But in the poly library you have to
provide a lot of boiler-plate code per-concept (one model, one
interface and one runtime-concept) (the code below shows a partial
implementation of what the compiler would do.
The compiler also knows if the concept is a refinement of another
concept. If the concept is a refinement of another concept, the
compiler would generate code for the base concepts and later for the
refinement classes. And the base classes representing the interface
run-time concept would be inherited too. I don't know very well how
this is achieved, since I didn't try, but the information from the
concepts is there. So you could also do this:
concept Bidirectional_Iterator<typename Iter> : Forward_Iterator<Iter>
{ ... }
template <class T>
runtime_concept<Bidirectional_Iterator<T>> bidirectional_iterator;
Another problem that remains is how to call the most efficient
implementation when this happens:
forward_iterator viterator = v.begin();
//viterator is an vector<int>::iterator wrapped in forward_iterator,
so, for example, advance should call O(1) advance function, although
viterator is wrapped inside a forward_iterator, which will call
advance for concept Forward_Iterator.
There would be a need to handle multiple inheritance when a concept
refines more than one concept and a there is a desire to make a run-
time concept.
Sorry if the explanation is not too accurate and the same for the code
(I have very little time). This is just an idea to illustrate a
feature I wish could be introduced in one way or another.
The code for an example is here:
namespace std {
concept Forward_Iterator<typename Iter>
{
//advance is O(n)
void advance(Iter &, difference_type);
}
//Refinement
concept Bidirectional_Iterator<typename Iter> : Forward_Iterator<Iter>
{
//advance is O(n) but can advance iterators backwards
//....
}
//More refinement
concept Random_Access_Iterator<typename Iter> :
Bidirectional_Iterator<Iter>
{
//advance is O(1) for Random_Access_Iterators
}
} //end namespace std
//Generating a runtime-concept class
template <typename T>
runtime_concept<Forward_Iterator<T>> forward_iterator;
/***RUN-TIME CONCEPT COMPILER GENERATED CODE ***/
class forward_iterator_iface {
//difference_type is a run-time concept generated elsewhere
virtual void advance(difference_type d) = 0;
//...
};
template <class T>
class forward_iterator_model : public forward_iterator_iface
{
T data_;
public:
//Constructors
//...
void advance(typename T::difference_type d)
{
//This does not have max performance, since T could be a
//Random_Access_Iterator wrapped in a forward_iterator.
//Could be an alternative mechanism to call advance based
//on checking the concept that models T at run-time
Forward_Iterator<T>::advance(data_, d);
}
};
class forward_iterator
{
forward_iterator_iface * object_;
public:
template <Forward_Iterator Iter>
forward_iterator(Iter && it) : object_(new
forward_iterator_model<Iter>(it)) {}
forward_iterator(forward_iterator && it) :
object_(it.object_.clone()) {}
void advance(difference_type d)
{
object_->advance(d);
}
};
//*****END COMPILER GENERATED CODE****//
namespace std
{
forward_iterator advance(forward_iterator & it, difference_type d)
{
it.advance(d);
}
}
int main(int argc, char * argv[])
{
using namespace std;
std::list<int> l = {1, 2, 3, 4, 5, 6, 7, 8, 9};
std::vector<int> v = {1, 2, 3, 4, 5, 6, 7 ,8, 9};
forward_iterator listiter = l.begin();
forward_iterator vectoriter = v.begin();
//O(n)
advance(listiter, 5);
//O(n). Should be O(1) if possible (through some kind of different
dispatch mechanism)
advance(vectoriter, 5);
std::vector<int>::iterator it = v.begin();
//Calls normal std::advance algorithm (the one from the STL) based
on
compile-time information
advance(v, 2);
}
--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]