È la completa C99 preprocessore Turing?

Question

Dopo aver scoperto le capacità Boost preprocessore mi chiesi: E 'la C99 preprocessore Turing completa ?

In caso contrario, che cosa manca di non qualificarsi?

Answer 1

Qui è un esempio di abusare preprocessore per implementare una macchina di Turing. Si noti che uno script di build esterno è necessario per alimentare di nuovo l'uscita del preprocessore nel suo ingresso, in modo che il preprocessore in sé e per sé, non è Turing completo. Eppure, è un progetto interessante.

Dalla descrizione del progetto afore-linked:

  

il preprocessore è non Turing completo, almeno non se   il programma è pre-elaborata una sola volta. Questo è vero anche se   il programma è permesso di includere in sé. (Il motivo   che per un dato programma, il preprocessore ha solo finita   numero di stati, oltre a una pila costituito dai luoghi che   il file è stato incluso da. Questo è solo un automa push-down.)

La risposta di Paul Fultz II è abbastanza impressionante e sicuramente più vicino di quanto ho pensato che il preprocessore potrebbe mai arrivare, ma non è una vera e propria macchina di Turing. Il preprocessore C ha alcuni limiti che le impediscono di eseguire un programma arbitrario come una macchina di Turing poteva, anche se si ha memoria e il tempo infinito. Sezione 5.2.4.1 del C spec dà i seguenti limiti minimi per un compilatore C:

  

  
• 63 livelli di nidificazione di espressioni tra parentesi all'interno di una piena espressione
  
• 63 significativi personaggi iniziali in un identificatore interno o un nome di macro
  
• 4095 macro identificatori simultaneamente secondo un'unità di traduzione preelaborazione
  
• 4095 caratteri in una linea logica fonte
  

Il meccanismo contatore sotto richiede una definizione macro per ogni valore, pertanto il limite macro definizione limiterà quante volte si può ciclo (EVAL(REPEAT(4100, M, ~)) sarebbe resa comportamento indefinito). Questo mette in sostanza un limite alla complessità del programma che è possibile eseguire. La nidificazione e la complessità delle espansioni multilivello possono colpire uno degli altri limiti.

Questo è fondamentalmente diverso dal limitazione "memoria infinita". In questo caso, le specifiche dice specificamente che la standard conforme C compilatore è necessaria solo per conformarsi a questi limiti, anche se ha tempo infinito, memoria, ecc Qualsiasi file di input superare tali limiti possono essere trattati in modo imprevedibile o indefinito (o addirittura respinto). Alcune implementazioni possono avere limiti più alti, o senza limiti a tutti, ma che è considerato "l'attuazione specifici" e non fa parte dello standard. E 'possibile usare il metodo di Paolo Fultz II di implementare qualcosa di simile a una macchina di Turing su qualche implementazione specifica compilatore che non ha limiti finiti, ma in un senso generale di "si può fare in qualsiasi arbitraria, norme conformi C99 pre-processore", la risposta è no. Dal momento che il limite qui è incorporata nel linguaggio stesso e non semplicemente un effetto collaterale della nostra incapacità di costruire un computer di infinito, dico che rompe Turing completezza.

Answer 2

macro Beh non si espandono in modo ricorsivo direttamente, ma ci sono modi in cui possiamo risolvere questo.

Il modo più semplice di fare ricorsione nel preprocessore è quello di utilizzare un'espressione differita. Un'espressione differita è un'espressione che richiede più scansioni di 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 viene sottoposto a scansione e in espansione, si crea un contesto invalidante. Questo contesto disabilitazione causerà un token, che si riferisce alla macro attualmente in espansione, da verniciare blu. Così, una volta il suo dipinto di blu, la macro non sarà più espandersi. Questo è il motivo per cui le macro non si espandono in modo ricorsivo. Tuttavia, un contesto invalidante esiste solo durante una scansione, in modo da rinviare un'espansione possiamo evitare che i nostri macro di diventare dipinto di blu. Ci sarà solo bisogno di applicare più scansioni all'espressione. Possiamo farlo utilizzando questa macro 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__

Ora, se vogliamo implementare una macro REPEAT utilizzando la ricorsione, in primo luogo abbiamo bisogno di alcuni operatori di incremento e decremento di Stato manico:

#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 di un paio di macro per 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 una macro REPEAT ricorsivo. Usiamo una macro REPEAT_INDIRECT per riferirsi a se stesso in modo ricorsivo. Ciò impedisce la macro vengano verniciati blu, poiché si espanderà su una scansione diversa (e utilizzando un contesto disabilitazione diverso). Usiamo OBSTRUCT qui, che rinviare l'espansione due volte. Ciò è necessario perché il WHEN condizionale si applica una scansione già.

#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 è limitata a 10 ripetizioni, a causa delle limitazioni del contatore. Proprio come un contatore di ripetizione in un computer sarebbe stato limitato dalla memoria finita. contatori di ripetizione multiple possono essere combinate insieme per aggirare questa limitazione, 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 tenterà di ? uscita per sempre, ma alla fine fermarsi perché non ci sono più scansioni in atto. Ora la domanda è, se abbiamo dato un numero infinito di scansioni sarebbe questo completo algoritmo? Questo è noto come il problema della terminazione, e Turing equivalenza è necessario dimostrare l'indecidibilità del problema della terminazione. Quindi, come si può vedere, il preprocessore può agire come un linguaggio completo Turing, ma invece di essere limitata alla memoria finita di un computer su cui è invece limitato dal numero finito di scansioni applicata.

Answer 3

Per essere Turing completi, si ha la necessità di definire la ricorsione che non può mai finire - uno li chiama mu-ricorsive operatore .

Per definire un tale un operatore necessita uno spazio infinito di identificatori definiti (nel caso in cui ciascun identificatore viene valutato un numero finito di volte), non si può conoscere a priori un limite massimo di tempo in quale si trova il risultato. Con un numero finito di operatori all'interno delle esigenze codice uno per essere in grado di controllare un numero illimitato di possibilità.

questa classe di funzioni non può essere calcolato dal preprocessore C perché in C preprocessore v'è un numero limitato di macro definiti e ognuno viene espansa solo una volta.

Il preprocessore C utilizza il algoritmo di Dave Prosser (scritto da Dave Prosser per il WG14 squadra nel 1984). In questo algoritmo una macro è dipinta blu nel momento della prima espansione; una chiamata ricorsiva (o chiamata ricorsiva reciproco) non si espande, come è già stato verniciato blu nel momento in cui si avvia la prima espansione. Quindi, con un numero finito di linee di pre-elaborazione è impossibile effettuare chiamate infinite di funzioni (macro), che caratterizza gli operatori mu-ricorsivi.

Il preprocessore C può calcolare solo operatori sigma-ricorsive .

Per dettagli vedi il corso di calcolo di Marvin Minsky L. (1967) - calcolo: finito e infinito Macchine , Prentice-Hall, Inc. Englewood Cliffs, NJ etc

.

Answer 4

E 'di Turing completo entro i limiti (come lo sono tutti i computer dal momento che non hanno RAM infinito). Controlla il tipo di cose che puoi fare con Boost preprocessore .

Modifica in risposta a modifiche domanda:

La limitazione principale Boost è la profondità massima espansione macro che è compilatore specifico. Inoltre, le macro che implementano la ricorsione (FOR ..., ENUM ..., etc.) non sono veramente ricorsivo, hanno appena sembra che modo grazie ad una serie di macro quasi identiche. Nella foto grande, questa limitazione non è diverso che avere una dimensione massima dello stack in un linguaggio realmente ricorsiva.

Le uniche due cose che sono realmente necessarie limitato Turing-completezza (Turing-compatibilità?) Sono iterazione / ricorsione (costrutti equivalenti) e branching condizionale.