Закончен ли препроцессор С99 Тьюринга? - PullRequest
64 голосов
/ 29 июня 2010

После обнаружения возможностей препроцессора Boost я задался вопросом: завершен ли процесс Тьюринга препроцессора C99?

Если нет, то чего не хватает, чтобы не подходить?

Ответы [ 4 ]

131 голосов
/ 10 мая 2012

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

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

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

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

31 голосов
/ 29 июня 2010

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

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

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

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

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

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

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

5 голосов
/ 26 мая 2016

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

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

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

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

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

Подробнее см. Курс вычислений Марвин Л. Минский (1967) - Вычисления: конечные и бесконечные машины , Prentice-Hall, Inc.

4 голосов
/ 29 июня 2010

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

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

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

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

...