Internal and external iteration, fibers

[Artur Skawina]

On 01/19/13 03:14, Timon Gehr wrote:
> On 01/18/2013 06:59 PM, Nick Sabalausky wrote:
>> ....
>> tl;dr: D's input ranges are much more awkward to create than they
>> actually NEED to be, but the existing workarounds all have big problems.
>> ...
>>
> 
> My shot at it: http://dpaste.dzfl.pl/baa538af
> (Does not work with 2.061)

What doesn't work?

I took the examples from your code and wrote a "saner" pseudo-generator.
It doesn't need to manipulate code as strings (that's reinventing the
preprocessor), but still needs to be given the source as a string. 
Real Programmers don't use closures, so there's no real alternative.
And the yield syntax is at least as unnatural as the opApply one that
Nick was complaining about.
But it's already usable, and a good starting point to figure out the
missing sugar. Well, after ignoring all the compiler-problem workarounds
in there. After writing this, I'm not touching a D compiler for a while...
At least the result is as efficient as it gets (gdc has no problem
optimizing simple generators away completely) which was the main goal,
and likely wouldn't have been possible w/ closures. Maybe someone can
figure out a saner 'yield' implementation - one which doesn't require a
symbol.

Code below.

artur


// Generator by Artur; Examples borrowed from Timon Gehr.

auto iota(T)(T start, T end) {
   struct State { T start, end, i; }; // An anon struct as template parm would have been better,
                                      // but until D supports that, this is better than a mixin.
   return Generator!(State, q{
                        for (i=start; i<end; ++i)
                           mixin(yield!(state.i));
                     })
                     (start, end);
}

auto map(alias F, T)(T src) {
   struct State { T r; alias F MF; };
   return Generator!(State, q{
                        for(; !r.empty; r.popFront()) {
                            auto y = MF(r.front);
                            mixin(yield!y);
                        }
                     })
                     (src);
}

auto take(T, N)(T src, N num) {
   struct State { T r; N n; };
   return Generator!(State, q{
                        while(n-- && !r.empty) {
                            auto y = r.front;
                            mixin(yield!y);
                            r.popFront();
                        }
                     })
                     (src, num);
}

auto cprod(A, B)(A a, B b) {
   struct State { A a; B b, t; import std.typecons : q = tuple; };
   return Generator!(State, q{
                        for ( ; !a.empty; a.popFront())
                           for (t=b.save; !t.empty; t.popFront()) {
                              auto r = q(a.front, t.front);
                              mixin(yield!r);
                           }
                     })
                     (a, b);
}

struct Tree(T) {
   Tree* l, r; T v;
   this(T a) { v = a; }
   this(Tree* a, T b, Tree* c) { l = a; v = b; r = c; }
}
Tree!T* tree(T)(T a = T.init) { return new Tree!T(a); }
Tree!T* tree(T)(Tree!T* a, T b, Tree!T* c=null) { return new Tree!T(a, b, c); }

struct InOrder(T) {
   struct State { Tree!T* root; InOrder* subtree; };
   mixin GeneratorT!(State, q{
                        if (root.l)
                           static if (typeof(subtree).tupleof.length) { // Naughty compiler!
                              for(subtree = new InOrder(root.l); !subtree.empty; subtree.popFront() ) {
                                 auto r = subtree.front;
                                 mixin(yield!r);
                              }
                           }
                        
                        auto r = root.v;
                        mixin(yield!(r, 2));
                        
                        if (root.r)
                           static if (typeof(subtree).tupleof.length) { // Ditto. Hrm.
                              if (!subtree)
                                 subtree = new InOrder(root.r);
                              else {
                                 subtree.reset();
                                 subtree.root = root.r;
                              }
                              for(; !subtree.empty; subtree.popFront() ) {
                                 auto r = subtree.front;
                                 mixin(yield!(r, 3));
                              }
                           }

                        if (subtree) { delete subtree; subtree = null; }
                     });
   this(A...)(A a) { setup(a); }
}

InOrder!T inorder(T)(Tree!T* tree) { return InOrder!T(tree); }

void main() {
   static import std.conv;
   writeln(take(map!(std.conv.to!string)(iota(42, 2_000_000_000)), 10));
   writeln(cprod([1,2,3], [1L,2]));
   writeln(inorder(tree(tree(tree!int(), 1, tree(3)), 12, tree(tree(2), 3, tree(2)))));
}

// Generator implementation:

template yield(alias S, int N=1) {  // Not exactly rvalue friendly by nature.
   // More than one 'yield' inside a function requires that all of them
   // (but one) are manually numbered. The compiler will catch any duplicates.
   enum string yield = "{"
      " this.lastYield = " ~ N.stringof ~ ";"
      " return " ~ S.stringof ~ ";"
      " case " ~ N.stringof ~ ": {} }\n";
}

import std.array;

struct Generator(STATE, string CODE) { mixin GeneratorT!(STATE,CODE); }

mixin template GeneratorT(STATE, string CODE) {
   alias typeof(Hack!STATE.RetTypeFunc!CODE()) ET;

   ET elem;

   int lastYield; // 0=Initial, -1=Empty, >0=yield#.
   void reset() { lastYield = 0; }
   
   bool empty() @property { if (!lastYield) elem = f(); return lastYield<0; }
   auto front() @property { if (!lastYield) elem = f(); if (lastYield>=0) return elem; assert(0); }
   void popFront() { elem = f(); }
   
   STATE state;
   alias state this;
   this(A...)(A a) { setup(a); }
   void setup(A...)(A a) { state.tupleof[0..A.length] = a; }
   
   ET f() {
      switch (lastYield) {
      default:
         mixin(CODE);
      }
      
      lastYield = -1;
      return typeof(return).init;
   }
}

// This struct is only used to deduce the type for Generator's 'front',
// The more obvious ways to do that fail because of either forward ref errors, or ICEs.
struct Hack(STATE) {
   int lastYield;
  
   STATE state;
   alias state this;
   auto RetTypeFunc(string CODE)() {
      switch (lastYield) {
      default:
         mixin(CODE);
      }
      assert(0);
   }
}