How do I write a recursive for-loop “repeat” macro

问题:

I want to force the preprocessor to do some automatic code generation for me. I don't need much: just a simple for-loop that contains another for-loop.[1]

I've read all that I can about macro expansion, and no longer giggle when the blue paint comes up. On a good day I can even explain why one needs multiple layers of macros to generate a function name with token pasting. I've actually got the for-loop working. But when it comes to putting a loop within a loop, I'm reduced to sprinkling randomly with DEFER, EVAL and OBSTRUCT and hoping for the best.

I will not be deterred by calls to reason. I really do want to do this with the standard C preprocessor. I promise that regardless of outcome, neither I, my employer, nor my heirs will sue you for technological malpractice. I promise I won't allow anyone else to maintain the code, or even view it, without appropriate safety glasses. Pretend if you'd like that I'm just asking out of theoretical interest. Or that my only other option is using M4: for if recursive macros in CPP are kinky, certainly M4 is the whole chicken.

The best reference material I've found is a 9-year-old Usenet thread: http://comp.std.c.narkive.com/5WbJfCof/double-cpp-expansion

It starts off-topic, is somewhat petty and combative in tone, and is way over my head. But I think the answer I seek is in there somewhere.

The next best is documentation for a CPP abusing header called Cloak: https://github.com/pfultz2/Cloak/wiki/C-Preprocessor-tricks,-tips,-and-idioms

It takes a somewhat different approach to iteration, and perhaps would serve my needs instead. But it's also a good overview.

Here's some cut-down code to show where I'm stuck.

repeat.h:

#define REPEAT(macro, times, start_n, next_func, next_arg, macro_args...) \
    _REPEAT_ ## times(macro, start_n, next_func, next_arg, ## macro_args)

#define REPEAT_ADD_ONE(macro, times, start_n, macro_args... )                    \
    REPEAT(macro, times, start_n, _REPEAT_ADD_ONE, 0, ## macro_args)

#define _REPEAT_ADD_ONE(n, ignore...) _REPEAT_ADD_ONE_ ## n

#define _REPEAT_0(args...)  /* empty */
#define _REPEAT_1(macro, n, func, i, args...) macro(n, ## args) 
#define _REPEAT_2(m, n, f, i, a...) m(n, ## a); _REPEAT_1(m, f(n, i), f, i, ## a)
#define _REPEAT_3(m, n, f, i, a...) m(n, ## a); _REPEAT_2(m, f(n, i), f, i, ## a)
#define _REPEAT_4(m, n, f, i, a...) m(n, ## a); _REPEAT_3(m, f(n, i), f, i, ## a)
#define _REPEAT_5(m, n, f, i, a...) m(n, ## a); _REPEAT_4(m, f(n, i), f, i, ## a)
#define _REPEAT_6(m, n, f, i, a...) m(n, ## a); _REPEAT_5(m, f(n, i), f, i, ## a)
#define _REPEAT_7(m, n, f, i, a...) m(n, ## a); _REPEAT_6(m, f(n, i), f, i, ## a)
#define _REPEAT_8(m, n, f, i, a...) m(n, ## a); _REPEAT_7(m, f(n, i), f, i, ## a)
#define _REPEAT_9(m, n, f, i, a...) m(n, ## a); _REPEAT_8(m, f(n, i), f, i, ## a)
#define _REPEAT_10(m, n, f, i, a...) m(n, ## a); _REPEAT_9(m, f(n, i), f, i, ## a)

#define _REPEAT_ADD_ONE_0 1
#define _REPEAT_ADD_ONE_1 2
#define _REPEAT_ADD_ONE_2 3
#define _REPEAT_ADD_ONE_3 4
#define _REPEAT_ADD_ONE_4 5
#define _REPEAT_ADD_ONE_5 6
#define _REPEAT_ADD_ONE_6 7
#define _REPEAT_ADD_ONE_7 8
#define _REPEAT_ADD_ONE_8 9
#define _REPEAT_ADD_ONE_9 10
#define _REPEAT_ADD_ONE_10 11

#define _REPEAT_ADD_0(x) x
#define _REPEAT_ADD_1(x) _REPEAT_ADD_ONE(x)
#define _REPEAT_ADD_2(x) _REPEAT_ADD_1(_REPEAT_ADD_ONE(x))
#define _REPEAT_ADD_3(x) _REPEAT_ADD_2(_REPEAT_ADD_ONE(x))
#define _REPEAT_ADD_4(x) _REPEAT_ADD_3(_REPEAT_ADD_ONE(x))
#define _REPEAT_ADD_5(x) _REPEAT_ADD_4(_REPEAT_ADD_ONE(x))
#define _REPEAT_ADD_6(x) _REPEAT_ADD_5(_REPEAT_ADD_ONE(x))
#define _REPEAT_ADD_7(x) _REPEAT_ADD_6(_REPEAT_ADD_ONE(x))
#define _REPEAT_ADD_8(x) _REPEAT_ADD_7(_REPEAT_ADD_ONE(x))
#define _REPEAT_ADD_9(x) _REPEAT_ADD_8(_REPEAT_ADD_ONE(x))
#define _REPEAT_ADD_10(x) _REPEAT_ADD_9(_REPEAT_ADD_ONE(x))

sample.c:

#include "repeat.h"

#define INNER_MACRO(inner, outer) if (inner == outer) printf("Match\n")
#define INNER_BLOCK  { if (inner == outer) printf("Match\n"); }

#define OUTER_MACRO_INNER_MACRO(outer) REPEAT_ADD_ONE(INNER_MACRO, 3, 0, outer)
#define OUTER_BLOCK_INNER_MACRO { REPEAT_ADD_ONE(INNER_MACRO, 3, 0, outer); }
#define OUTER_MACRO_INNER_BLOCK(outer) REPEAT_ADD_ONE(INNER_BLOCK, 3, 0, outer)
#define OUTER_BLOCK_INNER_BLOCK { REPEAT_ADD_ONE(INNER_BLOCK, 3, 0, outer); }

void outer_macro_inner_macro() {
    REPEAT_ADD_ONE(OUTER_MACRO_INNER_MACRO, 2, 1);
}

void outer_macro_inner_block() {
    REPEAT_ADD_ONE(OUTER_MACRO_INNER_BLOCK, 2, 1);
}

void outer_block_inner_macro() {
    REPEAT_ADD_ONE(OUTER_BLOCK_INNER_MACRO, 2, 1);
}

void outer_block_inner_block() {
    REPEAT_ADD_ONE(OUTER_BLOCK_INNER_BLOCK, 2, 1);
}

In sample.c I've shown four variations that come close to what I want. But none are quite there. Here's what I get as output with "cpp sample.c > out.c; astyle out.c;"

void outer_macro_inner_macro() {
    REPEAT_ADD_ONE(INNER_MACRO, 3, 0, 1);
    REPEAT_ADD_ONE(INNER_MACRO, 3, 0, 2);
}

void outer_macro_inner_block() {
    REPEAT_ADD_ONE({ if (inner == outer) printf("Match\n"); }, 3, 0, 1);
    REPEAT_ADD_ONE({ if (inner == outer) printf("Match\n"); }, 3, 0, 2);
}

void outer_block_inner_macro() {
    {
        if (0 == outer) printf("Match\n");
        if (1 == outer) printf("Match\n");
        if (2 == outer) printf("Match\n");
    }(1);
    {
        if (0 == outer) printf("Match\n");
        if (1 == outer) printf("Match\n");
        if (2 == outer) printf("Match\n");
    }(2);
}

void outer_block_inner_block() {
    { {
            if (inner == outer) printf("Match\n");
        }(0, outer);
        {
            if (inner == outer) printf("Match\n");
        }(1, outer);
        {
            if (inner == outer) printf("Match\n");
        }(2, outer);
    }(1);
    { {
            if (inner == outer) printf("Match\n");
        }(0, outer);
        {
            if (inner == outer) printf("Match\n");
        }(1, outer);
        {
            if (inner == outer) printf("Match\n");
        }(2, outer);
    }(2);
}

And here's the output I want to get instead:

void desired_results() {
   {
       if (0 == 1) printf("Match\n");
       if (1 == 1) printf("Match\n");
       if (2 == 1) printf("Match\n");
   };
   {
       if (0 == 2) printf("Match\n");
       if (1 == 2) printf("Match\n");
       if (2 == 2) printf("Match\n");
   };
}

Essentially, I can get things to work if I use a block as the outer loop body, but not if I use a function-like macro. But I need to use a macro with arguments so that the loop bodies can use the loop counter as a constant instead of as a variable.

The problem with the "macro"-"macro" manner is that the inner recursive call to REPEAT_ADD_ONE() is not expanded. The answer would seem to be deferring the expansion of the inner loop until after the outer loop is created, and then forcing another pass that expands the inner loop. But for some reason my "random monkey" approach to that hasn't yet produced a solution...

[1] Understatement intended.

回答1:

Vesa Karvonen's "Order" library/language can definitely do this for you. It implements unrestricted recursion and looping in the C preprocessor, and as a really cool bonus dresses it up with the nice concise syntax of a "proper" programming language (to clarify: this is not an alternative preprocessor, it just does a lot of token-pasting to keep its keywords short. It is still pure CPP).

It uses a rather different technique, converting your metaprograms to CPS and then passing them to a single loop construct that has potentially trillions of steps, and executes the metaprogram in a strictly linear fashion. Loops and recursive functions can therefore be nested as deeply as you like because they don't have separate drivers that need to interact and paint each other blue.

Yes really, someone implemented a full virtual machine and interpreter using CPP macros. It's intimidating.

(EDIT: try the archived version if Rosetta Code has stopped working for you too.)

回答2:

With help from the answers here (and studying P99, Chaos, Order, and Cloak) I think I have a reasonably simple and compact proof-of-concept(1). Since I wanted only "repeat" functionality rather than a full blown interpreter, I went with a somewhat different approach than those other solutions. Instead of creating generic "if", "while", or "when" macros, I instead directly used a series of "decrement" macros that expand to the desired macro plus a call to the macro for n-1.

#ifndef _REPEAT_H
#define _REPEAT_H

// Usage: REPEAT_ADD_ONE(macro, times, start_n, macro_args... )
//        Recursion allowed if inner macros use REPEAT_ADD_ONE_INNER().
//        This demo header only allows 3 layers of recursion and max n=10.
//        Sample code at bottom.

#define REPEAT_ADD_ONE(macro, times, start_n, macro_args... )           \
    _REPEAT_EXPAND_3(REPEAT_ADD_ONE_INNER(macro, times, start_n, ## macro_args))

#define REPEAT_ADD_ONE_INNER(macro, times, start_n, macro_args... )     \
    _REPEAT_ ## times(macro, start_n, _REPEAT_ADD_ONE, ## macro_args)

#define _REPEAT_0(args...)  /* empty */
#define _REPEAT_1(macro, n, func, args...) _REPEAT_DEFER(macro)(n, ## args)
#define _REPEAT_2(m, n, f, a...) _REPEAT_DEFER(m)(n, ## a); _REPEAT_1(m, f(n), f, ## a)
#define _REPEAT_3(m, n, f, a...) _REPEAT_DEFER(m)(n, ## a); _REPEAT_2(m, f(n), f, ## a)
#define _REPEAT_4(m, n, f, a...) _REPEAT_DEFER(m)(n, ## a); _REPEAT_3(m, f(n), f, ## a)
#define _REPEAT_5(m, n, f, a...) _REPEAT_DEFER(m)(n, ## a); _REPEAT_4(m, f(n), f, ## a)
#define _REPEAT_6(m, n, f, a...) _REPEAT_DEFER(m)(n, ## a); _REPEAT_5(m, f(n), f, ## a)
#define _REPEAT_7(m, n, f, a...) _REPEAT_DEFER(m)(n, ## a); _REPEAT_6(m, f(n), f, ## a)
#define _REPEAT_8(m, n, f, a...) _REPEAT_DEFER(m)(n, ## a); _REPEAT_7(m, f(n), f, ## a)
#define _REPEAT_9(m, n, f, a...) _REPEAT_DEFER(m)(n, ## a); _REPEAT_8(m, f(n), f, ## a)
#define _REPEAT_10(m, n, f, a...) _REPEAT_DEFER(m)(n, ## a); _REPEAT_9(m, f(n), f, ## a)
// ...

#define _REPEAT_ADD_ONE(n, ignore...) _REPEAT_ADD_ONE_ ## n
#define _REPEAT_ADD_ONE_0 1
#define _REPEAT_ADD_ONE_1 2
#define _REPEAT_ADD_ONE_2 3
#define _REPEAT_ADD_ONE_3 4
#define _REPEAT_ADD_ONE_4 5
#define _REPEAT_ADD_ONE_5 6
#define _REPEAT_ADD_ONE_6 7
#define _REPEAT_ADD_ONE_7 8
#define _REPEAT_ADD_ONE_8 9
#define _REPEAT_ADD_ONE_9 10
#define _REPEAT_ADD_ONE_10 11
// ...

#define _REPEAT_EMPTY()
#define _REPEAT_DEFER(token) token _REPEAT_EMPTY()

#define _REPEAT_EXPAND_3(args...) _REPEAT_EXPAND(_REPEAT_EXPAND(_REPEAT_EXPAND(args)))
#define _REPEAT_EXPAND(args...) args
// ...

#endif // _REPEAT_H

#ifdef SAMPLE_CODE
// to generate code:   cpp -DSAMPLE_CODE sample.c 
// or easier to read:  cpp -DSAMPLE_CODE sample.c > out.c; astyle out.c; less out.c
// to compile and run: gcc  -Wall -O3 -DSAMPLE_CODE sample.c -o sample

int printf(const char *format, ...);

#define BODY(i) printf("%d\n", i);
void simple(void) {
    REPEAT_ADD_ONE(BODY, 5, 1);
}

#define INNER(k, j, i) \
    printf("(%d, %d, %d)\n", i, j, k);          \
    if (i == j && j == k) printf("Match!\n")
#define MIDDLE(j, i) REPEAT_ADD_ONE_INNER(INNER, 2, 2, j, i)
#define OUTER(i) REPEAT_ADD_ONE_INNER(MIDDLE, 3, 0, i)
void recursive(void) {
    REPEAT_ADD_ONE(OUTER, 2, 1);
}

int main() {
    simple();
    recursive();
    return 0;
}

#endif // SAMPLE_CODE 

I still struggle to understand a lot of the subtleties, but as others pointed out the general rule is that no macro can expand itself. The way around this is to create a macro that expands just to the point where it would call itself, and then put a wrapper around this result to complete the expansion.

The (common) trick that I ended up using is to take advantage of the fact that a function-type macro only expands if it is immediately followed by parentheses. One can use a "defer" macro that puts an "empty" token between the called macro name and its parentheses, and then "expand" this as the argument to another macro.

Since expansion of the arguments takes place in a different context than the initial expansion, the initial macro will expand again. In my solution, one level of expansion is necessary for each level of potential recursion. If playing with the code to understand it, it can be useful to decrease the number of expansions to check the intermediate results.

Thanks for all the help!

(1) True, the standard for "reasonably simple" is quite loose when applied to recursive preprocessor macros. It is quite compact, though.

回答3:

P99 might provide you with what you are looking for. It has several types of macro iterators, simple ones like P99_UNROLL, P99_SER etc and a generic one P99_FOR.

回答4:

Im not sure I follow all of your macros there. This answer here(also here now as well) explains how to create a general purpose REPEAT macro, like this:

#define REPEAT(count, macro, ...) \
    WHEN(count) \
    ( \
        OBSTRUCT(REPEAT_INDIRECT) () \
        ( \
            DEC(count), macro, __VA_ARGS__ \
        ) \
        OBSTRUCT(macro) \
        ( \
            DEC(count), __VA_ARGS__ \
        ) \
    )
#define REPEAT_INDIRECT() REPEAT

This takes a count, a macro, and user data. Since the macro passed in is deferred, the REPEAT macro can be called again directly and recursively. So here is your OUTER and INNER repeat macros:

#define OUTER(i, j) { REPEAT(j, INNER, i) }
#define INNER(j, i) if (j == INC(i)) printf("Match\n");

EVAL(REPEAT(2, OUTER, 3))

This will output this:

{ 
    if (0 == 1) printf("Match\n"); 
    if (1 == 1) printf("Match\n"); 
    if (2 == 1) printf("Match\n"); 
}
{
    if (0 == 2) printf("Match\n"); 
    if (1 == 2) printf("Match\n"); 
    if (2 == 2) printf("Match\n");
}

Hopefully, this makes sense.