¿Por qué es útil el concepto de evaluación perezosa?

Parece que la evaluación perezosa de las expresiones puede hacer que un programador pierda el control sobre el orden en que se ejecuta su código. Tengo problemas para entender por qué esto sería aceptable o deseado por un programador.

¿Cómo se puede usar este paradigma para construir un software predecible que funcione según lo previsto, cuando no tenemos garantía de cuándo y dónde se evaluará una expresión?

Muchas de las respuestas van a cosas como listas infinitas y ganancias de rendimiento de partes no evaluadas de la computación, pero a esta falta la motivación más grande para la pereza: la modularidad .

El argumento clásico se presenta en el muy citado artículo "Por qué importa la programación funcional" (enlace PDF) de John Hughes. El ejemplo clave en ese artículo (Sección 5) es jugar Tic-Tac-Toe usando el algoritmo de búsqueda alfa-beta. El punto clave es (p. 9):

[Evaluación diferida] hace que sea práctico modularizar un programa como un generador que construye una gran cantidad de respuestas posibles, y un selector que elige la apropiada.

El programa Tic-Tac-Toe se puede escribir como una función que genera todo el árbol del juego comenzando en una posición determinada, y una función separada que lo consume. En el tiempo de ejecución, esto no genera intrínsecamente todo el árbol del juego, solo aquellas subpartes que el consumidor realmente necesita. Podemos cambiar el orden y la combinación en la que se producen alternativas cambiando el consumidor; no es necesario cambiar el generador en absoluto.

En un idioma entusiasta, no puede escribirlo de esta manera porque probablemente pasaría demasiado tiempo y memoria generando el árbol. Entonces terminas:

1. Combinando la generación y el consumo en la misma función;
2. Escribir un productor que funcione de manera óptima solo para ciertos consumidores;
3. Implementando su propia versión de la pereza.

¿Cómo se puede usar este paradigma para construir un software predecible que funcione según lo previsto, cuando no tenemos garantía de cuándo y dónde se evaluará una expresión?

Cuando una expresión está libre de efectos secundarios, el orden en que se evalúan las expresiones no afecta su valor, por lo que el comportamiento del programa no se ve afectado por el orden. Entonces el comportamiento es perfectamente predecible.

Ahora los efectos secundarios son un asunto diferente. Si los efectos secundarios pudieran ocurrir en cualquier orden, el comportamiento del programa sería de hecho impredecible. Pero este no es realmente el caso. Los lenguajes perezosos como Haskell hacen que sea un punto de referencia transparente, es decir, asegurarse de que el orden en que se evalúan las expresiones nunca afectará su resultado. En Haskell, esto se logra al forzar que todas las operaciones con efectos secundarios visibles para el usuario ocurran dentro de la mónada IO. Esto asegura que todos los efectos secundarios ocurran exactamente en el orden esperado.

Si está familiarizado con las bases de datos, una forma muy frecuente de procesar datos es:

• Haz una pregunta como select * from foobar
• Si bien hay más datos, haz: obtener la siguiente fila de resultados y procesarla

Usted no controla cómo se genera el resultado y de qué manera (¿índices? ¿Escaneos completos de la tabla?), O cuándo (¿deben generarse todos los datos de una vez o de forma incremental cuando se solicitan?). Todo lo que sabe es: si hay más datos, los obtendrá cuando los solicite.

La evaluación perezosa es bastante parecida a la misma. Digamos que tiene una lista infinita definida como ie. la secuencia de Fibonacci: si necesita cinco números, obtendrá cinco números calculados; si necesitas 1000 obtienes 1000. El truco es que el tiempo de ejecución sabe qué proporcionar dónde y cuándo. Es muy, muy útil.

(Los programadores de Java pueden emular este comportamiento con iteradores; otros lenguajes pueden tener algo similar)

Considere pedirle a su base de datos una lista de los primeros 2000 usuarios cuyos nombres comienzan con "Ab" y son mayores de 20 años. También deben ser hombres.

Aquí hay un pequeño diagrama.

You                                            Program Processor
------------------------------------------------------------------------------
Get the first 2000 users ---------->---------- OK!
                         --------------------- So I'll go get those records...
WAIT! Also, they have to ---------->---------- Gotcha!
start with "Ab"
                         --------------------- NOW I'll get them...
WAIT! Make sure they're  ---------->---------- Good idea Boss!
over 20!
                         --------------------- Let's go then...
And one more thing! Make ---------->---------- Anything else? Ugh!
sure they're male!

No that is all. :(       ---------->---------- FINE! Getting records!

                         --------------------- Here you go. 
Thanks Postgres, you're  ---------->----------  ...
my only friend.

Como puede ver en esta interacción terrible, la "base de datos" no está haciendo nada hasta que esté lista para manejar todas las condiciones. Son resultados de carga lenta en cada paso y la aplicación de nuevas condiciones cada vez.

En lugar de obtener los primeros 2000 usuarios, devolverlos, filtrarlos por "Ab", devolverlos, filtrarlos por más de 20, devolverlos y filtrar por hombres y finalmente devolverlos.

Carga perezosa en pocas palabras.

La evaluación perezosa de las expresiones hará que el diseñador de una determinada pieza de código pierda el control sobre la secuencia en que se ejecuta su código.

El diseñador no debería preocuparse por el orden en que se evalúan las expresiones siempre que el resultado sea el mismo. Al aplazar la evaluación, puede ser posible evitar evaluar algunas expresiones por completo, lo que ahorra tiempo.

Puede ver la misma idea en el trabajo en un nivel inferior: muchos microprocesadores pueden ejecutar instrucciones sin orden, lo que les permite usar sus diversas unidades de ejecución de manera más eficiente. La clave es que analizan las dependencias entre las instrucciones y evitan reordenar dónde cambiaría el resultado.

Hay varios argumentos para una evaluación perezosa que creo que son convincentes.

1. Modularidad Con la evaluación diferida puede dividir el código en partes. Por ejemplo, suponga que tiene el problema de "encontrar los primeros diez recíprocos de elementos en una lista de listas de modo que los recíprocos sean menores que 1." En algo como Haskell puedes escribir

   take 10 . filter (<1) . map (1/)
   

   pero esto es incorrecto en un lenguaje estricto, ya que si lo das, [2,3,4,5,6,7,8,9,10,11,12,0]dividirás por cero. Vea la respuesta de sacundim de por qué esto es increíble en la práctica

2. Más cosas funcionan Estrictamente (nunca mejor dicho) más programas terminan con la evaluación no estrictas que con la evaluación estricta. Si su programa termina con una estrategia de evaluación "entusiasta", terminará con una estrategia "perezosa", pero lo contrario no es cierto. Obtiene cosas como estructuras de datos infinitas (que en realidad son solo un poco geniales) como ejemplos específicos de este fenómeno. Más programas funcionan en lenguajes perezosos.

3. Optimidad La evaluación llamada por necesidad es asintóticamente óptima con respecto al tiempo. Aunque los principales lenguajes perezosos (que esencialmente son Haskell y Haskell) no prometen llamadas por necesidad, puede esperar más o menos un modelo de costo óptimo. Los analizadores de rigurosidad (y la evaluación especulativa) mantienen bajos los gastos generales en la práctica. El espacio es un asunto más complicado.

4. La pureza de las fuerzas mediante una evaluación perezosa hace que lidiar con los efectos secundarios de manera indisciplinada sea un dolor total, porque como lo expresas, el programador pierde el control. Ésto es una cosa buena. La transparencia referencial hace que la programación, la refracción y el razonamiento sobre los programas sean mucho más fáciles. Los idiomas estrictos inevitablemente ceden a la presión de tener partes impuras, algo que Haskell y Clean han resistido maravillosamente. Esto no quiere decir que los efectos secundarios sean siempre malos, pero controlarlos es tan útil que esta razón por sí sola es suficiente para usar lenguajes perezosos.

Suponga que tiene muchos cálculos caros en oferta, pero no sabe cuáles serán realmente necesarios o en qué orden. Puede agregar un complicado protocolo mother-may-i para obligar al consumidor a descubrir qué está disponible y activar los cálculos que aún no se han realizado. O simplemente podría proporcionar una interfaz que actúe como si todos los cálculos estuvieran hechos.

Además, suponga que tiene un resultado infinito. El conjunto de todos los primos, por ejemplo. Es obvio que no puede calcular el conjunto de antemano, por lo que cualquier operación en el dominio de los números primos debe ser lenta.

con la evaluación perezosa no pierde el control sobre la ejecución del código, sigue siendo absolutamente determinista. Sin embargo, es difícil acostumbrarse a él.

La evaluación diferida es útil porque es una forma de reducción del término lambda que terminará en algunos casos, donde la evaluación ansiosa fallará, pero no al revés. Esto incluye 1) cuando necesita vincular al resultado de cálculo antes de ejecutar realmente el cálculo, por ejemplo, cuando construye una estructura gráfica gráfica, pero desea hacerlo en el estilo funcional 2) cuando define una estructura de datos infinita, pero funciona esta alimentación de estructura usar solo parte de la estructura de datos.