Evaluación perezosa

8. Evaluacion tardiaLa evaluacion tardia (o perezosa) es un tecnica que se vuelve posible una vez que adoptamos una filosofia funcional.

Haskell es un ejemplo de lenguaje de evaluacion tardia. En Haskell no hay garantia de que el codigo sea ejecutado en ´orden (o que siquiera sea ejecutado), pues Haskell solo ejecuta el codigo cuando es requerido.La evaluacion tardia tiene numerosas ventajas as´ı como desventajas. Discutiremos las ventajasaqui, y veremos como lidiar con las desventajas en la siguiente seccion.

8.1. Optimizaci´onLa evaluaci´on tard´ıa ofrece un tremendo potencial para optimizaciones. Un compilador de estetipo ve al c´odigo funcional exactamente como un matem´atico ve una expresi´on algebraica. Puedecancelar cosas y prevenir completamente su ejecuci´on, reacomodar las piezas para mayor eficiencia,incluso reacomodar el c´odigo de una forma que reduzca los errores, todo esto garantizando que lal´ogica permanecer´a intacta. Este es el mayor beneficio de representar programas usando estrictamenteprimitivas formales: c´omo el c´odigo se adhiere a leyes matem´aticas, se puede pensar en ´elmatem´aticamente.

8.2. Abstracci´on de estructuras de controlLa evaluaci´on tard´ıa provee un nivel superior de abstracci´on que permite implementar cosasque de otra forma ser´ıan imposibles. Por ejemplo, considere implentar la estructura de control delListado 14:Listado 14: Estructura de control personalizadaaMenosQue ( stock . esEuropeo ()) {enviarASEC ( stock );}Deseamos ejecutar eviarASEC a menos que el stock sea europeo. ¿C´omo podr´ıamos implementaraMenosQue? Sin evaluaci´on tard´ıa, necesitariamos alguna tipo de macro, pero en un lenguaje comoHaskell no. ¡Podemos implementar aMenosQue como una funci´on! (Ve el Listado 15)Listado 15: Implementaci´on de la estructura de control con evaluaci´on tard´ıavoid aMenosQue (boolean condicion , List codigo ) {i f (! condicion )codigo ;}Nota que codigo nunca es evaluado si la condici´on es verdadera. No podemos hacer los mismoen un lenguaje de evaluaci´on estricta porque los argumentos ser´ıan evaluados antes de entrar enaMenosQue.

8.3. Estructuras de datos infinitasLos lenguajes de evaluaci´on tard´ıa permiten la definici´on de estructuras de datos infinitas, algo

que es mucho m´as complicado en un lenguaje de evaluaci´on estricta. Por ejemplo, considera unalista con los n´umeros de Fibonacci. Est´a claro que no podemos realizar c´alculos sobre una listainfinita en un tiempo razonable, o guardarla en memoria. En lenguajes de evaluaci´on estricta comoJava, simplemente definimos una function fibonacci que devuelva un miembro particular de la secuencia.En un lenguaje como Haskell podemos abstraerlo aun m´as y simplemente definir una listainfinita con los n´umeros de Fibonacci. Como el lenguaje es de evaluaci´on tard´ıa, solo las partes necesariasde la lista que son usadas realmente por el programa ser´an evaluadas. Esto permite abstraermuchos problemas y verlos desde una persepectiva de m´as alto nivel (por ejemplo, podemos usarprocesamiento de listas sobre una lista infinita).

8.3. Estructuras de datos infinitasLos lenguajes de evaluaci´on tard´ıa permiten la definici´on de estructuras de datos infinitas, algoque es mucho m´as complicado en un lenguaje de evaluaci´on estricta. Por ejemplo, considera unalista con los n´umeros de Fibonacci. Est´a claro que no podemos realizar c´alculos sobre una listainfinita en un tiempo razonable, o guardarla en memoria. En lenguajes de evaluaci´on estricta comoJava, simplemente definimos una function fibonacci que devuelva un miembro particular de la secuencia.En un lenguaje como Haskell podemos abstraerlo aun m´as y simplemente definir una listainfinita con los n´umeros de Fibonacci. Como el lenguaje es de evaluaci´on tard´ıa, solo las partes necesariasde la lista que son usadas realmente por el programa ser´an evaluadas. Esto permite abstraermuchos problemas y verlos desde una persepectiva de m´as alto nivel (por ejemplo, podemos usarprocesamiento de listas sobre una lista infinita).

Afortunadamente, no todo est´a perdido. Los matem´aticos han trabajado y desarrollado algunostrucos para asegurarse de que porciones del c´odigo sean ejecutadas en un ´orden particular en unambiente funcional. ¡Tenemos lo mejor de los dos mundos! Estas t´ecnicas incluyen continuaciones,monads, y escritura singular. En este art´ıculo solo veremos las continuaciones. Dejaremos las otrasdos para otra ocasi´on. Es interesante que las continuaciones son ´utiles para m´as cosas que permitirun ´orden particular de evaluaci´on. Hablaremos de esto tambi´en.

Evaluación PerezosaHoy quisiera hablar de una de las características de Haskell más fascinantes, la evaluación perezosa. Y me han entrado ganas de hablar de ello al ver la utilización que se da a la evaluación perezosa en el problema repMin de Richard Bird. El problema viene a ser el siguiente: reemplazar los valores en los nodos de

un árbol por el mínimo valor de este mismo árbol, y solo recorriendo el árbol una sola vez.

Yo voy a explicarlo con una estructura más sencilla, sustituir todos los valores de una lista de números por el mínimo valor de esta lista, recorriendo la lista una sola vez. Y esto usando de manera muy inteligente la evaluación perezosa. Vamos a empezar contando que es la evaluación perezosa (lazy).

Evaluación Perezosa

En los lenguajes de programación tradicionales, lo que tenemos esevaluación ansiosa (eager). Con este tipo de evaluación, cuando asignamos un valor a una variable, o pasamos un parámetro a una función, se calcula cual es el valor final a asignar o cual es el valor final del parámetro. Por ejemplo:

v = sqrt(2) + 3 * sqrt(5);

f( 4 / g( 7 ) );

Antes de asignar nada a v, se llamara a las funciones sqrt con sus parámetros correspondientes, luego se aplicara la expresión matemática para obtener el valor final a asignar a v. En el caso de la llamada a la función f, antes se ha de llamar a la función g y dividir entre 4 el resultado de esta llamada. Por eso se denomina evaluación perezosa, porque se ha de obtener el valor de las expresiones en cuanto el programa se las encuentra.

La evaluación perezosa solo calcula el valor de las expresiones cuando necesita hacer uso de este valor. En el código de ejemplo anterior, en v se guardaría como se calcula su valor y no el valor final. Y el parámetro pasado a f sería la formula completa y no el valor de aplicar la expresión. Si resulta que ni la variable v ni el parámetro de la función f se usan, pues nunca se llamaría a las funciones sqrt y g, ni se realizarían las operaciones matemáticas pertinentes.

Esto puede suponer una diferencia enorme entre ejecutar con evaluación perezosa y evaluación ansiosa. Si tenemos definidas f y g como:

int f( int a ){ return 4;}int g( int a ){ return a - 7;}

Con evaluación ansiosa obtendríamos un error "division by zero" mientras que con evaluación perezosa la ejecución terminaría sin error.

ReplaceMin

La primera versión que podemos pensar de replaceMin es la que pongo a continuación:

replaceMin xs = replace xs (minimum xs) where replace xs m = map (\a -> m) xs

Primero se calcula el mínimo de la lista de números xs y luego se sustituye todos los valores de esta lista por el valor mínimo (usando la función replace). Esta primera versión recorre la lista dos veces, una vez para calcular el mínimo y una segunda vez para reemplazar los valores.

Y ahora viene lo verdaderamente impresionante. La versión de replaceMin que recorre la lista una sola vez:

replaceMin xs = ys where (ys, m) = rpMin xs m

¿Y como funciona? Gracias a la evaluación perezosa. Entendiendo lo que hace la función rpMin, lograremos entender como funciona. La función rpMin tiene dos parámetros, una lista de números xs y un numero m. Lo que hace rpMin es sustituir todos los valores de xs por m (igual que replace) con el añadido de que a la vez va calculando el mínimo de xs. La función rpMin devuelve una tupla con la nueva lista con los valores sustituidos y con el mínimo de la antigua lista.

La magia ocurre en la manera de llamar a rpMin desde la funciónreplaceMin, como valor a sustituir se le pasa el mínimo que todavía no ha calculado rpMin y del cual no necesita saber su valor. Básicamente la conversación entre las dos funciones seria:

replaceMin: sustituyeme todos los valores de xs por este valor m del que

de momento no se nada

rpMin: ¿Pero como? ¡Necesitare saber el valor de m para ponerlo en la lista!

replaceMin: ¡No hombre, no! Recuerda que nosotros tenemos evaluación

perezosa.

rpMin: Bueno, pues tu sabrás cual es el valor de m, ya se lo dirás al que

quiera usar la lista resultante.

replaceMin: ¡Te vuelves a equivocar! El valor me lo dirás tu, cuando

calcules el mínimo de xs.

El valor de m solo será necesario fuera de la función replaceMin, por ejemplo cuando se imprima la lista resultante por pantalla, y para entonces rpMin ya habrá calculado el mínimo.

Esta sería la definición de rpMin. Simplemente va sustituyendo los valores de la lista por el valor m pasado como parámetro, y mientras va calculando el mínimo comparando cada valor de la lista con el mínimo hasta ese momento. Y todo recorriendo la lista una sola vez.

rpMin [x] m = ([m], x)rpMin (x:xs) m = (m:ys, min x my) where (ys, my) = rpMin xs m

Bueno, os dejo pensando en porqué funciona. O podeis probarlo por vosotros mismos en vuestra distribución de Haskell favorita. También os dejo los enlaces a las versiones de replaceMin para arboles.

QUÉ ES LA EVALUACIÓN PEREZOSA?

Evaluación impaciente (eager): el evaluador hace todo lo que puede.

Corresponde a llamada por-valor.

Evaluación perezosa (lazy):

El evaluador hace solamente lo preciso. Corresponde a llamada por-

necesidad.

Significa: Haz sólo lo que te pida un patrón a la izquierda de una

ecuación o cualificador (where o let).

Es una estrategia de evaluación que retrasa la evaluación de una

expresión hasta que el valor de esto realmente se requiera (evaluación

no estricta) y que también evita evaluaciones repetidas (compartimiento

de ciencias informáticas). El compartimiento puede reducir la duración

de ciertas funciones por un factor exponencial sobre otras estrategias de

evaluación no estrictas, como la llamada de nombre.

Las ventajas de la evaluación perezosa incluyen:

El rendimiento aumenta debido a evitación de cálculos innecesarios y

evitación de condiciones de error en la evaluación de expresiones

compuestas.

La capacidad de construir estructura de datos potencialmente infinita

La capacidad de definir estructura de control como abstracciones en vez

de como obras primitivistas.

La evaluación perezosa puede llevar a la reducción de la huella de

memoria, ya que los valores se crean cuando necesario. Sin embargo,

con la evaluación perezosa, es difícil combinarse con rasgos imperativos

como la excepción que se maneja (manejo de la excepción) y

entrada/salida (entrada/salida), porque el pedido de operaciones se hace

indeterminado. La evaluación perezosa puede introducir el agujero

espacial. También, la depuración es difícil.

3.1.- las estrategia de evaluación perezosa.

ESTRATEGIAS DE PROGRAMACIÓN PEREZOSA

Para los ejemplos se considera la función

mult :: (Int,Int) Int

mult (x,y) = x * y

Evaluación mediante paso de parámetros por valor (o por más internos):

mult (1+2,2+3)

= mult (3,5) [por def. de +]

= 3*5 [por def. de mult]

= 15 [por def. de *]

Evaluación mediante paso de parámetros por nombre (o por más

externos):

mult (1+2,2+3)

= (1+2)*(3+5) [por def. de mult]

= 3*5 [por def. de +]

Evaluación con lambda expresiones

mult’ (1+2) (2+3)

= mult’ 3 (2+3) [por def. de +]

= (λy → 3*y) (2+3) [por def. de mult’]

= (λy → 3*y) 5 [por def. de +]

= 3*5 [por def. de +]

= 15 [por def. de *]

3.2.- técnicas de programación funcional perezosa.