Mikola Lysenko wrote:
> "Walter Bright" <newshound@digitalmars.com> wrote in message news:ebvl5s$2k03$1@digitaldaemon.com...
>> An ideal solution would be if the compiler could statically detect if a nested class reference can 'escape' the stack frame, and only then allocate on the heap. Otherwise, the current (very efficient) method of just passing a frame pointer would be employed.
>>
> 
> Well, in general it is not decidable if a given nested function escapes. Here is a trivial example:
> 
> void delegate() func(void delegate() F)
> {
>     F();
>     return { F(); };
> }
> 
> This function will only return a delegate when F halts. One conservative 

I do not understand why or how this is undecidable. It seems clear that a delegate escapes (the literal delegate).

> strategy is to simply look for any nested function declarations in the function's lexical extent.  If such a declaration exists, then that function must be heap allocated.  I suspect that this is how C# handles the problem.
> 

Yes, that's idea that should be effective enough, if one wants language auto-detection of heaped functions.

> Another possibility is to add a special attribute modifier to the declaration of the initial function.  This places the burden of determining 'escapism' on the programmer instead of the compiler, and is probably the simplest to implement.
> 
> Perhaps the most flexible solution would be a combination of both approaches.  By default, any function containing a nested function declaration gets marked as heap allocated - unless it is declared by the programmer to be stack-based.  For this purpose, we could recycle the deprecated 'volatile' keyword.  Here is an example:
> 
> volatile void listBATFiles(char[][] files)
> {
>     foreach(char[] filename; filter(files,  (char[] fname)  { return fname[$-3..$] == "BAT"; })
>         writefln("%s", filename);
> }
> 
> In this case, we know that the anonymous delegate will never leave the function's scope, so it could be safely stack allocated.  Philosophically, this fits with D's design.  It makes the default behavior safe, while still allowing the more dangerous behavior when appropriate.
> 
> 

'volatile' is a crappy name IMO.

Consider this function:
  volatile void delegate() func(int b);
is func "heaped"(volatile), or is the return value dg type heaped? This may lend to some ambiguities.
Another option is for the specifier to be postfixed. Supose that NEW means heaped, and AUTO means stack framed:
  void delegate() AUTO func(int b) NEW;
(note AUTO is default and thus redundant)
I do not know for sure the implications in terms of grammar parsing for each of these alternatives, Walter should know better.

-- 
Bruno Medeiros - MSc in CS/E student
http://www.prowiki.org/wiki4d/wiki.cgi?BrunoMedeiros#D

Mikola Lysenko wrote:

> Recent D releases (notably 0.161) have updated the syntax and improved the overall usability of lambda delegates. All the syntactic sugar is nice, but it also lays a few traps for the unwary.  Here is a simple example:
> 
> // The Fibonacci numbers are an integer sequence such that
> //        F(n) = F(n - 1) + F(n - 2)
> //        And F(0) = 0, F(1) = 1
> int delegate() fibs()
> {
>     int a = 0;            // Initialize the last two terms of the Fibonacci     int b = 1;
> 
>     return
>     {
>         int c = a + b;     // Calculate the next term in the sequence
>         a = b;               // Shift the previous terms back
>         b = c;
>         return c;            // Return the result
>     };
> }
> 
> This function returns a function which will sequentially evaluate all of the Fibonacci numbers.  Notice that the inner delegate modifies the variables a and b in fibs() scope.  Because of this, it is not guaranteed to work after fibs returns.  This is most irritating, and it greatly restricts the use of this technique. Another potential use for lambda delegates is to create one-line adapter methods.  Consider the following attempt to create a button which will display an arbitrary message when clicked:

It took me awhile to get what you were doing but it is elegant -- or would be if it worked. I am sure I am missing something however so I hope you might explain why using static storage is not sufficient:

int delegate() fibs()
{
  return
  {
    static int a = 0;
    static int b = 1;
    int c = a + b;
    a = b;
    b = c ;
    return c;
  };
}

Sean Kelly wrote:
> 
> Upon further reflection (and some helpful criticism) this doesn't seem like it may not work so well with delegates from structs and classes. But I do like the general idea better than that of flagging the delegates upon declaration or something like that.  I don't suppose the idea could be somehow refined to eliminate these problems?

Forget I suggested this idea :-p  I forgot about problems like self-referent stack data and such where a simple copy wouldn't work. Not to mention that the surrounding function may not return right away and would be working on a different copy of the data than any delegates it may have passed.


Sean

nobody wrote:
> Mikola Lysenko wrote:
> 
>> Recent D releases (notably 0.161) have updated the syntax and improved the overall usability of lambda delegates. All the syntactic sugar is nice, but it also lays a few traps for the unwary.  Here is a simple example:
>>
>> // The Fibonacci numbers are an integer sequence such that
>> //        F(n) = F(n - 1) + F(n - 2)
>> //        And F(0) = 0, F(1) = 1
>> int delegate() fibs()
>> {
>>     int a = 0;            // Initialize the last two terms of the Fibonacci     int b = 1;
>>
>>     return
>>     {
>>         int c = a + b;     // Calculate the next term in the sequence
>>         a = b;               // Shift the previous terms back
>>         b = c;
>>         return c;            // Return the result
>>     };
>> }
>>
>> This function returns a function which will sequentially evaluate all of the Fibonacci numbers.  Notice that the inner delegate modifies the variables a and b in fibs() scope.  Because of this, it is not guaranteed to work after fibs returns.  This is most irritating, and it greatly restricts the use of this technique. Another potential use for lambda delegates is to create one-line adapter methods.  Consider the following attempt to create a button which will display an arbitrary message when clicked:
> 
> It took me awhile to get what you were doing but it is elegant -- or would be if it worked. I am sure I am missing something however so I hope you might explain why using static storage is not sufficient:
> 
> int delegate() fibs()
> {
>   return
>   {
>     static int a = 0;
>     static int b = 1;
>     int c = a + b;
>     a = b;
>     b = c ;
>     return c;
>   };
> }
> 

For starters, a delegate can access the outer function arguments, but those arguments cannot be made static.

And then there will only be one "instance" of the returned delegate (think of the delegate as an object). Any call to it will update only one single sequence:

  auto dg1 = fibs();
  auto dg2 = fibs();
  dg1(); // 1
  dg1(); // 2
  dg2(); // 3
  dg2(); // 5

However, with proper "heaped" frames, there are many delegate (outer frame) "instances":

  auto dg1 = fibs();
  auto dg2 = fibs();
  dg1(); // 1
  dg1(); // 2
  dg1(); // 3
  dg2(); // 1
  dg2(); // 2
  dg2(); // 3



-- 
Bruno Medeiros - MSc in CS/E student
http://www.prowiki.org/wiki4d/wiki.cgi?BrunoMedeiros#D

BCS wrote:
> Walter Bright wrote:
>> BCS wrote:
>>
>>> BTW how do you construct a delegate literal inside of a class method that uses "this" as it's context, rather than the frame pointer?
>>>
>>> class Foo
>>> {
>>>     int i;
>>>     int delegate() fig(){ return {return i;}; }
>>
>>
>> It uses the frame pointer of fig() to access fig()'s this. Of course, though, this will currently fail because fig() is exited before the delegate is called.
>>
> 
> a.k.a. It can't be done?

It's the same problem as elsewhere returning a delegate that accesses the frame of the function that returns it.

Sean Kelly wrote:
> Walter Bright wrote:
>> Sean Kelly wrote:
>>> The alternative would be to use a separate keyword for these delegates, 'closure' or 'lambda' or some such, but that's potentially confusing, and leaves anonymous delegates in an odd position.
>>
>> I *really* want to avoid having to do this. It's almost guaranteed that it'll be a rich source of bugs.
> 
> As an alternative, since it's really how the delegate is used that's at issue, perhaps the programmer could simply be given a way to manually "archive" the stack frame used by a delegate if he knows it will need to be called asynchronously?  From the original example:
> 
>     Button createButton(char[] click_msg)
>     {
>         Button b = new Button();
>         b.mouseClickCallback = { MsgBox(click_msg); };
>         return b;
>     }
> 
> Let's assume mouseClickCallback is written like so:
> 
>     void mouseClickCallback( void delegate() dg )
>     {
>         clickHandler = dg;
>     }
> 
> Following my suggestion, it would be changed to this:
> 
>     void mouseClickCallback( void delegate() dg )
>     {
>         dg.archive;
>         clickHandler = dg;
>     }
> 
> The archive routine would check dg's stack frame to see if a heap copy of the frame exists (assume it's stored as a pointer at this[0]).  If not then memory is allocated, the pointer is set, the frame is copied, and dg's 'this' pointer is updated to refer to the dynamic frame. Returning a delegate from a function would just implicitly call this 'archive' routine.  This could still cause errors, as a programmer may forget to call "dg.archive" before storing the delegate, but I think this is an acceptable risk and is far better than having the compiler try to "figure out" whether such a dynamic allocation is needed.  It also seems fairly easy to implement compared to the alternatives, and offering the feature through a property method would eliminate the need for a new keyword.
> 
> 
> Sean

I haven't read the entire thread yet, but I think something like this might be the right ticket.  Although the '.archive' property might cause collisions with user code on the return type.

Wouldn't it be better if we were to overload the use of 'new' on delegates/functions to do this instead?

    void mouseClickCallback( void delegate() dg )
    {
        clickHandler = new dg; //
    }

... or do we require the use of a delegate type instead of an instance?

Either way, as 'new' is implied to do heap allocation with classes, we're now doing the same on a given delegate for it's frame.

Sean Kelly wrote:
> The archive routine would check dg's stack frame to see if a heap copy of the frame exists (assume it's stored as a pointer at this[0]).  If not then memory is allocated, the pointer is set, the frame is copied, and dg's 'this' pointer is updated to refer to the dynamic frame. Returning a delegate from a function would just implicitly call this 'archive' routine.  This could still cause errors, as a programmer may forget to call "dg.archive" before storing the delegate, but I think this is an acceptable risk and is far better than having the compiler try to "figure out" whether such a dynamic allocation is needed.  It also seems fairly easy to implement compared to the alternatives, and offering the feature through a property method would eliminate the need for a new keyword.

It's not the new keyword that's the problem - it's the fact that the programmer has to identify the delegate as special.

kris wrote:
> C# gets around all this by (it's claimed) *always* using a heap-based frame for delegates.

That's the copout solution. I find more and more nifty uses for (synchronous) delegates, and having to allocate the frames on the heap is too high a price to pay. Paying that price would preclude D from having a viable alternative to C++ expression templates, for example.

Static escape analysis can yield 3 results:

1) guaranteed to not escape
2) might escape
3) does escape

If most of the (1) cases in actual use can be reliably detected as (1), then a reasonable strategy is to do so and allocate on the stack only those proven as (1).

On Thu, 17 Aug 2006 01:15:15 +0100, Bruno Medeiros <brunodomedeirosATgmail@SPAM.com> wrote:
> nobody wrote:
>> Mikola Lysenko wrote:
>>
>>> Recent D releases (notably 0.161) have updated the syntax and improved the overall usability of lambda delegates. All the syntactic sugar is nice, but it also lays a few traps for the unwary.  Here is a simple example:
>>>
>>> // The Fibonacci numbers are an integer sequence such that
>>> //        F(n) = F(n - 1) + F(n - 2)
>>> //        And F(0) = 0, F(1) = 1
>>> int delegate() fibs()
>>> {
>>>     int a = 0;            // Initialize the last two terms of the Fibonacci     int b = 1;
>>>
>>>     return
>>>     {
>>>         int c = a + b;     // Calculate the next term in the sequence
>>>         a = b;               // Shift the previous terms back
>>>         b = c;
>>>         return c;            // Return the result
>>>     };
>>> }
>>>
>>> This function returns a function which will sequentially evaluate all of the Fibonacci numbers.  Notice that the inner delegate modifies the variables a and b in fibs() scope.  Because of this, it is not guaranteed to work after fibs returns.  This is most irritating, and it greatly restricts the use of this technique. Another potential use for lambda delegates is to create one-line adapter methods.  Consider the following attempt to create a button which will display an arbitrary message when clicked:
>>  It took me awhile to get what you were doing but it is elegant -- or would be if it worked. I am sure I am missing something however so I hope you might explain why using static storage is not sufficient:
>>  int delegate() fibs()
>> {
>>   return
>>   {
>>     static int a = 0;
>>     static int b = 1;
>>     int c = a + b;
>>     a = b;
>>     b = c ;
>>     return c;
>>   };
>> }
>>
>
> For starters, a delegate can access the outer function arguments, but those arguments cannot be made static.
>
> And then there will only be one "instance" of the returned delegate (think of the delegate as an object). Any call to it will update only one single sequence:
>
>    auto dg1 = fibs();
>    auto dg2 = fibs();
>    dg1(); // 1
>    dg1(); // 2
>    dg2(); // 3
>    dg2(); // 5
>
> However, with proper "heaped" frames, there are many delegate (outer frame) "instances":
>
>    auto dg1 = fibs();
>    auto dg2 = fibs();
>    dg1(); // 1
>    dg1(); // 2
>    dg1(); // 3
>    dg2(); // 1
>    dg2(); // 2
>    dg2(); // 3

So, the other option is:

import std.stdio;

// The Fibonacci numbers are an integer sequence such that
//        F(n) = F(n - 1) + F(n - 2)
//        And F(0) = 0, F(1) = 1
int delegate(inout int,inout int) fibs()
{
    return (inout int a, inout int b)
    {
        int c = a + b;     // Calculate the next term in the sequence
        a = b;               // Shift the previous terms back
        b = c;
        return c;            // Return the result
    };
}

void main()
{
	int a = 0,b = 1;	
	writefln(fibs()(a,b));
	writefln(fibs()(a,b));
	writefln(fibs()(a,b));
	writefln(fibs()(a,b));
	writefln(fibs()(a,b));
	writefln(fibs()(a,b));
	writefln(fibs()(a,b));
}

Right? Passing the storage location to the calls.

Regan

Walter Bright wrote:
> kris wrote:
> 
>> C# gets around all this by (it's claimed) *always* using a heap-based frame for delegates.
> 
> 
> That's the copout solution. I find more and more nifty uses for (synchronous) delegates, and having to allocate the frames on the heap is too high a price to pay. Paying that price would preclude D from having a viable alternative to C++ expression templates, for example.

I wholeheartedly agree :)


> 
> Static escape analysis can yield 3 results:
> 
> 1) guaranteed to not escape
> 2) might escape
> 3) does escape
> 
> If most of the (1) cases in actual use can be reliably detected as (1), then a reasonable strategy is to do so and allocate on the stack only those proven as (1).

Aye, but doesn't that imply a heap-frame when passing a delegate to another function, when you explicitly know all callbacks will be synchronous only?

That would not be good at all, so I hope that wouldn't be the case :(