Qual è la complessità generale della costruzione di una rappresentazione linguistica canonica?

Question

Spesso è utile avere una rappresentazione canonica di una lingua (nel mio caso di solito sono lingue specifiche del dominio); tuttavia, credo che ci siano limiti rigorosi all'espressività delle lingue coinvolte che determinano se una forma canonica può essere determinata e / o creata per un programma arbitrario in quella lingua. Sfortunatamente, non sono stato in grado di trovare i riferimenti che (vagamente) ricordo di aver letto su questo in.

Da un lato, sembra ragionevole che la creazione di una rappresentazione canonica di un linguaggio sia di complessità comparabile a molti problemi con grafi duri (ad esempio: isomorfismo grafico), ma d'altro canto, iirc, compilatori come gcc, yhc e ghc usare rappresentazioni intermedie per generare output in vari formati (assembly, javascript, ecc.), quindi questo è almeno in alcune forme, un problema risolto.

Quando è possibile determinare / generare una forma canonica per una determinata lingua? (Quanto può essere espressiva quella lingua e in che modo l'espressività della lingua influisce sull'utilità delle forme canoniche?) Fornire riferimenti o prove se possibile.

Modifica: Ad esempio, un Regular Language (ad es. : la forma "pura" di espressioni regolari) non può esprimere molte delle stesse cose che un Linguaggio completo di Turing can. In altre parole, non puoi scrivere un web server in una lingua normale, ma puoi farlo con il calcolo lambda). La mia domanda riguarda le possibilità teoriche e ha una risposta specifica relativa alla teoria della complessità. Se ho un DSL che deve essere trasmesso a un altro sistema, sarà spesso utile generare una forma canonica di quel codice prima di trasmetterlo, poiché ciò disaccoppierà le rappresentazioni indipendenti utilizzate dai due diversi sistemi. Tuttavia , se è P-Space completo o NP-Complete per tradurre una lingua completa di Turing in una forma canonica, allora non dovresti perdere tempo a cercare di costruire una forma canonica - trova un altro modo per farlo, o ridurre la complessità del linguaggio a qualcosa che può essere canonicalizzato in tempo polinomiale.

Answer 1

Per " rappresentazione canonica " Suppongo che intendi quanto segue: chiama i programmi P e Q equivalente se " fanno la stessa cosa " sugli stessi ingressi. " Fare la stessa cosa " significa che i programmi hanno lo stesso output ed entrambi i programmi si arrestano dopo un tempo finito o entrambi entrano in un ciclo infinito. Questa relazione di equivalenza definisce le classi di equivalenza nell'insieme di tutti i programmi. La "rappresentazione canonica" di un programma P è un programma P ' appartenente alla stessa classe di equivalenza e si richiede che tutti i membri della stessa classe di equivalenza abbiano la stessa rappresentazione canonica.

Per le lingue complete di Turing, una rappresentazione canonica calcolabile di Turing ti consentirebbe di risolvere il Halting Problem come segue: prima scrivi un programma costituito da un ciclo infinito e trova la sua rappresentazione canonica Q . Quindi, per qualsiasi programma di input P , prima trasformalo meccanicamente in un programma P ₀ che fa la stessa cosa, tranne per il fatto che non produce alcun output, e quindi trova la rappresentazione canonica P ₀ 'di questo programma. Se il risultato è Q , sai che P ₀ non si ferma, e quindi nemmeno P . Altrimenti, P ₀ si interrompe, e anche P .

Per divertirti ancora di più, leggi alcuni dei il lavoro di Gregory Chaitin su ciò che chiama " elegante " programmi.

Answer 2

Mi sembra che la compilazione in un linguaggio assembly possa essere classificata come traduzione in una forma canonica in modo pratico.