www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Things preprocessor can do that mixins can't

reply James McComb <alan jamesmccomb.id.au> writes:
Here's another thing the preprocessor can do that mixins can't do.

This is the kewl way I used to write forever loops:

#define EVER ;;

for(EVER) { /* more kewl code */ }

So much for mixins. ;)

James McComb
May 19 2004
next sibling parent reply "Walter" <newshound digitalmars.com> writes:
"James McComb" <alan jamesmccomb.id.au> wrote in message
news:c8hast$1nt7$1 digitaldaemon.com...
 Here's another thing the preprocessor can do that mixins can't do.

 This is the kewl way I used to write forever loops:

 #define EVER ;;

 for(EVER) { /* more kewl code */ }

 So much for mixins. ;)

D is suitably chastised.
May 19 2004
parent reply Juan C <Juan_member pathlink.com> writes:
 #define EVER ;;

 for(EVER) { /* more kewl code */ }

 So much for mixins. ;)

D is suitably chastised.

Meaning "not at all" I hope. I see no comparison between mixins and pre-processor symbols. Mixins do what they do far better than the pre-processor would (not that I've tried them yet). In my opinion the above code is vile misuse of the pre-processor. But maybe the language should have a special "endless loop" construct? Or does Walter's reply simply mean, "Where C is F***ed, D is chaste"?
May 19 2004
next sibling parent reply "Walter" <newshound digitalmars.com> writes:
"Juan C" <Juan_member pathlink.com> wrote in message
news:c8hjrs$24vc$1 digitaldaemon.com...
 #define EVER ;;

 for(EVER) { /* more kewl code */ }

 So much for mixins. ;)

D is suitably chastised.

Meaning "not at all" I hope. I see no comparison between mixins and pre-processor symbols. Mixins do what they do far better than the

 would (not that I've tried them yet).

LOL. I was just making a joke. In general, syntax-altering macros should not be used. Despite that, C must support such macros, which is an anchor around its neck.
 In my opinion the above code is vile misuse of the pre-processor.
 But maybe the
 language should have a special "endless loop" construct?

What's wrong with: while (1) { ... } ?
May 20 2004
parent reply "Bruno A. Costa" <bruno codata.com.br> writes:
Walter wrote:

 
 "Juan C" <Juan_member pathlink.com> wrote in message
 news:c8hjrs$24vc$1 digitaldaemon.com...
 #define EVER ;;

 for(EVER) { /* more kewl code */ }

 So much for mixins. ;)

D is suitably chastised.

Meaning "not at all" I hope. I see no comparison between mixins and pre-processor symbols. Mixins do what they do far better than the

 would (not that I've tried them yet).

LOL. I was just making a joke. In general, syntax-altering macros should not be used. Despite that, C must support such macros, which is an anchor around its neck.
 In my opinion the above code is vile misuse of the pre-processor.
 But maybe the
 language should have a special "endless loop" construct?

What's wrong with: while (1) { ... } ?

Or, if you want to be more purist: while (true) { ... } ?
May 20 2004
parent Roel Mathys <roel.mathys yucom.be> writes:
Bruno A. Costa wrote:

 Walter wrote:
 
 
"Juan C" <Juan_member pathlink.com> wrote in message
news:c8hjrs$24vc$1 digitaldaemon.com...

#define EVER ;;

for(EVER) { /* more kewl code */ }

So much for mixins. ;)

D is suitably chastised.

Meaning "not at all" I hope. I see no comparison between mixins and pre-processor symbols. Mixins do what they do far better than the

pre-processor
would (not that I've tried them yet).

LOL. I was just making a joke. In general, syntax-altering macros should not be used. Despite that, C must support such macros, which is an anchor around its neck.
In my opinion the above code is vile misuse of the pre-processor.
But maybe the
language should have a special "endless loop" construct?

What's wrong with: while (1) { ... } ?

Or, if you want to be more purist: while (true) { ... } ?

or the classic loop :-) void main() { int i = 0; STARTLOOP: printf("%d\n",++i); goto STARTLOOP; } roel
May 20 2004
prev sibling parent reply Ilya Minkov <minkov cs.tum.edu> writes:
Juan C schrieb:

 [...] But maybe the
 language should have a special "endless loop" construct?

Why a special? Sather, a very sympathic language (though by far not as useful as D), only has one looping construct. Exactly, it's an endless loop, called "loop". Then the only other thing you need is to break out of it. For example using an iterator. "i ::= 1.upto!(5);" will loop 5 times assigning increasing values to i from 1 to 5. There are also many other itaertors defined. After it's finished, it breaks out of the loop automatically. You can have multiple interators within 1 loop as well, and well, the one that breaks first wins. :> -eye
May 20 2004
next sibling parent Juan C <Juan_member pathlink.com> writes:
Why a special? Sather, a very sympathic language (though by far not as 
useful as D), only has one looping construct. Exactly, it's an endless 
loop, called "loop". Then the only other thing you need is to break out 

Ooh, I like that.
May 20 2004
prev sibling parent reply Norbert Nemec <Norbert.Nemec gmx.de> writes:
Ilya Minkov wrote:

 Juan C schrieb:
 
 [...] But maybe the
 language should have a special "endless loop" construct?

Why a special? Sather, a very sympathic language (though by far not as useful as D), only has one looping construct. Exactly, it's an endless loop, called "loop". Then the only other thing you need is to break out of it. For example using an iterator. "i ::= 1.upto!(5);" will loop 5 times assigning increasing values to i from 1 to 5. There are also many other itaertors defined. After it's finished, it breaks out of the loop automatically. You can have multiple interators within 1 loop as well, and well, the one that breaks first wins. :>

Don't underestimate the complexity behind this. Sather loops/iterators are the most powerful loop concept of any language and allow lots of stuff, that simply is not even remotely possible in other languages. Anyone who has ever used Sather and tried to return to some other language afterward will have experienced the problem of expressing their ideas without Sather iterators. Anyhow: I doubt that there is a chance to make someone, who has never actually used Sather understand the idea and the power of it. The concept could certainly be added cleanly to D and it would definitely mean an unbelievable boost of the power of the language, but I see little chance to ever convince Walter to even think about it. B.t.w: "Sather iterators" are something completely different from "C++ iterators". They cannot be simulated in C++ at all. There is some similarity to coroutines in Modula, but unlike some clumsy coroutine implementations in C++, Sather iterators are not based upon expensive frame switches, but work cleanly on one stack. I do not know whether the intermediate languages of the DM/gcc backend are powerful enough to support them, or whether you would have to go down to assembler language. Conclusion: If Walter is willing to invest some time in looking into the concept of Sather iterators, I promise that he will find the absolute killer feature for D with extremely high addiction potential. Otherwise, I don't think there is much point in discussing the matter on this list.
May 21 2004
next sibling parent reply "Walter" <newshound digitalmars.com> writes:
"Norbert Nemec" <Norbert.Nemec gmx.de> wrote in message
news:c8kemm$24vv$1 digitaldaemon.com...
 Don't underestimate the complexity behind this. Sather loops/iterators are
 the most powerful loop concept of any language and allow lots of stuff,
 that simply is not even remotely possible in other languages.

 Anyone who has ever used Sather and tried to return to some other language
 afterward will have experienced the problem of expressing their ideas
 without Sather iterators. Anyhow: I doubt that there is a chance to make
 someone, who has never actually used Sather understand the idea and the
 power of it.

 The concept could certainly be added cleanly to D and it would definitely
 mean an unbelievable boost of the power of the language, but I see little
 chance to ever convince Walter to even think about it.

 B.t.w: "Sather iterators" are something completely different from "C++
 iterators". They cannot be simulated in C++ at all. There is some
 similarity to coroutines in Modula, but unlike some clumsy coroutine
 implementations in C++, Sather iterators are not based upon expensive

 switches, but work cleanly on one stack. I do not know whether the
 intermediate languages of the DM/gcc backend are powerful enough to

 them, or whether you would have to go down to assembler language.

 Conclusion: If Walter is willing to invest some time in looking into the
 concept of Sather iterators, I promise that he will find the absolute
 killer feature for D with extremely high addiction potential. Otherwise, I
 don't think there is much point in discussing the matter on this list.

Sather iterators are pretty cool. But I have no idea how they can be implemented without doing coroutines.
May 21 2004
next sibling parent reply Norbert Nemec <Norbert.Nemec gmx.de> writes:
Walter wrote:

 Sather iterators are pretty cool. But I have no idea how they can be
 implemented without doing coroutines.

You don't need coroutines at all. The important point is to realize that iterators are tightly coupled and highly synchronized with their enclosing loop. Coroutines are usually used as mostly independant routines that only synchronize where necessary (like in the old days of cooperative multitasking) Technically, both may be similar, but conceptually they are very different. Especially, with Sather iterators, the interaction between iterators and their enclosing loop is so well defined, that everything can be done on the stack with no more overhead than plain function calls (i.e. virtually none) Even inlining should be possible in many cases. Basically, the idea is: 1) the enclosing loop saves the SP on loop entrance. 2) Now iterators that are called for the first time ("initialization"), are called just like plain functions. 2) On initialization, the iterator allocates its stack frame just like any function. 3) Now, at the "yield", the interesting stuff happens: the iterator does not "return" (i.e. free the stack frame and pop the return address from the stack), but it *calls* the return address, effectively *pushing* the current IP and leaving its stack frame as it is. 4) The enclosing loop now pops this IP, stores it and the iterators's BP somewhere safe for future reference and continues. 5) Other iterators may be called in the same loop and will, in the same way, be initalized and thereby put their own stack frame above the frames of already initiated iterators. 6) Now, when the enclosing loop reaches an iterator call that has already been initialized, it does not call it directly, but restores the iterators BP and calls the stored IP address of that iterator, effectively reentering the iterator in the same state as it yielded, right behind the yield command. 7) This continues until some iterator reaches a quit (or the end of the iterator) here it will set some flag before returning to the loop, indicating, that the loop should immediately jump the end of the loop, at which place the initial SP is restored, all stack frames are forgotten and everyone is happy. As you see, it need some juggling with registers in a rather unusual way, which is the reason why I'm not sure, whether DM/gcc intermediate languages will suffice. Anyhow, I'm pretty sure the concept is portable to other architectures without problems. One special situation are loops containing yields (which may happen within iterators): These loops may not restore the old SP on exit since there might still be live iterators stored on the stack above. In the case that you have two nested loops within an iterator any the inner loop contains a yield, deserted stack frames may build up until the loop enclosing the iterator exits. This is a potential source of stack overflows, but it is not worse than that in recursive programming and the compiler may often be able to optimize it away. I should remark here, that the Sather implementation itself does not use this technique but rather works with structures on the heap. This is, of course, always a less efficient alternative if you do not want to fiddle with assembler. So, after all, Sather iterators should prove to be a powerful concept that is mostly orthogonal to existing concepts in D. Loops built upon iterators do not bring any performance penalty compared to loops containing function calls. You could forget about all conventional loops, even replacing foreach by something far simpler and far more flexible.
May 22 2004
next sibling parent "cbouc" <c-REDUCE-SPAM-PART-bouchon hotmail.com> writes:
I remembered reading interesting stuff about possible Sather iterators
implementation some years ago so I searched for it. Look for
http://www.icsi.berkeley.edu/~sather/Publications/tr-93-045.ps.gz (after
downloading, remove the .gz and use GSview to open it), section 5 (page 14)
gives some hints about possible simple Sather iterators optimizations. The
final paragraph also imply that some optimizations are possible even on more
complex Sather iterators.

"Norbert Nemec" <Norbert.Nemec gmx.de> a écrit dans le message de
news:c8mvpe$2sjd$1 digitaldaemon.com...
 Walter wrote:

 Sather iterators are pretty cool. But I have no idea how they can be
 implemented without doing coroutines.

You don't need coroutines at all. The important point is to realize that iterators are tightly coupled and highly synchronized with their enclosing loop. Coroutines are usually used as mostly independant routines that only synchronize where necessary (like in the old days of cooperative multitasking) Technically, both may be similar, but conceptually they are very different. Especially, with Sather iterators, the interaction between iterators and their enclosing loop is so well defined, that everything can be done on

 stack with no more overhead than plain function calls (i.e. virtually

 Even inlining should be possible in many cases.

 Basically, the idea is:

 1) the enclosing loop saves the SP on loop entrance.

 2) Now iterators that are called for the first time ("initialization"),

 called just like plain functions.

 2) On initialization, the iterator allocates its stack frame just like any
 function.

 3) Now, at the "yield", the interesting stuff happens: the iterator does

 "return" (i.e. free the stack frame and pop the return address from the
 stack), but it *calls* the return address, effectively *pushing* the
 current IP and leaving its stack frame as it is.

 4) The enclosing loop now pops this IP, stores it and the iterators's BP
 somewhere safe for future reference and continues.

 5) Other iterators may be called in the same loop and will, in the same

 be initalized and thereby put their own stack frame above the frames of
 already initiated iterators.

 6) Now, when the enclosing loop reaches an iterator call that has already
 been initialized, it does not call it directly, but restores the iterators
 BP and calls the stored IP address of that iterator, effectively

 the iterator in the same state as it yielded, right behind the yield
 command.

 7) This continues until some iterator reaches a quit (or the end of the
 iterator) here it will set some flag before returning to the loop,
 indicating, that the loop should immediately jump the end of the loop, at
 which place the initial SP is restored, all stack frames are forgotten and
 everyone is happy.

 As you see, it need some juggling with registers in a rather unusual way,
 which is the reason why I'm not sure, whether DM/gcc intermediate

 will suffice. Anyhow, I'm pretty sure the concept is portable to other
 architectures without problems.

 One special situation are loops containing yields (which may happen within
 iterators): These loops may not restore the old SP on exit since there
 might still be live iterators stored on the stack above. In the case that
 you have two nested loops within an iterator any the inner loop contains a
 yield, deserted stack frames may build up until the loop enclosing the
 iterator exits. This is a potential source of stack overflows, but it is
 not worse than that in recursive programming and the compiler may often be
 able to optimize it away.

 I should remark here, that the Sather implementation itself does not use
 this technique but rather works with structures on the heap. This is, of
 course, always a less efficient alternative if you do not want to fiddle
 with assembler.

 So, after all, Sather iterators should prove to be a powerful concept that
 is mostly orthogonal to existing concepts in D. Loops built upon iterators
 do not bring any performance penalty compared to loops containing function
 calls. You could forget about all conventional loops, even replacing
 foreach by something far simpler and far more flexible.

May 22 2004
prev sibling parent reply "Walter" <newshound digitalmars.com> writes:
Thanks. Your explanation makes sense, but I have to think about it some
more. There are other issues at stake, like cleanup of auto classes on the
stack.
May 22 2004
parent reply Norbert Nemec <Norbert.Nemec gmx.de> writes:
Walter wrote:

 Thanks. Your explanation makes sense, but I have to think about it some
 more. There are other issues at stake, like cleanup of auto classes on the
 stack.

Sather disallows yield-statements in the middle of try/catch blocks. Auto classes probably are a similar issue. Are auto classes bound to a function or to a block? I cannot find that documented in the specs. If they are bound to blocks, you might want to disallow yield statements within a block that contains auto classes. Otherwise you would have to completely prohibit auto classes in iterators. In any case, the principle is, that you never know whether execution will continue after a yield statement. The cleanup of the stackframe can be done be the enclosing loop. Any other cleanup must not be necessary. Anyhow: It is clear that this whole thing will need a lot of consideration. Iterators are a rather orthogonal addition to the existing language, but once they are used, the will affect the language rather fundamentally. Did I talk about that high addiction-potential? After using Sather for some time, I really had a hard time to do without iterators in C++...
May 23 2004
parent "Walter" <newshound digitalmars.com> writes:
"Norbert Nemec" <Norbert.Nemec gmx.de> wrote in message
news:c8pji6$k82$1 digitaldaemon.com...
 Walter wrote:
 Thanks. Your explanation makes sense, but I have to think about it some
 more. There are other issues at stake, like cleanup of auto classes on


 stack.

classes probably are a similar issue. Are auto classes bound to a function or to a block? I cannot find that documented in the specs. If they are bound to blocks, you might want to disallow yield statements within a block that contains auto classes. Otherwise you would have to completely prohibit auto classes in iterators.

Auto classes are just like stack classes in C++ - they are cleaned up on exit from the block.
 In any case, the principle is, that you never know whether execution will
 continue after a yield statement. The cleanup of the stackframe can be

 be the enclosing loop. Any other cleanup must not be necessary.

That is one solution - just disallow them.
 Anyhow: It is clear that this whole thing will need a lot of

 Iterators are a rather orthogonal addition to the existing language, but
 once they are used, the will affect the language rather fundamentally. Did
 I talk about that high addiction-potential? After using Sather for some
 time, I really had a hard time to do without iterators in C++...

I can see how they'd encourage a different way of thinking about iteration <g>.
May 23 2004
prev sibling next sibling parent reply Ilya Minkov <minkov cs.tum.edu> writes:
Walter schrieb:
 "Norbert Nemec" <Norbert.Nemec gmx.de> wrote in message
 news:c8kemm$24vv$1 digitaldaemon.com...
 
Don't underestimate the complexity behind this. Sather loops/iterators are
the most powerful loop concept of any language and allow lots of stuff,
that simply is not even remotely possible in other languages.


Ok, i don't know how fortunate this comment of mine was which was meant to be more humorous than serious. I haven't used Sather really but i like it a lot - each of the elegant and innovative details, and i'm glad we apparently have You now as a person with Sather experience here. It gives us a lot of interesting to learn.
The concept could certainly be added cleanly to D and it would definitely
mean an unbelievable boost of the power of the language, but I see little
chance to ever convince Walter to even think about it.


In some sense, its use partially overlaps with that of foreach construct. I wonder to what extent it covers the need for Sather iterators. Convincing Walter is not too hard, it just means making some work, which is: - sum up the usage cases; - propose an implementtion strategy; - convince Mr. Wilson. Which should usually result in the Walter being convinced, or the proposer un-convinced. :>
Conclusion: If Walter is willing to invest some time in looking into the
concept of Sather iterators, I promise that he will find the absolute
killer feature for D with extremely high addiction potential. Otherwise, I
don't think there is much point in discussing the matter on this list.

Sather iterators are pretty cool. But I have no idea how they can be implemented without doing coroutines.

Hmmm... Sather definately doesn't use coroutines to implement them, because it generates ANSI C as output! Which also means that every back-end should be powerful enough to implement it. It might be easiest to try to read from generated C code what it actually does. However, i recall Sather recognizes simple forms of iterationa and transfoms them into for or while loops - something to be aware of. I'll see if i have a compiled MinGW version of Sather lying anywhere. -eye
May 22 2004
next sibling parent reply J Anderson <REMOVEanderson badmama.com.au> writes:
Ilya Minkov wrote:

 Walter schrieb:

 "Norbert Nemec" <Norbert.Nemec gmx.de> wrote in message
 news:c8kemm$24vv$1 digitaldaemon.com...

 Don't underestimate the complexity behind this. Sather 
 loops/iterators are
 the most powerful loop concept of any language and allow lots of stuff,
 that simply is not even remotely possible in other languages.


Ok, i don't know how fortunate this comment of mine was which was meant to be more humorous than serious. I haven't used Sather really but i like it a lot - each of the elegant and innovative details, and i'm glad we apparently have You now as a person with Sather experience here. It gives us a lot of interesting to learn.
 The concept could certainly be added cleanly to D and it would 
 definitely
 mean an unbelievable boost of the power of the language, but I see 
 little
 chance to ever convince Walter to even think about it.


In some sense, its use partially overlaps with that of foreach construct. I wonder to what extent it covers the need for Sather iterators. Convincing Walter is not too hard, it just means making some work, which is: - sum up the usage cases; - propose an implementtion strategy; - convince Mr. Wilson. Which should usually result in the Walter being convinced, or the proposer un-convinced. :>

Also you need to prove that its useful by providing a real-life comparison of why its needed. -- -Anderson: http://badmama.com.au/~anderson/
May 22 2004
parent reply Norbert Nemec <Norbert.Nemec gmx.de> writes:
J Anderson wrote:

 Also you need to prove that its useful by providing a real-life
 comparison of why its needed.

Consider the following code scribble (using "#" as a preliminary syntax, "loop" is nothing else than "while(true)"): --------------------------------- class tree(T) { tree!(T) left; tree!(T) right; T leaf; T elt#() { if(left !== null) loop { yield left.elt#(); }; yield leaf; if(right !== null) loop { yield right.elt#(); }; } } int main() { tree!(char[]) t = create_some_string_tree(); loop { printf("%s\n",t.elt#()); }; } --------------------------------- Consider what you usually have to code to traverse a binary tree or other structures. Of course, C++ iterators allow traversal as well, but they are somewhat more complicated to use and by far more complicated to implement, especially in recursive data structures, where the iterator has to create it's own stack to keep track of the current position. Sather iterators are generally only "forward iterators", best compared to streams, that yield one element after the other until they quit. There is no need to check for the end of the stream, since the loop is automatically broken as one iterator quits. (Even in the middle of an expression, like in the above case, where there is no additional "garbage line" printed.) Bidirectional or random access iterators do not exist in Sather. I don't think, there is a chance to fit them into the concept at all. I think, there are plenty more real-life examples, but anything that really exploits the power of Sather iterators would probably be hard to understand without further explanation.
May 22 2004
next sibling parent reply Patrick Down <pat codemoon.com> writes:
Comments inline

Norbert Nemec <Norbert.Nemec gmx.de> wrote in
news:c8nmsn$uil$1 digitaldaemon.com: 

 J Anderson wrote:
 
 Also you need to prove that its useful by providing a real-life
 comparison of why its needed.

Consider the following code scribble (using "#" as a preliminary syntax, "loop" is nothing else than "while(true)"): --------------------------------- class tree(T) { tree!(T) left; tree!(T) right; T leaf; T elt#() { if(left !== null) loop { yield left.elt#(); }; yield leaf; if(right !== null) loop { yield right.elt#(); }; } } int main() { tree!(char[]) t = create_some_string_tree(); loop { printf("%s\n",t.elt#()); }; } ---------------------------------

Here is an example with more that one iterator. int main() { tree!(char[]) t1 = create_some_string_tree(); tree!(char[]) t2 = create_some_string_tree(); loop { if(t1.elt#() != t2.elt#()) { printf("Different\n"); break; } }; }
May 22 2004
parent reply Norbert Nemec <Norbert.Nemec gmx.de> writes:
Patrick Down wrote:

 Here is an example with more that one iterator.
 
 int main() {
     tree!(char[]) t1 = create_some_string_tree();
     tree!(char[]) t2 = create_some_string_tree();
     loop {
          if(t1.elt#() != t2.elt#()) {
               printf("Different\n");
               break;
          }
     };
 }

True, even though, this example might behave in an unexpected way if t1 and t2 have different length: If both trees are identical except for some additional elements at the end of t2, the loop will quit without notice as soon as it hits the end of t1, without even checking whether t2 has elements left. This example already shows: using iterators correctly takes some care, but I guess that's true for about every powerful feature in a language...
May 22 2004
parent reply Patrick Down <pat codemoon.com> writes:
Norbert Nemec <Norbert.Nemec gmx.de> wrote in
news:c8ns2q$1616$1 digitaldaemon.com: 

 Patrick Down wrote:
 
 Here is an example with more that one iterator.
 
 int main() {
     tree!(char[]) t1 = create_some_string_tree();
     tree!(char[]) t2 = create_some_string_tree();
     loop {
          if(t1.elt#() != t2.elt#()) {
               printf("Different\n");
               break;
          }
     };
 }

True, even though, this example might behave in an unexpected way if t1 and t2 have different length: If both trees are identical except for some additional elements at the end of t2, the loop will quit without notice as soon as it hits the end of t1, without even checking whether t2 has elements left. This example already shows: using iterators correctly takes some care, but I guess that's true for about every powerful feature in a language...

Yes this is true. I was trying to find a quick example that demonstrated more than one iterator. D's opApply and foreach already provide good single iterator functionality.
May 22 2004
parent reply Norbert Nemec <Norbert.Nemec gmx.de> writes:
Patrick Down wrote:

 Yes this is true.  I was trying to find a quick example that demonstrated
 more than one iterator.  D's opApply and foreach already provide good
 single iterator functionality.

"good" - yes - but still far from what Sather iterators offer. Just take a look at the opApply-example from the D-specs: ---------------------------------------- class Foo { uint array[2]; int opApply(int delegate(inout uint) dg) { int result = 0; for (int i = 0; i < array.length; i++) { result = dg(array[i]); if (result) break; } return result; } } void test() { Foo a = new Foo(); a.array[0] = 73; a.array[1] = 82; foreach (uint u; a) { printf("%d\n", u); } } ---------------------------------------- This would translate to the following, using Sather iterators: ---------------------------------------- class Foo { uint array[2]; elt#() { for (int i = 0; i < array.length); i++) yield array[i]; } } void test() { Foo a = new Foo(); a.array[0] = 73; a.array[1] = 82; loop { printf("%d\n", a.elt#()); } } ---------------------------------------- and this simplification is not just because the example was so simple... As you can see from the example: the real power of Sather iterators lies not primarily in their use, but in their definition. C++-iterators and D-foreach loops are both fairly comfortable to use, but defining them for just moderately complicated structures is rather tricky. Sather iterators actually are fun to implement yourself!
May 22 2004
parent reply "Bent Rasmussen" <exo bent-rasmussen.info> writes:
Sather iterators as described here seriously reminds me of this

http://msdn.microsoft.com/netframework/archive/default.aspx?pull=/msdnmag/issues/04/05/c20/default.aspx

<quote>
public class CityCollection : IEnumerable
{
   string[] m_Cities = {"New York","Paris","London"};
   public IEnumerator GetEnumerator()
   {
      for(int i = 0; i<m_Cities.Length; i++)
         yield return m_Cities[i];
   }
}
</quote>

Looks Satherish. The article explains "new" features of C# 2.0.
May 22 2004
next sibling parent Norbert Nemec <Norbert.Nemec gmx.de> writes:
Bent Rasmussen wrote:

 Sather iterators as described here seriously reminds me of this
 

 
 <quote>
 public class CityCollection : IEnumerable
 {
    string[] m_Cities = {"New York","Paris","London"};
    public IEnumerator GetEnumerator()
    {
       for(int i = 0; i<m_Cities.Length; i++)
          yield return m_Cities[i];
    }
 }
 </quote>
 
 Looks Satherish. The article explains "new" features of C# 2.0.

Indeed, this shows some similarity. I'm not really sure, whether it really captures the whole concept. Have to check that more thoroghly.
May 22 2004
prev sibling parent Norbert Nemec <Norbert.Nemec gmx.de> writes:
Bent Rasmussen wrote:

 Sather iterators as described here seriously reminds me of this
 

 
 <quote>
 public class CityCollection : IEnumerable
 {
    string[] m_Cities = {"New York","Paris","London"};
    public IEnumerator GetEnumerator()
    {
       for(int i = 0; i<m_Cities.Length; i++)
          yield return m_Cities[i];
    }
 }
 </quote>
 
 Looks Satherish. The article explains "new" features of C# 2.0.

Took another look at it. Actually, it captures quite a bit of the idea from Sather, anyhow, there is one fundamental difference: In C#, an enumerator is an object of a class with a certain interface. Implementing and using an iterator looks very similar to Sather. The difference lies in what happens internally: C# takes the iterator routine containing the different yields and *decomposes* it into a class with the appropriate interface in such a way that it can be used in foreach loops. In Sather, an iterator is a basic concept of the language without any classes etc. involved. This makes it possible, to implement the whole thing completely on the stack, inline iterators and in principle allows to boost the speed of iterator loops to the same speed as plain C loops. I strongly doubt that you will ever get similar performace out of the C# iterators. The implementation in Sather does not exploit this possibility, since this would not be possible within ANSI C. I have no idea whether the Sather developers ever realized that this might be possible, but the concept definitely allows it and it should be possible to introduce the same concept in D.
May 22 2004
prev sibling parent reply "Walter" <newshound digitalmars.com> writes:
"Norbert Nemec" <Norbert.Nemec gmx.de> wrote in message
news:c8nmsn$uil$1 digitaldaemon.com...
 Consider what you usually have to code to traverse a binary tree or other
 structures. Of course, C++ iterators allow traversal as well, but they are
 somewhat more complicated to use and by far more complicated to implement,
 especially in recursive data structures, where the iterator has to create
 it's own stack to keep track of the current position.

D's 'foreach' will do the same as the above in about the same amount of code (for opApply()). Where Sather's iterators are better are: 1) multiple different iterators in the same loop 2) having multiple iterators for a class to access the members in different orders
 Sather iterators are generally only "forward iterators", best compared to
 streams, that yield one element after the other until they quit. There is
 no need to check for the end of the stream, since the loop is

 broken as one iterator quits. (Even in the middle of an expression, like

 the above case, where there is no additional "garbage line" printed.)

I don't get that. When an iterator ends, exactly when is this checked for in the loop? The middle of the expression?
May 22 2004
parent Norbert Nemec <Norbert.Nemec gmx.de> writes:
Walter wrote:

 
 "Norbert Nemec" <Norbert.Nemec gmx.de> wrote in message
 news:c8nmsn$uil$1 digitaldaemon.com...
 Consider what you usually have to code to traverse a binary tree or other
 structures. Of course, C++ iterators allow traversal as well, but they
 are somewhat more complicated to use and by far more complicated to
 implement, especially in recursive data structures, where the iterator
 has to create it's own stack to keep track of the current position.

D's 'foreach' will do the same as the above in about the same amount of code (for opApply()).

True, when I wrote the above, I had not yet fully understood opApply. Anyhow: Sather iterator definitions are yet more compact than the definition of opApply.
 Sather iterators are generally only "forward iterators", best compared to
 streams, that yield one element after the other until they quit. There is
 no need to check for the end of the stream, since the loop is

 broken as one iterator quits. (Even in the middle of an expression, like

 the above case, where there is no additional "garbage line" printed.)

I don't get that. When an iterator ends, exactly when is this checked for in the loop? The middle of the expression?

Exactly. When the iterator quits, it does not return any value at all, but instead causes the enclosing loop to jump directly out of the loop and clean up the loop-stackframe. If this happens within an expression, this expression can, of course, not be continued, since there is no value that could be used, so the loop is broken in the middle of that expression. In expressions with side-effects, this may, of course, cause some undefined behaviour, but that is just a matter of D not guaranteeing the order of calls within an expression.
May 23 2004
prev sibling next sibling parent Norbert Nemec <Norbert.Nemec gmx.de> writes:
Ilya Minkov wrote:

 Walter schrieb:
 "Norbert Nemec" <Norbert.Nemec gmx.de> wrote in message
 news:c8kemm$24vv$1 digitaldaemon.com...
 
Don't underestimate the complexity behind this. Sather loops/iterators
are the most powerful loop concept of any language and allow lots of
stuff, that simply is not even remotely possible in other languages.


Ok, i don't know how fortunate this comment of mine was which was meant to be more humorous than serious. I haven't used Sather really but i like it a lot - each of the elegant and innovative details, and i'm glad we apparently have You now as a person with Sather experience here. It gives us a lot of interesting to learn.

Well, the only thing where I think D could actually learn from Sather is that concept of iterators, and maybe also that of closures, which are basically just a more general form of delegates and function pointers. Beyond these, the major point where I see an advantage in Sather is, that it has a far superior concept of classes and interfaces, which, of course, is completely incompatible with the concepts of C++ and D.
The concept could certainly be added cleanly to D and it would definitely
mean an unbelievable boost of the power of the language, but I see little
chance to ever convince Walter to even think about it.


In some sense, its use partially overlaps with that of foreach construct. I wonder to what extent it covers the need for Sather iterators.

Foreach offers really just a tiny fraction of what Sather iterators could do. The step from foreach to Sather iterators is probably about as big as from the C preprocessor to D templates...
 Convincing Walter is not too hard, it just means making some work, which
 is: - sum up the usage cases;
 - propose an implementtion strategy;
 - convince Mr. Wilson.

Sounds like an interesting road ahead... :-)
 Hmmm... Sather definately doesn't use coroutines to implement them,
 because it generates ANSI C as output! Which also means that every
 back-end should be powerful enough to implement it. It might be easiest
 to try to read from generated C code what it actually does.

The existing Sather implementation keeps the state (local variables and postition of the last yield) of an initialized iterator in a struct on the heap. At every subsequent call of the same iterator, that state is restored by doing a switch/case/goto at the beginning of the iterator, jumping behind the yield that was executed before. This is easy to implement and completely portable, but rather inefficient. I have worked out a concept to do the same thing completely on the stack with direct jumps right into the iterator to the position where it yielded before. I don't think this possibility has been explored before at all. You cannot do it in C and maybe not even in the current DM/gcc intermediate language, but if the compiler generates plain assembler, it should not be a problem on any architecture (and if the concept catches on, DM/gcc intermediate languages can probably be extended)
 However, i 
 recall Sather recognizes simple forms of iterationa and transfoms them
 into for or while loops - something to be aware of.

That's just an optimization like inlining of routines. In the current Sather implementation, it makes quite some difference, of course, since iterators are rather inefficient. In a stack-based implementation, iterator calls don't cost more than routine calls, so inlining will give you just the usual speedup of function inlining. Ciao, Nobbi
May 22 2004
prev sibling parent "Matthew" <matthew.hat stlsoft.dot.org> writes:
 Convincing Walter is not too hard, it just means making some work, which is:
 - sum up the usage cases;
 - propose an implementtion strategy;
 - convince Mr. Wilson.

 Which should usually result in the Walter being convinced, or the
 proposer un-convinced. :>

Who's this _Mr_ Wilson, then, eh? :-)
May 22 2004
prev sibling parent reply no where.com writes:
In article <c8lutu$1blp$1 digitaldaemon.com>, Walter says...
Sather iterators are pretty cool. But I have no idea how they can be
implemented without doing coroutines.

I'm wondering how foreach/opApply is implemented in D. Their behaviour looks very much like coroutines: i.e. each keeps its own stack frame. Is there any stack frame switching involved?
Nov 04 2004
parent Norbert Nemec <Norbert Nemec-online.de> writes:
no where.com wrote:

 I'm wondering how foreach/opApply is implemented in D.  Their behaviour
 looks
 very much like coroutines: i.e. each keeps its own stack frame.  Is there
 any stack frame switching involved?

No coroutine, no frame-switching: The loop body is wrapped up as function and the opApply gets a pointer to that function which is then called for each element in the list. Neat and simple idea, but it cannot be expanded to more than one opApply routine running in for one loop. Furthermore, the handling of function pointers means a certain overhead, making foreach-loops questionable for performance critical work.
Nov 05 2004
prev sibling next sibling parent ac(ex-a_coward) <ac(ex-a_coward)_member pathlink.com> writes:
In article <c8kemm$24vv$1 digitaldaemon.com>, Norbert Nemec says...
Conclusion: If Walter is willing to invest some time in looking into the
concept of Sather iterators, I promise that he will find the absolute
killer feature for D with extremely high addiction potential. Otherwise, I
don't think there is much point in discussing the matter on this list.

I guess Walter is 130% busy right now. Better would be to write a few short but powerful examples! If Walter sees the important guys here getting convinced, then he probably will pay attention. (And that is as it shoud!)
Oct 29 2004
prev sibling parent reply Matthias Becker <Matthias_member pathlink.com> writes:
 [...] But maybe the
 language should have a special "endless loop" construct?

Why a special? Sather, a very sympathic language (though by far not as useful as D), only has one looping construct. Exactly, it's an endless loop, called "loop". Then the only other thing you need is to break out of it. For example using an iterator. "i ::= 1.upto!(5);" will loop 5 times assigning increasing values to i from 1 to 5. There are also many other itaertors defined. After it's finished, it breaks out of the loop automatically. You can have multiple interators within 1 loop as well, and well, the one that breaks first wins. :>

Don't underestimate the complexity behind this. Sather loops/iterators are the most powerful loop concept of any language and allow lots of stuff, that simply is not even remotely possible in other languages. Anyone who has ever used Sather and tried to return to some other language afterward will have experienced the problem of expressing their ideas without Sather iterators. Anyhow: I doubt that there is a chance to make someone, who has never actually used Sather understand the idea and the power of it. The concept could certainly be added cleanly to D and it would definitely mean an unbelievable boost of the power of the language, but I see little chance to ever convince Walter to even think about it. B.t.w: "Sather iterators" are something completely different from "C++ iterators". They cannot be simulated in C++ at all. There is some similarity to coroutines in Modula, but unlike some clumsy coroutine implementations in C++, Sather iterators are not based upon expensive frame switches, but work cleanly on one stack. I do not know whether the intermediate languages of the DM/gcc backend are powerful enough to support them, or whether you would have to go down to assembler language. Conclusion: If Walter is willing to invest some time in looking into the concept of Sather iterators, I promise that he will find the absolute killer feature for D with extremely high addiction potential. Otherwise, I don't think there is much point in discussing the matter on this list.

Anyway, CLU has have such a construct decades before. ICON has them, too. So it's not a new idea of sather. They just copied it.
Oct 30 2004
parent Norbert Nemec <Norbert Nemec-online.de> writes:
Matthias Becker wrote:
 Anyway, CLU has have such a construct decades before. ICON has them, too.
 So it's not a new idea of sather. They just copied it.

I know neither CLU nor ICON. Of course, language constructs are hardly every new. Languages evolve from each other, copying ideas and improving them. Anyhow: I know many languages have features similar to Sather iterators, but none of them (as far as I have found it) captures the full power. Python "generators" seem to come very close, but they are fundamentally based on using an exception to break the iteration, which is inacceptable for a compiled language striving for performance. Also, Python iterators can only be used in the head of a "for-in" loop. Modula-III Coroutines seem similar, but they are only loosely synchronized and demand expensive frame-switching. Several functional languages with infinite lists allow similar constructs, but the concept is closely tied to the functional character of the language and can not easily be translated to multiparadigm languages. About any modern language has something that is called "iterator" but usually, it has little to do with Sather iterators. The genius idea in Sather (or wherever it came from originally) is the interplay of iterators and loops, which allows for semantics very similar to coroutines with an implementation that works completely on the stack. This kind of implementation, though, depends strongly on the details of the calling convention of functions, the placement of local variables, etc. It can definitely not be done in the library or with a preprocessor without loosing efficiency. Whether existing compiler-backends would support this kind of code is something I still have to determine.
Nov 04 2004
prev sibling next sibling parent Andy Friesen <andy ikagames.com> writes:
James McComb wrote:
 Here's another thing the preprocessor can do that mixins can't do.
 
 This is the kewl way I used to write forever loops:
 
 #define EVER ;;
 
 for(EVER) { /* more kewl code */ }
 
 So much for mixins. ;)
 
 James McComb

No, mixins cannot be used to butcher the syntax of the language. Sorry. #define sizeof(x) rand() #define if(x) while(!x) et cetera -- andy
May 19 2004
prev sibling parent reply "Matthew" <matthew.hat stlsoft.dot.org> writes:
Oh, please!

That's one of the most stupid things I've ever heard. Almost, but not quite, as
bad as the idiot I used to work with who did

    #define retrun return

just because he mistyped it so often.

for(;;) is a recognised and recommended way of defining a non-claused loop. Why
would you not use that?

Remember, one man's cool is many other's naff/trite/stupid/etc.

"James McComb" <alan jamesmccomb.id.au> wrote in message
news:c8hast$1nt7$1 digitaldaemon.com...
 Here's another thing the preprocessor can do that mixins can't do.

 This is the kewl way I used to write forever loops:

 #define EVER ;;

 for(EVER) { /* more kewl code */ }

 So much for mixins. ;)

 James McComb

May 22 2004
next sibling parent "Bent Rasmussen" <exo bent-rasmussen.info> writes:
or one man's bate is another mans meal ;)
May 23 2004
prev sibling parent "Walter" <newshound digitalmars.com> writes:
"Matthew" <matthew.hat stlsoft.dot.org> wrote in message
news:c8p5i7$303j$1 digitaldaemon.com...
 Oh, please!

I think he was just kidding. It's in the same category as: #define BEGIN { #define END } which was popular practice in the mid 1980's. As Pascal asymptotically approached 0 users (*), people got bored with trying to remake C in Pascal's image and the community began to realize that it was better to write things in the C style when using C. (*) Pascal was all but dead and buried when Borland briefly re-animated it with Turbo Pascal. TP burned white hot for a couple years, but the C blob inevitably absorbed it as well. I suspect that having to type BEGIN END instead of { } was its downfall <g>.
May 23 2004