Prova de que o código morto não pode ser detectado pelos compiladores

32

Estou planejando ministrar um curso de inverno sobre um número variável de tópicos, um dos quais serão compiladores. Agora, eu me deparei com esse problema enquanto pensava em atribuições a serem entregues ao longo do trimestre, mas ele me deixou perplexo, para que eu pudesse usá-lo como exemplo.

public class DeadCode {
  public static void main(String[] args) {
     return;
     System.out.println("This line won't print.");
  }
}

No programa acima, é óbvio que a instrução print nunca será executada devido ao return. Às vezes, os compiladores dão avisos ou erros sobre código morto. Por exemplo, o código acima não será compilado em Java. O compilador javac, no entanto, não detectará todas as instâncias de código morto em todos os programas. Como eu provaria que nenhum compilador pode fazer isso?

Thomas
fonte
29
Qual é a sua formação e qual o contexto em que você estará ensinando? Para ser franco, estou levemente preocupado que você precise perguntar isso, já que vai ensinar. Mas boa ligação perguntando aqui!
Raphael
9
@ MichaelKjörling A detecção de código morto é impossível mesmo sem essas considerações.
David Richerby
2
BigInteger i = 0; while(isCollatzConjectureTrueFor(i)) i++; printf("Hello world\n");
user253751
2
@immibis A pergunta pede uma prova de que a detecção de código morto é impossível . Você deu um exemplo em que a detecção correta de código morto requer a solução de um problema aberto em matemática. Isso não prova que a detecção de código morto é impossível .
David Richerby

Respostas:

57

Tudo vem da indecidibilidade do problema da parada. Suponha que tenhamos uma função de código morto "perfeita", alguma Máquina de Turing M e alguma string de entrada x, e um procedimento parecido com isto:

Run M on input x;
print "Finished running input";

Se M for executado para sempre, excluiremos a instrução print, pois nunca a alcançaremos. Se M não durar para sempre, precisamos manter a declaração de impressão. Portanto, se tivermos um removedor de código morto, ele também nos permitirá resolver o Problema da Interrupção, para que saibamos que não existe esse removedor de código morto.

A maneira de contornar isso é por "aproximação conservadora". Portanto, no meu exemplo de máquina de Turing acima, podemos supor que a execução de M em x possa terminar, por isso é seguro e não removemos a declaração de impressão. No seu exemplo, sabemos que, independentemente de quais funções são ou não interrompidas, não há como chegarmos a essa declaração impressa.

Geralmente, isso é feito através da construção de um "gráfico de controle-fluxo". Fazemos suposições simplificadoras, como "o final de um loop while está conectado ao início e a declaração depois", mesmo que seja executado para sempre ou seja apenas uma vez e não visite os dois. Da mesma forma, assumimos que uma declaração if pode alcançar todos os seus ramos, mesmo que, na realidade, alguns nunca sejam usados. Esse tipo de simplificação nos permite remover "obviamente código morto" como o exemplo que você dá, enquanto permanece decidível.

Para esclarecer algumas confusões dos comentários:

  1. Nitpick: para M fixo, isso é sempre decidível. M tem que ser a entrada

    Como Raphael diz, no meu exemplo, consideramos a Máquina de Turing como uma entrada. A idéia é que, se tivéssemos um algoritmo DCE perfeito, poderíamos construir o trecho de código que eu dou para qualquer Máquina de Turing , e ter um DCE resolveria o problema de parada.

  2. não convencido. retornar como uma declaração contundente em uma execução direta sem ramificação não é difícil de decidir. (e meu compilador me diz que é capaz de descobrir isso)

    Para o problema que o njzk2 levanta: você está absolutamente certo; nesse caso, você pode determinar que não há como uma declaração após o retorno ser alcançada. Isso ocorre porque é simples o suficiente para que possamos descrever sua inacessibilidade usando restrições de gráfico de fluxo de controle (ou seja, não há arestas de saída de uma declaração de retorno). Mas não existe um eliminador perfeito de código morto, que elimina todo o código não utilizado.

  3. Não tomo uma prova dependente de entrada para uma prova. Se existe esse tipo de entrada do usuário que pode permitir que o código seja finito, é correto que o compilador assuma que a ramificação a seguir não está morta. Não consigo ver para que servem todos esses votos positivos, é óbvio (por exemplo, stdin sem fim) e errado.

    Para TomášZato: não é realmente uma prova dependente de entrada. Em vez disso, interprete-o como um "forall". Funciona da seguinte forma: assuma que temos um algoritmo DCE perfeito. Se você me der uma máquina de Turing M arbitrária e a entrada x, eu posso usar meu algoritmo DCE para determinar se M pára, construindo o trecho de código acima e ver se a instrução print é removida. Essa técnica, de deixar um parâmetro arbitrário para provar uma declaração forall, é comum em matemática e lógica.

    Eu não entendo completamente o ponto de TomášZato sobre o código ser finito. Certamente o código é finito, mas um algoritmo DCE perfeito deve ser aplicado a todo o código, que é um conjunto de informações. Da mesma forma, enquanto o próprio código é finito, os conjuntos potenciais de entrada são infinitos, assim como o tempo de execução potencial do código.

    Quanto a considerar o ramo final como não morto: é seguro em termos da "aproximação conservadora" de que falo, mas não é suficiente detectar todas as instâncias de código morto, conforme o OP solicita.

Considere um código como este:

while (true)
  print "Hello"
print "goodbye"

Claramente, podemos remover print "goodbye"sem alterar o comportamento do programa. Portanto, é um código morto. Mas se houver uma chamada de função diferente, e não (true)na whilecondição, não saberemos se podemos removê-la ou não, levando à indecidibilidade.

Note que eu não vou apresentar isso sozinho. É um resultado bem conhecido na teoria dos compiladores. É discutido no The Tiger Book . Você pode ver de onde eles falam nos livros do Google .

jmite
fonte
1
@ njzk2: Estamos tentando mostrar que é impossível criar um eliminador de código morto que elimine todo o código morto, não que seja impossível criar um eliminador de código morto que elimine algum código morto. O exemplo de impressão após retorno pode ser eliminado facilmente usando técnicas de gráfico de controle de fluxo, mas nem todo código morto pode ser eliminado dessa maneira.
user2357112 suporta Monica 11/11
4
Esta resposta faz referência a comentários. Ao ler a resposta, preciso pular para os comentários e retornar à resposta. Isso é confuso (duplamente quando você considera que os comentários são frágeis e podem ser perdidos). Uma resposta independente seria muito mais fácil de ler.
TRiG 12/11
1
nn
3
MxMx
1
jmite, incorpore comentários válidos na resposta para que a resposta seja por si só. Em seguida, sinalize todos os comentários obsoletos, para que possamos limpar. Obrigado!
Raphael
14

Essa é uma reviravolta na resposta de jmite que contorna a confusão potencial sobre a não terminação. Vou dar um programa que sempre se interrompe, pode ter código morto, mas não podemos (sempre) decidir algoritmicamente se ele possui.

Considere a seguinte classe de entradas para o identificador de código morto:

simulateMx(n) {
  simulate TM M on input x for n steps
  if M did halt
    return 0
  else
    return 1
}

Desde Me xsão corrigidos, simulateMstem código morto com return 0se e somente se Mnão parar x.

MxMM

Portanto, a verificação de código morto não é computável.

Caso você não esteja familiarizado com a redução como uma técnica de prova nesse contexto, recomendo nosso material de referência .

Rafael
fonte
5

Uma maneira simples de demonstrar esse tipo de propriedade sem se preocupar com os detalhes é usar o seguinte lema:

Lema: Para qualquer compilador C para uma linguagem completa de Turing, existe uma função undecidable_but_true()que não aceita argumentos e retorna o booleano true, de modo que C não pode prever se undecidable_but_true()retorna true ou false.

Observe que a função depende do compilador. Dada uma função undecidable_but_true1(), um compilador sempre pode ser aumentado com o conhecimento de se essa função retorna verdadeira ou falsa; mas sempre há outras funções undecidable_but_true2()que não serão abordadas.

Prova: pelo teorema de Rice , a propriedade "esta função retorna verdadeira" é indecidível. Portanto, qualquer algoritmo de análise estática não pode decidir essa propriedade para todas as funções possíveis.

Corolário: dado um compilador C, o seguinte programa contém código morto que não pode ser detectado:

if (!undecidable_but_true()) {
    do_stuff();
}

Uma observação sobre Java: a linguagem Java exige que os compiladores rejeitem certos programas que contenham código inacessível, enquanto exige sensatamente que o código seja fornecido em todos os pontos alcançáveis ​​(por exemplo, o fluxo de controle em uma função não nula deve terminar com uma returninstrução). O idioma especifica exatamente como a análise de código inacessível é executada; caso contrário, seria impossível escrever programas portáteis. Dado um programa do formulário

some_method () {
    <code whose continuation is unreachable>
    // is throw InternalError() needed here?
}

é necessário especificar em quais casos o código inacessível deve ser seguido por algum outro código e em quais casos não deve ser seguido por nenhum código. Um exemplo de um programa Java que contém código inacessível, mas não da maneira que os compiladores Java podem perceber, aparece no Java 101:

String day_of_week(int n) {
    switch (n % 7) {
    case 0: return "Sunday";
    case 1: case -6: return "Monday";
    …
    case 6: case -1: return "Saturday";
    }
    // return or throw is required here, even though this point is unreachable
}
Gilles 'SO- parar de ser mau'
fonte
Observe que alguns compiladores para alguns idiomas podem detectar que o final de day_of_weeké inacessível.
usar o seguinte comando
@immibis Sim, por exemplo, os alunos do CS101 podem fazer isso na minha experiência (embora, reconhecidamente, os alunos do CS101 não sejam um analisador estático de som, eles geralmente esquecem os casos negativos). Isso faz parte do meu argumento: é um exemplo de um programa com código inacessível que um compilador Java não detectará (pelo menos, pode avisar, mas não pode rejeitar).
Gilles 'SO- stop be evil'
1
Receio que a formulação do lema seja enganosa, na melhor das hipóteses, com um tom de injustiça. Indecidibilidade só faz sentido se você os definir termos de conjuntos (infinitos) de instâncias. (O compilador faz produzir uma resposta para cada função, e sabemos que ele não pode ser sempre correto, mas dizendo que não há uma única instância indecidível está desligado.) Seu parágrafo entre o Lema ea prova (que não chega a corresponder ao Lema como afirmado) tenta corrigir isso, mas acho que seria melhor formular um lema claramente correto.
Raphael
@Raphael Uh? Não, o compilador não precisa produzir uma resposta para a pergunta "essa função é constante?". Não é necessário distinguir “não sei” de “não” para produzir código de trabalho, mas isso não é relevante aqui, pois estamos interessados ​​apenas na parte de análise estática do compilador, não na parte de conversão de código. Não entendo o que você acha enganoso ou incorreto sobre a declaração do lema - a menos que você queira dizer que eu deveria escrever "analisador estático" em vez de "compilador"?
Gilles 'SO- stop be evil'
A declaração soa como "indecidibilidade significa que há uma instância que não pode ser resolvida", o que está errado. (Eu sei que você não quer dizer isso, mas é assim que ele pode ler as / os novatos incautos, IMHO.)
Raphael
3

A resposta de jmite se aplica se o programa sairá de um cálculo - apenas porque é infinito, eu não chamaria o código depois de morto.

No entanto, há outra abordagem: um problema para o qual existe uma resposta, mas é desconhecido:

public void Demo()
{
  if (Chess.Evaluate(new Chessboard(), int.MaxValue) != 0)
    MessageBox.Show("Chess is unfair!");
  else
    MessageBox.Show("Chess is fair!");
}

public class chess
{
  public Int64 Evaluate(Chessboard Board, int SearchDepth)
  {
  ...
  }
}

Essa rotina, sem dúvida , contém código morto - a função retornará uma resposta que executa um caminho, mas não o outro. Boa sorte em encontrá-lo! Minha memória é que nenhum computador teórico pode resolver isso dentro da vida útil do universo.

Em mais detalhes:

A Evaluate()função calcula qual lado vence um jogo de xadrez se os dois lados jogarem perfeitamente (com profundidade máxima de busca).

Os avaliadores de xadrez normalmente olham para frente a cada movimento possível em alguma profundidade especificada e, em seguida, tentam pontuar o tabuleiro nesse ponto (às vezes expandindo certos ramos mais longe, olhando na metade de uma troca ou algo semelhante, pode produzir uma percepção muito distorcida.) Desde a profundidade máxima real Se 17695 fizer meio movimento, a pesquisa é exaustiva; ela percorre todos os jogos de xadrez possíveis. Como todos os jogos terminam, não há como tentar decidir qual a posição de cada tabuleiro (e, portanto, não há razão para analisar a lógica de avaliação do tabuleiro - nunca será chamada), o resultado é uma vitória, uma perda ou um desenho. Se o resultado é um empate, o jogo é justo, se o resultado não é um empate, é um jogo injusto. Para expandir um pouco, temos:

public Int64 Evaluate(Chessboard Board, int SearchDepth)
{
  foreach (ChessMove Move in Board.GetPossibleMoves())
    {
      Chessboard NewBoard = Board.MakeMove(Move);
      if (NewBoard.Checkmate()) return int.MaxValue;
      if (NewBoard.Draw()) return 0;
      if (SearchDepth == 0) return NewBoard.Score();
      return -Evaluate(NewBoard, SearchDepth - 1);
    }
}

Observe também que será praticamente impossível para o compilador perceber que Chessboard.Score () é um código morto. O conhecimento das regras do xadrez nos permite descobrir isso, mas para entender isso, você precisa saber que o MakeMove nunca pode aumentar a contagem de peças e que Chessboard.Draw () retornará verdadeiro se a contagem de peças permanecer estática por muito tempo. .

Observe que a profundidade da pesquisa está em meio movimento, não em movimentos inteiros. Isso é normal para esse tipo de rotina de IA, pois é uma rotina O (x ^ n) - adicionar mais uma folha de pesquisa tem um efeito importante sobre quanto tempo leva para ser executado.

Loren Pechtel
fonte
8
Você assume que um algoritmo de verificação teria que executar o cálculo. Uma falácia comum! Não, você não assume nada sobre como um verificador funcionaria, caso contrário, você não pode refutar sua existência.
Raphael
6
A pergunta solicita uma prova de que é impossível detectar código morto. Sua postagem contém um exemplo de caso em que você suspeita que seria difícil detectar código morto. Essa não é uma resposta para a pergunta em questão.
David Richerby
2
@ LorenPechtel Eu não sei, mas isso não é uma prova. Veja também aqui ; um exemplo mais limpo do seu equívoco.
Raphael
3
Se ajudar, considere que, teoricamente, nada impede alguém de executar seu compilador por mais do que a vida útil do universo; a única limitação é praticidade. Um problema decidível é um problema decidível, mesmo que esteja na classe de complexidade NONELEMENTARY.
Pseudônimo
4
Em outras palavras, essa resposta é, na melhor das hipóteses, uma heurística destinada a mostrar por que provavelmente não é fácil criar um compilador que detecte todo o código morto - mas não é uma prova de impossibilidade. Esse tipo de exemplo pode ser útil como uma maneira de criar intuição para os alunos, mas não é uma prova. Ao se apresentar como prova, faz um desserviço. A resposta deve ser editada para afirmar que é um exemplo de construção de intuição, mas não uma prova de impossibilidade.
DW
-3

Eu acho que em um curso de computação, a noção de código morto é interessante no contexto da compreensão da diferença entre tempo de compilação e tempo de execução!

Um compilador pode determinar quando você tem um código que nunca pode ser percorrido em nenhum cenário de tempo de compilação, mas não pode ser feito em tempo de execução. um loop while simples com entrada do usuário para o teste de quebra de loop mostra isso.

Se um compilador realmente pode determinar o código morto de tempo de execução (ou seja, discernir Turing completo), há um argumento de que o código nunca precisa ser executado, porque o trabalho já está concluído!

Se nada mais, a existência de código que passa nas verificações de código morto em tempo de compilação ilustra a necessidade de verificação pragmática de limites em entradas e higiene geral de codificação (no mundo real de projetos reais).

dwoz
fonte
1
A pergunta pede uma prova de que é impossível detectar código morto. Você não respondeu a essa pergunta.
David Richerby
Além disso, sua afirmação de que "um compilador pode determinar quando você tem um código que nunca pode ser percorrido em nenhum cenário de tempo de compilação" está incorreta e contradiz diretamente o que a pergunta pede para você provar.
David Richerby
@ David Richerby, acho que você pode estar me interpretando mal. Não estou sugerindo que a verificação em tempo de compilação possa encontrar TODOS os códigos mortos, definitivamente não. Estou sugerindo que exista um subconjunto do conjunto de todo o código morto que seja discernível em tempo de compilação. Se eu escrever: if (true == false) {print ("something");}, essa instrução print será discernível em tempo de compilação para ser um código morto. Você discorda de que este é um contra-exemplo à sua afirmação?
dwoz
Claro, você pode determinar algum código morto. Mas se você disser "determinar quando [você tem código morto]" sem qualificações, então, para mim, significa encontrar todo o código morto, não apenas alguns deles.
David Richerby