tech – Xudong Huang's Blog

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类型的定义如下：

1 2	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));

});

// 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的输出连接起来

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()函数的例子。

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的生命周期检查。

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

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(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作为一个处理单元然后串接起来。
以下的例子先求元素的平方，再求元素的平方和

#![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的设计与实现》一文

Category: tech

Don’t visit thread local storage in corountine context

generator

generator introduction

generator的创建

generator的调用

generator的返回

generator的取消

generator的特性

generator是特殊的函数

generator是特殊的结构体

generator是自动状态机

generator的应用

Iterator

pipe

解递归

实现协程