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