¿Cuál es la complejidad general de construir una representación de lenguaje canónico?

Question

A menudo es útil tener una representación canónica de un idioma (en mi caso, generalmente son idiomas específicos del dominio); sin embargo, creo que existen límites estrictos en la expresividad de los idiomas involucrados que determinan si una forma canónica se puede determinar y / o crear para un programa arbitrario en ese idioma. Desafortunadamente, no he podido encontrar las referencias en las que recuerdo (vagamente) haber leído sobre esto.

Por un lado, parece razonable que crear una representación canónica de un lenguaje sea de una complejidad comparable a muchos problemas de gráficos duros (por ejemplo: isomorfismo de gráficos), pero por otro lado, iirc, compiladores como gcc, yhc y ghc use representaciones intermedias para generar salidas en varios formatos (ensamblaje, javascript, etc.), por lo que esto es, al menos en algunas formas, un problema resuelto.

¿Cuándo es posible determinar / generar una forma canónica para un idioma dado? (¿Cuán expresivo puede ser ese lenguaje y cómo la expresividad del lenguaje impacta la utilidad de las formas canónicas?) Proporcione referencias o pruebas si es posible.

Editar: Por ejemplo, un Idioma regular (p. ej. : la forma 'pura' de las expresiones regulares) no puede expresar muchas de las mismas cosas que un Lenguaje completo de Turing can. En otras palabras, no puede escribir un servidor web en un idioma normal, pero puede hacerlo con cálculo lambda). Mi pregunta es sobre las posibilidades teóricas y tiene una respuesta específica relacionada con la teoría de la complejidad. Si tengo un DSL que necesita ser transmitido a otro sistema, a menudo será beneficioso generar una forma canónica de ese código antes de transmitirlo, ya que eso desacoplará las representaciones independientes utilizadas por los dos sistemas diferentes. Sin embargo , si es P-Space complete o NP-Complete para traducir un lenguaje Turing-complete a una forma canónica, entonces no debería perder el tiempo tratando de construir una forma canónica, ya sea encontrar otra forma de hacerlo, o reducir la complejidad del lenguaje a algo que puede ser canonicalizado en tiempo polinómico.

Answer 1

Por " representación canónica " Supongo que se refiere a lo siguiente: Llame a los programas P y Q equivalentes si "hacen lo mismo". en las mismas entradas. "Hacer lo mismo" significa que los programas tienen la misma salida, y ambos programas se detienen después de un tiempo finito o ambos ingresan en un bucle infinito. Esta relación de equivalencia define las clases de equivalencia en el conjunto de todos los programas. La "representación canónica" de un programa P es un programa P ' que pertenece a la misma clase de equivalencia, y usted requiere que todos los miembros de la misma clase de equivalencia tengan la misma representación canónica.

Para los idiomas completos de Turing, una representación canónica computable de Turing le permitiría resolver el Problema de detención como sigue: primero escriba un programa que consista en un bucle infinito y encuentre su representación canónica Q . Luego, para cualquier programa de entrada P , primero transfórmelo mecánicamente en un programa P ₀ que haga lo mismo excepto que no produce salida, y luego busque la representación canónica P ₀ 'de este programa. Si el resultado es Q , sabe que P ₀ no se detiene y, por lo tanto, tampoco lo hace P . De lo contrario, P ₀ se detiene, y también lo hace P .

Para aún más diversión, lee algunos de los trabajos de Gregory Chaitin sobre lo que él llama " elegante " programas.

Answer 2

Me parece que compilar en un lenguaje ensamblador podría clasificarse como traducción a una forma canónica de manera práctica.