language-agnostic - tecnicas - programacion logica y funcional pdf

¿Cuáles son las ventajas de la evaluación perezosa?

Question

¿Qué ventajas tiene la evaluación perezosa en comparación con la evaluación impaciente?

¿Qué sobrecarga de rendimiento hay? ¿La evaluación perezosa será más lenta o más lenta? ¿Por qué (o depende de la implementación)?

¿Cómo funciona realmente la evaluación perezosa en la mayoría de las implementaciones? A mi parecer, parece que sería mucho más lento y requeriría mucha memoria, ya que las variables deben almacenar operaciones y números. Entonces, ¿cómo funciona eso en un lenguaje como Haskell (nota, realmente 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

En ruby, usamos modificadores de función, típicamente llamados "una vez", para envolver un método para que haga una evaluación perezosa. Dicho método solo se evaluará una vez, el valor se almacenará en la memoria caché y las llamadas posteriores devolverán ese valor.

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

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 confía demasiado en este truco.

Answer 2

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

No sé haskel, pero por lo que sé, lenguajes de programación como Python o ML evalúan con entusiasmo. Por ejemplo, para simular una evaluación perezosa en ML, debe crear una función ficticia que no tome parámetros pero devuelva el resultado. Esta función es su árbol de sintaxis que puede evaluar perezosamente en cualquier momento invocándola con una lista de argumentos vacía.

Answer 3

La evaluación perezosa 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 una evaluación estricta (ansiosa), si x es igual a dos, entonces x + 3 se evalúa y devuelve, de lo contrario, x + 2, en Haskell, no ocurre tal cosa, x + 3 se compone solo de la expresión, por ejemplo, di que tengo

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

Bueno, luego guardo eso en una variable, pero ¿qué pasa si alguna vez uso esa variable debido a algún otro condicional hmm? Perdí una suma entera muy cara en mi CPU para nada. (bueno, en la práctica no ganas con esto, pero obtienes la idea con expresiones más grandes)

Entonces surge la pregunta: ¿por qué no todos los lenguajes son perezosos ?, bueno, la razón simple es que en los lenguajes puramente funcionales, las expresiones tienen la garantía de no tener efectos secundarios. 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 idiomas donde las expresiones no tienen efectos secundarios, 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 cualquier tipo, 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 solo se evalúan cuando se necesitan, lo que generalmente se encuentra 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 piensa que no son necesarias para el resultado final. Por ejemplo, si divido una expresión muy compleja por sí misma, solo puede sustituirse por ''1'' sin evaluar ambas partes.

La diferencia es visible en Esquema, que tradicionalmente se evalúa estrictamente, pero hay una variante perezosa llamada Esquema perezoso, en Esquema (display (apply if (> xy) "x is larger than y" "x is not larger than y")) es un error porque if no es una función, es una sintaxis especializada (aunque algunos dicen que la sintaxis no es nada especial en Esquema) 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 la visualización.

Answer 4

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

Solo para dar un ejemplo, aquí hay 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 al frente de la pila en O(1) , pero requiere O(n) tiempo para agregar un elemento en la parte 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 se evalúa perezosamente:

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 se ejecuta claramente en tiempo O(1) ahora. Cuando accedemos a la propiedad Tail , evaluará un valor perezoso lo suficiente para devolver el nodo principal, luego se detiene, por lo que ya no es una función monolítica.