生成器 (電腦編程)

生成器（Generator），是電腦科學中特殊的子程序。實際上，所有生成器都是迭代器。生成器非常類似於返回陣列的函數，都是具有參數、可被調用、產生一系列的值。但是生成器不是構造出陣列包含所有的值並一次性返回，而是每次產生一個值，因此生成器看起來像函數，但行為像迭代器。

生成器可以用更有表達力的控制流結構實現，如協程或頭等續體。生成器，也被稱作半協程（semicoroutine），是特殊的、能力更弱的協程，總是在傳回一個值時把控制交還給調用者，而不是像協程那樣指出另一個協程繼續執行。

## 使用

生成器通常在一個循環內部被調用。生成器第一次被調用是在進入這個循環結構時，創建一個對象以封裝生成器的狀態、綁定的實參。生成器的實體接著被執行直至遇到一個特別的`yield`動作，在這裡提供給`yield`動作的值被返回給調用者。在下一次調用同一個生成器的時候，生成器從`yield`動作之後恢復執行，直到遇上另一個`yield`動作。生成器的執行也可以遇到`finish`動作而終止。

由於生成器在需要的才計算它的要被`yield`的值，因此可以用來代表一個串流，這種序列要一次性全部計算出來是昂貴的甚至是不可能的，這種情況還包括無窮序列或現場數據串流。

如果需要及早求值（主要是在序列是有限的時候，否則求值將永不終止），可以使用列表或使用並行結構來創建一個列表替代生成器。例如，Python的一個生成器`g`，通過`l = list(g)`，可被求值成列表`l`。而在F♯中，序列表達式`seq { ... }`，將除了`[ ... ]`之外的惰性的（生成器或序列）求值為及早的（列表）。

在有生成器出現的情況下，語言的循環構造，比如`for`和`while`，可以歸約成一個單一的`loop ... end loop`構造；可以用合適的生成器以正確的方式，順暢的模擬所有常見的循環構造。例如，一個按範圍的循環如`for x = 1 to 10`，可以通過生成器而被實現為迭代，比如Python的`for x in range(1, 10)`。進一步的，`break`可以被實現為向生成器發送`finish`，而接著在循環中使用`continue`。

## 歷史

生成器最早出現於CLU語言（1975年），也是字串操縱語言Icon（1977年）的顯著特徵。它現在出現在Python、C#、Ruby、最新版本的ECMAScript（ES6/ES2015）與其他語言之中。在CLU與C#中，生成器稱作迭代器，在Ruby稱作枚舉器。

## 語言實例

### CLU

CLU使用`yield`語句來在使用者定義數據抽象上進行迭代：

```ada
string_chars = iter (s: string) yields (char);
  index: int := 1;
  limit: int := string$size (s);
  while index <= limit do
    yield (string$fetch(s, index));
    index := index + 1;
    end;
end string_chars;

for c: char in string_chars(s) do
   ...
end;
```

### Icon

在Icon中，所有表達式（包括循環）都是生成器。語言有很多內建生成器，甚至使用生成器機制實現某些邏輯語義（邏輯析取或`OR`以此達成）。

列印從`0`到`20`的平方，可以如下這樣使用協程完成：

```icon
   local squares, j
   squares := create (seq(0) ^ 2)
   every j := |@squares do
      if j <= 20 then
         write(j)
      else
         break
```

但是多數時候，定製生成器是使用`suspend`關鍵字來實現，它的功能完全類似CLU中的`yield`關鍵字。

### C++

使用宏預處理的例子見:

```cpp
$generator(descent)
{
   // place for all variables used in the generator
   int i; // our counter

   // place the constructor of our generator, e.g. 
   // descent(int minv, int maxv) {...}
   
   // from $emit to $stop is a body of our generator:
    
   $emit(int) // will emit int values. Start of body of the generator.
      for (i = 10; i > 0; --i)
         $yield(i); // a.k.a. yield in Python,
                    // returns next number in [1..10], reversed.
   $stop; // stop, end of sequence. End of body of the generator.
};
```

可迭代：

```cpp
int main(int argc, char* argv[])
{
  descent gen;
  for(int n; gen(n);) // "get next" generator invocation
    printf("next number is %d\n", n);
  return 0;
}
```

C++11提供的foreach loop可用於任何具有`begin`與`end`成員函數的類。還需要有`operator!=`, `operator++` 與`operator*`。例如：

```cpp
#include <iostream>
int main()
{
    for (int i: range(10))
    {
        std::cout << i << std::endl;
    }
    return 0;
}
```

一個基本實現：

```cpp
class range
{
private:
    int last;
    int iter;

public:
    range(int end):
        last(end),
        iter(0)
    {}

    // Iterable functions
    const range& begin() const { return *this; }
    const range& end() const { return *this; }

    // Iterator functions
    bool operator!=(const range&) const { return iter < last; }
    void operator++() { ++iter; }
    int operator*() const { return iter; }
};
```

### C#

C# 2.0開始可以利用`yield`構造生成器。

```csharp
// Method that takes an iterable input (possibly an array)
// and returns all even numbers.
public static IEnumerable<int> GetEven(IEnumerable<int> numbers) {
    foreach (int i in numbers) {
        if ((i % 2) == 0) {
            yield return i;
        }
    }
}
```

可以使用多個`yield return`語句：

```csharp
public class CityCollection : IEnumerable<string> {
    public IEnumerator<string> GetEnumerator() {
        yield return "New York";
        yield return "Paris";
        yield return "London";
    }
}
```

### Python

Python自2001年的2.2版開始支持生成器。下面是生成器一個例子，它是個計數器：

```python
def countfrom(n):
    while True:
        yield n
        n += 1

# 例子使用: 打印出从10到20的整数
# 注意这个迭代通常会终止，即使countfrom()被写为了无限循环

for i in countfrom(10):
    if i <= 20:
        print(i)
    else:
        break
```

另一個生成器例子，它按需要無盡的產生素數：

```python
import itertools
def primes():
    yield 2
    n = 3
    p = []
    while True:
        if not any(n%f == 0 for f in 
                itertools.takewhile(lambda f: f*f <= n, p)): 
            yield n
            p.append(n)
        n += 2
```

Python的生成器可以認為是一個迭代器包含了凍結的棧幀。當用`next()`方法調用迭代器，Python恢復凍結的棧幀，繼續執行至下一次的`yield`語句。生成器的棧幀再一次凍結，被yield的值返回給調用者。

PEP 380 (Python 3.3開始)增加了`yield from`表達式，允許生成器將它的一部份操作委託給另一個生成器。

#### 生成器表達式

Python擁有建模於列表推導式的一種語法，叫做生成器表達式，用來輔助生成器的創建。下面的例子擴展了上面第一個例子，使用生成器表達式來計算來自`countfrom`生成器函數的數的平方：

```python
squares = (n*n for n in countfrom(2))

for j in squares:
    if j <= 20:
        print(j)
    else:
        break
```

### ECMAScript

ECMAScript 6介入了函數生成器。

使用函數生成器書寫一個無窮斐波那契序列：

```javascript
function* fibonacci(limit) {
    let [prev, curr] = [0, 1];
    while (!limit || curr <= limit) {
        yield curr;
        [prev, curr] = [curr, prev + curr];
    }
}

// 加上限10为边界
for (const n of fibonacci(10)) {
    console.log(n);
}

// 没有上界的生成器
for (const n of fibonacci()) {
    console.log(n);
    if (n > 10000) break;
}

// 手动迭代
let fibGen = fibonacci();
console.log(fibGen.next().value); // 1
console.log(fibGen.next().value); // 1
console.log(fibGen.next().value); // 2
console.log(fibGen.next().value); // 3
console.log(fibGen.next().value); // 5
console.log(fibGen.next().value); // 8

// 从停止的地方继续
for (const n of fibGen) {
    console.log(n);
    if (n > 10000) break;
}
```

### Smalltalk

下面例子使用Pharo Smalltalk，黃金分割率生成器對`goldenRatio next`調用，每次返回一個更加逼近的黃金分割率：

```Smalltalk
goldenRatio := Generator on: [ :g |
    | x y z r | 
	x := 0.
	y := 1.
	[  
		z := x + y.
		r := (z / y) asFloat.
		x := y.
		y := z.
		g yield: r
	] repeat	
].

goldenRatio next.
```

下面的表達式返回的下次`10`個逼近。

```Smalltalk
(1 to: 10) collect: [ :dummy | goldenRatio next].
```

## 參考文獻

- Stephan Murer, Stephen Omohundro, David Stoutamire and Clemens Szyperski: Iteration abstraction in Sather. ACM Transactions on Programming Languages and Systems, 18(1):1-15 (1996)