¿Cuándo has encontrado el problema de la detención en el campo? [cerrado]
https://stackoverflow.com/questions/235984
-
04-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
¿Cuándo ha encontrado personalmente 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.
El momento más reciente en que se me ocurrió fue cuando estudiaba las verificadoras de tipos. Nuestra clase se dio cuenta de que sería imposible escribir un verificador de tipo perfecto (uno que aceptara 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, de hecho, resolvería el problema de detención . Otra fue cuando nos dimos cuenta, en la misma clase, 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.
Solución
I literalmente se me asignó 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 mucha exposición teórica.
Otros consejos
Hace años, recuerdo haber leído una crítica (en la revista Byte, creo) de un producto llamado Basic Infinite Loop Finder o BILF. Se suponía que BILF escaneaba el código fuente de Microsoft Basic y encontraba los bucles que no terminaban. 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 el programa funcione en todos los casos, tendría que resolver el problema de detención y llegó a proporcionar una prueba matemática de por qué no podía funcionar en todos los casos.
En el próximo 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: encontré una imagen del artículo en imgur. Me acordé de la revista equivocada. Fue la computación creativa, no el byte. De lo contrario, es más o menos como lo recordaba.
Puede ver una versión de alta resolución de la misma 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 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 les dan dos funciones (de prueba) iguales '' ? O incluso " ¿importa el orden de esas dos llamadas (aserciones) " ?
Lo interesante de este proyecto es que, aunque no puede responder esas preguntas en todas situaciones, puede encontrar soluciones inteligentes que resuelvan el problema el 90% de El tiempo, que para este dominio es realmente muy bueno.
Es probable que otras herramientas que intentan 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, afecten (por lo tanto, se vean obligadas a encontrar soluciones) al problema de detención.
Ejemplo 1. ¿Cuántas páginas en mi informe?
Cuando estaba aprendiendo a programar, jugué haciendo una herramienta para imprimir informes bonitos a partir de datos. Obviamente, quería que fuera realmente flexible y potente para que fuera el generador de informes que finalizara todos los generadores de informes.
La definición del informe terminó siendo tan flexible que se completó con Turing. Podría mirar 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, para que pueda poner una cadena que diga " página n de N " en cada página Hice dos pases, el primero para contar las páginas (durante el cual N se estableció en cero), y el segundo para generarlos realmente, usando el N obtenido del primer paso.
A veces, el primer pase calcularía N, y luego el segundo pase generaría un número diferente de páginas (porque ahora el N distinto de cero cambiaría lo que hizo el informe). Intenté hacer pases iterativamente hasta que la N se calmó. 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 se va a establecer en un valor estable para el número de páginas que produce su informe?" Afortunadamente para entonces, me había interesado en leer sobre Turing, Godel, computabilidad, etc. e hice 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 de C ++
El proceso de compilación implica expandir 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. Por lo tanto, es un meta-sistema completo de Turing (puramente funcional), en el que las definiciones de plantilla son el lenguaje, los tipos son los valores y el compilador es realmente un intérprete. Esto fue un accidente.
Por consiguiente, no es posible examinar ningún programa C ++ dado 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 la pila de plantillas recursivas. Puede ajustar la profundidad en g ++.
Hace muchas, muchas lunas asistí a un consultor de nuestra empresa que estaba implementando un sistema de riel muy complejo para mover cestas de piezas metálicas dentro y fuera de un alto horno de 1500 grados. La pista en sí era un 'mini-railyard' bastante complejo en el taller que se cruzaba en un par de lugares. Varios palets motorizados transportarían cestas de partes de acuerdo con un horario. Fue 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 su lugar, escribió un simulador bonito y gráfico. Mientras observábamos cómo se movían las paletas virtuales en el diseño de su 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 análisis de código estático sofisticado puede encontrarse con el problema de la detención.
Por ejemplo, si una máquina virtual Java puede probar 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 la detenció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 funcionar? Para juegos y otras cosas comerciales, lo primero es probablemente lo que quieres, pero para computación 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 ha respondido durante algún tiempo, lo mata, lo que limita artificialmente la potencia de cálculo cuando se realiza el cálculo en la GPU.
No hay 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 forma de que el controlador sepa si su sombreador va a terminar o no.
No sé si esta situación ha mejorado recientemente, pero me gustaría saberlo.
Otra versión común de esto es "necesitamos eliminar cualquier punto muerto en nuestro código multiproceso". Una solicitud perfectamente razonable, desde la perspectiva de la administración, pero para evitar puntos muertos en el caso general, debe analizar todos los posibles estados de bloqueo en los que puede entrar el software, lo que no es sorpresa, equivalente al problema de detención.
Hay formas de "resolver" parcialmente puntos muertos en un sistema complejo al imponer 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:
Imagina que tienes dos bloqueos, A y B, y dos hilos, X e Y. Si el hilo X tiene el bloqueo A, y también quiere el bloqueo B, y el hilo Y tiene el bloqueo B y quiere A también, entonces tienes un punto muerto .
Si tanto X como Y tienen acceso tanto a A como a B, entonces la única forma de asegurarse de que nunca llegue al mal estado es determinar todas las rutas posibles que cada subproceso puede tomar a través del código, y el orden en el que pueden adquirir y mantener cerraduras en todos esos casos. Luego, determina si los dos subprocesos pueden adquirir más de un bloqueo en un orden diferente.
Pero, determinar todas las rutas posibles que cada subproceso puede tomar a través del código es (en el caso general) equivalente al problema de detención.
El sistema de prueba de Perl mantiene un contador de prueba. O bien, coloca el número de pruebas que vas a ejecutar en la parte superior del programa, o declaras que no lo vas a seguir. Esta protección contra su prueba sale 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 por usted. Esto es, por supuesto, derrotado por un simple bucle. Siguen adelante de todos modos, haciendo trucos cada vez más complicados para intentar detectar los bucles y adivinar cuántas iteraciones habrá y resolver el problema de la detención. Por lo general, declaran que solo tiene que ser " suficientemente bueno " ;.
Una vez estuve trabajando en un proyecto de integración en el dominio ATM (cajeros automáticos). ¡El cliente me solicitó que generara un informe de mi sistema para las transacciones enviadas por el cambio 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] normalmente no puede razonar acerca de los bucles donde no hay terminación depende de los detalles de la mutación del montón en cada iteración de bucle. Esto se debe a que nuestra ejecución simbólica es conservadora en La concreción de los punteros, y nuestro razonamiento simbólico insuficientemente. poderoso. Creemos que combinando nuestras técnicas con el análisis de formas. y la generación invariante más poderosa y la prueba serían valiosas trabajo futuro.
En otras palabras, " el problema se solucionará en la próxima versión " ;.
De la Descripción general funcional de (Eclipse) Editor visual :
El Eclipse Visual Editor (VE) puede ser se usa para abrir el archivo any .java. Entonces analiza el código fuente de Java buscando para frijoles visuales. ...
Algunas herramientas de edición visual solo lo harán proporcionar un modelo visual de código que esa herramienta visual particular en sí tiene generado. Edición directa posterior del código fuente puede prevenir el herramienta visual de analizar el código y construyendo un modelo.
Eclipse VE, sin embargo, ... puede ser se usa para editar GUI desde cero, o de archivos Java que han sido 'codificado' o construido en un diferente herramienta visual El archivo fuente puede ya sea actualizado utilizando el gráfico Visor, JavaBeans Tree o Propiedades ver o se puede editar directamente por el editor de fuente.
Tal vez debería seguir con Matisse por ahora.
No relacionado, aquí hay alguien pidiendo 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 difíciles como la reflexión. Aún así, la afirmación de construir una GUI a partir de any java parece ser halt-ish.
" ¿Cómo puede asegurarme que su código está 100% libre de errores? "
