Programas teoricamente livres de erros

Eu li muitos artigos que afirmam que o código não pode estar livre de erros e eles estão falando sobre esses teoremas:

• Problema de parada
• Teorema da incompletude de Gödel
• Teorema de Rice

Na verdade, o teorema de Rice parece uma implicação do problema de parada e o problema de parada está em estreita relação com o teorema da incompletude de Gödel.

Isso implica que todo programa terá pelo menos um comportamento não intencional? Ou significa que não é possível escrever código para verificá-lo? E a verificação recursiva? Vamos supor que eu tenho dois programas. Ambos têm erros, mas não compartilham o mesmo erro. O que acontecerá se eu executá-los simultaneamente?

E, claro, a maioria das discussões falou sobre máquinas de Turing. E a automação com limite linear (computadores reais)?

Não é tanto que os programas não possam estar livres de erros; é muito difícil provar que são, se o programa que você está tentando provar não é trivial.

Não por falta de tentativa, lembre-se. Os sistemas de tipos devem fornecer alguma garantia; Haskell possui um sistema de tipo altamente sofisticado que faz isso, até certo ponto. Mas você nunca pode remover toda a incerteza.

Considere a seguinte função:

int add(int a, int b) { return a + b; }

O que pode dar errado com essa função? Eu já sei o que você está pensando. Digamos que cobrimos todas as bases, como verificação de estouro, etc. O que acontece se um raio cósmico atinge o processador, causando sua execução

LaunchMissiles();

em vez de?

OK, talvez isso seja um pouco artificial. Porém, mesmo funções simples, como a addfunção acima, devem operar em ambientes em que o processador muda constantemente os contextos, alternando entre vários threads e núcleos. Em um ambiente como esse, tudo pode acontecer. Se você duvida disso, considere que a RAM é confiável, não porque está livre de erros, mas porque possui um sistema interno para corrigir os erros de bits que inevitavelmente ocorrem.

Eu sei o que você está pensando. "Mas estou falando de software, não de hardware".

Existem muitas técnicas que podem melhorar seu nível de confiança de que o software funciona da maneira que deveria. A programação funcional é uma delas. A programação funcional permite raciocinar melhor sobre simultaneidade. Mas a programação funcional não é uma prova, os testes de unidade.

Por quê? Porque você tem essas coisas chamadas casos extremos.

E depois que você ultrapassa um pouco a simplicidade return a + b, torna-se notavelmente difícil provar a correção de um programa.

Leitura adicional
Eles escrevem as coisas certas
A explosão de Ariane 5

Primeiro, vamos estabelecer em que contexto você deseja discutir isso. As perguntas e respostas dos programadores no Stack Exchange sugerem que você provavelmente está interessado na existência de ferramentas / linguagens no mundo real, em vez de resultados teóricos e teoremas da ciência da computação .

Eu li muitos artigos que afirmam que o código não pode estar livre de erros

Espero que não, porque essa afirmação está incorreta. Embora seja comumente aceito que a maioria dos aplicativos em larga escala não esteja livre de bugs, de acordo com o meu conhecimento e experiência.

Mais comumente aceito é que não existe (ex. Existência, não possibilidade) uma ferramenta que determine perfeitamente se um programa escrito em um arquivo Turing-complete linguagem de programação está completamente livre de bugs.

Uma não prova é uma extensão intuitiva do Problema da Parada, combinada com os dados de observação da experiência cotidiana.

Não faz software existem que podem fazer "provas de correção " que verificar que um programa atende aos correspondentes formais especificações para o programa.

Isso implica que todo programa terá pelo menos um comportamento não intencional?

Não. Embora a maioria dos aplicativos tenha pelo menos um bug ou comportamento não intencional.

Ou significa que não é possível escrever código para verificá-lo?

Não, você pode usar especificações formais e assistentes de prova para verificar seguindo a especificação , mas, como a experiência demonstrou, ainda podem existir erros no sistema geral, como fatores fora da especificação - o tradutor e o hardware do código-fonte e os erros mais frequentes são cometidos nas próprias especificações.

Para detalhes mais sangrentos, consulte Coq é uma ferramenta / idioma / sistema.

E a verificação recursiva?

Eu não sei. Não estou familiarizado com isso e não tenho certeza se é um problema de computabilidade ou um problema de otimização do compilador.

Eu quero perguntar, isso implica que todo código terá pelo menos um comportamento não intencional?

Não. Os programas corretos podem ser e são gravados. Lembre-se, um programa pode estar correto, mas sua execução pode falhar devido a, por exemplo, circunstâncias físicas (como o usuário Robert Harvey escreveu em sua resposta aqui ), mas isso é uma questão distinta: o código desse programa ainda está correto. Para ser mais preciso, a falha não é causada por uma falha ou erro no próprio programa, mas na máquina subjacente que o executa (*).

(*) Estou emprestando definições de falha , erro e falha do campo de confiabilidade como, respectivamente, um defeito estático, um estado interno incorreto e um comportamento externo incorreto observado de acordo com sua especificação (consulte <qualquer artigo desse campo>) .

Ou significa que não sou capaz de escrever um código, que irá verificá-lo?

Consulte o caso geral na declaração acima e você está correto.

Você poderá escrever um programa que verifique se um programa X específico está correto. Por exemplo, se você definir um programa "olá mundo" como um com duas instruções em sequência, a saber, print("hello world")e exitpoderá escrever um programa que verifique se sua entrada é um programa composto por essas duas instruções em sequência, relatando assim se é um programa "olá mundo" correto ou não.

O que você não pode fazer usando as formulações atuais é escrever um programa para verificar se algum programa arbitrário é interrompido, o que implica a impossibilidade de testar a correção nos casos gerais.

A execução de duas ou mais variantes do mesmo programa é uma técnica bem conhecida de tolerância a falhas denominada programação N-variant (ou N-version). É um reconhecimento da presença de erros no software.

Geralmente essas variantes são codificadas por diferentes equipes de desenvolvimento, usando diferentes compiladores e, às vezes, são executadas em diferentes CPUs com diferentes sistemas operacionais. Os resultados são votados antes de serem enviados ao usuário. A Boeing e a Airbus amam esse tipo de arquitetura.

Dois links fracos permanecem, levando a erros no modo comum:

• Existe apenas uma especificação.
• o sistema de votação é único ou complexo.

Um programa tem algumas especificações e é executado em algum ambiente.

^{(o exemplo do raio cósmico em outras respostas que mudam addpara FireMissiles pode ser considerado parte do "ambiente")}

Supondo que você possa especificar formalmente o comportamento pretendido do programa (ou seja, sua especificação) e seu ambiente, às vezes você pode provar formalmente que o programa está nesse preciso sentido livre de bugs (portanto, seu comportamento ou resultado respeita a formalização de sua especificação na formalização do seu ambiente).

Em particular, você pode usar analisadores de fonte estática de som, como, por exemplo, Frama-C .

^{(mas o estado da arte atual desses analisadores não permite a análise completa de programas e a prova de programas em grande escala, como o compilador GCC, o navegador Firefox ou o kernel Linux; e eu acredito que essas provas não acontecerão durante a minha vida Nasci em 1959)}

No entanto, o que você provou é o comportamento correto do programa com alguma especificação específica em alguns ambientes (de classe).

Na prática, você poderia (e a NASA ou a ESA provavelmente querem) provar que alguns softwares de naves espaciais estão "livres de bugs", com algumas especificações precisas e formalizadas. Mas isso não significa que seu sistema sempre se comportará como você deseja.

Em palavras mais simples, se o robô da sua nave espacial encontrar algum ET e você não especificou isso, não há como fazer com que o robô se comporte como você realmente deseja ....

Leia também as entradas do blog de J.Pitrat .

Aliás, o problema da parada ou o teorema de Gödel provavelmente se aplicam também ao cérebro humano, ou mesmo à espécie humana.

Isso implica que todo programa terá pelo menos um comportamento não intencional?

Não.

O problema da parada diz que é impossível escrever um programa que teste se todo programa pára em um período finito de tempo. Isso não significa que é impossível escrever um programa que possa categorizar alguns programas como interrompidos, outros como não interrompidos. O que isso significa é que sempre haverá alguns programas que um analisador de parada não pode categorizar de uma maneira ou de outra.

Os teoremas de incompletude de Gödel têm uma área cinza semelhante a eles. Dado um sistema matemático de complexidade suficiente, existirão algumas declarações feitas no contexto desse sistema cuja veracidade não pode ser avaliada. Isso não significa que os matemáticos tenham que desistir da ideia de prova. A prova continua sendo a pedra angular da matemática.

Alguns programas podem ser comprovadamente corretos. Não é fácil, mas pode ser feito. Esse é o objetivo da prova formal do teorema (parte dos métodos formais). Os teoremas da incompletude de Gödel aparecem aqui: nem todos os programas podem ser provados corretos. Isso não significa que seja totalmente inútil usar métodos formais, porque alguns programas podem ser formalmente comprovados como corretos.

Nota: Os métodos formais impedem a possibilidade de um raio cósmico atingir o processador e executar em launch_missiles()vez de a+b. Eles analisam programas no contexto de uma máquina abstrata em vez de máquinas reais que estão sujeitas a distúrbios de eventos únicos, como o raio cósmico de Robert Harvey.

Há muitas respostas boas aqui, mas todas parecem contornar o ponto crítico, que é o seguinte: todos esses teoremas têm uma estrutura semelhante e dizem coisas semelhantes, e o que eles dizem não é "é impossível provavelmente escrever corretamente programas"(para algum valor específico de 'correta' e 'programa' que varia em cada caso), mas o que eles fazem dizer é 'é impossível impedir que alguém escrever um programa incorreto que não podemos provar ser incorreto' ( etc).

Tomando o exemplo específico do problema da parada, a diferença se torna mais clara: obviamente existem programas que provam parar e outros programas que provavelmente nunca param. O fato de haver uma terceira classe de programas cujo comportamento não pode ser determinado de qualquer maneira não é um problema, se tudo o que queremos fazer é escrever um programa de interrupção comprovada, pois podemos simplesmente evitar escrever um programa que pertença a essa classe.

O mesmo se aplica ao teorema de Rice. Sim, para qualquer propriedade não trivial de um programa, podemos escrever um programa que não pode ter essa propriedade comprovada como verdadeira nem falsa; também podemos evitar a criação de um programa desse tipo, porque podemos determinar se um programa é comprovável.

Minha resposta será da perspectiva dos negócios do mundo real e dos desafios que toda equipe de desenvolvimento enfrenta. O que vejo nesta pergunta e muitas respostas é realmente sobre o controle de defeitos.

O código pode estar livre de erros. Pegue qualquer um dos exemplos de código "Hello World" para qualquer linguagem de programação e execute-o na plataforma pretendida, que funcionará de forma consistente e produzirá os resultados desejados. Termina qualquer teoria sobre a impossibilidade de código estar livre de erros.

Os erros em potencial aparecem à medida que a lógica se torna mais complexa. O exemplo simples do Hello World não tem lógica e faz a mesma coisa estática a cada vez. Assim que você adiciona um comportamento dinâmico controlado por lógica, é isso que introduz a complexidade que leva aos erros. A própria lógica pode ser falha ou os dados que são inseridos na lógica podem variar de uma maneira que a lógica não lida.

Um aplicativo moderno também depende de bibliotecas de tempo de execução, CLR, middleware, banco de dados, etc. camadas que, ao mesmo tempo em que economizam tempo de desenvolvimento, também são camadas em que os erros nessas camadas podem existir e passar despercebidos pelo desenvolvimento e testes UAT e para produção.

Por fim, a cadeia de aplicativos / sistemas em que o aplicativo consome dados que alimentam sua lógica são todas fontes de possíveis bugs, dentro da lógica ou no software que empilha as lógicas sobre os sistemas de upstream que consome dados.

Os desenvolvedores não estão no controle de 100% de cada peça móvel que suporta a lógica de sua aplicação. Na verdade, não temos controle de muito. É por isso que o teste de unidade é importante, e o gerenciamento de configurações e alterações são processos importantes que não devemos ignorar ou ser preguiçosos / desleixados.

Além disso, acordos documentados entre o aplicativo que consomem dados de uma fonte fora do seu controle, que define o formato e as especificações específicos para os dados transferidos, bem como quaisquer limites ou restrições que seu sistema assume que o sistema de origem é responsável por garantir que a saída esteja dentro esses limites.

No aplicativo de engenharia de software do mundo real, você não será capaz de fazê-lo voar, explicando aos negócios por que, teoricamente, os aplicativos não podem estar livres de erros. Discussões dessa natureza entre tecnologia e negócios nunca acontecerão, exceto após um mau funcionamento tecnológico que tenha impactado a capacidade da empresa de ganhar dinheiro, evitar perder dinheiro e / ou manter as pessoas vivas. A resposta para "como isso pode acontecer" não pode ser "deixe-me explicar essa teoria para você entender".

Em termos de cálculos maciços que teoricamente poderiam levar uma eternidade para realizar o cálculo e obter um resultado, um aplicativo que não pode terminar e retornar com um resultado - isso é um bug. Se a natureza da computação é tal que consome muito tempo e consome muita computação, você atende a essa solicitação e fornece feedback ao usuário sobre como / quando ele pode recuperar o resultado e inicia os encadeamentos paralelos para agitá-lo. Se isso precisa acontecer mais rapidamente do que pode ser feito em um servidor e é importante para os negócios, você o expande em todos os sistemas necessários. É por isso que a nuvem é muito atraente e a capacidade de ativar nós para trabalhar e diminuí-los quando terminar.

Se existe a possibilidade de obter uma solicitação de que nenhuma quantidade de energia de computação pode ser concluída, ela não deve ficar lá correndo infinitamente, com um processo de negócios aguardando a resposta para o que a empresa considera um problema finito.

Eu não acredito que o código seja 100% livre de erros, porque o código nunca é realmente concluído. Você sempre pode melhorar o que escreve.

A programação é um campo da ciência e da matemática. Nesse caso, as duas são infinitas. O melhor de ser desenvolvedor é que nosso trabalho é interminável.

Existem mais de mil maneiras de escrever uma única linha de código. A idéia é escrever a versão mais otimizada dessa linha de código, mas isso pode não estar livre de erros. Sem erros refere-se à idéia de que seu código é inquebrável e todo o código pode ser quebrado em algum grau ou método.

Então, o código pode ser eficiente? Sim.
O código pode ser otimizado infinitamente? Sim.
O código pode estar livre de bugs? Não, você simplesmente ainda não encontrou uma maneira de quebrá-lo.
Dito isto, se você se esforçar para melhorar a si mesmo e suas práticas de escrita de código, será difícil quebrá-lo.