Prueba de que los compiladores no pueden detectar el código muerto

32

Estoy planeando enseñar un curso de invierno sobre un número variable de temas, uno de los cuales será compiladores. Ahora, me encontré con este problema mientras pensaba en tareas para dar durante el trimestre, pero me tiene perplejo, por lo que podría usarlo como un ejemplo.

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

En el programa anterior, es obvio que la declaración de impresión nunca se ejecutará debido a return. Los compiladores a veces dan advertencias o errores sobre el código muerto. Por ejemplo, el código anterior no se compilará en Java. Sin embargo, el compilador javac no detectará todas las instancias de código muerto en cada programa. ¿Cómo probaría que ningún compilador puede hacerlo?

Thomas
fuente
29
¿Cuál es su experiencia y en qué contexto enseñará? Para ser franco, estoy un poco preocupado de que tengas que preguntar esto, ya que vas a enseñar. Pero buena llamada preguntando aquí!
Raphael
99
@ MichaelKjörling La detección de código muerto es imposible incluso sin esas consideraciones.
David Richerby
2
BigInteger i = 0; while(isCollatzConjectureTrueFor(i)) i++; printf("Hello world\n");
user253751
2
@immibis La pregunta pide una prueba de que la detección de código muerto es imposible . Ha dado un ejemplo en el que la detección correcta de código muerto requiere resolver un problema abierto en matemáticas. Eso no prueba que la detección de código muerto sea imposible .
David Richerby

Respuestas:

57

Todo proviene de la indecidibilidad del problema de detención. Supongamos que tenemos una función de código muerto "perfecto", algo de Turing Machine M y algo de cadena de entrada x, y un procedimiento que se parece a esto:

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

Si M se ejecuta para siempre, entonces eliminamos la declaración de impresión, ya que nunca la alcanzaremos. Si M no se ejecuta para siempre, entonces debemos mantener la declaración de impresión. Por lo tanto, si tenemos un eliminador de código muerto, también nos permite resolver el problema de detención, por lo que sabemos que no puede haber tal eliminador de código muerto.

La forma de evitar esto es mediante una "aproximación conservadora". Entonces, en mi ejemplo anterior de Turing Machine, podemos suponer que la ejecución de M en x podría terminar, por lo que jugamos a lo seguro y no eliminamos la declaración de impresión. En su ejemplo, sabemos que no importa qué funciones se detengan o no, no hay forma de llegar a esa declaración impresa.

Por lo general, esto se realiza mediante la construcción de un "gráfico de control de flujo". Hacemos suposiciones simplificadoras, como "el final de un ciclo while está conectado al principio y la declaración posterior", incluso si se ejecuta para siempre o se ejecuta solo una vez y no visita ambos. Del mismo modo, suponemos que una declaración if puede alcanzar todas sus ramas, incluso si en realidad algunas nunca se usan. Este tipo de simplificaciones nos permiten eliminar el "código obviamente muerto" como el ejemplo que da, sin dejar de ser decidible.

Para aclarar algunas confusiones de los comentarios:

  1. Nitpick: para M fijo, esto siempre es decidible. M tiene que ser la entrada

    Como dice Raphael, en mi ejemplo, consideramos la máquina de Turing como una entrada. La idea es que, si tuviéramos un algoritmo DCE perfecto, podríamos construir el fragmento de código que doy para cualquier máquina de Turing , y tener un DCE resolvería el problema de detención.

  2. no convencido. regresar como una declaración contundente en una ejecución directa sin rama no es difícil de decidir. (y mi compilador me dice que es capaz de resolver esto)

    Para el problema que plantea njzk2: tiene toda la razón, en este caso puede determinar que no hay forma de que se llegue a una declaración después de la devolución. Esto se debe a que es lo suficientemente simple como para que podamos describir su inalcanzabilidad utilizando restricciones de gráficos de flujo de control (es decir, no hay bordes salientes de una declaración de retorno). Pero no hay un eliminador de código muerto perfecto, que elimina todo el código no utilizado.

  3. No tomo pruebas dependientes de entrada para una prueba. Si existe tal tipo de entrada del usuario que puede permitir que el código sea finito, es correcto que el compilador suponga que la siguiente rama no está muerta. No puedo ver para qué son todos estos votos, es obvio (por ejemplo, interminable sin fin) y está mal.

    Para TomášZato: no es realmente una prueba dependiente de entrada. Por el contrario, interpretarlo como un "forall". Funciona de la siguiente manera: supongamos que tenemos un algoritmo DCE perfecto. Si me das una Turing Machine M arbitraria e ingresas x, puedo usar mi algoritmo DCE para determinar si M se detiene, al construir el fragmento de código anterior y ver si la declaración de impresión se elimina. Esta técnica, de dejar un parámetro arbitrario para probar una declaración general, es común en matemáticas y lógica.

    No entiendo completamente el punto de TomášZato sobre que el código es finito. Seguramente el código es finito, pero un algoritmo DCE perfecto debe aplicarse a todo el código, que es un conjunto infinito. Del mismo modo, aunque el código en sí es finito, los conjuntos potenciales de entrada son infinitos, al igual que el tiempo de ejecución potencial del código.

    En cuanto a considerar la rama final no muerta: es segura en términos de la "aproximación conservadora" de la que hablo, pero no es suficiente para detectar todas las instancias de código muerto como lo solicita el OP.

Considere un código como este:

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

Claramente podemos eliminar print "goodbye"sin cambiar el comportamiento del programa. Por lo tanto, es un código muerto. Pero si hay una llamada a una función diferente en lugar de (true)la whilecondición, entonces no sabemos si podemos eliminarla o no, lo que lleva a la indecidibilidad.

Tenga en cuenta que no voy a pensar en esto por mi cuenta. Es un resultado bien conocido en la teoría de los compiladores. Se discute en The Tiger Book . (Es posible que pueda ver de dónde hablan en los libros de Google .

jmite
fuente
1
@ njzk2: Estamos tratando de mostrar que es imposible construir un eliminador de código muerto que elimine todo el código muerto, no es imposible construir un eliminador de código muerto que elimine algún código muerto. El ejemplo de impresión después de retorno puede eliminarse fácilmente utilizando técnicas de gráficos de flujo de control, pero no todo el código muerto puede eliminarse de esta manera.
user2357112 es compatible con Monica el
44
Esta respuesta hace referencia a comentarios. Mientras leo la respuesta, necesito saltar a los comentarios y luego regresar a la respuesta. Esto es confuso (doblemente cuando considera que los comentarios son frágiles y pueden perderse). Una respuesta independiente sería mucho más fácil de leer.
TRiG
1
@ TomášZato: considere el programa que incrementa una variable y verifica si es un número perfecto impar o no , terminando solo cuando encuentra dicho número. Claramente, este programa no depende de ninguna entrada externa. ¿Está afirmando que se puede determinar fácilmente si este programa finaliza o no? nnn
Gregory J. Puleo
3
@ TomášZato Estás equivocado en tu comprensión del problema de detención. Dada una máquina de Turing finita y una entrada finita , es imposible determinar si un bucle infinito mientras se ejecuta en . No lo he probado rigurosamente porque se ha demostrado una y otra vez, y es un principio fundamental de la informática. Hay un buen bosquejo de la prueba en Wikipediax M xMxMx
jmite
1
jmite, por favor incorpore comentarios válidos en la respuesta para que la respuesta sea independiente. Luego marque todos los comentarios que estén obsoletos como tal para que podamos limpiarlos. ¡Gracias!
Raphael
14

Este es un giro en la respuesta de jmite que evita la posible confusión sobre la no terminación. Daré un programa que siempre se detiene, puede tener un código muerto pero no podemos (siempre) algorítmicamente decidir si lo tiene.

Considere la siguiente clase de entradas para el identificador de código muerto:

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

Desde My xson fijos, simulateMstiene un código muerto con return 0if y only if Mno se detiene x.

Esto nos da inmediatamente una reducción del problema de detención a la verificación de código muerto: dado TM como instancia de problema de detención, cree el programa anterior con el código de : tiene código muerto si y solo si no se detiene por sí solo código.M MMxMM

Por lo tanto, la verificación de código muerto no es computable.

En caso de que no esté familiarizado con la reducción como técnica de prueba en este contexto, le recomiendo nuestro material de referencia .

Rafael
fuente
5

Una manera simple de demostrar este tipo de propiedad sin atascarse en detalles es usar el siguiente lema:

Lema: Para cualquier compilador C para un lenguaje completo de Turing, existe una función undecidable_but_true()que no toma argumentos y devuelve el verdadero booleano, de modo que C no puede predecir si undecidable_but_true()devuelve verdadero o falso.

Tenga en cuenta que la función depende del compilador. Dada una función undecidable_but_true1(), un compilador siempre se puede aumentar con el conocimiento de si esta función devuelve verdadero o falso; pero siempre hay alguna otra función undecidable_but_true2()que no se cubrirá.

Prueba: según el teorema de Rice , la propiedad "esta función devuelve verdadero" es indecidible. Por lo tanto, cualquier algoritmo de análisis estático no puede decidir esta propiedad para todas las funciones posibles.

Corolario: dado un compilador C, el siguiente programa contiene código muerto que no se puede detectar:

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

Una nota sobre Java: el lenguaje Java exige que los compiladores rechacen ciertos programas que contienen código inalcanzable, al tiempo que exige que el código se proporcione en todos los puntos accesibles (por ejemplo, el flujo de control en una función no vacía debe terminar con una returndeclaración). El lenguaje especifica exactamente cómo se realiza el análisis de código inalcanzable; Si no fuera así, sería imposible escribir programas portátiles. Dado un programa de la forma

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

es necesario especificar en qué casos el código inalcanzable debe ser seguido por algún otro código y en qué casos no debe ser seguido por ningún código. Un ejemplo de un programa Java que contiene código que es inalcanzable, pero no de una manera que los compiladores de Java puedan notar, aparece en 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- deja de ser malvado'
fuente
Tenga en cuenta que algunos compiladores para algunos idiomas pueden detectar que el final de day_of_weekes inalcanzable.
user253751
@immibis Sí, por ejemplo, los estudiantes de CS101 pueden hacerlo en mi experiencia (aunque es cierto que los estudiantes de CS101 no son un analizador estático de sonido, generalmente se olvidan de los casos negativos). Eso es parte de mi punto: es un ejemplo de un programa con código inalcanzable que un compilador de Java no detectará (al menos, puede advertir, pero no puede rechazar).
Gilles 'SO- deja de ser malvado'
1
Me temo que la redacción del Lemma es engañosa en el mejor de los casos, con un tinte de error. La indecidibilidad solo tiene sentido si lo expresas en términos de conjuntos (infinitos) de instancias. (El compilador hace producir una respuesta para cada función, y sabemos que no siempre puede ser correcto, pero decir que hay una sola instancia indecidible está apagado.) Su punto entre el lema y la prueba (que no se ajusta exactamente con el lema como se indicó) intenta arreglar esto, pero creo que sería mejor formular un lema claramente correcto.
Raphael
@Raphael Uh? No, el compilador no necesita producir una respuesta a la pregunta "¿es esta función constante?". No es necesario distinguir "No sé" de "no" para producir código de trabajo, pero eso no es relevante aquí ya que solo estamos interesados ​​en la parte de análisis estático del compilador, no en la parte de traducción de código. No entiendo lo que encuentra engañoso o incorrecto acerca de la declaración del lema, a menos que su punto sea que debería escribir "analizador estático" en lugar de "compilador".
Gilles 'SO- deja de ser malvado'
La afirmación suena como "la indecidibilidad significa que hay una instancia que no se puede resolver", lo cual es incorrecto. (Sé que no quieres decir eso, pero así es como se puede leer a los incautos / novatos, en mi humilde opinión).
Raphael
3

La respuesta de jmite se aplica a si el programa alguna vez saldrá de un cálculo, solo porque es infinito, no llamaría al código después de que esté muerto.

Sin embargo, hay otro enfoque: un problema para el cual hay una respuesta pero se desconoce:

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

Esta rutina, sin duda, no contiene código muerto - la función devolverá una respuesta que ejecuta un camino, pero no el otro. ¡Buena suerte para encontrarlo! Mi memoria es que ninguna computadora teórica puede resolver esto dentro de la vida útil del universo.

Con más detalle:

La Evaluate()función calcula qué lado gana un juego de ajedrez si ambos lados juegan perfectamente (con la máxima profundidad de búsqueda).

Los evaluadores de ajedrez normalmente miran hacia adelante en cada movimiento posible a una profundidad específica y luego intentan anotar el tablero en ese punto (a veces expandir ciertas ramas más lejos como mirar a la mitad de un intercambio o similar puede producir una percepción muy sesgada). son 17695 movimientos a medias, la búsqueda es exhaustiva, atravesará todos los juegos de ajedrez posibles. Dado que todos los juegos terminan, no hay problema en tratar de decidir qué tan buena es la posición de cada tablero (y, por lo tanto, no hay razón para mirar la lógica de evaluación del tablero, nunca se llamará), el resultado es una victoria, una pérdida o un empate. Si el resultado es un empate, el juego es justo, si el resultado no es un empate, es un juego injusto. Para expandirlo un poco obtenemos:

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);
    }
}

Tenga en cuenta, además, que será prácticamente imposible para el compilador darse cuenta de que Chessboard.Score () es un código muerto. El conocimiento de las reglas del ajedrez nos permite a los humanos resolver esto, pero para saberlo, debes saber que MakeMove nunca puede aumentar el conteo de piezas y que Chessboard.Draw () volverá verdadero si el conteo de piezas permanece estático durante demasiado tiempo. .

Tenga en cuenta que la profundidad de búsqueda es en medio movimientos, no en movimientos completos. Esto es normal para este tipo de rutina de IA, ya que es una rutina O (x ^ n): agregar una capa de búsqueda más tiene un efecto importante sobre cuánto tiempo tarda en ejecutarse.

Loren Pechtel
fuente
8
Asume que un algoritmo de verificación tendría que realizar el cálculo. Una falacia común! No, no puedes asumir nada sobre cómo funcionaría un corrector, de lo contrario no puedes refutar su existencia.
Raphael
66
La pregunta solicita una prueba de que es imposible detectar el código muerto. Su publicación contiene un ejemplo de un caso en el que sospecha que sería difícil detectar el código muerto. Esa no es una respuesta a la pregunta en cuestión.
David Richerby
2
@LorenPechtel No lo sé, pero eso no es una prueba. Ver también aquí ; Un ejemplo más claro de su error.
Rafael
3
Si ayuda, considere que, en teoría, no hay nada que impida que alguien ejecute su compilador más que la vida del universo; La única limitación es la practicidad. Un problema decidible es un problema decidible, incluso si está en la clase de complejidad NOELEMENTARIA.
Seudónimo
44
En otras palabras, esta respuesta es, en el mejor de los casos, una heurística destinada a mostrar por qué probablemente no sea fácil construir un compilador que detecte todos los códigos muertos, pero no es una prueba de imposibilidad. Este tipo de ejemplo podría ser útil como una forma de desarrollar la intuición para los estudiantes, pero no es una prueba. Al presentarse como una prueba, hace un mal servicio. La respuesta debe ser editada para indicar que es un ejemplo de construcción de intuición pero no una prueba de imposibilidad.
DW
-3

¡Creo que en un curso de informática, la noción de código muerto es interesante en el contexto de comprender la diferencia entre el tiempo de compilación y el tiempo de ejecución!

Un compilador puede determinar cuándo tiene un código que no se puede atravesar en ningún momento de tiempo de compilación, pero no puede hacerlo en tiempo de ejecución. un simple while-loop con entrada del usuario para la prueba de loop-break lo muestra

Si un compilador realmente puede determinar el código muerto de tiempo de ejecución (es decir, discernir que Turing está completo), entonces hay un argumento de que el código nunca necesita ejecutarse, ¡porque el trabajo ya está hecho!

Por lo menos, la existencia de código que pasa las comprobaciones de código muerto en tiempo de compilación ilustra la necesidad de una verificación pragmática de los límites en las entradas y la higiene general de la codificación (en el mundo real de los proyectos reales).

dwoz
fuente
1
La pregunta solicita una prueba de que es imposible detectar el código muerto. No has respondido esa pregunta.
David Richerby
Además, su afirmación de que "Un compilador puede determinar cuándo tiene un código que nunca se puede atravesar en tiempo de compilación" es incorrecta y contradice directamente lo que la pregunta le pide que pruebe.
David Richerby
@David Richerby, creo que puedes estar malinterpretándome. No estoy sugiriendo que la verificación en tiempo de compilación pueda encontrar TODOS los códigos muertos, definitivamente no. Estoy sugiriendo que hay un subconjunto del conjunto de todos los códigos muertos que se puede discernir en el momento de la compilación. Si escribo: if (true == false) {print ("algo");}, esa declaración de impresión será discernible en el momento de la compilación como código muerto. ¿No está de acuerdo con que este sea un contraejemplo de su afirmación?
dwoz
Claro, puedes determinar un código muerto. Pero si va a decir "determinar cuándo [tiene un código muerto]" sin calificaciones, eso, para mí, significa encontrar todo el código muerto, no solo parte de él.
David Richerby