The future of lambda delegates

kris foo at bar.com
Wed Aug 16 16:47:31 PDT 2006


Mikola Lysenko wrote:
> "Walter Bright" <newshound at digitalmars.com> wrote in message 
> news:ebvl5s$2k03$1 at 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 
> 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.
> 
> 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.
> 
> 


A definition
---------------

It's worth making a distinction between the two types of delegate. 
There's what I'll call the synchronous and asynchronous versions, where 
the scope of the former is live only for the duration of its "host" 
function (frame needs no preservation; how D works today). Asynchronous 
delegates can be invoked beyond the lifespan of their original host, and 
thus their frame may need to be preserved. I say 'may' because it needs 
to be preserved only if referenced.


A couple of observations
------------------------

1) seems like the use of "volatile" (above) is more attuned to an 
asynchronous invocation rather than a synchronous one? The above 
listBatFiles() example is of a synchronous nature, yes?

2) the 'qualifier' in the above example is placed upon the host, where 
in fact it is the *usage* of the delegate that is at stake. Not the fact 
that it simply exists. For example:

# foo(char[] s)
# {
#    bool isNumeric(char c) {return c >= 0 && c <= '9';}
#
#    foreach (c; s)
#             if (isNumeric(c))
#                 // do something
#                 ;
# }

In the above case, the nested isNumeric() function is clearly of the 
synchronous variety. It should use the stack, as it does today. Whereas 
this variation

# foo(Gui gui, char[] s)
# {
#    bool isNumeric(char c) {return c >= 0 && c <= '9';}
#
#    bool somethingElse() {return s ~ ": something else";}
#
#    foreach (c; s)
#             if (isNumeric(c))
#                 // do something
#                 ;
#	      else
#                {
#                funcWrittenBySomeoneElse (somethingElse);
#                break;
#                }
# }

How do you know what the else clause will do with the provided delegate? 
Is the usage-context synchronous, or will it wind up asynchronous? You 
just don't know what the function will do with the delegate, because we 
don't have any indication of the intended usage.

(please refrain from comments about indentation in these examples <g>)


Yet another strategy
--------------------

Consider attaching the qualifier to the usage point. For example, the 
decl of setButtonHandler() could be as follows:

# void setButtonHandler (volatile delegate() handler);

... indicating that the scope of an argument would need to be preserved. 
For the case of returned delegates, the decl would need to be applied to 
  the return value and to the assigned lValue:

# alias volatile delegate() Handler;
#
# Handler getButtonHandler();
#
# auto handler = getButtonHandler();

This is clearly adding to the type system (and would be type-checked), 
but it does seem to catch all cases appropriately. The other example 
(above) would be declared in a similar manner, if it were to use its 
argument in an asynchronous manner:

# void funcWrittenBySomeoneElse (delegate() other);
#
# or
#
# void funcWrittenBySomeoneElse (volatile delegate() other);

C# gets around all this by (it's claimed) *always* using a heap-based 
frame for delegates. That is certainly safe, but would be inappropriate 
for purely synchronous usage of nexted functions, due to the overhead of 
frame allocation. It depends very much on the context involved ~ how the 
delegates are actually used.










More information about the Digitalmars-d mailing list