Evaluación perezosa - Lazy evaluation

Estrategias de evaluación

En la teoría del lenguaje de programación , la 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 ( evaluación no estricta ) y que también evita evaluaciones repetidas ( compartir ). El intercambio puede reducir el tiempo de ejecución de ciertas funciones en un factor exponencial sobre otras estrategias de evaluación no estrictas, como la llamada por nombre , que evalúan repetidamente la misma función, a ciegas, independientemente de si la función se puede memorizar .

Los beneficios de la evaluación perezosa incluyen:

  • La capacidad de definir el flujo de control (estructuras) como abstracciones en lugar de primitivas.
  • La capacidad de definir estructuras de datos potencialmente infinitas . Esto permite una implementación más sencilla de algunos algoritmos.
  • El rendimiento aumenta al evitar cálculos innecesarios y evitar condiciones de error al evaluar expresiones compuestas.

La evaluación perezosa se combina a menudo con memoization , como se describe en Jon Bentley 's programas eficientes de escritura . Después de que se calcula 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ámetro ya está disponible. Si es así, el resultado almacenado simplemente se devuelve. De lo contrario, la función se evalúa y se agrega otra entrada a la tabla de búsqueda para su reutilización.

La evaluación perezosa puede conducir a una reducción en la huella de memoria, ya que los valores se crean cuando es necesario. Sin embargo, la evaluación perezosa 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. La evaluación perezosa puede introducir pérdidas de memoria .

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

Historia

La evaluación diferida fue introducida para el cálculo lambda por Christopher Wadsworth y empleada por Plessey System 250 como una parte crítica de una metamáquina Lambda-Calculus, reduciendo la sobrecarga de resolución para el acceso 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 = 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 x, pero lo que realmente está incluido xes irrelevante hasta que se necesite su valor. a través de una referencia xen alguna expresión posterior cuya evaluación podría aplazarse, aunque eventualmente el árbol de dependencias de rápido crecimiento se podaría para producir algún símbolo en lugar de otro para que el mundo exterior lo viera.

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. Por ejemplo, se podría crear una función que cree 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, lo que obligaría a evaluar solo los primeros n miembros de la lista.

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

 fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

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

Siempre que el programador tenga cuidado, solo se evalúan los valores necesarios para producir un resultado en particular. 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 terminara o se quedara sin memoria .

Estructuras de Control

En casi todos los lenguajes "ansiosos" comunes, las declaraciones if se evalúan de manera perezosa. 

if a then b else 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, no se evaluarán ni (b) ni (c). Por el contrario, en un lenguaje ansioso, el comportamiento esperado es que 

define f(x, y) = 2 * x
set k = f(d, e)

seguirá evaluando (e) al calcular el valor de f (d, e) aunque (e) no se utilice en la función f. Sin embargo, las estructuras de control definidas por el usuario dependen de la sintaxis exacta, por ejemplo 

define g(a, b, c) = if a then b else c
l = g(h, i, j)

(i) y (j) se evaluarían en un lenguaje ávido. Mientras que en un idioma perezoso, 

l' = if h then i else j

Se evaluarían (i) o (j), pero nunca ambos.

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. Si (i) o (j) tienen efectos secundarios o introducen errores de tiempo de ejecución, las diferencias sutiles entre (l) y (l ') pueden ser complejas. Por lo general, es posible introducir estructuras de control perezosas definidas por el usuario en lenguajes ansiosos como funciones, aunque pueden apartarse de la sintaxis del lenguaje para una evaluación ansiosa: a menudo, los cuerpos de código involucrados (como (i) y (j)) deben estar envueltos en un valor de función, de modo que se ejecuten solo cuando se llamen.

La evaluación de cortocircuito de las estructuras de control booleanas a veces se denomina perezosa .

Trabajar con estructuras de datos infinitas

Muchos lenguajes ofrecen la noción de estructuras de datos infinitas . Estos permiten que las definiciones de datos se den en términos de rangos infinitos o recursividad sin fin, pero los valores reales solo se calculan cuando es necesario. Tomemos, por ejemplo, este programa trivial en Haskell: 

numberFromInfiniteList :: Int -> Int
numberFromInfiniteList n =  infinity !! n - 1
    where infinity = [1..]

main = print $ numberFromInfiniteList 4

En la función numberFromInfiniteList , el valor de infinito es un rango infinito, pero hasta que se necesite 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).

Patrón de lista de éxitos

Evitando un esfuerzo excesivo

Una expresión compuesta puede tener el formato EasilyComputed o LotsOfWork, de modo que si la parte fácil da verdadero, se podría evitar una gran cantidad de trabajo. Por ejemplo, suponga que se debe verificar un gran número N para determinar si es un número primo y una función IsPrime (N) está disponible, pero lamentablemente, puede requerir muchos cálculos para evaluar. Quizás N = 2 o [Mod (N, 2) ≠ 0 e IsPrime (N)] ayudarán si va a haber muchas evaluaciones con valores arbitrarios para N.

Evitación de condiciones de error

Una expresión compuesta puede tener el formato SafeTo Try y Expression, por lo que si SafeTo Try es falso, no se debe intentar evaluar la expresión para que no se señale un error en tiempo de ejecución, como dividir por cero o indexar fuera de los límites, etc. Por ejemplo, el siguiente pseudocódigo ubica el último elemento distinto de cero de una matriz: 

 L:=Length(A);
 While L>0 and A(L)=0 do L:=L - 1;

Si todos los elementos de la matriz son cero, el ciclo funcionará hasta L = 0 y, en este caso, el ciclo debe terminarse sin intentar hacer referencia al elemento cero de la matriz, que no existe.

Otros usos

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

Otro ejemplo de pereza en los sistemas informáticos modernos es la asignación de páginas de copia en escritura o la paginación por 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 la carga de páginas desde el disco impulsada por la demanda , de modo que solo las páginas realmente tocadas se cargan en la memoria y no se asigna 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 conduce a un error de memoria insuficiente al actualizar un elemento posteriormente en lugar de durante la operación de copia.

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 idiomas, la evaluación puede ser retrasado mediante la suspensión de forma explícita el cálculo utilizando la sintaxis especial (como ocurre con el esquema de " delay" y " force" y OCaml 's ' lazy' y " Lazy.force") o, más generalmente, envolviendo la expresión en un golpe seco . El objeto que representa una evaluación tan explícitamente retrasada se llama futuro perezoso . Raku usa la evaluación perezosa de listas, por lo que uno puede asignar listas infinitas a variables y usarlas como argumentos para funciones, pero a diferencia de Haskell y Miranda, Raku no usa la evaluación perezosa de operadores aritméticos y funciones por defecto.

Pereza y afán

Controlar el entusiasmo en lenguajes perezosos

En los lenguajes de programación perezosos como Haskell, aunque el valor predeterminado es evaluar las expresiones sólo cuando se exigen, en algunos casos es posible hacer que el código sea más ansioso o, por el contrario, hacerlo más perezoso nuevamente después de que se haya hecho 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 ansioso) 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 son conceptos técnicamente diferentes.

Sin embargo, hay una optimización implementada en algunos compiladores llamada análisis de rigurosidad , 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 de rigor obligará a una evaluación estricta.

En Haskell, marcar los campos del constructor como estrictos significa que sus valores siempre se exigirán de inmediato. La seqfunción también se puede usar para exigir un valor inmediatamente y luego pasarlo, lo cual es útil si un campo de constructor generalmente debe ser perezoso. Sin embargo, ninguna de estas técnicas implementa un 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 el ~calificador debe usarse para hacerlo perezoso.

Simular la pereza en idiomas á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 ha admitido una notación compacta para esto. La siguiente interfaz genérica de ejemplo proporciona un marco para la evaluación diferida: 

interface 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.

Cada clase que implementa la Lazyinterfaz debe proporcionar un evalmétodo, y las instancias de la clase pueden tener los valores que el método necesite para realizar una evaluación perezosa. Por ejemplo, considere el siguiente código para calcular e imprimir perezosamente 2 10 : 

Lazy<Integer> a = ()-> 1;
for (int i = 1; i <= 10; i++) {
    final Lazy<Integer> b = a;
    a = ()-> b.eval() + b.eval();
}
System.out.println( "a = " + a.eval() );

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

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

Este es un programa ineficiente porque esta implementación de enteros perezosos no memoriza el resultado de llamadas anteriores a eval . También implica una considerable cantidad de 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 adiciones reales involucradas en el cálculo del resultado se realizan en respuesta a la llamada a a.eval()en la línea final de código. Esta llamada recorre recursivamente la lista para realizar las adiciones necesarias.

Podemos construir una clase Java que memorice objetos perezosos de la siguiente manera: 

class Memo<T> implements Lazy<T> {
    private Lazy<T> lazy;  // a lazy expression, eval sets it to null
    private T memo = null; // the memorandum of the previous value

    public Memo( Lazy<T> lazy ) { // constructor
        this.lazy = lazy;
    }

    public T eval() {
        if (lazy != null) {
            memo = lazy.eval();
            lazy = null;
        }
        return memo;
    }
}

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

Lazy<Integer> a = ()-> 1;
for (int i = 1; i <= 10; i++) {
    final Lazy<Integer> b = a;
    a = new Memo<Integer>( ()-> b.eval() + b.eval() );
}
System.out.println( "a = " + a.eval() );

Tenga en cuenta que las expresiones lambda de Java son simplemente azúcar sintáctico . Todo lo 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 ser movido al nivel de anidación más externo.

JavaScript

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

/**
 * Generator functions return generator objects, which reify lazy evaluation.
 * @return {!Generator<bigint>} A non-null generator of integers.
 */
function* fibonacciNumbers() {
    let memo = [1n, -1n]; // create the initial state (e.g. a vector of "negafibonacci" numbers)
    while (true) { // repeat indefinitely
        memo = [memo[0] + memo[1], memo[0]]; // update the state on each evaluation
        yield memo[0]; // yield the next value and suspend execution until resumed
    }
}

let stream = fibonacciNumbers(); // create a lazy evaluated stream of numbers
let first10 = Array.from(new Array(10), () => stream.next().value); // evaluate only the first 10 numbers
console.log(first10); // the output is [0n, 1n, 1n, 2n, 3n, 5n, 8n, 13n, 21n, 34n]

Pitón

En Python 2.x, la range()función 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: 

>>> r = range(10)
>>> print r
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
>>> print r[3]
3

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

>>> r = range(10)
>>> print(r)
range(0, 10)
>>> print(r[3])
3
Este cambio a la evaluación diferida ahorra tiempo de ejecución para rangos grandes a los que nunca se puede hacer referencia por completo y el uso de memoria para rangos grandes donde solo se necesitan uno o unos pocos elementos 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 a pedido. La ventaja de xrangees que el objeto generado siempre ocupará la misma cantidad de memoria. 

>>> r = xrange(10)
>>> print(r)
xrange(10)
>>> lst = [x for x in r]
>>> print(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 tuplas o listas. Por ejemplo (Python 2): 

>>> numbers = range(10)
>>> iterator = iter(numbers)
>>> print numbers
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
>>> print iterator
<listiterator object at 0xf7e8dd4c>
>>> print iterator.next()
0
El ejemplo anterior muestra que las listas se evalúan cuando se llaman, pero en el caso del iterador, el primer elemento '0' se imprime cuando surge la necesidad.

.NET Framework

En .NET Framework es posible realizar una evaluación diferida usando la clase . 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 las que brindan soporte integrado para la evaluación diferida. System.Lazy<T>lazyforceMicrosoft.FSharp.Collections.Seq

let fibonacci = Seq.unfold (fun (x, y) -> Some(x, (y, x + y))) (0I,1I)
fibonacci |> Seq.nth 1000

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

public int Sum()
{
    int a = 0;
    int b = 0; 
    Lazy<int> x = new Lazy<int>(() => a + b);
    a = 3;
    b = 5;
    return x.Value; // returns 8
}

O con un ejemplo más práctico: 

// recursive calculation of the n'th fibonacci number
public int Fib(int n)
{
   return (n == 1)? 1 : (n == 2)? 1 : Fib(n-1) + Fib(n-2);
}

public void Main()
{
    Console.WriteLine("Which Fibonacci number do you want to calculate?");
    int n = Int32.Parse(Console.ReadLine()); 
    Lazy<int> fib = new Lazy<int>(() => Fib(n)); // function is prepared, but not executed
    bool execute; 
    if (n > 100)
    {
        Console.WriteLine("This can take some time. Do you really want to calculate this large number? [y/n]");
        execute = (Console.ReadLine() == "y"); 
    }
    else execute = true;
    
    if (execute) Console.WriteLine(fib.Value); // number is only calculated if needed
}

Otra forma es usar la yieldpalabra clave: 

// eager evaluation 
public IEnumerable<int> Fibonacci(int x)
{
    IList<int> fibs = new List<int>();

    int prev = -1;
    int next = 1;
    for (int i = 0; i < x; i++)
    {
        int sum = prev + next;
        prev = next;
        next = sum;
        fibs.Add(sum); 
    }
    return fibs;
}

// lazy evaluation 
public IEnumerable<int> LazyFibonacci(int x)
{
    int prev = -1;
    int next = 1;
    for (int i = 0; i < x; i++)
    {
        int sum = prev + next;
        prev = next;
        next = sum;
        yield return sum;
    }
}
Artículo principal: Thunk

Ver también

Referencias

Otras lecturas

enlaces externos