En la teoría del lenguaje de programación , evaluación diferida o llamada por necesidad , [1] es una estrategia de evaluación que retrasa la evaluación de una expresión hasta que se necesita su valor ( evaluación no estricta ) y que también evita evaluaciones repetidas (mediante el uso de compartir ). [2] [3]
Los beneficios de la evaluación diferida incluyen:
La evaluación perezosa a menudo se combina con la memorización , como se describe en Writing Efficient Programs de Jon Bentley . [4] 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 que está indexada por los valores de esos parámetros; la próxima vez que se llama a la función, se consulta 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 características 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 entusiasta , 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 [ cuantificar ] .
Christopher Wadsworth [5] introdujo la evaluación diferida para el cálculo lambda y la empleó Plessey System 250 como parte crítica de una metamáquina de cálculo Lambda, lo que reduce la sobrecarga de resolución para el acceso a objetos en un espacio de direcciones de capacidad limitada . [6] Para los lenguajes de programación, fue introducido de forma independiente por Peter Henderson y James H. Morris [7] y por Daniel P. Friedman y David S. Wise. [8] [9]
La evaluación retrasada se utiliza particularmente en lenguajes de programación funcionales . Cuando se utiliza 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 = expression;(es decir, la asignación del resultado de una expresión a una variable) claramente exige que se evalúe la expresión y se coloque el resultado en x, pero lo que realmente está en xes irrelevante hasta que sea necesario su valor. a través de una referencia a xalguna expresión posterior cuya evaluación podría en sí misma diferirse, aunque eventualmente el árbol de dependencias en rápido crecimiento sería podado para producir algún símbolo en lugar de otro para que lo vea el mundo exterior. [10]
La evaluación diferida permite que las estructuras de control se definan normalmente, y no como primitivas o técnicas en tiempo de compilación. Por ejemplo, se pueden definir operadores de evaluación de cortocircuito y si-entonces : [11] [12]
ifThenElse Verdadero b c = b ifThenElse Falso b c = c -- o Verdadero || b = Verdadero Falso || segundo = segundo -- y Verdadero && b = b Falso && b = Falso Estos tienen la semántica habitual, es decir, evalúa (a), entonces, si y sólo si (a) se evalúa como verdadero, se evalúa (b); en caso contrario, se evalúa (c). Es decir, se evaluará exactamente uno de (b) o (c). De manera similar, para , si la parte fácil da True , se podría evitar la expresión de mucho trabajo. Finalmente, al evaluar , si SafeToTry es falso no habrá ningún intento de evaluar la Expresión .ifThenElse a b cEasilyComputed || LotsOfWorkSafeToTry && Expression
Por el contrario, en un lenguaje entusiasta, la definición anterior de 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 , tardar mucho en calcularse o generar errores. Generalmente es posible introducir estructuras de control diferido definidas por el usuario en lenguajes ansiosos como funciones, aunque pueden apartarse de la sintaxis del lenguaje para una evaluación entusiasta: a menudo, los cuerpos de código involucrados deben incluirse en un valor de función, de modo que solo se ejecuten. cuando lo llaman.ifThenElse a b c
La evaluación retrasada tiene la ventaja de poder crear listas infinitas calculables sin bucles infinitos o cuestiones de tamaño que interfieran en el cálculo. Los valores reales sólo se calculan cuando es necesario. Por ejemplo, se podría crear una función que cree una lista infinita (a menudo llamada secuencia ) 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 solo de los primeros n miembros de la lista. [13] [14]
Tomemos, por ejemplo, este programa trivial en Haskell :
numberFromInfiniteList :: Int -> Int numberFromInfiniteList n = infinito !! n - 1 donde infinito = [ 1 .. ] principal = imprimir $ numeroDeListaInfinita 4 En la función numberFromInfiniteList , el valor de infinito es un rango infinito, pero hasta que se necesita 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 como necesario (es decir, hasta el índice deseado). Siempre que el programador tenga cuidado, el programa se completa normalmente. Sin embargo, ciertos cálculos pueden dar como resultado 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 provocaría que el programa no terminara 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: [14]
fibs = 0 : 1 : zipCon ( + ) fibs ( fibs de cola ) En la sintaxis de Haskell, " :" antepone un elemento a una lista, taildevuelve una lista sin su primer elemento y zipWithutiliza una función especificada (en este caso, suma) para combinar los elementos correspondientes de dos listas para producir una tercera. [13]
En los sistemas de ventanas informáticas , la pintura 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. [15]
Otro ejemplo de pereza en los sistemas informáticos modernos es la asignación de páginas de copia en escritura o paginación por demanda , donde la memoria se asigna solo cuando se cambia un valor almacenado en esa memoria. [15]
La pereza puede resultar útil en escenarios de alto rendimiento. Un ejemplo es la función mmap de Unix , que proporciona carga de páginas desde el disco según la demanda , de modo que sólo las páginas realmente tocadas se cargan en la memoria y no se asigna memoria innecesaria.
MATLAB implementa copiar en edición , donde las matrices que se copian tienen su almacenamiento de memoria real replicado solo cuando se cambia su contenido, lo que posiblemente provoque un error de falta de memoria al actualizar un elemento posteriormente en lugar de durante la operación de copia. [dieciséis]
El número de reducciones beta para reducir un término lambda con llamada por necesidad no es mayor que el número necesario mediante la reducción de llamada por valor o llamada por nombre . [17] [18] Y con ciertos programas el número de pasos puede ser mucho menor, por ejemplo, una familia específica de términos lambda que utilizan números de Church toma una cantidad infinita de pasos con llamada por valor (es decir, nunca completa), un exponencial número 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 trabajos innecesarios (similar a la llamada por nombre). [19] La evaluación diferida también puede conducir a una reducción en la huella de memoria , ya que los valores se crean cuando es necesario. [20]
En la práctica, la evaluación perezosa puede causar importantes problemas de rendimiento 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 realizarlo inmediatamente. Esto puede aliviarse mediante un análisis de rigor . [19] La evaluación diferida también puede introducir pérdidas de memoria debido a expresiones no evaluadas. [21] [22]
Algunos lenguajes de programación retrasan la evaluación de expresiones de forma predeterminada y otros proporcionan funciones o sintaxis especiales para retrasar la evaluación. En Miranda y Haskell , la evaluación de los argumentos de la función se retrasa de forma predeterminada. En muchos otros lenguajes, la evaluación se puede retrasar suspendiendo explícitamente el cálculo usando una sintaxis especial (como con " " y " " de Scheme y " " y " " de OCaml ) o, más generalmente, envolviendo la expresión en un procesador . El objeto que representa una evaluación tan explícitamente retrasada se llama futuro perezoso . Raku usa una evaluación diferida 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 usa una evaluación diferida de operadores y funciones aritméticos de forma predeterminada. [10]delayforcelazyLazy.force
En lenguajes de programación diferidos como Haskell, aunque el valor predeterminado es evaluar expresiones sólo cuando se solicitan, en algunos casos es posible hacer que el código sea más ágil o, por el contrario, volverlo más perezoso nuevamente después de que se haya vuelto más entusiasta. 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 vago). 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 de rigor , que, en algunos casos, permite al compilador inferir que siempre se utilizará 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 de rigor forzará una evaluación estricta .
En Haskell, marcar los campos del constructor como estrictos significa que sus valores siempre se solicitarán de inmediato. La seqfunción también se puede utilizar para exigir un valor inmediatamente y luego pasarlo, lo cual es útil si un campo constructor generalmente debe ser diferido. Sin embargo, ninguna de estas técnicas implementa el rigor recursivo ; para eso, deepSeqse inventó una función llamada.
Además, la coincidencia de patrones en Haskell 98 es estricta de forma predeterminada, por lo que ~se debe usar el calificador para hacerlo perezoso. [23]
En Java , la evaluación diferida se puede realizar utilizando objetos que tengan un método para evaluarlos cuando se necesita el valor. El cuerpo de este método debe contener el código requerido para realizar esta evaluación. Desde la introducción de expresiones lambda en Java SE8, Java ha admitido una notación compacta para esto. El siguiente ejemplo de interfaz genérica proporciona un marco para la evaluación diferida: [24] [25]
interfaz Lazy < T > { T eval (); } La Lazyinterfaz con su eval()método es equivalente a la Supplierinterfaz con su get()método en la java.util.functionbiblioteca. [26] [27] : 200
Cada clase que implementa la Lazyinterfaz debe proporcionar un evalmétodo, y las instancias de la clase pueden llevar 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 diferida 2 10 :
Perezoso <Entero> a = ( ) - > 1 ; for ( int i = 0 ; i < 10 ; i ++ ) { Perezoso <Entero> b = a ; a = () -> b . evaluación () + b . evaluación (); } Sistema . afuera . println ( "a = " + a . eval ()); En lo anterior, la variable a inicialmente se refiere a un objeto entero diferido creado por la expresión lambda . Evaluar esta expresión lambda es similar [a] a construir una nueva instancia de una clase anónima que se implementa con un método eval que devuelve 1 .() -> 1Lazy<Integer>
Cada iteración del bucle vincula a a un nuevo objeto creado evaluando la expresión lambda dentro del bucle. Cada uno de estos objetos contiene una referencia a otro objeto diferido, b , y tiene un método eval que llama 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 desde una expresión lambda sean efectivamente finales.b.eval()
Este es un programa ineficiente porque esta implementación de enteros diferidos 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 ciclo, el programa ha construido una lista enlazada de 11 objetos y que todas las sumas reales involucradas en calcular el resultado se realizan en respuesta a la llamada a en la línea final de código. Esta llamada recorre recursivamente la lista para realizar las adiciones necesarias.a.eval()
Podemos construir una clase Java que memorice un objeto diferido de la siguiente manera: [24] [25]
clase Memo <T> implementa Lazy <T> { privado Lazy <T> lazy ; // una expresión diferida, eval la establece en nulo memo privado T ; // el memorándum del valor anterior Memo público ( Lazy <T> lazy ) { this . perezoso = perezoso ; } public T eval () { if ( lazy ! = null ) { memo = lazy . evaluación (); perezoso = nulo ; } devolver nota ; } } Esto permite reescribir el ejemplo anterior para que sea mucho más eficiente. Mientras que el original se ejecutó en tiempo exponencial en el número de iteraciones, la versión memorizada se ejecuta en tiempo lineal :
Perezoso <Entero> a = ( ) - > 1 ; for ( int i = 0 ; i < 10 ; i ++ ) { Perezoso <Entero> b = a ; a = nueva nota <entero> (() - > b . eval () + b . eval ()) ; } Sistema . afuera . println ( "a = " + a . eval ()); Las expresiones lambda de Java son simplemente azúcar sintáctica . Todo lo que se 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, [a] y cualquier uso de una clase interna anónima se puede reescribir usando una clase interna con nombre, y cualquier La clase interna nombrada se puede mover al nivel de anidamiento más externo.
En JavaScript , la evaluación diferida se puede simular mediante el uso de un generador . Por ejemplo, la secuencia de todos los números de Fibonacci se puede escribir, usando memorización , como:
/** * Las funciones generadoras devuelven objetos generadores, que cosifican la evaluación diferida. * @return {!Generator<bigint>} Un generador de números enteros no nulo. */ function * númerosfibonacci () { let memo = [ 1n , - 1n ]; // crea el estado inicial (por ejemplo, un vector de números "negafibonacci") while ( true ) { // repite indefinidamente memo = [ memo [ 0 ] + memo [ 1 ], memo [ 0 ]]; // actualiza el estado de cada nota de rendimiento de evaluación [ 0 ]; // arroja el siguiente valor y suspende la ejecución hasta que se reanude } } let stream = números de fibonacci (); // crea un flujo de números evaluado de forma diferida let first10 = Array . from ( nueva matriz ( 10 ), () => secuencia . siguiente (). valor ); //evaluar sólo los primeros 10 números de la consola . iniciar sesión ( primeros10 ); // la salida es [0n, 1n, 1n, 2n, 3n, 5n, 8n, 13n, 21n, 34n] En Python 2.x, la range()función [28] 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 inmediata o entusiasta:
>>> r = rango ( 10 ) >>> imprimir r [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] >>> imprimir r [ 3 ] 3En Python 3.x, la range()función [29] devuelve un generador que calcula elementos de la lista bajo demanda. Los elementos solo se generan cuando son necesarios (por ejemplo, cuando print(r[3])se evalúan en el siguiente ejemplo), por lo que este es un ejemplo de evaluación diferida o diferida:
>>> r = rango ( 10 ) >>> imprimir ( r ) rango(0, 10) >>> imprimir ( r [ 3 ]) 3En Python 2.x es posible utilizar una función llamada xrange()que devuelve un objeto que genera los números en el rango a pedido. La ventaja de xrangees que el objeto generado siempre ocupará la misma cantidad de memoria.
>>> r = rangox ( 10 ) >>> imprimir ( r ) rangox(10) >>> lista = [ x para x en r ] >>> imprimir ( lista ) [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]Desde la versión 2.2 en adelante, Python manifiesta una evaluación diferida mediante la implementación de iteradores (secuencias diferidas) a diferencia de las secuencias de tuplas o listas. Por ejemplo (Python 2):
>>> números = rango ( 10 ) >>> iterador = iter ( números ) >>> imprimir números [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] >>> imprimir iterador < objeto listiterator en 0xf7e8dd4c> >>> imprimir iterador . siguiente () 0En el marco .NET , es posible realizar una evaluación diferida utilizando la clase . [30] La clase se puede explotar fácilmente en F# usando la palabra clave, mientras que el método forzará la evaluación. También hay colecciones especializadas como la que brindan soporte integrado para la evaluación diferida. System.Lazy<T>lazyforceMicrosoft.FSharp.Collections.Seq
sea fibonacci = Seq . desplegar ( divertido ( x , y ) -> Algunos ( x , ( y , x + y ))) ( 0I , 1I ) fibonacci |> Seq . enésimo 1000 En C# y VB.NET, la clase se utiliza directamente. System.Lazy<T>
public int suma () { int a = 0 ; int b = 0 ; Lazy < int > x = nuevo Lazy < int > (() => a + b ); un = 3 ; segundo = 5 ; devolver x . Valor ; // devuelve 8 } O con un ejemplo más práctico:
// cálculo recursivo del enésimo número de Fibonacci public int Fib ( int n ) { return ( n == 1 ) ? 1 : ( norte == 2 ) ? 1 : Fibra ( n - 1 ) + Fibra ( n - 2 ); } public void Principal () { Consola . WriteLine ( "¿Qué número de Fibonacci quieres calcular?" ); int norte = Int32 . Analizar ( Consola . ReadLine ()); Lazy < int > fib = new Lazy < int > (() => Fib ( n )); // la función está preparada, pero no ejecutada bool ejecutar ; si ( n > 100 ) { Consola . WriteLine ( "Esto puede llevar algún tiempo. ¿Realmente desea calcular este número tan grande? [s/n]" ); ejecutar = ( Consola . ReadLine () == "y" ); } más ejecutar = verdadero ; si ( ejecutar ) Consola . WriteLine ( fib . Valor ); // el número sólo se calcula si es necesario } Otra forma es utilizar la yieldpalabra clave:
// evaluación ansiosa public IEnumerable < int > Fibonacci ( int x ) { IList < int > fibs = nueva Lista < int > (); int anterior = - 1 ; int siguiente = 1 ; for ( int i = 0 ; i < x ; i ++ ) { int suma = anterior + siguiente ; anterior = siguiente ; siguiente = suma ; mentiras . Sumar ( suma ); } devolver mentiras ; } // evaluación diferida public IEnumerable < int > LazyFibonacci ( int x ) { int prev = - 1 ; int siguiente = 1 ; for ( int i = 0 ; i < x ; i ++ ) { int suma = anterior + siguiente ; anterior = siguiente ; siguiente = suma ; suma de retorno de rendimiento ; } }