Quelle est la complexité générale de la construction d’une représentation canonique du langage?

Question

Il est souvent utile d’avoir une représentation canonique d’une langue (dans mon cas, c’est généralement une langue spécifique à un domaine); Cependant, je pense qu'il existe des limites strictes à l'expressivité des langues impliquées qui déterminent si une forme canonique peut être déterminée et / ou créée pour un programme arbitraire dans cette langue. Malheureusement, je suis incapable de trouver les références dont je me souviens (vaguement) avoir lu à ce sujet.

D'un côté, il semble raisonnable que la création d'une représentation canonique d'une langue présente une complexité comparable à celle de nombreux problèmes de graphes difficiles (par exemple: l'isomorphisme des graphes), mais d'un autre côté, des compilateurs tels que gcc, yhc et ghc utilisez des représentations intermédiaires pour générer des sorties dans différents formats (assemblage, javascript, etc.), il s'agit donc, au moins sous certaines formes, d'un problème résolu.

Quand est-il possible de déterminer / générer une forme canonique pour une langue donnée? (Dans quelle mesure cette langue peut-elle être expressive et quelle en est son influence sur l'utilité des formes canoniques?) Veuillez fournir des références ou des preuves si possible.

Éditer: Par exemple, un Langage ordinaire (par exemple : la forme «pure» des expressions rationnelles) ne peut pas exprimer beaucoup de choses identiques à celles d'un langue Turing-complete peut. En d’autres termes, vous ne pouvez pas écrire un serveur Web dans une langue courante, mais vous pouvez le faire avec lambda calcul). Ma question concerne les possibilités théoriques et a une réponse spécifique concernant la théorie de la complexité. Si j'ai un DSL qui doit être transmis à un autre système, il sera souvent avantageux de générer une forme canonique de ce code avant de le transmettre, car cela découplera les représentations indépendantes utilisées par les deux systèmes différents. Cependant , si P-Space complete ou NP-Complete permet de traduire une langue complète de Turing en une forme canonique, vous ne devez pas perdre de temps à essayer de construire une forme canonique. Une autre façon de le faire ou de réduire la complexité du langage à quelque chose qui peut être canonisé en temps polynomial.

Answer 1

Par "représentation canonique" Je suppose que vous voulez dire ce qui suit: Appelez les programmes P et Q équivalents s’ils "font la même chose". sur les mêmes entrées. " Faire la même chose " signifie que les programmes ont la même sortie et que les deux programmes s’arrêtent après un temps fini ou les deux entrent dans une boucle infinie. Cette relation d'équivalence définit les classes d'équivalence dans l'ensemble de tous les programmes. La " représentation canonique " d'un programme P est un programme P ' appartenant à la même classe d'équivalence, et vous exigez que tous les membres de la même classe d'équivalence aient la même représentation canonique.

Pour les langages complets de Turing, une représentation canonique calculable avec Turing vous permettrait de résoudre le Problème stoppant comme suit: écrivez d’abord un programme constitué d’une boucle infinie et trouvez sa représentation canonique Q . Ensuite, pour tout programme d'entrée P , commencez par le transformer mécaniquement en un programme P ₀ faisant la même chose, sauf qu'il ne produit aucune sortie. puis trouvez la représentation canonique P ₀ 'de ce programme. Si le résultat est Q , vous savez que P ₀ ne s’arrête pas, et donc P non plus. Sinon, P ₀ s'arrête, de même que P .

Pour encore plus de plaisir, lisez le travail de de Gregory Chaitin sur ce qu'il appelle " élégant " programmes.

Answer 2

Il me semble que la compilation en langage assembleur pourrait être qualifiée de traduction sous une forme canonique de manière pratique.