generator

generator introduction

本文主要介绍基于rust的generator库的基本概念和使用方法。rust的generator的语义同Python的generator语义基本一致。

generator是一种非常特殊的函数。与普通函数不同的是它可以有多个返回点。普通的函数只有一个返回点,也就是return指令,执行return之后这个函数就完成了。而generator可以通过yield有多个返回点,并且当generator再次运行时又会从上一次的运行环境中继续执行yield之后的指令。generator也可以使用return指令作为最后一个返回点,表示这个generator已经完成,不能再重入了,这和普通函数是一样的。generator的调用者使用send接口来访问它。send/yield组成了一对完整的调用路径:send使程序的执行由调用者转入generator;yield使程序的执行由generator返回调用者。由于generator具有函数的所有性质,因而可以在任何环境中调用generator,比如在线程中调用generator,在generator中调用generator,在协程中调用generator等,凡是函数可以出现的地方,都可以替换为generator。

generator在实现上是有自己的独立的栈的,在yield返回之后栈仍然保存着当前的执行状态。因而当下一次调用它的send接口时可以恢复到上次执行的地方。读者可以参考《generator与coroutine的设计与实现》一文获得更加深入的理解。

generator类型的定义如下:

A表示传入generator的数据类型,T表示从generator传出的数据类型。'a表示generator函数体的生存有效期。这个生存周期是由创建generator时传入的函数参数决定的。

generator的创建

Gn是创建generator的接口类型。它提供了两种形式的generator创建,普通形式的创建和Scoped形式的创建。

普通形式的创建创建接口例子如下,其传入的参数是符合FnOnce() -> T定义的任意函数类型。在generator函数体中只能使用yield_()等原语。同时还必须指出generator传入参数的类型。

由于yield关键字已经被rust语言留用,因而我们不能直接使用它,本文中使用yield_()函数指代。

Scoped形式的创建举例如下,其传入的参数是符合FnOnce(Scope<A, T>) -> T定义的任意函数类型。Scope表示当前generator自身的一个代理。在generator函数体中可以使用Scopeyield_等成员函数。

yeild接口有一个问题,就是无法获取当前generator的传入传出参数类型,必须手动指定。同时运行时的参数类型检查也不够高效。另外一个限制是参数类型必须是'static的才能满足Any接口的要求。所以要实现一个有参数类型静态检查的generator,就必须向generator的函数体中提供额外的变量来提供这些参数信息。这个额外的变量类型就是Scope。从上面的例子中可以看到使用new_scoped()接口的创建并没有指定传入参数类型A,它可以由编译器自动推导得到,同时s.yield_()的返回类型也由编译器做了静态检查。基于以上优点,我们应该尽量使用scoped版本的创建函数。

上面的两个创建接口都是使用默认大小的栈(4K word,在64位系统下为32K bytes)。如果想要创建指定栈大小的generator,可以使用new_opt()new_scoped_opt()接口
例如Scoped形式的创建举例如下:

generator的调用

调用一个generator只需要使用它的raw_send()send()接口。其定义分别如下:

其中send()接口只是raw_send()接口的简单包装,参数传递上使用了原始数据类型,而非Option数据类型。当我们无需向generator传递数据时,就可以使用raw_send(None)

当第一次启动一个generator时,我们并不需要指定一个传入参数,因为generator会首先返回一个值。当第二次调用generator时,generator才会取得这个传入的值,这一点要特别注意。

Iterator

当generator没有传入参数时,也就是A()类型时,generator还实现了Iterator接口,它实际上调用的就是raw_send()接口。

以下是一个使用的例子:

generator的返回

从generator中返回给调用者,可以有如下几种形式的返回:

return

return关键字会终止当前的generator,当调用is_done()时会返回true。例如:

yield

yield_()函数表示从当前generator向调用者返回一个传出值,并且当generator再次重入时,取出调用者发送给它的传入值。
它的定义如下:

可以参考上面send()接口的例子。

done

done!()是一个宏调用。它是一个特殊的return。表示立即从当前generator返回,却没有携带任何返回值。

它在统一代码上非常有用,例如在一个循环结束后,可以直接使用done!()来返回,而无需在构造最后一个返回值。

上面 Iterator 的例子可以改成如下形式

yield_from

yield_from()函数表示从一个已有的generator中返回参数,而当前generator则是作为一个代理。它循环调用传入的generator,所需参数从其自身的环境变量中取得,将传入generator的返回值返回给自己的调用者。
下面的例子演示了将两个generator的输出连接起来

yield_with
在上面yield的语义描述中我们知道第一次启动generator时不必准备传入参数,因为它首先返回给调用者,然后再取得下一次send时的传入参数。这其实是一种调用反转,相当于generator先向调用者传出数据,调用者处理这个数据,然后调用者将处理结果再次发送给generator。这样做有些违反直觉,但是这样的逻辑兼容了Python的语义,便于算法的移植。

其实generator库提供了更加底层的原语。它们就是yield_with()get_yield()函数。yield_with()函数直接将数据返回给调用者,而并不处理传入的参数。get_yield()函数只是取得传入的参数。实际上yield_()函数本身就是这两个原语的组合。

为了解决调用反转的问题,我们可以在generator中首先调用get_yield()函数取得出入参数,然后再调用yield_with()函数返回结果。下面的例子是返回所有历史传入参数的和。

generator的取消

在上一个例子中创建的generator永远处于循环当中,如果不析构它或是显式的取消它,则在函数中已经分配的资源就得不到释放。generator库提供了cancel()函数用来取消一个generator,从而可以顺利的释放其资源。同样的在generator的析构函数当中,如果判断出当前generator没有完成,则会默认调用它的cancel()函数。因此上面的例子在结束时会自动调用cancel()函数。

显示调用cancel()函数的例子。

generator的特性

利用generator进行编程直观简单,在如何更好的使用generator上,应该了解以下几个方面:

generator是特殊的函数

generator是拥有多个返回点的函数,另一方面普通函数是只有一个返回点的generator,所以也可以说普通函数是特殊的generator。实际上通过闭包(closure)我们可以很容易的将任意的函数调用转化为generator调用。在上面xrange的例子中我们已经见到了。

generator当中一般都会出现yield调用。generator库中的所有yield调用都允许出现在任何位置上,甚至是子函数的内部。实际上在运行时我们会做一定的检查,如果判断出当前是在generator的运行期间,yield调用回会正常执行,否则就会抛出异常。

以下的yield调用不在generator当中,所以会出错

以下的yield调用出现在子函数里,可以正常运行

generator是特殊的结构体

generator可以返回自身栈内部的数据,只要generator不是处于完成状态。generator拥有自己独立的栈,在运行期间栈上的数据是一直存在的,因而对其数据的引用也是有效的。当运行完return指令后,或是被取消后,它的栈会被销毁,而栈上的数据也会随之消失。由于这些数据保存在独立的栈上,这和普通的结构实例非常类似,它们都拥有属于自己的数据。只不过generator栈上的数据是融入到代码中的,并不需要定义特殊的结构。事实上只要generator拥有相同类型的输入输出参数,它们可以看做是相同类型的实例。

以下代码中,generator返回了内部的一块地址,这是安全的,缺点是必须使用unsafe以绕过rust的生命周期检查。

generator是自动状态机

generator本身也是一个自动状态机。栈完整的记录了它的内部状态,下次的执行又会从上次留下的状态开始。

下面的例子是一个简单的CD player

上面的例子会输出

generator的应用

generator是一种非常有用的编程工具,以下列举了generator的几个应用方面。

Iterator

generator最常用的场景就是随意的创建Iterator。这类generator没有指定输入参数。
以下的例子会输出一个fib数列:

pipe

generator可以处理一个序列,将generator作为一个处理单元然后串接起来。
以下的例子先求元素的平方,再求元素的平方和

解递归

TODO:

实现协程

generator是实现协程的基础,详见《generator与coroutine的设计与实现》一文

Leave a Reply

Your email address will not be published. Required fields are marked *