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


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) { ... }
?
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


 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) { ... }
?
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


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


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




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.


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


done

 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


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


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.



"loop" is nothing else than "while(true)"):
---------------------------------
class tree(T) {
        tree!(T) left;
        tree!(T) right;
        T leaf;


                if(left !== null)
                        loop {

                        };
                yield leaf;
                if(right !== null)
                        loop {

                        };
        }
}

int main() {
        tree!(char[]) t = create_some_string_tree();
        loop {

        };
}
---------------------------------

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.


 

 syntax, "loop" is nothing else than "while(true)"):
 ---------------------------------
 class tree(T) {
         tree!(T) left;
         tree!(T) right;
         T leaf;
 

                 if(left !== null)
                         loop {

                         };
                 yield leaf;
                 if(right !== null)
                         loop {

                         };
         }
 }
 
 int main() {
         tree!(char[]) t = create_some_string_tree();
         loop {

         };
 }
 ---------------------------------


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 {

    	    	    	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 {

               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 {

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


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

            }
        }
----------------------------------------

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


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>
 



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
 


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>
 



Took another look at it. Actually, it captures quite a bit of the idea from
Sather, anyhow, there is one fundamental difference:


Implementing and using an iterator looks very similar to Sather. The

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


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


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


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


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


 
 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