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

Mikola Lysenko wrote:

> 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

I agree that the current spec allows you to very easily write very elegant code that will be broken. Your proposed solution seems to me to be a well thought out (and acceptable) solution to make them actually work (and keep D as a language ahead of the pack, as the other alternatives most probably are to either create not-so-elegant syntax, or disallow them altogether).

-- 
Lars Ivar Igesund
blog at http://larsivi.net
DSource & #D: larsivi

Mikola Lysenko wrote:
[...]
> All the syntactic sugar is nice, but it also lays a few traps for the unwary.
[...]
> 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;
> }
> 
[...]
> 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; };
> }
> 
[...]
> 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.  
[...]
> Such a translation is possible for any of these examples, albeit quite tedious.  
[...]
> 
> Any thoughts or comments?
> 
> -Mikola Lysenko 
> 
> 

Interesting ideas, however using a struct rather than a class would be faster.

Maybe what is needed is some way to define the context pointer of a delegate literal.


int[] delegate() sort_threaded(int[] array)
{
    auto foo = new struct   // this might need new syntax
    {
        int[] result;
        Thread tsort;
    };

    with(foo)
    {
        result = array.dup;
                            // delegate with alt context
        tsort = new Thread(foo.{
            result.sort;
            return 0;
        });
        tsort.start();
    }
                            // delegate with alt context
    return foo.{
        // array[0];        // not in scope
        tsort.wait;
        return result;
    };
}


This would also work on another of the examples:

Button createButton(char[] click_msg)
{
    Button b = new Button();
    b.mouseClickCallback = click_msg.{ MsgBox(this); };
    return b;
}


for the first example some sort of joining of the anon struct deceleration and with statement might make this vary elegant


int[] delegate() sort_threaded(int[] array)
{
        // (using mixin for lack of a better syntax)
        // inject these into the namespace,
        //but put them on the heep
    mixin foo = new struct
    {
        int[] result;
        Thread tsort;
    };

    result = array.dup;
    tsort = new Thread(foo.{
        result.sort;
        return 0;
    });

    tsort.start();

    return foo.{
        tsort.wait;
        return result;
    };
}

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


Yeah, this is a serious trap for the unwary and, unfortunately, prohibits the use of such delegates in the one place where the elegance would be most notable: as gui callbacks, per your example. As you say, the way around it (currently) is to create a class to house the 'scope' content, or otherwise refer to it. That's unweildy, even with anonymous-class syntax.

If, as you suggest, D had some means to indicate that the scope should be placed on the heap instead of the stack, it would resolve the concern nicely. Perhaps that indication might be lambda syntax itself? For example, in C# the lambda indicator is the symbol '=>'

Either way, if D could safely utilize lambda delegates for, say, gui work (or any design based around callbacks) it would be immediately noticable as both an elegant solution & a big step up from C++

Good idea, Mikola

Mikola Lysenko wrote:
> 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?

Yes, I'm aware of this, and want to fix it for D 2.0. The way to fix it is, as you suggest, allocating the frame on the heap rather than on the stack. The drawback with that is that heap allocation is far, far more expensive than stack allocation.

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.

Of course, then there's the problem of nested functions within nested functions, that then escape and try to reference multiple nesting levels back on the stack.

kris wrote:

> Yeah, this is a serious trap for the unwary and, unfortunately, prohibits the use of such delegates in the one place where the elegance would be most notable: as gui callbacks, per your example. As you say, the way around it (currently) is to create a class to house the 'scope' content, or otherwise refer to it. That's unweildy, even with anonymous-class syntax.
> 
> If, as you suggest, D had some means to indicate that the scope should be placed on the heap instead of the stack, it would resolve the concern nicely. Perhaps that indication might be lambda syntax itself? For example, in C# the lambda indicator is the symbol '=>'

I don't think any special syntax is needed. I believe the compiler could be able to automatically identify whether a function may have escaping delegates referring to local variables.

/Oskar

Oskar Linde wrote:
> kris wrote:
> 
> 
>>Yeah, this is a serious trap for the unwary and, unfortunately,
>>prohibits the use of such delegates in the one place where the elegance
>>would be most notable: as gui callbacks, per your example. As you say,
>>the way around it (currently) is to create a class to house the 'scope'
>>content, or otherwise refer to it. That's unweildy, even with
>>anonymous-class syntax.
>>
>>If, as you suggest, D had some means to indicate that the scope should
>>be placed on the heap instead of the stack, it would resolve the concern
>>nicely. Perhaps that indication might be lambda syntax itself? For
>>example, in C# the lambda indicator is the symbol '=>'
> 
> 
> I don't think any special syntax is needed. I believe the compiler could be
> able to automatically identify whether a function may have escaping
> delegates referring to local variables. 
> 
> /Oskar
> 

Yes, that's certainly one way. But the suggestion was to "take advantage" of an even simpler form of lambda delegates; one that C# 3.0 is moving toward. It's worth taking a look at, just for comparitive purposes? Two random links:

http://www.interact-sw.co.uk/iangblog/2005/09/30/expressiontrees
http://www.developer.com/net/csharp/article.php/3598381

On the other hand, one of the great things about the D compiler is it's voracious speed. If it turns out that automagically trying to figure out where the 'escapees' are will noticably slow the compiler down, then a bit of syntactic sugar might make all the difference :)

Walter Bright wrote:
> Mikola Lysenko wrote:
> 
>> 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?
> 
> 
> Yes, I'm aware of this, and want to fix it for D 2.0. The way to fix it is, as you suggest, allocating the frame on the heap rather than on the stack. The drawback with that is that heap allocation is far, far more expensive than stack allocation.

because this is so much slower, I would hate to see it happen silently. Having a function use a heap-frame just because I add a delegate could cause some hard to track down performance hits. I would advocate making the escaping delegate illegal unless the code explicitly says to put /part/ or all of the frame on the heap.

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




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;}; }
//	int delegate() fig(){ return this.{return i;}; }  // this maybe?
}

void main()
{
	auto foo = new Foo;
	auto farm = foo.fig;

	foo.i = 5;
	auto i = farm(); // valid if context is "foo"
	assert(i == 5);
}

Walter Bright wrote:
> Mikola Lysenko wrote:
>> 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?
> 
> Yes, I'm aware of this, and want to fix it for D 2.0. The way to fix it is, as you suggest, allocating the frame on the heap rather than on the stack. The drawback with that is that heap allocation is far, far more expensive than stack allocation.

In the general case, yes, but it doesn't have to be.  An allocator with per-thread heaps could allocate without the need for a mutex, and special cases like this could force an allocation if the heap is full instead of triggering a collection.  That said, I agree with your motivation here.

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

Agreed.  As well as detect whether the delegates reference any local stack data in the first place.  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.

> Of course, then there's the problem of nested functions within nested functions, that then escape and try to reference multiple nesting levels back on the stack.

I would expect the compiler to just put as much data on the heap as necessary, be it for a single nesting level or for multiple levels.  I suppose it would be ideal for this to be contiguous, but it wouldn't have to be.  I grant that the code generation may be a bit of a pain, but it doesn't sound impossible.


Sean

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.

> //    int delegate() fig(){ return this.{return i;}; }  // this maybe?
> }
> 
> void main()
> {
>     auto foo = new Foo;
>     auto farm = foo.fig;
> 
>     foo.i = 5;
>     auto i = farm(); // valid if context is "foo"
>     assert(i == 5);
> }