C# Language Lazy Evaluation Example: Fibonacci Numbers


Example

using System;
using System.Collections.Generic;
using System.Linq;
using System.Numerics; // also add reference to System.Numberics

namespace ConsoleApplication33
{
    class Program
    {
        private static IEnumerable<BigInteger> Fibonacci()
        {
            BigInteger prev = 0;
            BigInteger current = 1;
            while (true)
            {
                yield return current;
                var next = prev + current;
                prev = current;
                current = next;
            }
        }

        static void Main()
        {
            // print Fibonacci numbers from 10001 to 10010
            var numbers = Fibonacci().Skip(10000).Take(10).ToArray();
            Console.WriteLine(string.Join(Environment.NewLine, numbers));
        }
    }
}

How it works under the hood (I recommend to decompile resulting .exe file in IL Disaambler tool):

  1. C# compiler generates a class implementing IEnumerable<BigInteger> and IEnumerator<BigInteger> (<Fibonacci>d__0 in ildasm).
  2. This class implements a state machine. State consists of current position in method and values of local variables.
  3. The most interesting code are in bool IEnumerator.MoveNext() method. Basically, what MoveNext() do:
    • Restores current state. Variables like prev and current become fields in our class (<current>5__2 and <prev>5__1 in ildasm). In our method we have two positions (<>1__state): first at the opening curly brace, second at yield return.
    • Executes code until next yield return or yield break/}.
    • For yield return resulting value is saved, so Current property can return it. true is returned. At this point current state is saved again for the next MoveNext invocation.
    • For yield break/} method just returns false meaning iteration is done.

Also note, that 10001th number is 468 bytes long. State machine only saves current and prev variables as fields. While if we would like to save all numbers in the sequence from the first to the 10000th, the consumed memory size will be over 4 megabytes. So lazy evaluation, if properly used, can reduce memory footprint in some cases.