¿Cuáles son las ventajas de Lazy Evaluation?

Question

¿Qué ventajas hay en la evaluación diferida en comparación con la evaluación ansiosa?

¿Qué cantidad de rendimiento hay? ¿La evaluación lenta va a ser más lenta o más rápida? ¿Por qué (o depende de la implementación?)?

¿Cómo funciona la evaluación diferida actualmente trabajo en la mayoría de las implementaciones? Para mí, parecería que sería mucho más lento y requeriría más memoria porque las variables deben almacenar operaciones además de números. Entonces, ¿cómo funciona eso en un lenguaje como Haskell (nota, en realidad no conozco ese idioma)? ¿Cómo se implementa y se hace la pereza para que no sea tremendamente más lenta/consuma más espacio?

Answer 1

Esto se refiere a la evaluación de un árbol de sintaxis. Si evalúa un árbol de sintaxis de forma perezosa (es decir, cuando se necesita el valor que representa), debe llevarlo a través de los pasos precedentes de su cálculo en su totalidad. Esta es la sobrecarga de la evaluación perezosa. Sin embargo, hay dos ventajas. 1) no evacuarás el árbol innecesariamente si el resultado nunca se usa, y 2) puedes expresar y usar un árbol de sintaxis infinita de alguna forma recursiva, porque solo lo evaluarás a la profundidad que necesites, en lugar de evaluar (con impaciencia) en su totalidad, lo que sería imposible.

No conozco haskel, pero hasta donde sé, los lenguajes de programación como python o ML evalúan con entusiasmo. Por ejemplo, para simular la evaluación diferida en ML, debe crear una función ficticia que no tome parámetros pero devuelva el resultado. Esta función es entonces tu árbol de sintaxis que puedes evaluar perezosamente en cualquier momento invocándolo con una lista de argumentos vacía.

Answer 2

En ruby, usamos modificadores de función, generalmente llamados "una vez", para envolver un método para que haga una evaluación diferida. Tal método solo se evaluará una vez, el valor se almacenará en caché, las llamadas posteriores devolverán ese valor.

Un uso (o mal uso) de la evaluación perezosa es hacer que el orden de la inicialización del objeto sea implícito en lugar de explícito. Antes:

def initialize 
    setup_logging # Must come before setup_database 
    setup_database # Must come before get_addresses 
    setup_address_correction # Must come before get_addresses 
    get_addresses 
end 

def setup_logging 
    @log = Log.new 
end 

def setup_database 
    @db = Db.new(@log) 
end 

def setup_address_correction 
    @address_correction = AddressCorrection.new 
end 

def get_addresses 
    @log.puts ("Querying addresses") 
    @addresses = @address_correction.correct(query_addresses(@db)) 
end 

Con la evaluación perezosa:

def initialize 
    get_addresses 
end 

def log 
    Log.new 
end 
once :log 

def db 
    Db.new(log) 
end 
once :db 

def address_corrector 
    AddressCorrection.new 
end 
once :address_corrector 

def get_addresses 
    log.puts ("Querying addresses") 
    @addresses = address_corrector.correct(query_addresses(db)) 
end 

El orden de inicialización de los diversos objetos interdependientes es ahora (1) implícito, y (2) automático. En el lado negativo, el flujo de control puede ser opaco si se recurre demasiado a este truco.

Answer 3

La evaluación diferida puede ser muy útil en la creación de estructuras de datos con límites amortizados eficientes.

Sólo para dar un ejemplo, aquí es una clase de pila inmutable:

class Stack<T> 
{ 
    public static readonly Stack<T> Empty = new Stack<T>(); 
    public T Head { get; private set; } 
    public Stack<T> Tail { get; private set; } 
    public bool IsEmpty { get; private set; } 

    private Stack(T head, Stack<T> tail) 
    { 
     this.Head = head; 
     this.Tail = tail; 
     this.IsEmpty = false; 
    } 

    private Stack() 
    { 
     this.Head = default(T); 
     this.Tail = null; 
     this.IsEmpty = true; 
    } 

    public Stack<T> AddFront(T value) 
    { 
     return new Stack<T>(value, this); 
    } 

    public Stack<T> AddRear(T value) 
    { 
     return this.IsEmpty 
      ? new Stack<T>(value, this) 
      : new Stack<T>(this.Head, this.Tail.AddRear(value)); 
    } 
} 

Puede agregar un elemento a la parte delantera de la pila en O(1) tiempo, pero requiere O(n) el momento de añadir un elemento a la posterior. Como tenemos que reconstruir toda nuestra estructura de datos, AddRear es una operación monolítica.

Aquí está la misma pila inmutable, pero ahora su pereza evaluó:

class LazyStack<T> 
{ 
    public static readonly LazyStack<T> Empty = new LazyStack<T>(); 

    readonly Lazy<LazyStack<T>> innerTail; 
    public T Head { get; private set; } 
    public LazyStack<T> Tail { get { return innerTail.Value; } } 
    public bool IsEmpty { get; private set; } 

    private LazyStack(T head, Lazy<LazyStack<T>> tail) 
    { 
     this.Head = head; 
     this.innerTail = tail; 
     this.IsEmpty = false; 
    } 

    private LazyStack() 
    { 
     this.Head = default(T); 
     this.innerTail = null; 
     this.IsEmpty = true; 
    } 

    public LazyStack<T> AddFront(T value) 
    { 
     return new LazyStack<T>(value, new Lazy<LazyStack<T>>(() => this, true)); 
    } 

    public LazyStack<T> AddRear(T value) 
    { 
     return this.IsEmpty 
      ? new LazyStack<T>(value, new Lazy<LazyStack<T>>(() => this, true)) 
      : new LazyStack<T>(this.Head, new Lazy<LazyStack<T>>(() => this.Tail.AddRear(value), true)); 
    } 
} 

Ahora la función AddRear va claramente en O(1) tiempo.Cuando accedemos a la propiedad Tail, se evaluará un valor Lazy lo suficiente como para devolver el nodo principal, luego se detiene, por lo que ya no es una función monolítica.

Answer 4

La evaluación diferida es una propiedad común de los lenguajes de programación puramente funcionales para 'recuperar el rendimiento', funciona bastante simple, solo evalúa una expresión una vez que la necesita. Por ejemplo, considere en Haskell

if x == 1 then x + 3 else x + 2 

En estricta evaluación (ansioso), si x hecho, es igual a dos, entonces x + 3 se evalúa y devueltos, de lo x + 2, en Haskell, tal cosa sucede, x + 3 está simplemente compuesto a la expresión, por ejemplo, decir que tengo:

let x = if x == 1 then x + 3 else x + 2 

Bueno, entonces tienda que en una variable, pero lo que si nunca siempre siempre siempre uso esa variable debido a algunas otras condicionales hmm? Perdí una suma entera muy costosa en mi CPU para nada. (está bien, en la práctica no ganas en esto pero obtienes la idea con expresiones más grandes)

Entonces la pregunta es inútil, ¿por qué no son todos lenguajes lazy ?, bueno, la simple razón es que en puramente lenguajes funcionales, se garantiza que las expresiones no tendrán ningún efecto secundario. Si lo hubieran hecho, tendríamos que evaluarlos en el orden correcto. Es por eso que en la mayoría de los idiomas son evaluados con entusiasmo. En los idiomas en los que las expresiones no tienen ningún efecto secundario, no hay riesgo en la evaluación perezosa, por lo que es una opción lógica recuperar el rendimiento que tienden a perder en otras áreas.

Otro efecto secundario interesante es que if-then-else en Haskell es realmente una función del tipo Bool -> a -> a -> a. En Haskell esto significa que toma un argumento del tipo Boolean, otro del tipo any, otro del mismo tipo que el primero, y devuelve ese tipo nuevamente. No se encuentra con una evaluación infinita de diferentes ramas de control porque los valores se evalúan solo cuando son necesarios, lo que generalmente ocurre al final del programa cuando se ha compuesto una expresión enorme y luego se evalúa para el resultado final, descartando todas las cosas que el compilador cree que no son necesarias para el resultado final. Por ejemplo, si divido una expresión enormemente compleja por sí misma, solo se puede sustituir por '1' sin evaluar ambas partes.

La diferencia es visible en el esquema, que es tradicionalmente estrictamente evaluado, pero hay una variante perezoso llamado Lazy Esquema, en el Esquema (display (apply if (> x y) "x is larger than y" "x is not larger than y")) es un error porque if no es una función, que es una sintaxis especializada (aunque algunos dicen sintaxis es no es especial en Scheme) ya que no necesariamente evalúa todos sus argumentos, de lo contrario nos quedaríamos sin memoria si intentáramos calcular un factorial, por ejemplo. En Lazy Scheme eso funciona bien porque ninguno de esos argumentos se evalúa en absoluto hasta que una función realmente necesita el resultado para que la evaluación continúe, como mostrar.