Czy obliczenia oparte na constexpr są kompletne?

Wiemy, że metaprogramowanie szablonów C++ jest skończone, ale metaprogramowanie preprocesora nie jest .

C++11 daje nam nową formę metaprogramowania: obliczanie funkcji constexpr. Czy ta forma obliczeń Turinga jest kompletna? Myślę, że skoro rekurencja i operator warunkowy (?:) są dozwolone w funkcjach constexpr, byłoby, ale chciałbym, aby ktoś z większą wiedzą potwierdził.

Author: Community, 2012-02-09
Source

3 answers

Tl;dr: constexpr W C++11 nie był Turing-complete, ze względu na błąd w specyfikacji języka, ale ten błąd został rozwiązany w późniejszych wersjach standardu, a clang już implementuje poprawkę.

constexpr, jak określono w międzynarodowym standardzie ISO C++11, nie jest Turing-complete. Dowód szkicu:

  • każdy wynik constexpr funkcji f na określonym ciągu argumentów, a..., jest określony tylko przez wartości a...
  • każda wartość argumentu, która może być skonstruowana wewnątrz wyrażenia stałego, musi być typu dosłownego, który przez [basic.types]p10 jest albo:
    • typ skalarny,
    • a reference,
    • tablica typu literalnego, lub
    • typ klasy
  • każdy z powyższych przypadków ma skończony zbiór wartości.
    • dla typu skalarnego, bez wskaźnika, wynika to trywialnie.
    • aby wskaźnik lub odniesienie były używane w wyrażeniu stałym, musi być inicjowane przez adres lub stałe wyrażenie odniesienia, więc musi odnosić się do obiektu o statycznym czasie przechowywania, którego w dowolnym programie jest tylko skończona ilość.
    • dla tablicy, Wiązanie musi być stałą, a każdy element musi być zainicjowany wyrażeniem stałym, z którego wynika wynik.
    • dla typu klasy istnieje skończona liczba członów, a każdy element musi być typu literalnego i zainicjowany wyrażeniem stałym, z którego wynik / align = "left" /
  • zatem zbiór możliwych wejść a..., Które f Może Otrzymać jest skończony, więc każdy skończenie opisany constexpr system jest skończoną maszyną stanową, a zatem nie jest Turinga-zupełny.

Jednak od czasu publikacji standardu C++11 sytuacja uległa zmianie.

Problem opisany w odpowiedzi Johannesa Schauba na std::max() i std::min() nie constexpr został zgłoszony do Komitetu standaryzacji C++ jako problem podstawowy 1454. Na spotkaniu WG21 w lutym 2012 roku zdecydowaliśmy, że jest to wada standardu, a wybrana uchwała obejmowała możliwość tworzenia wartości typów klas ze wskaźnikami lub referencjami, które wyznaczają czasowniki. Pozwala to na gromadzenie i przetwarzanie nieograniczonej ilości informacji przez funkcję constexpr i jest wystarczające, aby constexpr ewaluacja Turing-complete (zakładając, że implementacja obsługuje rekurencję do nieograniczonej głębokości).

W celu w przypadku kompilatora, który implementuje proponowaną rozdzielczość wydania podstawowego 1454, napisałem symulator maszyny Turinga dla zestawu testów clanga:

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

Wersje Trunkowe zarówno g++ , jak i clang implementują rozwiązanie tego podstawowego problemu, ale implementacja g++obecnie nie jest w stanie przetworzyć tego kodu.

 55
Author: Richard Smith,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2017-05-23 12:13:46
 7
Author: Andrzej,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2012-02-08 22:48:35

Jeśli weźmiemy pod uwagę ograniczenia rzeczywistego komputera - takie jak skończona pamięć i skończona wartość MAX_INT - to oczywiście constexpr (a także cały C++) nie jest Turing-kompletny.

Ale jeśli usuniemy to ograniczenie - na przykład, jeśli pomyślimy o int jako całkowicie arbiterowej dodatniej liczbie całkowitej - to tak, constexpr część C++ będzie Turinga kompletna. Łatwo jest wyrazić dowolną część funkcji rekurencyjnej.

0, S (n) = N+1 i selektory I_n^m(x_1, ..., x_n) = x_m i superpozycja można oczywiście wyrazić za pomocą constexpr.

Prymitywną rekurencję można wykonać prosto: 

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));
}

I dla częściowej rekurencji potrzebujemy prostej sztuczki: 

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

Otrzymujemy więc dowolną funkcję rekurencyjną częściową jako constexpr.

 1
Author: mihaild,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2012-02-21 12:52:11