Generator in Programming Language

看到C#的yield之後，上網查了一下，發現這是Generator的概念。根據Wiki上的寫法

A generator is a special routine that can be used to control the iteration behaviour of a loop

以C#為程式語言示範，假設沒有控制Iterator的話，印出一到一百間所有質數，我們會這麼寫。

static IList<int> GeneratorPrimes()
{
        var result = new List<int>();
        for (int i = 2; i <= 100; i++)
        {
            bool flag = true;
            for (int j = 2; j * j <= i && flag; j++)
                if (i % j == 0) flag = false;
            if (flag) result.Add(i);
        }
        return result;
 }
 
 IList<int> ans = GeneratorPrimes();
 foreach (var item in ans)
 {
        Console.WriteLine(" {0} ", item);
 }

假設我們想產生無限的質數列表，這方法就不適用，因此我們需要改變一個思緒，每次從中取得一個數，需要的時候在取下一個，因此，我們需要儲存狀態。

foreach (var item in GeneratorPrime())
{
        Console.WriteLine(" {0} ", item);
}

至於GeneratorPrime的作法就是我們要討論的部份

沒有語言支援的作法

沒有語言支援，只好再內部維護一個狀態機，記住當今狀態，以及如何移動狀態。

public class PrimesGenerator : IEnumerator<int>
{
    int current, next;
    public PrimesGenerator()
    {
        Reset();
    }
    private void calcNext()
    {
        for (next++; ; next++)
        {
            bool flag = true;
            for (int i = 2; flag && i * i <= next; i++)
                if (next % i == 0) flag = false;
            if (flag) break;
        }
    }
    public bool MoveNext()
    {
        return current < 100;
    }
    public void Dispose()
    {
    }
    public int Current 
    { 
        get {
            int ret = current;
            current = next;
            calcNext();
            return ret;
        }  
    }
    object System.Collections.IEnumerator.Current
    {
        get {
            int ret = current;
            current = next;
            calcNext();
            return ret;
        }  
    }
    public void Reset()
    {
        current = 2;
        next = 3;
    }
}
public class IEnumerablePrimes : IEnumerable<int> 
{
    public IEnumerator<int> GetEnumerator()
    {
        return new PrimesGenerator();
    }
    System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
    {
        return GetEnumerator();
    }
}
public static IEnumerable<int> GeneratorPrime()
{
    return new IEnumerablePrimes();
}

C++和Java的作法略有不同，不過重點是放在PrimesGenerator中各種狀態的保存及移轉。如果簡單的話還好，像是Tree Traversal這種複雜的情況就一個頭兩個大。

語言支援的作法

由於C#提供yield，yield表示江控制權教還給呼叫者，而Iterator保持在回傳時的那個狀態，當再一度被呼叫時，可以重剛剛那個狀態繼續運行下去，於是我們程式碼可以寫成這樣。

public static IEnumerable<int> GeneratorPrime()
{
        for (int i = 2; i <= 100; i++)
        {
            bool flag = true;
            for (int j = 2; j * j <= i && flag; j++)
                if (i % j == 0) flag = false;
            if (flag) yield return i;
        }
}

這邊的yield就是一個syntax sugar，透過編譯器的幫忙，將上面這段code改寫成類似上面的State Machine，有興趣的人可以透過Resharper來看看邊義氣幫你處理掉多少東西。

Haskell的解法

由於Haskell有Lazy evaluation，所有東西都是Generator，所以可以寫成這樣。

primes = 2 : 3 : nextprime 5  where
  nextprime n | b = n : nextprime (n+2)
              | otherwise = nextprime (n+2)
    where b = all ((/= 0).(rem n)) $ takeWhile ((<= n).(^2)) $ tail primes

printPrimes = mapM_ print $ takeWhile (<= 100) primes

前面的primes產生一個無限質數數列，而printPrimes印出這個數列中滿足條件的部份，