language agnostic - La detención en el campo
language-agnostic field (13)
¿Cuándo se ha encontrado personalmente con el problema de detención en el campo? Esto puede ser cuando un compañero de trabajo / jefe sugirió una solución que violaría los límites fundamentales de la computación, o cuando se dio cuenta de que un problema que estaba tratando de resolver era, de hecho, imposible de resolver.
La última vez que se me ocurrió fue cuando estudiaba las fichas de tipo. Nuestra clase se dio cuenta de que sería imposible escribir un corrector de tipo perfecto (uno que aceptaría todos los programas que se ejecutarían sin errores de tipo y rechazaría todos los programas que se ejecutarían con errores de tipo) porque esto resolvería el problema de detención. . Otro fue cuando nos dimos cuenta, en la misma clase, de que sería imposible determinar si una división ocurriría alguna vez por cero, en la etapa de verificación de tipo, porque verificar si un número, en tiempo de ejecución, es cero, también es una versión del problema de detención.
"¿Cómo me puedes asegurar que tu código está 100% libre de errores?"
Desde la Descripción funcional del editor visual (Eclipse) :
El Eclipse Visual Editor (VE) se puede usar para abrir cualquier archivo .java. A continuación, analiza el código fuente de Java en busca de beans visuales. ...
Algunas herramientas de edición visual solo proporcionarán un modelo visual de código que esa herramienta visual en particular ha generado. La edición directa posterior del código fuente puede evitar que la herramienta visual analice el código y cree un modelo.
Eclipse VE, sin embargo, ... puede usarse para editar GUI desde cero, o desde archivos Java que han sido ''codificados'' o construidos en una herramienta visual diferente. El archivo de origen puede actualizarse utilizando el Visor gráfico, el Árbol de JavaBeans o la vista Propiedades o puede editarlo directamente el Editor de origen.
Quizás debería quedarme con Matisse por ahora.
Sin relación, aquí hay alguien que pregunta por el problema de detención 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í, el reclamo para compilar GUI a partir de cualquier archivo java parece alto.
El sistema de prueba de Perl mantiene un contador de prueba. O bien, coloca la cantidad de pruebas que ejecutará en la parte superior del programa, o declara que no va a rastrearlas. Esta protección contra su prueba sale prematuramente, pero hay otros guardias así 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. Siguen adelante de todos modos, haciendo trucos cada vez más elaborados 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".
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 probar que una porción 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 para detenerse.
Encontré un artículo de Berkeley: Looper: Detección ligera de bucles Infinite 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 detención.
¿Qué dicen sobre sus limitaciones?
[LOOPER] normalmente no puede razonar sobre bucles donde la no terminación depende de las particularidades de la mutación de pila en cada iteración de bucle. Esto se debe a que nuestra ejecución simbólica es conservadora al concretar punteros, y nuestro razonamiento simbólico es insuficientemente poderoso. Creemos que la combinación de nuestras técnicas con el análisis de formas y la generación y prueba de invariantes más potentes sería un trabajo futuro valioso.
En otras palabras, "el problema se solucionará en la próxima versión".
Esto sigue siendo un problema para los sombreadores en aplicaciones de 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, lo primero es probablemente lo que quieres, pero para informática científica / GPU, lo último es lo que quieres. Peor aún, algunas versiones de Windows suponen que, dado que el controlador de gráficos no responde durante un tiempo, lo mata, lo que limita artificialmente la potencia de cálculo al hacer cálculos en la GPU.
No hay API para que una aplicación controle cómo debe comportarse el controlador o establezca el tiempo de espera o algo así, y ciertamente no hay forma de que el controlador diga si su sombreador va a terminar o no.
No sé si esta situación ha mejorado recientemente, pero me gustaría saberlo.
Hace años, recuerdo haber leído una reseña (en la revista Byte, creo) de un producto llamado Basic Infinite Loop Finder o BILF. Se suponía que BILF escaneaba su código fuente básico de Microsoft y buscaba cualquier bucle que no terminaba. Afirmó poder 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 interrupción e ir tan lejos como para proporcionar una prueba matemática de por qué no podrí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 sobre imgur. Me acordé de la revista equivocada. Era Computación Creativa, no Byte. De lo contrario, es más o menos como lo recordaba.
Puede ver una versión de alta resolución en imgur .
Hace muchas lunas asistí a un consultor de nuestra empresa que estaba implementando un sistema ferroviario muy complejo para mover cestas de piezas de metal dentro y fuera de un alto horno de 1500 grados. La pista en sí era una "mini-terminal" bastante compleja en el piso de la tienda que se intersectaba en un par de lugares. Varias paletas motorizadas transportarían canastas de piezas de acuerdo con un cronograma. Era muy importante que las puertas del horno estuvieran abiertas durante el menor tiempo posible.
Como 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 cambio, escribió un bonito simulador gráfico. Mientras observamos que las paletas virtuales se movían 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á".
Otra versión común de esto es "tenemos que eliminar cualquier punto muerto en nuestro código de subprocesos múltiples". Una solicitud perfectamente razonable, desde la perspectiva de la administración, pero para evitar interbloqueos en el caso general, debe analizar todos los estados de bloqueo posibles en los que pueda incurrir el software, lo que no es sorpresa, equivalente al problema de detención.
Hay formas de "resolver" parcialmente los interbloqueos en un sistema complejo mediante la imposición de otra capa en la parte superior del bloqueo (como un orden de adquisición definido), pero estos métodos no siempre son aplicables.
Por qué esto es equivalente al problema de detención:
Imagine que tiene dos bloqueos, A y B, y dos hilos, X e Y. Si el hilo X tiene bloqueo A, y también desea bloquear B, y el hilo Y tiene bloqueo B y quiere A también, entonces tiene un punto muerto.
Si tanto X como Y tienen acceso a A y B, entonces la única manera de asegurarse de que nunca ingrese en el estado malo es determinar todas las rutas posibles que cada hilo puede tomar a través del código, y el orden en que puede adquirir y mantener bloqueos en todos esos casos. A continuación, determina si los dos subprocesos 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.
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!
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" . Que es una instancia de un problema de detención. Otro problema que surgió durante el desarrollo es "¿se dan las mismas dos funciones (de prueba)" ? O incluso "¿Importa el orden de esas dos llamadas (aserciones)" ?
Lo interesante de este proyecto es que, aunque no pueda responder esas preguntas en todas las situaciones, puede encontrar soluciones inteligentes que resuelvan el problema el 90% del tiempo, lo que para este dominio es realmente muy bueno.
Es probable que otras herramientas que intentan razonar sobre otro código, como optimizar compiladores / intérpretes, herramientas de análisis de código estático e incluso herramientas de refactorización, se vean afectadas (por lo tanto, se vean forzadas a encontrar soluciones) al problema de detención.
Literalmente me asignaron el problema de detención, como en "escribir un complemento de monitor para determinar si un host está permanentemente inactivo". ¿Seriamente? OK, entonces solo le daré un umbral. "No, porque podría volver a aparecer después".
Se produjo una gran exposición teórica.
Ejemplo 1. ¿Cuántas páginas hay en mi informe?
Cuando estaba aprendiendo a programar, jugué con la creación de una herramienta para imprimir informes bonitos a partir de datos. Obviamente, quería que fuera realmente flexible y potente, de modo que sería el generador de informes el que finalizara con todos los generadores de informes.
La definición del informe terminó siendo tan flexible que fue completa. Podría observar variables, elegir entre alternativas, usar bucles para repetir cosas.
Definí una variable incorporada 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 pases, el primero en contar las páginas (durante el cual N se estableció en cero) y el segundo en generarlas, usando el N obtenido de la primera pasada.
Algunas veces, el primer pase computaría N, y luego el segundo pase generaría un número diferente de páginas (porque ahora el N no nulo cambiaría lo que el informe hizo). Intenté hacer pases iterativamente hasta que el N se calmó. Entonces me di cuenta de que esto era inútil porque, ¿qué pasaría si no se calmaba?
Esto lleva a la pregunta: "¿Al menos puedo detectar y advertir al usuario si la iteración nunca se va a establecer en un valor estable para la cantidad de páginas que produce su informe?" Afortunadamente en este momento me interesé en leer sobre Turing, Godel, computabilidad, etc. y establecí la conexión.
Años después noté que MS Access a veces imprime "Página 6 de 5", lo cual es algo realmente maravilloso.
Ejemplo 2: compiladores C ++
El proceso de compilación implica expandir plantillas. Las definiciones de plantilla pueden seleccionarse de múltiples especializaciones (lo suficientemente buenas como para servir como "cond") y también pueden ser recursivas. Entonces, es un meta-sistema de Turing completo (funcional puro), en el cual las definiciones de plantilla son el lenguaje, los tipos son los valores y el compilador es realmente un intérprete. Esto fue un accidente.
En consecuencia, no es posible examinar ningún programa C ++ dado y decir si el compilador podría terminar en principio con una compilación exitosa del programa.
Los vendedores de compiladores solucionan esto limitando la profundidad de pila de la plantilla recursiva. Puede ajustar la profundidad en g ++.