Como os compiladores são tão confiáveis?

Usamos compiladores diariamente como se sua correção fosse um dado, mas compiladores também são programas e podem potencialmente conter bugs. Eu sempre me perguntei sobre essa robustez infalível. Você já encontrou um bug no próprio compilador? O que foi e como você percebeu que o problema estava no próprio compilador?

... e como é que eles fazem compiladores tão confiável?

Eles são testados minuciosamente pelo uso de milhares ou até milhões de desenvolvedores ao longo do tempo.

Além disso, o problema a ser resolvido está bem definido (por uma especificação técnica muito detalhada). E a natureza da tarefa se presta facilmente a testes de unidade / sistema. Ou seja, está basicamente traduzindo entrada de texto em um formato muito específico para saída em outro tipo de formato bem definido (algum tipo de bytecode ou código de máquina). Portanto, é fácil criar e verificar casos de teste.

Além disso, geralmente os bugs também são fáceis de reproduzir: além das informações exatas da plataforma e da versão do compilador, geralmente tudo o que você precisa é de um código de entrada. Sem mencionar que os usuários do compilador (sendo eles próprios desenvolvedores) tendem a fornecer relatórios de erros muito mais precisos e detalhados do que qualquer usuário médio de computador :-)

Além de todas as ótimas respostas até agora:

Você tem um "viés de observador". Você não observa bugs e, portanto, assume que não há nenhum.

Eu costumava pensar como você. Então eu comecei a escrever compiladores profissionalmente, e deixe-me dizer, existem muitos erros por aí!

Você não vê os bugs porque escreve um código que é igual a 99,999% de todo o restante do código que as pessoas escrevem. Você provavelmente escreve um código perfeitamente normal, direto e claramente correto, que chama métodos e executa loops e não faz nada extravagante ou estranho, porque você é um desenvolvedor normal resolvendo problemas comerciais normais.

Você não vê nenhum erro do compilador porque os erros do compilador não estão nos cenários de código normal fáceis de analisar; os erros estão na análise do código estranho que você não escreve.

Eu, por outro lado, tenho o viés oposto de observador. Eu vejo códigos malucos o dia todo, todos os dias e, para mim, os compiladores parecem estar cheios de bugs.

Se você sentou-se com a especificação de idioma de qualquer idioma e adotou qualquer implementação de compilador para esse idioma, e realmente tentou determinar se o compilador implementou exatamente a especificação ou não, concentrando-se em casos de canto obscuros, logo você descobriria erros do compilador com bastante frequência. Deixe-me dar um exemplo, aqui está um bug do compilador C # que encontrei literalmente cinco minutos atrás.

static void N(ref int x){}
...
N(ref 123);

O compilador fornece três erros.

• Um argumento ref ou out deve ser uma variável atribuível.
• A melhor correspondência para N (ref int x) possui argumentos inválidos.
• "Ref" ausente no argumento 1.

Obviamente, a primeira mensagem de erro está correta e a terceira é um erro. O algoritmo de geração de erro está tentando descobrir por que o primeiro argumento era inválido, olha para ele, vê que é uma constante e não volta ao código fonte para verificar se foi marcado como "ref"; ao contrário, assume que ninguém seria tolo o suficiente para marcar uma constante como ref e decide que o juiz deve estar ausente.

Não está claro qual é a terceira mensagem de erro correta, mas não é isso. De fato, também não está claro se a segunda mensagem de erro está correta. A resolução de sobrecarga deve falhar ou "ref 123" deve ser tratado como um argumento ref do tipo correto? Agora vou ter que pensar um pouco e conversar com a equipe de triagem para que possamos determinar qual é o comportamento correto.

Você nunca viu esse bug porque provavelmente nunca faria algo tão bobo a ponto de passar por 123 por ref. E se você o fizesse, provavelmente nem notaria que a terceira mensagem de erro não faz sentido, pois a primeira é correta e suficiente para diagnosticar o problema. Mas eu tento fazer coisas assim, porque estou tentando quebrar o compilador. Se você tentasse, também veria os erros.

Você está brincando comigo? Os compiladores também têm bugs, realmente carregam.

O GCC é provavelmente o mais célebre dos compiladores de código aberto do planeta e veja seu banco de dados de erros: http://gcc.gnu.org/bugzilla/buglist.cgi?product=gcc&component=c%2B%2B&resolution=-- -

Entre o GCC 3.2 e o GCC 3.2.3, observe quantos bugs foram corrigidos: http://gcc.gnu.org/gcc-3.2/changes.html

Quanto a outros como o Visual C ++, nem quero começar.

Como você torna os compiladores confiáveis? Bem, para começar, eles têm cargas e cargas de testes de unidade. E o planeta inteiro as usa, então não há escassez de testadores.

Sério, porém, os desenvolvedores de compiladores que eu gosto de acreditar são programadores superiores e, embora não sejam infalíveis, eles têm um grande impacto.

Eu encontrei dois ou três no meu dia. A única maneira real de detectar um é olhar o código do assembly.

Embora os compiladores sejam altamente confiáveis ​​por razões apontadas por outros pôsteres, acho que a confiabilidade do compilador geralmente é uma avaliação auto-realizada. Os programadores tendem a ver o compilador como o padrão. Quando algo der errado, você assume que é sua culpa (porque 99,999% do tempo é) e altera seu código para solucionar o problema do compilador e não o contrário. Por exemplo, o travamento de código em uma configuração de alta otimização é definitivamente um bug do compilador, mas a maioria das pessoas o define um pouco mais baixo e segue em frente sem relatar o bug.

Os compiladores têm várias propriedades que levam à sua correção:

• O domínio é muito conhecido e pesquisado. O problema está bem definido e as soluções oferecidas estão bem definidas.
• O teste automatizado é suficiente para provar que os compiladores funcionam corretamente
• Os compiladores têm testes muito extensos, tipicamente públicos, automatizados e de unidade, que vêm se acumulando ao longo do tempo para cobrir mais espaço de erro do que na maioria dos outros programas
• Os compiladores têm um número muito grande de olhos observando seus resultados

Usamos compiladores diariamente

... e como eles tornam os compiladores tão confiáveis?

Eles não. Nós fazemos. Como todo mundo os usa o tempo todo, os erros são encontrados rapidamente.

É um jogo de números. Porque compiladores se acostumar tão incisiva, é altamente provável que qualquer bug vai ser desencadeada por alguém, mas porque há um número tão grande de usuários, é altamente improvável que esse alguém será você especificamente.

Portanto, depende do seu ponto de vista: em todos os usuários, os compiladores são bugs. Mas é muito provável que outra pessoa tenha compilado um pedaço de código semelhante antes de você, portanto, se fosse um bug, ele teria atingido, não você, então, do seu ponto de vista individual , parece que o bug foi nunca lá.

Obviamente, além disso, você pode adicionar todas as outras respostas aqui: os compiladores são bem pesquisados, bem compreendidos. Existe esse mito de que eles são difíceis de escrever, o que significa que apenas programadores muito inteligentes e muito bons realmente tentam escrever um, e são extremamente cuidadosos quando o fazem. Eles geralmente são fáceis de testar e fáceis de testar o estresse ou o teste de fuzz. Os usuários do compilador tendem a ser programadores especializados, levando a relatórios de erros de alta qualidade. E o contrário: os escritores de compiladores tendem a ser usuários de seu próprio compilador.

Além de todas as respostas já, gostaria de adicionar:

Eu acredito que muitas vezes, os vendedores estão comendo sua própria comida de cachorro. Ou seja, eles estão escrevendo os compiladores em si mesmos.

Eu sempre encontrei erros do compilador.

Você pode encontrá-los nos cantos mais escuros, onde há menos testadores. Por exemplo, para encontrar erros no GCC, tente:

• Crie um compilador cruzado. Você encontrará literalmente dezenas de bugs nos scripts de configuração e compilação do GCC. Alguns resultam em falhas de compilação durante a compilação do GCC e outros resultam em falha do compilador cruzado na compilação de executáveis ​​em funcionamento.
• Crie uma versão Itanium do GCC usando o perfil de inicialização. Nas últimas vezes em que tentei isso no GCC 4.4 e 4.5, ele não conseguiu produzir um manipulador de exceção C ++ em funcionamento. A compilação não otimizada funcionou bem. Ninguém parecia interessado em corrigir o erro que eu relatei e desisti de corrigi-lo depois de tentar examinar o que estava quebrando nas especificações de memória asm do GCC.
• Tente criar seu próprio GCJ de trabalho a partir dos itens mais recentes sem seguir um script de criação de distribuição. Atreva-se.

Várias razões:

• Os escritores de compiladores " comem sua própria comida de cachorro ".
• Compiladores são baseados em princípios bem entendidos de CS.
• Compiladores são construídos com uma especificação muito clara .
• Compiladores são testados .
• Compiladores nem sempre são muito confiáveis .

Eles geralmente são muito bons em -O0. De fato, se suspeitarmos de um bug do compilador, comparamos -O0 versus qualquer nível que estamos tentando usar. Níveis mais altos de otimização correm maior risco. Alguns são até deliberadamente e rotulados como tal na documentação. Eu encontrei muitos (pelo menos cem durante o meu tempo), mas eles estão se tornando muito mais raros recentemente. No entanto, na busca de bons números de especificação (ou outros parâmetros importantes para o marketing), a tentação de ultrapassar os limites é grande. Alguns anos atrás, tivemos problemas em que um fornecedor (para não nomear) decidiu tornar a violação do parêntese padrão - em vez de alguma opção especial de compilação claramente rotulada.

Pode ser difícil diagnosticar um erro do compilador versus, digamos, uma referência de memória dispersa, uma recompilação com opções diferentes pode simplesmente embaralhar o posicionamento relativo dos objetos de dados na memória, para que você não saiba se é o Heisenbug do código-fonte ou um buggy compilador. Além disso, muitas otimizações fazem alterações legítimas na ordem das operações, ou mesmo simplificações algébricas na sua álgebra, e estas terão propriedades diferentes em relação ao arredondamento do ponto flutuante e ao excesso / transbordamento. É difícil separar esses efeitos dos bugs REAIS. A computação de ponto flutuante de núcleo duro é difícil por esse motivo, porque erros e sensibilidade numérica geralmente não são fáceis de desemaranhar.

Os erros do compilador não são tão raros. O caso mais comum é um compilador relatar um erro no código que deve ser aceito ou um compilador aceitar o código que deveria ter sido rejeitado.

Sim, encontrei um bug no compilador ASP.NET ontem:

Quando você usa modelos fortemente tipados em vistas, há um limite para quantos modelos de parâmetros podem conter. Obviamente, ele não pode levar mais de quatro parâmetros de modelo, de modo que os dois exemplos abaixo tornam demais para o compilador lidar:

ViewUserControl<System.Tuple<type1, type2, type3, type4, type5>>

Não seria compilado como está, mas será type5removido.

ViewUserControl<System.Tuple<MyModel, System.Func<type1, type2, type3, type4>>>

Compilaria se type4for removido.

Note que System.Tupletem muitas sobrecargas e pode levar até 16 parâmetros (é uma loucura, eu sei).

Você já encontrou um bug no próprio compilador? O que foi e como você percebeu que o problema estava no próprio compilador?

Sim!

Os dois mais memoráveis ​​foram os dois que eu já encontrei. Ambos estavam no compilador Lightspeed C para Macs 680x0 por volta de 1985-7.

O primeiro foi onde, em algumas circunstâncias, o operador inteiro pós-incremento não fez nada - em outras palavras, em um trecho de código específico, "i ++" simplesmente não fez nada com "i". Eu estava puxando meu cabelo até olhar para uma desmontagem. Depois, fiz o incremento de uma maneira diferente e enviei um relatório de erro.

O segundo foi um pouco mais complicado e foi realmente um "recurso" mal considerado que deu errado. Os primeiros Macs tinham um sistema complicado para realizar operações de disco de baixo nível. Por alguma razão que eu nunca entendi - provavelmente relacionado à criação de executáveis ​​menores - em vez de o compilador apenas gerar as instruções de operação do disco no local no código do objeto, o compilador Lightspeed chamaria uma função interna, que em tempo de execução gerou a operação do disco instruções na pilha e pulou lá.

Isso funcionou muito bem em 68000 CPUs, mas quando você executava o mesmo código em uma CPU 68020, costumava fazer coisas estranhas. Descobriu-se que um novo recurso do 68020 era um cache de instruções de 256 bytes de instruções primitivas. Sendo o início dos caches da CPU, não havia noção de que o cache estava "sujo" e precisava ser recarregado; Eu acho que os designers de CPU da Motorola não pensaram em código auto-modificável. Portanto, se você executasse duas operações de disco suficientemente próximas na sua sequência de execução, e o tempo de execução do Lightspeed construísse as instruções reais no mesmo local da pilha, a CPU pensaria erroneamente que havia um cache de instruções atingido e executaria a primeira operação de disco duas vezes.

Mais uma vez, descobrir isso levou algumas investigações com um desmontador e várias etapas em um depurador de baixo nível. Minha solução alternativa foi prefixar cada operação de disco com uma chamada para uma função que executava 256 instruções "NOP", que inundavam (e, portanto, limpavam) o cache de instruções.

Nos últimos 25 anos, desde então, tenho visto cada vez menos erros de compilador ao longo do tempo. Eu acho que existem algumas razões para isso:

• Há um conjunto cada vez maior de testes de validação para compiladores.
• Os compiladores modernos geralmente são divididos em duas ou mais partes, uma das quais gera código independente da plataforma (por exemplo, o LLVM direciona o que você pode considerar uma CPU imaginária) e outra que traduz isso em instruções para o hardware de destino real. Nos compiladores de várias plataformas, a primeira parte é usada em todos os lugares e, portanto, recebe muitos testes no mundo real.

Foi encontrado um erro gritante no Turbo Pascal há 5,5 anos. Um erro presente na versão anterior (5.0) nem na próxima (6.0) do compilador. E um que deveria ter sido fácil de testar, pois não era uma base de dados (apenas uma chamada que não é tão comumente usada).

Em geral, certamente os construtores de compiladores comerciais (em vez de projetos de hobby) terão controle de qualidade e procedimentos de teste muito extensos. Eles sabem que seus compiladores são seus principais projetos e que as falhas parecerão muito ruins para eles, pior do que em outras empresas que fabricam a maioria dos outros produtos. Os desenvolvedores de software são um grupo implacável, nossos fornecedores de ferramentas nos decepcionam, é provável que procuremos alternativas em vez de esperar por uma correção do fornecedor, e é provável que comuniquemos esse fato a nossos colegas que podem seguir nossa exemplo. Em muitos outros setores, esse não é o caso; portanto, a perda potencial para um fabricante de compiladores como resultado de um bug sério é muito maior do que a de um fabricante de software de edição de vídeo.

Quando o comportamento do seu software é diferente quando compilado com -O0 e -O2, você encontrou um erro do compilador.

Quando o comportamento do seu software é apenas diferente do que você espera, é provável que o bug esteja no seu código.

Os erros do compilador acontecem, mas você os encontra em cantos estranhos ...

Houve um erro estranho no compilador VAX VMS C da Digital Equipment Corporation nos anos 90

(Eu estava usando uma cebola no meu cinto, como era a moda na época)

Um ponto-e-vírgula estranho em qualquer lugar anterior a um loop for seria compilado como o corpo do loop for.

f(){...}
;
g(){...}

void test(){
  int i;
  for ( i=0; i < 10; i++){
     puts("hello");
  }
}

No compilador em questão, o loop é executado apenas uma vez.

vê

f(){...}
g(){...}

void test(){
  int i;
  for ( i=0; i < 10; i++) ;  /* empty statement for fun */

  {
     puts("hello");
  }
}

Isso me custou muito tempo.

A versão mais antiga do compilador PIC C que infligíamos à experiência de trabalho dos alunos não podia gerar código que usasse a interrupção de alta prioridade corretamente. Você teve que esperar 2-3 anos e atualizar.

O compilador MSVC 6 tinha um bug bacana no vinculador, ele segmentava falhas e morria de vez em quando sem motivo. Uma construção limpa geralmente a consertava (mas nem sempre suspira ).

Em alguns domínios, como o software aviônico, existem requisitos de certificação extremamente altos, no código e no hardware, bem como no compilador. Sobre esta última parte, há um projeto que visa criar um compilador C formalmente verificado, chamado Compcert . Em teoria, esse tipo de compilador é tão confiável quanto possível.

Eu já vi vários bugs do compilador, relatei alguns deles (especificamente, em F #).

Dito isso, acho que os erros do compilador são raros, porque as pessoas que escrevem compiladores geralmente se sentem muito confortáveis ​​com os conceitos rigorosos da ciência da computação que os tornam realmente conscientes das implicações matemáticas do código.

Presumivelmente, muitos deles estão familiarizados com coisas como cálculo lambda, verificação formal, semântica denotacional etc. - coisas que um programador comum como eu mal consegue compreender.

Além disso, geralmente há um mapeamento bastante direto da entrada para a saída nos compiladores, portanto, depurar uma linguagem de programação é provavelmente muito mais fácil do que depurar, por exemplo, um mecanismo de blog.

Encontrei um bug no compilador C # há pouco tempo. Você pode ver como Eric Lippert (que faz parte da equipe de design do C #) descobriu qual era o bug aqui .

Além das respostas já dadas, gostaria de adicionar mais algumas coisas. Os projetistas de compiladores geralmente são programadores extremamente bons. Compiladores são muito importantes: a maioria da programação é feita usando compiladores, por isso é imperativo que o compilador seja de alta qualidade. Portanto, é do interesse das empresas que fabricam compiladores colocar seus melhores profissionais (ou pelo menos muito bons: os melhores podem não gostar do design do compilador). A Microsoft gostaria que seus compiladores C e C ++ funcionassem corretamente, ou o resto da empresa não pode fazer seu trabalho.

Além disso, se você estiver construindo um compilador realmente complexo, não poderá simplesmente cortá-lo juntos. A lógica por trás dos compiladores é altamente complexa e fácil de formalizar. Portanto, esses programas costumam ser criados de uma maneira muito 'robusta' e genérica, o que tende a resultar em menos erros.