[mpl]iter_fold_if Forward Backward rationale?
Why is there both a ForwardOp and BackwardOp template argument to iter_fold_if? https://svn.boost.org/trac/boost/browser/trunk/boost/mpl/iter_fold_if.hpp#L6... I would have thought that only 1 was needed. Since iter_fold_if is not documented here: http://www.boost.org/doc/libs/1_38_0/libs/mpl/doc/refmanual/refmanual_toc.ht... I assume it's not meant to be used by the user, but is only an implementation detail; however, it, or a variation, might be useful to implement the and_seq mentioned here: http://article.gmane.org/gmane.comp.lib.boost.devel/186204 As shown in that post, the template, while_if_then was used, and it does not require anything like both a ForwardOp and BackwardOp, it just requires the If and Then unary metafunctions. One problem I encountered with while_if_then was moving to the end of the sequence, at which time the Then metafunction couldn't be called; hence, I had to make it lazy to avoid dereferencing the end iterator. Is that somehow related to the need for BackwardOp in iter_fold_if. IOW, because iter_fold_if might reach the end iterator, it has to backup? I'm really asking because in the variadic template version of mpl, I wondering if iter_fold_if could be replaced with something like while_if_then (which may be renamed fold_if to be more consistent with other names with similar function). Any insight about the rationale for the iter_fold_if would probably save me considerable time in deciding whether it can be replaced with the proposed fold_if. -regards, Larry
On Mar 9, 2009, at 10:00 AM, Larry Evans wrote:
Why is there both a ForwardOp and BackwardOp template argument to iter_fold_if?
https://svn.boost.org/trac/boost/browser/trunk/boost/mpl/iter_fold_if.hpp #L62
I would have thought that only 1 was needed.
Yeah, only one is needed if you are only interested in traversing the list forward (or backward). iter_fold_if is supposed to be the most general linear traversal algorithm, upon which all the others can be built. Remember that list structures can only be built backwards, and think about the use of inserters and such with the sequence constructing algorithms.
Since iter_fold_if is not documented here:
http://www.boost.org/doc/libs/1_38_0/libs/mpl/doc/refmanual/refmanual_toc.ht...
I assume it's not meant to be used by the user, but is only an implementation detail;
I think that was probably an oversight
however, it, or a variation, might be useful to implement the and_seq mentioned here:
http://article.gmane.org/gmane.comp.lib.boost.devel/186204
As shown in that post, the template, while_if_then was used, and it does not require anything like both a ForwardOp and BackwardOp, it just requires the If and Then unary metafunctions. One problem I encountered with while_if_then was moving to the end of the sequence, at which time the Then metafunction couldn't be called; hence, I had to make it lazy to avoid dereferencing the end iterator. Is that somehow related to the need for BackwardOp in iter_fold_if.
No.
IOW, because iter_fold_if might reach the end iterator, it has to backup?
I'm really asking because in the variadic template version of mpl, I wondering if iter_fold_if could be replaced with something like while_if_then (which may be renamed fold_if to be more consistent with other names with similar function).
Any insight about the rationale for the iter_fold_if would probably save me considerable time in deciding whether it can be replaced with the proposed fold_if.
HTH, -- David Abrahams BoostPro Computing http://boostpro.com
On 03/13/09 18:49, David Abrahams wrote:
On Mar 9, 2009, at 10:00 AM, Larry Evans wrote:
Why is there both a ForwardOp and BackwardOp template argument to iter_fold_if?
https://svn.boost.org/trac/boost/browser/trunk/boost/mpl/iter_fold_if.hpp#L6...
I would have thought that only 1 was needed.
Yeah, only one is needed if you are only interested in traversing the list forward (or backward). [snip] Remember that list structures can only be built backwards, and think about the use of inserters and such with the sequence constructing algorithms.
Lists can only be constructed backwards because lists don't have a push_back? IOW, with only a push_front, the lists have to be constructed: push_front < push_front < push_front < list<> , i3 > , i2 > , i1
to create list<i1,i2,i3>? So, a traversal from back to front, (i3->i1), is needed, and, for example, fold<vector<i1,i2,i3>,list<>, push_front<_,_> > would give: list<i3,i2,i1> Instead, to create list<i1,i2,i3> from some sequence, S<i1,i2,i3>, reverse_fold would be needed: reverse_fold<S<i1,i2,i3>,list<>, push_front<_,_> > Is that about what you mean? [snip]
HTH,
Yes. Thank you, David. -regards, Larry
On 04/02/09 14:34, Larry Evans wrote:
On 03/13/09 18:49, David Abrahams wrote: [snip] Lists can only be constructed backwards because lists don't have a push_back? IOW, with only a push_front, the lists have to be constructed:
push_front < push_front < push_front < list<> , i3 > , i2 > , i1
to create list<i1,i2,i3>? So, a traversal from back to front, (i3->i1), is needed, and, for example,
fold<vector<i1,i2,i3>,list<>, push_front<_,_> >
would give:
list<i3,i2,i1>
Instead, to create list<i1,i2,i3> from some sequence, S<i1,i2,i3>, reverse_fold would be needed:
reverse_fold<S<i1,i2,i3>,list<>, push_front<_,_> >
Is that about what you mean?
[snip] One reason I'm interested is that I can't figure out how reverse_fold would work on a sequence, S, such that begin<S>::type with just a forward iterator. I would have thought that you'd need a bidirectional iterator in order to traverse backwards; yet: https://svn.boost.org/trac/boost/browser/trunk/libs/mpl/test/fold.cpp#L46 shows that it works on lists. Another reason I'm interested is that both vector and list are implemented using what looks like binary operators, v_item, and l_item, and I'm wondering why they couldn't be done with some sort of fold method. After all the vector super: v_item<T_i, vector<T_i-1,T_i-2,...> > looks like it could be done with a fold. Inspired by that example, I actually coded one: -{--code fold_reverse-- template < typename IterNow , typename IterEnd , typename State , typename ForwardOp , typename NextOp=next<arg<1> >
struct fold_reverse_iter : apply < ForwardOp , typename fold_reverse_iter < typename apply<NextOp,IterNow>::type , IterEnd , State , ForwardOp , NextOp >::type , IterNow
{ }; template < typename IterEnd , typename State , typename ForwardOp , typename NextOp
struct fold_reverse_iter < IterEnd , IterEnd , State , ForwardOp , NextOp
{ typedef State type ; }; template < class Sequence , class State , class ForwardOp
struct fold_reverse : fold_reverse_iter < typename begin<Sequence>::type , typename end<Sequence>::type , State , typename lambda<ForwardOp>::type::template apply < arg<1> , deref<arg<2> > >
{ }; -}--code fold_reverse-- Note how similar it is to the normal fold for the variadic compiler: -{--code fold-- template < typename IterNow , typename IterEnd , typename State , typename ForwardOp , typename NextOp=next<arg<1> >
struct fold_iter : fold_iter < typename apply<NextOp,IterNow>::type , IterEnd , typename apply<ForwardOp,State,IterNow>::type , ForwardOp , NextOp
{ }; template < typename IterEnd , typename State , typename ForwardOp , typename NextOp
struct fold_iter < IterEnd , IterEnd , State , ForwardOp , NextOp
{ typedef State type ; }; template < typename Sequence , typename State , typename ForwardOp
struct fold : fold_iter < typename begin<Sequence>::type , typename end<Sequence>::type , State , typename lambda<ForwardOp>::type::template apply < arg<1> , deref<arg<2> > >
{ }; -}--code fold-- So, back to v_item and fold_reverse_iter. The difference is that instead of: v_item < T0 , vector<T...>
in fold_reverse_iter there's: apply < ForwardOp , typename fold_reverse_iter < typename apply<NextOp,IterNow>::type , IterEnd , State , ForwardOp , NextOp >::type , IterNow
where ForwardOp would be push_front<arg<1>, deref<arg<2> > >. So, my next question is what's the advantage of using v_item< vector<T...> > instead of using fold_reverse_iter? I guess you could say it's more complicated, but then it reuses code and it's not (IMO) that much more complicated. OTOH, using iter_fold_if is more complicated and the justification may be that it also reuses code; however, I'm wondering if it could be simplified by using something like the fold_reverse_iter. -regards, Larry
on Thu Apr 02 2009, Larry Evans <cppljevans-AT-suddenlink.net> wrote:
One reason I'm interested is that I can't figure out how reverse_fold would work on a sequence, S, such that begin<S>::type with just a forward iterator. I would have thought that you'd need a bidirectional iterator in order to traverse backwards; yet:
https://svn.boost.org/trac/boost/browser/trunk/libs/mpl/test/fold.cpp#L46
shows that it works on lists.
More later, but remember there's recursion involved. You apply the forward function "on the way in" and the reverse one "on the way out" of the recursion. -- Dave Abrahams BoostPro Computing http://www.boostpro.com
On 04/03/09 21:31, David Abrahams wrote:
on Thu Apr 02 2009, Larry Evans <cppljevans-AT-suddenlink.net> wrote:
One reason I'm interested is that I can't figure out how reverse_fold would work on a sequence, S, such that begin<S>::type with just a forward iterator. I would have thought that you'd need a bidirectional iterator in order to traverse backwards; yet:
https://svn.boost.org/trac/boost/browser/trunk/libs/mpl/test/fold.cpp#L46
shows that it works on lists.
More later, but remember there's recursion involved. You apply the forward function "on the way in" and the reverse one "on the way out" of the recursion.
Thanks David. I thought it would be interesting to compare the mpl folds with the haskell folds. From pp. 116-117 of: http://haskell.org/defxnxtxon/haskell98-report.pdf the following is a trace of the execution of foldl and foldr where the argument order is modified to reflect that of mpl fold argument order. IOW: [x1,x2,x3] represents an mpl sequence z represents the initial state, e.g. list<>. F represents the binary operation, e.g.push_front. Now, the foldl trace: foldl([x1,x2,x3],z,F) = foldl([x2,x3],F(z,x1),F) = foldl([x3],F(F(z,x1),x2),F) = F(F(F(z,x1),x2),x3) which looks like mpl::fold since, when F == push_front, the resulting sequence is reversed, which is what happens with mpl::fold. Then, the foldr trace: foldr([x1,x2,x3],z,F) = F(x1,foldr([x2,x3],z,F)) = F(x1,F(x2,foldr([x3],z,F))) = F(x1,F(x2,F(x3,z))) which looks like mpl::fold_reverse since, when F == push_front, the resulting sequence is the same is the start sequence, which is what happens with mpl::fold_reverse. OOPS, push_front takes the sequence as 1st arg, but F(x3,z) has the sequence (e.g. list<> ) as the 2nd argument. Now, is the F in the foldr applied "on the way out" and the F in the foldl applied " on the way in"? -regards, Larry
On 04/04/09 02:05, Larry Evans wrote:
On 04/03/09 21:31, David Abrahams wrote: [snip]
You apply the forward function "on the way in" and the reverse one "on the way out" of the recursion.
I thought it would be interesting to compare the mpl folds with the haskell folds.
From pp. 116-117 of:
http://haskell.org/defxnxtxon/haskell98-report.pdf
the following is a trace of the execution of foldl and foldr where the argument order is modified to reflect that of mpl fold argument order. IOW:
[x1,x2,x3] represents an mpl sequence z represents the initial state, e.g. list<>. F represents the binary operation, e.g.push_front.
Now, the foldl trace:
foldl([x1,x2,x3],z,F) = foldl([x2,x3],F(z,x1),F) = foldl([x3],F(F(z,x1),x2),F) = F(F(F(z,x1),x2),x3)
which looks like mpl::fold since, when F == push_front, the resulting sequence is reversed, which is what happens with mpl::fold.
Then, the foldr trace:
foldr([x1,x2,x3],z,F) = F(x1,foldr([x2,x3],z,F)) = F(x1,F(x2,foldr([x3],z,F))) = F(x1,F(x2,F(x3,z)))
which looks like mpl::fold_reverse since, when F == push_front, the resulting sequence is the same is the start sequence, which is what happens with mpl::fold_reverse. OOPS, push_front takes the sequence as 1st arg, but F(x3,z) has the sequence (e.g. list<> ) as the 2nd argument.
Now, is the F in the foldr applied "on the way out" and the F in the foldl applied " on the way in"?
So now I'm wondering what's the haskell counterpart to iter_fold_if. Assuming ForwardPredicate and BackwardPredicate are always<true_>, then AFAICT, it would be foldlr defined partially by cases as: foldlr([],z,F,B) = z foldlr([x1],z,F,B) = B(x1,F(z,x1)) foldlr([x1,x2],z,F,B) = B(x1,B(x2,F(F(z,x1),x2))) foldlr([x1,x2,x3],z,F,B) = B(x1,B(x2,B(x3,F(F(F(z,x1),x2),x3)))) Where F is the iter_fold_if ForwardOp and B is the iter_fold_if BackwardOp. Now, if B==F==push_front, this would produce a palindrome: [x1,x2,x3,x3,x2,x1] This is demonstrated by the attached program which produces on cout: ***test_iter_fold_if<1> numbers=: value:0 ***test_iter_fold_if<1> result::state=: r_iter:0 r_iter:1 r_iter:1 r_iter:1 r_iter:0 ***test_iter_fold_if<2> numbers=: value:0 value:1 ***test_iter_fold_if<2> result::state=: r_iter:0 r_iter:1 r_iter:2 r_iter:2 r_iter:1 r_iter:0 However, I 've not figured out where the extra number (1 in case of iter_fold_if<1> and 2 in case of iter_fold_if<2>) is coming from. OTOH, I haven't tried very hard to figure it out. -regards, Larry
On 04/04/09 12:41, Larry Evans wrote: [snip]
Now, if B==F==push_front, this would produce a palindrome:
[x1,x2,x3,x3,x2,x1]
This is demonstrated by the attached program which produces on cout:
***test_iter_fold_if<1> numbers=: value:0 ***test_iter_fold_if<1> result::state=: r_iter:0 r_iter:1 r_iter:1 r_iter:1 r_iter:0
[snip]
However, I 've not figured out where the extra number (1 in case of iter_fold_if<1> and 2 in case of iter_fold_if<2>) is coming from. OTOH, I haven't tried very hard to figure it out.
The previous attachment should have had: push_front<arg<1>,deref<arg<2> > > instead of: push_front<arg<1>,arg<2> > as both the ForwardOp and BackwardOp. Also, the BackwardPredicate should have been: protect < aux::iter_fold_if_pred < always<true_> , typename end<numbers>::type > > With those changes, the correct palindrome is produced. Just as the ForwardPredicate is "augmented" with protection against dereferencing the end<numbers>::type in this code: https://svn.boost.org/trac/boost/browser/trunk/boost/mpl/iter_fold_if.hpp#L4... shouldn't the BackwardPredicate also be augmented with the same protection here: https://svn.boost.org/trac/boost/browser/trunk/boost/mpl/iter_fold_if.hpp#L7... ? -regards, Larry the B
On 04/05/09 08:39, Larry Evans wrote: [snip]
The previous attachment should have had:
push_front<arg<1>,deref<arg<2> > >
instead of:
push_front<arg<1>,arg<2> >
as both the ForwardOp and BackwardOp. Also, the BackwardPredicate should have been:
protect < aux::iter_fold_if_pred < always<true_> , typename end<numbers>::type >
With those changes, the correct palindrome is produced.
Just as the ForwardPredicate is "augmented" with protection against dereferencing the end<numbers>::type in this code:
https://svn.boost.org/trac/boost/browser/trunk/boost/mpl/iter_fold_if.hpp#L4...
shouldn't the BackwardPredicate also be augmented with the same protection here:
https://svn.boost.org/trac/boost/browser/trunk/boost/mpl/iter_fold_if.hpp#L7...
?
The attached code has the template, if_recur, which, AFAICT, is more general than iter_fold_if. It's more general because it's not "tied" to sequences. IOW, it's more like a while loop only instead of just tail recursion, it implements a more general type of "linear"recursion as described in the reference shown in the comments. The test shows both the equivalent of the fold and the reverse_fold (the result_up_push and the result_down_push_). It also shows the equivalent to the palindrome example of the previous post. Of cousse it maybe not as efficient as just using fold or reverse_fole; however, that's just the cost of more generality. It would be interesting to figure out how to code a sequence of linear recursive equations. The if_recur is just a single equation. Anybody care to try? -regards, Larry
on Sun Apr 05 2009, Larry Evans <cppljevans-AT-suddenlink.net> wrote:
Just as the ForwardPredicate is "augmented" with protection against dereferencing the end<numbers>::type in this code:
https://svn.boost.org/trac/boost/browser/trunk/boost/mpl/iter_fold_if.hpp#L4...
shouldn't the BackwardPredicate also be augmented with the same protection here:
https://svn.boost.org/trac/boost/browser/trunk/boost/mpl/iter_fold_if.hpp#L7...
Well, it doesn't need to be; if it did, tests and uses wouldn't compile ;-) Just think about how you'd implement it and it should become obvious why. -- Dave Abrahams BoostPro Computing http://www.boostpro.com
On 04/08/09 10:35, David Abrahams wrote:
on Sun Apr 05 2009, Larry Evans <cppljevans-AT-suddenlink.net> wrote:
Just as the ForwardPredicate is "augmented" with protection against dereferencing the end<numbers>::type in this code:
https://svn.boost.org/trac/boost/browser/trunk/boost/mpl/iter_fold_if.hpp#L4...
shouldn't the BackwardPredicate also be augmented with the same protection here:
https://svn.boost.org/trac/boost/browser/trunk/boost/mpl/iter_fold_if.hpp#L7...
Well, it doesn't need to be; if it did, tests and uses wouldn't compile ;-)
Just think about how you'd implement it and it should become obvious why.
My first guess at how to implement it is just change the result_ to: typedef aux::iter_fold_if_impl< first_ , State , ForwardOp , protect< aux::iter_fold_if_pred< ForwardPredicate,last_ > > , BackwardOp , protect< aux::iter_fold_if_pred< backward_pred_ ,last_ > > > result_; However, it's not obvious to me yet why this wouldn't work. Maybe if I tried to compile it, it would become obvious. Before I go to that trouble and if you've the time and inclination, could you give me some hint about why the if_recur in my recent post couldn't replace iter_fold_if? AFAICT, the only purpose of BackwardPredicate is to prevent selected BackwardOp applications "on the way out" (to quote from http://article.gmane.org/gmane.comp.lib.boost.devel/188246 ). However, that role could be performed by the BackwardOp itself, couldn't it? The counterpart to the BackwardOp in if_recur is the NowUp binary function. NowUp has access to all the information that BackwardPred and BackwardOp have (and it knows it's not at the end iterator, because that's handled by the eval_if test. The advantage of if_recur is that it's more understandable (at least to me) and doesn't suffer the problem of a casually coded BackwardPredicate allowing the BackwardOp to deref an end iterator (that's what happened to me and what lead to my suggestion about protecting BackwardPredicate). -regards, Larry
On 04/08/09 10:35, David Abrahams wrote:
on Sun Apr 05 2009, Larry Evans <cppljevans-AT-suddenlink.net> wrote:
Just as the ForwardPredicate is "augmented" with protection against dereferencing the end<numbers>::type in this code:
https://svn.boost.org/trac/boost/browser/trunk/boost/mpl/iter_fold_if.hpp#L4...
shouldn't the BackwardPredicate also be augmented with the same protection here:
https://svn.boost.org/trac/boost/browser/trunk/boost/mpl/iter_fold_if.hpp#L7...
Well, it doesn't need to be; if it did, tests and uses wouldn't compile ;-)
Just think about how you'd implement it and it should become obvious why.
David, With the change shown in attachment, the mpl tests passsed, as shown in the vault's: Template Metaprogramming/bjam.iter_fold_if_protected.out -regards, Larry P.S. AFAICT they passed because I saw no **failed** in the .out file.
on Thu Apr 09 2009, Larry Evans <cppljevans-AT-suddenlink.net> wrote:
On 04/08/09 10:35, David Abrahams wrote:
on Sun Apr 05 2009, Larry Evans <cppljevans-AT-suddenlink.net> wrote:
Just as the ForwardPredicate is "augmented" with protection against dereferencing the end<numbers>::type in this code:
https://svn.boost.org/trac/boost/browser/trunk/boost/mpl/iter_fold_if.hpp#L4...
shouldn't the BackwardPredicate also be augmented with the same protection here:
https://svn.boost.org/trac/boost/browser/trunk/boost/mpl/iter_fold_if.hpp#L7...
Well, it doesn't need to be; if it did, tests and uses wouldn't compile ;-)
Just think about how you'd implement it and it should become obvious why.
David,
With the change shown in attachment, the mpl tests passsed, as shown in the vault's:
Of course it does. The change has no effect, because the predicate is never executed on the past-the-end position. When recursing inward, you need to terminate recursion when you reach the end *or* when the forward predicate is satisfied, and you can't test the forward predicate on the past-the-end position. When recursing outward, the backward predicate simply tells you whether to keep applying the operation or not; whether you'll evaluate the predicate on a past-the-end position is a non-issue. -- Dave Abrahams BoostPro Computing http://www.boostpro.com
On 04/13/09 16:40, David Abrahams wrote:
on Thu Apr 09 2009, Larry Evans <cppljevans-AT-suddenlink.net wrote:
[snip]
With the change shown in attachment, the mpl tests passsed, as shown in the vault's:
Of course it does. The change has no effect, because the predicate is never executed on the past-the-end position.
The following zip file in the vault's variadic_template directory: http://preview.tinyurl.com/c6h7vc contains: 1) iter_fold_if_bkprotect.cpp 2) iter_fold_if_bkprotect.compile 3) iter_fold_if.hpp The .cpp file compiles with the change; however, without the change, it fails to compile with some error message suggesting an attempt to deref l_end: -{--compilation-- COMPILE.cmd=/usr/bin/g++-4.1 -c -Wall -ftemplate-depth-100 -O0 -fno-inline -I/home/evansl/prog_dev/boost-svn/ro/boost-trunk iter_fold_if_bkprotect.cpp -MMD -o /home/evansl/prog_dev/boost-svn/ro/boost-trunk/sandbox/build/gcc4_1/boost-vrtmp/libs/mpl/sandbox/iter_fold_if_bkprotect.o BD Software STL Message Decryptor v3.10 for gcc 2/3/4 /home/evansl/prog_dev/boost-svn/ro/boost-trunk/boost/mpl/list/aux_/iterator.hpp : In instantiation of 'boost::mpl::deref< boost::mpl::l_iter<boost::mpl::l_end> >': ... iter_fold_if_bkprotect.cpp:37: instantiated from here /home/evansl/prog_dev/boost-svn/ro/boost-trunk/boost/mpl/list/aux_/iterator.hpp:39: error: no type named 'item' in 'boost::mpl::l_end' -}--compilation-- The .compile file shows the complete error message. The .hpp file is the existing iter_fold_if.hpp modified with an '#ifdef PROTECT_BACK_PRED' which selects whether or not to use the suggested change. Now, if the predicate is never executed on the past-the-end position, then what causes the above error message? I assumed that, because of the above error message and because BackwardPred in the attachment was always<true_>, that it was tested on the past-the-end position (i.e. l_end) and returned true, which then allowed the BackwardOp to execute, which then casued the above error message. That assumption is supported by the lack of an error message when there's '#define PROTECT_BACK_PRED'. I can't think of another explanation. What am I missing? What's strange to me is that when the input sequence is a range_c, the .cpp compiles without the change, but when the input sequence is a list_c, the .cpp compile requires the change. There's an '#ifdef USE_LIST_C' which selects which input sequence is used.
When recursing inward, you need to terminate recursion when you reach the end *or* when the forward predicate is satisfied, and you can't test the forward predicate on the past-the-end position. When recursing outward, the backward predicate simply tells you whether to keep applying the operation or not;
That's about what I thought. I'm guessing that the BackwardPred allows "short-circuiting", i.e. as soon as the first false_ is encountered, the recursion stops. If so, then there's a definite advantage of iter_fold_if over the if_recur attached to post: http://article.gmane.org/gmane.comp.lib.boost.devel/188322 Does the BackwardPred allow such short-circuiting, somewhat like what happens when evaluating mpl::and_ or mpl::or_, but only starting from the back? I appreciate your patience. -regards, Larry
On 04/15/09 11:39, Larry Evans wrote:
On 04/13/09 16:40, David Abrahams wrote:
on Thu Apr 09 2009, Larry Evans <cppljevans-AT-suddenlink.net wrote:
[snip]
With the change shown in attachment, the mpl tests passsed, as shown in the vault's:
Of course it does. The change has no effect, because the predicate is never executed on the past-the-end position.
The following zip file in the vault's variadic_template directory:
http://preview.tinyurl.com/c6h7vc
contains:
1) iter_fold_if_bkprotect.cpp 2) iter_fold_if_bkprotect.compile 3) iter_fold_if.hpp
The .cpp file compiles with the change; however, without the change, it fails to compile with some error message suggesting an attempt to deref l_end:
[snip] In the same vaule directory, there's: iter_fold_if_bkprotect2.zip This contains modified versions of: mpl/iter_fold_if.hpp mpl/aux_/iter_fold_if_impl.hpp as well as the test driver and more compilations. The iter_fold_if_impl.hpp file was modified by copying parts of the preprocessor output into the file and disabling the parts that were replaced. This enabled seeing where the errors were occuring. Also, several MPL_ASSERTS were placed in that file to check where the end iterator was being passed to the iter_fold_if_backward_step template. The *.sizeI.compile files shows where the assertions fail. There's always at least one assertion failure. The number of failures is governed by the size of the input sequence. AFAICT, the iter_fold_if_backward_step should never be passed the end iterator; hence, there's a bug in iter_fold_if_impl.hpp. Am I missing something? -regards, Larry
On 04/21/09 11:36, Larry Evans wrote:
On 04/15/09 11:39, Larry Evans wrote: [snip]
The following zip file in the vault's variadic_template directory:
[snip]
replaced. This enabled seeing where the errors were occuring. Also, several MPL_ASSERTS were placed in that file to check where the end iterator was being passed to the iter_fold_if_backward_step template. The *.sizeI.compile files shows where the assertions fail. There's always at least one assertion failure. The number of failures is governed by the size of the input sequence.
AFAICT, the iter_fold_if_backward_step should never be passed the end iterator; hence, there's a bug in iter_fold_if_impl.hpp.
[snip] There's now in the same vault directory, while.cpp. This demonstrates how a while_ template can be used with an explicit stack to avoid the problems of iter_fold_if accessing the end iterator. The exlicit stack is the 3ird parameter to: template < typename Iter , typename State , typename Stack > struct forward_state ; This stack is built up during the 1st while_ instantiation and then that stack is traversed during the 2nd while_ instantiation. IOW, an explicit stack is used to simiulate recursion. I think that's about what iter_fold_if_impl was doing with the forward_stepI, for I=0,4 as well as a recursive call to itself. However, as noted above, it mistakenly assumed forward_stepI::iterator, for i=0,3, was not the end iterator. A nice side effect of this solution is the while_ could be used to solve the {or,and)_problem reported here: http://article.gmane.org/gmane.comp.lib.boost.devel/185908 -regards, Larry
On 04/22/09 11:19, Larry Evans wrote:
On 04/21/09 11:36, Larry Evans wrote:
On 04/15/09 11:39, Larry Evans wrote: [snip]
The following zip file in the vault's variadic_template directory:
[snip]
There's now in the same vault directory, while.cpp. This demonstrates how a while_ template can be used with an explicit stack to avoid the problems of iter_fold_if accessing the end iterator. The exlicit stack is the 3ird parameter to:
template < typename Iter , typename State , typename Stack > struct forward_state ;
This stack is built up during the 1st while_ instantiation and then that stack is traversed during the 2nd while_ instantiation. [snip]
However, the if_recur template attached to a previous post: http://article.gmane.org/gmane.comp.lib.boost.devel/188322 could be used to accomplish the same task. The Else parameter to if_recur could be another ir_recur. The outer if_recur would perform the task of the 1st while (building up the stack as well as building the state) and the Else if_recur would perform the task of the 2nd while. At least I think so. I haven't tried it yet. Is there any interest? -regards, Larry
On 04/22/09 11:19, Larry Evans wrote:
On 04/21/09 11:36, Larry Evans wrote:
On 04/15/09 11:39, Larry Evans wrote: [snip]
The following zip file in the vault's variadic_template directory:
[snip]
replaced. This enabled seeing where the errors were occuring. Also, several MPL_ASSERTS were placed in that file to check where the end iterator was being passed to the iter_fold_if_backward_step template. The *.sizeI.compile files shows where the assertions fail. There's always at least one assertion failure. The number of failures is governed by the size of the input sequence.
AFAICT, the iter_fold_if_backward_step should never be passed the end iterator; hence, there's a bug in iter_fold_if_impl.hpp.
[snip]
There's now in the same vault directory, while.cpp. This demonstrates how a while_ template can be used with an explicit stack to avoid the problems of iter_fold_if accessing the end iterator. The exlicit stack is the 3ird parameter to: [snip] The following trac ticket was created:
https://svn.boost.org/trac/boost/ticket/3044 Attachments to that ticket are the same as the files in the vault; hence, those vault files will be deleted.
AMDG David Abrahams wrote:
on Sun Apr 05 2009, Larry Evans <cppljevans-AT-suddenlink.net> wrote:
Just as the ForwardPredicate is "augmented" with protection against dereferencing the end<numbers>::type in this code:
https://svn.boost.org/trac/boost/browser/trunk/boost/mpl/iter_fold_if.hpp#L4...
shouldn't the BackwardPredicate also be augmented with the same protection here:
https://svn.boost.org/trac/boost/browser/trunk/boost/mpl/iter_fold_if.hpp#L7...
Well, it doesn't need to be; if it did, tests and uses wouldn't compile ;-)
Alas. AFAICT, there are no tests or uses for the Backward Predicate in MPL. In Christ, Steven Watanabe
On 05/18/09 17:19, Steven Watanabe wrote:
AMDG
David Abrahams wrote:
on Sun Apr 05 2009, Larry Evans <cppljevans-AT-suddenlink.net> wrote:
Just as the ForwardPredicate is "augmented" with protection against dereferencing the end<numbers>::type in this code:
https://svn.boost.org/trac/boost/browser/trunk/boost/mpl/iter_fold_if.hpp#L4...
shouldn't the BackwardPredicate also be augmented with the same protection here:
https://svn.boost.org/trac/boost/browser/trunk/boost/mpl/iter_fold_if.hpp#L7...
Well, it doesn't need to be; if it did, tests and uses wouldn't compile ;-)
Alas. AFAICT, there are no tests or uses for the Backward Predicate in MPL.
However, there may be a use in the future. For example, reverse_find_if. Of course one could implement that by first doing a reverse and then a find_if, but then using that rationale, one could argue there's no need for reverse_fold. I've actually got a use case: error recovery in LL1 parsers. I can't remember the details, but just as find_if could be used to find the first non-nilable element in a spirit sequence, one could use a reverse_find_if to find the last non-nilable element in the same sequence. From the Lewi reference in the vault's Home /Strings Text Processing/LewiLL1.lhs_rhs.zip there's some method of using this to calculate error recovery. IIRC, it's calculated just like the First attribute shown in the vault reference, except the sequence is reversed. There would be no need to reverse the sequence if reverse_find_if were available, and reverse_find_if can be implemented using the BackwardPredicate withe ForwardPredicate being always<true_>.
on Tue May 19 2009, Larry Evans <cppljevans-AT-suddenlink.net> wrote:
Alas. AFAICT, there are no tests or uses for the Backward Predicate in MPL.
However, there may be a use in the future.
That's really no excuse ;-) I think this is probably a case of premature generalization. -- Dave Abrahams BoostPro Computing http://www.boostpro.com
AMDG David Abrahams wrote:
on Tue May 19 2009, Larry Evans <cppljevans-AT-suddenlink.net> wrote:
Alas. AFAICT, there are no tests or uses for the Backward Predicate in MPL.
However, there may be a use in the future.
That's really no excuse ;-)
I think this is probably a case of premature generalization.
Anything that can be done with the backward predicate can be done by passing an appropriate boolean flag along with the result. Unlike the forward predicate, there are no big-O gains from having the algorithm know about it. The only case where it is significantly more convenient to use the backward predicate is when doing both a forward and a reverse operation. For this case, what is really needed is the ability to give iter_fold_if a lambda expression which will be used to package the result of the forward operation for the backwards operation. (This is all premature generalization of course...) In Christ, Steven Watanabe
On 05/29/09 16:02, Steven Watanabe wrote:
David Abrahams wrote:
on Tue May 19 2009, Larry Evans <cppljevans-AT-suddenlink.net> wrote:
Alas. AFAICT, there are no tests or uses for the Backward Predicate in MPL.
However, there may be a use in the future.
That's really no excuse ;-)
I think this is probably a case of premature generalization.
Anything that can be done with the backward predicate can be done by passing an appropriate boolean flag along with the result. Unlike the forward predicate, there are no big-O gains from having the algorithm know about it.
Why not? It seems there should be. After all, if the backward predicate is satisfied by the last element in the sequence, wouldn't that avoid going back up the recursion stack? Let's see, for a sequence, Seq, where size<Seq>::value == n, then you'd take linear time going down (with forward predicate == always<true_>) and then linear time going up *unless* the backward predicate was satisfied early. So, wouldn't the complexity for something like reverse_find be n (going down)+n/2(on the average,going up)? -Larry
on Wed Jun 03 2009, Larry Evans <cppljevans-AT-suddenlink.net> wrote:
Anything that can be done with the backward predicate can be done by passing an appropriate boolean flag along with the result. Unlike the forward predicate, there are no big-O gains from having the algorithm know about it.
Why not? It seems there should be. After all, if the backward predicate is satisfied by the last element in the sequence, wouldn't that avoid going back up the recursion stack?
How can you possibly "avoid going back up the recursion stack?" That's like asking the recursive metafunction invocations not to "return." I suppose we could cause a compiler error, but I doubt that's what you had in mind! -- Dave Abrahams BoostPro Computing http://www.boostpro.com
On 06/05/09 10:00, David Abrahams wrote:
on Wed Jun 03 2009, Larry Evans <cppljevans-AT-suddenlink.net> wrote:
Anything that can be done with the backward predicate can be done by passing an appropriate boolean flag along with the result. Unlike the forward predicate, there are no big-O gains from having the algorithm know about it. Why not? It seems there should be. After all, if the backward predicate is satisfied by the last element in the sequence, wouldn't that avoid going back up the recursion stack?
How can you possibly "avoid going back up the recursion stack?"
By making the stack explicit and using 2 while loops. The first while loop goes down the recursion stack, while storing the values in an mpl::list, the 2nd while then goes up the stack but terminates when the BackPred is reached. Shouldn't that work? It does work for the tests shown in the code. I thought the test cases accompanying the while.cpp in the previous post I mentioned showed that. OOPS, I didn't put that code in the post, but did put it in the vault and announced it earlier in this thread: http://article.gmane.org/gmane.comp.lib.boost.devel/188775 OOPS, I deleted it from the vault for some reason; however, it's here: https://svn.boost.org/trac/boost/attachment/ticket/3044/while.cpp However, there's also a version, while_unroll_recur, which does loop unrolling. I've just added while_unroll.cpp to the ticket. https://svn.boost.org/trac/boost/attachment/ticket/3044/while_recur.cpp while_recur.cpp has a 2 functionally equivalent while templates: - while_recur (no unrolling, just like the earlier attachment) - while_unroll_recur (does unrolling) The macro, USE_WHILE_UNROLL, governs which is used. A comparision of what the min value of NN in the compiler option, -ftemplate-depth-NN needed to compile the code is: For while_unroll_recur: depth compiled? ----- --------- 32 yes 31 no For while_recur: depth compiled? ----- --------- 38 yes 37 no I would have guessed maybe a factor of 4 improvement; however, it just appears only a difference of 6. I've no idea why.
That's like asking the recursive metafunction invocations not to "return." I suppose we could cause a compiler error, but I doubt that's what you had in mind!
On 06/05/09 11:05, Larry Evans wrote: [snip]
unrolling. I've just added while_unroll.cpp to the ticket.
https://svn.boost.org/trac/boost/attachment/ticket/3044/while_recur.cpp
Please ignore: https://svn.boost.org/trac/boost/attachment/ticket/3044/while_recur.2.cpp It's the same as while_recur.cpp (I attached twice by accident).
On 06/05/09 11:05, Larry Evans wrote:
On 06/05/09 10:00, David Abrahams wrote:
on Wed Jun 03 2009, Larry Evans <cppljevans-AT-suddenlink.net> wrote:
Anything that can be done with the backward predicate can be done by passing an appropriate boolean flag along with the result. Unlike the forward predicate, there are no big-O gains from having the algorithm know about it. Why not? It seems there should be. After all, if the backward predicate is satisfied by the last element in the sequence, wouldn't that avoid going back up the recursion stack?
How can you possibly "avoid going back up the recursion stack?"
By making the stack explicit and using 2 while loops. The first while loop goes down the recursion stack, while storing the values in an mpl::list, the 2nd while then goes up the stack but terminates when the BackPred is reached. Shouldn't that work? It does work for the tests shown in the code.
[snip]
That's like asking the recursive metafunction invocations not to "return." I suppose we could cause a compiler error, but I doubt that's what you had in mind!
Actually, the 2 BOOST_PP_REPEAT invocations in iter_fold_if_impl do essentially the same as 2 while loops mentioned above. The 1st BOOST_PP_REPEAT invocation creates the "explicit" stack and the 2nd BOOST_PP_REPEAT goes down this explicit stack (or up the "implicit" recursion stack), while invoking BackwardOp. Well, that's not entirely true. The explicit stack is created by recursive calls of iter_fold_if_impl *and* the 1st BOOST_PP_REPEAT call. If the I-th recursive call of iter_fold_if_impl is denoted by: iter_fold_if_impl@[I] and the typedef target (e.g. forward_step4) produced by the J-th call of the 1st BOOST_PP_REPEAT is denoted by: forward_step#[J] then the explicit stack can be denoted by: iter_fold_if_impl@[0]::forward_step#[0] iter_fold_if_impl@[0]::forward_step#[1] iter_fold_if_impl@[0]::forward_step#[2] . . . iter_fold_if_impl@[0]::forward_step#[M] iter_fold_if_impl@[1]::forward_step#[0] iter_fold_if_impl@[1]::forward_step#[1] iter_fold_if_impl@[1]::forward_step#[2] . . . iter_fold_if_impl@[1]::forward_step#[M] ... iter_fold_if_impl@[N]::forward_step#[0] iter_fold_if_impl@[N]::forward_step#[1] iter_fold_if_impl@[N]::forward_step#[2] . . . iter_fold_if_impl@[N]::forward_step#[M+1] where: horizontal indentation is a visual que (in addition to the @[.] notation ) to the recursion depth. M+1 == BOOST_MPL_LIMIT_UNROLLING. N is the number of recursive calls to iter_fold_if_impl. As mentioned, the 2nd BOOST_PP_REPEAT goes up the recursion stack. Instead of creating forward_stepJ typedefs, it creates backward_stepJ typedefs. These will be denoted: backward_step#[J]<Iterator,State> where: Iterator and State are some previous typedef targets. The reason for the <,> suffix is to indicate the dependency on previous typedefs. The actual dependency is, roughly, on the stack's forwardstep's iterator and the immediately previous backstep's state. Thus, going up the recursion stack results in typedefs denoted by: iter_fold_if_impl@[N]::backward_step#[M] < iter_fold_if_impl@[N]::forward_step#[M]::iterator , iter_fold_if_impl@[N]::forward_step#[M]::state > . . . iter_fold_if_impl@[N]::backward_step#[2] < iter_fold_if_impl@[N]::forward_step#[2]::iterator , iter_fold_if_impl@[N]::backward_step#[3]::state > iter_fold_if_impl@[N]::backward_step#[1] < iter_fold_if_impl@[N]::forward_step#[1]::iterator , iter_fold_if_impl@[N]::backward_step#[2]::state > iter_fold_if_impl@[N]::backward_step#[0] < iter_fold_if_impl@[N]::forward_step#[0]::iterator , iter_fold_if_impl@[N]::backward_step#[1]::state > ... iter_fold_if_impl@[1]::backward_step#[M] < iter_fold_if_impl@[1]::forward_step#[M]::iterator , iter_fold_if_impl@[2]::backward_step#[0]::state > . . . iter_fold_if_impl@[1]::backward_step#[2] < iter_fold_if_impl@[1]::forward_step#[2]::iterator , iter_fold_if_impl@[1]::backward_step#[3]::state > iter_fold_if_impl@[1]::backward_step#[1] < iter_fold_if_impl@[1]::forward_step#[1]::iterator , iter_fold_if_impl@[1]::backward_step#[2]::state > iter_fold_if_impl@[1]::backward_step#[0] < iter_fold_if_impl@[1]::forward_step#[0]::iterator , iter_fold_if_impl@[1]::backward_step#[1]::state > iter_fold_if_impl@[0]::backward_step#[M] < iter_fold_if_impl@[0]::forward_step#[M]::iterator , iter_fold_if_impl@[1]::backward_step#[0]::state > . . . iter_fold_if_impl@[0]::backward_step#[2] < iter_fold_if_impl@[0]::forward_step#[2]::iterator , iter_fold_if_impl@[0]::backward_step#[3]::state > iter_fold_if_impl@[0]::backward_step#[1] < iter_fold_if_impl@[0]::forward_step#[1]::iterator , iter_fold_if_impl@[0]::backward_step#[2]::state > iter_fold_if_impl@[0]::backward_step#[0] < iter_fold_if_impl@[0]::forward_step#[0]::iterator , iter_fold_if_impl@[0]::backward_step#[1]::state > One bad consequence of using BOOST_PP_REPEAT this way is that the iterator argument to the topmost backward_step: iter_fold_if_impl@[N]::backward_step#[M] < iter_fold_if_impl@[N]::forward_step#[M]::iterator , iter_fold_if_impl@[N]::forward_step#[M]::state > may be the the end iterator, mpl::end<Sequence>::type, where Sequence is the 1st argument to iter_fold_if. The solution proposed here: https://svn.boost.org/trac/boost/attachment/ticket/3044/iter_fold_if.patch is to simply replace the BackwardPred with a test on whether the iterator is the end iterator. Of course this lessens the ease of use because now the user, if he desires something like reverse_find, will have to modify BackwardOp to incorporate some sort of BackwardPred and to do nothing if this BackwardPred is false. This solution was proposed here: http://article.gmane.org/gmane.comp.lib.boost.devel/189764 A second bad consequence of using BOOST_PP_REPEAT is that no "short-circuiting" (i.e. BackwardPred returns false part-way up the recursion stack) is possible. This is because each backward_step#[J]'s depends on either backward_step#[J+1] in the current recursive call or the backward_step#[0] in the previous recursive call to iter_fold_if_impl. Thus all the bacward_step#[J]'s instantiated even if they're no-ops. In contrast, the 2 while loop solution, implemented using the while_recur template here: https://svn.boost.org/trac/boost/attachment/ticket/3044/while_recur.cpp suffers neither of these bad consequences because the explicit recursion stack is implemented with a mpl::list. While creating the explicit stack, the end iterator is not pushed onto the explicit stack because template metaprogramming (in contrast to preprocessor metaprogramming) can detect the end iterator. Going up the recursion stack can be short-circuited because, again, template metaprogramming can detect when an element in the explicit stack fails the BackwardPred and can exit the while_recur loop early. The only advantage that the 2 BOOST_PP_REPEAT loop solution has over the 2 while_recur solution is that it may create fewer template instantions, especially when BackwardPred is always<true_>. That's because with such a BacwardPred, no short-ciruiting is possible and the mpl::list used to implement the explicit stack has some instantiation overhead. However, that's only a guess. To really tell, some tests with Steven's template profiler are needed. -regards, Larry
On 05/29/09 16:02, Steven Watanabe wrote: ]snip]
The only case where it is significantly more convenient to use the backward predicate is when doing both a forward and a reverse operation. For this case, what is really needed is the ability to give iter_fold_if a lambda expression which will be used to package the result of the forward operation for the backwards operation. (This is all premature generalization of course...)
IIUC, this "lambda expression..for the backwards operation" would be used to test if the BackwardPred were satisifed, and only then would the oringinal backwards operation be applied; otherwise, the backward operation would just be the identity operation. If so, then that's what I was suggesting here: AFAICT, the only purpose of BackwardPredicate is to prevent selected BackwardOp applications "on the way out" (to quote from http://article.gmane.org/gmane.comp.lib.boost.devel/188246 ). However, that role could be performed by the BackwardOp itself, couldn't it? from: http://article.gmane.org/gmane.comp.lib.boost.devel/188358 Now AFAICT, the if_recur template, mentioned in the previous sentence to that suggestion, is functionally equivalent to the your proposed modification to iter_fold_if_impl because it doesn't have the BackwardPred either. The difference is that if_recur doesn't have the 2 calls to BOOST_PP_REPEAT whose only purpose, AFAICT, is to alleviate the "template instantiation depth" limitation described here: http://www.mywikinet.com/mpl/paper/mpl_paper.html#sequences.unrolling The advantage of if_recur is that it's clearer because: 1) if_recur doesn't try to alleviate the template instantiation depth problem and therefore doesn't use any BOOST_PP_REPEAT calls. Such BOOST_PP_REPEAT calls obscure the code. Maybe there's some if_unrolled_recur, based somehow on if_recur, that could alleviate the template instantiation depth problem using BOOST_PP_REPEAT. However even if if_unrolled_recur is used, the if_recur code should be kept around for documentation. IOW, just as the mpl_paper.html document showed fold_impl before and after the unrolling, the rationale or implementation doc for if_unrolled_recur would show the original (and clearer) if_recur and explain how if_unrolled_recur was derived from if_recur based on the pattern in the mpl_paper (or some other document within mpl docs or boost docs). 2) The other reason if_recur is clearer is that it generalizes the fold problem into a recursive if-else problem. The recursive if-else is clearer because everyone is familiar with both the if-else construct and recursion and the if_recur just has fewer template parameters than iter_fold_if_impl and this makes it easier to understand. Of course those if_recur template parameters have to be constructed from the ForwardPred and ForwardOp and BacwardOp args to iter_fold_if, but that has to be done with the existing code. In this case, the generalization is a help w.r.t. code clarity; hence, I don't think it should be characterized as premature generalization. Actually, the only reason for the while_ template mentioned here: http://article.gmane.org/gmane.comp.lib.boost.devel/188775 is to allow the short-circuiting going up the recursion stack, an advantage not possible with if_recur. I thought that would be more acceptable than if_recur because it seemed important in this post: http://article.gmane.org/gmane.comp.lib.boost.devel/171634 If short-circuiting is considered an advantage, then why not use the while_? [snip]
on Thu Apr 02 2009, Larry Evans <cppljevans-AT-suddenlink.net> wrote:
Instead, to create list<i1,i2,i3> from some sequence, S<i1,i2,i3>, reverse_fold would be needed:
reverse_fold<S<i1,i2,i3>,list<>, push_front<_,_> >
Is that about what you mean?
Yep -- Dave Abrahams BoostPro Computing http://www.boostpro.com
participants (3)
-
David Abrahams -
Larry Evans -
Steven Watanabe