yield 实现小探

前面多次提到 yield 的实现问题,这里参考一些现有的实现进行一些探讨。第一个实现当然是基于 Duff’s device 的东西,原始的 code 见这里,一个简单的例子如下

#include "generator.h"
#include <iostream>

$generator(descent) {
   int i;
   $emit(int)
      for (i = 10; i > 0; --i)
         $yield(i);
   $stop;
};

int
main(int argc, char* argv[]) {
  descent gen;
  for(int n; gen(n);)
    std::cout << "next number is " << n << "\n" ;

  return 0;
}

其中预编译后我们的 generator 如下

struct descent : public _generator {
   int i;
   bool operator()(int& _rv) {
     switch(_line) {
     case 0:;
      for (i = 10; i > 0; --i)
         do {
           _line=15;
           _rv = (i);
           return true;
     case 15:;
         } while (0);

     }
     _line = 0;
     return false;
   }
};

这个代码段就是传说中的 Duff’s device 了。这玩意想改还是很费神的,特别如果你想弄成看起来不那么山寨的版本的话(如这个)。这里有几个地方困难,一个是不能直接 goto,因为 goto 的 label 是静态的。第二个为什么不用 boost::optional 来做,有部分原因是现在这样可以通过函数的参数推断获得模板,而如果改成没有参数,就很难推断类型了。

当然也有人搞 Java 版本的,其中一个是通过改 byte code,估计也是模拟 Duff’s device 编译后的情况,另外一个就是不是办法的办法,就是将 caller 的输出导入到一个 queue 里面,然后将其拿出来,这样做需要一个 blocking queue 通过另一个线程生成数据,而 adapter 本身只是实现了 Iterable 接口,将其对应方法 forward 到结果上的过程。

那么我们是否能看看 scala 的情况呢?

object generator {

  def descent (n:Int) = {
    for (a <- 1 to n) yield a
  }

  def main (arg:Array[String]) =
    descent (5).map (println)
}

简单起见就直接写了个 for yield,编译之后 descent 就变得有点摸不着头脑了…

 public scala.collection.immutable.IndexedSeq descent(int);
    Code:
       0: getstatic     #19                 // Field scala/Predef$.MODULE$:Lscala/Predef$;
       3: iconst_1      
       4: invokevirtual #24                 // Method scala/Predef$.intWrapper:(I)Lscala/runtime/RichInt;
       7: iload_1       
       8: invokevirtual #30                 // Method scala/runtime/RichInt.to:(I)Lscala/collection/immutable/Range$Inclusive;
      11: new           #32                 // class generator$$anonfun$descent$1
      14: dup           
      15: invokespecial #33                 // Method generator$$anonfun$descent$1."<init>":()V
      18: getstatic     #38                 // Field scala/collection/immutable/IndexedSeq$.MODULE$:Lscala/collection/immutable/IndexedSeq$;
      21: invokevirtual #42                 // Method scala/collection/immutable/IndexedSeq$.canBuildFrom:()Lscala/collection/generic/CanBuildFrom;
      24: invokeinterface #48,  3           // InterfaceMethod scala/collection/TraversableLike.map:(Lscala/Function1;Lscala/collection/generic/CanBuildFrom;)Ljava/lang/Object;
      29: checkcast     #50                 // class scala/collection/immutable/IndexedSeq
      32: areturn

似乎还有个匿名的类… 用起来容易看起来不那么容易看明白的呀… ~~><~~

——————
And his father Isaac said unto him, Come near now, and kiss me, my son.

Advertisements
yield 实现小探

一个有关“yield 实现小探”的想法

  1. guojc 说:

    scala 是编译成
    (1 to n).map( x=>x)

    临时类是给 x=>x 这个匿名函数提供closure的

    完整的for loop yield是
    collection.filterWithMap(filter,map)

    canBuildFrom的作用是用来返回一个最接近原始类型的同类型的collection

    你被scala的yield 骗了, scala的yield不能算严格意义上的corountine

    1. guojc 说:

      其实这里corountine是靠closure捕获来模拟的,区别你用recursive function搞一下你就明白了。你的c++例子也不是corountine,不过对yield来说够用了。python的generator倒是真正的corountine

发表评论

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 更改 )

Twitter picture

You are commenting using your Twitter account. Log Out / 更改 )

Facebook photo

You are commenting using your Facebook account. Log Out / 更改 )

Google+ photo

You are commenting using your Google+ account. Log Out / 更改 )

Connecting to %s