C99 Preprocessor Turing завершится?

StackOverflow https://stackoverflow.com/questions/3136686

Вопрос

После обнаружения Повысить возможности препроцессора Я нашел интересно: это C99 Preprocessor Turing Complete Complete?

Если нет, что ему не хватает квалификации?

Это было полезно?

Решение

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

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

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

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

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

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

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

Другие советы

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

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

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

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

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

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

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

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

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

Подробнее см. Курс вычисления Marvin L. Minsky (1967) - вычисление: конечные и бесконечные машины, Prentice-Hall, Inc. Englewood Cliffs, NJ и т. Д.

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

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

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

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

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top