¿Puede un entorno de tiempo de ejecución detectar un bucle infinito?

¿Sería posible que un entorno de tiempo de ejecución detecte bucles infinitos y posteriormente detenga el proceso asociado, o la implementación de dicha lógica sería equivalente a resolver el problema de detención?

A los efectos de esta pregunta, defino un "bucle infinito" para que signifique una serie de instrucciones y datos de pila / montón de inicio asociados que, cuando se ejecutan, devuelven el proceso exactamente al mismo estado (incluidos los datos) como estaba antes iniciando el ciclo infinito. (En otras palabras, un programa que genera una expansión decimal indefinidamente larga de pi no está "atascado" en un "bucle infinito", porque en cada iteración, tiene más dígitos de pi en algún lugar de su memoria asociada).

(Portado de /programming//q/16250472/1858225 )

Teóricamente podría ser posible que un entorno de tiempo de ejecución compruebe dichos bucles utilizando el siguiente procedimiento:

Después de que se ejecute la instrucción, el entorno de ejecución generará una imagen completa del estado de un proceso en ejecución (es decir, toda la memoria asociada con él, incluidos los registros, la PC, la pila, el montón y los globales), guardará esa imagen en algún lugar y luego la comprobará en vea si coincide con alguna de sus imágenes guardadas previamente para ese proceso. Si hay una coincidencia, el proceso se atasca en un bucle infinito. De lo contrario, se ejecuta la siguiente instrucción y se repite el proceso.

De hecho, en lugar de realizar esta verificación después de cada instrucción, el entorno de ejecución simplemente podría pausar el proceso periódicamente y hacer un estado de guardado. Si el proceso está atascado en un bucle infinito que involucra n estados, luego, como máximo, n verificaciones, se observará un estado duplicado.

Tenga en cuenta, por supuesto, que esto no es una solución al problema de detención; La distinción se discute aquí .

Pero tal característica sería un enorme desperdicio de recursos ; pausar continuamente un proceso para guardar toda la memoria asociada con él lo ralentizaría enormemente y consumiría una enorme cantidad de memoria muy rápidamente. (Aunque las imágenes antiguas podrían eliminarse después de un tiempo, sería arriesgado limitar el número total de imágenes que podrían guardarse porque un gran bucle infinito, es decir, uno con muchos estados) podría no quedar atrapado si hay muy pocos estados guardados en la memoria.) Además, esta característica en realidad no proporcionaría tantos beneficios, ya que su capacidad para detectar errores sería extremadamente limitada y porque es relativamente simple encontrar bucles infinitos con otros métodos de depuración (como simplemente recorrer el código y reconociendo el error lógico).

Por lo tanto, dudo que exista un entorno de tiempo de ejecución o que exista, a menos que alguien lo programe solo por diversión. (Lo cual estoy un poco tentado a hacer ahora).

Supongamos que el programa no interactúa con el mundo exterior, por lo que es realmente posible encapsular todo el estado del programa. (Esto significa que no hace ninguna entrada, al menos). Además, supongamos que el programa se está ejecutando en un entorno determinista para que cada estado tenga un sucesor único, lo que significa que el tiempo de ejecución no está enhebrado o que el subproceso se puede reducir determinísticamente a una secuencia.

Bajo estos supuestos altamente improbables pero teóricamente no limitantes, podemos duplicar el programa y ejecutarlo en dos tiempos de ejecución separados; cada uno hará exactamente el mismo cálculo.

Entonces hagamos eso. Lo ejecutaremos una vez en el tiempo de ejecución de Tortoise, y al mismo tiempo lo ejecutaremos en el tiempo de ejecución de Hare. Sin embargo, haremos los arreglos para que el tiempo de ejecución de Hare funcione exactamente el doble de rápido; cada vez que el tiempo de ejecución de Tortoise da un paso, el tiempo de ejecución de Hare da dos pasos.

$n$$p$$kn$$k$$kn\ge p$

El costo total de la prueba es un estado adicional y una comparación de estado por paso, y terminará en no más de tres veces el número de pasos necesarios para que el programa complete su primer ciclo. (Una vez en la tortuga y dos veces en la liebre, por un total de tres veces).

Como los términos que utilicé implican, este es solo el famoso algoritmo de detección de ciclos de tortugas y liebres de Robert Floyd .

Justo cuando iba a sugerir el algoritmo de detección de ciclos de Floyd, la publicación de Rici me convenció. Sin embargo, todo se puede hacer más práctico al acelerar las comparaciones de estados completos.

El cuello de botella del algoritmo propuesto sería comparar el estado completo. Estas comparaciones generalmente no terminarán, pero se detendrán temprano --- en la primera diferencia. Una optimización es recordar dónde ocurrieron las diferencias pasadas y verificar primero esas partes del estado. Por ejemplo, mantenga una lista de ubicaciones y revise esta lista antes de hacer una comparación completa. Cuando una ubicación de esta lista expone una diferencia, detenga la comparación (con error) y mueva la ubicación al frente de la lista.

Un enfoque diferente (y potencialmente más escalable) es utilizar hashing incremental. Elija una función del estado completo de modo que los valores hash sean fáciles de ajustar en O (1) cuando alguna parte del estado cambia. Por ejemplo, tome una suma ponderada de palabras de estado mod con un primo grande y concatene con la suma de ponderación mod algún otro primo grande (también puede agregar una suma ponderada modular de cuadrados de palabras, con diferente peso y módulo). De esta manera, las actualizaciones hash tomarán O (1) tiempo en cada paso de ejecución, y las comparaciones tomarán O (1) tiempo hasta que recibas un golpe. La probabilidad de un falso positivo (es decir, los hashes coinciden mientras los estados difieren) es muy baja, e incluso si esto sucede, se amortizará en un gran número de negativos verdaderos (los falsos negativos son imposibles).

Por supuesto, en la práctica, parece más probable entrar en situaciones como generar dígitos del número pi --- las cosas siguen cambiando, pero nunca terminan. Otra posibilidad frecuente es que el bucle infinito asigne memoria, en cuyo caso agota rápidamente toda la memoria disponible.

En mi curso sobre algoritmos y estructuras de datos, nuestro autograder tiene que lidiar con los envíos de los estudiantes que a veces entran en bucles infinitos. Esto se soluciona con un tiempo de espera de 30 segundos y un cierto límite de memoria. Ambos son mucho más flexibles que los presupuestos de tiempo de ejecución y memoria que imponemos como parte de la calificación. No estoy seguro de si la implementación de la detección de bucle infinito verdadero tendría mucho sentido en este contexto porque tales programas se ejecutarán un poco más lento (aquí es donde el soporte de hardware para el hash de estado podría ayudar, pero nuevamente necesitaría usos adicionales para justifica esto). Cuando los estudiantes saben que su programa expiró, generalmente pueden encontrar el ciclo infinito.

La herramienta de terminación AProVE realiza un análisis estático en los sistemas de reescritura (incluida una subclase de programas Haskell) que puede probar la no terminación, dando un ejemplo real de programa sin terminación. La técnica es bastante poderosa y funciona usando una variante de una técnica llamada estrechamiento .

Sin embargo, hasta donde sé, no ha habido mucho trabajo para detectar la no terminación real de los idiomas generales.