Jump to page: 1 26  
Page
Thread overview
Internal and external iteration, fibers
Jan 15, 2013
bearophile
Jan 15, 2013
Sean Kelly
Jan 18, 2013
Nick Sabalausky
Jan 19, 2013
Timon Gehr
Jan 20, 2013
Artur Skawina
Jan 19, 2013
qznc
Jan 19, 2013
Nick Sabalausky
Jan 20, 2013
Timon Gehr
Jan 20, 2013
Philippe Sigaud
Jan 20, 2013
deadalnix
Jan 20, 2013
Philippe Sigaud
Jan 20, 2013
Nick Sabalausky
Jan 21, 2013
deadalnix
Jan 21, 2013
Nick Sabalausky
Jan 21, 2013
deadalnix
Jan 21, 2013
Timon Gehr
Jan 21, 2013
deadalnix
Jan 21, 2013
Nick Sabalausky
Jan 21, 2013
Jacob Carlborg
Jan 21, 2013
Rob T
Jan 22, 2013
deadalnix
Jan 22, 2013
Daniel Murphy
Jan 22, 2013
Daniel Murphy
Jan 22, 2013
Jacob Carlborg
Jan 22, 2013
Daniel Murphy
Jan 22, 2013
Jacob Carlborg
Jan 22, 2013
Philippe Sigaud
Jan 22, 2013
deadalnix
Jan 22, 2013
Max Samukha
Jan 22, 2013
deadalnix
Jan 23, 2013
Jacob Carlborg
Jan 23, 2013
deadalnix
Jan 23, 2013
H. S. Teoh
Jan 23, 2013
John Colvin
Jan 23, 2013
Russel Winder
Jan 23, 2013
Russel Winder
Jan 24, 2013
Araq
Jan 24, 2013
Jacob Carlborg
Jan 24, 2013
Rob T
Jan 23, 2013
Jacob Carlborg
Jan 24, 2013
deadalnix
Jan 24, 2013
Jacob Carlborg
Jan 24, 2013
David Nadlinger
Jan 24, 2013
deadalnix
Jan 24, 2013
Jacob Carlborg
Jan 22, 2013
H. S. Teoh
Jan 22, 2013
Timon Gehr
Jan 21, 2013
Rob T
Jan 21, 2013
Nick Sabalausky
Jan 21, 2013
Rob T
Jan 21, 2013
Nick Sabalausky
Jan 22, 2013
deadalnix
January 15, 2013
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
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
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
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
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
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
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
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
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
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 6