Является ли препроцессор C++ метапрограммирования полным по Тьюрингу?

Question

Я знаю, что метапрограммирование шаблона C++ завершено по Тьюрингу. То же самое относится и к метапрограммированию препроцессора?

Answer 1

Нет. Препроцессор C++ не допускает неограниченного состояния. У вас есть только конечное количество включенных / выключенных состояний плюс стек включения. Это делает его автоматом нажатия, а не машиной Тьюринга (при этом игнорируется также тот факт, что рекурсия препроцессора ограничена - как и рекурсия шаблона).

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

Answer 2

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

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

#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 повторами из-за ограничений счетчика. Также как счетчик повторов в компьютере будет ограничен конечной памятью. Несколько обходных счетчиков могут быть объединены вместе, чтобы обойти это ограничение, как в компьютере. Кроме того, мы могли бы определить FOREVER макрос:

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

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