Re: [boost] [preprocessor] Variadics suggestion

Subject: Re: [boost] [preprocessor] Variadics suggestion
From: Paul Mensonides (pmenso57_at_[hidden])
Date: 2012-10-10 01:42:20

On 10/9/2012 6:07 PM, Dave Abrahams wrote:
>
>> A quick example:
>>
>> #include <chaos/preprocessor/arithmetic/dec.h>
>> #include <chaos/preprocessor/control/if.h>
>> #include <chaos/preprocessor/facilities/empty.h>
>> #include <chaos/preprocessor/punctuation/comma.h>
>> #include <chaos/preprocessor/recursion/basic.h>
>> #include <chaos/preprocessor/recursion/expr.h>
>> #include <chaos/preprocessor/tuple/eat.h>
>>
>> // interface:
>>
>> #define DELINEATE(c, sep, m, ...) \
>>      DELINEATE_S(CHAOS_PP_STATE(), c, sep, m, __VA_ARGS__) \
>>      /**/
>> #define DELINEATE_S(s, c, sep, m, ...) \
>>      DELINEATE_I(s, c, CHAOS_PP_EMPTY, sep, m, __VA_ARGS__) \
>>      /**/
>>
>> // implementation:
>>
>> #define DELINEATE_I(s, c, s1, s2, m, ...) \
>>      CHAOS_PP_IF(c)( \
>>          DELINEATE_II, CHAOS_PP_EAT \
>>      )(CHAOS_PP_OBSTRUCT(), CHAOS_PP_NEXT(s), \
>>          CHAOS_PP_DEC(c), s1, s2, m, __VA_ARGS__) \
>>      /**/
>> #define DELINEATE_INDIRECT() DELINEATE_I
>> #define DELINEATE_II(_, s, c, s1, s2, m, ...) \
>>      CHAOS_PP_EXPR_S _(s)(DELINEATE_INDIRECT _()( \
>>          s, c, s2, s2, m, __VA_ARGS__ \
>>      )) \
>>      m _(s, c, __VA_ARGS__) s1() \
>>      /**/
>>
>> // reusable:
>>
>> #define REPEAT(c, m, ...) DELINEATE(c, CHAOS_PP_EMPTY, m, __VA_ARGS__)
>> #define REPEAT_S(s, c, m, ...) \
>>      DELINEATE_S(s, c, CHAOS_PP_EMPTY, m, __VA_ARGS__) \
>>      /**/
> What's the point of showing REPEAT here?  It doesn't seem to be used
> below.  Are you just illustrating that you can build REPEAT and ENUM
> using the same foundation?
It is just a tacit illustration of generality and reusability. Doing the 
same ala Boost.Preprocessor has far greater implications. In fact, in 
Boost.Preprocessor, there are a relatively few number of core 
algorithms--each of which has its own recursion state.  Then there are a 
few derived algorithms which are hacked to look like they use one of 
those states.  Lastly, there are a bunch of algorithms implemented in 
terms of the more low-level ones.  None of those are reentrant.  The 
above redirection, on the other hand, has no usability consequences 
other than that a natively built REPEAT or ENUM would be /slightly/ 
faster due to not passing around and invoking the separators.

Chaos' recursion backend is just a bunch of macros that look like this:

#define EXPR_1(...) __VA_ARGS__
#define EXPR_2(...) __VA_ARGS__
#define EXPR_3(...) __VA_ARGS__
// ...

When a macro such as MACRO(args) is called (provided args is used in the 
replacement list without being an operand of # or ##), args is scanned 
for macro replacement once on "entry" to MACRO(where a disabling context 
on MACROdoes not yet exist) and again after MACRO(args) has been 
replaced by MACRO's (parametized) replacement list (where a disabling 
context on MACRO does exist).

What Chaos' does, fundamentally, is control /when/ a macro is 
invoked//.  Given a function-like macro A(args), DEFER(A)(args) causes 
the invocation of A to /not/ happen through one scan for macro 
replacement.  I.e. the result of scanning DEFER(A)(args) for macro 
replacement is A(args).  A subsequent scan of that result will cause 
A(args) to be replaced.  Chaos' then uses this to cause an algorithmic 
step to bootstrap into the next step.  For example, assuming it is going 
to continue, B(1, args) expands to something that looks like 
EXPR_2(B_ID()(2, args)) where B_ID() just expands to B when replaced 
(used to avoid blue paint).  When you say EXPR_1(B(1, args)), the scan 
on entry to EXPR_1 yields EXPR_2(B_ID()(2, args)).  When that sequence 
of tokens is scanned again, after EXPR_1(B(1, args)) is replaced, the 
disabling context for B no longer exists (though now one for EXPR_1 does 
exist). That scan proceeds to cause EXPR_2(B_ID()(2, args)) to expand 
and now the entire process is self-bootstrapping provided there are 
enough EXPR_s macros to terminate.

The actual algorithms in Chaos tend to be a lot more complicated than 
this.  For example, the REPEAT et al algorithms generate their 
repetitions this way, but trampoline all of the higher-order calls back 
to the beginning.  E.g. EXPR_s(REPEAT_S(s, 3, M)) pseudo-expands to M(s 
+ 1, 0) M(s + 1, 1) M(s + 1, 3) where the state parameter is always s + 
1. This type of thing occurs when the number of steps required by the 
algorithm is bounded by the input in a non-higher-order way (and when it 
isn't too complicated).  For example, something like 
EXPR_s(FOLD_LEFT_S(s, op, seq, x)) generates

op(s + 1, seq[n - 1], ... op(s + 1, seq[1], op(s + 1, seq[0],x)) ... )

prior to expanding any of it.  It can do this because the input sequence 
(not the higher-order op argument) determines the length of the algorithm.

Hence the name "Chaos".  That doesn't come from "random" or "messy".  It 
is a reference to chaos theory where a relatively simple set of rules 
and initial conditions can produce a complex result.  Aside from the 
enormous number of workarounds in Boost.Preprocessor, the complexity of 
Chaos' implementation is drastically higher than that of 
Boost.Preprocessor.  One has to know what they are doing when directly 
implementing an algorithm (rather than using those already provided).  
Under the right circumstances, with bad input, you can get bad output 
which is way larger than anything Boost.Preprocessor can generate and 
way larger than even template instantiation error messages.  In some 
cases, there is so much headroom that that we're talking death by memory 
exhaustion. I.e. assuming infinite memory, it is possibly to construct 
an invocation that won't terminate for millenia.

Assuming that they are used in order, the library can do a binary search 
to find the next available index (which the library calls s for 
"state").  This is like the "automatic recursion" in Boost.Preprocessor 
except that it is more efficient.  Though it isn't necessary, the 
library distinguishes between higher-order algorithms and 
non-higher-order algorithms.

A higher-order algorithm ALGO is natively invoked as EXPR(ALGO(...)) 
which deduces the state or EXPR_S(s)(ALGO_S(s, ...)) which does not.

Non-higher-order algorithms are implemented under what the library calls 
"bypass semantics".  They may not use higher-order algorithms in their 
implementation.  What they do is start at the end of the recursion 
backed (i.e. EXPR_512 or whatever it is right now) and go backward.  
Because these algorithms are non-higher-order, they cannot be 
reentrant.  A non-higher-order algorithm ALGO is natively invoked as 
ALGO(...) by "top-level" code or ALGO_BYPASS(s, ...) when being used by 
another non-higher-order algorithm.  The restrictions on algorithms 
operating under bypass semantics are such that "normal" algorithms can 
always deduce the state (i.e. the binary search doesn't break) and so 
they can assume that they have all of the remaining backend to use 
(sometimes creatively).  Higher-order algorithms, on the other hand, may 
use the non-higher-order algorithms.

The library goes on to make a distinction between algorithmic steps 
(i.e. related to EXPR_s and the recursion backend) and algorithmic entry 
points.  A call such as EXPR(REPEAT(3, M)) can have M reenter REPEAT 
around 500 times recursively.  However, while a large number of steps is 
sometimes necessary, that many entry points is not.  To that end, the 
library defines about 16 separate entry point thunks which which 
essentially translate AUTO_REPEAT(...) into EXPR(REPEAT(...)). However, 
there are only a low number of those that are shared over the entire 
library so one top-level call implemented entirely using the AUTO_ 
macros can only have a reentry depth of 16 at maximum--which is usually 
more than enough.  There are only a low number of these thunks because 
each AUTO_ macro has to replicate macros to produce enable them for that 
macro.  The replication could be avoid if the syntax was, for example, 
AUTO(REPEAT, ...) translated to EXPR(REPEAT(...)) though Chaos doesn't 
provide that.

>> #define ENUM(c, m, ...) DELINEATE(c, CHAOS_PP_COMMA, m, __VA_ARGS__)
>> #define ENUM_S(s, c, m, ...) \
>>      DELINEATE_S(s, c, CHAOS_PP_COMMA, m, __VA_ARGS__) \
>>      /**/
>>
>> // recursive:
>>
>> #define TTP(s, n, id) \
>>      template<CHAOS_PP_EXPR(ENUM( \
>>          CHAOS_PP_INC(n), class CHAOS_PP_EAT, ~ \
> Did CHAOS_PP_INC come in with CHAOS_PP_DEC?  I don't see an #include for
> it.
No.  I missed it.  It actually comes in (at least) via recursion/expr.h 
because that defines the NEXT(s) and PREV(s) macros which are 
implemented in terms of INC and DEC.
>>      ))> class id ## n \
>>      /**/
>>
>> CHAOS_PP_EXPR(ENUM(3, TTP, T))
>>
>> -> template<class> class T0 ,
>>      template<class, class> class T1 ,
>>       template<class, class, class> class T2
>>
>> Complicated?...yes.  But compare that to the implementation of
>> BOOST_PP_REPEAT.  Unlike BOOST_PP_REPEAT, however, this macro can be
>> recursively reentered about 500 times.  The actual implementations of
>> these in Chaos is far fancier.
> I went to look at the code and found the mercurial repo doesn't appear
> to contain most of chaos, which was a little confusing.  Just thought it
> would be worth telling people to look at the CVS.
I disabled the hg repo for the moment.  I was starting a new version, 
started debating whether to include a lambda mechanism, started playing 
with alternate lambda mechanisms, and ran out of time pending work I 
have to do for my actual job.  The library as it currently exists is in 
CVS and is stable.  If Chaos' integration into Boost proceeds, I will 
shelve the hg repository at Sourceforge, and develop the Boost vesion in 
a private hg repo pending Boost's git migration.  On the other hand, if 
Chaos' integration into Boost does not proceed, I will develop the next 
iteration of the library in the hg repo at Sourceforge.

Regards,
Paul Mensonides