Завершены ли вычисления Тьюринга на основе constexpr?

Question

Мы знаем, что метапрограммирование шаблона C ++ завершено по Тьюрингу , но метапрограммирование препроцессора не .

C ++ 11 дает нам новую форму метапрограммирования: вычислениефункций constexpr.Является ли эта форма вычисления тьюрингово-полной?Я думаю, что поскольку рекурсия и условный оператор (? :) разрешены в функциях constexpr, это было бы так, но я хотел бы, чтобы кто-то с большим опытом подтвердил это.

Answer 1

tl; dr: constexpr в C ++ 11 не был завершен по Тьюрингу из-за ошибки в спецификации языка, но эта ошибка была устранена в более поздних версиях стандарта, и clang уже реализуетfix.

constexpr, как указано в международном стандарте ISO C ++ 11, не является полным по Тьюрингу.Доказательство эскиза:

• Результат каждой (* 1009) * * * * функции f для конкретной последовательности аргументов, a..., определяется только значениями a...
• Каждое значение аргумента, которое может быть построено внутри константного выражения, должно иметь литеральный тип, который по [basic.types]p10 является либо:
  • скалярным типом,
  • ссылкой,
  • массив литерального типа или
  • тип класса
• Каждый из приведенных выше случаев имеет конечный набор значений.
  • Для скалярного типа без указателя это следует тривиально.
  • Чтобы указатель или ссылка использовались в константном выражении, он должен быть инициализирован выражением адреса или ссылочной константы,поэтому он должен ссылаться на объект со статической продолжительностью хранения, для которого в любой программе имеется только конечное количество.
  • Для массива граница должна быть константой, и каждый член должен быть инициализирован выражением константы., из которого следует результат.
  • Для типа класса существует конечное число членов, и каждый член должен быть литерального типа и инициализироваться константным выражением, из которого следует результат.
• Таким образом, набор возможных входных данных a..., которые может получить f, конечен, поэтому любая конечно-описанная система constexpr является конечным автоматом и, следовательно, не является полной по Тьюрингу..

Однако со времени публикации стандарта C ++ 11 ситуация изменилась.

Описанная проблемав ответе Йоханнеса Шауба на std :: max () и std :: min () not constexpr было сообщено Комитету по стандартизации C ++ как основной вопрос 1454. На совещании WG21 в феврале 2012 г. мы решили, что этодефект в стандарте, и выбранное разрешение включало возможность создания значений типов классов с указателями или ссылочными элементами, которые обозначают временные объекты.Это позволяет накапливать и обрабатывать неограниченное количество информации с помощью функции constexpr и является достаточным для полной оценки Тьюринга constexpr (при условии, что реализация поддерживает рекурсию на неограниченную глубину).

Чтобы продемонстрировать полноту Тьюринга constexpr для компилятора, который реализует предлагаемое решение основной проблемы 1454, я написал симулятор Тьюринга для набора тестов clang:

http://llvm.org/svn/llvm-project/cfe/trunk/test/SemaCXX/constexpr-turing.cpp

В магистральных версиях g ++ и clang реализовано решение этой основной проблемы, но реализация g ++ в настоящее время не может обработать этот код.

Answer 2

Посмотрите на это.Я скомпилировал примеры, и они работают в GCC 4.6: Вычисления во время компиляции , Разбор строк во время компиляции - Часть I , Разбор строк во время компиляции - Часть II

Answer 3

Если мы примем во внимание ограничения реального компьютера - такие как ограниченная память и конечное значение MAX_INT - тогда, конечно, constexpr (а также весь C ++) не полон по Тьюрингу.

Но еслимы удалим это ограничение - например, если мы будем думать о int как о совершенно произвольном натуральном числе - тогда да, часть constexpr в C ++ будет завершена по Тьюрингу.Любую частично рекурсивную функцию легко выразить.

0, S (n) = n + 1 и селекторы I_n ^ m (x_1, ..., x_n) = x_m, и суперпозиция, очевидно, может быть выражена с помощью constexpr.

Примитивную рекурсию можно сделать прямо:

constexpr int h(int x1, ..., int xn, int y) {
  return (xn == 0) ? f(x1, ..., xn) : g(x1, ..., xn, y-1, h(x1, ..., xn, y-1));
}

А для частичной рекурсии нам нужен простой трюк:

constexpr int h(int x1, ... int xn, int y = 0) {
  return (f(x1, ... xn, y) == 0) ? y : h(x1, ..., xn, y+1);
}

Итак, мы получаем любую частичную рекурсиюфункционировать как консистр.