Re: [boost] [preprocessor] Variadics suggestion

Subject: Re: [boost] [preprocessor] Variadics suggestion
From: Paul Mensonides (pmenso57_at_[hidden])
Date: 2012-10-11 05:18:24

On 10/10/2012 3:15 PM, paul Fultz wrote:
> The _1, _2, etc, are not macros, but instead are parsed by the invoker.

Uh... you /can't/ parse them unless you restrict the input. The only way 
you can interact with them would be through token-pasting--which you 
can't do unless you know what you've got is an identifier or pp-number 
(that doesn't include decimal points).

>> Now, I'm not sure if this scales to every scenario.  And it is playing
>> extremely fast and loose with hanging parenthesis.  I haven't spent a
>> great deal of time playing with it.  But, this would be magic:
>>
>> #define _0 ARG(0)
>> #define _1 ARG(1)
>>
>> APPLY(
>>      (A)(B),
>>      template<class T> class _0 : public _1 {
>>          public:
>>              inline _0(const _0& c) : _1(1, 2, 3) {
>>                  // ...
>>              }
>>      };
>> )
>>
>> #undef _0
>> #undef _1
>>
>> If that can be made to work, that would be freakishly clever.  You'd then
>> have to do lambda bindings as another type of "control flag" to delay
>> them
>> (and hide the actual macros' names).
>>
>>
>>   This seems really cool.

I've played with this some (see my other email from a few days ago), but 
it is not fully fleshed out.  I believe that it is possible, however.  
The basic idea is to make the placeholders accessible to the parser.  
Which you have to use someone elaborate methods to involving commas and 
unmatched parentheses.

>>>   As well as supporting lambda or even user-defined invokable expressions.
>>>   Ultimately, bind would just be implemented as this(Yes I know chaos
>>>   already has a bind macro):
>>>
>>>       #define CHAOS_PP_BIND(m, ...) (CHAOS_PP_BIND)(m, __VA_ARGS__)
>> The library already allows what you pass to be a deferred expression in
>> terms of NEXT(s).  So you can put an arbitrary remapper:
>>
>> #define MACRO(x, y) x - y
>> #define DROP_AND_SWAP(s, y, x) (x, y)
>>
>> CHAOS_PP_EXPR(CHAOS_PP_ENUM(
>>      3, MACRO DROP_AND_SWAP, 3
>> ))
>>
>> ...contrived, I know.
>>
> I didn't realize deferred expression could be given, this seems to be a better way to
> approach the problem. You should really write a book on this.

The underlying /reason/ that it allows the argument to expand to a 
deferred expression in terms of NEXT(s) is so that the whatever is 
called can be reused recursively also.  E.g.

#define A(s, n) \
     n B(CHAOS_PP_OBSTRUCT(), CHAOS_PP_NEXT(s), n) \
     /**/
#define A_ID() A
#define B(_, s, n) \
     CHAOS_PP_EXPR_S _(s)(CHAOS_PP_REPEAT_S _( \
         s, n, A_ID _() \
     )) \
     /**/

CHAOS_PP_EXPR(CHAOS_PP_REPEAT(
     10, A
))

Here REPEAT calls A, A calls REPEAT, REPEAT calls A, and so on.  
Essentially, the algorithm is starting a bootstrap on the call just like 
with at the top level.

If you use that bootstrap to rearrange the arguments, you lose the 
ability to self-recurse as in the above.  For the case of REPEAT, you 
/could/ add more bootstraps to the top-level but that is only because 
REPEAT does not care what the result of your macro is.  In other cases, 
such as with predicates and state transition operators such as in 
WHILE.  In that case, the algorithm needs to invoke the predicate and do 
something with the result.  The operator here is involved with the 
algorithm because its result is passed to the predicate.  In the case of 
something like FOLD, the predicate is internal (i.e. some variety of "is 
cons"), so the algorithm doesn't care what you do with the operator you 
pass (provided it doesn't produce unmatched parentheses).  However, the 
operator itself will care.

In my own use, however, I've rarely had scenarios were I needed to 
see-saw as in the above example, so using the extra bootstrap to mess 
with the arguments is usually viable.

>> A lot of this type of stuff is extremely trickly subject matter.  A
>> typical user isn't writing algorithms, etc..  They are just using the
>> provided higher-level macros.  What Chaos' does, for the most part, is
>> take all implementation-level macros that could be useful as interfaces
>> and define them as interfaces.  I agree, however, that over-arching
>> concepts, themes, idioms, and techniques need adequate documentation.
>>
>> Where I got the term "parametric" from in this context I have no
>> idea!
>> Essentially, those algorithms process through from (e.g.) EXPR_1 through
>> EXPR_10, but leave an extra EXPR_1, then jump back to EXPR_2, leave an
>> extra EXPR_2, and so on.  I.e. they use the recursion backend like this:
>>
>> X
>> X X
>> X X X
>> X X X
>> X X X
>>    X X
>>      X
>>
>> I.e. it is sort of a backend linear multiplier.
>>
>> The _X macros use the backend in an exponential fashion--but those have
>> some usability issues.  I actually have a few combinations-of-both (i.e.
>> _PARAMETRIC_X--whatever that means) algorithms laying around somewhere
>> that are superior to the _X versions.
>>
>> In both cases, however, these algorithms trade some speed for headroom.
>> _PARAMETRIC is a little slower than normal, and _X is slower yet.
>>
> So the extra headroom can be used for the macro thats passed in, or for more
> repetitions, or both?

It depends on the algorithm.  For something like REPEAT, all of the 
calls to user-provided macros are already trampolined back to s + 1.

Playing with it a bit, I sort of misrepresented what the "parametric" 
algorithms do.  I haven't ever used them in real code, so I was sort of 
recalling a combination of the them and algorithms that I have laying 
around somewhere--which reminds me of why they got the name 
"parametric".  Here's what they /actually/ do....  When the end of the 
recursion backend is hit, the algorithm trampolines /itself/ back to s + 
1.  For example,

CHAOS_PP_EXPR_S(500)(CHAOS_PP_REPEAT_PARAMETRIC_S(
     500, 20, M
))

There isn't enough headroom here to directly produce the 20 repetitions, 
so the algorithm produces as many as it can, and then trampolines 
itself--which you will see if you run the above.  That result can be 
/resumed/ with an additional bootstrap

CHAOS_PP_EXPR_S(500)(
     CHAOS_PP_EXPR_S(500)(CHAOS_PP_REPEAT_PARAMETRIC_S(
         500, 20, M
     ))
)

and this can be done as many times as needed.  The "parametric" is short 
for /parametric resumption/ which is a piece of terminology I made up to 
describe the above scenario--re-bootstrapping the result by using it is 
a parameter again.  I know--not very good terminology here.

Regardless, however, the M will always be invoked with 501 in this scenario.

The _X algorithms, on the other hand are more complicated still.  They 
do the same sort of trampolined jump that the parametric algorithms do, 
but the use the recursion backend exponentially on the way.  However, 
they take an additional argument which is the size of a buffer at the 
end of the backend which it won't use.  They also don't trampoline their 
higher-order arguments.  For example,

CHAOS_PP_EXPR_S(500)(CHAOS_PP_REPEAT_X_S(
     500, 5, 20, M
))

The exponential here is sufficient to produce all 20 repetitions 
/without/ a parametric resumption.  However, notice that the M is 
invoked with s-values which are all over the place put never exceed 512 - 5.

And that is the flaw of these algorithms.  That behavior doesn't scale.  
What they need to do is take a /relative/ number of steps which they can 
use (not a number of steps left over at the end).  The exponential 
algorithms can get enormous numbers of steps extremely quickly.  The 
number is actually:

/f/(/s/, /?/, /p/, /b/, /?/) = /p/ * (1 - /b/^(/?/ - /s/ - /?/ - 1)) / 
(1 - /b/) - 1

where /p/ is the number of wrapping bootstraps, /b/ is the exponential 
base used by the algorithm, /?/ is LIMIT_EXPR which is 512 currently, 
and /?/ is the passed buffer size. The /?/ is global, so we have:

/g/(/s/, /?/, /p/, /b/) = /f/(/s/, /?/, /p/, /b/, 512)

The value of /b/ is algorithm-specific.  I believe it is always 2 (which 
can be increased fairly easily), but for REPEAT_X, I /know/ it is 2.  
So, for REPEAT_X we have:

/h/(/s/, /?/, /p/) = /g/(/s/, /?/, /p/, 2)

So, in the case above, we have /h/(500, 5, 1) = 62.  However, at the 
beginning with no buffer, we'd have /h/(1, 0, 1) which is

335195198248564927489350624955146153186984145514
809834443089036093044100751838674420046857454172
585692250796454662151271343847070298664248660841
2251521022

The number type that REPEAT_X uses cannot count that high, but the 
arbitrary precision arithmetic mechanism could /in theory/.

Of course, the above is ridiculously high.  Assuming infinite memory, if 
you generated one repetition per nanosecond, it would take about 3 x 
10^226 years to complete (if I did the math right).

So, obviously you don't need that many, but the what the algorithm 
should do is uses a relative depth so that the number of available steps 
is not dependent on s.  Instead, it would be something like:

/f/(/?/, /p/, /b/) = /p/ * (1 - /b/^(/?/ - 1)) / (1 - /b/) - 1

Where /?/ is now the number of backend steps that the algorithm is 
allowed to use.  So EXPR(REPEAT_X(10, n, M)) could generate something 
like 510 steps before trampolining without going past s + 10 - 1 in the 
backend.  Even something as low as 20 yields unrealistic numbers of 
steps (about 524286).

So, what these algorithms /should/ be are algorithms which allow 
parametric resumption but use either linear multipliers or exponential 
multipliers with relative upper bounds on the backend. The linear 
version would be faster, but the exponential version would yield a lost 
more steps.  The current _PARAMETRIC and _X algorithms don't do that.

Regards,
Paul Mensonides