kris wrote:
>> 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?

If the source to that function is not known to the compiler, then yes.

Walter Bright wrote:
> kris wrote:
> 
>>> 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?
> 
> 
> If the source to that function is not known to the compiler, then yes.

Aye; that's a tough one.

On the one hand it's certainly 'safer' to rely on analysis only. On the other, there's a lot of good reason to support a means to disable the analysis (for known cases) thus ensuring a stack-frame instead. The latter could be fraught with issue, though; just like the former.

I'm hoping there's another option, better than both the above (or the above combination) ~ it's seems apparent that neither present an ideal resolution

On 2006-08-16 07:55:38 -0700, "Mikola Lysenko" <mclysenk@mtu.edu> said:

> D's delegates are great.  They are vastly superior to C++'s confused pointer-to-member functions, and much more useful than Java's adapter classes.  In the world of system programs, nothing comes close.  One interesting type of delegate is the anonymous-nested-delegate-literal, or "lambda" delegate.  For those unacquainted with such niceties, here are the documentation links:
> http://www.digitalmars.com/d/function.html#nested
> http://www.digitalmars.com/d/expression.html#FunctionLiteral
> 
> 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 sequence
>     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:
> 
> Button createButton(char[] click_msg)
> {
>     Button b = new Button();
>     b.mouseClickCallback = { MsgBox(click_msg); };
>     return b;
> }
> 
> Once more, this sort of method relies on access to the outer function scope from within the lambda delegate.  Given the current semantics, this code is doomed to fail in any number of random ways.  As a final example, suppose we want to perform a lengthy calculation in a separate thread, and only wait for the value once it is needed.  In this case, one could try to do the following:
> 
> int[] delegate() sort_threaded(int[] array)
> {
>     int[] result = array.dup;
> 
>     //Create and run a worker thread to perform an expensive operation, (in this case a sort)
>     Thread tsort = new Thread(
>      {
>         result.sort;
>         return 0;
>      });
>     tsort.start();
> 
>     //The returned lambda delegate waits for the thread's calculation to finish, then returns the result.
>     return { tsort.wait; return result; };
> }
> 
> In this situation, we can let the thread execute in the background while the program performs other tasks, and only wait for the result once we need it. This type of deferred calculation can be very useful for improving the amount of parallelism within an application without adding much synchronization overhead.  It is very sad that none of these examples work, since there are so many nice solutions just like them.
> 
> One possible solution is to allocate the frame for each function containing nested-functions on the heap.  This allows any returned delegates to use the member variables freely.  One could think of it as translating the function into a class with a thunk.  Here is above Fibonacci function rewritten in this way:
> 
> class fibs_
> {
>     int a = 0;
>     int b = 1;
> 
>     int lambda1()
>     {
>         int c = a + b;
>         a = b;
>         b = c;
>         return c;
>     }
> 
>     int delegate() func()
>     {
>         return &lambda1;
>     }
> }
> 
> int delegate() fibs()
> {
>     return (new fibs_()).func();
> }
> 
> Such a translation is possible for any of these examples, albeit quite tedious.  From what I gather C# applies a similar technique with its lambda delegates and inner classes.  For a machine code compiler, such a rewrite is not even necessary, since it could simply overwrite the frame pointer at the start of the function with a GC allocated block.  This would preserve frame-based addressing for arguments and variables, requiring no change in any of the internally generated machine code.  The run time overhead is fairly low, only on the order of one extra memory allocation per function call.  Practically, such an implementation would be extremely simple.
> 
> Any thoughts or comments?
> 
> -Mikola Lysenko

Perl has this same problem.    May be of use to look at how perl solves it.

kris wrote:
> I'm hoping there's another option, better than both the above (or the above combination) ~ it's seems apparent that neither present an ideal resolution

Delegates are a pretty advanced programming technique. I don't think it would be bad solution to just let the programmer mark the exceptional cases. At least until a fail-safe general solution becomes available.

L.

Mikola Lysenko wrote:
<snip>
>     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
>     };
<snip>

Is it my imagination, or does this create yet another ambiguity in the D syntax?

    { ... } + 69;

Is this one ExpressionStatement containing an AddExpression, or a BlockStatement followed by an ExpressionStatement containing a UnaryExpression?  OK, so neither makes semantic sense, but it still needs defining at the syntactic level.

Stewart.

pragma wrote:
> 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.
> 
> 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.

I do like this idea the best, but here are some of the problems that occurred to me:

    void setCallback( void delegate() dg )
    {
        callback = new dg;
    }

    void evilFn1()
    {
        int callCount = 0;

        void dg()
        {
            callCount++;
        }

        setCallback( &dg );

        while( true )
        {
            Thread.sleep( 1000 );
            printf( "Called %d times.\n", callCount );
        }
    }

    void evilFn2()
    {
        int[10] buf;
        int* cur = &buf[0];

        void dg()
        {
            printf( "%d\n", *cur );
            if( ++cur > &buf[9] )
                cur = &buf[0];
        }

        initBuf( buf );
        setCallback( &dg );
    }

Since my original proposal was to create a dynamic copy of the stack frame for delegates as needed after the original stack frame had been created, it assumed that the original stack frame would be gone or irrelevant when the delegate was called.  In evilFn1, such behavior would result in "Called 0 times." being printed regardless of the number of times the delegate is called.  evilFn2 demonstrates that a memcpy of the stack frame may not be sufficient to preserve intended behavior.  I do think both of these could probably be overcome with fancier code generation, but they would make the code complex and somewhat non-obvious to a debugger.  I still like this idea the best because it allows the programmer aware that the frame must be preserved to do so, but someone would have to resolve the above problems to make it correct and safe.  And I didn't even mention the problems with passing a delegate from a struct on the stack or a class constructed in-place on the stack with alloca.


Sean

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

Note: C# doesn't allocate the *whole* (outer) frame on the stack or on the heap. It will allocate on the heap only those variables that are accessed by a delegate literal, which are called outer variables (and are said to be "captured" or "lifted"). The delegate's (own) frame, is normal I believe, unless it also has delegate literals.

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

Also, such analysis would also be useful for object (and data) allocation, as the concept (and the compiler checking method too, I think) is pretty much the same. (A new'ed object
can be allocated on the stack, if it is determined that it does not escape).

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

kris wrote:
> 
> On the one hand it's certainly 'safer' to rely on analysis only. On the other, there's a lot of good reason to support a means to disable the analysis (for known cases) thus ensuring a stack-frame instead. The latter could be fraught with issue, though; just like the former.
> 
> I'm hoping there's another option, better than both the above (or the above combination) ~ it's seems apparent that neither present an ideal resolution

This is what prompted my 'archive' solution that turned out to be problematic, but I'm hoping the same thing.  I don't find any of the other suggestions terribly appealing.


Sean

kris wrote:
> Walter Bright wrote:
>> kris wrote:
>>
>>>> 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?
>>
>>
>> If the source to that function is not known to the compiler, then yes.
> 
> Aye; that's a tough one.
> 
> On the one hand it's certainly 'safer' to rely on analysis only. On the other, there's a lot of good reason to support a means to disable the analysis (for known cases) thus ensuring a stack-frame instead. The latter could be fraught with issue, though; just like the former.
> 

Hum, taking a clue that this problem is very similar to object(and data) allocation, one possibility is for both work the same way:
Outer variables be heap-allocated by default (like new), and stack-allocated when escape analysis determines that is safe, or when the user explicitly states it with the auto(raii) keyword:

void func() {
  auto int x; // x is not heap-allocated, no matter what.
  int y;      // y is stack-allocated, as it is not an outer var
  doSomething( { return x++; } ); //thus this dg literal is synchronous
}

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

Bruno Medeiros wrote:
> 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)

Forget this idea, it is crappy, for several reasons.

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