Это С99 препроцессора полный Тьюринга?

ну макросы непосредственно не расширяются рекурсивно, но есть способы, которыми мы можем обойти это.

самый простой способ сделать рекурсию в препроцессоре-использовать отложенное выражение. Отложенное выражение-это выражение, которое требует дополнительного сканирования для полного расширения:

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

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

почему это важно? Ну, когда макрос сканируется и расширяется, он создает отключающий контекст. Этот отключающий контекст вызовет токен, который ссылается на текущий момент расширение макроса, который будет окрашен в синий цвет. Таким образом, как только он окрашен в синий цвет, макрос больше не будет расширяться. Вот почему макросы не расширяются рекурсивно. Однако отключающий контекст существует только во время одного сканирования, поэтому, отложив расширение, мы можем предотвратить окрашивание наших макросов в синий цвет. Нам просто нужно будет применить больше сканирований к выражению. Мы можем сделать это с помощью этого EVAL макро:

#define EVAL(...)  EVAL1(EVAL1(EVAL1(__VA_ARGS__)))
#define EVAL1(...) EVAL2(EVAL2(EVAL2(__VA_ARGS__)))
#define EVAL2(...) EVAL3(EVAL3(EVAL3(__VA_ARGS__)))
#define EVAL3(...) EVAL4(EVAL4(EVAL4(__VA_ARGS__)))
#define EVAL4(...) EVAL5(EVAL5(EVAL5(__VA_ARGS__)))
#define EVAL5(...) __VA_ARGS__

теперь, если мы хотим реализовать REPEAT макрос с помощью рекурсии, сначала нам нужно немного операторы инкремента и декремента для обработки состояния:

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

#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

Далее нам нужно еще несколько макросов, чтобы сделать логику:

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

теперь со всеми этими макросами мы можем написать рекурсивный REPEAT макрос. Мы используем REPEAT_INDIRECT макрос для рекурсивной ссылки на себя. Это предотвращает окрашивание макроса в синий цвет, так как он будет расширяться при другом сканировании(и с использованием другого контекста отключения). Мы используем OBSTRUCT здесь, который будет откладывать расширение в два раза. Это необходимо потому что условный WHEN уже применяется одно сканирование.

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

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

теперь этот пример ограничен 10 повторами, из-за ограничений счетчика. Точно так же, как счетчик повторов в компьютере будет ограничен конечной памятью. Несколько счетчиков повторения могут быть объединены вместе, чтобы обойти это ограничение, как и в компьютере. Кроме того, мы могли бы определить a FOREVER макро:

#define FOREVER() \
    ? \
    DEFER(FOREVER_INDIRECT) () ()
#define FOREVER_INDIRECT() FOREVER
// Outputs question marks forever
EVAL(FOREVER())

это будет пытаться вывести ? навсегда, но в конечном итоге остановитесь, потому что больше не применяется сканирование. Теперь вопрос в том, если мы дадим ему бесконечное количество сканирований, будет ли этот алгоритм завершен? Это известно как проблема остановки, и полнота Тьюринга необходима, чтобы доказать неразрешимость проблемы остановки. Итак, как вы можете видеть, препроцессор может действовать как полный язык Тьюринга, но вместо того, чтобы быть ограниченным конечной памятью компьютера, он вместо этого ограничен конечным числом применяемых сканирований.

Это Тьюринг полный в пределах (как и все компьютеры, так как они не имеют бесконечного ОЗУ). Проверьте виды вещей, которые вы можете сделать с Повышение Препроцессора.

редактировать в ответ на вопрос правки:

основное ограничение на Boost-это максимальная глубина расширения макроса, которая зависит от компилятора. Кроме того, макросы, реализующие рекурсию (FOR..., ПЕРЕЧИСЛЕНИЕ..., прием.) не являются действительно рекурсивными, они просто появляются таким образом благодаря куче почти идентичные макросы. В целом это ограничение ничем не отличается от максимального размера стека в фактически рекурсивном языке.

единственные две вещи, которые действительно необходимы для ограниченной полноты Тьюринга (Тьюринг-совместимость?) являются итерацией / рекурсией (эквивалентные конструкции) и условным ветвлением.

чтобы быть полным Тьюрингом, нужно определить рекурсию, которая может никогда не закончиться (их называют MU-рекурсивным оператором -- https://en.wikipedia.org/wiki/%CE%9C-recursive_function).

для определения такого оператора необходимо бесконечное пространство идентификаторов (в случае, если каждый идентификатор вычисляется конечное число раз), так как никто не может знать априори верхний предел времени, в котором находится результат. С конечным числом операторов внутри код нужно уметь проверять неограниченное количество возможностей.

таким образом, этот класс функций не может быть вычислен препроцессором C.

препроцессор C может вычислять только Сигма-рекурсивные операторы -- https://en.wikipedia.org/wiki/Primitive_recursive_function .

Подробнее см. курс вычислений Марвина л. Минского ( 1967) -- вычисление: конечные и бесконечные машины, Prentice-Hall, Inc. Энглвуд Клиффс, Нью-Джерси так далее.