Evaluación perezosa

En la teoría del lenguaje de programación, evaluación perezosa, o llamada por necesidad, es una estrategia de evaluación que retrasa la evaluación de una expresión hasta que se necesita su valor (no -evaluación estricta) y que además evita las evaluaciones repetidas (compartir).

Los beneficios de la evaluación perezosa incluyen:

• La capacidad de definir el flujo de control (estructuras) como abstracciones en lugar de primitivos.
• La capacidad de definir estructuras de datos potencialmente infinitas. Esto permite una implementación más sencilla de algunos algoritmos.
• La capacidad de definir estructuras de datos parcialmente definidas donde algunos elementos son errores. Esto permite un prototipado rápido.

La evaluación perezosa a menudo se combina con la memorización, como se describe en Writing Efficient Programs de Jon Bentley. Después de calcular el valor de una función para ese parámetro o conjunto de parámetros, el resultado se almacena en una tabla de búsqueda indexada por los valores de esos parámetros; la próxima vez que se llame a la función, se consultará la tabla para determinar si el resultado de esa combinación de valores de parámetros ya está disponible. Si es así, simplemente se devuelve el resultado almacenado. De lo contrario, se evalúa la función y se agrega otra entrada a la tabla de búsqueda para su reutilización.

La evaluación diferida es difícil de combinar con funciones imperativas como el manejo de excepciones y la entrada/salida, porque el orden de las operaciones se vuelve indeterminado.

Lo opuesto a la evaluación perezosa es la evaluación ansiosa, a veces conocida como evaluación estricta. La evaluación entusiasta es la estrategia de evaluación empleada en la mayoría de los lenguajes de programación.

Historia

Christopher Wadsworth introdujo la evaluación diferida para el cálculo lambda y Plessey System 250 la empleó como una parte fundamental de una metamáquina de cálculo lambda, lo que reduce la sobrecarga de resolución para acceder a objetos en un espacio de direcciones de capacidad limitada. Para los lenguajes de programación, fue introducido de forma independiente por Peter Henderson y James H. Morris y por Daniel P. Friedman y David S. Wise.

Aplicaciones

La evaluación retrasada se usa particularmente en lenguajes de programación funcionales. Cuando se usa la evaluación retrasada, una expresión no se evalúa tan pronto como se vincula a una variable, sino cuando el evaluador se ve obligado a producir el valor de la expresión. Es decir, una declaración como x = expresión; (es decir, la asignación del resultado de una expresión a una variable) claramente requiere que se evalúe la expresión y que el resultado se coloque en x, pero lo que realmente está en x es irrelevante hasta que se necesite su valor a través de una referencia a x en alguna expresión posterior cuya evaluación podría aplazarse, aunque finalmente el árbol de dependencias, que crece rápidamente, sería podado para producir algún símbolo en lugar de otro para que el mundo exterior lo viera.

Estructuras de control

La evaluación diferida permite que las estructuras de control se definan normalmente, y no como técnicas primitivas o de tiempo de compilación. Por ejemplo, se pueden definir operadores de evaluación if-then-else y de cortocircuito:

Si Cierto. b c = bSi Falso b c = c- oCierto. Silencio b = Cierto.Falso Silencio b = b- yCierto. " b = bFalso " b = Falso

Tienen la semántica habitual, es decir, ifThenElse a b c evalúa (a), entonces si y solo si (a) se evalúa como verdadero, evalúa (b), de lo contrario, evalúa (c). Es decir, se evaluará exactamente uno de (b) o (c). Del mismo modo para EasilyComputed || Mucho Trabajo, si la parte fácil da Verdadero, se podría evitar la expresión de mucho trabajo. Finalmente, al evaluar SafeToTry && Expresión, si SafeToTry es false no se intentará evaluar el Expresión.

Por el contrario, en un lenguaje entusiasta, la definición anterior para ifThenElse a b c evaluaría (a), (b) y (c) independientemente del valor de (a). Este no es el comportamiento deseado, ya que (b) o (c) pueden tener efectos secundarios, tomar mucho tiempo para calcular o arrojar errores. Por lo general, es posible introducir estructuras de control diferidas definidas por el usuario en lenguajes entusiastas como funciones, aunque pueden apartarse de la sintaxis del lenguaje para una evaluación entusiasta: a menudo, los cuerpos de código involucrados deben estar envueltos en un valor de función, de modo que se ejecutan sólo cuando se les llama.

Trabajar con infinitas estructuras de datos

La evaluación retrasada tiene la ventaja de poder crear listas infinitas calculables sin bucles infinitos o cuestiones de tamaño que interfieren en el cálculo. Los valores reales solo se calculan cuando es necesario. Por ejemplo, se podría crear una función que crea una lista infinita (a menudo llamada flujo) de números de Fibonacci. El cálculo del n-ésimo número de Fibonacci sería simplemente la extracción de ese elemento de la lista infinita, forzando la evaluación de solo los primeros n miembros de la lista.

Tome como ejemplo este programa trivial en Haskell:

Número Desde InfinitoList :: Int - IntNúmero Desde InfinitoList n = infinity ! n - 1 Donde infinity = [1..]principal = impresión $ Número Desde InfinitoList 4

En la función numberFromInfiniteList, el valor de infinity es un rango infinito, pero hasta que un valor real (o más específicamente, un valor específico en un índice determinado), la lista no se evalúa e incluso entonces solo se evalúa según sea necesario (es decir, hasta el índice deseado). Siempre que el programador tenga cuidado, el programa se completa normalmente. Sin embargo, ciertos cálculos pueden hacer que el programa intente evaluar un número infinito de elementos; por ejemplo, solicitar la longitud de la lista o intentar sumar los elementos de la lista con una operación de plegado daría como resultado que el programa no pudiera terminar o se quedara sin memoria.

Como otro ejemplo, la lista de todos los números de Fibonacci se puede escribir en el lenguaje de programación Haskell como:

 fibs = 0 : 1 : Con cremallera ()+) fibs ()cola fibs)

En la sintaxis de Haskell, ":" antepone un elemento a una lista, tail devuelve una lista sin su primer elemento, y zipWith usa una función específica (en este caso, la adición) para combinar los elementos correspondientes de dos listas para producir un tercero.

Patrón de lista de éxitos

Otros usos

En los sistemas de ventanas de computadora, la representación de información en la pantalla está impulsada por eventos de exposición que impulsan el código de visualización en el último momento posible. Al hacer esto, los sistemas de ventanas evitan computar actualizaciones innecesarias del contenido de la pantalla.

Otro ejemplo de pereza en los sistemas informáticos modernos es la asignación de página de copia en escritura o paginación bajo demanda, donde la memoria se asigna solo cuando se cambia un valor almacenado en esa memoria.

La pereza puede ser útil para escenarios de alto rendimiento. Un ejemplo es la función mmap de Unix, que proporciona una carga de páginas desde el disco impulsada por la demanda, de modo que solo las páginas realmente tocadas se carguen en la memoria y no se asigne la memoria innecesaria.

MATLAB implementa copiar al editar, donde las matrices que se copian tienen su almacenamiento de memoria real replicado solo cuando se cambia su contenido, lo que posiblemente genere un error de memoria insuficiente cuando actualizando un elemento después en lugar de durante la operación de copia.

Rendimiento

La cantidad de reducciones beta para reducir un término lambda con llamada por necesidad no es mayor que la cantidad necesaria para la reducción de llamada por valor o llamada por nombre. Y con ciertos programas, la cantidad de pasos puede ser mucho menor, por ejemplo, una familia específica de términos lambda que usan números de la Iglesia toman una cantidad infinita de pasos con llamada por valor (es decir, nunca completa), una cantidad exponencial de pasos con llamada- por nombre, pero solo un número polinomial con llamada por necesidad. La llamada por necesidad incorpora dos optimizaciones: nunca repetir el trabajo (similar a la llamada por valor) y nunca realizar un trabajo innecesario (similar a la llamada por nombre). La evaluación perezosa también puede conducir a la reducción de la huella de memoria, ya que los valores se crean cuando es necesario.

En la práctica, la evaluación perezosa puede causar problemas de rendimiento significativos en comparación con la evaluación entusiasta. Por ejemplo, en las arquitecturas informáticas modernas, retrasar un cálculo y realizarlo más tarde es más lento que hacerlo inmediatamente. Esto se puede paliar mediante un análisis de rigor. La evaluación perezosa también puede introducir fugas de memoria debido a expresiones no evaluadas.

Implementación

Algunos lenguajes de programación retrasan la evaluación de expresiones de forma predeterminada y otros proporcionan funciones o sintaxis especial para retrasar la evaluación. En Miranda y Haskell, la evaluación de los argumentos de función se retrasa de forma predeterminada. En muchos otros lenguajes, la evaluación se puede retrasar suspendiendo explícitamente el cómputo usando una sintaxis especial (como con "delay" de Scheme y "force " y OCaml's "lazy" y "Lazy.force") o, más generalmente, envolviendo la expresión en un thunk. El objeto que representa una evaluación tan explícitamente retrasada se denomina futuro perezoso. Raku usa la evaluación perezosa de listas, por lo que se pueden asignar listas infinitas a variables y usarlas como argumentos para funciones, pero a diferencia de Haskell y Miranda, Raku no utiliza la evaluación perezosa de funciones y operadores aritméticos de forma predeterminada.

Pereza y afán

Controlando el entusiasmo en lenguajes perezosos

En lenguajes de programación perezosos como Haskell, aunque el valor predeterminado es evaluar las expresiones solo cuando se solicitan, en algunos casos es posible hacer que el código sea más entusiasta o, por el contrario, volver a hacerlo más perezoso una vez que se ha creado. más ansioso Esto se puede hacer codificando explícitamente algo que fuerce la evaluación (lo que puede hacer que el código sea más entusiasta) o evitando dicho código (lo que puede hacer que el código sea más perezoso). La evaluación estricta suele implicar entusiasmo, pero técnicamente son conceptos diferentes.

Sin embargo, hay una optimización implementada en algunos compiladores llamada análisis estricto que, en algunos casos, permite al compilador inferir que siempre se usará un valor. En tales casos, esto puede hacer que la elección del programador de forzar o no ese valor en particular sea irrelevante, porque el análisis estricto forzará una evaluación estricta.

En Haskell, marcar los campos del constructor como estrictos significa que sus valores siempre se exigirán de inmediato. La función seq también se puede usar para exigir un valor de inmediato y luego pasarlo, lo cual es útil si un campo constructor generalmente debe ser perezoso. Sin embargo, ninguna de estas técnicas implementa el rigor recursivo; para eso, se inventó una función llamada deepSeq.

Además, la coincidencia de patrones en Haskell 98 es estricta de forma predeterminada, por lo que se debe usar el calificador ~ para que sea perezoso.

Simulación de la pereza en lenguajes ávidos

Java

En Java, la evaluación diferida se puede realizar mediante el uso de objetos que tienen un método para evaluarlos cuando se necesita el valor. El cuerpo de este método debe contener el código necesario para realizar esta evaluación. Desde la introducción de expresiones lambda en Java SE8, Java admite una notación compacta para esto. La siguiente interfaz genérica de ejemplo proporciona un marco para la evaluación diferida:

interfaz Lazy.T■ {} T eval();}

La interfaz Lazy con su método eval() es equivalente a la interfaz Supplier con su get() método en la biblioteca java.util.function.

Cada clase que implementa la interfaz Lazy debe proporcionar un método eval, y las instancias de la clase pueden tener cualquier valor que el método necesite para realizar una evaluación diferida. Por ejemplo, considere el siguiente código para calcular e imprimir de forma perezosa 2¹⁰:

Lazy.Integer■ a = ()- 1;para ()int i = 1; i . 10; i++) {} final Lazy.Integer■ b = a; a = ()- b.eval() + b.eval();}Sistema.Fuera..println() "a = " + a.eval() );

En lo anterior, la variable a inicialmente se refiere a un objeto entero perezoso creado por la expresión lambda ()->1. Evaluar esta expresión lambda es similar a construir una nueva instancia de una clase anónima que implementa Lazy<Integer> con un método eval que devuelve 1.

Cada iteración del bucle vincula a a un nuevo objeto creado mediante la evaluación de la expresión lambda dentro del bucle. Cada uno de estos objetos contiene una referencia a otro objeto perezoso, b, y tiene un método eval que llama a b. eval() dos veces y devuelve la suma. La variable b es necesaria aquí para cumplir con el requisito de Java de que las variables a las que se hace referencia dentro de una expresión lambda sean definitivas.

Este es un programa ineficiente porque esta implementación de enteros perezosos no memoriza el resultado de llamadas anteriores a eval. También implica un considerable autoboxing y unboxing. Lo que puede no ser obvio es que, al final del bucle, el programa ha construido una lista enlazada de 11 objetos y que todas las adiciones reales involucradas en el cálculo del resultado se realizan en respuesta a la llamada a a. eval() en la última línea de código. Esta llamada atraviesa recursivamente la lista para realizar las adiciones necesarias.

Podemos construir una clase Java que memorice un objeto perezoso de la siguiente manera:

clase Memo.T■ implementos Lazy.T■ {} privado Lazy.T■ perezoso; / // una expresión perezosa, eval lo pone a null privado T memo = nulo; // el memorando del valor anterior público Memo() Lazy.T■ perezoso ) {} // constructor esto.perezoso = perezoso; } público T eval() {} si ()perezoso ! nulo) {} memo = perezoso.eval(); perezoso = nulo; } retorno memo; }}

Esto permite reescribir el ejemplo anterior para que sea mucho más eficiente. Donde el original se ejecutó en un tiempo exponencial en el número de iteraciones, la versión memorizada se ejecuta en un tiempo lineal:

Lazy.Integer■ a = ()- 1;para ()int i = 1; i . 10; i++) {} final Lazy.Integer■ b = a; a = nuevo Memo.Integer■() ()- b.eval() + b.eval() );}Sistema.Fuera..println() "a = " + a.eval() );

Tenga en cuenta que las expresiones lambda de Java son solo azúcar sintáctica. Cualquier cosa que pueda escribir con una expresión lambda se puede reescribir como una llamada para construir una instancia de una clase interna anónima que implemente la interfaz, y cualquier uso de una clase interna anónima se puede reescribir usando una clase interna con nombre, y cualquier clase interna con nombre puede moverse al nivel de anidamiento más externo.

JavaScript

En JavaScript, la evaluación diferida se puede simular usando un generador. Por ejemplo, el flujo de todos los números de Fibonacci se puede escribir, utilizando la memorización, como:

* * Las funciones del generador devuelven objetos del generador, que reanifican la evaluación perezosa. * @return {!Generatorיbigint confianza} Un generador no cero de enteros. */función* fibonacciNumbers() {} Deja memo = [1n, -1n]; // crear el estado inicial (por ejemplo, un vector de números "negafibonacci") mientras ()verdadero) {} // repetir indefinidamente memo = [memo[0] + memo[1] memo[0]] // Actualizar el estado en cada evaluación rendimiento memo[0]; // ceder el valor siguiente y suspender la ejecución hasta la reanudación }}Deja streaming = fibonacciNumbers(); // crear un flujo de números evaluado perezosoDeja primero10 = Array.desde()nuevo Array()10), () = streaming.siguiente().valor); // evaluar sólo los primeros 10 númerosconsola.log()primero10); // la salida es [0n, 1n, 1n, 2n, 3n, 5n, 8n, 13n, 21n, 34n]

Pitón

En Python 2.x, la función range() calcula una lista de números enteros. La lista completa se almacena en la memoria cuando se evalúa la primera declaración de asignación, por lo que este es un ejemplo de evaluación ansiosa o inmediata:

, titulado r = rango()10), titulado impresión r[0, 1, 2, 3, 4, 5, 6, 7, 8, 9], titulado impresión r[3]3

En Python 3.x, la función range() devuelve un generador que calcula los elementos de la lista a pedido. Los elementos solo se generan cuando se necesitan (por ejemplo, cuando se evalúa print(r[3]) en el siguiente ejemplo), por lo que este es un ejemplo de evaluación diferida o diferida:

, titulado r = rango()10), titulado impresión()r)rango(0, 10), titulado impresión()r[3])3

Este cambio a la evaluación perezosa ahorra tiempo de ejecución para grandes rangos que pueden nunca ser completamente referenciados y el uso de memoria para grandes rangos donde sólo uno o algunos elementos son necesarios en cualquier momento.

En Python 2.x es posible usar una función llamada xrange() que devuelve un objeto que genera los números en el rango bajo demanda. La ventaja de xrange es que el objeto generado siempre ocupará la misma cantidad de memoria.

, titulado r = xrange()10), titulado impresión()r)xrange(10), titulado lst = [x para x dentro r], titulado impresión()lst)[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

Desde la versión 2.2 en adelante, Python manifiesta una evaluación perezosa mediante la implementación de iteradores (secuencias perezosas) a diferencia de las secuencias de tupla o lista. Por ejemplo (Python 2):

, titulado números = rango()10), titulado iterator = iter()números), titulado impresión números[0, 1, 2, 3, 4, 5, 6, 7, 8, 9], titulado impresión iteratorobjeto identificador en 0xf7e8dd4c, titulado impresión iterator.siguiente()0

El ejemplo anterior muestra que las listas se evalúan cuando se llama, pero en caso de iterador, el primer elemento '0' se imprime cuando surge la necesidad.

Marco.NET

En.NET Framework, es posible realizar una evaluación diferida utilizando la clase Sistema.Lazy<T>. La clase se puede explotar fácilmente en F# usando el lazy palabra clave , mientras que la clase force forzará la evaluación. También hay colecciones especializadas como Microsoft.FSharp.Colecciones.Seq que proporcionan compatibilidad integrada para la evaluación diferida.

Deja fibonacci = Seq.desplegable ()diversión ()x, Sí.) - Algunos()x, ()Sí., x + Sí.)) ()0I,1I)fibonacci ← Seq.No 1000

En C# y VB.NET, la clase System.Perezoso< T> se usa directamente.

público int Sum(){} int a = 0; int b = 0;  Lazy.int■ x = nuevo Lazy.int(() = a + b); a = 3; b = 5; retorno x.Valor; // devoluciones 8}

O con un ejemplo más práctico:

// Cálculo recurrente del n'th fibonacci númeropúblico int Fib()int n){} retorno ()n == 1)? 1 : ()n == 2)? 1 : Fib()n-1) + Fib()n-2);}público vacío Main(){} Consola.WriteLine()"¿Qué número de Fibonacci quieres calcular?"); int n = Int32.Parse()Consola.ReadLine());  Lazy.int■ fib = nuevo Lazy.int(() = Fib()n)); // función se prepara, pero no se ejecuta bool ejecutar;  si ()n ■ 100) {} Consola.WriteLine()"Esto puede tomar algún tiempo. ¿De verdad quieres calcular este gran número? [y/n]); ejecutar = ()Consola.ReadLine() == "y");  } más ejecutar = verdadero;  si ()ejecutar) Consola.WriteLine()fib.Valor); // número sólo se calcula si es necesario}

Otra forma es usar el rendimiento:

// evaluación ansiosa público IEnumerable.int■ Fibonacci()int x){} IList.int■ fibs = nuevo Lista.int. int prev = -1; int siguiente = 1; para ()int i = 0; i . x; i++) {} int suma = prev + siguiente; prev = siguiente; siguiente = suma; fibs.Añadir()suma);  } retorno fibs;}// Evaluación perezosa público IEnumerable.int■ LazyFibonacci()int x){} int prev = -1; int siguiente = 1; para ()int i = 0; i . x; i++) {} int suma = prev + siguiente; prev = siguiente; siguiente = suma; rendimiento retorno suma; }}