Qual é a complexidade geral de construir uma representação linguagem canônica?

Question

Muitas vezes, é útil ter uma representação canônica de uma linguagem (no meu caso eles geralmente são linguagens específicas de domínio); No entanto, eu acredito que há limites rígidos sobre a expressividade dos idiomas envolvidos que determinam se uma forma canônica pode ser determinada e / ou criado por um programa arbitrário nesse idioma. Infelizmente, eu fui incapaz de encontrar as referências que eu (vagamente) lembro de ter lido sobre isso em.

Por um lado, parece razoável que a criação de uma representação canônica de uma língua é de complexidade comparável a muitos problemas gráfico duro (por exemplo: Gráfico de isomorfismo), mas, por outro lado, IIRC, compiladores, como o gcc, YHC e ghc usam representações intermediários para gerar saídas em vários formatos (montagem, JavaScript, etc.), de modo que este é, pelo menos, em algumas formas, um problema resolvido.

Quando é possível determinar / gerar uma forma canônica para um determinado idioma? (Como expressiva pode ser que a linguagem, e como impacto linguagem expressividade a utilidade das formas canônicas?) Por favor, fornecer referências ou provas, se possível.

Editar: Por exemplo, um regular Idioma (por exemplo, : a forma 'pura' de expressões regulares) não pode expressar muitas das mesmas coisas que uma língua Turing-complete pode. Em outras palavras, você não pode escrever um servidor web em uma linguagem regular, mas você pode com cálculo lambda). Minha pergunta é sobre as possibilidades teóricas, e tem uma resposta específica relativa à teoria da complexidade. Se eu tiver uma DSL que precisa ser transmitido para outro sistema, ele vai muitas vezes ser benéfico para gerar uma forma canônica de que o código antes de transmiti-lo, uma vez que irá separar as representações independentes utilizadas pelos dois sistemas diferentes. No entanto , se for P-Space completa, ou NP-Completo de traduzir uma linguagem Turing-completa em uma forma canônica, então você não deve perder tempo tentando construir uma forma canônica - quer encontrar outra maneira de fazê-lo, ou reduzir a complexidade linguagem para algo que pode ser canonicalized em tempo polinomial.

Answer 1

Por "representação canônica" Eu suponho que você quer dizer o seguinte: programas de chamada P e Q equivalente se "fazer a mesma coisa" sobre as mesmas entradas. "Fazendo a mesma coisa" significa que os programas têm a mesma saída, e quer ambos os programas parar depois de um tempo finito ou ambos inserir um loop infinito. Esta relação de equivalência definir classes de equivalência no conjunto de todos os programas. A "representação canônica" de um programa P é um programa P ' pertencente à mesma classe de equivalência, e você exigir que todos os membros da mesma classe de equivalência têm o mesmo canônica representação.

Para linguagens Turing-completos, uma representação canônica Turing-computável lhe permitiria resolver o Travar Problema da seguinte forma: primeiro escrever um programa que consiste em um loop infinito e encontrar sua representação canônica Q . Então, para qualquer programa de entrada P , primeiro transformá-lo mecanicamente em um programa P ₀ , que faz a mesma coisa, exceto que ele não produz nenhuma saída, e em seguida, encontrar a representação canônica P ₀ ' deste programa. Se o resultado for Q , você sabe que P ₀ não parar, e, portanto, nem o P . Caso contrário, P ₀ paradas, e assim faz P .

Para se divertir ainda mais, ler alguns dos trabalho de Gregory Chaitin sobre o que ele chama de "elegante "programas.

Answer 2

Parece-me que a compilação em uma linguagem de montagem poderia ser categorizada como tradução para uma forma canônica de uma forma prática.