View mode: basic / threaded / horizontal-split · Log in · Help
January 15, 2013
Internal and external iteration, fibers
The author of the experimental language Magpie is very 
intelligent (in past I have read a very nice blog post about the 
unusual bootstrapped type system of Magpie). Here he nicely 
discusses well known things:

http://journal.stuffwithstuff.com/2013/01/13/iteration-inside-and-out/

Reddit thread:
http://www.reddit.com/r/programming/comments/16ja3f/iteration_inside_and_out/

A person on Reddit ("munificent", I think the blog post author 
himself) says that Magpie uses fibers to solve that dilemma, to 
be seen in a successive post.

In D the Range static protocol of iteration is external and 
opApply is internal. Some persons have suggested to use fibers in 
D to introduce a very handy "yield" syntax for internal iteration.

I think similarly short but clear article, about D Ranges and 
opApply should be added in the articles 
(http://dlang.org/articles.html ) section of the D site.

Bye,
bearophile
January 15, 2013
Re: Internal and external iteration, fibers
On Jan 15, 2013, at 4:52 AM, bearophile <bearophileHUGS@lycos.com> wrote:

> The author of the experimental language Magpie is very intelligent (in past I have read a very nice blog post about the unusual bootstrapped type system of Magpie). Here he nicely discusses well known things:
> 
> http://journal.stuffwithstuff.com/2013/01/13/iteration-inside-and-out/
> 
> Reddit thread:
> http://www.reddit.com/r/programming/comments/16ja3f/iteration_inside_and_out/
> 
> A person on Reddit ("munificent", I think the blog post author himself) says that Magpie uses fibers to solve that dilemma, to be seen in a successive post.
> 
> In D the Range static protocol of iteration is external and opApply is internal. Some persons have suggested to use fibers in D to introduce a very handy "yield" syntax for internal iteration.
> 
> I think similarly short but clear article, about D Ranges and opApply should be added in the articles (http://dlang.org/articles.html ) section of the D site.

Maybe someone could crib from Mikola's talk:

http://vimeo.com/1873969
January 18, 2013
Re: Internal and external iteration, fibers
On Tue, 15 Jan 2013 13:52:10 +0100
"bearophile" <bearophileHUGS@lycos.com> wrote:
> 
> In D the Range static protocol of iteration is external and 
> opApply is internal. Some persons have suggested to use fibers in 
> D to introduce a very handy "yield" syntax for internal iteration.
> 

D has problems in this area, there's at least three ways to do it and
yet all of them have major downsides:

opApply: The result is NOT usable as a range; it's strictly
foreach-only. Also: Unintuitive function signature, "yield" must become
"mixin(yield...)", and you need to create a dummy struct for it to sit
in.

Fibers: Too much performance overhead to be a general solution. Only
good for, as an example, heavily I/O-bound stuff.

Custom Input Range: Technically amounts to a co-routine, but is created
using an awkward event-loop style. The event-loop style is
necessary for Bidirectional/Random-access/etc ranges to be possible, but
this is an artificial constraint for input (and maybe even forward)
ranges.

Then there's C/C++ which has libs that offer what are known as
"stackless fibers". These utilize the preprocessor, along with switch
and goto, to accomplish the same thing that (AIUI) C# does for its
coroutines: It lets the user write a normal coroutine, with a normal
yield, which then gets trivially rewritten behind-the-scenes into an
event loop (with NO actual fibers involved). I'm not sure to what
extent this would be possible in D. If it is, the lack of preprocessor
would probably make it much less nice-looking to use than the C/C++/C#
versions. (Not that I'd want a preprocessor.)

So what D really, REALLY needs (this is one of the top things on my
wish list for a hypothetical D3) is real coroutine syntax which, much
like C#'s coroutines and C/C++'s stackless fibers, gets trivially
rewritten behind-the-scenes into a switch-based event loop, BUT this
coroutine would actually count as an input range.

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.


> I think similarly short but clear article, about D Ranges and 
> opApply should be added in the articles 
> (http://dlang.org/articles.html ) section of the D site.
> 
> Bye,
> bearophile
January 19, 2013
Re: Internal and external iteration, fibers
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)
January 19, 2013
Re: Internal and external iteration, fibers
On Friday, 18 January 2013 at 17:59:36 UTC, Nick Sabalausky wrote:
> Then there's C/C++ which has libs that offer what are known as
> "stackless fibers". These utilize the preprocessor, along with 
> switch
> and goto, to accomplish the same thing that (AIUI) C# does for 
> its
> coroutines: It lets the user write a normal coroutine, with a 
> normal
> yield, which then gets trivially rewritten behind-the-scenes 
> into an
> event loop (with NO actual fibers involved). I'm not sure to 
> what
> extent this would be possible in D. If it is, the lack of 
> preprocessor
> would probably make it much less nice-looking to use than the 
> C/C++/C#
> versions. (Not that I'd want a preprocessor.)

Is this also known as protothreads?

http://dunkels.com/adam/pt/
January 19, 2013
Re: Internal and external iteration, fibers
On Sat, 19 Jan 2013 09:45:25 +0100
"qznc" <qznc@go.to> wrote:

> On Friday, 18 January 2013 at 17:59:36 UTC, Nick Sabalausky wrote:
> > Then there's C/C++ which has libs that offer what are known as
> > "stackless fibers". These utilize the preprocessor, along with 
> > switch
> > and goto, to accomplish the same thing that (AIUI) C# does for 
> > its
> > coroutines: It lets the user write a normal coroutine, with a 
> > normal
> > yield, which then gets trivially rewritten behind-the-scenes 
> > into an
> > event loop (with NO actual fibers involved). I'm not sure to 
> > what
> > extent this would be possible in D. If it is, the lack of 
> > preprocessor
> > would probably make it much less nice-looking to use than the 
> > C/C++/C#
> > versions. (Not that I'd want a preprocessor.)
> 
> Is this also known as protothreads?
> 
> http://dunkels.com/adam/pt/

Yea. In fact, that's the exact same lib I've used.
January 20, 2013
Re: Internal and external iteration, fibers
On 01/19/2013 10:46 PM, Nick Sabalausky wrote:
> On Sat, 19 Jan 2013 09:45:25 +0100
> "qznc" <qznc@go.to> wrote:
>
>> On Friday, 18 January 2013 at 17:59:36 UTC, Nick Sabalausky wrote:
>>> Then there's C/C++ which has libs that offer what are known as
>>> "stackless fibers". These utilize the preprocessor, along with
>>> switch
>>> and goto, to accomplish the same thing that (AIUI) C# does for
>>> its
>>> coroutines: It lets the user write a normal coroutine, with a
>>> normal
>>> yield, which then gets trivially rewritten behind-the-scenes
>>> into an
>>> event loop (with NO actual fibers involved). I'm not sure to
>>> what
>>> extent this would be possible in D. If it is, the lack of
>>> preprocessor
>>> would probably make it much less nice-looking to use than the
>>> C/C++/C#
>>> versions. (Not that I'd want a preprocessor.)
>>
>> Is this also known as protothreads?
>>
>> http://dunkels.com/adam/pt/
>
> Yea. In fact, that's the exact same lib I've used.
>

This can be implemented a lot better looking in D. (My quick hack 
already looks better.) But I think we should first build a 
general-purpose DSEL library.
January 20, 2013
Re: Internal and external iteration, fibers
On Sun, Jan 20, 2013 at 3:45 AM, Timon Gehr <timon.gehr@gmx.ch> wrote:

> But I think we should first build a general-purpose DSEL library.

Almost there. I almost have macros, even. But the generated parser is
still quite slow...
January 20, 2013
Re: Internal and external iteration, fibers
On Sunday, 20 January 2013 at 02:45:01 UTC, Timon Gehr wrote:
> On 01/19/2013 10:46 PM, Nick Sabalausky wrote:
>> On Sat, 19 Jan 2013 09:45:25 +0100
>> "qznc" <qznc@go.to> wrote:
>>
>>> On Friday, 18 January 2013 at 17:59:36 UTC, Nick Sabalausky 
>>> wrote:
>>>> Then there's C/C++ which has libs that offer what are known 
>>>> as
>>>> "stackless fibers". These utilize the preprocessor, along 
>>>> with
>>>> switch
>>>> and goto, to accomplish the same thing that (AIUI) C# does 
>>>> for
>>>> its
>>>> coroutines: It lets the user write a normal coroutine, with a
>>>> normal
>>>> yield, which then gets trivially rewritten behind-the-scenes
>>>> into an
>>>> event loop (with NO actual fibers involved). I'm not sure to
>>>> what
>>>> extent this would be possible in D. If it is, the lack of
>>>> preprocessor
>>>> would probably make it much less nice-looking to use than the
>>>> C/C++/C#
>>>> versions. (Not that I'd want a preprocessor.)
>>>
>>> Is this also known as protothreads?
>>>
>>> http://dunkels.com/adam/pt/
>>
>> Yea. In fact, that's the exact same lib I've used.
>>
>
> This can be implemented a lot better looking in D. (My quick 
> hack already looks better.) But I think we should first build a 
> general-purpose DSEL library.

DSEL ?
January 20, 2013
Re: Internal and external iteration, fibers
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);
  }
}
« First   ‹ Prev
1 2 3 4 5
Top | Discussion index | About this forum | D home