www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - yield iteration

reply "anonymous" <anonymous example.com> writes:
A subthread of the "Impressed" thread revolved around D's lack of 
a yield mechanism for iteration.
Nick Sabalausky mentioned his earlier attempt to create a library 
based yield which unfortunately was too slow to compete with 
explicit opApply/ranges [1].

I took a shot at it. It's fast. The resulting code is reasonably 
pretty. But it doesn't provide a range interface, just opApply.

---
module yielder;

import core.thread;

/**
	Examples:
	---
	import yielder;
	import std.stdio;
	
	auto y = new class Yielder!int {
		final void yielding() {
			yield(0);
			yield(13);
			yield(42);
		}
	};
	
	foreach(x; y) {
		writeln(x);
	}
	---
*/
class Yielder(E) {
	abstract void yielding();
	
	this() {
		this.fiber = new Fiber(&yielding);
	}
	
	private {
		Fiber fiber;
		int result;
		int delegate(ref E) callback;
	}
	
	final int opApply(int delegate(ref E) cb) {
		callback = cb;
		result = 0;
		fiber.reset();
		fiber.call();
		return result;
	}
	
	final void yield(ref E value) {
		result = callback(value);
		if(result != 0) {
			Fiber.yield();
		}
	}
	final void yield(E value) {
		yield(value);
	}
}
---

[1] 
https://semitwist.com/articles/article/view/combine-coroutines-and-input-ranges-for-dead-simple-d-iteration
Jul 29 2012
next sibling parent reply "bearophile" <bearophileHUGS lycos.com> writes:
anonymous:

 A subthread of the "Impressed" thread revolved around D's lack 
 of a yield mechanism for iteration.

The yield as in Python is so useful and handy, and I miss it often in D. This is an example of Inverse Gray iterator (Sloane series A006068) Python2 code from: http://code.activestate.com/recipes/221457/ def A006068(): yield 0 for x in A006068(): if x & 1: yield 2 * x + 1 yield 2 * x else: if x: yield 2 * x yield 2 * x + 1 Turning that in D code that uses opApply is not hard, but the code inflates 3X, and you can't use most std.algorithm on it. I have discussed the situation a little here: http://d.puremagic.com/issues/show_bug.cgi?id=5660 Bye, bearophile
Jul 29 2012
parent reply travert phare.normalesup.org (Christophe Travert) writes:
"bearophile" , dans le message (digitalmars.D:173647), a écrit :
 Turning that in D code that uses opApply is not hard, but the 
 code inflates 3X, and you can't use most std.algorithm on it.

I believe most std.algorithm that work on input range could be made to work with opApply, or opApply-like delegates. It just wouldn't be particularly efficient unless agressive inlining is used. For example, filter could work like this for opApply-like delegates: template filter(pred) { auto filter(T)(int delegate(int delegate(ref T)) apply) { return (int delegate(ref T) dg) { return apply( (ref T t) { return pred(t)? dg(t): 1; }); } } } -- Christophe
Jul 31 2012
parent travert phare.normalesup.org (Christophe Travert) writes:
Christophe Travert, dans le message (digitalmars.D:173787), a écrit :
 "bearophile" , dans le message (digitalmars.D:173647), a écrit :
 Turning that in D code that uses opApply is not hard, but the 
 code inflates 3X, and you can't use most std.algorithm on it.

I believe most std.algorithm that work on input range could be made to work with opApply, or opApply-like delegates. It just wouldn't be particularly efficient unless agressive inlining is used. For example, filter could work like this for opApply-like delegates: template filter(pred) { auto filter(T)(int delegate(int delegate(ref T)) apply) { return (int delegate(ref T) dg) { return apply( (ref T t) { return pred(t)? dg(t): 1; });

     }
   }
 }
 
 -- 
 Christophe

Jul 31 2012
prev sibling next sibling parent "Tobias Pankrath" <tobias pankrath.net> writes:
 This is an example of Inverse Gray iterator (Sloane series 
 A006068) Python2 code from:
 http://code.activestate.com/recipes/221457/

 def A006068():
     yield 0
     for x in A006068():
         if x & 1:
             yield 2 * x + 1
             yield 2 * x
         else:
             if x:
                 yield 2 * x
             yield 2 * x + 1

Does this spawn linear many generators?
Jul 29 2012
prev sibling next sibling parent reply Timon Gehr <timon.gehr gmx.ch> writes:
Ideally it would look like this:

struct Map(alias fun, R){
     R range;
     mixin YieldInputRange!q{
         for(; !range.empty; range.popFront())
             yield fun(range.front);
     }
     static if(is(typeof(range.save)))  property auto save(){
         return Map!(fun, R)(range.save);
     }
     ...
}

Or as a built-in:

struct Map(alias fun, R){
     R range;
     yield {
         for(; !range.empty; range.popFront())
             yield fun(x);
     }
     static if(is(typeof(range.save)))  property auto save(){
         return Map!(fun, R)(range.save);
     }
     ...
}
Jul 29 2012
parent Timon Gehr <timon.gehr gmx.ch> writes:
On 07/29/2012 04:48 PM, Timon Gehr wrote:
 Ideally it would look like this:

 struct Map(alias fun, R){
      R range;
      mixin YieldInputRange!q{
          for(; !range.empty; range.popFront())
              yield fun(range.front);
      }
      static if(is(typeof(range.save)))  property auto save(){
          return Map!(fun, R)(range.save);
      }
      ...
 }

 Or as a built-in:

 struct Map(alias fun, R){
      R range;
      yield {
          for(; !range.empty; range.popFront())
              yield fun(x);

      }
      static if(is(typeof(range.save)))  property auto save(){
          return Map!(fun, R)(range.save);
      }
      ...
 }

Jul 29 2012
prev sibling parent "bearophile" <bearophileHUGS lycos.com> writes:
Tobias Pankrath:

 Does this spawn linear many generators?

I have written this little test code, Python2.6+: count = 0 def A006068(): global count count += 1 yield 0 for x in A006068(): if x & 1: yield 2 * x + 1 yield 2 * x else: if x: yield 2 * x yield 2 * x + 1 from itertools import islice def main(): global count for p in xrange(15): n = 2 ** p count = 0 print sum(1 for _ in islice(A006068(), 0, n)), count main() The output seems to show that it spawns only logarithmically: 1 1 2 2 4 3 8 4 16 5 32 6 64 7 128 8 256 9 512 10 1024 11 2048 12 4096 13 8192 14 16384 15 Bye, bearophile
Jul 29 2012