El problema de la detención en el campo [cerrado]

Hace años, recuerdo haber leído una reseña (creo que en la revista Byte) de un producto llamado Basic Infinite Loop Finder o BILF. Se suponía que BILF escanearía tu código fuente de Microsoft Basic y encontraría cualquier bucle que no terminara. Afirmó ser capaz de encontrar cualquier bucle infinito en el código.

El revisor fue lo suficientemente inteligente como para señalar que para que ese programa funcione en todos los casos, tendría que resolver el problema de la detención y fue tan lejos como para proporcionar una prueba matemática de por qué no podía funcionar en todos los casos.

En el siguiente número, publicaron una carta de un representante de la compañía explicando que el problema se solucionaría en la próxima versión.

Actualización: me encontré con una imagen del artículo en imgur. Recordé la revista equivocada. Era Computación Creativa, no Byte. De lo contrario, es más o menos como lo recordaba.

Puedes ver una versión de alta resolución en imgur.

El proyecto en el que estoy trabajando ahora tiene problemas indecidibles por todas partes. Es un generador de pruebas unitarias, por lo que en general lo que intenta lograr es responder a la pregunta "qué hace este programa". Lo que es un ejemplo de un problema de detención. Otro problema que surgió durante el desarrollo es "¿se dan dos funciones (de prueba) iguales"? O incluso "¿importa el orden de esas dos llamadas (aserciones)"?

Qué es interesante de este proyecto es que, aunque no puedes responder esas preguntas en todas las situaciones, puedes encontrar soluciones inteligentes que resuelvan el problema el 90% del tiempo, lo que para este dominio es realmente muy bueno.

Otras herramientas que tratan de razonar sobre otro código, como la optimización de compiladores/intérpretes, herramientas de análisis de código estático, incluso herramientas de refactorización, son propensos a golpear (por lo tanto se ven obligados a encontrar soluciones a) el problema de detención.

Ejemplo 1. ¿Cuántas páginas de mi informe?

Cuando estaba aprendiendo a programar, jugué haciendo una herramienta para imprimir bonitos informes a partir de datos. Obviamente quería que fuera realmente flexible y potente para que fuera el generador de informes para terminar con todos los generadores de informes.

La definición del informe terminó siendo tan flexible que estaba completa. Podría mirar variables, elegir entre alternativas, usar bucles para repetir cosas.

Definí un built-in variable N, el número de páginas en la instancia del informe, por lo que podría poner una cadena que dijera "página n de N" en cada página. Hice dos pasadas, la primera para contar las páginas (durante las cuales N se puso a cero), y la segunda para generarlas, usando la N obtenida de la primera pasada.

A veces la primera pasada computaría N, y luego la segunda pasada generaría un número diferente de páginas (porque ahora la N distinta de cero cambiaría lo que hizo el informe). Intenté hacer pases iterativamente hasta que la N se estableció. Entonces me di cuenta de que esto era inútil porque ¿y si no se calmaba?

Esto lleva a la pregunta, "¿Puedo al menos detectar y advertir al usuario si la iteración nunca va a establecerse en un valor estable para el número de páginas que produce su informe?"Afortunadamente para este momento me había interesado en leer sobre Turing, Godel, computability, etc. e hizo la conexión.

Años más tarde me di cuenta de que MS Access a veces imprime "Página 6 de 5", que es una cosa verdaderamente maravillosa.

Ejemplo 2: Compiladores de C++

El proceso de compilación implica la expansión de plantillas. Las definiciones de plantilla se pueden seleccionar de múltiples especializaciones (lo suficientemente buenas como para servir como un "cond") y también pueden ser recursivas. Así que es un meta-sistema Turing completo (funcional puro), en el que las definiciones de la plantilla son el lenguaje, los tipos son los valores, y el compilador es realmente un intérprete. Este fue un accidente.

En consecuencia, no es posible examinar ningún programa dado de C++ y decir si el compilador podría en principio terminar con una compilación exitosa del programa.

Los proveedores de compiladores evitan esto limitando la profundidad de pila de la plantilla recursiva. Puede ajustar la profundidad en g++.

Hace muchas muchas lunas estaba ayudando a un consultor de nuestra empresa que estaba implementando un sistema ferroviario muy complejo para mover cestas de piezas metálicas dentro y fuera de un alto horno de 1500 grados. La vía en sí era un "mini-railyard" bastante complejo en el piso de la tienda que se cruzaba en un par de lugares. Varias plataformas motorizadas lanzarían cestas de piezas alrededor según un horario. Era muy importante que las puertas del horno estuvieran abiertas por un tiempo tan corto como posible.

Dado que la planta estaba en plena producción, el consultor no pudo ejecutar su software en 'tiempo real' para probar sus algoritmos de programación. En su lugar, escribió un bonito simulador gráfico. Mientras veíamos las plataformas virtuales moverse en su diseño de pista en pantalla, le pregunté "¿cómo sabrá si tiene algún conflicto de programación?"

Su respuesta rápida, "Fácil - la simulación nunca se detendrá."

El sofisticado análisis de código estático puede encontrarse con el problema de detención.

Por ejemplo, si una máquina virtual Java puede demostrar que un fragmento de código nunca accederá a un índice de matriz fuera de los límites, puede omitir esa comprobación y ejecutarse más rápido. Para algunos códigos esto es posible; a medida que se vuelve más complejo, se convierte en el problema de detención.

Esto sigue siendo un problema para los shaders en aplicaciones GPU. Si un sombreador tiene un bucle infinito (o un cálculo muy largo), ¿debería el controlador (después de algún límite de tiempo) detenerlo, matar el fragmento o simplemente dejarlo correr? Para juegos y otras cosas comerciales, el primero es probablemente lo que quieres, pero para la computación científica/GPU, el último es lo que quieres. Peor aún, algunas versiones de Windows asumen que dado que el controlador de gráficos no ha respondido durante algún tiempo, lo mata, lo que artificialmente limita la potencia de cálculo al realizar cálculos en la GPU.

No hay ninguna API para que una aplicación controle cómo debe comportarse el controlador o establecer el tiempo de espera o algo así, y ciertamente no hay manera para que el controlador diga si su sombreador va a terminar o no.

No se si esta situación ha mejorado recientemente, pero me gustaría saber.

Otra versión común de esto es "necesitamos eliminar cualquier interbloqueos en nuestro multi-roscado código". Una petición perfectamente razonable, desde el punto de vista de la gestión, pero para evitar bloqueos en el caso general, hay que analizar todos los posibles estados de bloqueo en los que puede entrar el software, lo que, no es de extrañar, equivale al problema de detención.

Hay maneras de "resolver" parcialmente los bloqueos en un sistema complejo mediante la imposición de otra capa en la parte superior del bloqueo (como un orden definido de adquisición), pero estos métodos no siempre son aplicables.

Por qué esto es equivalente al problema de detención:

Imagina que tienes dos bloqueos, A y B, y dos hilos, X e Y. Si el hilo X tiene bloqueo A, y quiere bloqueo B también, y el hilo Y tiene bloqueo B y quiere A también, entonces tienes un bloqueo.

Si tanto X como Y tienen acceso tanto a A como a B, entonces la única manera de asegurarse de que nunca llegue al mal estado es determinar todas las posibles rutas que cada hilo puede tomar a través del código, y el orden en el que pueden adquirir y mantener bloqueos en todos esos casos. Luego determina si los dos hilos pueden adquirir más de un bloqueo en un orden diferente.

Pero, determinar todas las rutas posibles que cada hilo puede tomar a través del código es (en el caso general) equivalente al problema de detención.

El sistema de pruebas de Perl mantiene un contador de pruebas. Que poner el número de pruebas que se van a ejecutar en la parte superior del programa, o declarar que no vas a seguir. Esta guardia contra su prueba salir prematuramente, pero hay otros guardias por lo que no es tan importante.

De vez en cuando alguien intenta escribir un programa para contar el número de pruebas para usted. Esto es, por supuesto, derrotado por un simple bucle. Aran hacia adelante de todos modos, haciendo más y más elaborar trucos para tratar de detectar bucles y adivinar cuántas iteraciones habrá y resolver el problema de detención. Por lo general, declaran que solo tiene que ser "lo suficientemente bueno".

He aquí un ejemplo particularmente elaborado.

Una vez estuve trabajando en un proyecto de integración en el dominio ATM (Automated Teller Machines). El cliente me pidió que generara un informe de mi sistema para las transacciones enviadas por el conmutador de país que no fueron recibidas por mi sistema!!

Encontré un artículo de Berkeley: Looper: Detección ligera de Bucles Infinitos en Tiempo de ejecución http://www.eecs.berkeley.edu / ~jburnim / pubs / BurnimJalbertStergiouSen-ASE09. pdf

LOOPER puede ser útil ya que la mayoría de los bucles infinitos son errores triviales. Sin embargo, este documento ni siquiera menciona el problema de la detención!

¿Qué dicen sobre sus limitaciones?

[LOOPER] típicamente no puede razonar sobre bucles donde no se termina depende de la particulars of heap mutation in every loop iteration. Esto se debe a que nuestra ejecución simbólica es conservadora en concretizar punteros, y nuestro razonamiento simbólico insuficientemente poderoso. Creemos combinar nuestras técnicas con el análisis de formas y más poderosa generación invariante y probar sería valioso labor futura.

En otras palabras, "el problema se solucionará en la próxima versión".

De la Descripción funcional del Editor Visual (Eclipse) :

El Editor Visual de Eclipse (VE) puede ser utilizado para abrir cualquiera .archivo java. Entonces analiza el código fuente de Java buscando para visual frijoles. ...

Algunas herramientas de edición visual solo proporcionar un modelo visual de código que esa herramienta visual en particular tiene generar. Posterior edición directa del código fuente puede prevenir la herramienta visual de analizar el código y construyendo un modelo.

Eclipse VE, sin embargo, ... puede ser se utiliza para editar GUI desde cero, o desde archivos Java que han sido 'hardcoded' or built in a different herramienta visual. El archivo fuente puede o bien se actualizará utilizando el gráfico Visor, Árbol de JavaBeans o Propiedades ver o que se puede editar directamente por el Editor de Fuentes.

No relacionado, aquí hay alguien pidiendo la detención problema dentro de Eclipse.

Para ser justos, el dominio de VE es bastante limitado, y probablemente no se volverá loco por cosas complicadas como la reflexión. Aún así, la afirmación de construir GUI a partir de cualquiera archivo java parece halt-ish.

"¿Cómo me puede asegurar que su código está 100% libre de errores?"