Thread overview | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
|
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 | ||||
---|---|---|---|---|
| ||||
Posted in reply to bearophile | 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 | ||||
---|---|---|---|---|
| ||||
Posted in reply to bearophile | 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 | ||||
---|---|---|---|---|
| ||||
Posted in reply to Nick Sabalausky | 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 | ||||
---|---|---|---|---|
| ||||
Posted in reply to Nick Sabalausky | 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 | ||||
---|---|---|---|---|
| ||||
Posted in reply to qznc | 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 | ||||
---|---|---|---|---|
| ||||
Posted in reply to Nick Sabalausky | 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 | ||||
---|---|---|---|---|
| ||||
Posted in reply to Timon Gehr | 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 | ||||
---|---|---|---|---|
| ||||
Posted in reply to Timon Gehr | 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 | ||||
---|---|---|---|---|
| ||||
Posted in reply to Timon Gehr | 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); } } |
Copyright © 1999-2021 by the D Language Foundation