Preprocessor recursion depth counting

[Mark Riphenburg]

Hello,

I'm working on a project where I need to count the current recursion depth of a macro to abstract recursion so that given instances don't collide. The idea is to provide say 8 instances of each re-enterable macro in the library so that the individual macros can more or less stack to an arbitrary nesting depth so code for example, can be written like:

int Var = mAdd( mMul( A, mAdd( B, mMul( C, D ) ) ) );
 

where mAdd and mMul are preprocessor macros that perform their operations and emit tokens.

what I have tried is something like:

#define mMul mNestLevel(Count,mMul))
#define _mMul( A, B ) ... _mNestLevel(Emit,Result)  // level 1 version
#define __mMul( A, B ) ... __mNestLevel(Emit,Result)  ...  // level 2 version
#define ___mMul( A, B ) ... __mNestLevel(Emit,Result)  ... // level 3 version
... continued for a set nesting limit
 

that is the rough idea of what I have tried - as pseudo code because I haven't gotten it working yet.

- each reentrant function has an object-like 'constructor' which decorates the function like version with the current nest depth ( as prepended '_' i.e. ___ is nest depth 3)

- each reentrant function returns it's value as _m NestLevel(Emit, Result) ..at the current nest level to keep mNestLevel from resolving so that it is marked used for the next nesting level

- mNestLevel uses the fact that if a version is still resolving, it will just be emitted directly without firing. a '_' is then prepended and the first version that actually fires is the current nest level.

- mNestLevel has 2 modes, controled by it's first parameter - Count and Emit. During count, it prepends '_' antil it reaches a level that will acutally fire then it fires the Fn. Emit mode is a wrapper for the return value of the function being 'executed'

The problem is in the mNestLevel macro. I haven't been able to get it to work right. Does anyone have any ideas for a macro that can count the current nesting level? The problems I have been having are that what I've tried has always been resolving completely to nest level 0 or not at all.

Before I get a bunch of 'why do you want to do that?' spam, It is because it would allow fully recursive list processing at compile time. In an elegant syntax similar to:

mForEach( (A,B,C,D,mMoreList),
          Do( 
             mIfElse( mIsNumeric(Elem),
                      mIndex(Elem, mOtherList),
                      Elem)
             )
         )
 

I'm currently using expressions similar to that to do a variety of things like fill the gaping holes in template partial specialization. Right now, I'm having to select operations that aren't being used somewhere else in the expression, or manually select a free nest level version. If get this recursion abstraction working, any standard preprocessor can be turned into something getting fairly close to a lisp engine just by including one file.


Thanks for reading, I've been stuck on this piece for a couple days now. If anyone has a solution it would help greatly.

-
Mark

[donbock]

I'm having trouble understanding what you are trying to accomplish.

What would be the final preprocessor output for the example you gave:

int Var = mAdd( mMul( A, mAdd( B, mMul( C, D ) ) ) );

[Mark Riphenburg]

o, sorry, I was a bit overly synoptic there. if:
#define A 5
#define B 3
#define C 2
#define D 4
int Var = 55; emitted as a token i.e. (5##5)
I see the first mAdd is missing its second parameter which gets resolved to a 0 token

Ironically, the problem i'm having with counting the nesting levels is that - (at least MSVC 2005) is that the nesting control logic is getting resolved completely even if it is nested. Whereas, given:
#define mMyFn(A) A
mMyFn(mMyFn(hello))

I would expect failure due to recursion on the nested mMyFn and pass it unexpanded yeilding 'mMyFn(hello)' instead of the fully expanded 'hello'. Some expressions are allowed to recurse and some are not under MSVC (perhaps in all standard PPs) and it isn't clear to me what factors determine the failure/success cases.

In the mAdd( mMul( A, mAdd( B, mMul( C, D ) ) )/*,0*/ ) example. The intended expansion is:
_mAdd( _mMul( A, __mAdd( B, __mMul( C, D ) ), 0 )

where the object-like macros mAdd and mMul count the nesting level and prepend it to fn name to trigger actual invocation of the appropriate nesting level aware version.

Here is a code clipping of stage 4 of one of the nesting level counting variations I have tried:

#define NL4( Mode, Fn ) NL4##Mode(Fn) //the mode selector
#define NL4Peek(Fn) Deepen(Fn) //the result of the nest test - echoed for parent caller
#define NL4Test(Fn) mMGlue4(NL4_,NL3(Peek,##Fn)) //perform a term test
#define NL4_NL3(x,Fn) NL4_Call##Fn //failed nest test - call Fn from this level
#define NL4_Call(Fn,...) ____##Fn##__VA_ARGS__
#define NL4_Deepen(Fn) NL3(Test,Fn ) //successful nest test - iterate to next level
#define NL4Return(RVal) NL4ReturnDP##RVal //return values of all functions are wrapped in NL(Emit,(RVal)) form
#define NL4ReturnDP(...) __VA_ARGS__ //remove the paren and emit the actual value

That cascades through all stages until it finds one that doesn't resolve - because the Peek mode fails returning (at this stage), the token NL4_NL3(_,_) instead of Deepen(Fn). This variation attempt failed because it is always able to cascade successfully to level 1, resulting in _##mAdd invocation. I not able to keep current nest level version of NL from resolving, even if _mAdd returns its value wrapped in a recursive call to NL i.e. NL1( Return, RVal )

In my latest approach, I am using a trait system to determine if an argument is a function or not, and if it is, how many arguments it has. I can also detect if an argument is parenthised and I can separate a single argument into its function Name and its invocation, so I can walk an expression from left to right and determine what each part is. i.e.
mTraitExp( mAdd( mMul( A, mAdd( B, mMul( C, D ) ) ), 0 ) )

emits: Fn(mAdd), _LPrn_, Fn(mMul), _LPrn_, NotDef(A), Fn(mAdd), _LPrn_, NotDef(B), Fn(mMul), LPrn, NotDef(C), NotDef(D), _RPrn_, _RPrn_, _RPrn_, NotDef(0), _RPrn_

the function identifiers in this scheme are inactive so don't resolve. From that I can create a final resolving expression of:
_mAdd( __mMul( A, ___mAdd( B, ____mMul( C, D ) ) ), 0 )
where the depth level is increased by one for each successive expression, but it isn't nesting level counting. That attempt is almost feasible but linking nest level to function chain length causes it to grow too quickly for long chains and it requires that the function primitives not reference any other top level function primitives within their definition.

;)
-Mark Riphenburg

[donbock]

It is probably just my lack of imagination, but I can't think of any way to accomplish your desire using only standard preprocessor features. Do you have any reason to believe it is possible?

Maybe you need a custom preprocessor that is hard-coded to do this nesting level stuff for you.

[Mark Riphenburg]

lol, dang. I was hoping someone could solve it for me ;). No I haven't seen it done before. The basic reason I think its possible is that I believe the preprocessor has more than enough qualities to classify it as universally computational. I think that means I just haven't been clever enough to solve it yet. ...that and my trait system is a partial solution already.

I haven't seen anyone do preprocessor search functions either, but I manage that with:

#define mMTrait_Animal_dog 1,1,
#define mMTrait_Animal_cat 1,1,
#define mMTrait_Animal_horse 1,1,
#define mMTrait_Thing_car 1,1,
#define mMTrait_Thing_house 1,1,
#define mMTrait_Thing_spoon 1,1,
#define mMTrait_Thing_fork 1,1,

#define mLStuff dog, cat, horse, tree, car, house

mListSelectTrait( Animal, mLStuff, spoon, fork, ball )
emits: dog, cat, horse

mListSelectTrait( Thing, mLStuff, spoon, fork, ball )
emits: car, house, spoon, fork

Some of the stuff I can do easily in the preprocessor would be difficult in C++ because it has elements of Prolog and Lisp. It becomes more relevant the more complex the descriptions become which is why I'm trying to abstract nesting in the first place.

Thanks for reading,

Mark Riphenburg

[Mark Riphenburg]

@Mark Riphenburg
I solved it! ;)

Its now crazy-recursive. It ends up that macros can recurse or repeat to arbitrary depth. You just have to define a list of unique identifiers that act as an anchor point for each level of recursion. In effect, it acts as a translation
from vertical repetition:
fn(fn(fn(fn(...))))
to horizontal repetition:
fn()fn()fn()fn()...
horizontal repetition is legal and has almost no restictions.

The recursion anchor gets embedded within a fixed location in the overall expansion so it acts like a variable as in

NL0 = Fn( NL1 = Fn( NL2 = Fn( NL3 =Fn( ... ) ) ) )

Fn(NL1) Fn(NL2) Fn(NL3) Fn(NL...) ...

[donbock]

Here's an example of how to create your own specialized preprocessor: C Preprocessing with TCL
(Jonathan S. Arney, Dr. Dobbs Journal, August 1998, pp 46-49,91)

[Mark Riphenburg]

Thanks,

Interesting. I have been dealing with the preprocessor stage of compilation quite a bit lately. My conclusions are , and always have been, that the C/CPP code generation cycle is a hack based on antiquated kludges like make.
What I am doing is developing protocols for making the process recursively object oriented. The end result being serializable code that can be transmitted, and compiled remotely with nothing but a tiny client that sits on top of the remote compiler/linker. To do this, the concept of file objects has to be introduced. There is no good reason that C++ can't have the same serialization qualities as java while at the same time having improved speed, generality, extensibility and folding.

I think grafting on additional partial solutions, like tcl are a step away from an elegant recursive solution, even if they add a few extra features. Frankensteinian grafting is a very trendy way to program atm, so I'm sure its not without its merits.