c# - Deferred execution and eager evaluation

Question

Could you please give me an example for Deferred execution with eager evaluation in C#?

I read from MSDN that deferred execution in LINQ can be implemented either with lazy or eager evaluation. I could find examples in the internet for Deferred execution with lazy evaluation, however I could not find any example for Deferred execution with eager evaluation.

Moreover, how deferred execution differs from lazy evaluation? In my point of view, both are looking same. Could you please provide any example for this too?

Answer 1

Bellow is my answer but also note that Jon Skeet spoke about it today on his blog an about the fact that he is not totally ok with the MSDN meaning of "Lazy" as MSDN isn't really clear of what lazy exactly mean when they use it in Just how lazy are you ? his post make for an interesting read.

Additionally Wikipedia assume that three rules should be maintained for lazy evaluation and third point isn't respected in MSDN meaning as the expression will be evaluated more than once if GetEnumerator is called again (By the spec Reset is not implemented on enumerator objects generated using the yield keyword and most of linq use it currently)

---

Considering a function

int Computation(int index)

Immediate execution

IEnumerable<int> GetComputation(int maxIndex)
{
    var result = new int[maxIndex];
    for(int i = 0; i < maxIndex; i++)
    {
        result[i] = Computation(i);
    }
    return result;
}

• When the function is called Computation is executed maxIndex times
• GetEnumerator returns a new instance of the enumerator doing nothing more.
• Each call to MoveNext put the the value stored in the next Array cell in the Current member of the IEnumerator and that's all.

Cost: Big upfront, Small during enumeration (only a copy)

Deferred but eager execution

IEnumerable<int> GetComputation(int maxIndex)
{
    var result = new int[maxIndex];
    for(int i = 0; i < maxIndex; i++)
    {
        result[i] = Computation(i);
    }
    foreach(var value in result)
    {
        yield return value;
    }
}

• When the function is called an instance of an auto generated class (called "enumerable object" in the spec) implementing IEnumerable is created and a copy of the argument (maxIndex) is stored in it.
• GetEnumerator returns a new instance of the enumerator doing nothing more.
• The first call to MoveNext executes maxIndex times the compute method, store the result in an array and Current will return the first value.
• Each subsequent call to MoveNext will put in Current a value stored in the array.

Cost: nothing upfront, Big when the enumeration start, Small during enumeration (only a copy)

Deferred and lazy execution

IEnumerable<int> GetComputation(int maxIndex)
{
    for(int i = 0; i < maxIndex; i++)
    {
        yield return Computation(i);
    }
}

• When the function is called the same thing as the lazy execution case happens.
• GetEnumerator returns a new instance of the enumerator doing nothing more.
• Each call to MoveNext execute once the Computation code, put the value in Current and let the caller immediately act on the result.

Most of linq use deferred and lazy execution but some functions can't be so like sorting.

Cost: nothing upfront, Moderate during enumeration (the computation is executed there)

To summarize

• Immediate mean that the computation/execution is done in the function and finished once the function return. (Fully eager evaluation as most C# code does)
• Deferred/Eager mean that most of the work will be done on the first MoveNext or when the IEnumerator instance is created (For IEnumerable it is when GetEnumerator is called)
• Deferred/Lazy mean that the work will be done each time MoveNext is called but nothing before.

Parallel LINQ does it a little differently as the computation could be considered deferred/Lazy from the point of view of the caller but internally the computation of some number of elements begin in parallel as soon as the enumeration begin. The result is that if the next value is already there you get it immediately but otherwise you will have to wait for it.