Завершен ли препроцессор Тьюринга C99?

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

Из описания связанного выше проекта:

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

Ответ Пола Фульца II впечатляет и определенно ближе, чем я думал, что препроцессор когда-либо сможет получить, но это не настоящая машина Тьюринга. Препроцессор C имеет определенные ограничения, которые не позволяют ему выполнять произвольную программу, такую ​​как машина Тьюринга, даже если у вас есть бесконечная память и время. Раздел 5.2.4.1 спецификации C дает следующие минимальные ограничения для компилятора C:

• 63 уровня вложенности выражений в скобках в полное выражение
• 63 значащих начальных символа во внутреннем идентификаторе или имени макроса
• 4095 макроидентификаторов, одновременно определенных в одной блоке трансляции предварительной обработки
• 4095 символов в логической исходной строке

Приведенный ниже механизм счетчика требует определения макроса для каждого значения, поэтому предел определения макроса будет ограничивать количество раз, которое вы можете выполнять в цикле (EVAL(REPEAT(4100, M, ~)) приведет к неопределенному поведению). По сути, это ограничивает сложность программы, которую вы можете выполнить. Вложенность и сложность многоуровневых расширений также могут достигать одного из других ограничений.

Это принципиально отличается от ограничения «бесконечной памяти». В этом случае в спецификации конкретно говорится, что соответствующий стандартам компилятор C должен соответствовать этим ограничениям, даже если он имеет бесконечное время, память и т. Д. Любой входной файл, превышающий эти ограничения, может быть обработан непредсказуемым или неопределенным образом. (или категорически отвергнуты). Некоторые реализации могут иметь более высокие ограничения или вообще не иметь ограничений, но это считается «зависящим от реализации», а не частью стандарта. Возможно, можно будет использовать метод Пола Фульца II для реализации чего-то вроде машины Тьюринга на некоторой конкретной реализации компилятора, которая не имеет конечных ограничений, но в общем смысле «можно ли это сделать на любом произвольном, соответствующий стандартам препроцессор C99 ", ответ - нет. Поскольку ограничение здесь встроено в сам язык, а не просто побочный эффект нашей неспособности построить бесконечный компьютер, я говорю, что это нарушает полноту Тьюринга.

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

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

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

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

Чтобы быть полным по Тьюрингу, нужно определить рекурсию, которая может никогда не закончиться - их называют mu-рекурсивный оператор.

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

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

Препроцессор C использует алгоритм Дэйва Проссера (написанный Дэйвом Проссером для команды WG14 в 1984 г. ). В этом алгоритме макрос окрашивается в синий цвет в момент первого раскрытия; рекурсивный вызов (или взаимный рекурсивный вызов) не расширяет его, так как он уже был окрашен в синий цвет в момент, когда начинается первое раскрытие. Таким образом, с конечным числом строк предварительной обработки невозможно совершать бесконечные вызовы функций (макросов), что характерно для мю-рекурсивных операторов.

Препроцессор C может вычислять только сигма-рекурсивные операторы.

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

Это Тьюринг завершен в определенных пределах (как и все компьютеры, поскольку у них нет бесконечной оперативной памяти). Узнайте, что вы можете делать с помощью Boost Preprocessor.

Изменить в ответ на правки вопроса:

Основным ограничением Boost является максимальная глубина раскрытия макроса, зависящая от компилятора. Кроме того, макросы, реализующие рекурсию (FOR ..., ENUM ... и т. Д.), Не являются действительно рекурсивными, они просто появляются таким образом благодаря кучке почти идентичных макросов. В целом это ограничение ничем не отличается от максимального размера стека в рекурсивном языке.

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