Recuperación del desbordamiento de la pila o agotamiento del montón en un programa Haskell

Question

Actualmente estoy escribiendo un algoritmo genético en Haskell en el que mis cromosomas son estructuras bastante complejas que representan los sistemas ejecutables.

Para poder evaluar la aptitud de mis cromosomas tengo que ejecutar una función evolution que realiza un ciclo computacional de un sistema dado. La condición física se calcula simplemente contando cuántas veces se puede aplicar evolution antes de que no haya cambios en el sistema (en cuyo caso el sistema finaliza).

El problema ahora es el siguiente: algunos sistemas pueden ejecutarse infinitamente largos y nunca terminarán; quiero penalizarlos (dándoles poca puntuación). Simplemente podría poner un cierto límite en el número de pasos, pero no resuelve otro problema.

Algunos de mis sistemas realizan cálculos exponenciales (es decir, incluso para valores pequeños de los pasos de evloution crecen a tamaño gigante) y causan ERROR - Control stack overflow. Para el observador humano, está claro que nunca terminarán, pero el algoritmo no tiene forma de saber, por lo que corre y se aplasta.

Mi pregunta es: ¿Es posible recuperarse de dicho error? Me gustaría que mi algoritmo siga funcionando después de encontrar este problema y simplemente ajustar la puntuación del cromosoma en consecuencia.

Me parece que la mejor solución sería decirle al programa: "Oye, intenta hacer esto, pero si no lo haces, no te preocupes. Sé cómo manejarlo". Sin embargo, ni siquiera estoy seguro de si eso es posible. Si no, ¿hay alguna alternativa?

Answer 1

Esto será difícil de realizar de forma fiable desde dentro de Haskell, aunque en algunas condiciones GHC will raise exceptions for these conditions. (Necesitarás GHC 7).

import Control.Exception 

Si realmente se desea capturar los desbordamientos de pila, esto es posible, como muestra este ejemplo:

> handle (\StackOverflow -> return Nothing) $ 
       return . Just $! foldr (+) 0 (replicate (2^25) 1) 
Nothing 

o la captura de cualquier excepción asíncrona (incluyendo el agotamiento montón):

> handle (\(e :: AsyncException) -> print e >> return Nothing) $ 
       return . Just $! foldr (+) 0 (replicate (2^25) 1) 
stack overflow 
Nothing 

Sin embargo, esto es frágil.

Como alternativa, con GHC flags puede imponer el tamaño máximo de pila (o montón) en un proceso compilado por GHC, haciendo que muera si excede esos límites (parece que GHC no tiene un límite máximo de pila en estos días).

Si se compila el programa Haskell con GHC (como se recomienda), ejecutándolo como:

$ ghc -O --make A.hs -rtsopts 

se aplica el límite de pila baja a continuación:

$ ./A +RTS -M1M -K1M 
Heap exhausted; 

Esto requiere GHC. (De nuevo, no deberías estar usando Abrazos para este tipo de trabajo). Finalmente, debe asegurarse de que sus programas no usan excesivamente en primer lugar, a través del profiling in GHC.

Answer 2

It seems to me like the best solution would be to tell the program: 
"Hey, try doing this, but if you fail don't worry. I know how to handle it" 

En la mayoría de los idiomas que serían un bloque try/catch. No estoy seguro de cuál es el equivalente en Haskell, o incluso si existe algún equivalente. Además, dudo que un constructo try/catch pueda atrapar/manejar efectivamente una condición de desbordamiento de la pila.

Pero, ¿sería posible aplicar algunas restricciones razonables para evitar el desbordamiento? Por ejemplo, tal vez podría establecer un límite superior en el tamaño de un sistema, y ​​controlar cómo cada sistema se acerca al límite de una iteración a la siguiente. Entonces podría aplicar una regla como "si en un solo evolution un sistema excedió su límite superior o consumió más del 50% del espacio restante entre su asignación anterior y su límite superior, ese sistema se termina y sufre una penalización de puntaje ".

Answer 3

Creo que una solución general aquí es proporcionar una forma de medir el tiempo de cálculo y matarlo si lleva demasiado tiempo. Simplemente puede agregar un contador a su función de evaluación si es recursiva y si cae a cero, devuelve un valor de error, por ejemplo, Nothing, de lo contrario es Just result.

Este enfoque puede implementarse de formas distintas al parámetro de conteo explícito, por ejemplo, poniendo este contador en mónada utilizado por evaluación (si su código es monádico) o, impuramente, ejecutando computación en un hilo separado que se eliminará en se acabó el tiempo.

Preferiría usar cualquier solución pura, ya que sería más confiable.

Answer 4

Un pensamiento sobre su algoritmo genético: Parte de la aptitud de sus cromosomas es que no consumen demasiados recursos computacionales. La pregunta que hiciste define "demasiados recursos" como el bloqueo del sistema de tiempo de ejecución. Esta es una medida bastante arbitraria y algo aleatoria.

Sabiendo que se agregará a la complejidad de su función evolve, aún sugeriría que esta función tenga conocimiento de los recursos computacionales que consume un cromosoma. Esto le permite afinar cuando ha "comido" demasiado y muere prematuramente de "inanición". También podría permitirle ajustar su penalización según la rapidez con que el cromosoma se volvió exponencial con la idea de que un cromosoma apenas exponencial está más en forma que uno con un factor de ramificación extremadamente alto.