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 deal with all the pain. For an example in C# 2.0 see
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 port-based concurrency library for C# 2.0 developed by George 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

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

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 .

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

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

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

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.

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.

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

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.