overloads: request for discussion
An overload set can be represented as a class with _numbered_ call operators: struct has_intersection { bool operator()(id<1>, Circle&, Circle& ) const; bool operator()(id<2>, Circle&, Rectangle&) const; bool operator()(id<3>, Rectangle&, Circle& ) const; bool operator()(id<4>, Rectangle&, Rectangle&) const; }; I wonder how to pass it to different kind of algorithms. Here's my brain dump of the topic: 1. Pass an overload set, MPL sequence of positions and a predicate find_if< has_intersection , range_c<int,1,5> , is_same<first_arg<_>, Circle&> > The find_if algorithm works with mpl sequence of positions, that is, it takes positions and return an iterator to first found position. Unlike mpl::find_if, the predicate takes a signature, not a position. I used it till recently. But it's not quite an OverloadSet concept. 2. MPL-like sequence would be nice to have. Something similar to: mpl::vector< bool(Circle&, Circle& ) , bool(Circle&, Rectangle&) , bool(Rectangle&, Circle& ) , bool(Rectangle&, Rectangle&) > or mpl::set< bool(Circle&, Circle& ) , bool(Circle&, Rectangle&) , bool(Rectangle&, Circle& ) , bool(Rectangle&, Rectangle&) > Unfortunately, if typeof is not available, deref and some other operations work only in deduced context (that is, inside special function). Presumably that sequence should store pairs of id and a signature in deduced context or id and unknown otherwise: pair<id<1>, bool(Circle&,Circle&) > // deduced context pair<id<1>, unknown> // non-deduced context (This reminds me of mpl::map but I'm not sure about keys and values: id -> signature or signature -> id?) Algorithms that accept boolean predicates will be using deduced context (this can be extended to predicates that return integral constants in limited range). Question about whether to implement other algorithms is open. This approach has an advantage on a long run. When typeof becomes standartized, everything can be switched to the first case. To summarize, I see it being as close to MPL sequence (I don't know to which one, though) as possible typedef overload_set<has_intersection, range_c<int,1,5> > seq; but not closer. For example, overload_set is extensible only in a limited way: you can't insert new overload but you can restore an overload removed by previous algorithm or a filter. This means, in particular, that sort should work because it only changes an order of elements. Note that sorting by id or signature is less important then sorting by return or argument type and then applying unique algorithm. At best, sorting of huge overload set can be avoided. MPL has a trick for this: mpl::copy<from, inserter<set<>, insert<_1,_2> > > Something similar can be done for overload_set. Otherwise, new algorithm should be introduced because of its high importance. It has to be very fast at compile-time to deal efficiently with huge overload sets. (This algorithm exists already under name "unique"). 3. Fusion-like interface. Overload sets are not pure compile-time entities as shown in this example: tuple< bool (has_intersection::*)(id<1>, Circle&, Circle& ) const, bool (has_intersection::*)(id<2>, Circle&, Rectangle&) const, bool (has_intersection::*)(id<3>, Rectangle&, Circle& ) const, bool (has_intersection::*)(id<4>, Rectangle&, Rectangle&) const > t( &has_intersection::operator(), &has_intersection::operator(), &has_intersection::operator(), &has_intersection::operator() ); Something like that would be great addition for overloads library. The library is available at cpp-experiment.sf.net (please, use CVS). -- Alexander Nasonov
Alexander Nasonov writes:
An overload set can be represented as a class with _numbered_ call operators:
struct has_intersection { bool operator()(id<1>, Circle&, Circle& ) const; bool operator()(id<2>, Circle&, Rectangle&) const; bool operator()(id<3>, Rectangle&, Circle& ) const; bool operator()(id<4>, Rectangle&, Rectangle&) const; };
I wonder how to pass it to different kind of algorithms. Here's my brain dump of the topic:
1. Pass an overload set, MPL sequence of positions and a predicate
find_if< has_intersection , range_c<int,1,5> , is_same<first_arg<_>, Circle&> >
The find_if algorithm works with mpl sequence of positions, that is, it takes positions and return an iterator to first found position. Unlike mpl::find_if, the predicate takes a signature, not a position.
Can't it be something like mpl::find_if< overload_set<1,5,has_intersection> , is_same<first_arg<_>, Circle&> > ?
I used it till recently. But it's not quite an OverloadSet concept.
2. MPL-like sequence would be nice to have. Something similar to:
mpl::vector< bool(Circle&, Circle& ) , bool(Circle&, Rectangle&) , bool(Rectangle&, Circle& ) , bool(Rectangle&, Rectangle&) >
or
mpl::set< bool(Circle&, Circle& ) , bool(Circle&, Rectangle&) , bool(Rectangle&, Circle& ) , bool(Rectangle&, Rectangle&) >
Unfortunately, if typeof is not available, deref and some other operations work only in deduced context (that is, inside special function).
I'm afraid I don't follow; the above seems perfectly viable to me. Could you provide an example?
Presumably that sequence should store pairs of id and a signature in deduced context or id and unknown otherwise:
pair<id<1>, bool(Circle&,Circle&) > // deduced context pair<id<1>, unknown> // non-deduced context
(This reminds me of mpl::map but I'm not sure about keys and values: id -> signature or signature -> id?)
Algorithms that accept boolean predicates will be using deduced context (this can be extended to predicates that return integral constants in limited range). Question about whether to implement other algorithms is open.
This approach has an advantage on a long run. When typeof becomes standartized, everything can be switched to the first case.
To summarize, I see it being as close to MPL sequence (I don't know to which one, though) as possible
typedef overload_set<has_intersection, range_c<int,1,5> > seq;
but not closer. For example, overload_set is extensible only in a limited way: you can't insert new overload but you can restore an overload removed by previous algorithm or a filter. This means, in particular, that sort should work because it only changes an order of elements. Note that sorting by id or signature is less important then sorting by return or argument type and then applying unique algorithm. At best, sorting of huge overload set can be avoided. MPL has a trick for this:
mpl::copy<from, inserter<set<>, insert<_1,_2> > >
Something similar can be done for overload_set. Otherwise, new algorithm should be introduced because of its high importance. It has to be very fast at compile-time to deal efficiently with huge overload sets. (This algorithm exists already under name "unique").
And we can always specialize it for the overload set sequences.
3. Fusion-like interface. Overload sets are not pure compile-time entities as shown in this example:
tuple< bool (has_intersection::*)(id<1>, Circle&, Circle& ) const, bool (has_intersection::*)(id<2>, Circle&, Rectangle&) const, bool (has_intersection::*)(id<3>, Rectangle&, Circle& ) const, bool (has_intersection::*)(id<4>, Rectangle&, Rectangle&) const > t( &has_intersection::operator(), &has_intersection::operator(), &has_intersection::operator(), &has_intersection::operator() );
Something like that would be great addition for overloads library.
I think Fusion is already capable of building tuples based on the MPL sequences. -- Aleksey Gurtovoy MetaCommunications Engineering
Aleksey Gurtovoy wrote:
Can't it be something like
mpl::find_if< overload_set<1,5,has_intersection> , is_same<first_arg<_>, Circle&> >
?
Well, I could use mpl find_if but it's not the best way (unless mpl::find_if is specialized). 1. The overload_set is a mixture of positions and signatures. You can think of it as of a vector of pointers to sequence elements or, even more closely to problem domain, as a vector of indicies with elements stored in another vector. It's perfectly valid to operate on position level and to "dereference" it in predicate: mpl::find_if< range_c<int,1,5> , test1<has_intersection, first_arg_is_Circle_ref, _1> // this is position ^^ > 2. Without typeof you can't get signature from everywhere and pass it to an algorithm. test1 can do this but the algorithm should operate on position level then. 3. Performance. When number of functions is high everything is important. For example, if all functions have same arity it decrease compilation time significantly. I have to pass a strategy to algorithms. Currently, this example looks like: overloads::find_if< overload_set<has_intersection, mpl::range_c<int,1,5> > , is_same<first_arg<_>, Circle&> > Close to your code but it's not mpl::find_if.
I used it till recently. But it's not quite an OverloadSet concept.
2. MPL-like sequence would be nice to have. Something similar to:
mpl::vector< bool(Circle&, Circle& ) , bool(Circle&, Rectangle&) , bool(Rectangle&, Circle& ) , bool(Rectangle&, Rectangle&) >
or
mpl::set< bool(Circle&, Circle& ) , bool(Circle&, Rectangle&) , bool(Rectangle&, Circle& ) , bool(Rectangle&, Rectangle&) >
Unfortunately, if typeof is not available, deref and some other operations work only in deduced context (that is, inside special function).
I'm afraid I don't follow; the above seems perfectly viable to me. Could you provide an example?
It is viable. But function and metainformation (signature) are stored in different places. It's ok only if you have few functions. What if you have 400? Can mpl::vector or mpl::set contain 400 elements? I'm afraid not. Some overloads library work even on higher numbers (up to 700 on my laptop). 400 is not a random number. Imagine, you have 20 classes in Shape hierarchy. Intersestion of all of them requires 20x20=400 has_intersection functions. BTW, I remember Dave mentioned that you generate FSM using mpl::vectorN, with N higher then default 50. How high is N?
I think Fusion is already capable of building tuples based on the MPL sequences.
1. It's different. In mpl case you use a sequence to generate tuple *type*. In overloads case, it's both types and values. overload_set is more like mpl sequence of integral constants. You can pass it to for_each, for example. 2. The problem is that overload_set is not an MPL sequence. -- Alexander Nasonov
Alexander Nasonov wrote:
Aleksey Gurtovoy wrote:
Can't it be something like
mpl::find_if< overload_set<1,5,has_intersection> , is_same<first_arg<_>, Circle&> >
?
Well, I could use mpl find_if but it's not the best way (unless mpl::find_if is specialized).
Good news, I can use mpl:find_if even though typeof isn't available! This is how I do it: 1. define overload_set_iter class template that takes an overload set and an iterator for current position. (If it was ever possible, deref could return a signature of an overload the iterator refers to). 2. specialize mpl::aux::iter_apply1 for overload_set_iter. Unlike primary template, specialized version doesn't deref overload_set_iter, it dereferences nested position iterator and then pass that position to test1 metafunction. This metafunction tests a predicate passed to iter_apply1 indirectly (that is, by position). This only one local hack I'm able to use mpl::find_if. This is much better then before. Aleksey, if you're interested in tighter integration between mpl and overloads, let me use more hacks legally. I'm not sure it will always be possible not to touch mpl code, but I'll try. PS. I'll check my e-mail tomorrow morning and then I'll check it again only on Tuesday because I'm on vacation. -- Alexander Nasonov
Alexander Nasonov writes:
Good news, I can use mpl:find_if even though typeof isn't available!
This is how I do it:
1. define overload_set_iter class template that takes an overload set and an iterator for current position. (If it was ever possible, deref could return a signature of an overload the iterator refers to).
What if you define a "signature" as an (overload set, index) pair, declare it as a standard way to pass things around (within your library, that is), and make 'overload_set_iter' return that on dereference? Any reason why the approach you outline below is preferable?
2. specialize mpl::aux::iter_apply1 for overload_set_iter. Unlike primary template, specialized version doesn't deref overload_set_iter, it dereferences nested position iterator and then pass that position to test1 metafunction. This metafunction tests a predicate passed to iter_apply1 indirectly (that is, by position).
This only one local hack I'm able to use mpl::find_if. This is much better then before.
Aleksey, if you're interested in tighter integration between mpl and overloads,
Definitely.
let me use more hacks legally. I'm not sure it will always be possible not to touch mpl code, but I'll try.
I'm willing to make the necessary changes once we explore the design space to the extent that would make the need obvious.
PS. I'll check my e-mail tomorrow morning and then I'll check it again only on Tuesday because I'm on vacation.
Sure thing. Have fun, -- Aleksey Gurtovoy MetaCommunications Engineering
Aleksey Gurtovoy writes:
Alexander Nasonov writes:
Good news, I can use mpl:find_if even though typeof isn't available!
This is how I do it:
1. define overload_set_iter class template that takes an overload set and an iterator for current position. (If it was ever possible, deref could return a signature of an overload the iterator refers to).
What if you define a "signature" as an (overload set, index) pair, declare it as a standard way to pass things around (within your library, that is), and make 'overload_set_iter' return that on dereference? Any reason why the approach you outline below is preferable?
Oh, I see it now: specializing 'iter_apply1' allows for intuitively obvious find_if< overloads, is_same<bool(int),_1> > while my suggestion would require something like find_if< overloads , overload_match< _1, is_same<bool(int),_1> > > That's indeed quite appealing. However, specializing 'iter_apply1' this way assumes that it's always invoked on a predicate metafunction, which, at least theoretically, does not hold. On the other hand, with 'typeof', dereferencing 'overload_set_iter' would simply return a corresponding function type and things would "just work" without any special effort on our side, and in that light 'iter_apply1' specialization for the compilers that need it is simply an implementation detail which I'm willing to close my eyes to ;). It's going to be interesting to see how many MPL algorithms can be made to work with overload sequences using this approach. -- Aleksey Gurtovoy MetaCommunications Engineering
Aleksey Gurtovoy wrote:
Oh, I see it now: specializing 'iter_apply1' allows for intuitively obvious
find_if< overloads, is_same<bool(int),_1> >
while my suggestion would require something like
find_if< overloads , overload_match< _1, is_same<bool(int),_1> > >
Exactly!
That's indeed quite appealing. However, specializing 'iter_apply1' this way assumes that it's always invoked on a predicate metafunction, which, at least theoretically, does not hold.
Either predicate or metafunction that returns IntegralConstant constructed from sizeof (possibly shifted).
On the other hand, with 'typeof', dereferencing 'overload_set_iter' would simply return a corresponding function type and things would "just work"
That's true.
... without any special effort on our side, and in that light 'iter_apply1' specialization for the compilers that need it is simply an implementation detail which I'm willing to close my eyes to ;). It's going to be interesting to see how many MPL algorithms can be made to work with overload sequences using this approach.
I've already tried find find_if contains and equal. Here is my plan. For now, we can reimplement mpl algorithms based on predicate using iter_applyN. Later, when typeof becomes common among popular compilers we can switch seamlessly to typeof. -- Alexander Nasonov
Alexander Nasonov writes:
Aleksey Gurtovoy wrote:
Oh, I see it now: specializing 'iter_apply1' allows for intuitively obvious
find_if< overloads, is_same<bool(int),_1> >
while my suggestion would require something like
find_if< overloads , overload_match< _1, is_same<bool(int),_1> > >
Exactly!
That's indeed quite appealing. However, specializing 'iter_apply1' this way assumes that it's always invoked on a predicate metafunction, which, at least theoretically, does not hold.
Either predicate or metafunction that returns IntegralConstant constructed from sizeof (possibly shifted).
On the other hand, with 'typeof', dereferencing 'overload_set_iter' would simply return a corresponding function type and things would "just work"
That's true.
... without any special effort on our side, and in that light 'iter_apply1' specialization for the compilers that need it is simply an implementation detail which I'm willing to close my eyes to ;). It's going to be interesting to see how many MPL algorithms can be made to work with overload sequences using this approach.
I've already tried find find_if contains and equal.
Here is my plan. For now, we can reimplement mpl algorithms based on predicate using iter_applyN. Later, when typeof becomes common among popular compilers we can switch seamlessly to typeof.
Sounds good. Looking forward to hearing how it goes! -- Aleksey Gurtovoy MetaCommunications Engineering
Alexander Nasonov writes:
Aleksey Gurtovoy wrote:
Can't it be something like
mpl::find_if< overload_set<1,5,has_intersection> , is_same<first_arg<_>, Circle&> >
?
Well, I could use mpl find_if but it's not the best way (unless mpl::find_if is specialized).
[...]
3. Performance. When number of functions is high everything is important. For example, if all functions have same arity it decrease compilation time significantly. I have to pass a strategy to algorithms.
Currently, this example looks like:
overloads::find_if< overload_set<has_intersection, mpl::range_c<int,1,5> > , is_same<first_arg<_>, Circle&> >
Close to your code but it's not mpl::find_if.
Hmm, what _is_ the strategy here? 'overload_set'?
I used it till recently. But it's not quite an OverloadSet concept.
2. MPL-like sequence would be nice to have. Something similar to:
mpl::vector< bool(Circle&, Circle& ) , bool(Circle&, Rectangle&) , bool(Rectangle&, Circle& ) , bool(Rectangle&, Rectangle&) >
or
mpl::set< bool(Circle&, Circle& ) , bool(Circle&, Rectangle&) , bool(Rectangle&, Circle& ) , bool(Rectangle&, Rectangle&) >
Unfortunately, if typeof is not available, deref and some other operations work only in deduced context (that is, inside special function).
I'm afraid I don't follow; the above seems perfectly viable to me. Could you provide an example?
It is viable. But function and metainformation (signature) are stored in different places. It's ok only if you have few functions. What if you have 400? Can mpl::vector or mpl::set contain 400 elements?
'mpl::set' definitely can. Structurally, it's not very different from an "overload set".
I'm afraid not. Some overloads library work even on higher numbers (up to 700 on my laptop).
Interesting. How do you generate these in the first place?
400 is not a random number. Imagine, you have 20 classes in Shape hierarchy. Intersestion of all of them requires 20x20=400 has_intersection functions.
BTW, I remember Dave mentioned that you generate FSM using mpl::vectorN, with N higher then default 50. How high is N?
~70, IIRC.
I think Fusion is already capable of building tuples based on the MPL sequences.
1. It's different. In mpl case you use a sequence to generate tuple *type*.
I'd expect that you can generate a tuple type populated with some corresponding values (?).
In overloads case, it's both types and values. overload_set is more like mpl sequence of integral constants. You can pass it to for_each, for example.
IOW, it's a Fusion sequence?
2. The problem is that overload_set is not an MPL sequence.
I was assuming that we can make it such; the absence of standard 'typeof' facility is really limiting, isn't it? -- Aleksey Gurtovoy MetaCommunications Engineering
Aleksey Gurtovoy wrote:
Alexander Nasonov writes:
3. Performance. When number of functions is high everything is important. For example, if all functions have same arity it decrease compilation time significantly. I have to pass a strategy to algorithms.
Currently, this example looks like:
overloads::find_if< overload_set<has_intersection, mpl::range_c<int,1,5> > , is_same<first_arg<_>, Circle&> >
Close to your code but it's not mpl::find_if.
Hmm, what _is_ the strategy here? 'overload_set'?
Oops, there is no explicit strategy in my example. The strategy is optimization for sets of fixed arity. Signature deduction on a huge set is not as fast as on small sets especially if repeated many times. Deduction of 4 signatures at once speeds things up. You can think of it as different unrolling strategy. Unrolling used in mpl is getting 4 iterators and then apllying deref to each while unrolling of fixed arity overlod set is vectorized deref that returns 4 types. I think I can use strategy only in overlod_set specific algorithms (It would be interesting to see it in mpl algorithms but it's a lot work only for one not so widely used sequence).
What if you have 400? Can mpl::vector or mpl::set contain 400 elements?
'mpl::set' definitely can. Structurally, it's not very different from an "overload set".
I wonder how to create such a huge set. By inserting elements 400 times? How much compilation time would it take then?
I'm afraid not. Some overloads library work even on higher numbers (up to 700 on my laptop).
Interesting. How do you generate these in the first place?
typedef overload_set<overloads, range_c<int,1,701> > huge_set; struct overloads contains 700 call operators. You can't do much with it. Only special algorithms that is designed with this number in mind and which are supposed to return a moderate amount of element. For example, typical FSM may have 20 states and 30 events, that is, up to 600 transitions. First algorithm to apply to an overload set of transitions is searching for unique states. It should return an overload set with size 20 where each signature contains unique state. 20 is moderate number and can be represented by vector20. This is how this algorithm can transform transitions into overloads with unique states inside: in : overload_set<overloads, range_c<int,1,601> > out: overload_set<overloads, vector20< /*...*/> > Something similar to has_key would be nice too. I have one idea how to imlement fast detection of a given signature but I have to check it.
400 is not a random number. Imagine, you have 20 classes in Shape hierarchy. Intersestion of all of them requires 20x20=400 has_intersection functions.
BTW, I remember Dave mentioned that you generate FSM using mpl::vectorN, with N higher then default 50. How high is N?
~70, IIRC.
Is it a number of transitions?
I think Fusion is already capable of building tuples based on the MPL sequences.
1. It's different. In mpl case you use a sequence to generate tuple *type*.
I'd expect that you can generate a tuple type populated with some corresponding values (?).
I don't know much about fusion, I can only guess. I know for sure that I need for_each and few other algorithms. The fact that fusion has more than for_each and that it is designed for things having both run- and compile- time sequence properties lead me to conclusion that it might be useful. Overloads have both. Set of signatures is compile-time set while each call operator is run-time thing (it can be called at runtime either directly or indirectly). -- Alexander Nasonov
Alexander Nasonov writes:
What if you have 400? Can mpl::vector or mpl::set contain 400 elements?
'mpl::set' definitely can. Structurally, it's not very different from an "overload set".
I wonder how to create such a huge set. By inserting elements 400 times?
That would be one way.
How much compilation time would it take then?
Depends on the compiler. On my G5, CodeWarrior 9.2 swallowed the following in ~15 sec: typedef copy< range_c<int,0,400> , inserter< set<>, insert<_1,_2> > >::type r;
I'm afraid not. Some overloads library work even on higher numbers (up to 700 on my laptop).
Interesting. How do you generate these in the first place?
typedef overload_set<overloads, range_c<int,1,701> > huge_set; struct overloads contains 700 call operators.
Hand-written?
You can't do much with it. Only special algorithms that is designed with this number in mind and which are supposed to return a moderate amount of element. For example, typical FSM may have 20 states and 30 events, that is, up to 600 transitions. First algorithm to apply to an overload set of transitions is searching for unique states. It should return an overload set with size 20 where each signature contains unique state. 20 is moderate number and can be represented by vector20.
This is how this algorithm can transform transitions into overloads with unique states inside:
in : overload_set<overloads, range_c<int,1,601> > out: overload_set<overloads, vector20< /*...*/> >
Something similar to has_key would be nice too. I have one idea how to imlement fast detection of a given signature but I have to check it.
400 is not a random number. Imagine, you have 20 classes in Shape hierarchy. Intersestion of all of them requires 20x20=400 has_intersection functions.
BTW, I remember Dave mentioned that you generate FSM using mpl::vectorN, with N higher then default 50. How high is N?
~70, IIRC.
Is it a number of transitions?
Yep. -- Aleksey Gurtovoy MetaCommunications Engineering
Aleksey Gurtovoy wrote:
Alexander Nasonov writes:
What if you have 400? Can mpl::vector or mpl::set contain 400 elements?
'mpl::set' definitely can. Structurally, it's not very different from an "overload set".
I wonder how to create such a huge set. By inserting elements 400 times?
That would be one way.
How much compilation time would it take then?
Depends on the compiler. On my G5, CodeWarrior 9.2 swallowed the following in ~15 sec:
typedef copy< range_c<int,0,400> , inserter< set<>, insert<_1,_2> > >::type r;
15 seconds, wow! It takes more then 5 min on my centrino :(
Interesting. How do you generate these in the first place?
typedef overload_set<overloads, range_c<int,1,701> > huge_set; struct overloads contains 700 call operators.
Hand-written?
No. I typed one function in vim editor: void operator()(id<1>, struct X1*) const; and then pressed: qqyyp<CTRL-a>l<CTRL-a>q698@q This magic sequence inserts 699 lines similar to first one but with incremented numbers. Aleksey, Do you you have ideas how to inegrate mpl and overloads? If I understood you correctly, you're positive about changing mpl algorithm to iter_applyN scheme. Right? If so, what would be the best strategy? New CVS branch for iter_applyN-based mpl? Where should I store overloads algorithms? In my CVS repository or in boost[-sandbox] CVS? -- Alexander Nasonov
Alexander Nasonov writes:
Do you you have ideas how to inegrate mpl and overloads? If I understood you correctly, you're positive about changing mpl algorithm to iter_applyN scheme. Right?
If something needs to be changed, yes.
If so, what would be the best strategy? New CVS branch for iter_applyN-based mpl?
This would be the most convenient scheme for integrating them back.
Where should I store overloads algorithms? In my CVS repository or in boost[-sandbox] CVS?
I think at this early stage it'd be premature to put the library inside MPL code base (after all, it might turn out to be conceptually closer to Fusion). As for boost-sandbox vs. your CVS repository -- whatever is convenient for you, I guess. -- Aleksey Gurtovoy MetaCommunications Engineering
participants (9)
-
Aleksey Gurtovoy -
Alexander Nasonov