Macro iteration (a limited form of recursion)?

Macro iteration (a limited form of recursion)?

Post by Max TenEyc » Fri, 10 Nov 2006 15:21:14


Background:

I need a fairly complex initializer for some table entries
and have a set of preprocessor function-like macros that
hide the conversion of the semantic specifications to
actual values. I can change some of the implementation
details without requiring that existing specifications be
re-written.

Intention:

I would like to hide even more of the implementation details
so I can add more features. One of the more important
requirements is to take a long list of specifications and
pass them to (modified versions of) the macros described above.

The invocation should look something like:

SUPER_TABLE( name, (spec...), (spec...)..., (spec...));

The problem:

The problem is that I need to work on each of the (spec...)
arguments in turn. I've picked up a method for detecting
the end of the argument list from a previous thread in this
news group, so I can assure that the processing terminates,
and I know how to strip one (spec...) out of the argument
list. But how do I get this to iterate?

I understand why simple recursion is disabled in macro
expansion. I even agree that that limitation is helpful
in many cases. However I happen to need a controlled form
of recursion to implement the syntax above. Is there any
way around the limit specified by the standard?

(I posted the equivalent question in comp.lang.c and have
gotten nothing useful after almost a week. A referral to
that news group would therefor not be useful.)
 
 
 

Macro iteration (a limited form of recursion)?

Post by David R Tr » Sat, 11 Nov 2006 09:24:08


I'm not completely sure this will work, but look up the '...'
and '__VA_ARGS__' features provided by the C preprocessor.
You use them to define a macro that can pick off the first N
arguments and pass the remaining ones to a recursive
invocation of the same macro (or perhaps a recursive helper
macro).

Something along the lines of:
#define LIST(a,...) (a) + LIST(__VA_ARGS__)

This may not work, though, because of the last invocation of
LIST() with no arguments.

-drt

 
 
 

Macro iteration (a limited form of recursion)?

Post by Max TenEyc » Sat, 11 Nov 2006 11:09:34


I found information on how to construct, built and have tested
a macro that I've named GT1ARG that returns 0 if there is only
one argument and 1 otherwise. It's based on a discussion in
this newsgroup from 2004. Assuming CONCAT concatenates its
two arguments after substitution, usage works something like:

#define LIST( ...) CONCAT(LIST_,GT1ARG(__VA_ARGS__))(__VA_ARGS__)
#define LIST_0(a) whatever...
#define LIST_1(a,...) LIST_0(a), \
CONCAT(LIST_,GT1ARG(__VA_ARGS__))(__VA_ARGS__)

The question I had was 'will the second invocation of LIST_1 be
expanded or will the recursion suppressor poison it?
 
 
 

Macro iteration (a limited form of recursion)?

Post by Jun Woon » Sat, 11 Nov 2006 11:10:31


...

Is the macro name being currently expanded not invoked?


``All opinions expressed are mine, and do not represent
the official opinions of any organization.''
 
 
 

Macro iteration (a limited form of recursion)?

Post by Max TenEyc » Sat, 11 Nov 2006 11:16:07


Normally no. That is precisely the problem I am trying
to work around.
 
 
 

Macro iteration (a limited form of recursion)?

Post by Jun Woon » Sat, 11 Nov 2006 11:24:14


...

Should read:

Isn't the macro name being currently expanded suppressed?

Sorry.

``All opinions expressed are mine, and do not represent
the official opinions of any organization.''
 
 
 

Macro iteration (a limited form of recursion)?

Post by Max TenEyc » Sat, 11 Nov 2006 11:47:39


That is OK. I understood what you were trying to say even if
I was slightly confused by the way you said it.

More precisely:

Isn't the expansion of any macro currently being expanded
suppressed when it is re-encountered during that expansion?

My reading suggests strongly that it is suppressed. This
is called poisoning the identifier in the GCC CPP internals
documentation and is precisely the problem I am trying to
work around.
 
 
 

Macro iteration (a limited form of recursion)?

Post by Jun Woon » Sat, 11 Nov 2006 12:19:11


Thanks.


Yes. With that question, I tried to point out what David R Tribble
missed in his answer.


Or called "blue-painted" in other places.


AFAICT there is no standard-conforming way to work around it. The only
way I can think now is depending on unspecified behavior occurred when
only a part of the macro being currently expanded comes from the
expansion of the macro itself.

``All opinions expressed are mine, and do not represent
the official opinions of any organization.''
 
 
 

Macro iteration (a limited form of recursion)?

Post by Jun Woon » Sat, 11 Nov 2006 12:23:28


...

Interesting. Could you elaborate on the way to implement it?


LIST_1 is blue-painted, which makes the second expansion be
suppressed.


``All opinions expressed are mine, and do not represent
the official opinions of any organization.''
 
 
 

Macro iteration (a limited form of recursion)?

Post by Max TenEyc » Sat, 11 Nov 2006 12:42:55


That technique is called the Socratic method. It works very well
with intelligent people... (apologies: my bad)
I was hopping for something using the ## operator, but I had reached
the same conclusion you had. Still it is better to ask than assume.

This is a case where the new standard (C89!) is providing more
protection than is desirable. There aught to be a way to say that a
particular function-like macro is to be expanded iteratively.
Something like:

#define :name(a, ...)

or

#define name( a; ...)
 
 
 

Macro iteration (a limited form of recursion)?

Post by Max TenEyc » Sat, 11 Nov 2006 13:56:19


The original idea was posted
by: Paul Mensonides
on: Sat, Nov 27 2004 3:27 am
in: comp.std.c

It took a bit of work to clean it up. The trick is to postpone
the expansion of a special macro until it has been passed through
at least one other expansion stage. It is almost all about
playing with the number of commas.

#define PASTE( a, b) a ## b
#define SELEC0( a, ...) a
#define SELEC1( a, ...) __VA_ARGS__
#define SELECT( a, ...) PASTE(SELEC, a)(__VA_ARGS__)

#define ARG0 0, 0
#define ARG2( a, b, ...) b
#define GT1ARG( ...) SELECT(0,SELECT(1,ARG2(__VA_ARGS,ARG0, 0),1,1)

Examples:

start: GT1ARG(x)
args: GT1ARG(...); __VA_ARGS__=>x
expand:SELECT(0,SELECT(1,ARG2(x,ARG0,0),1,1)
args: SELECT(a,...); a=>0; __VA_ARGS__=>SELECT(1,ARG2(x,ARG0,0),1,1)
expand:PASTE(SELEC,0)(SELECT(1,ARG2(x,ARG0,0),1,1))
args: PASTE(a, b)(SELECT(1,ARG2(x,ARG0,0),1,1)); a=>SELEC; b=>0
expand:SELEC##0(SELECT(1,ARG2(x,ARG0,0),1,1))
args: SELEC##0(SELECT(a,...); a=>1; __VA_ARGS__=>ARG2(x,ARG0,0),1,1)
expand:SELEC##0(PASTE(SELEC,1)(ARG2(x,ARG0,0),1,1))
args: SELEC##0(PASTE(a, b)(ARG2(x,ARG0,0),1,1)); a=>SELEC; b=>1
expand:SELEC##0(SELEC##1(ARG2(x,ARG0,0),1,1))
args: SELEC##0(SELEC##1(ARG2(a,b ,...),1,1)); a=>; b=>ARG0; ...
expand:SELEC##0(SELEC##1(ARG0,1,1))
paste: SELEC##0(SELEC1(ARG0,1,1)
rescan:SELEC##0(SELEC1(0,0,1,1))
args: SELEC##0(SELEC1(a,...); a=>0; __VA_ARGS__=>0,1,1
expand:SELEC##0(0,1,1)
paste: SELEC0(0,1,1)
args: SELEC0(a,...); a=>0; __VA_ARGS__=>1,1
expand:0

start: GT1ARG(x,y)
args: GT1ARG(...); __VA_ARGS__=>x,y
expand:SELECT(0,SELECT(1,ARG2(x,y,ARG0,0),1,1)
args: SELECT(a,...); a=>0; __VA_ARGS__=>SELECT(1,ARG2(x,y,ARG0,0),1,1)
expand:PASTE(SELEC,0)(SELECT(1,ARG2(x,y,ARG0,0),1,1))
args: PASTE(a, b)(SELECT(1,ARG2(x,y,ARG0,0),1,1)); a=>SELEC; b=>0
expand:SELEC##0(SELECT(1,ARG2(x,y,ARG0,0),1,1))
args: SELEC##0(SELECT(a,...); a=>1; __VA_ARGS__=>ARG2(x,y,ARG0,0),1,1)
expand:SELEC##0(PASTE(SELEC,1)(ARG2(x,y,ARG0,0),1,1))
args: SELEC##0(PASTE(a, b)(ARG2(x,y,ARG0,0),1,1)); a=>SELEC; b=>1
expand:SELEC##0(SELEC##1(ARG2(x,y,ARG0,0),1,1))
args: SELEC##0(SELEC##1(ARG2(a,b,...),1,1)); a=>; b=>y; ...
expand:SELEC##0(SELEC##1(y,1,1))
paste: SELEC##0(SELEC1(y,1,1))
args: SELEC##0(SELEC1(a,...); a=>y; __VA_ARGS__=>1,1
expand:SELEC##0(1,1)
paste: SELEC0(1,1)
args: SELEC0(a,...); a=>1; __VA_ARGS__=>1
expand 1

Hmm. Looking at it again shows me a couple places I can clean it
up a bit more, but that's off-topic...
 
 
 

Macro iteration (a limited form of recursion)?

Post by Jun Woon » Sat, 18 Nov 2006 15:27:53


[...]

Oh, I didn't know you post this.

It was interesting to follow how your GT1ARG macro is expanded to
different results depending on the number of arguments. Thanks.

<OT>
I noticed that what SELEC0 and SELEC1 do is essentially the same as
ARG2 does, which can be used to clean it up:

#define ARG0 0, 0
#define ARG2(a, b, ...) b
#define EARG2(...) ARG2(__VA_ARGS__, 1, 1)

#define GT1ARG(...) EARG2(ARG2(__VA_ARGS__, ARG0, 0))

GT2ARG(x, y) // expanded to 1
GT2ARG(x) // expanded to 0

</OT>


``All opinions expressed are mine, and do not represent
the official opinions of any organization.''
 
 
 

Macro iteration (a limited form of recursion)?

Post by akihabar » Sat, 18 Nov 2006 18:11:54


No it is not. "Poisoning" an identifier has a quite different
meaning in GCC. It means any later occurrence of that
identifier, not in a macro expansion, is a hard error.
 
 
 

Macro iteration (a limited form of recursion)?

Post by David R Tr » Sun, 19 Nov 2006 08:01:49


Ah, I missed that. Yes, 'LIST' is not expanded while in the midst
of already being expanded.

On the other hand if it were (hypothetically speaking), the final
invocation of 'LIST' would be 'LIST()', resulting in a blank 'a'
macro argument.

I suggest using a more powerful macro processor, such as m4,
for such things.

-drt
 
 
 

Macro iteration (a limited form of recursion)?

Post by Max TenEyc » Tue, 05 Dec 2006 23:46:50


Thank you for the clarification. I'll have to go over that
document more carefully.