How do I write a recursive for-loop "repeat" macro to generate C code with the CPP preprocessor?

Question

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.

Alex Celeste · Answer 1 · 2013-06-17T12:58:14.007

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.)

Thanks for the pointer. The source also seems to be available alongside Mensonides' Chaos library: http://chaos-pp.cvs.sourceforge.net/viewvc/chaos-pp/ — Nathan Kurz, Jun 18 '13 at 22:23

Nathan Kurz · Answer 2 · 2013-06-19T04:23:05.533

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.

score 2 · Answer 3 · answered Jun 16 '13 at 10:25

2

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.

answered Jun 16 '13 at 10:25

Jens Gustedt

76,821
6
102
177

Hi Jens --- Looks exciting, and I'll definitely check it out. The documentation is great! Appears that it takes the NARGS based approach, and does all of its processing on variadic args. Do you know offhand if the loop-within-a-loop works, and if it's possible for the macro of the inner loop to receive the outer loop's counter as an argument? – Nathan Kurz Jun 16 '13 at 12:06
@NathanKurz, nesting two loops that are based on the same primitive wouldn't work easily, I think. But if for use case it would be sufficient to combine `P99_FOR` with `P99_SER` (or similar) that should be possible. The only of these construct that has something like a loop counter is `P99_FoR`, but it should be possible to make that accessible to another inner iterative construct. – Jens Gustedt Jun 16 '13 at 14:27
I've looked into P99, but I don't want an external dependency, and it's hard to begin understanding just what is needed for P99_FOR and only needed for that. Everything is named very confusingly and haphazardly. – MarcusJ Nov 21 '21 at 07:03
@MarcusJ, sorry if you have that impression and that names are confusing you. `P99_FOR` is highly non-trivial, if it weren't I probably would not have provided it as an open source project in the first place, I think, but just posted some code on my blog. I think that implementing such a thing on your own is generally not a good idea, it is very time consuming and errorprone. – Jens Gustedt Nov 22 '21 at 09:37

score 1 · Answer 4 · edited May 23 '17 at 10:30

1

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.

edited May 23 '17 at 10:30

Community

1
1

answered Jun 17 '13 at 03:51

Paul Fultz II

17,682
13
62
59

Hi Paul --- Thanks a lot for answering, and thanks for the working example. I've read your page and your other answers here several times. Although I understand it line by line, I'm still confused by how the expansion works and how the indirection interacts with the (double) defer. But between your examples and Jen's P99 code I hope to figure it all out. Are there other resources you've found helpful? – Nathan Kurz Jun 17 '13 at 06:11
@NathanKurz The indirection is necessary to avoid getting a blue painted token. Even though the deferred macro is not evaluated it is scanned by the preprocessor and when it sees a token in its disabling context(say `REPEAT` again) it will paint it blue and the token can no longer expand. So, we put a `REPEAT_INDIRECT` macro there so the preprocessor doesn't see the `REPEAT` token, until another scan is applied, which will have a different disabling context, hopefully, without `REPEAT` in it. – Paul Fultz II Jun 17 '13 at 06:33
Also, the `OBSTRUCT`(or double defer) just means two scans are needed to fully expand the macro. So, `EXPAND(OBSTRUCT(macro))()` is equivalent to `DEFER(macro)()`. Its necessary for `REPEAT` because of the conditional. The `WHEN` macro will apply one scan to it. Basically, causing `OBSTRUCT(REPEAT_INDIRECT) ()` to become `DEFER(REPEAT_INDIRECT) ()`. Now if we just had `DEFER(REPEAT_INDIRECT) ()` instead, it would become `REPEAT` after the scan was applied, causing `REPEAT` to become painted blue. Does that make sense? – Paul Fultz II Jun 17 '13 at 06:58
@NathanKurz Also the only resource, I know of is the Chaos preprocessor library from Paul Mensonides. He invented most of these techniques, except they are more sophisticated. For example, the recursive macros uses a recursion state so only the number of scans needed are applied, which is more efficient than the `EVAL` macro which always applies lots of scans even if they are not needed. – Paul Fultz II Jun 17 '13 at 07:03

How do I write a recursive for-loop "repeat" macro to generate C code with the CPP preprocessor?

4 Answers4

Linked