www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Walter: any plan to add support for yield/return Iterators/generators?

reply Marcio <mqmnews321 sglebs.com> writes:
Hi,

   People who have used socket/select without Threads probably had to 
suffer writing their own state machine by hand. Some people may have had 
adventures in continuation passing land, even.

   Recently languages have incorporated yield/iterators/generators which 
allows them to code in a more convenient style and have the compiler 

http://www.ondotnet.com/pub/a/dotnet/2004/06/07/liberty.html
http://msdn2.microsoft.com/en-us/library/dscyy5s0.aspx
http://www.c-sharpcorner.com/UploadFile/rmcochran/yieldreturn04022006113850AM/yieldreturn.aspx?ArticleID=4617984b-2209-4211-9d08-8f06e0fe2da5

   Python has the same thing now: 
http://www.python.org/doc/current/ref/yield.html

   It turns out this is great to fully leverage multi core with optimal 
utilization of system threads while having a lean app. Just read about CCR:


"The Concurrency and Coordination Runtime (CCR) is a lightweight 

Chrysanthakopoulos in the Advanced Strategies group at Microsoft. Here 
http://channel9.msdn.com/ShowPost.aspx?PostID=143582 , we have a deep 
discussion about CCR with George, a Software Architect, and Satnam 
Singh, Architect. You can get more info about CCR on the CCR Wiki 
http://channel9.msdn.com/wiki/default.aspx/Channel9.ConcurrencyRuntime . 
This is super cool stuff and represents a really innovative approach to 
making managed threaded programming more readily understandable and 
predictable.

Please check out the OOPSLA/SCOOL paper on the CCR
http://research.microsoft.com/~tharris/scool/papers/sing.pdf .

Click here http://channel9.msdn.com/Showpost.aspx?postid=206574 to see 
how the CCR is being used by the Microsoft Robotics Group."

CCR Programming http://channel9.msdn.com/ShowPost.aspx?PostID=219308

     * article: 
http://msdn.microsoft.com/msdnmag/issues/06/09/ConcurrentAffairs/default.aspx

(Relates to Stackless Python too: http://www.stackless.com/)



   So, I wonder if D plans to add this feature too? It would be neat to 
have a port of CCR to D, but that would require delegates and also yield 
support. Check out at least the link 
http://msdn.microsoft.com/msdnmag/issues/06/09/ConcurrentAffairs/default.aspx

   Thanks,

marcio
Sep 04 2006
next sibling parent reply Walter Bright <newshound digitalmars.com> writes:
I've thought of doing generators, but they're a 2.0 or later feature. 
They're a lot of work to implement.
Sep 04 2006
parent reply Marcio <mqmnews123 sglebs.com> writes:
Walter Bright wrote:

 I've thought of doing generators, but they're a 2.0 or later feature. 
 They're a lot of work to implement.



I am curious... Do you have references to papers on the implementation 
tricks needed?

I believe they were first implemented in Barbara Liskov's CLU? 
http://www.lcs.mit.edu/publications/pubs/pdf/MIT-LCS-TR-561.pdf

marcio
Sep 05 2006
parent reply Bruno Medeiros <brunodomedeiros+spam com.gmail> writes:
Marcio wrote:

 Walter Bright wrote:

 I've thought of doing generators, but they're a 2.0 or later feature. 
 They're a lot of work to implement.


 
 
 I am curious... Do you have references to papers on the implementation 
 tricks needed?
 
 I believe they were first implemented in Barbara Liskov's CLU? 
 http://www.lcs.mit.edu/publications/pubs/pdf/MIT-LCS-TR-561.pdf
 
 marcio


One of the things needed for sure is heap frames.

-- 
Bruno Medeiros - MSc in CS/E student
http://www.prowiki.org/wiki4d/wiki.cgi?BrunoMedeiros#D
Sep 05 2006
parent reply Walter Bright <newshound digitalmars.com> writes:
Bruno Medeiros wrote:

 Marcio wrote:

 Walter Bright wrote:

 I've thought of doing generators, but they're a 2.0 or later feature. 
 They're a lot of work to implement.



 I am curious... Do you have references to papers on the implementation 
 tricks needed?

 I believe they were first implemented in Barbara Liskov's CLU? 
 http://www.lcs.mit.edu/publications/pubs/pdf/MIT-LCS-TR-561.pdf

 marcio


 
 One of the things needed for sure is heap frames.


That's right, instead of using the stack for the locals, the heap is 
used. It isn't that much different from using a functor. In fact, now 
that I think about it, a functor might be a better way to do it than yield.
Sep 05 2006
parent reply Marcio <mqmnews123 sglebs.com> writes:
Walter Bright wrote:

 One of the things needed for sure is heap frames.


 
 That's right, instead of using the stack for the locals, the heap is 
 used. It isn't that much different from using a functor. In fact, now 
 that I think about it, a functor might be a better way to do it than yield.



	Smalltalk blocks, basically.

	But Smalltalk blocks prevented you from returning from the same 
enclosing method more than once. I wonder if the yield generator, with 
multiple yield return points, requires one to relax that or if it is 
just a compiler bag of tricks to provide such an illusion. In other 
words, Smalltalk has blocks but no syntax to do yield/return generators 
from a regular method. There must be extra tricks needed?

	Basically I think that yield/return (generators) are a high level 
mechanism, desirable even if your language has "functors".

marcio
Sep 05 2006
parent reply Steve Horne <stephenwantshornenospam100 aol.com> writes:
On Tue, 05 Sep 2006 21:24:39 -0400, Marcio <mqmnews123 sglebs.com>
wrote:


Walter Bright wrote:

 One of the things needed for sure is heap frames.


 
 That's right, instead of using the stack for the locals, the heap is 
 used. It isn't that much different from using a functor. In fact, now 
 that I think about it, a functor might be a better way to do it than yield.



	Smalltalk blocks, basically.


I don't think so.

For each instance of a generator, you need a complete separate stack.
That stack is kept on the heap, separate from the normal processor
stack. Both have to be full stacks, since both contexts need to
support function calls - even recursion - independently. Even though
the generator itself is likely to be a single function with yields
done directly from itself, it still needs to call normal functions to
do its stuff.

It's a long time since I used smalltalk, and I never used it much
anyway, but aren't blocks basically a kind of closure thing? That is,
they hold parameters and locals in heap-allocated memory, but without
stacking support - just single fixed-size frame?

I seem to remember it as some kind of
anonymous-functions-with-closures hack.


By the way...


In Python, you can write something like this...

  x = First (i for i in xrange(100) if Acceptable (i))

This bit...

  i for i in xrange(100) if Acceptable (i)

...is a generator expression, and closely related to the following
list comprehension...

  [i for i in range(100) if Acceptable (i)]

Which builds a list of all 'acceptable' values of i in the range 0 to
99 inclusive. The generator expression differs in that it only
generates values as they are needed. It doesn't build the whole list.
It is 'lazy'.

The 'First' function would be written as...

  def First (p) :
    return p.next ()

That only generates enough results to find the first acceptable value.

Personally, I think Pythons generator expressions are an extremely
important language feature. They remind me of the language that, to
me, defines generator-obsessive programming - Icon. But Pythons
generator expressions have a much more intuitive syntax, since Python
doesn't obsess - it simply provides.

My vote is that, if D gets generators, it should also get some kind of
generator expression as a way of creating anonymous generators.

But first, Walter needs to concentrate on achieving immortality, so he
has time to do all this ;-)

-- 
Remove 'wants' and 'nospam' from e-mail.
Sep 06 2006
parent reply Marcio <mqmnews123 sglebs.com> writes:
Steve Horne wrote:

 On Tue, 05 Sep 2006 21:24:39 -0400, Marcio <mqmnews123 sglebs.com>
 wrote:
 

 Walter Bright wrote:

 One of the things needed for sure is heap frames.


 That's right, instead of using the stack for the locals, the heap is 
 used. It isn't that much different from using a functor. In fact, now 
 that I think about it, a functor might be a better way to do it than yield.


 	Smalltalk blocks, basically.


 
 I don't think so.



	I was saying a functor would be a smalltalk block. But I still inquire 
if that is really enough for generators, and I am not sure. So, we are 
not disagreeing (you and me). Maybe we are disagreeing with Walter's 
claim that just a functor is enough.

	Having said that...


 For each instance of a generator, you need a complete separate stack.
 That stack is kept on the heap, separate from the normal processor
 stack. Both have to be full stacks, since both contexts need to
 support function calls - even recursion - independently. Even though
 the generator itself is likely to be a single function with yields
 done directly from itself, it still needs to call normal functions to
 do its stuff.


	... Perhaps the caller will see its runtime stack used by the generator 
as it runs until its next yield/return. So, the environments are 
maintained in the heap and survive the return (therefore values of 
variables are remembered) while the stack used between 2 yield/returns 
is borrowed from the caller's stack. So, in this case Walter would be right.

	Anyway, that is why I was curious about code generation tricks. I guess 




 But first, Walter needs to concentrate on achieving immortality, so he
 has time to do all this ;-)



	Exactly!! :-)

marcio
Sep 06 2006
parent Marcio <mqmnews123 sglebs.com> writes:
	Indeed a single stack can be used if you impose limitations. See what 
Barbara Liskov says in "A History of CLU":

http://www.lcs.mit.edu/publications/pubs/pdf/MIT-LCS-TR-561.pdf#search=%22A%20History%20of%20CLU%22

3.10. Iterators
"Iterators are related to coroutines; the iterator and the body of the 
for loop pass control back and forth.
However, their use is limited so that CLU programs can make do with a 
single stack."
[...]
"Imposing the limitations on iterators was done to get the efficient, 
single stack
implementation, albeit at the expense of some expressive power."

And she credits the original invention to Alphard:
[Shaw, 1977]
Shaw, Mary, William Wulf, and Ralph London, Abstraction and Verification 
in Alphard: Defining and Specifying Iteration and Generators, 
Communications of the ACM, 20:8, August 1977.

marcio

Marcio wrote:

     I was saying a functor would be a smalltalk block. But I still 
 inquire if that is really enough for generators, and I am not sure. So, 
 we are not disagreeing (you and me). Maybe we are disagreeing with 
 Walter's claim that just a functor is enough.
 
     Having said that...
 
  > For each instance of a generator, you need a complete separate stack.
  > That stack is kept on the heap, separate from the normal processor
  > stack. Both have to be full stacks, since both contexts need to
  > support function calls - even recursion - independently. Even though
  > the generator itself is likely to be a single function with yields
  > done directly from itself, it still needs to call normal functions to
  > do its stuff.
  >
 
     ... Perhaps the caller will see its runtime stack used by the 
 generator as it runs until its next yield/return. So, the environments 
 are maintained in the heap and survive the return (therefore values of 
 variables are remembered) while the stack used between 2 yield/returns 
 is borrowed from the caller's stack. So, in this case Walter would be 
 right.
Sep 11 2006
prev sibling parent reply Mikola Lysenko <mclysenk mtu.edu> writes:
You may be interested in a library I wrote some time ago for D known as 
StackThreads.  It solves exactly this problem.  You can get it from my 
website at www.assertfalse.com .
Sep 04 2006
parent reply Marcio <mqmnews123 sglebs.com> writes:
Mikola Lysenko wrote:

 You may be interested in a library I wrote some time ago for D known as 
 StackThreads.  It solves exactly this problem.  You can get it from my 
 website at www.assertfalse.com .



	Neat, thanks. I had seen your post before already. But I want to 
leverage multi core etc. CCR actually does this really well. Also, the 
yield return in generators are not the same as the yield in coroutines. 
They are much higher level to the end user.

	Also: do you use a stack or the heap? It was not clear from the FAQ, 
although the delegate example suggests you rely on 1 thread and 
therefore its stack. One of the problems with threads is that you pay 
the price of a stack in advance, instead of as you go (N threads means N 
stacks sparsely used). Contrast this with Stackless Python for example, 
which uses continuation passing & the heap. If I understood your FAQ, 
you use 1 Thread so just 1 stack, but on the other hand you can't 
leverage multi core because of that.

marcio
Sep 05 2006
parent Mikola Lysenko <mclysenk mtu.edu> writes:
Marcio wrote:

     Neat, thanks. I had seen your post before already. But I want to 
 leverage multi core etc. CCR actually does this really well. Also, the 
 yield return in generators are not the same as the yield in coroutines. 
 They are much higher level to the end user.
 
     Also: do you use a stack or the heap? It was not clear from the FAQ, 
 although the delegate example suggests you rely on 1 thread and 
 therefore its stack. One of the problems with threads is that you pay 
 the price of a stack in advance, instead of as you go (N threads means N 
 stacks sparsely used). Contrast this with Stackless Python for example, 
 which uses continuation passing & the heap. If I understood your FAQ, 
 you use 1 Thread so just 1 stack, but on the other hand you can't 
 leverage multi core because of that.
 
 marcio
 


I believe there is a misunderstanding.  The objective of StackThreads is 
to give a program more than one stack - for exactly the reasons you have 
listed.

All stack memory is heap allocated inside the StackContext.  As you 
create contexts, you will allocate more stacks.  Each context can be 
considered a continuation.  Daniel Keep has already demonstrated a 
coroutine/generator system based on the library which is included with 
version 0.2.

At the moment it is single threaded because D lacks a decent thread 
local storage mechanism.  It would be trivial to make the implementation 
thread safe if it is ever added.  (Only 2 lines of code would need to 
change.)  One work around would be to integrate the StackContext object 
with std.thread by adding the necessary members to Phobos' Thread 
object, but this is strictly DIY.
Sep 05 2006