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 like this:

//This is the interface
#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))

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.