Sunday, February 22, 2009

Reaching Closure...

A diligent reader commented on my previous post that the implementation of nested functions in D for .NET was buggy for multi-threaded programs.

Indeed, in the code below asyncWork() never returned. That's because a copy by-value of the variable go was used in the closure.

void main()
{
bool go;

void asyncWork()
{
while (!go)
{
//busy wait
}
}
Threading.Thread t = new Threading.Thread(&asyncWork);
t.Start();

go = true;
}

I am trying to avoid generating unverifiable code in this compiler project: IL does not allow managed pointers as fields in a class; ILASM accepts unmanaged pointers but that yields unverifiable code. My first instinct for closures was to use a copy for all the referenced variables, but as observed by my reader that approach did not work for multi-threaded programs.

One way to solve the problem is to use unmanaged pointers in the closure; under this implementation the example above runs correctly. There may be at least another solution: wrap each referenced variable into an object, and have both the nested function and the surrounding context share the object reference; I found it to convoluted and pursued the unmanaged pointers route instead.

This is how the generated IL looks for the D code in the example:

.module 'example'
.custom instance void [mscorlib]System.Security.UnverifiableCodeAttribute::.ctor() = ( 01 00 00 00 )


//--------------------------------------------------------------
// main program
//--------------------------------------------------------------
.method public hidebysig static void _Dmain ()
{
.entrypoint
.maxstack 3
.locals init (
[0] bool pinned 'go',
[1] class [mscorlib]System.Threading.Thread 't',
[2] class example.main.closure1 '$closure3'
)
newobj instance void example.main.closure1::.ctor()
stloc.s 2 // '$closure3'
ldloc.2 // '$closure3'
ldloca 0 // 'go'
stfld bool* 'example.main.closure1'::go2
ldloc.2 // '$closure3'
dup
ldvirtftn instance void example.main.closure1::'asyncWork' ()
newobj instance void class [mscorlib]System.Threading.ThreadStart::.ctor(object, native int)
newobj instance void [mscorlib]System.Threading.Thread::.ctor (ThreadStart)
stloc.s 1 // 't'
ldloc.1 // 't'
callvirt instance void [mscorlib]System.Threading.Thread::'Start' ()
ldc.i4 1
stloc.s 0 // 'go'
ret
}

.class private auto example.main.closure1 extends [dnetlib]core.Object
{

.method public virtual newslot hidebysig instance void 'asyncWork' ()
{
.maxstack 2
L1_example:
ldarg.0
ldfld bool* 'example.main.closure1'::go2
ldind.i1
ldc.i4 0
beq L1_example
ret
}
.field public bool* go2
// default ctor, compiler-generated
.method public hidebysig instance void .ctor()
{
ldarg.0
call instance void [dnetlib]core.Object::.ctor()
ret
}
} // end of example.main.closure1

Now there is only one more small problem to address: synchronization between threads...

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.

Tuesday, February 10, 2009

Delegates in D for .NET

This past weekend I typed "Joe Newman" in Pandora and sat down for a couple of hours to implement delegates in my .NET back-end for the D compiler.

I begun by studying the documentation on MSDN and I noticed some differences in the way delegates work in .NET and D.

In .NET (and C#) delegates are objects that wrap pointers to functions so that they can be manipulated and invoked safely. The functions may be either standalone or members of a class. In D, the concept of delegates applies only to member functions. Delegates may be called asynchronously in .NET (I am not aware of a similar feature in the D programming language). The concept of delegates is thus simpler in D.

The implementation that I came up with is straight-forward: classes that derive from [mscorlib]System.MulticastDelegate are generated for each delegate type. The classes are sealed and each have a virtual Invoke method that matches the signature of the D delegate.

For the following D code snippet

class Test
{
void fun(int i)
{ ...
...
}
}
Test t = new Test;
void delegate(int) dg = &t.fun;

the generated IL looks like this:

.class sealed $Delegate_1 extends [mscorlib]System.MulticastDelegate
{
.method public instance void .ctor(object, native int) runtime managed {}
.method public virtual void Invoke(int32) runtime managed {}
}
...
...
.locals init (
[0] class Test 't',
[1] class $Delegate_1 'dg'
)
newobj instance void delegate.Test::.ctor ()
stloc.s 0 // 't'

ldloc.0 // 't'
dup
ldvirtftn instance void delegate.Test::'print' (int32 'i')
newobj instance void class $Delegate_1::.ctor(object, native int)
stloc.1

One small (and annoying) surprise that I had was that although the IL standard contains code samples with user-defined classes derived directly from [mscorlib]System.Delegate, such code did not pass PEVERIFY and, more tragically, crashed at run-time. The error message ("Unable to resolve token", or something like that) was not helpful; but the ngen utility dispelled the confusion by stating bluntly that my class could not inherit System.Delegate directly. Replacing System.Delegate with System.MulticastDelegate closed the issue.

Once I got delegates to work for class methods, I realized that the code can be reused to support D pointers to functions as well. In D pointers to functions are a different concept from delegates; in .NET however, a delegate can be constructed from a standalone function by simply passing a null for the object in the constructor. It is trivial for the compiler to generate code that instantiates .NET delegates in lieu of function pointers.

One nice side-effect of representing pointers to functions as delegates is that they can be aggregated as class members, unlike pointers to other data types that cannot be aggregated as struct or class fields (an IL-imposed restriction for managed pointers).

I hope that one day D decides to support asynchronous delegate calls. I have yet to imagine the possibilities for asynchronous, pure methods.

Until then, the .NET back-end is moving along getting closer and closer to a public release.

Sunday, February 08, 2009

D-elegating Constructors

The D programming language allows a constructor of a class to call another constructor of the same class, for the purpose of sharing initialization code. This feature is called "delegating constructors"; it is also present in C# and in the emerging C++ 0x.

C#'s syntax for delegating constructors resembles the initializer lists in C++, and strictly enforces that the delegated constructor is called before any other code in the body of the caller constructor; the feature is masterfully explained in More Effective C#: 50 Specific Ways to Improve Your C# (Effective Software Development Series).

D is more flexible, a constructor can be called from another constructor's body pretty much like any other "regular" method, provided that some simple rules are observed (for example, it is not permitted to call a constructor from within a loop).

A D compiler must detect constructor delegation and ensure that some initialization code is not executed more than once. Let's consider an example:

class Example
{
int foo = 42;
int bar;

this()
{
bar = 13;
}
this(int i)
{
foo = i;
this();
}
}

In the first constructor, before the field bar is assigned the value 13, some "invisible" code executes: first, the constructor of the base class is invoked. The Example class does not have an explicit base; but in D, similar to Java and C#, all classes have an implicit root Object base. It is as if we wrote:

class Example : Object
{ ...
}

After generating the call to Object's constructor, the compiler generates the code that initializes foo to 42. The explicit assignment as written by the programmer executes after wards.

The compiler must be careful so that the initializations steps described above happen only once in the second constructor. This is not simply a matter of efficiency; it is more importantly, a matter of correctness. If calling the base Object constructor and the initialization of foo where generated blindly inside the body of each constructor, then the following would happen in the second constructor's case:

  1. Object's ctor is invoked (compiler generated)

  2. foo = 42 (compiler generated)

  3. foo = i (programmer's code)

  4. constructor delegation occurs (programmer's code), which means that:

  5. Object's ctor is invoked

  6. foo = 42 (compiler generated)


This is obviously incorrect, since it leaves the Example object in a different state than the programmer intended.

Such scenario is very easily avoided by a native compiler. Object creation is translated to several distinct steps:

  1. memory for the object is allocated

  2. invocation of base ctor is generated

  3. initializers are generated (this is where foo = 42 happens)

  4. constructor as written by programmer is invoked


The important thing to note is that in the native compiler's case the compiler leaves the constructors alone, as written by the programmer, and inserts its magic "pre-initializaton" steps in between the memory allocation and constructor invocation.

When writing a compiler back-end for .NET things are slightly different: the creation of an object is expressed in one compact, single line of MSIL (Microsoft Intermediary Language) assembly code:

newobj <constructor call>

In our example, that would be

newobj void class Example::.ctor()

and

newobj void class Example::.ctor(int32)

respectively. So the compiler-generated magic steps of calling the base constructor, etc have to happen inside the constructor body. To prevent the erroneous scenario of double-initialization from happening, I had to generate a hidden, "guard" Boolean field for classes that use constructor delegation. The variable is set when entering a constructor's body; it is checked inside each constructor before calling the base constructor and stuff. Here's how the generated IL code looks like:

//--------------------------------------------------------------
// ctor.d compiled: Sun Feb 08 23:04:49 2009
//--------------------------------------------------------------
.assembly extern mscorlib {}
.assembly extern dnetlib {}
.assembly 'ctor' {}

.module 'ctor'


.class public auto ctor.Example extends [dnetlib]core.Object
{
.field public int32 foo
.field public int32 bar
.method public hidebysig instance void .ctor ()
{
.maxstack 3
ldarg.0
ldfld bool 'ctor.Example'::$in_ctor
brtrue L0_ctor
ldarg.0
call instance void [dnetlib]core.Object::.ctor()
ldarg.0
ldc.i4 42
stfld int32 'ctor.Example'::foo
L0_ctor:
ldarg.0 // 'this'
ldc.i4 13
stfld int32 'ctor.Example'::bar
ret
}
.method public hidebysig instance void .ctor (int32 'i')
{
.maxstack 3
ldarg.0
call instance void [dnetlib]core.Object::.ctor()
ldarg.0
ldc.i4 42
stfld int32 'ctor.Example'::foo
ldarg.0 // 'this'
ldarg.1 // 'i'
stfld int32 'ctor.Example'::foo
ldarg.0 // 'this'
ldc.i4 1
stfld bool 'ctor.Example'::$in_ctor
ldarg.0
call instance void ctor.Example::.ctor ()
ret
}
.field bool $in_ctor
} // end of ctor.Example

As a side note, in the second constructor's case a small redundancy still exists: foo is assigned to 42 only to be set to another value right away. I am hoping that this isn't much of an issue if the JIT engine detects it and optimizes it out. I'd be happy to hear any informed opinions.

Sunday, February 01, 2009

Stepping Over STL Code



When debugging C++ code written using the Standard Template Library (STL) it is not unusual to find yourself stepping through STL code. Most of the time, this is not very useful: The STL implementation typically comes bundled with the C++ compiler, and it has been thoroughly tested by the vendor; it is unlikely that the bug you are after is caused by the STL.

So when a statement such as myVector.push_back(x) is encountered while tracing with the debugger, you normally want to step over it, not into it. Most debuggers offer a "step over" and a "step into" function. So you would chose "step over".

But how about this? You want to debug a routine named my_func(size_t containerSize) and want to step into the body of my_func when this statement is hit: my_func(myVector.size()). If you select "step into", the debugger will first take you into the guts of STL's vector<T>::size() implementation before stepping into my_func.

The ZeroBUGS debugger allows you to avoid such annoyances. Once inside size(), you can right click, and select to "Always step over..." that function, all functions in that file, or all files in the same directory. The debugger will remember your option, and you don't have to see the guts of size(), or any other vector function, or any other STL function, respectively.

The functionality can be used not just with the STL but any code. If you later change your mind, the "Manage" menu allows you to remove functions, files or directories from the step-into blacklist.

To Destruct a D Struct

I wrote a while ago about similarities between D and .NET (and implicitly C#). My interest in mapping D features to .NET is driven by a research project that I took on a few months ago: a D 2.0 language compiler for .NET (D 2.0 is a branch version of D that includes experimental features). I was mentioning how in both D and C# structs are lightweight, value types.

After working on struct support in more detail, I have come to the realization that D structs cannot be implemented as .NET value type classes. Rather, they have to be implemented as reference type classes.

The short explanation is that while in IL value classes do not participate in garbage collection, D expects the GC to reap structs after they are no longer in use.

Interestingly enough, value types may be newobj-ed (not just created on the stack).

We can use a simple example to demonstrate the difference between value classes and reference classes. If we compile the following program using the IL assembler (ILASM) and run it, nothing gets printed on the screen:

.assembly extern mscorlib {}
.assembly 'test' {}

.class public value auto Test
{
.field public int32 i

.method public void .ctor()
{
ret
}
.method virtual family void Finalize()
{
ldstr "finalizing..."
call void [mscorlib]System.Console::WriteLine(string)
ret
}
}
//--------------------------------------------------------------
// main program
//--------------------------------------------------------------
.method public static void main ()
{
.entrypoint
.locals init (
class Test t
)
newobj instance void Test::.ctor()
stloc 't'
ret
}


But if we changed the declaration of the Test class from a value type to class, like this:

.class public auto Test

we could see "finalizing..." printed, a confirmation that the destructor (the Finalize method) is being invoked by the garbage collector. All it takes is removing "value" from the declaration.

In IL, value types have no self-describing type information attached. I suspect that the reason for not having them being garbage collected is that, without type information, the system cannot possibly know which (virtual) Finalize method to call (note that although C# struct are implemented as sealed value classes, "sealed" and "value" are orthogonal).

D supports the contract programming paradigm, and class invariants is one of its core concepts.

The idea is that the user can write a special method named "invariant", which tests that certain properties of a class or struct hold. In debug mode, the D compiler inserts "probing points" throughout the lifetime of the class (or struct), ensuring that this function is automatically called: after construction, before and after execution of public methods, and before destruction.

The natural mechanism for implementing the last statement is to generate a call to the invariant method at the top the destructor function body. But if the destructor is never called then we've got a problem.

So having destructors work correctly is not just a matter of collecting memory after the struct expires, but it is also crucial to contract programming in D.

Assignment to structs and passing in and to functions may become heavier weight in D.NET than in the native, Digital Mars D compiler (albeit this is something that I have to measure) by implementing structs as reference type classes, but it is necessary in order to support important D language features.