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

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?

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 .

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.

$M$x$M$$M$

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 .

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
}

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.

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).