What are the advantages of Lazy Evaluation?

Question

What advantages are there to Lazy Evaluation as opposed to Eager Evaluation?

What performance overhead is there? Is Lazy Evaluation going to be slower or faster? Why(or does it depend on implementation?)?

How does lazy evaluation actually work in most implementations? To me it would seem like it would be much slower and memory intensive because variables must stored operations as well as numbers. so how does that work in a language like Haskell(note, I don't actually know that language)? How is the lazyness implemented and done so that it is not tremendously slower/consume more space?

Answer 1

This refers to the evaluation of a syntax tree. If you evaluate a syntax tree lazily (i.e. when the value it represents is needed), you must carry it through the preceeding steps of your computation in its entirety. This is the overhead of lazy evaluation. However, there are two advantages. 1) you will not evaulate the tree unnecessarily if the result is never used, and 2) you can express and use an infinite syntax tree in some recursive form, because you will only ever evaluate it to the depth you need, as opposed to evaluating (eagerly) in its entirety, which would be impossible.

I don't know haskel, but as far as I know programming languages like python or ML evaluate eagerly. For example to simulate lazy evaluation in ML, you must create a dummy function that takes no parameters but returns the result. This function is then your syntax tree that you can lazily evaluate at any time by invoking it with an empty argument list.

Answer 2

In ruby, we use function modifiers, typically called "once", to wrap a method so that it does lazy evaluation. Such a method will only be evaluated once, the value cached, subsequent calls returning that value.

One use (or misuse) of lazy evaluation is to make order of object initialization implicit rather than explicit. Before:

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

With lazy evaluation:

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

The order of initialization of the various interdependent objects is now (1) implicit, and (2) automatic. On the downside, the flow of control can be opaque if this trick is relied upon too heavily.

Answer 3

Lazy evaluation can be pretty useful in the creation of data structures with efficient amortized bounds.

Just to give an example, here is an immutable stack class:

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));
    }
}

You can add an item to the front of the stack in O(1) time, but it requires O(n) time to add an item to the rear. Since we have to re-build our entire data structure, AddRear is a monolithic operation.

Here's the same immutable stack, but now its lazily evaluated:

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));
    }
}

Now the AddRear function clearly runs in O(1) time now. When we access the Tail property, it will evaluate a Lazy value just enough to return the head node, then it stops, so its no longer a monolithic function.

Answer 4

Lazy evaluation is a common property of purely functional programming languages to 'win back performance', it works quite simple, you only evaluate an expression once you need it. For instance, consider in Haskell

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

In strict (eager) evaluation, if x indeed is equal to two, then x + 3 is evaluated and returned, else x + 2, in Haskell, no such thing happens, x + 3 is just composed unto the expression, for instance, say I have:

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

Well, then I store that in a variable, but what if I never ever ever ever use that variable due to some other conditionals hmm? I wasted a very expensive integer addition on my CPU for nothing. (okay, in practise you don't win on this but you get the idea with larger expressions)

Then the question begs, why aren't all languages lazy?, well, the simple reason is that in purely functional languages, expressions are guaranteed to have no side-effects at all. If they had, we would have to evaluate them in the right order. That's why in most languages they are eagerly evaluated. In languages where expressions have no side effect, there is no risk in lazy evaluation so it's a logical choice to win back the performance they tend to lose on other areae.

Another interesting side effect is that if-then-else in Haskell is really a function of the type Bool -> a -> a -> a. In Haskell this means that it takes one argument of the type Boolean, another of the any type, another of the same type as the first, and returns that type again. You don't run into infinite evaluation of different control branches because values are evaluated only when they are needed for, which usually is at the very end of the program when a huge expression has been composed and is then evaluated for the final result, discarding all things the compiler thinks are not needed for the end result. For instance if I divide a hugely complex expression by itself, it can just be substituted for '1' without evaluating both parts.

The difference is visible in Scheme, which is traditionally strictly evaluated, but there is a lazy variant called Lazy Scheme, in Scheme (display (apply if (> x y) "x is larger than y" "x is not larger than y")) is an error because if is not a function, it's a specialized syntax (though some say syntax is not special in Scheme at all) as it does not necessarily evaluates all its arguments, else we'd run out of memory if we tried to compute a factorial for instance. In Lazy Scheme that works just fine because none of those arguments is evaluated at all until a function really needs the result for evaluation to continue, like display.