Is the C preprocessor Turing complete?

As we all know macros don't expand recursively, but there are two ways we can work around this. Both ways are complementary to each other.

First, we can make macros re-entrant(up to a certain recursion level) by detecting the recursion state of the macro and calling another macro. This is cumbersome because we have to write a macro for each recursion level.

The second way of doing recursion in the preprocessor is to use a deferred expression. A deferred expression is an expression that requires more scans to fully expand:

#define EMPTY()
#define DEFER(id) id EMPTY()
#define OBSTRUCT(id) id DEFER(EMPTY)()
#define EXPR(...) __VA_ARGS__

#define A() 123
A() // Expands to 123
DEFER(A)() // Expands to A () because it requires one more scan to fully expand
EXPR(DEFER(A)()) // Expands to 123, because the EXPR macro forces another scan

Why is this important? Well when macros are scanned and expanded, they are painted blue, which means they can no longer expand for that one scan; but when the preprocessor starts another scan all these blue painted macros are cleared, which means they can expand again. So what that means for us, is we can create multiple EXPR macros, which will let our deferred expression expand on different preprocessor scans:

#define CAT(a, ...) PRIMITIVE_CAT(a, __VA_ARGS__)
#define PRIMITIVE_CAT(a, ...) a ## __VA_ARGS__

#define EXPR_S(s) PRIMITIVE_CAT(EXPR_, s)
#define EXPR_0(...) __VA_ARGS__
#define EXPR_1(...) __VA_ARGS__
#define EXPR_2(...) __VA_ARGS__
#define EXPR_3(...) __VA_ARGS__
#define EXPR_4(...) __VA_ARGS__
#define EXPR_5(...) __VA_ARGS__
#define EXPR_6(...) __VA_ARGS__
#define EXPR_7(...) __VA_ARGS__
#define EXPR_8(...) __VA_ARGS__
#define EXPR_9(...) __VA_ARGS__

Now we could make an EXPR macro that is re-entrant, but for brevity of this wiki we won't do that. We will just keep track of the recursion state ourselves. Hence, why we defined an EXPR_S macro. This will invoke a different preprocessor scan for each recursion state. Futhermore, we can define increment and decrement operators to move through the state:

#define INC(x) PRIMITIVE_CAT(INC_, x)
#define INC_0 1
#define INC_1 2
#define INC_2 3
#define INC_3 4
#define INC_4 5
#define INC_5 6
#define INC_6 7
#define INC_7 8
#define INC_8 9
#define INC_9 9

#define DEC(x) PRIMITIVE_CAT(DEC_, x)
#define DEC_0 0
#define DEC_1 0
#define DEC_2 1
#define DEC_3 2
#define DEC_4 3
#define DEC_5 4
#define DEC_6 5
#define DEC_7 6
#define DEC_8 7
#define DEC_9 8

Now if we want to implement say a REPEAT macro, then we need a few more macros to do logic:

#define CHECK_N(x, n, ...) n
#define CHECK(...) CHECK_N(__VA_ARGS__, 0,)

#define NOT(x) CHECK(PRIMITIVE_CAT(NOT_, x))
#define NOT_0 ~, 1,

#define COMPL(b) PRIMITIVE_CAT(COMPL_, b)
#define COMPL_0 1
#define COMPL_1 0

#define BOOL(x) COMPL(NOT(x))

#define IIF(c) PRIMITIVE_CAT(IIF_, c)
#define IIF_0(t, ...) __VA_ARGS__
#define IIF_1(t, ...) t

#define IF(c) IIF(BOOL(c))

#define EAT(...)
#define EXPAND(...) __VA_ARGS__
#define WHEN(c) IF(c)(EXPAND, EAT)

Now with all these macros we can write a recursive REPEAT macro. We split the macro in two parts in the interface and implementation. This just makes it easier to set up any values that will be used several times, such as incrementing the recursion state and decrementing the repeat counter. Also we pass the OBSTRUCT macro in as the first parameter. This is just to make it easier and cleaner to write a deferred expression in the implementation. So instead of writing DEFER(WHEN)(n), we will just write WHEN _(n).

//This is the interface
//REPEAT_S(s, n, m, data...)
// s    - This is the current recursion state
// n    - This the number of repeats
// m    - This is macro to be called at each repeat: m(s, n, data...)
// data - data is passed to the macro, in addition to the counter and state.
#define REPEAT_S(s, n, m, ...) \
        REPEAT_I(OBSTRUCT(), INC(s), DEC(n), m, __VA_ARGS__)
//This is the implementation
#define REPEAT_INDIRECT() REPEAT_S
#define REPEAT_I(_, s, n, m, ...) \
        WHEN _(n) \
        ( \
            EXPR_S _(s)(REPEAT_INDIRECT _()(s, n, m, __VA_ARGS__) ) \
        ) \
        m _(s, n, __VA_ARGS__)

//An example of using this macro
#define M(s, i, _) i
EXPR_S(0)(REPEAT_S(0, 8, M, ~)) // 0 1 2 3 4 5 6 7

Now this example is limited to 10 recursion levels. Now exceeding this level will cause the algorithm to stop just like it would stop in a computer because of a stack overflow. Here is an example of a FOREVER macro:

//This is the interface
#define FOREVER_S(s) FOREVER_I(OBSTRUCT(), INC(s))

//This is the implementation
#define FOREVER_INDIRECT() FOREVER_S
#define FOREVER_I(_, s) \
    s, EXPR_S _(s)(FOREVER_INDIRECT _()(s))

//This could run forever
EXPR_S(0)(FOREVER_S(0))

Now the question is, if we gave it an infinite number of recursion levels would this algorithm complete? This is known as the halting problem, and turing completeness is necessary to prove the undecidability of the halting problem. So as you can see, the preprocessor can act as a turing complete language, but instead of being limited to the finite memory of a computer it is instead limited by the finite number of recursion depths defined.