Czy procesor wstępny C++ jest metaprogramowaniem Turing-complete?

Question

Wiem, że metaprogramowanie szablonu C++ to Turing-complete. Czy to samo dotyczy metaprogramowania preprocesora?

Answer 1

Nie. Procesor C++ nie zezwala na nieograniczony stan. Masz tylko skończoną liczbę stanów włączania/wyłączania oraz stos dołączania. To sprawia, że ​​jest to automat push-down, a nie turing (ignoruje to również fakt, że rekurencja preprocesora jest ograniczona - ale tak samo jest rekursja szablonu).

Jednakże, jeśli nieco zagiąć swoje definicje, jest to możliwe poprzez wielokrotne wywoływanie preprocesora - przez umożliwienie preprocesorowi wygenerowania programu, który ponownie wywoła preprocesor, a na zewnątrz pętli, to jest indeed possible to make a turing machine with the preprocessor. Połączony przykład używa C, ale powinien być łatwo adaptowalny do C++.

Answer 2

Cóż, makra nie rozszerzają się bezpośrednio rekurencyjnie, ale istnieją sposoby, aby temu zaradzić.

Najprostszym sposobem wykonywania rekurencji w preprocesorze jest użycie odroczonego wyrażenia. Odroczona ekspresja to wyrażenie wymagające więcej skanów do pełnego rozwinięcia:

#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 

Dlaczego jest to ważne? Cóż, gdy makro jest skanowane i rozwijane, tworzy kontekst wyłączający. Ten wyłączający kontekst spowoduje, że token, który odnosi się do aktualnie rozwijającego się makra, zostanie pomalowany na niebiesko. Tak więc, po pomalowaniu na niebiesko, makro nie będzie się już rozszerzać. Właśnie dlatego makra nie rozszerzają się rekurencyjnie. Jednak kontekst wyłączający istnieje tylko podczas jednego skanowania, więc odraczając rozszerzenie, możemy zapobiec pomalowaniu naszych makr na niebieskie. Będziemy musieli zastosować więcej skanów do wyrażenia. Możemy to zrobić za pomocą tego EVAL makro:

#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__ 

Teraz, jeśli chcemy wdrożyć REPEAT makro za pomocą rekurencji, najpierw musimy niektóre inkrementacja obsłużyć Stan:

#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 

Następnie musimy jeszcze kilka makr zrobić logicznych:

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

teraz z tych wszystkich makr możemy napisać rekurencyjną REPEAT makro. Używamy makra REPEAT_INDIRECT, aby odnieść się do siebie rekursywnie. Zapobiega to pomalowaniu makra na niebiesko, ponieważ rozszerza się na innym skanie (i przy użyciu innego kontekstu wyłączającego). Używamy tutaj OBSTRUCT, co spowoduje dwukrotne przesunięcie rozszerzenia. Jest to konieczne, ponieważ warunkowe WHEN stosuje już jeden skan.

#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 

Ten przykład jest ograniczony do 10 powtórzeń, z powodu ograniczeń licznika. Podobnie jak licznik powtórzeń w komputerze byłby ograniczony przez skończoną pamięć. Wiele powtórzeń liczników można połączyć, aby obejść to ograniczenie, tak jak w komputerze. Co więcej, możemy zdefiniować FOREVER makro:

#define FOREVER() \ 
    ? \ 
    DEFER(FOREVER_INDIRECT)()() 
#define FOREVER_INDIRECT() FOREVER 
// Outputs question marks forever 
EVAL(FOREVER()) 

to spróbuje wyjściu ? zawsze, ale w końcu zatrzymać, ponieważ nie ma więcej skanów obecnie stosowane. Teraz pytanie brzmi, czy daliśmy mu nieskończoną liczbę skanów, czy ten algorytm byłby kompletny? Jest to tak zwany problem zatrzymania, a kompletność Turinga jest niezbędna, aby udowodnić nierozstrzygalność problemu zatrzymania.Jak widać, preprocesor może działać jako kompletny język Turinga, ale zamiast ograniczać się do skończonej pamięci komputera, jest on ograniczony przez skończoną liczbę zastosowanych skanów.