生成器 (计算机编程)
![本页使用了标题或全文手工转换](http://images.weserv.nl/?url=//upload.wikimedia.org/wikipedia/commons/thumb/c/cd/Zh_conversion_icon_m.svg/35px-Zh_conversion_icon_m.svg.png)
生成器(Generator),是计算机科学中特殊的子程序。实际上,所有生成器都是迭代器[1]。生成器非常类似于返回数组的函数,都是具有参数、可被调用、产生一系列的值。但是生成器不是构造出数组包含所有的值并一次性返回,而是每次产生一个值,因此生成器看起来像函数,但行为像迭代器。
生成器可以用更有表达力的控制流结构实现,如协程或头等續體[2]。生成器,也被称作半协程(semicoroutine)[3],是特殊的、能力更弱的协程,总是在传回一个值时把控制交还给调用者,而不是像协程那样指出另一个协程继续执行。
使用
生成器通常在一个循环内部被调用。[4] 生成器第一次被调用是在进入这个循环结构时,创建一个对象以封装生成器的状态、绑定的实参。生成器的实体接着被执行直至遇到一个特别的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年)[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
以此达成)。
打印从0
到20
的平方,可以如下这样使用协程完成:
但是多数时候,定制生成器是使用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可用于任何具有begin
与end
成员函数的类。还需要有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].
参见
注释
- ^ 存档副本. [2017-11-30]. (原始内容存档于2020-06-25).
- ^ Kiselyov, Oleg. General ways to traverse collections in Scheme. January 2004 [2017-11-30]. (原始内容存档于2019-12-22).
- ^ 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. - ^ 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.
- ^ Liskov, Barbara. A History of CLU (PDF). April 1992 [2008-03-08]. (原始内容 (pdf)存档于2003-09-17).
- ^ 6.0 6.1 Python Enhancement Proposals: PEP 255: Simple Generators (页面存档备份,存于互联网档案馆), PEP 289: Generator Expressions (页面存档备份,存于互联网档案馆), PEP 342: Coroutines via Enhanced Generators (页面存档备份,存于互联网档案馆)
- ^ yield (C# Reference). [2017-11-30]. (原始内容存档于2016-11-16).
- ^ Liskov, B.; Snyder, A.; Atkinson, R.; Schaffert, C. Abstraction mechanisms in CLU. Communications of the ACM. 1977, 20 (8). doi:10.1145/359763.359789.
- ^ 存档副本. [2017-11-30]. (原始内容存档于2019-02-07).
- ^ PEP 380 -- Syntax for Delegating to a Subgenerator. [2017-11-30]. (原始内容存档于2020-06-04).
参考文献
- 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) [1] (页面存档备份,存于互联网档案馆)
|
|