clean up preprocessor/seq/fold_left.hpp

[anonymous]

introductionary notes:

BOOST_PP_SEQ_FOLD_LEFT is a macro that applies a submitted macro (henceforth called operation) to all elements of a sequence, starting with element 0 (leftmost). The operation macro op(n, state, elem) takes three arguments, the first being a counter starting from 2 and incremented after each operation, second, an arbitrary sequence of preprocessing tokens comprising the intermediate result (or current state), and finally the current element, stripped of the embracing parentheses. The result of the operation is an updated state, passed on to the next call to the operation.

BOOST_PP_SEQ_FOLD_LEFT is called with three parameters: first, the name of the operation macro, second, the initial state, and third, the sequence to which to apply the operation element-wise. It returnes the final state.

Since the above mentioned counter starts from 2, submitting a sequence of length 256 to BOOST_SEQ_FOLD_LEFT will result in a final call to the operation macro with its first parameter set to 257. I neither expect a counter starting from anything but 0 or 1, nor do I expect, it might get me out of the arithmetic range, so I consider this a really bad design decision.

The 1.43 implementation of BOOST_PP_SEQ_FOLD_LEFT contains a huge amount of what seems to be leftovers from a major rework, not having been removed yet, and, in addition, allows for significant reduction of evaluation costs.

fold_left.hpp is now simplified in 3 major steps.

step 1:

The definition of BOOST_PP_SEQ_FOLD_LEFT entails a call to BOOST_PP_AUTO_REC. In short, this call turns out to be completely pointless, as it will always return 1 as result, and can be simply replaced by this constant.

This can be seen as follows:

BOOST_PP_AUTO_REC operates on macros P(n), that

• take integers from 1 to 256 as paramater;
• are binary, i.e. yields only 0 or 1 as a result;
• are monotonely rising, i.e. there is an integer n such that P(i) == 0 for i < n and == 1 otherwise.

BOOST_PP_AUTO_SEC is designed to find the 'leap position' where P assumes 1 for the first time.

BOOST_PP_SEQ_FOLD_LEFT_P is such a P(n). Although the replacement of BOOST_PP_SEQ_FOLD_LEFT_P looks complex, a closer look at

BOOST_PP_SEQ_FOLD_LEFT_I_ ## n(BOOST_PP_SEQ_FOLD_LEFT_O, BOOST_PP_NIL, (nil), 1)

reveals, that this expression, independently of n, will always expand to BOOST_PP_NIL, and after some more replacing, BOOST_PP_SEQ_FOLD_LEFT_P turns out to be constantly 1. Consequently, BOOST_PP_AUTO_REC, applied to this (constant) macro, will yield 1 as a result.

Hence simplify the definition of BOOST_PP_SEQ_FOLD_LEFT:

# define BOOST_PP_SEQ_FOLD_LEFT BOOST_PP_SEQ_FOLD_LEFT_1

step 2:

Now, that BOOST_PP_SEQ_FOLD_LEFT_P has been eliminated, its definition may be removed. Then, none of the BOOST_PP_SEQ_FOLD_LEFT_CHECK_* macros are called any more (not only in fold_left.hpp, but throughout the whole preprocessor branch). The same holds for some other macros as well. Here is the list:

• BOOST_PP_SEQ_FOLD_LEFT_P;
• BOOST_PP_SEQ_FOLD_LEFT_O;
• BOOST_PP_SEQ_FOLD_LEFT_CHECK_*;
• BOOST_PP_SEQ_FOLD_LEFT_*257;
• BOOST_PP_SEQ_FOLD_LEFT_n for 2 <= n <= 256;

Drop their definitions.

step 3

The loop iterating over the elements has been unrolled disadvantageously. Although the length of the sequence is determined in advance, the loop starts in a forward manner and, thus, has to permanently check when to terminate. A countdown strategy is more appropriate here, automatically terminating when iteration 1 is reached. This saves a couple of macro replacements per iteration. Because of the 257 quirk of BOOST_PP_SEQ_FOLD_LEFT mentioned in the first section, an extra parameter q257 has to be introduced, controlling the setting of the counter to the somewhat irregular value 257 when a sequence of length 256 is encountered.

While the reduction and dropping in step 1 and 2 should not be affected by preprocessor quirks, the optimization carried out here might be susceptible to them. So, for safety reasons, this optimization takes effect only when BOOST_PP_CONFIG_FLAGS() is equal to BOOST_PP_CONFIG_STRICT().

[ookami1@…]

Forgot to add my name and a greeting:

Cheers Wolf Lammen

[ookami1@…]

takes BOOST_PP_SEQ_FOLD_RIGHT into account

[ookami1@…]

Forget step 3 for the time being, as this would break BOOST_PP_SEQ_FOLD_RIGHT

Cheers

Wolf Lammen

[Steven Watanabe]

Replying to anonymous:

step 1:

The definition of BOOST_PP_SEQ_FOLD_LEFT entails a call to BOOST_PP_AUTO_REC. In short, this call turns out to be completely pointless, as it will always return 1 as result, and can be simply replaced by this constant.

This can be seen as follows:

BOOST_PP_AUTO_REC operates on macros P(n), that

• take integers from 1 to 256 as paramater;
• are binary, i.e. yields only 0 or 1 as a result;
• are monotonely rising, i.e. there is an integer n such that P(i) == 0 for i < n and == 1 otherwise.

BOOST_PP_AUTO_SEC is designed to find the 'leap position' where P assumes 1 for the first time.

BOOST_PP_SEQ_FOLD_LEFT_P is such a P(n). Although the replacement of BOOST_PP_SEQ_FOLD_LEFT_P looks complex, a closer look at

BOOST_PP_SEQ_FOLD_LEFT_I_ ## n(BOOST_PP_SEQ_FOLD_LEFT_O, BOOST_PP_NIL, (nil), 1)

reveals, that this expression, independently of n, will always expand to BOOST_PP_NIL, and after some more replacing, BOOST_PP_SEQ_FOLD_LEFT_P turns out to be constantly 1. Consequently, BOOST_PP_AUTO_REC, applied to this (constant) macro, will yield 1 as a result.

Nope. BOOST_PP_SEQ_FOLD_LEFT_P expands to 1 iff. we are not currently in an expansion of BOOST_PP_SEQ_FOLD_LEFT_I_ ## n. If BOOST_PP_SEQ_FOLD_LEFT_I_ ## n is being expanded, then it will not be expanded again, since recursive calls to a macro are not expanded. BOOST_PP_AUTO_REC is used to find the first available index that is not on the macro expansion stack. This allows nested calls to BOOST_PP_SEQ_FOLD_LEFT. Note that the s parameter to the macro is not the index in the sequence. It is the next available index for reentering BOOST_PP_FOLD_LEFT. See http://www.boost.org/libs/preprocessor/doc/ref/seq_fold_left.html.

[anonymous]

Yes, judging from how BOOST_PP_SEQ_FOLD_LEFT_* macros were used, I already had the idea, they might be a pool of macros shared among several loops. I just did not see how this pool was managed, so I thought 'get rid of it!'.

Your explanation fills in here, and I mark this ticket as invalid (that is if I have sufficient right to do so).

Cheers

Wolf Lammen