Il preprocessore C++ metaprogrammazione Turing-complete?

Question

So che la metaprogrammazione del modello C++ è completa con Turing. La stessa cosa vale per la metaprogrammazione del preprocessore?

Answer 1

No. Il preprocessore C++ non consente lo stato illimitato. Hai solo un numero finito di stati on/off, più uno stack di inclusione. Questo lo rende un automa push-down, non una turing machine (questo ignora anche il fatto che la ricorsione del preprocessore è limitata - ma lo è anche la ricorsione dei template).

Tuttavia, se si piegano le definizioni un po ', ciò è possibile invocando il preprocessore più volte - consentendo al preprocessore di generare un programma che richiama il preprocessore e, eseguendo il loop esternamente, è indeed possible to make a turing machine with the preprocessor. L'esempio collegato usa C, ma dovrebbe essere facilmente adattabile in C++.

Answer 2

Le macro di pozzo non si espandono direttamente in modo ricorsivo, ma ci sono modi in cui possiamo ovviare a questo problema.

Il modo più semplice di eseguire la ricorsione nel preprocessore consiste nell'utilizzare un'espressione differita. Un'espressione posticipata è un'espressione che richiede più scansioni per espandersi completamente:

#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 

Perché è importante? Bene, quando una macro è scansionata e in espansione, crea un contesto disabilitante. Questo contesto di disabilitazione causerà la colorazione blu di un token, che si riferisce alla macro attualmente in espansione. Quindi, una volta dipinto in blu, la macro non si espanderà più. Questo è il motivo per cui le macro non si espandono in modo ricorsivo. Tuttavia, un contesto di disabilitazione esiste solo durante una scansione, quindi rinviando un'espansione possiamo impedire che i nostri macro diventino blu. Dovremo solo applicare più scansioni all'espressione. Possiamo farlo utilizzando questo EVAL macro:

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

Ora, se vogliamo realizzare un REPEAT macro utilizzando la ricorsione, in primo luogo abbiamo bisogno di alcuni operatori di incremento e decremento per gestire lo stato:

#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 

Poi abbiamo bisogno un paio di macro da fare logica:

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

Ora con tutte queste macro possiamo scrivere la ricorsiva REPEAT macro. Utilizziamo una macro REPEAT_INDIRECT per fare riferimento a se stessa in modo ricorsivo. Ciò impedisce che la macro venga dipinta di blu, poiché si espanderà su una scansione diversa (e utilizzando un diverso contesto di disabilitazione). Qui viene utilizzato OBSTRUCT, che rinvierà l'espansione due volte. Questo è necessario perché il condizionale WHEN applica già una scansione.

#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 

Ora questo esempio è limitato a 10 ripetizioni, a causa delle limitazioni del contatore. Proprio come un contatore di ripetizioni in un computer sarebbe limitato dalla memoria finita. È possibile combinare più contatori di ripetizioni per risolvere questo limite, proprio come in un computer. Inoltre, potremmo definire una macro FOREVER:

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

Questo cercherà di uscita ? per sempre, ma finirà per fermarsi perché non ci sono più scansioni in atto. Ora la domanda è, se gli avessimo dato un numero infinito di scansioni, questo algoritmo sarebbe completo? Questo è noto come il problema dell'arresto e la completezza di Turing è necessaria per dimostrare l'indecidibilità del problema dell'arresto.Quindi, come potete vedere, il preprocessore può agire come un linguaggio completo di Turing, ma invece di essere limitato alla memoria finita di un computer è invece limitato dal numero finito di scansioni applicate.