Odd limitation in Fusion design ?
I see that the "Cons" sequence is Forward-only. reverse_view requires a Bidirectional sequence, at least. The for_each iteration function goes forward. However, hand-written recursive loop on a cons-like thing can do stuff before and other stuff after the recursive call to the cdr portion. Putting stuff "after" will give a reversed processing. So, in general, a reversed_for_each is not out of the question, and can be specialized for Cons when the general form of iterating backwards does not work. I also ponder that a more general form that indeed does stuff before AND other stuff after recursing the tail would be a useful addition. It might actually perform one operation iterating forward, then perform the other operation iterating backward back to the beginning; or use recursion; depending on the nature of the container. --John TradeStation Group, Inc. is a publicly-traded holding company (NASDAQ GS: TRAD) of three operating subsidiaries, TradeStation Securities, Inc. (Member NYSE, FINRA, SIPC and NFA), TradeStation Technologies, Inc., a trading software and subscription company, and TradeStation Europe Limited, a United Kingdom, FSA-authorized introducing brokerage firm. None of these companies provides trading or investment advice, recommendations or endorsements of any kind. The information transmitted is intended only for the person or entity to which it is addressed and may contain confidential and/or privileged material. Any review, retransmission, dissemination or other use of, or taking of any action in reliance upon, this information by persons or entities other than the intended recipient is prohibited. If you received this in error, please contact the sender and delete the material from any computer.
On 07/07/10 19:40, John Dlugosz wrote:
I see that the "Cons" sequence is Forward-only. reverse_view requires a Bidirectional sequence, at least. The for_each iteration function goes forward.
However, hand-written recursive loop on a cons-like thing can do stuff before and other stuff after the recursive call to the cdr portion. Putting stuff "after" will give a reversed processing. So, in general, a reversed_for_each is not out of the question, and can be specialized for Cons when the general form of iterating backwards does not work.
I also ponder that a more general form that indeed does stuff before AND other stuff after recursing the tail would be a useful addition. It might actually perform one operation iterating forward, then perform the other operation iterating backward back to the beginning; or use recursion; depending on the nature of the container.
[snip] Sounds like the if_recur template metaprogram found here: http://svn.boost.org/svn/boost/sandbox/variadic_templates/boost/mpl/if_recur... does what your asking, except for templates, not values. I'd guess it could serve as a guide on how to do it for values. -regards, Larry
On 07/07/10 20:26, Larry Evans wrote: [snip]
Sounds like the if_recur template metaprogram found here:
http://svn.boost.org/svn/boost/sandbox/variadic_templates/boost/mpl/if_recur...
does what your asking, except for templates, not values. I'd guess it could serve as a guide on how to do it for values.
[snip] Further explanation is found here: http://article.gmane.org/gmane.comp.lib.boost.devel/190063 which also mentions a limitation of the if_recur, i.e. it cannot short-circuit going up the "recursion stack". As also mentioned in that post, a while_ with explicit stack can be used to do the short-circuiting going up.
Sounds like the if_recur template metaprogram found here:
http://svn.boost.org/svn/boost/sandbox/variadic_templates/boost/mpl/if_ recur.hpp
does what your asking, except for templates, not values. I'd guess it could serve as a guide on how to do it for values.
-regards,
Larry
How does it know when to stop? Does the supplied if_recur have to include a "end" test? TradeStation Group, Inc. is a publicly-traded holding company (NASDAQ GS: TRAD) of three operating subsidiaries, TradeStation Securities, Inc. (Member NYSE, FINRA, SIPC and NFA), TradeStation Technologies, Inc., a trading software and subscription company, and TradeStation Europe Limited, a United Kingdom, FSA-authorized introducing brokerage firm. None of these companies provides trading or investment advice, recommendations or endorsements of any kind. The information transmitted is intended only for the person or entity to which it is addressed and may contain confidential and/or privileged material. Any review, retransmission, dissemination or other use of, or taking of any action in reliance upon, this information by persons or entities other than the intended recipient is prohibited. If you received this in error, please contact the sender and delete the material from any computer.
On 07/08/10 12:04, John Dlugosz wrote:
Sounds like the if_recur template metaprogram found here:
http://svn.boost.org/svn/boost/sandbox/variadic_templates/boost/mpl/if_ recur.hpp
does what your asking, except for templates, not values. I'd guess it could serve as a guide on how to do it for values.
-regards,
Larry
How does it know when to stop? Does the supplied if_recur have to include a "end" test?
The Recur template arg to the if_recur template provides the "end" test. You might find the backus_turingaward_lecture.pdf reference mentioned in the code comments helpful.
You might find the backus_turingaward_lecture.pdf reference mentioned in the code comments helpful.
//Purpose: // Almost the same as section 12.5 equation 1) which is: f ≡ p → g; Q(f) where Q(k) ≡ h∘[i, k∘j] Sorry, no. TradeStation Group, Inc. is a publicly-traded holding company (NASDAQ GS: TRAD) of three operating subsidiaries, TradeStation Securities, Inc. (Member NYSE, FINRA, SIPC and NFA), TradeStation Technologies, Inc., a trading software and subscription company, and TradeStation Europe Limited, a United Kingdom, FSA-authorized introducing brokerage firm. None of these companies provides trading or investment advice, recommendations or endorsements of any kind. The information transmitted is intended only for the person or entity to which it is addressed and may contain confidential and/or privileged material. Any review, retransmission, dissemination or other use of, or taking of any action in reliance upon, this information by persons or entities other than the intended recipient is prohibited. If you received this in error, please contact the sender and delete the material from any computer.
Sounds like the if_recur template metaprogram found here:
http://svn.boost.org/svn/boost/sandbox/variadic_templates/boost/mpl/if_ recur.hpp
does what your asking, except for templates, not values. I'd guess it could serve as a guide on how to do it for values.
-regards,
Larry
So you give it two functions, one to do on the way down and another to do on a the way up? TradeStation Group, Inc. is a publicly-traded holding company (NASDAQ GS: TRAD) of three operating subsidiaries, TradeStation Securities, Inc. (Member NYSE, FINRA, SIPC and NFA), TradeStation Technologies, Inc., a trading software and subscription company, and TradeStation Europe Limited, a United Kingdom, FSA-authorized introducing brokerage firm. None of these companies provides trading or investment advice, recommendations or endorsements of any kind. The information transmitted is intended only for the person or entity to which it is addressed and may contain confidential and/or privileged material. Any review, retransmission, dissemination or other use of, or taking of any action in reliance upon, this information by persons or entities other than the intended recipient is prohibited. If you received this in error, please contact the sender and delete the material from any computer.
On 07/08/10 14:43, John Dlugosz wrote:
Sounds like the if_recur template metaprogram found here:
http://svn.boost.org/svn/boost/sandbox/variadic_templates/boost/mpl/if_ recur.hpp
does what your asking, except for templates, not values. I'd guess it could serve as a guide on how to do it for values.
-regards,
Larry
So you give it two functions, one to do on the way down and another to do on a the way up?
Yes. However, I'm not sure if the way-up function is the NowUp or Else template parameter. I'd have to look at the backus_turingaward_lecture.pdf reference to see which is which.
So you give it two functions, one to do on the way down and another to do on a the way up?
Yes. However, I'm not sure if the way-up function is the NowUp or Else template parameter. I'd have to look at the backus_turingaward_lecture.pdf reference to see which is which.
My own effort at this, straddling the compile-time and run-time boundaries, is posted on a new topic. I can't get the necessarily run-time test for done-ness to play nice with the compile-time metafunctions that are "run" (expanded) regardless of what might happen at run time. I'm sure it's a documentation problem with Fusion. There is no guarantee that the 'end' iterator evaluates to a unique type that won't happen to match the iterator's type inside the normal work. For a cons (Lisp-like) list I'm rather certain that it will be, unless he's using some kind of type erasure in the implementation, but I don't want to make that assumption, and even if that were taken, it seems difficult to accomplish (compared with simply knowing a simple name for a type that could be used in a partial specialization or overloaded form). I'm assuming that there is intended to be some simple and natural way to iterate a collection other than using the canned fold or for_each functions! --John TradeStation Group, Inc. is a publicly-traded holding company (NASDAQ GS: TRAD) of three operating subsidiaries, TradeStation Securities, Inc. (Member NYSE, FINRA, SIPC and NFA), TradeStation Technologies, Inc., a trading software and subscription company, and TradeStation Europe Limited, a United Kingdom, FSA-authorized introducing brokerage firm. None of these companies provides trading or investment advice, recommendations or endorsements of any kind. The information transmitted is intended only for the person or entity to which it is addressed and may contain confidential and/or privileged material. Any review, retransmission, dissemination or other use of, or taking of any action in reliance upon, this information by persons or entities other than the intended recipient is prohibited. If you received this in error, please contact the sender and delete the material from any computer.
On 07/08/10 19:42, John Dlugosz wrote:
So you give it two functions, one to do on the way down and another to do on a the way up? Yes. However, I'm not sure if the way-up function is the NowUp or Else template parameter. I'd have to look at the backus_turingaward_lecture.pdf reference to see which is which.
My own effort at this, straddling the compile-time and run-time boundaries, is posted on a new topic. I can't get the necessarily run-time test for done-ness to play nice with the compile-time metafunctions that are "run" (expanded) regardless of what might happen at run time.
I'm sure it's a documentation problem with Fusion. There is no guarantee that the 'end' iterator evaluates to a unique type that won't happen to match the iterator's type inside the normal work. For a cons (Lisp-like) list I'm rather certain that it will be, unless he's using some kind of type erasure in the implementation, but I don't want to make that assumption, and even if that were taken, it seems difficult to accomplish (compared with simply knowing a simple name for a type that could be used in a partial specialization or overloaded form). I'm assuming that there is intended to be some simple and natural way to iterate a collection other than using the canned fold or for_each functions! [snip]
John, I think I had a similar problem and didn't find a good answer. The problem was posted in a thread to this list whose last post was: http://thread.gmane.org/gmane.comp.lib.boost.user/58611/focus=58612 Anyway, the attached fusion::if_recur does what I was thinking as a solution. The test driver is also attached with the output. The test driver uses: http://svn.boost.org/svn/boost/sandbox/variadic_templates/boost/iostreams/ut... The output shows the reverse of the input going up the recursion stack and that's why I thought the if_recur might provide the "reverse processing" that you mentioned in post: http://article.gmane.org/gmane.comp.lib.boost.user/60210 However, the attached fusion::if_recur suffers the problem that the result_type is fixed by the ElseBtm::result_type. I'm not sure this can be used to solve the problem of reversing a heterogeneous fusion sequence since the result_type would have to be the reverse of the original type. Anyway, hope this helps. -regards, Larry /home/evansl/prog_dev/boost-svn/ro/trunk/sandbox-local/build/gcc4_4v/boost-svn/ro/sandbox/rw/variadic_templates/libs/fusion/sandbox/if_recur.exe show_default=9 increment:state=0 increment:state=1 increment:state=2 increment:state=3 print_btm:state_btm=4 print_pair:state_now=3:state_up=4 print_pair:state_now=2:state_up=4 print_pair:state_now=1:state_up=4 print_pair:state_now=0:state_up=4 show_less_increment=4 Compilation finished at Sat Jul 10 08:20:10
Anyway, hope this helps.
-regards, Larry
When I noticed that Fusion has its own metafunction to use instead of is_same, I figure it is there to make 'end' testing work correctly. That could be a documentation issue, but could be a semi-oversight that could be tightened up in the spec. That is, result_of::equal_to<T1,T2> returns true if they are iterators to the same position. 'end' should be considered a position. Does it work if the arguments are from different collections? Is 'end' equal for all collections or all collections of the same kind, or pot-luck? --John TradeStation Group, Inc. is a publicly-traded holding company (NASDAQ GS: TRAD) of three operating subsidiaries, TradeStation Securities, Inc. (Member NYSE, FINRA, SIPC and NFA), TradeStation Technologies, Inc., a trading software and subscription company, and TradeStation Europe Limited, a United Kingdom, FSA-authorized introducing brokerage firm. None of these companies provides trading or investment advice, recommendations or endorsements of any kind. The information transmitted is intended only for the person or entity to which it is addressed and may contain confidential and/or privileged material. Any review, retransmission, dissemination or other use of, or taking of any action in reliance upon, this information by persons or entities other than the intended recipient is prohibited. If you received this in error, please contact the sender and delete the material from any computer.
On 7/13/10 2:52 AM, John Dlugosz wrote:
Anyway, hope this helps.
-regards, Larry
When I noticed that Fusion has its own metafunction to use instead of is_same, I figure it is there to make 'end' testing work correctly. That could be a documentation issue, but could be a semi-oversight that could be tightened up in the spec. That is, result_of::equal_to<T1,T2> returns true if they are iterators to the same position. 'end' should be considered a position. Does it work if the arguments are from different collections? Is 'end' equal for all collections or all collections of the same kind, or pot-luck?
I suggest you (re)read Fusion concepts (sequence and iterator concepts). These are all documented (e.g. http://tinyurl.com/5llaf8). Regards, -- Joel de Guzman http://www.boostpro.com http://spirit.sf.net
I suggest you (re)read Fusion concepts (sequence and iterator concepts). These are all documented (e.g. http://tinyurl.com/5llaf8).
OK, I will. Maybe another pass after having used it will "stick" more. TradeStation Group, Inc. is a publicly-traded holding company (NASDAQ GS: TRAD) of three operating subsidiaries, TradeStation Securities, Inc. (Member NYSE, FINRA, SIPC and NFA), TradeStation Technologies, Inc., a trading software and subscription company, and TradeStation Europe Limited, a United Kingdom, FSA-authorized introducing brokerage firm. None of these companies provides trading or investment advice, recommendations or endorsements of any kind. The information transmitted is intended only for the person or entity to which it is addressed and may contain confidential and/or privileged material. Any review, retransmission, dissemination or other use of, or taking of any action in reliance upon, this information by persons or entities other than the intended recipient is prohibited. If you received this in error, please contact the sender and delete the material from any computer.
On 07/10/10 08:57, Larry Evans wrote:
On 07/08/10 19:42, John Dlugosz wrote:
So you give it two functions, one to do on the way down and another to do on a the way up? Yes. However, I'm not sure if the way-up function is the NowUp or Else template parameter. I'd have to look at the backus_turingaward_lecture.pdf reference to see which is which.
[snip] Anyway, the attached fusion::if_recur does what I was thinking as a solution. The test driver is also attached with the output. The test driver uses:
http://svn.boost.org/svn/boost/sandbox/variadic_templates/boost/iostreams/ut...
[snip] A revised version of this code is now in: http://svn.boost.org/svn/boost/sandbox/variadic_templates/ boost/fusion/algorithm/if_recur.hpp libs/fusion/sandbox/if_recur.cpp The compilation and run output is in the attachment. The indentation provided by indent_scoped_ostreambuf shows the recursion depth pretty clearly. The if_recur template has another template parameter, the last one, which governs whether the recursion is terminated on values or types. The recursion termination on types was *much* harder to implement. I'm wondering if going up the recursion stack wouldn't be faster if an explicit stack were used instead of the way it's done in if_recur. A nice side effect of the explicit stack is the ability to short-circuit the recursion as soon as a termination condition is met. In contrast, with the example in if_recur.cpp, the stack, since its implicit, must be unwound completely, while a flag is used to tell the template functions, specifically, the iter_find_target<*>::now_up<*>::call, that the answer is already found. In the example, that flag is simply that IterUp is not the same as IterEnd. Anyway, HTH. -regards, Larry ###-*- mode: compilation; default-directory: "~/prog_dev/boost-svn/ro/sandbox/rw/variadic_templates/libs/fusion/sandbox/" -*- Compilation started at Sun Jul 18 10:54:13 make run install -d `dirname /home/evansl/prog_dev/boost-svn/ro/trunk/sandbox-local/build/gcc4_5v/boost-svn/ro/sandbox/rw/variadic_templates/libs/fusion/sandbox/if_recur.o` /home/evansl/download/stlfilt/gfilt -compiler:/home/evansl/download/gcc/4.5-20100624/install/bin/g++ -c -Wall -ftemplate-depth-300 -O0 -g3 -fno-inline -std=gnu++0x -DCXX0X_VARIADIC_TEMPLATES -I/home/evansl/prog_dev/boost-svn/ro/sandbox/rw/variadic_templates -I/home/evansl/prog_dev/boost-svn/ro/trunk/sandbox-local/lje -I/home/evansl/prog_dev/boost-svn/ro/trunk -DTEMPLATE_DEPTH=300 if_recur.cpp -MMD -o /home/evansl/prog_dev/boost-svn/ro/trunk/sandbox-local/build/gcc4_5v/boost-svn/ro/sandbox/rw/variadic_templates/libs/fusion/sandbox/if_recur.o COMPILE.cmd=/home/evansl/download/gcc/4.5-20100624/install/bin/g++ -c -Wall -ftemplate-depth-300 -O0 -g3 -fno-inline -std=gnu++0x -DCXX0X_VARIADIC_TEMPLATES -I/home/evansl/prog_dev/boost-svn/ro/sandbox/rw/variadic_templates -I/home/evansl/prog_dev/boost-svn/ro/trunk/sandbox-local/lje -I/home/evansl/prog_dev/boost-svn/ro/trunk -DTEMPLATE_DEPTH=300 if_recur.cpp -MMD -o /home/evansl/prog_dev/boost-svn/ro/trunk/sandbox-local/build/gcc4_5v/boost-svn/ro/sandbox/rw/variadic_templates/libs/fusion/sandbox/if_recur.o BD Software STL Message Decryptor v3.10 for gcc 2/3/4 sed -e 's#^if_recur.o:#/home/evansl/prog_dev/boost-svn/ro/trunk/sandbox-local/build/gcc4_5v/boost-svn/ro/sandbox/rw/variadic_templates/libs/fusion/sandbox/if_recur.o:#' /home/evansl/prog_dev/boost-svn/ro/trunk/sandbox-local/build/gcc4_5v/boost-svn/ro/sandbox/rw/variadic_templates/libs/fusion/sandbox/if_recur.d> /home/evansl/prog_dev/boost-svn/ro/trunk/sandbox-local/build/gcc4_5v/boost-svn/ro/sandbox/rw/variadic_templates/libs/fusion/sandbox/if_recur.o.dep #rm /home/evansl/prog_dev/boost-svn/ro/trunk/sandbox-local/build/gcc4_5v/boost-svn/ro/sandbox/rw/variadic_templates/libs/fusion/sandbox/if_recur.d /home/evansl/download/gcc/4.5-20100624/install/bin/g++ -Wl,-rpath /home/evansl/download/gcc/4.5-20100624/install/lib64 /home/evansl/prog_dev/boost-svn/ro/trunk/sandbox-local/build/gcc4_5v/boost-svn/ro/sandbox/rw/variadic_templates/libs/fusion/sandbox/if_recur.o -o /home/evansl/prog_dev/boost-svn/ro/trunk/sandbox-local/build/gcc4_5v/boost-svn/ro/sandbox/rw/variadic_templates/libs/fusion/sandbox/if_recur.exe /home/evansl/prog_dev/boost-svn/ro/trunk/sandbox-local/build/gcc4_5v/boost-svn/ro/sandbox/rw/variadic_templates/libs/fusion/sandbox/if_recur.exe list_v=[int_val<-9>(-9), int_val<0>(0), int_val<-9>(-9), int_val<2>(2)] target_v=int_val<-9>(-9) iter_next: iter_now=int_val<-9>(-9) int_val<0>(0) int_val<-9>(-9) int_val<2>(2) iter_next: iter_now=int_val<0>(0) int_val<-9>(-9) int_val<2>(2) iter_next: iter_now=int_val<-9>(-9) int_val<2>(2) iter_next: iter_now=int_val<2>(2) iter_btm: iter_now= now_up: iter_now=int_val<2>(2) iter_up= now_up: iter_now=int_val<-9>(-9) int_val<2>(2) iter_up= now_up: iter_now=int_val<0>(0) int_val<-9>(-9) int_val<2>(2) iter_up=int_val<-9>(-9) int_val<2>(2) now_up: iter_now=int_val<-9>(-9) int_val<0>(0) int_val<-9>(-9) int_val<2>(2) iter_up=int_val<-9>(-9) int_val<2>(2) result_v=int_val<-9>(-9) int_val<2>(2) Compilation finished at Sun Jul 18 10:54:19
On 7/8/10 8:40 AM, John Dlugosz wrote:
I see that the "Cons" sequence is Forward-only. reverse_view requires a Bidirectional sequence, at least. The for_each iteration function goes forward.
However, hand-written recursive loop on a cons-like thing can do stuff before and other stuff after the recursive call to the cdr portion. Putting stuff "after" will give a reversed processing. So, in general, a reversed_for_each is not out of the question, and can be specialized for Cons when the general form of iterating backwards does not work.
I also ponder that a more general form that indeed does stuff before AND other stuff after recursing the tail would be a useful addition. It might actually perform one operation iterating forward, then perform the other operation iterating backward back to the beginning; or use recursion; depending on the nature of the container.
That is an interesting thought. Contributions are always welcome. Algorithms can indeed be applied reversibly in Fusion, not only for cons lists but all fusion ranges in general (I think). The stack holds all the iterators anyway! Regards, -- Joel de Guzman http://www.boostpro.com http://spirit.sf.net
participants (3)
-
Joel de Guzman -
John Dlugosz -
Larry Evans