I have a preprocessing task that exceeds my limited abilities. If any PP gurus want to step in and prevent me from hurting myself further, I would be very grateful. My problem is this: I want to mpl::and_ together a bunch of predicates. mpl::and_ has a limit of 4 arguments. So this is wrong: mpl::and_< pred1, pred2, pred3, pred4, pred5 > but this is ok: mpl::and_< pred1, pred2, pred3, mpl::and_< pred4, pred5 > > The challenge, should you choose to accept it, is to write some PP magic that, given a MAKE_PREDICATE(z, n, data) macro and a max arity (which is greater than 4!), generates a properly nested mpl::and_-ing of the predicates. Any takers? -- Eric Niebler Boost Consulting www.boost-consulting.com
Eric Niebler wrote:
I have a preprocessing task that exceeds my limited abilities. If any PP gurus want to step in and prevent me from hurting myself further, I would be very grateful.
My problem is this: I want to mpl::and_ together a bunch of predicates. mpl::and_ has a limit of 4 arguments. So this is wrong:
mpl::and_< pred1, pred2, pred3, pred4, pred5 >
but this is ok:
mpl::and_< pred1, pred2, pred3, mpl::and_< pred4, pred5 > >
Would folding a predicate sequence using and_ work?
Peter Dimov wrote:
Eric Niebler wrote:
I have a preprocessing task that exceeds my limited abilities. If any PP gurus want to step in and prevent me from hurting myself further, I would be very grateful.
My problem is this: I want to mpl::and_ together a bunch of predicates. mpl::and_ has a limit of 4 arguments. So this is wrong:
mpl::and_< pred1, pred2, pred3, pred4, pred5 >
but this is ok:
mpl::and_< pred1, pred2, pred3, mpl::and_< pred4, pred5 > >
Would folding a predicate sequence using and_ work?
It would, except (a) it would be more expensive at compile time than a PP-based solution, and I have reason to care, and (b) it's semantically not the same, since if I used and_ directly, I get short-circuit evaluation. (b) also makes an mpl::fold-based solution unnecessarily expensive by forcing the instantiation of more predicates than necessary to evaluate the and_. -- Eric Niebler Boost Consulting www.boost-consulting.com
-----Original Message----- From: boost-bounces@lists.boost.org [mailto:boost-bounces@lists.boost.org] On Behalf Of Eric Niebler
I have a preprocessing task that exceeds my limited abilities. If any PP gurus want to step in and prevent me from hurting myself further, I would be very grateful.
My problem is this: I want to mpl::and_ together a bunch of predicates. mpl::and_ has a limit of 4 arguments. So this is wrong:
mpl::and_< pred1, pred2, pred3, pred4, pred5 >
but this is ok:
mpl::and_< pred1, pred2, pred3, mpl::and_< pred4, pred5 > >
The challenge, should you choose to accept it, is to write some PP magic that, given a MAKE_PREDICATE(z, n, data) macro and a max arity (which is greater than 4!), generates a properly nested mpl::and_-ing of the predicates.
Do you have a sequence (i.e. a selection) of predicates already or are they all "pred1", "pred2", etc.? Regards, Paul Mensonides
Paul Mensonides wrote:
-----Original Message----- From: boost-bounces@lists.boost.org [mailto:boost-bounces@lists.boost.org] On Behalf Of Eric Niebler
I have a preprocessing task that exceeds my limited abilities. If any PP gurus want to step in and prevent me from hurting myself further, I would be very grateful.
My problem is this: I want to mpl::and_ together a bunch of predicates. mpl::and_ has a limit of 4 arguments. So this is wrong:
mpl::and_< pred1, pred2, pred3, pred4, pred5 >
but this is ok:
mpl::and_< pred1, pred2, pred3, mpl::and_< pred4, pred5 > >
The challenge, should you choose to accept it, is to write some PP magic that, given a MAKE_PREDICATE(z, n, data) macro and a max arity (which is greater than 4!), generates a properly nested mpl::and_-ing of the predicates.
Do you have a sequence (i.e. a selection) of predicates already or are they all "pred1", "pred2", etc.?
The predicates can be generated given an integer. They're not quite as simple as "pred1" and "pred2" but you can ignore that for the sake of discussion. In case it helps, the predicates will all be of the form: matches< typename meta::arg_c<basic_expr<Tag, Args1, M>, N>::type , typename meta::arg_c<basic_expr<Tag, Args2, M>, N>::type
where M is a constant (could be passed into the macro as data), and N is the monotonically increasing index. -- Eric Niebler Boost Consulting www.boost-consulting.com
Eric Niebler wrote:
I have a preprocessing task that exceeds my limited abilities.
<snip> Disregard. I solved this problem by rolling my own version of mpl::and_ that takes the number of parameters I need. It does short-circuit evaluation. I'd still be curious what a PP solution looks like, though. The problem stumped me for quite some time. -- Eric Niebler Boost Consulting www.boost-consulting.com
Eric Niebler wrote:
I'd still be curious what a PP solution looks like, though. The problem stumped me for quite some time.
I'll bite. It's a bit of a hack, but it works. :) It basically accumulates the closing >'s as it goes, and expands them after the last item. It keeps a looping counter that keeps track of when to split into another mpl::and_<>. #include <boost/preprocessor/for.hpp> #include <boost/preprocessor/if.hpp> #include <boost/preprocessor/empty.hpp> #include <boost/preprocessor/dec.hpp> #include <boost/preprocessor/tuple/elem.hpp> #include <boost/preprocessor/punctuation/comma.hpp> #include <boost/preprocessor/arithmetic/div.hpp> #include <boost/preprocessor/logical/or.hpp> #include <boost/preprocessor/logical/not.hpp> #define MAKE_PREDICATE(z, n, data) \ BOOST_PP_CAT(pred,n) #define PREDICATE(r, state) \ BOOST_PP_TUPLE_ELEM(3,0,state) #define OP0(r, state, m) \ ( \ BOOST_PP_DEC(BOOST_PP_TUPLE_ELEM(3,0,state)) \ , m \ , BOOST_PP_TUPLE_ELEM(3,2,state) \ BOOST_PP_IF( \ BOOST_PP_OR( \ m \ , BOOST_PP_NOT( \ BOOST_PP_DEC( \ BOOST_PP_DEC(BOOST_PP_TUPLE_ELEM(3,0,state)) \ ) \ ) \ ) \ , BOOST_PP_EMPTY \ , > BOOST_PP_EMPTY \ )() \ ) #define OP(r, state) \ OP0( \ r \ , state \ , BOOST_PP_IF( \ BOOST_PP_TUPLE_ELEM(3,1,state) \ , BOOST_PP_DEC(BOOST_PP_TUPLE_ELEM(3,1,state)) \ , 2 \ ) \ ) #define M(r, state) \ BOOST_PP_IF( \ BOOST_PP_OR( \ BOOST_PP_TUPLE_ELEM(3,1,state) \ , BOOST_PP_NOT( \ BOOST_PP_DEC(BOOST_PP_TUPLE_ELEM(3,0,state)) \ ) \ ) \ , BOOST_PP_EMPTY \ , mpl::and_< BOOST_PP_EMPTY \ )() \ MAKE_PREDICATE( \ 0, BOOST_PP_TUPLE_ELEM(3,0,state), ~ \ ) \ BOOST_PP_IF( \ BOOST_PP_DEC(BOOST_PP_TUPLE_ELEM(3,0,state)) \ , BOOST_PP_COMMA \ , BOOST_PP_TUPLE_ELEM(3,2,state) BOOST_PP_EMPTY \ )() // for n >= 2 #define PREDICATE_LIST(n) \ BOOST_PP_FOR( \ (n,0,>) \ , PREDICATE \ , OP \ , M \ ) PREDICATE_LIST(2) PREDICATE_LIST(3) PREDICATE_LIST(4) PREDICATE_LIST(5) PREDICATE_LIST(6) PREDICATE_LIST(7) PREDICATE_LIST(8) -- Daniel Wallin Boost Consulting www.boost-consulting.com
Daniel Wallin wrote:
Eric Niebler wrote:
I'd still be curious what a PP solution looks like, though. The problem stumped me for quite some time.
I'll bite. It's a bit of a hack, but it works. :) It basically accumulates the closing >'s as it goes, and expands them after the last item. It keeps a looping counter that keeps track of when to split into another mpl::and_<>.
Here is an alternative implementation with a similar approach, using a sequence to "escape" the commas and SEQ_ENUM for "unescaping". Next fun challenge: build a tree instead: mpl::and_< pred0, pred1, pred2, pred3 > // ... mpl::and_< pred0, pred1, pred2, mpl::and_< pred3, pred4, pred5, pred6> > mpl::and_< pred0, pred1, mpl::and_< pred2, pred3>, mpl::and_< pred4, pred5, pred6, pred7 > > mpl::and_< pred0, pred1, mpl::and_< pred2, pred3, pred4>, mpl::and_< pred5, pred6, pred7, pred8 > > mpl::and_< pred0, pred1, mpl::and_< pred2, pred3, pred4, pred5>, mpl::and_< pred6, pred7, pred8, pred9 > > // ... ;-P Regards, Tobias #include <boost/preprocessor/facilities/expand.hpp> #include <boost/preprocessor/facilities/empty.hpp> #include <boost/preprocessor/facilities/identity.hpp> #include <boost/preprocessor/arithmetic/inc.hpp> #include <boost/preprocessor/arithmetic/mod.hpp> #include <boost/preprocessor/comparison/not_equal.hpp> #include <boost/preprocessor/logical/not.hpp> #include <boost/preprocessor/logical/or.hpp> #include <boost/preprocessor/control/if.hpp> #include <boost/preprocessor/control/while.hpp> #include <boost/preprocessor/seq/enum.hpp> // state is a tuple (prev-seq,next-seq,n,stop) // "unescape" the state into output #define FINALIZE_STATE(head_seq, tail_elem, n, stop) \ BOOST_PP_SEQ_ENUM(head_seq()) tail_elem() // state modifiers #define NEXT_PRED(head_seq, tail_elem, n, stop) \ ( BOOST_PP_IDENTITY(head_seq() (pred ## n)) \ , tail_elem \ , BOOST_PP_INC(n), stop \ ) #define NEXT_OP(head_seq, tail_elem, n, stop) \ ( BOOST_PP_IDENTITY(head_seq() (mpl::and_< pred ## n)) \ , > tail_elem \ , BOOST_PP_INC(n), stop \ ) // select either NEXT_PRED or NEXT_OP #define NEXT_PRED_COND(head_seq, tail_elem, n, stop) \ BOOST_PP_OR( BOOST_PP_MOD(n,3) \ , BOOST_PP_NOT( \ WHILE_PRED_IMPL (~,~,BOOST_PP_INC(n),stop) ) ) #define WHILE_OP(d,state) \ BOOST_PP_IF(NEXT_PRED_COND state, NEXT_PRED \ , NEXT_OP) state // predicate to terminate the while loop #define WHILE_PRED_IMPL(head_seq, tail_elem, n, stop) \ BOOST_PP_NOT_EQUAL(n,stop) #define WHILE_PRED(d,state) WHILE_PRED_IMPL state // #define ALL(n) BOOST_PP_EXPAND( FINALIZE_STATE \ BOOST_PP_WHILE(WHILE_PRED, WHILE_OP \ , (BOOST_PP_EMPTY,BOOST_PP_EMPTY,0,n)) ) ALL(1) ALL(2) ALL(3) ALL(4) ALL(5) ALL(6) ALL(7) ALL(8) ALL(9)
Tobias Schwinger wrote:
Daniel Wallin wrote:
Eric Niebler wrote:
I'd still be curious what a PP solution looks like, though. The problem stumped me for quite some time.
I'll bite. It's a bit of a hack, but it works. :) It basically accumulates the closing >'s as it goes, and expands them after the last item. It keeps a looping counter that keeps track of when to split into another mpl::and_<>.
Here is an alternative implementation with a similar approach, using a sequence to "escape" the commas and SEQ_ENUM for "unescaping".
<snip> WOW! That's cool. -- Eric Niebler Boost Consulting www.boost-consulting.com
Tobias Schwinger wrote:
Daniel Wallin wrote:
Eric Niebler wrote:
I'd still be curious what a PP solution looks like, though. The problem stumped me for quite some time.
I'll bite. It's a bit of a hack, but it works. :) It basically accumulates the closing >'s as it goes, and expands them after the last item. It keeps a looping counter that keeps track of when to split into another mpl::and_<>.
Here is an alternative implementation with a similar approach, using a sequence to "escape" the commas and SEQ_ENUM for "unescaping".
Yes, FWIW my rationale for doing it the way I did was that I wanted to allow the predicates to have embedded commas. Also, it's *a lot* faster, and this is a contest, right? ;) -- Daniel Wallin Boost Consulting www.boost-consulting.com
Daniel Wallin wrote:
Tobias Schwinger wrote:
Daniel Wallin wrote:
Eric Niebler wrote:
I'd still be curious what a PP solution looks like, though. The problem stumped me for quite some time.
I'll bite. It's a bit of a hack, but it works. :) It basically accumulates the closing >'s as it goes, and expands them after the last item. It keeps a looping counter that keeps track of when to split into another mpl::and_<>.
Here is an alternative implementation with a similar approach, using a sequence to "escape" the commas and SEQ_ENUM for "unescaping".
Yes, FWIW my rationale for doing it the way I did was that I wanted to allow the predicates to have embedded commas. Also, it's *a lot* faster,
I figured it would be superior in terms of performance - the massive expansion certainly takes its toll. My objective was to keep it simple and easy to follow.
and this is a contest, right? ;)
Dunno... But if it is Dave started the next lap - go for the play-off :). Regards, Tobias
David Abrahams wrote:
Tobias Schwinger <tschwinger@neoscientists.org> writes:
Next fun challenge: build a tree instead:
Okay,
I'm sure this could be faster, and it does have "comma limitations", but I'm sure those could be overcome.
Well then, (it was actually half a joke, but) time to attend to duty (: I tried a different algorithm: Traversal of an imaginary, linearized tree. It does not have the "comma limitation" but surprisingly (for me, at least) it runs awfully slow. I believe it's still worth a post and I'd be most thankful for a hint on what causes the poor performance. Regards, Tobias #include <boost/preprocessor/arithmetic/add.hpp> #include <boost/preprocessor/arithmetic/dec.hpp> #include <boost/preprocessor/arithmetic/div.hpp> #include <boost/preprocessor/arithmetic/inc.hpp> #include <boost/preprocessor/arithmetic/mod.hpp> #include <boost/preprocessor/arithmetic/mul.hpp> #include <boost/preprocessor/comparison/greater.hpp> #include <boost/preprocessor/comparison/equal.hpp> #include <boost/preprocessor/selection/min.hpp> #include <boost/preprocessor/logical/or.hpp> #include <boost/preprocessor/repetition/for.hpp> #include <boost/preprocessor/control/iif.hpp> #include <boost/preprocessor/control/if.hpp> #include <boost/preprocessor/tuple/eat.hpp> #include <boost/preprocessor/tuple/elem.hpp> #include <boost/preprocessor/tuple/rem.hpp> #include <boost/preprocessor/facilities/expand.hpp> #include <boost/preprocessor/facilities/empty.hpp> #include <boost/preprocessor/punctuation/comma.hpp> // operations on linearized 4ary (right-balanced) tree // number of branch nodes for 4-ary tree #define N_INNER_NODES(n_leafes) BOOST_PP_DIV(BOOST_PP_INC(n_leafes),3) // the last valid index for the linearized tree #define I_MAX(n_leafes) \ BOOST_PP_DEC(BOOST_PP_ADD(n_leafes,N_INNER_NODES(n_leafes))) // index operations #define FIRST_CHILD(i) BOOST_PP_INC(BOOST_PP_MUL(i,4)) #define LAST_CHILD(i,i_max) BOOST_PP_MIN(BOOST_PP_MUL(BOOST_PP_INC(i),4),i_max) #define PARENT_NODE(i) BOOST_PP_DEC(BOOST_PP_DIV(BOOST_PP_ADD(i,3),4)) // node properties #define IS_LEAF(i,i_max) BOOST_PP_GREATER(FIRST_CHILD(i),i_max) #define IS_FIRST_CHILD(i) BOOST_PP_NOT(BOOST_PP_MOD(BOOST_PP_DEC(i),4)) #define IS_LAST_CHILD(i,i_max) BOOST_PP_OR(BOOST_PP_NOT(BOOST_PP_MOD(i,4)), \ BOOST_PP_EQUAL(i,i_max)) // FSM for tree traversal (pre&post order) // // Using right-to-left traversal // L,D,U and F abbreviate Left, Down, Up and Finish // // state : condition | next // =======:===========|====== // * D : leaf | L // * D : ~ | D // L : last_leaf | U // L : leaf | L // L : ~ | D // U : last | U // U : ~ | L // U : root | F // + F : ~ | F // // * start state // + end state // ~ any condition not explicitly specified // move to rightmost child (push) #define STP_D(i,i_max) (D) (LAST_CHILD(i,i_max),i_max)(i,i_max) #define TRN_D(i,i_max) (BOOST_PP_IIF(IS_LEAF(i,i_max),L,D)) (i,i_max) // move left (decrement index) #define STP_L(i,i_max) (L) (BOOST_PP_DEC(i),i_max) #define TRN_L(i,i_max) (BOOST_PP_IIF( IS_LEAF(i,i_max), \ BOOST_PP_IIF(IS_FIRST_CHILD(i),U,L),D)) (i,i_max) // move up (pop) #define STP_U(i,i_max) (U) #define TRN_U(i,i_max) \ (BOOST_PP_IIF(IS_FIRST_CHILD(i),BOOST_PP_IF(i,U,F),L)) (i,i_max) // "traversal driver" #define OP(r,for_state) OP_I(r, BOOST_PP_TUPLE_ELEM(2,0,for_state), \ BOOST_PP_TUPLE_ELEM(2,1,for_state)) #define OP_I(r,cnt,stack) \ ( BOOST_PP_IIF( BOOST_PP_EXPAND(IS_LEAF GET_POS(stack)),BOOST_PP_INC, \ BOOST_PP_TUPLE_REM(1))(cnt) \ , BOOST_PP_EXPAND(DO_TRN DO_STP stack) ) #define DO_TRN(state) TRN_ ## state #define DO_STP(state) STP_ ## state // state queries (is this the bottleneck?) #define GET_STATE(stack) BOOST_PP_CAT(GET_STATE_I stack, _FIN) #define GET_POS(stack) BOOST_PP_CAT(GET_POS_I stack, _FIN) #define GET_STATE_I(state) state BSEQ_EAT_I #define GET_POS_I(state) BSEQ_HEAD_I #define BSEQ_HEAD_I(a,b) (a,b) BSEQ_EAT_I #define BSEQ_EAT_I(a,b) BSEQ_EAT_II #define BSEQ_EAT_II(a,b) BSEQ_EAT_I #define BSEQ_EAT_I_FIN #define BSEQ_EAT_II_FIN // termination #define PRED(r,for_state) \ BOOST_PP_CAT(CHK_CONT_,GET_STATE(BOOST_PP_TUPLE_ELEM(2,1,for_state))) #define CHK_CONT_D 1 #define CHK_CONT_L 1 #define CHK_CONT_U 1 #define CHK_CONT_F 0 // code generation #define CODEGEN_PRED(cnt,pos) CODEGEN_COMMA pos p ## cnt #define CODEGEN_COMMA(i,i_max) \ BOOST_PP_IIF(IS_LAST_CHILD(i,i_max),BOOST_PP_EMPTY,BOOST_PP_COMMA)() #define CODEGEN_D(cnt,pos) CODEGEN_COMMA pos mpl::and_< #define CODEGEN_L(cnt,pos) \ BOOST_PP_IIF(IS_LEAF pos,CODEGEN_PRED,BOOST_PP_TUPLE_EAT(2))(cnt,pos) #define CODEGEN_U(cnt,pos) \ BOOST_PP_IIF(IS_LEAF pos,CODEGEN_PRED,BOOST_PP_TUPLE_EAT(2))(cnt,pos) > #define CODEGEN_F(cnt,pos) #define MACRO(r,for_state) MACRO_I(r, BOOST_PP_TUPLE_ELEM(2,0,for_state), \ BOOST_PP_TUPLE_ELEM(2,1,for_state)) #define MACRO_I(r,cnt,stack) \ BOOST_PP_CAT(CODEGEN_,GET_STATE(stack))(cnt, GET_POS(stack)) // put it all together #define ALL(n) BOOST_PP_FOR( (0, (D) (0,I_MAX(n)) ),PRED,OP,MACRO) // ALL(1) would need special treatment ALL(2) ALL(3) ALL(4) ALL(5) ALL(6) ALL(7) ALL(8) ALL(9) ALL(10) ALL(11) ALL(12) ALL(13) ALL(14) ALL(15) ALL(16) ALL(17) ALL(18) ALL(19) ALL(20) ALL(21) ALL(22) ALL(23) ALL(24) ALL(25) ALL(26) ALL(27) ALL(28) ALL(29)
Tobias Schwinger <tschwinger@neoscientists.org> writes:
Well then, (it was actually half a joke, but) time to attend to duty (: I tried a different algorithm: Traversal of an imaginary, linearized tree.
Looks interesting... but I don't get it :)
It does not have the "comma limitation" but surprisingly (for me, at least) it runs awfully slow. I believe it's still worth a post and I'd be most thankful for a hint on what causes the poor performance.
Well, here's another, with no comma limitation, and it seems plenty fast. It's based on the enclosed Python program. Unfortunately I found the way that BOOST_PP_FOR works made the translation a little hard; it's something like: for(;;) MACRO(state); cont = PRED(state); state = NEXT(state); if !(cont) break; I got a bit tangled up in trying to unwind my Python code to fit BOOST_PP_FOR in this case. Maybe you can do better. ==== add.py ===== ==== add.cpp ===== -- Dave Abrahams Boost Consulting www.boost-consulting.com
David Abrahams wrote:
Tobias Schwinger <tschwinger@neoscientists.org> writes:
Well then, (it was actually half a joke, but) time to attend to duty (: I tried a different algorithm: Traversal of an imaginary, linearized tree.
Looks interesting... but I don't get it :)
OK, here is the description of the algorithm. A linearized tree is inherently left-balanced, since it fills from top to bottom, left to right. E.g: a a b c ... -> / \ b c ... The structure of such a tree can be represented by a single integer (number of nodes). So we first have to calculate the total number of nodes given the number of leafes. When traversing our "imaginary" (I use this adjective because there is no tree-shaped data structure, just an integer) we can emit code based on the node type and the steps performed during traversal (in detail: 'p ## n' for leafes, 'mpl::and<' when descending, '>' when ascending). There's no recursion in the PP, so we throw a state machine and a stack at the problem. Since we want to generate a right-balanced tree structure instead of a left-balanced one (like our imaginary tree), we implement traversal from right-to-left. Does that work? Regards, Tobias
Tobias Schwinger <tschwinger@neoscientists.org> writes:
When traversing our "imaginary" (I use this adjective because there is no tree-shaped data structure, just an integer) we can emit code based on the node type and the steps performed during traversal (in detail: 'p ## n' for leafes, 'mpl::and<' when descending, '>' when ascending).
There's no recursion in the PP, so we throw a state machine and a stack at the problem. Since we want to generate a right-balanced tree structure instead of a left-balanced one (like our imaginary tree), we implement traversal from right-to-left.
Does that work?
I guess. Sounds like roughly what I'm doing. -- Dave Abrahams Boost Consulting www.boost-consulting.com
participants (6)
-
Daniel Wallin -
David Abrahams -
Eric Niebler -
Paul Mensonides -
Peter Dimov -
Tobias Schwinger