"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
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.

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

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.

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

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

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/

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

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.

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;
    	    	}
    	};
}

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

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.