Estou interessado em compiladores verificados formalizados na teoria do tipo Martin-Löf, ou seja, Coq / Agda. No momento, escrevi um pequeno exemplo de brinquedo. Com isso, posso provar que minhas otimizações estão corretas. Por exemplo, adições com zero podem ser eliminadas, ou seja, expressões como "x + 0".
Existem otimizações difíceis de executar com um compilador regular, que serviriam como um bom exemplo? É possível provar certas propriedades de um programa que permitem otimizações que não são possíveis de serem executadas com um compilador regular? (ou seja, sem a inferência possível com um provador de teoremas)
Eu estaria interessado em idéias ou exemplos e também em referências sobre o tópico.
Uma questão relacionada: Provas de correção do compilador
edit: Como Tsuyoshi bem comentou: Estou procurando técnicas de otimização que são difíceis de implementar se um compilador é escrito em (digamos) C, mas mais fácil de implementar se um compilador é escrito em (digamos) Coq. Enquanto o Agda compila para C (via haskell), é possível fazer tudo o que é possível no Agda e também no C. Provavelmente, o único benefício de provadores de teoremas como Coq / Agda é que o compilador e as otimizações podem ser verificados.
edit2: Conforme sugerido por Vijay DI, escreva o que li até agora. Eu me concentrei principalmente em Xavier Leroy e no projeto CompCert no INRIA (acho que há um artigo de 80 páginas que é uma boa leitura). Um segundo interesse estava no trabalho de Anton Setzer em programas interativos. Eu achava que talvez o trabalho dele pudesse ser usado para provar propriedades sobre programas de IO e bisimulação de programas de IO. Obrigado por mencionar Sewell. Eu ouvi sua palestra "Contos da selva" no ICFP e li talvez 2-3 de seus artigos. Mas não olhei especificamente para o trabalho dele e de seus co-autores.
Ainda não descobri por onde começar ou procurei artigos sobre como otimizar compiladores; por exemplo, quais otimizações seria interessante observar na configuração de um compilador verificado.
Respostas:
este artigo de Yves Bertot, Benjamin Gr´egoire e Xavier Leroy constrói um compilador otimizador para uma linguagem semelhante a C baseada puramente na especificação Coq. alguma desta tecnologia é aparentemente utilizada no compilador CompCert C .
Uma abordagem estruturada para provar otimizações do compilador com base na análise de fluxo de dados
considera a correção de duas otimizações, propagação constante (CP) e eliminação de subexpressão comum (CSE), seção 4. essas otimizações são mais avançadas do que aquelas associadas aos compiladores não baseados em Coq para o mesmo idioma. veja por exemplo isso gráfico de referência em comparação com o gcc. (o compilador baseado em Coq é presumivelmente mais lento para compilar, embora isso raramente seja mencionado!)
no entanto, no final do artigo, eles observam que existem algumas otimizações do compilador em compiladores reais que não podem ser modeladas em sua estrutura.
otimização aprimorada não é o único elemento de consideração aqui, outro aspecto é que a lógica de otimização do compilador pode estar sujeita a defeitos sutis, especialmente devido à sua natureza complexa. ao longo dos anos, constatou-se que o gcc apresenta bugs em suas inúmeras rotinas lógicas de otimização. por exemplo, bug do gcc?
fonte
É equivalente a estender o verificador de tipos para fornecer algumas propriedades de um programa ao otimizador. Acredito que Tsuyoshi Ito está certo e você pode estar um pouco desorientado sobre Coq. É uma ótima ferramenta para fornecer um compilador sem erros, mas no caso descrito, ele não fornece mais poder às análises estáticas.
A única coisa que posso pensar sobre o fortalecimento das análises estáticas com o Coq é equipar seu idioma com afirmações que contêm algumas provas escritas pelo usuário. - Se o compilador em si fosse traduzido para um idioma, incluindo uma pena para digitação dinâmica, e se as provas escritas pelo usuário fossem conversíveis em funções, seria possível aplicar essas funções como propriedades pré-necessárias para alguns subtipos ou otimizações. - Isso realmente forneceria mais energia ao compilador.
No entanto, até onde posso ver, seria bastante útil para fortalecer a subtipagem. - É difícil fazer um programador saber que propriedade em que local seria útil para o otimizador.
fonte