Boost logo

Boost :

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)( \
>> CHAOS_PP_DEC(c), s1, s2, m, __VA_ARGS__) \
>> /**/
>> #define DELINEATE_II(_, s, c, s1, s2, m, ...) \
>> 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, ...) \
>> /**/
> 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, ...) \
>> /**/
>> // 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 \
>> /**/
>> -> 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.

Paul Mensonides

Boost list run by bdawes at, gregod at, cpdaniel at, john at