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

Question

Il est souvent utile d'avoir une représentation canonique d'une langue (dans mon cas, ce sont généralement des langues spécifiques au domaine); cependant, je crois qu'il y a des limites strictes sur 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, j'ai été incapable de trouver les références que je me rappelle (vaguement) lire à ce sujet.

D'une part, il semble raisonnable que la création d'une représentation canonique d'un langage soit d'une complexité comparable à celle de nombreux problèmes de graphes durs. (par exemple: isomorphisme graphique), mais d'un autre côté, iirc, les compilateurs comme gcc, yhc et ghc utilisent des représentations intermédiaires pour générer des sorties dans différents formats (assemblage, javascript, etc.), donc au moins sous certaines formes, 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 comment l'expressivité du langage influence-t-elle l'utilité des formes canoniques?) Veuillez fournir des références ou des preuves si cela est possible.

Edit: Par exemple, un Regular Language (par exemple: la forme 'pure' des expressions régulières) ne peut pas exprimer un grand nombre des mêmes choses qu'un Turing-complete language can. En d'autres termes, vous ne pouvez pas écrire un serveur web dans une langue régulière, mais vous pouvez le faire avec un calcul lambda). Ma question concerne les possibilités théoriques et a une réponse spécifique à la théorie de la complexité. Si j'ai un DSL qui doit être transmis à un autre système, il sera souvent utile 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 c'est P-Espace complet, ou NP-complet pour traduire un langage complet de Turing en une forme canonique, alors vous ne devriez pas perdre de temps à essayer de construire une forme canonique - soit trouver une autre façon de le faire , ou réduire la complexité du langage à quelque chose que peut canaliser en temps polynomial.

Answer 1

Par « la représentation canonique » Je suppose que vous parlez de ce qui suit: Appel des programmes P et Qéquivalent si elles « 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 tous les deux entrent dans une boucle infinie. Cette relation d'équivalence définit des 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 langues Turing-complet, une représentation canonique Turing calculable vous permettrait de résoudre le Halting Problem comme suit: d'abord écrire un programme consistant en une boucle infinie et trouver sa représentation canonique Q. Ensuite, pour tout programme d'entrée P, d'abord transformer mécaniquement en un programme P qui fait la même chose, sauf qu'il ne produit pas de sortie, puis trouver la représentation canonique P 'de ce programme .Si le résultat est Q, vous savez que P n'arrête pas, et par conséquent ni ne P. Sinon, P s'arrête, tout comme P.

Pour encore plus de plaisir, lisez quelques-unes des Gregory Chaitin's sur ce qu'il appelle des programmes «élégants».

Answer 2

Il me semble que la compilation dans un langage d'assemblage pourrait être catégorisée comme une traduction en forme canonique d'une manière pratique.