Eager versus Lazy Haskell. Listas infinitas posibles en idiomas impacientes?

Question

Aparentemente, es posible implementar Haskell de modo que se evalúe con entusiasmo sin cambiar la semántica del lenguaje en absoluto. Si eso es cierto, ¿cómo se manejan las estructuras de datos infinitas?

http://csg.csail.mit.edu/pubs/haskell.html

Por lo tanto, una gran cantidad de tiempo se dedica a la creación y la destrucción de piezas suspendidas de computación (procesadores). Con demasiada frecuencia, estos cálculos son lo suficientemente simples como para que sea tan fácil evaluarlos en su lugar. Faxen y otros han utilizado el análisis estático para exponer tales oportunidades para el afán. En su lugar, proponemos utilizar el afán en todas partes, mientras usamos mecanismos que nos permiten recuperar si nuestro programa está demasiado ansioso.

Lo más importante es que "tenemos mecanismos para recuperar si nuestro programa está demasiado ansioso". ¿Cuáles son estos mecanismos? ¿Cómo lo permiten para las estructuras de datos infinitas y los otros aspectos de la evaluación perezosa que me han hecho creer que son imposibles en un lenguaje entusiasta?

Answer 1

Eso no es del todo cierto: puede evaluar los términos de Haskell con entusiasmo si puede demostrar que no divergirán.

Por ejemplo, cuando se ve f x, se podía primera ejecutar hasta 1.000 pasos de x (detenerse si se llega a WHNF (forma normal débil cabeza) o un error), y luego pasarlo a f - la semántica se conserva, pero si cree que x va a ser evaluado, entonces puede hacer que esto ocurra antes de tiempo como una optimización.

Si x = fix id, simplemente se dará por vencido después de 1.000 pasos de no ir a ninguna parte. Si x = undefined, causará un error y se dará por vencido (restaurando el procesador original y pasándolo a f). Y así.

Si x = [1..], entonces podría terminar reduciendo a 1 : 2 : 3 : ... : 999 : 1000 : [1001..], alcanzar el límite, y detenerse allí, pasando el resultado a f.

Básicamente: Al probar que una expresión no puede diferir, o al limitar la evaluación para que las cosas terminen aunque lo haga. Sin cambios en la semántica, y posiblemente una gran mejora en el rendimiento.

Por supuesto, la desventaja es que si x resulta ser algún cálculo muy caro que f solamente utiliza la mitad de, pasará de 1.000 pasos de reducción de la pérdida de tiempo. Y en el caso de [1..], podría terminar usando mucha memoria para almacenar una lista; si f procesa la lista un elemento a la vez, tirando la cabeza cada vez, entonces perderá la memoria. Es por eso que es complicado :)

La página que se vinculó originalmente entra en más detalles en cuanto a las técnicas específicas utilizadas.