Wednesday, February 11, 2009

Nested Functions and Delegates

My previous post missed one aspect of delegates in D: nested functions. Walter Bright gave me this example:

int delegate() foo(int i)
{
int bar() { return i; }
return &bar;
}

Function bar is nested inside foo; foo wraps bar into a delegate which is returned. My blog post is guilty of overlooking this use case for delegates; yet my compiler implementation is innocent: the example compiles and runs correctly.

The code example may look like a new use case at first, but is in fact similar to making a delegate from an object instance and a method:

class Foo {
int i;
int bar() { return i; }
}
...
Foo f = new Foo;
int delegate() dg = &f.bar;

The reason is that there is an invisible object in the nested function case. In the D programming language, nested functions have access to the surrounding lexical scope (note how function bar uses i which is declared as a parameter of foo); the .NET D compiler represents internally the lexical context of the nested function as an object. The fields of the context object are shallow copies of the variables in the "parent" scope. The IL class declaration for the context is synthesized by the compiler, which also instantiates the context. The context is populated on the way in (before calling the nested function) and used to update the variables in the parent scope on the way out (after the call has completed).

The constructor of a delegate object takes two parameters: an object reference and a pointer to a function; in the case of nested functions, the first parameter that the compiler passes under the hood is the context object. This is why constructing a delegate from a nested function is not different from using an object and one of its methods.

What if the nested function is declared inside of a class method (you ask). In this case there is no need to synthesize a class declaration to model the context of the nested call. The class to which the method belongs is augmented with hidden fields that shadow the variables in the parent scope.

3 comments:

BCS said...

there are several problems with what you describe (assuming I don't understand incorrectly). It sounds like a delegate will not effect the outer function's variable until after it returns to the outer function. what happens in the case that a delegate is called by a called thread or if it is called from another thread. As a pathological case: A thread is launched that calls a delegate that alters a flag in the outer function and then waits for another flag there to be changed. The outer function continues in the old thread an waits on the first flag an then sets the second. Under DMD this would work, but not under your implementation.

I think the correct way to make this work would be to have all variables referred to by nested function only reside in an object. All accesses, by the outer function or nested functions use this object.

The Free Meme said...

Thank you for your insight.

Your observation is accurate, the delegate (or any nested function for that matter) will not affect the outer scope until the call returns. That's when "the transaction commits".

But I do not see it as incorrect behavior, because I am not aware of any official D specification that governs the observable behavior of multi-threaded programs.

Implementation-dependent behavior is legal (albeit not necessarily fair) game.

I agree a hundred percent that in the case that you described a better design would be for shared data to reside in an object.

I would never risk having a thread accessing the local variables of some function, betting that it's activation record is valid in another thread (with or without reference counting).

The Free Meme said...

BCS,

I spent more time thinking about the problem that you outlined.

Over the weekend I had an email exchange with Walter and Bartosz on the topic of threads behavior.
It turns out that in D 2.0 when a thread is constructed from a delegate, that delegate must have a "shared" modifier (but the specifics of thread creation are not fully baked yet).

I am thinking about using the "shared" hint and construct the nested function's context in a way that avoids the problem that you so diligently identified. I will post an update when I have a working solution.