www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Internal and external iteration, fibers

reply "bearophile" <bearophileHUGS lycos.com> writes:
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
Jan 15 2013
next sibling parent Sean Kelly <sean invisibleduck.org> writes:
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:

=20
 http://journal.stuffwithstuff.com/2013/01/13/iteration-inside-and-out/
=20
 Reddit thread:
 =


http://www.reddit.com/r/programming/comments/16ja3f/iteration_inside_and_o=
ut/

=20
 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.

=20
 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.

=20
 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=
Jan 15 2013
prev sibling parent reply Nick Sabalausky <SeeWebsiteToContactMe semitwist.com> writes:
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

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

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

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
Jan 18 2013
next sibling parent reply Timon Gehr <timon.gehr gmx.ch> writes:
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)
Jan 18 2013
parent Artur Skawina <art.08.09 gmail.com> writes:
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;


   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);
   }
}
Jan 20 2013
prev sibling next sibling parent reply "qznc" <qznc go.to> writes:
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

 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 

 versions. (Not that I'd want a preprocessor.)


Is this also known as protothreads?

http://dunkels.com/adam/pt/
Jan 19 2013
parent reply Nick Sabalausky <SeeWebsiteToContactMe semitwist.com> writes:
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

 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 

 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.
Jan 19 2013
parent reply Timon Gehr <timon.gehr gmx.ch> writes:
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

 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

 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.
Jan 19 2013
next sibling parent Philippe Sigaud <philippe.sigaud gmail.com> writes:
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...
Jan 20 2013
prev sibling next sibling parent reply "deadalnix" <deadalnix gmail.com> writes:
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

 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

 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 ?
Jan 20 2013
parent Philippe Sigaud <philippe.sigaud gmail.com> writes:
On Sun, Jan 20, 2013 at 5:27 PM, deadalnix <deadalnix gmail.com> wrote:


 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 ?


Domain-Specific Embedded Language, I guess.

Timon is just making a distinction between internal DSL (hence DSEL),
that you 'embed' in your code and external DSL (like build files...)
that are, well, in external files.
Jan 20 2013
prev sibling parent reply Nick Sabalausky <SeeWebsiteToContactMe semitwist.com> writes:
On Sun, 20 Jan 2013 03:45:00 +0100
Timon Gehr <timon.gehr gmx.ch> 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

 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

 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.


If we need to resort to using D-as-a-DSL-inside-D to get decent
coroutines, then that just further proves the need for a real coroutine
support in the language.
Jan 20 2013
parent reply "deadalnix" <deadalnix gmail.com> writes:
On Sunday, 20 January 2013 at 20:19:56 UTC, Nick Sabalausky wrote:

 If we need to resort to using D-as-a-DSL-inside-D to get decent
 coroutines, then that just further proves the need for a real 
 coroutine
 support in the language.


A good part of the job is done with Fibers. The biggest problem I 
see is module constructor and switching from TLS to fiber local 
storage.
Jan 20 2013
parent reply Nick Sabalausky <SeeWebsiteToContactMe semitwist.com> writes:
On Mon, 21 Jan 2013 03:27:49 +0100
"deadalnix" <deadalnix gmail.com> wrote:


 On Sunday, 20 January 2013 at 20:19:56 UTC, Nick Sabalausky wrote:

 If we need to resort to using D-as-a-DSL-inside-D to get decent
 coroutines, then that just further proves the need for a real 
 coroutine
 support in the language.


 
 A good part of the job is done with Fibers. The biggest problem I 
 see is module constructor and switching from TLS to fiber local 
 storage.


That's no good for general-purpose, then. Fibers may be light-weight
compared to threads, but (as I learned when *I* made a fiber-based
solution last year) fibers still have way to much overhead to be a
*general-purpose* approach the the matter. For more info, see jerro's
posts here:

http://forum.dlang.org/thread/jno6o5$qtb$1 digitalmars.com

So like I already said a few posts back, *ALL* the currently-possible
solutions in D have issues:

opApply: Not a range; awkward to use

Manually-Created Input Range: Event-loop-style instead of
procedural. Yuck.

Real Fibers: Too slow to be general-purpose.

Stackless "fibers": Requires gross syntactical contortions much like
opApply does.
Jan 21 2013
parent reply "deadalnix" <deadalnix gmail.com> writes:
On Monday, 21 January 2013 at 08:27:28 UTC, Nick Sabalausky wrote:

 Stackless "fibers": Requires gross syntactical contortions much 
 like
 opApply does.


Can you explain more what a stackless fiber is ? From the linked 
posted above I did really understood, as the example code clearly 
call functions, which require stack.
Jan 21 2013
parent reply Timon Gehr <timon.gehr gmx.ch> writes:
On 01/21/2013 10:08 AM, deadalnix wrote:

 On Monday, 21 January 2013 at 08:27:28 UTC, Nick Sabalausky wrote:

 Stackless "fibers": Requires gross syntactical contortions much like
 opApply does.


 Can you explain more what a stackless fiber is ? From the linked posted
 above I did really understood, as the example code clearly call
 functions, which require stack.


A stackless fiber does not have the execution stack as part of its 
context. (Therefore it cannot yield from nested function calls.)
Jan 21 2013
parent reply "deadalnix" <deadalnix gmail.com> writes:
On Monday, 21 January 2013 at 09:18:34 UTC, Timon Gehr wrote:

 On 01/21/2013 10:08 AM, deadalnix wrote:

 On Monday, 21 January 2013 at 08:27:28 UTC, Nick Sabalausky 
 wrote:

 Stackless "fibers": Requires gross syntactical contortions 
 much like
 opApply does.


 Can you explain more what a stackless fiber is ? From the 
 linked posted
 above I did really understood, as the example code clearly call
 functions, which require stack.


 A stackless fiber does not have the execution stack as part of 
 its context. (Therefore it cannot yield from nested function 
 calls.)


Ho yeah, I looked at the implementation. It is mostly made of 
macro that create a function with a big switch in it.

Why can't this be done in D ? What are the major problems ?
Jan 21 2013
parent reply Nick Sabalausky <SeeWebsiteToContactMe semitwist.com> writes:
On Mon, 21 Jan 2013 11:48:58 +0100
"deadalnix" <deadalnix gmail.com> wrote:


 On Monday, 21 January 2013 at 09:18:34 UTC, Timon Gehr wrote:

 On 01/21/2013 10:08 AM, deadalnix wrote:

 On Monday, 21 January 2013 at 08:27:28 UTC, Nick Sabalausky 
 wrote:

 Stackless "fibers": Requires gross syntactical contortions 
 much like
 opApply does.


 Can you explain more what a stackless fiber is ? From the 
 linked posted
 above I did really understood, as the example code clearly call
 functions, which require stack.


 A stackless fiber does not have the execution stack as part of 
 its context. (Therefore it cannot yield from nested function 
 calls.)


 
 Ho yeah, I looked at the implementation. It is mostly made of 
 macro that create a function with a big switch in it.
 
 Why can't this be done in D ? What are the major problems ?


I don't know whether or not it can be done in D. But, if it can be
done, it would definitely require awkward syntax. Probably more awkward
than the preprocessor-based syntax of the C/C++ version. (Not that I
want a preprocessor in D.)

Maybe you could do it by sticking the whole coroutine into a string
literal that gets ripped apart and reassembled by a CTFE D parser, but
that would just be so clumsy and error-prone, and frankly far more
complex than should really be necessary, that I'd call it more of a
kludge than a solution. And really, if I have to write D code inside a
string literal to use it, that alone indicates that we're looking down
the wrong path.
Jan 21 2013
next sibling parent reply Jacob Carlborg <doob me.com> writes:
On 2013-01-21 20:00, Nick Sabalausky wrote:


 I don't know whether or not it can be done in D. But, if it can be
 done, it would definitely require awkward syntax. Probably more awkward
 than the preprocessor-based syntax of the C/C++ version. (Not that I
 want a preprocessor in D.)

 Maybe you could do it by sticking the whole coroutine into a string
 literal that gets ripped apart and reassembled by a CTFE D parser, but
 that would just be so clumsy and error-prone, and frankly far more
 complex than should really be necessary, that I'd call it more of a
 kludge than a solution. And really, if I have to write D code inside a
 string literal to use it, that alone indicates that we're looking down
 the wrong path.


I know people don't like it but I have to say, this seems it could be a 
job for AST macros.

-- 
/Jacob Carlborg
Jan 21 2013
next sibling parent "Rob T" <alanb ucora.com> writes:
On Monday, 21 January 2013 at 19:23:19 UTC, Jacob Carlborg wrote:

 I know people don't like it but I have to say, this seems it 
 could be a job for AST macros.


It would be just as ugly as C macros. Well maybe not as ugly, but 
D should have direct support for co-routines, it's an important 
feature with plenty of uses.

BTW, has anyone in here has experience working with Simula? 
Co-routines as a language feature has been around for decades in 
a proven way.

--rt
Jan 21 2013
prev sibling parent reply "deadalnix" <deadalnix gmail.com> writes:
On Monday, 21 January 2013 at 19:23:19 UTC, Jacob Carlborg wrote:

 On 2013-01-21 20:00, Nick Sabalausky wrote:


 I don't know whether or not it can be done in D. But, if it 
 can be
 done, it would definitely require awkward syntax. Probably 
 more awkward
 than the preprocessor-based syntax of the C/C++ version. (Not 
 that I
 want a preprocessor in D.)

 Maybe you could do it by sticking the whole coroutine into a 
 string
 literal that gets ripped apart and reassembled by a CTFE D 
 parser, but
 that would just be so clumsy and error-prone, and frankly far 
 more
 complex than should really be necessary, that I'd call it more 
 of a
 kludge than a solution. And really, if I have to write D code 
 inside a
 string literal to use it, that alone indicates that we're 
 looking down
 the wrong path.


 I know people don't like it but I have to say, this seems it 
 could be a job for AST macros.


I was thinking the same thing, but don't wanted to bug people. 
Indeed, it is the perfect job for AST macro. I can concur now 
that you mentioned it xD
Jan 21 2013
next sibling parent "Daniel Murphy" <yebblies nospamgmail.com> writes:
"deadalnix" <deadalnix gmail.com> wrote in message 
news:zrmlbyboedaswcllzwgb forum.dlang.org...

 On Monday, 21 January 2013 at 19:23:19 UTC, Jacob Carlborg wrote:

 On 2013-01-21 20:00, Nick Sabalausky wrote:

 I know people don't like it but I have to say, this seems it could be a 
 job for AST macros.


 I was thinking the same thing, but don't wanted to bug people. Indeed, it 
 is the perfect job for AST macro. I can concur now that you mentioned it 
 xD
Jan 21 2013
prev sibling next sibling parent reply "Daniel Murphy" <yebblies nospamgmail.com> writes:
"deadalnix" <deadalnix gmail.com> wrote in message 
news:zrmlbyboedaswcllzwgb forum.dlang.org...

 On Monday, 21 January 2013 at 19:23:19 UTC, Jacob Carlborg wrote:

 On 2013-01-21 20:00, Nick Sabalausky wrote:


 I know people don't like it but I have to say, this seems it could be a 
 job for AST macros.


 I was thinking the same thing, but don't wanted to bug people. Indeed, it 
 is the perfect job for AST macro. I can concur now that you mentioned it 
 xD


AST macros are just compiler support pushed into user code/libraries. 
Exposing the AST to the user is a huge task and forces any supporting 
compiler to use a fixed AST representation.
Jan 21 2013
parent reply Jacob Carlborg <doob me.com> writes:
On 2013-01-22 04:43, Daniel Murphy wrote:


 AST macros are just compiler support pushed into user code/libraries.
 Exposing the AST to the user is a huge task and forces any supporting
 compiler to use a fixed AST representation.


Would that be so bad idea, to have a fixed AST representation? The AST 
presented for the user doesn't need to be the same as the compiler uses 
internally.

It's the same as any library function. You can easily change the 
implementation as long as the signature and behavior is the same.

-- 
/Jacob Carlborg
Jan 21 2013
parent reply "Daniel Murphy" <yebblies nospamgmail.com> writes:
"Jacob Carlborg" <doob me.com> wrote in message 
news:kdlfhr$1676$1 digitalmars.com...

 Would that be so bad idea, to have a fixed AST representation? The AST 
 presented for the user doesn't need to be the same as the compiler uses 
 internally.

 It's the same as any library function. You can easily change the 
 implementation as long as the signature and behavior is the same.

 -- 
 /Jacob Carlborg


It depends how much information is in the AST you give the user.  Just 
syntax?  Types?  Full semantic information?

Of course you can transform the internal AST to the user AST, but the more 
information the closer this gets to forcing the compiler to use the user 
AST, or support two ASTs internally.
Jan 22 2013
parent Jacob Carlborg <doob me.com> writes:
On 2013-01-22 12:00, Daniel Murphy wrote:


 It depends how much information is in the AST you give the user.  Just
 syntax?  Types?  Full semantic information?

 Of course you can transform the internal AST to the user AST, but the more
 information the closer this gets to forcing the compiler to use the user
 AST, or support two ASTs internally.


I watched a talk about AST macros in Scala. He said it was a fairly 
small change to the compiler to implement. Around 1k lines of code. The 
AST introspection was already there in the form of runtime reflection.

I don't expect it to be as easy to do in DMD. Although Don has said it 
would be pretty easy to expose the internal AST to the user.

-- 
/Jacob Carlborg
Jan 22 2013
prev sibling next sibling parent reply Philippe Sigaud <philippe.sigaud gmail.com> writes:
On Tue, Jan 22, 2013 at 2:55 AM, deadalnix <deadalnix gmail.com> wrote:

 On Monday, 21 January 2013 at 19:23:19 UTC, Jacob Carlborg wrote:



 I know people don't like it but I have to say, this seems it could be a
 job for AST macros.


 I was thinking the same thing, but don't wanted to bug people. Indeed, it is
 the perfect job for AST macro. I can concur now that you mentioned it xD


Would any of you be so kind as to propose another definition for AST
macros here ?

http://wiki.dlang.org/Commonly-Used_Acronyms
Jan 21 2013
next sibling parent "deadalnix" <deadalnix gmail.com> writes:
On Tuesday, 22 January 2013 at 05:51:16 UTC, Philippe Sigaud 
wrote:

 On Tue, Jan 22, 2013 at 2:55 AM, deadalnix 
 <deadalnix gmail.com> wrote:

 On Monday, 21 January 2013 at 19:23:19 UTC, Jacob Carlborg 
 wrote:



 I know people don't like it but I have to say, this seems it 
 could be a
 job for AST macros.


 I was thinking the same thing, but don't wanted to bug people. 
 Indeed, it is
 the perfect job for AST macro. I can concur now that you 
 mentioned it xD


 Would any of you be so kind as to propose another definition 
 for AST
 macros here ?

 http://wiki.dlang.org/Commonly-Used_Acronyms


Well, AST macro don't exists in D, so it will probably be subject 
to controversy, but let me add something here.
Jan 21 2013
prev sibling parent reply "Max Samukha" <maxsamukha gmail.com> writes:
On Tuesday, 22 January 2013 at 05:51:16 UTC, Philippe Sigaud 
wrote:

 On Tue, Jan 22, 2013 at 2:55 AM, deadalnix 
 <deadalnix gmail.com> wrote:

 On Monday, 21 January 2013 at 19:23:19 UTC, Jacob Carlborg 
 wrote:



 I know people don't like it but I have to say, this seems it 
 could be a
 job for AST macros.


 I was thinking the same thing, but don't wanted to bug people. 
 Indeed, it is
 the perfect job for AST macro. I can concur now that you 
 mentioned it xD


 Would any of you be so kind as to propose another definition 
 for AST
 macros here ?

 http://wiki.dlang.org/Commonly-Used_Acronyms


AST macros is CTFE done right :)
Jan 22 2013
next sibling parent "deadalnix" <deadalnix gmail.com> writes:
On Tuesday, 22 January 2013 at 12:14:26 UTC, Max Samukha wrote:

 On Tuesday, 22 January 2013 at 05:51:16 UTC, Philippe Sigaud 
 wrote:

 On Tue, Jan 22, 2013 at 2:55 AM, deadalnix 
 <deadalnix gmail.com> wrote:

 On Monday, 21 January 2013 at 19:23:19 UTC, Jacob Carlborg 
 wrote:



 I know people don't like it but I have to say, this seems it 
 could be a
 job for AST macros.


 I was thinking the same thing, but don't wanted to bug 
 people. Indeed, it is
 the perfect job for AST macro. I can concur now that you 
 mentioned it xD


 Would any of you be so kind as to propose another definition 
 for AST
 macros here ?

 http://wiki.dlang.org/Commonly-Used_Acronyms


 AST macros is CTFE done right :)


That is completely nonsensial.
Jan 22 2013
prev sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 1/22/13 7:14 AM, Max Samukha wrote:

 On Tuesday, 22 January 2013 at 05:51:16 UTC, Philippe Sigaud wrote:

 On Tue, Jan 22, 2013 at 2:55 AM, deadalnix <deadalnix gmail.com> wrote:

 On Monday, 21 January 2013 at 19:23:19 UTC, Jacob Carlborg wrote:



 I know people don't like it but I have to say, this seems it could be a
 job for AST macros.


 I was thinking the same thing, but don't wanted to bug people.
 Indeed, it is
 the perfect job for AST macro. I can concur now that you mentioned it xD


 Would any of you be so kind as to propose another definition for AST
 macros here ?

 http://wiki.dlang.org/Commonly-Used_Acronyms


 AST macros is CTFE done right :)


Not at all, I'd say. CTFE has a much lower cost of learning - you only 
need to know which subset of D is allowed. Maybe you meant code mixins?

Andrei
Jan 22 2013
parent reply Jacob Carlborg <doob me.com> writes:
On 2013-01-22 20:51, Andrei Alexandrescu wrote:


 Not at all, I'd say. CTFE has a much lower cost of learning - you only
 need to know which subset of D is allowed. Maybe you meant code mixins?


To be able to use AST macros one needs CTFE. One needs functions to 
manipulate the AST during compile time. As far as I understand it, in 
Scala they just create a new instance of the compiler, during 
compilation, and just like that they have access to the whole language 
during compilation.

In D it feels like a feature first need to be implemented in the regular 
compiler. Then it needs to be duplicated to be able to be used as CTFE.

Example, in Scala if you throw an exception during compile time it will 
be handled properly and generate a compile error. What happens if you do 
the same in D? It won't run the function during compile time?

Techincally you can generate an empty AST just to be able to run a bunch 
of functions during compile time. This would be no higher cost of 
learning than CTFE in D.

-- 
/Jacob Carlborg
Jan 22 2013
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 1/23/13 2:28 AM, Jacob Carlborg wrote:

 On 2013-01-22 20:51, Andrei Alexandrescu wrote:


 Not at all, I'd say. CTFE has a much lower cost of learning - you only
 need to know which subset of D is allowed. Maybe you meant code mixins?


 To be able to use AST macros one needs CTFE. One needs functions to
 manipulate the AST during compile time. As far as I understand it, in
 Scala they just create a new instance of the compiler, during
 compilation, and just like that they have access to the whole language
 during compilation.


Martin Odersky confessed to me being quite worried about the possible 
community reaction to the introduction of AST macros. I haven't kept 
close tabs to see how it's turning out.


 In D it feels like a feature first need to be implemented in the regular
 compiler. Then it needs to be duplicated to be able to be used as CTFE.

 Example, in Scala if you throw an exception during compile time it will
 be handled properly and generate a compile error. What happens if you do
 the same in D? It won't run the function during compile time?

 Techincally you can generate an empty AST just to be able to run a bunch
 of functions during compile time. This would be no higher cost of
 learning than CTFE in D.


I completely disagree. (Sorry to foul you twice.) All AST macro systems 
I've studied are considerably difficult to understand and use 
effectively. By comparison, string macros are brutal and unstructured 
but the kind of thing all programmer worth their salt can get done.


Andrei
Jan 22 2013
next sibling parent reply "deadalnix" <deadalnix gmail.com> writes:
On Wednesday, 23 January 2013 at 07:57:10 UTC, Andrei 
Alexandrescu wrote:

 Martin Odersky confessed to me being quite worried about the 
 possible community reaction to the introduction of AST macros. 
 I haven't kept close tabs to see how it's turning out.


Can he or you explain why ?


 I completely disagree. (Sorry to foul you twice.) All AST macro 
 systems I've studied are considerably difficult to understand 
 and use effectively. By comparison, string macros are brutal 
 and unstructured but the kind of thing all programmer worth 
 their salt can get done.


2 things here.

First, that is why people used to say about templates. D shows 
that this isn't a fatality.

Secondly, this is true that AST macro is probably harder to 
understand. In fact, it is not expected that most programmer use 
it (or at least not before I'm retired as a dev). I don't even 
think any experienced dev should use it on a daily basis.

However, it opens so much doors. First, no need for a custom 
compiler to test new features. Anyone can download source code 
and start using some new features. We can actually integrate 
field tested stuff in the language. Every D compiler can get the 
new feature as well.

If a feature is controversial, I can include in in my project, 
but not in D in general.

An example of such new feature is the iteration mechanism 
proposed here.

However, I do think that attribute was a key piece for such 
mechanism, and has been handled the most backward possible way. 
So clean AST macro may have been impaired here.

Anyway, I do strongly feel like we should stop adding more stuff 
now. Too much stuff is here already, some already start to 
misbehave together. It is probably time to consolidate the 
language, and keep that kind of stuff for a later version.

After all, many language live without most of the feature D have.
Jan 23 2013
parent reply "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
On Wed, Jan 23, 2013 at 09:38:01AM +0100, deadalnix wrote:
[...]

 Anyway, I do strongly feel like we should stop adding more stuff
 now. Too much stuff is here already, some already start to misbehave
 together. It is probably time to consolidate the language, and keep
 that kind of stuff for a later version.
 
 After all, many language live without most of the feature D have.


Yeah, as I said elsewhere in this forum, D tends to work wonderfully
well when features are used in isolation, but once you start combining
them, you quickly tread into unexplored territory, compiler holes, etc..
It's fun and cool to add new features, I'll agree, but it's really time
for us to focus on using what we already have and iron out all the
wrinkles so that we can have a product that we are proud of.


T

-- 
"No, John.  I want formats that are actually useful, rather than
over-featured megaliths that address all questions by piling on
ridiculous internal links in forms which are hideously over-complex." --
Simon St. Laurent on xml-dev
Jan 23 2013
parent "John Colvin" <john.loughran.colvin gmail.com> writes:
On Wednesday, 23 January 2013 at 15:36:16 UTC, H. S. Teoh wrote:

 On Wed, Jan 23, 2013 at 09:38:01AM +0100, deadalnix wrote:
 [...]

 Anyway, I do strongly feel like we should stop adding more 
 stuff
 now. Too much stuff is here already, some already start to 
 misbehave
 together. It is probably time to consolidate the language, and 
 keep
 that kind of stuff for a later version.
 
 After all, many language live without most of the feature D 
 have.


 Yeah, as I said elsewhere in this forum, D tends to work 
 wonderfully
 well when features are used in isolation, but once you start 
 combining
 them, you quickly tread into unexplored territory, compiler 
 holes, etc..
 It's fun and cool to add new features, I'll agree, but it's 
 really time
 for us to focus on using what we already have and iron out all 
 the
 wrinkles so that we can have a product that we are proud of.


 T


D is already so feature rich. As cool as all these ideas are, at 
this stage it's hardly a priority.

Also, having a high feature introduction rate with a low usage 
rate means that we lose the benefit of the practical hindsight 
that has provided so much useful information thus far (from c++, 
c, java etc.)
Jan 23 2013
prev sibling next sibling parent reply Russel Winder <russel winder.org.uk> writes:
On Wed, 2013-01-23 at 02:57 -0500, Andrei Alexandrescu wrote:
[=E2=80=A6]

 Martin Odersky confessed to me being quite worried about the possible=20
 community reaction to the introduction of AST macros. I haven't kept=20
 close tabs to see how it's turning out.


AST transforms are working wonderfully well in Groovy. This is the tool
that is allowing there to be static type checking and static compilation
of Groovy code amongst a whole load of other things.

Macros in Scala are a bit more of a mixed blessing, not because they are
not a useful tool but because of the reaction of the community.  All in
all I suspect they will be fine.

[=E2=80=A6]

 I completely disagree. (Sorry to foul you twice.) All AST macro systems=


=20

 I've studied are considerably difficult to understand and use=20
 effectively. By comparison, string macros are brutal and unstructured=20
 but the kind of thing all programmer worth their salt can get done.


There is no doubt that AST transforms in Groovy is not something the
application programmer would spend time on unless they knew what they
were doing. It isn't a trivial API. However it is straightforward once
you know ASTs.
--=20
Russel.
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D
Dr Russel Winder      t: +44 20 7585 2200   voip: sip:russel.winder ekiga.n=
et
41 Buckmaster Road    m: +44 7770 465 077   xmpp: russel winder.org.uk
London SW11 1EN, UK   w: www.russel.org.uk  skype: russel_winder
Jan 23 2013
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 1/23/13 2:08 PM, Russel Winder wrote:

 There is no doubt that AST transforms in Groovy is not something the
 application programmer would spend time on unless they knew what they
 were doing. It isn't a trivial API. However it is straightforward once
 you know ASTs.


Given the richness of today's D, I'd say AST macros are not part of the 
mythical plan.

Andrei
Jan 23 2013
parent reply Russel Winder <russel winder.org.uk> writes:
On Wed, 2013-01-23 at 15:15 -0500, Andrei Alexandrescu wrote:
[=E2=80=A6]

 Given the richness of today's D, I'd say AST macros are not part of the=


=20

 mythical plan.


Works for me.

The issue is only whether there is an idiomatic expression for a given
style. For me currently D has everything I need that C++ makes
difficult.

The difficult tension for me is JVM vs. native. On the JVM I have
Groovy, Scala, (Ceylon, Kotlin, JRuby, Jython, Clojure), even Java,
which is an interesting milieu. Natively there is  C, C++, D, Clay,
Rust, Haskell which makes for fun tensions.

The core problem is how to make D appealing to C and C++ programmers.

--=20
Russel.
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D
Dr Russel Winder      t: +44 20 7585 2200   voip: sip:russel.winder ekiga.n=
et
41 Buckmaster Road    m: +44 7770 465 077   xmpp: russel winder.org.uk
London SW11 1EN, UK   w: www.russel.org.uk  skype: russel_winder
Jan 23 2013
next sibling parent reply "Araq" <rumpf_a web.de> writes:
 The difficult tension for me is JVM vs. native. On the JVM I 
 have
 Groovy, Scala, (Ceylon, Kotlin, JRuby, Jython, Clojure), even 
 Java,
 which is an interesting milieu. Natively there is  C, C++, D, 
 Clay,
 Rust, Haskell which makes for fun tensions.


There is also Nimrod which has 'yield' and AST macros ...
Jan 23 2013
parent Jacob Carlborg <doob me.com> writes:
On 2013-01-24 01:30, Araq wrote:


 There is also Nimrod which has 'yield' and AST macros ...


And Nemerle (on .Net), which both has AST macros and allows the 
programmer to add new syntax for these macros.

-- 
/Jacob Carlborg
Jan 23 2013
prev sibling parent "Rob T" <alanb ucora.com> writes:
On Wednesday, 23 January 2013 at 21:13:12 UTC, Russel Winder 
wrote:
[...]

 The core problem is how to make D appealing to C and C++ 
 programmers.


One possibility is that once we have 100% shared library support, 
C/C++ programmers can start making use out of a growing base of 
very nice libraries written in D that are also made compatible 
(to a degree) with C/C++.

That's a potential ice breaker IMO, esp when C/C++ programmers 
discover that they will get much more functionality if they 
ditched C/C++ and used these libs with native D applications 
instead.

This method of conversion to D a relatively safe and simple 
migration path.

--rt
Jan 23 2013
prev sibling parent reply Jacob Carlborg <doob me.com> writes:
On 2013-01-23 08:57, Andrei Alexandrescu wrote:


 I completely disagree. (Sorry to foul you twice.) All AST macro systems
 I've studied are considerably difficult to understand and use
 effectively. By comparison, string macros are brutal and unstructured
 but the kind of thing all programmer worth their salt can get done.


I was talking about functions running at compile time. In D that's 
handled by an interpreter which doesn't support the full language. It 
also behaves differently from the "regular" language. Bugs occur in the 
CTFE interpreter which doesn't occur in the regular compiler.

In Scala it _is_ the regular compiler that handles both the CTFE and the 
regular code. A bug in the regular compiler will show up during CTFE as 
well.

BTW, how do you make a string mixin hygienic?

-- 
/Jacob Carlborg
Jan 23 2013
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 1/23/13 3:29 PM, Jacob Carlborg wrote:

 On 2013-01-23 08:57, Andrei Alexandrescu wrote:


 I completely disagree. (Sorry to foul you twice.) All AST macro systems
 I've studied are considerably difficult to understand and use
 effectively. By comparison, string macros are brutal and unstructured
 but the kind of thing all programmer worth their salt can get done.


 I was talking about functions running at compile time. In D that's
 handled by an interpreter which doesn't support the full language.


It's a subset. That's a better thing than _another_ language.


 It
 also behaves differently from the "regular" language.


To the smallest extent possible.


 Bugs occur in the
 CTFE interpreter which doesn't occur in the regular compiler.


Not an argument.


 In Scala it _is_ the regular compiler that handles both the CTFE and the
 regular code. A bug in the regular compiler will show up during CTFE as
 well.


Agreed this is a good thing for Scala, it takes advantage of the jit 
infrastructure.


 BTW, how do you make a string mixin hygienic?


By passing fresh names as arguments into the function creating it. We 
don't have a strong story there.


Andrei
Jan 23 2013
next sibling parent reply "deadalnix" <deadalnix gmail.com> writes:
On Wednesday, 23 January 2013 at 21:50:39 UTC, Andrei 
Alexandrescu wrote:

 In Scala it _is_ the regular compiler that handles both the 
 CTFE and the
 regular code. A bug in the regular compiler will show up 
 during CTFE as
 well.


 Agreed this is a good thing for Scala, it takes advantage of 
 the jit infrastructure.


SDC does something similar with LLVM JIT capabilities.
Jan 23 2013
parent reply Jacob Carlborg <doob me.com> writes:
On 2013-01-24 03:35, deadalnix wrote:


 SDC does something similar with LLVM JIT capabilities.


That's the correct approach.

-- 
/Jacob Carlborg
Jan 23 2013
parent reply "David Nadlinger" <see klickverbot.at> writes:
On Thursday, 24 January 2013 at 07:55:37 UTC, Jacob Carlborg 
wrote:

 On 2013-01-24 03:35, deadalnix wrote:


 SDC does something similar with LLVM JIT capabilities.


 That's the correct approach.


The question is not so much about correctness, but about 
performance.

Building an LLVM function and JIT-compiling it every time you 
need to evaluate a D expression will completely ruin your compile 
times (and I say that as an LLVM proponent). The idea itself is 
interesting for computationally heavy CTFE code, but I don't 
think it is feasible to go without lightweight code at least for 
simple »constant folding«-type applications.

David
Jan 24 2013
parent "deadalnix" <deadalnix gmail.com> writes:
On Thursday, 24 January 2013 at 13:59:43 UTC, David Nadlinger 
wrote:

 On Thursday, 24 January 2013 at 07:55:37 UTC, Jacob Carlborg 
 wrote:

 On 2013-01-24 03:35, deadalnix wrote:


 SDC does something similar with LLVM JIT capabilities.


 That's the correct approach.


 The question is not so much about correctness, but about 
 performance.

 Building an LLVM function and JIT-compiling it every time you 
 need to evaluate a D expression will completely ruin your 
 compile times (and I say that as an LLVM proponent). The idea 
 itself is interesting for computationally heavy CTFE code, but 
 I don't think it is feasible to go without lightweight code at 
 least for simple »constant folding«-type applications.


This is what SDC does currently, but yes, simple constant folding 
should avoid doing that.

But 1/ make it work and 2/ make it fast.

Current implementation permit easily to add constant folding 
later.
Jan 24 2013
prev sibling parent Jacob Carlborg <doob me.com> writes:
On 2013-01-23 22:50, Andrei Alexandrescu wrote:


 It's a subset. That's a better thing than _another_ language.


Of course. But then the CTFE and regular code is handled differently by 
the compiler it will start to become a different language, although very 
similar. I'm wondering if that is even worse.


 Not an argument.


The argument is that it's not code to have two different parts of the 
compiler handling this.


 In Scala it _is_ the regular compiler that handles both the CTFE and the
 regular code. A bug in the regular compiler will show up during CTFE as
 well.


 Agreed this is a good thing for Scala, it takes advantage of the jit
 infrastructure.


Exactly, that's what I'm trying to say.



 By passing fresh names as arguments into the function creating it. We
 don't have a strong story there.


The function cannot then generate a symbol that is only used internally 
as a helper without breaking the hygienicy (or what it's called). You 
don't want the user to pass in names for symbols it doesn't know about, 
doesn't care about and should not know about.

-- 
/Jacob Carlborg
Jan 23 2013
prev sibling parent "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
On Tue, Jan 22, 2013 at 06:51:07AM +0100, Philippe Sigaud wrote:

 On Tue, Jan 22, 2013 at 2:55 AM, deadalnix <deadalnix gmail.com> wrote:

 On Monday, 21 January 2013 at 19:23:19 UTC, Jacob Carlborg wrote:


 

 I know people don't like it but I have to say, this seems it could
 be a job for AST macros.


 I was thinking the same thing, but don't wanted to bug people.
 Indeed, it is the perfect job for AST macro. I can concur now that
 you mentioned it xD


 
 Would any of you be so kind as to propose another definition for AST
 macros here ?
 
 http://wiki.dlang.org/Commonly-Used_Acronyms


I don't think anyone has defined what "AST macros" are supposed to be
yet. There have been some vague ideas thrown about, but nothing is
concrete AFAIK.

For one thing, it's not even clear how said "AST macros" are supposed to
work, or what they're supposed to do.

Do they perform *arbitrary* transformations from some given AST subtree
into another? (Arbitrary, as in, you can implement an "in-library"
optimizer that substitutes inefficient subtrees with optimized versions,
or even a codegen that transforms AST trees into a linear form that maps
directly to IR or machine code.)

Or is it something simpler and more within our reach, something like the
C preprocessor but operating on AST subtrees instead of tokens (as in, a
macro is called with some AST tree fragments as parameters, which get
grafted into the macro body's AST at certain points)?

Or is it something else altogether, like some kind of compile-time
introspection that allows you to access and modify node attributes in
the parsed AST of the code in some way, so that you change the way it's
compiled?

Until this is pinned down, "AST macros" can virtually be *anything*. It
has been said that they can solve all kinds of problems in D, including
the halting problem, world peace, and world hunger, and can be used to
construct all manner of amazing features like writing your code for you,
implementing an oracle machine, etc..  But nobody even knows what they
are or how they're supposed to work.


T

-- 
Freedom: (n.) Man's self-given right to be enslaved by his own depravity.
Jan 21 2013
prev sibling parent Timon Gehr <timon.gehr gmx.ch> writes:
On 01/21/2013 08:00 PM, Nick Sabalausky wrote:

 On Mon, 21 Jan 2013 11:48:58 +0100
 "deadalnix" <deadalnix gmail.com> wrote:
...

 Why can't this be done in D ? What are the major problems ?


 I don't know whether or not it can be done in D. ...


Why not? I have essentially done it and posted it here.
Also, there is nothing feasible that 'cannot be done' in D, because D 
can host arbitrarily complex embedded languages.
Jan 22 2013
prev sibling parent reply "Rob T" <alanb ucora.com> writes:
On Friday, 18 January 2013 at 17:59:36 UTC, Nick Sabalausky wrote:

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


Where does the overhead come from? Is the overhead from using 
fibers the only problem for implementing coroutines?

I ask, because if except for the overhead, fibers are a good 
general solution, then it makes sense to determine if anything 
can be done to lessen the overhead before trying to implement yet 
another solution.

--rt
Jan 20 2013
parent reply Nick Sabalausky <SeeWebsiteToContactMe semitwist.com> writes:
On Mon, 21 Jan 2013 01:18:48 +0100
"Rob T" <alanb ucora.com> wrote:


 On Friday, 18 January 2013 at 17:59:36 UTC, Nick Sabalausky wrote:

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


 
 Where does the overhead come from? Is the overhead from using 
 fibers the only problem for implementing coroutines?
 


Real fibers have their own call stacks, so creating them and switching
contexts between them on every iteration can never be made as fast as a
simple for-loop or event-loop (both of which are computationally
trivial). Stackless "fibers" OTOH can do this easily since they
literally *are* trivial switch-driven event-loops under the hood, but
just written in a cleaner way.


 I ask, because if except for the overhead, fibers are a good 
 general solution, then it makes sense to determine if anything 
 can be done to lessen the overhead before trying to implement yet 
 another solution.
 


Yea, they *would* be a good general solution, and I'm sure the overhead
can be decreased, but AIUI I don't think it's even theoretically
possible for them to optimized enough to compete with any of the other
approaches as a general-purpose thing.

The other stuff can be optimized down as far as being little more than
an increment per iteration. But AIUI, using a real fiber would require
two context-switches per iteration, so I'm not sure that can ever
compete.
Jan 21 2013
parent reply "Rob T" <alanb ucora.com> writes:
On Monday, 21 January 2013 at 08:44:10 UTC, Nick Sabalausky wrote:

 I ask, because if except for the overhead, fibers are a good 
 general solution, then it makes sense to determine if anything 
 can be done to lessen the overhead before trying to implement 
 yet another solution.
 


 Yea, they *would* be a good general solution, and I'm sure the 
 overhead
 can be decreased, but AIUI I don't think it's even theoretically
 possible for them to optimized enough to compete with any of 
 the other
 approaches as a general-purpose thing.

 The other stuff can be optimized down as far as being little 
 more than
 an increment per iteration. But AIUI, using a real fiber would 
 require
 two context-switches per iteration, so I'm not sure that can 
 ever
 compete.


I have not yet had time to actually use fibers for anything real, 
but I did play around with them and the usage seemed to be 
exactly what we're looking for to implement co-routines. Since 
you have experience using them for real, do you think they are 
useful in general assuming that the performance can be made par 
with the stackless select switch method?

By chance, do you know if the current implementation is a 
built-in language feature or if it's implemented entirely as a 
library?

--rt
Jan 21 2013
next sibling parent Nick Sabalausky <SeeWebsiteToContactMe semitwist.com> writes:
On Mon, 21 Jan 2013 21:15:48 +0100
"Rob T" <alanb ucora.com> wrote:


 On Monday, 21 January 2013 at 08:44:10 UTC, Nick Sabalausky wrote:

 I ask, because if except for the overhead, fibers are a good 
 general solution, then it makes sense to determine if anything 
 can be done to lessen the overhead before trying to implement 
 yet another solution.
 


 Yea, they *would* be a good general solution, and I'm sure the 
 overhead
 can be decreased, but AIUI I don't think it's even theoretically
 possible for them to optimized enough to compete with any of 
 the other
 approaches as a general-purpose thing.

 The other stuff can be optimized down as far as being little 
 more than
 an increment per iteration. But AIUI, using a real fiber would 
 require
 two context-switches per iteration, so I'm not sure that can 
 ever
 compete.


 
 I have not yet had time to actually use fibers for anything real, 
 but I did play around with them and the usage seemed to be 
 exactly what we're looking for to implement co-routines.


Their usage, yes, and that does make it a very enticing prospect. And
they are indeed fantastic for many things. But as soon as you start
using them to implement something like:

coroutine int myCoroutine()
{
    yield 10;
    yield 20;

    if(blah)
        yield 30;

    foreach(i; arr)
        yield i;

    //etc
}

In other words, exactly the sorts of use-cases that coroutines are
perfectly suited for. Then you have to consider that your coroutine
may get used for anything from:

foreach(i; myCoroutine)
{
    string result = curl("http://example.com/"~to!string(i));
    writeFile(to!string(i)~".txt", result);
}

to things like:

int sum = myCoroutine.reduce!"a+b"();

The first case, with the I/O, is perfectly fine even if the coroutine
operates using fibers. But the second example, as sleek and deceptively
appealing as it looks, would have very poor performance because it's
doing a ton of context switching even though all it *really* needs to
do is grab a bunch of ints and add them.

OTOH, *both* examples would be perfectly fine if the coroutine were
trivially rewritten behind-the-scenes into a stackless event-loop that
*didn't* use fibers:

struct myCoroutine_localVars
{
    int state=0; // Simulate the instruction pointer
    int i; // The foreach loop variable
}
enum IsDone {Yes, No}
IsDone myCoroutine(ref myCoroutine_localVars context, ref int
yieldValue)
{
    switch(context.state)
    {
    case 0:
        context.state = 1;
        yieldValue = 10;
        return IsDone.No; // yield 10

    case 1:
        context.state = 2;
        yieldValue = 20;
        return IsDone.No; // yield 20

    case 2:
        if(blah)
        {
            context.state = 3;
            yieldValue = 30;
            return IsDone.No; // yield 30;
        }
        context.state = 3;
        goto case 3:

    case 3:
        context.i = 0; // Start for loop
        context.state = 4;
        goto case 4:

    case 4:
        if(context.i < arr.length)
        {
            context.i++;
            yieldValue = arr[context.i - 1];
            return IsDone.No; // yield i
        }
        context.state = 5;
        goto case 5:

    case 5:
        return IsDone.Yes;
    }
}

// foreach(val; myCoroutine) {...stuff...}
//   becomes -->
myCoroutine_localVars context;
int yieldValue;
while(myCoroutine(context, yieldValue) == IsDone.No)
{
    int val = yieldValue;
    ...stuff...
}

Note that looks similar to an equivalent hand-written input
range. So you'd have the performance of an input range in *all*
situations, while still having the convenience of coroutine syntax. (My

that's how C/C++'s protothreads work.) Note that transformation can
be easily automated since C/C++'s protothreads does exactly that
using nothing more than some very simple preprocessor macros.

Real fibers are enticing as an easy way to implement coroutines, but
once implemented, the only thing fibers would really accomplish here is
to slow things down for certain use-cases.

Well, also, real fibers would allow yielding from a function called
by myCoroutine. But even without fibers there are ways to get around
that limitation (as demonstrated by C/C++'s protothreads library).


 Since 
 you have experience using them for real, do you think they are 
 useful in general assuming that the performance can be made par 
 with the stackless select switch method?
 


If they could, then yes, but I don't believe that's a realistic
possibility. (Others can correct me if I'm wrong, but I'm fairly
sure.)


 By chance, do you know if the current implementation is a 
 built-in language feature or if it's implemented entirely as a 
 library?
 


In short, I don't know. Others could answer better.

In long:

I *think* they're implemented in druntime, or at least their core
functionality anyway. I don't know whether or not the druntime
implementation relies on any special compiler support. Others can
probably answer that.

I do know that D's fibers don't use the OS-provided fibers (at
least on Windows) since, at least on Windows, the OS fibers are
generally considered to not be very fast or good.
Jan 21 2013
prev sibling parent "deadalnix" <deadalnix gmail.com> writes:
On Monday, 21 January 2013 at 20:15:49 UTC, Rob T wrote:

 On Monday, 21 January 2013 at 08:44:10 UTC, Nick Sabalausky 
 wrote:

 I ask, because if except for the overhead, fibers are a good 
 general solution, then it makes sense to determine if 
 anything can be done to lessen the overhead before trying to 
 implement yet another solution.
 


 Yea, they *would* be a good general solution, and I'm sure the 
 overhead
 can be decreased, but AIUI I don't think it's even 
 theoretically
 possible for them to optimized enough to compete with any of 
 the other
 approaches as a general-purpose thing.

 The other stuff can be optimized down as far as being little 
 more than
 an increment per iteration. But AIUI, using a real fiber would 
 require
 two context-switches per iteration, so I'm not sure that can 
 ever
 compete.


 I have not yet had time to actually use fibers for anything 
 real, but I did play around with them and the usage seemed to 
 be exactly what we're looking for to implement co-routines. 
 Since you have experience using them for real, do you think 
 they are useful in general assuming that the performance can be 
 made par with the stackless select switch method?


It has no chance to be as fast. However, I use them quite a lot 
and they are very useful. Especially to hide IO latency or for 
dependancy management. I use them for the latter, some other 
software (like vide.d) use them for the former.

This cannot be achieved with stackless coroutine method as you 
need to yield from anywhere, not only the root function.


 By chance, do you know if the current implementation is a 
 built-in language feature or if it's implemented entirely as a 
 library?


This is done as library right now, which is awesome !
Jan 21 2013