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类型的定义如下:
|
pub type Generator<'a, A, T> = ......; |
A
表示传入generator的数据类型,T
表示从generator传出的数据类型。'a
表示generator函数体的生存有效期。这个生存周期是由创建generator时传入的函数参数决定的。
generator的创建
Gn
是创建generator的接口类型。它提供了两种形式的generator创建,普通形式的创建和Scoped形式的创建。
|
impl<A: Any> Gn<A> { /// create a new generator with default stack size pub fn new<'a, T: Any, F>(f: F) -> Generator<'a, A, T> where F: FnOnce() -> T + 'a } impl<A> Gn<A> { /// create a scoped generator with default stack size pub fn new_scoped<'a, T, F>(f: F) -> Generator<'a, A, T> where F: FnOnce(Scope<A, T>) -> T + 'a |
普通形式的创建创建接口例子如下,其传入的参数是符合FnOnce() -> T
定义的任意函数类型。在generator函数体中只能使用yield_()
等原语。同时还必须指出generator传入参数的类型。
由于yield
关键字已经被rust语言留用,因而我们不能直接使用它,本文中使用yield_()
函数指代。
|
let mut g = Gn::<()>::new(|| { yield_::<u32>(17); return 42u32; }); |
Scoped形式的创建举例如下,其传入的参数是符合FnOnce(Scope<A, T>) -> T
定义的任意函数类型。Scope
表示当前generator自身的一个代理。在generator函数体中可以使用Scope
的yield_
等成员函数。
|
let mut g = Gn::new_scoped(|mut s| { s.yield_(17); return 42; }); |
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形式的创建举例如下:
|
// set the stack size to 0x2000 words let mut g = Gn::new_scoped_opt(0x2000, |mut s| { s.yield_(17); return 42; }); |
generator的调用
调用一个generator只需要使用它的raw_send()
和send()
接口。其定义分别如下:
|
impl<'a, A, T> Generator<'a, A, T> { pub fn raw_send(&mut self, para: Option<A>) -> Option<T> {......} pub fn send(&mut self, para: A) -> T {......} } |
其中send()
接口只是raw_send()
接口的简单包装,参数传递上使用了原始数据类型,而非Option
数据类型。当我们无需向generator传递数据时,就可以使用raw_send(None)
。
当第一次启动一个generator时,我们并不需要指定一个传入参数,因为generator会首先返回一个值。当第二次调用generator时,generator才会取得这个传入的值,这一点要特别注意。
|
let mut g = Gn::new_scoped(|mut s| { let a = s.yield_(5); assert_eq!(a, Some(10)); 42 }); // first send a None to start the generator assert_eq!(g.raw_send(None), Some(5)); assert_eq!(g.send(10), 42); |
Iterator
当generator没有传入参数时,也就是A
为()
类型时,generator还实现了Iterator
接口,它实际上调用的就是raw_send()
接口。
|
impl<'a, T> Iterator for Generator<'a, (), T> { type Item = T; fn next(&mut self) -> Option<T> { self.raw_send(None) } } |
以下是一个使用的例子:
|
let g = Gn::new_scoped(|mut s| { for i in 0..10 { s.yield_(i); } 10 // this is the last return }); // sum from 0 to 10 let sum = g.fold(0, |acc, x| { acc + x }); assert_eq!(sum, 55); |
generator的返回
从generator中返回给调用者,可以有如下几种形式的返回:
return
return
关键字会终止当前的generator,当调用is_done()
时会返回true
。例如:
|
let mut g = Gn::new_scoped(|_s| { return 42; }); assert_eq!(g.next(), Some(42)); assert!(g.is_done()); |
yield
yield_()
函数表示从当前generator向调用者返回一个传出值,并且当generator再次重入时,取出调用者发送给它的传入值。
它的定义如下:
|
impl<A, T> Scope<A, T> { pub fn yield_(&mut self, v: T) -> Option<A> {......} } |
可以参考上面send()
接口的例子。
done
done!()
是一个宏调用。它是一个特殊的return
。表示立即从当前generator返回,却没有携带任何返回值。
|
let mut g = Gn::new_scoped(|mut s| { s.yield_(2); done!(); }); assert_eq!(g.next(), Some(2)); assert!(!g.is_done()); assert_eq!(g.next(), None); assert!(g.is_done()); |
它在统一代码上非常有用,例如在一个循环结束后,可以直接使用done!()
来返回,而无需在构造最后一个返回值。
上面 Iterator 的例子可以改成如下形式
|
let g = Gn::new_scoped(|mut s| { for i in 0..11 { s.yield_(i); } done!(); // this is the last return None }); |
yield_from
yield_from()
函数表示从一个已有的generator中返回参数,而当前generator则是作为一个代理。它循环调用传入的generator,所需参数从其自身的环境变量中取得,将传入generator的返回值返回给自己的调用者。
下面的例子演示了将两个generator的输出连接起来
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
|
fn xrange(start: u32, end: u32) -> u32 { for i in start..end { yield_::<(), _>(i); } done!(); } let g1 = Gn::new(|| xrange(0, 10)); let g2 = Gn::new(|| xrange(10, 20)); // this will generate 0..20 let g = Gn::new_scoped(|mut s| { s.yield_from(g1); s.yield_from(g2); done!(); }); // sum of [0..20) let sum = g.fold(0, |acc, x| { acc + x }); assert_eq!(sum, 190); |
yield_with
在上面yield
的语义描述中我们知道第一次启动generator时不必准备传入参数,因为它首先返回给调用者,然后再取得下一次send
时的传入参数。这其实是一种调用反转,相当于generator先向调用者传出数据,调用者处理这个数据,然后调用者将处理结果再次发送给generator。这样做有些违反直觉,但是这样的逻辑兼容了Python的语义,便于算法的移植。
其实generator库提供了更加底层的原语。它们就是yield_with()
和get_yield()
函数。yield_with()
函数直接将数据返回给调用者,而并不处理传入的参数。get_yield()
函数只是取得传入的参数。实际上yield_()
函数本身就是这两个原语的组合。
|
impl<A, T> Scope<A, T> { pub fn yield_(&mut self, v: T) -> Option<A> { self.yield_with(v); self.get_yield() } } |
为了解决调用反转的问题,我们可以在generator中首先调用get_yield()
函数取得出入参数,然后再调用yield_with()
函数返回结果。下面的例子是返回所有历史传入参数的和。
|
let mut g = Gn::new_scoped(|mut s| { let mut sum = 0; loop { let i = s.get_yield().unwrap(); sum += i; s.yield_with(sum); } }); let mut sum = 0; for i in 0..10 { sum = g.send(i); } assert_eq!(sum, 45); // g got dropped |
generator的取消
在上一个例子中创建的generator永远处于循环当中,如果不析构它或是显式的取消它,则在函数中已经分配的资源就得不到释放。generator库提供了cancel()
函数用来取消一个generator,从而可以顺利的释放其资源。同样的在generator的析构函数当中,如果判断出当前generator没有完成,则会默认调用它的cancel()
函数。因此上面的例子在结束时会自动调用cancel()
函数。
显示调用cancel()
函数的例子。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
|
let mut g = Gn::new_scoped(|mut s| { let mut sum = 0; loop { let i = s.get_yield().unwrap(); sum += i; s.yield_with(sum); } }); let mut sum = 0; for i in 0..10 { sum = g.send(i); } assert_eq!(sum, 45); assert_eq!(g.is_done(), false); unsafe { g.cancel() }; assert_eq!(g.is_done(), true); |
generator的特性
利用generator进行编程直观简单,在如何更好的使用generator上,应该了解以下几个方面:
generator是特殊的函数
generator是拥有多个返回点的函数,另一方面普通函数是只有一个返回点的generator,所以也可以说普通函数是特殊的generator。实际上通过闭包(closure)我们可以很容易的将任意的函数调用转化为generator调用。在上面xrange
的例子中我们已经见到了。
|
fn xrange(start: u32, end: u32) -> u32 { for i in start..end { yield_::<(), _>(i); } done!(); } let g1 = Gn::new(|| xrange(0, 10)); for i in g1 { println!("i={}", i); } |
generator当中一般都会出现yield
调用。generator库中的所有yield
调用都允许出现在任何位置上,甚至是子函数的内部。实际上在运行时我们会做一定的检查,如果判断出当前是在generator的运行期间,yield
调用回会正常执行,否则就会抛出异常。
以下的yield
调用不在generator当中,所以会出错
|
// this will trigger a panic because we can't yield from a non-generator context xrange(0, 10); |
以下的yield
调用出现在子函数里,可以正常运行
|
fn another_wrap() -> u32 { xrange(10, 20) } let g2 = Gn::new(|| another_wrap(0, 10)); for i in g2 { println!("i={}", i); } |
generator是特殊的结构体
generator可以返回自身栈内部的数据,只要generator不是处于完成状态。generator拥有自己独立的栈,在运行期间栈上的数据是一直存在的,因而对其数据的引用也是有效的。当运行完return
指令后,或是被取消后,它的栈会被销毁,而栈上的数据也会随之消失。由于这些数据保存在独立的栈上,这和普通的结构实例非常类似,它们都拥有属于自己的数据。只不过generator栈上的数据是融入到代码中的,并不需要定义特殊的结构。事实上只要generator拥有相同类型的输入输出参数,它们可以看做是相同类型的实例。
以下代码中,generator返回了内部的一块地址,这是安全的,缺点是必须使用unsafe
以绕过rust的生命周期检查。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
|
let mut g = Gn::new_scoped(|mut s| { // setup something let mut x: u32 = 10; s.yield_with(unsafe { ::std::mem::transmute(&mut x) }); // after use the internal resource assert!(x == 5); done!(); }); { // keep the ref in a valid scope // use the resource setup from generator let a: &mut u32 = g.next().unwrap(); assert!(*a == 10); *a = 5; } // finish the generator g.next(); assert!(g.is_done()); |
generator是自动状态机
generator本身也是一个自动状态机。栈完整的记录了它的内部状态,下次的执行又会从上次留下的状态开始。
下面的例子是一个简单的CD player
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54
|
extern crate generator; use generator::*; #[derive(Debug)] enum Action { Play(&'static str), Stop, } #[derive(Debug, Clone, Copy, PartialEq)] enum State { Playing, Stopped, } use Action::*; use State::*; fn main() { let mut cd_player = Gn::new_scoped(|mut s| { let mut state = Stopped; loop { match s.get_yield() { Some(Play(s)) => { if state == Stopped { println!("I'm playing {}", s); state = Playing; } else { println!("should first stop"); } } Some(Stop) => { if state == Playing { println!("I'm stopped"); state = Stopped; } else { println!("I'm already stopped"); } } a => { println!("invalid action: {:?}", a); } } s.yield_with(state); } }); cd_player.send(Play("hello world")); cd_player.send(Play("hello another day")); cd_player.send(Stop); cd_player.send(Stop); cd_player.send(Play("hello another day")); } |
上面的例子会输出
|
I'm playing hello world should first stop I'm stopped I'm already stopped I'm playing hello another day |
generator的应用
generator是一种非常有用的编程工具,以下列举了generator的几个应用方面。
Iterator
generator最常用的场景就是随意的创建Iterator。这类generator没有指定输入参数。
以下的例子会输出一个fib数列:
|
let fib = Gn::new_scoped(|mut s| { let (mut a, mut b) = (0, 1); while b < 200 { std::mem::swap(&mut a, &mut b); b = a + b; s.yield_with(b); } done!(); }); for i in fib { println!("{}", i); } |
pipe
generator可以处理一个序列,将generator作为一个处理单元然后串接起来。
以下的例子先求元素的平方,再求元素的平方和
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
|
#![feature(conservative_impl_trait)] #[macro_use] extern crate generator; use generator::*; fn main() { fn square<'a, T: Iterator<Item = u32> + 'a>(input: T) -> impl Iterator<Item = u32> + 'a { Gn::new_scoped(|mut s| { for i in input { s.yield_with(i * i); } done!(); }) } fn sum<'a, T: Iterator<Item = u32> + 'a>(input: T) -> impl Iterator<Item = u32> + 'a { Gn::new_scoped(|mut s| { let mut acc = 0; for i in input { acc += i; s.yield_(acc); } done!(); }) } for i in sum(square(0..10)) { println!("i = {:?}", i); } } |
解递归
TODO:
实现协程
generator是实现协程的基础,详见《generator与coroutine的设计与实现》一文