生成器 (電腦編程)

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

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

使用

生成器通常在一個迴圈內部被呼叫。[4] 生成器第一次被呼叫是在進入這個迴圈結構時,建立一個對象以封裝生成器的狀態、繫結的實參。生成器的實體接著被執行直至遇到一個特別的yield動作,在這裡提供給yield動作的值被返回給呼叫者。在下一次呼叫同一個生成器的時候,生成器從yield動作之後恢復執行,直到遇上另一個yield動作。生成器的執行也可以遇到finish動作而終止。

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

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

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

歷史

生成器最早出現於CLU語言(1975年)[5],也是字串操縱語言Icon(1977年)的顯著特徵。它現在出現在Python[6]C#[7]Ruby、最新版本的ECMAScript(ES6/ES2015)與其他語言之中。在CLU與C#中,生成器稱作迭代器,在Ruby稱作列舉元。

語言實例

CLU

CLU使用yield語句來在使用者定義資料抽象上進行迭代[8]

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以此達成)。

列印從020的平方,可以如下這樣使用協程完成:

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

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

C++

使用宏預處理的例子見[9]:

$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.
};

可迭代:

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可用於任何具有beginend成員函式的類。還需要有operator!=, operator++operator*。例如:

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

一個基本實現:

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構造生成器。

// 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語句:

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

Python

Python自2001年的2.2版開始支援生成器[6]。下面是生成器一個例子,它是個計數器:

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

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

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

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

import itertools
def primes():
    yield 2
    n = 3
    p = []
    while True:
        # 这有效于Python 2.5+ 
        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表達式,允許生成器將它的一部份操作委託給另一個生成器。[10]

生成器表達式

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

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

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

Smalltalk

下面例子使用Pharo Smalltalk黃金分割率生成器對goldenRatio next呼叫,每次返回一個更加逼近的黃金分割率:

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逼近

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

參見

注釋

  1. ^ 存档副本. [2017-11-30]. (原始內容存檔於2020-06-25). 
  2. ^ Kiselyov, Oleg. General ways to traverse collections in Scheme. January 2004 [2017-11-30]. (原始內容存檔於2019-12-22). 
  3. ^ O. -J. Dahl; C. A. R. Hoare. Hierarchical Program Structures. C. A. R. Hoare (編). Structured Programming. London, UK: Academic Press. 1972: 175–220. ISBN 978-0122005503. In SIMULA, a coroutine is represented by an object of some class, co-operating by means of resume instructions with objects of the same or another class, which are named by means of reference variables. ……
    Thus a main program may establish a coroutine relationship with an object that it has generated, using the call/detach mechanism instead of the more symmetric resume/resume mechanism. In this case, the generated object remains subordinate to the main program, and for this reason is sometimes known as a Semicoroutine. ……
    Let X and Y be objects, generated by a "master program" M. Assume that M issues a call (X), thereby invoking an "active phase" of X, terminated by a detach operation in X; and then issues a call (Y), and so forth. In this way M may act as a "supervisor" sequencing a pattern of active phases of X, Y, and other objects. Each object is a "slave", which responds with an active phase each time it is called for, whereas M has the responsibility to define the large scale pattern of the entire computation.
    Alternatively the decision making may be "decentralised", allowing an object itself to determine its dynamic successor by a resume operation. The operation resume (Y), executed by X, combines an exit out of X (by detach) and a subsequent call (Y), thereby bypassing M. Obligation to return to M is transferred to Y.
     
  4. ^ The Icon Programming Language utilizes generators to implement its goal directed evaluation. In Icon, generators can be invoked in contexts outside of the normal looping control structures.
  5. ^ Liskov, Barbara. A History of CLU (PDF). April 1992 [2008-03-08]. (原始內容 (pdf)存檔於2003-09-17). 
  6. ^ 6.0 6.1 Python Enhancement Proposals: PEP 255: Simple Generators頁面存檔備份,存於網際網路檔案館), PEP 289: Generator Expressions頁面存檔備份,存於網際網路檔案館), PEP 342: Coroutines via Enhanced Generators頁面存檔備份,存於網際網路檔案館
  7. ^ yield (C# Reference). [2017-11-30]. (原始內容存檔於2016-11-16). 
  8. ^ Liskov, B.; Snyder, A.; Atkinson, R.; Schaffert, C. Abstraction mechanisms in CLU. Communications of the ACM. 1977, 20 (8). doi:10.1145/359763.359789. 
  9. ^ 存档副本. [2017-11-30]. (原始內容存檔於2019-02-07). 
  10. ^ PEP 380 -- Syntax for Delegating to a Subgenerator. [2017-11-30]. (原始內容存檔於2020-06-04). 

參考文獻