B# .NET Technical Community Homepage

Windows PowerShell through IronRuby - Writing a custom PSHost

bart — Sun, 06 Jul 2008 08:00:00 GMT

Introduction

Lately I've been playing quite a bit with DLR technologies, including IronRuby. During some experiments I came to the conclusion that the Kernel.` method isn't implemented yet in the current version. This `backtick` method allows executing OS commands from inside a Ruby program. It's a bit like Process.Start, redirecting the standard output as a string to the Ruby program for further use (actually the Kernel.exec method is precisely implemented like this).

One thing I like about the NotImplementedException is the fact it points unambiguously to the source that's missing :-). Indeed, if you browse the IronRuby source, you'll find this:

[RubyMethod("`", RubyMethodAttributes.PrivateInstance)]
[RubyMethod("`", RubyMethodAttributes.PublicSingleton)]
public static MutableString ExecuteCommand(CodeContext/*!*/ context, object self, [NotNull]MutableString/*!*/ command) {
// TODO:
throw new NotImplementedException();
}

Actually there are a couple of things here that are worth to discuss besides the current void of the method body:

Strings in Ruby are mutable as opposed to strings in the CLR/BCL. Therefore they are wrapped in a MutableString class.
The weird /*!*/ notation indicates not-nullness, mirrored after the equivalent uncommented form in Spec# (e.g. MutableString! means a null-nullable string). To work with regular C#, the NotNullAttribute is used.
Methods like this one are not invoked by Ruby directly, instead the RubyMethodAttribute declaration carries the metadata that provides the entry-point to the method (as well as other metadata).

Kernel.`

I won't cover the differences between Kernel.`, Kernel.system and Kernel.exec; more information can be found here. The backtick one is our target for the scope of this post:

`cmd` => string

Returns the standard output of running cmd in a subshell. The built-in syntax %x{…} uses this method. Sets $? to the process status.
   `date`                   #=> "Wed Apr  9 08:56:30 CDT 2003\n"
   `ls testdir`.split[1]    #=> "main.rb"
   `echo oops && exit 99`   #=> "oops\n"
   $?.exitstatus            #=> 99

Actually I want to focus on (yet another) powerful feature in PowerShell, namely the ability to create custom hosts. What we want to achieve here is that the backtick syntax (or the equivalent %x syntax) runs the specified command as a PowerShell command (or pipeline of multiple cmdlets), emitting the string output as the `'s methods return value. Notice though this actually downgrades ones of the core principles of PowerShell concerning the use of objects through the pipeline rather than falling back to strings. One could easily think of a more powerful way to expose the results of a PowerShell invocation as PSObjects in Ruby but we'll keep that for later.

Important: This post outlines no more than the capability to hook up PowerShell in IronRuby through Kernel.`. Obviously no promises are made about the way Kernel.` will eventually be implemented in IronRuby as we move forward.

Building a custom PS host

Creating custom PS hosts isn't that hard, depending on how much functionality you want to take over. We'll stick with the basics of console I/O, actually just the O in this. What we want to get done is this:

Build up a runspace containing the command passed to Kernel.` (in addition to some more pipeline commands to produce the right output, see further).
Invoke the built-up pipeline.
Retrieve the string output from the host, concatenate it into one big string and return that one to the caller of Kernel.`.

Preparing for PowerShell programming

In order to extend PowerShell, you'll need to add a reference to System.Management.Automation.dll which can be found in the Reference Assemblies folder (click to enlarge):

Runspaces

Let's start at the very top by implementing a method called "InvokePS" that sets up the infrastructure to call PowerShell:

public static class RubyToPS
{
    public static string InvokePS(string command)
    {
        RubyPSHost host = new RubyPSHost();

        using (Runspace runspace = RunspaceFactory.CreateRunspace(host))
        {
            runspace.Open();

            using (Pipeline pipeline = runspace.CreatePipeline())
            {
                pipeline.Commands.AddScript(command);
                pipeline.Commands[0].MergeMyResults(PipelineResultTypes.Error, PipelineResultTypes.Output);                 pipeline.Commands.Add("out-default");

                pipeline.Invoke();
            }
        }

        return ((RubyPSHostUserInterface)host.UI).Output;
    }
}

The RubyPSHost class will be shown next, let's focus on the Runspace stuff for now. A runspace serves as the entry-point to the PowerShell engine and encapsulates all the state needed to execute pipelines. Once we've opened the runspace, a pipeline is created to which we add the passed-in command as a script. This allows more than just one cmdlet invocation to be executed (e.g. "gps | where { $_.WorkingSet64 -gt 50MB }"). To send output to the host we append Out-Default to the pipeline:

NAME
    Out-Default

SYNOPSIS
    Send the output to the default formatter and the default output cmdlet. Thi
    s cmdlet has no effect on the formatting or output. It is a placeholder tha
    t lets you write your own Out-Default function or cmdlet.

SYNTAX
    Out-Default [-inputObject <psobject>] [<CommonParameters>]

DETAILED DESCRIPTION
    The Out-Default cmdlet send the output to the default formatter and the def
    ault output cmdlet. This cmdlet has no effect on the formatting or output.
    It is a placeholder that lets you write your own Out-Default function or cm
    dlet.

The MergeMyResults call is used to ensure that error objects produced by the first command are merged into the output (otherwise you'll get an exception instead). Finally the output is retrieved from the host after invoking the pipeline. How this works will be covered in a minute.

To read more about PowerShell runspaces, check out my other posts on the topic.

Deriving from PSHost

Custom PowerShell hosts derive from the abstract PSHost base class. There's quite some stuff that can be done here but we'll stick with the absolute minimum functionality required to reach our goals:

internal class RubyPSHost : PSHost
{
    private Guid _hostId = Guid.NewGuid();
    private RubyPSHostUserInterface _ui = new RubyPSHostUserInterface();

    public override Guid InstanceId
    {
        get { return _hostId; }
    }

    public override string Name
    {
        get { return "RubyPSHost"; }
    }

    public override Version Version
    {
        get { return new Version(1, 0); }
    }

    public override PSHostUserInterface UI
    {
        get { return _ui; }
    }

    public override CultureInfo CurrentCulture
    {
        get { return Thread.CurrentThread.CurrentCulture; }
    }

    public override CultureInfo CurrentUICulture
    {
        get { return Thread.CurrentThread.CurrentUICulture; }
    }

    public override void EnterNestedPrompt()
    {
        throw new NotImplementedException();
    }

    public override void ExitNestedPrompt()
    {
        throw new NotImplementedException();
    }

    public override void NotifyBeginApplication()
    {
        return;
    }

    public override void NotifyEndApplication()
    {
        return;
    }

    public override void SetShouldExit(int exitCode)
    {
        return;
    }
}

More information about all of those methods and properties can be found on MSDN. The most important one to us the the UI property that points at our PSHostUserInterface implementation called RubyPSHostUserInterface.

Implementing PSHostUserInterface

Where the PSHost class provides basic information concerning the metadata of the host (name, version, id)m lifetime of the host (nested prompt, execit commands) and general settings (cultures), the PSHostUserInterface class deals with "dialog-oriented and line-oriented interaction between the cmdlet and the user, such as writing to, prompting for, and reading from user input" (from MSDN). The part we're interested in the writing to part. We won't deal with prompts or user interaction - if one wants to do this, the Kernel.` command is no longer non-interactive (a possible alternative way to implement this would be to spawn PowerShell.exe and just get the shell's output here - the default host would take care of all user interaction if required; the only problem is that prompts would appear in the Kernel.` output as well). Implementation of this class isn't that hard either:

internal class RubyPSHostUserInterface : PSHostUserInterface
{
    private StringBuilder _sb;

    public RubyPSHostUserInterface()
    {
        _sb = new StringBuilder();
    }

    public override void Write(ConsoleColor foregroundColor, ConsoleColor backgroundColor, string value)
    {
        _sb.Append(value);
    }

    public override void Write(string value)
    {
        _sb.Append(value);
    }

    public override void WriteDebugLine(string message)
    {
        _sb.AppendLine("DEBUG: " + message);
    }

    public override void WriteErrorLine(string value)
    {
        _sb.AppendLine("ERROR: " + value);
    }

    public override void WriteLine(string value)
    {
        _sb.AppendLine(value);
    }

    public override void WriteVerboseLine(string message)
    {
        _sb.AppendLine("VERBOSE: " + message);
    }

    public override void WriteWarningLine(string message)
    {
        _sb.AppendLine("WARNING: " + message);
    }

    public override void WriteProgress(long sourceId, ProgressRecord record)
    {
        return;
    }

    public string Output
    {
        get
        {
            return _sb.ToString();
        }
    }

    public override Dictionary<string, PSObject> Prompt(string caption, string message, System.Collections.ObjectModel.Collection<FieldDescription> descriptions)
    {
        throw new NotImplementedException();
    }

    public override int PromptForChoice(string caption, string message, System.Collections.ObjectModel.Collection<ChoiceDescription> choices, int defaultChoice)
    {
        throw new NotImplementedException();
    }

    public override PSCredential PromptForCredential(string caption, string message, string userName, string targetName, PSCredentialTypes allowedCredentialTypes, PSCredentialUIOptions options)
    {
        throw new NotImplementedException();
    }

    public override PSCredential PromptForCredential(string caption, string message, string userName, string targetName)
    {
        throw new NotImplementedException();
    }

    public override PSHostRawUserInterface RawUI
    {
        get { return null; }
    }

    public override string ReadLine()
    {
        throw new NotImplementedException();
    }

    public override System.Security.SecureString ReadLineAsSecureString()
    {
        throw new NotImplementedException();
    }
}

The core of our implementation lies in the fact that all Write* methods emit their data to a StringBuilder instance that aggregates all output sent to the host. This is the data that gets retrieved by our InvokePS method on the last line:

return ((RubyPSHostUserInterface)host.UI).Output;

Notice this isn't the absolute end of host-level extensibility in PowerShell. A PSHostUserInterface class can point at a PSHostRawUserInterface object that controls host window characteristics (such as the size, position and title of the window). Actually it would be interesting to implement this one as well in order to provide an accurate BufferSize that will be used by PowerShell to control the maximum length of individual lines before wrapping to the next line. The reason this would be a good idea is that screen-scraping Ruby programs should be able to ignore different wrapping behavior depending on the hosting command window (which would cause programs to behave differently depending where they run). Ideally there would be no wrapping at all (letting the DLR IronRuby command-line host dealing with wrapping when printing data to the screen). I'll leave this exercise to the reader.

Hooking it up

All of the above has been implemented in a separate strong-named Class Library which I'm just referencing in the IronRuby.Libraries project. This is actually very quick-and-dirty, making IronRuby directly dependent on our assembly and by extension Windows PowerShell. A way around this would be to load the assembly dynamically possibly based on an environment variable. There are lots of possibilities here which we consider just an implementation detail for now. The only thing left to do is to call our InvokePS method which requires some conversions between System.String and MutableString:

[RubyMethod("`", RubyMethodAttributes.PrivateInstance)]
[RubyMethod("`", RubyMethodAttributes.PublicSingleton)]
public static MutableString ExecuteCommand(CodeContext/*!*/ context, object self, [NotNull]MutableString/*!*/ command) {
return MutableString.Create(RubyToPS.InvokePS(command.ConvertToString()));
}

That's it! Here's the result:

Note: The \r\n insertions in the output for display by Ruby's console cause things to wrap a bit nasty given the default of 80 characters buffer width. I've adjusted to 83 characters to make this render correctly. With some smart "Raw UI host" one could eliminate some issues here - however the internal contents of the string is more important since the app will likely rely on that (otherwise you'd simply run a PowerShell interactive shell, wouldn't you?). Just as one sample, here's the output of the each_line iterator:

Does look an awful lot like PowerShell, doesn't it?

Cheers!

1.To(3) - Ruby-style Internal Iterators in C#

bart — Sat, 05 Jul 2008 08:35:44 GMT

External or internal?

C# introduced the concept of iterators in C# 2.0 but it's a less-known fact that there are two sorts of iterators. The ones provided in C# are so-called external iterators. The distinction lies in the party that controls the enumeration of the iteration, e.g.

public IEnumerator<int> FromTo(int from, int to)
{
for (int i = from; i <= to; i++)
yield return i;
}

does by itself not perform any iteration; it's only when the consumer starts to suck data out of the enumerator object (typically using a foreach loop) that the data is fetched:

foreach (int i in FromTo(1, 3))
Console.WriteLine(i);

In other words, the object returned by FromTo (which is a little state machine implementing IEnumerator<T> or IEnumerable<T>) just captures the capability of iterating over the produced results in an on-request basis. Notice using C# 3.0 syntax, we can make the use of it 'different', obtaining a more Ruby-like style:

public static IEnumerator<int> To(this int from, int to)
{
for (int i = from; i <= to; i++)
yield return i;
}

using an extension method so it can be called like this:

foreach (int i in 1.To(3))
Console.WriteLine(i);

Still no different than what we started with but as you can guess: besides external iterators we have internal iterators. Internal iterators perform the iteration themselves (they push the generated values into the code body associated with them) and are therefore very similar to built-in loop control structures in the language. A possible implementation looks like this:

public static IEnumerator<int> To(this int from, int to, Action<int> a)
{
for (int i = from; i <= to; i++)
a(i);
}

which can be called like this:

1.To(3, i => { Console.WriteLine(i); });

using a C# 3.0 lambda expression. Notice there is no blue (syntax coloring) left, we have defined our own control structure. Nothing fancy but one thing we've actually given up here is our ability to define an object that captures the "iterator's potential" to iterate from 1 to 3 and that can be invoked multiple times. (Whether or not this is a cosmetic detail is left for judgement by the reader.) In other words, we'd like to be able to define a control structure like this:

var myLoop = 1.To(3);
myLoop(i => { Console.WriteLine(i); });
myLoop(i => { Console.WriteLine(i + " again!"); });

What we're doing here is making use of partial function application. It looks like we're calling the To method with just one parameter, allowing the other parameters to be filled in later, realizing higher-order functions. I deliberately obfuscated the type of 1.To(3) in the fragment above to elaborate on it a bit more now. What does the type of 1.To(3) need to look like? Well, we should be able to call it with one parameter of type Action<int>. The result of calling through the 1.To(3) object is purely side-effect based, i.e. the call doesn't return anything by itself, so the return type of the type we're looking for is void. To wrap up, a void-returning callable thing is nothing less than an Action<T> where T is our parameter, an Action<int>, so the resulting type is Action<Action<int>>. This level of "action-indirection" signifies the possible delayed characteristic of the iterator invocation. The reason the delayed execution is optional is obvious since one can call it like this:

1.To(3)(i => { Console.WriteLine(i); });

In Ruby one would write:

1.upto(3) { |i| print i }

Implementing internal iterators

So how to implement this? Not that difficult at all:

public static Action<Action<int>> To(this int from, int to)
{
return a => { for (int i = from; i <= to; i++) a(i); };
}

Notice how the iteration moved inside the "iterator", how it's indirected through one level of lambda-abstraction and now yield keywords have been used (making it no longer an iterator in C# lingo). In fact, there's lots of magic going on in this fragment. First of all, the type inference carried out by the compiler. Since the signature of the To method indicates we're returning an Action<Action<int>> - which is fancy speak for delegate void _(delegate void_(int)) - the compiler can infer that the lambda's parameter a has type Action<int>:

return (Action<int> a) => { for (int i = from; i <= to; i++) a(i); };

Furthermore, lambda's are pure syntactical sugar for anonymous methods (at least in this case where no expression trees are involved):

return delegate (Action<int> a) { for (int i = from; i <= to; i++) a(i); };

The end result with sample looks like this:

We could stop here but if you're curious for the technical details that make this work, read on.

Behind the compiler curtains

The real question though is what gets returned. This is where closures kick in:

The <>c__DisplayClass1 captures the from and to arguments to the iterator "constructor" call (since that's ultimately what our To call does) and has a method called <To>b__0 that contains our iteration logic:

Notice the call through the supplied Action<int> delegate on line IL_000c. An obvious question is whether or not a closure in this case is useful. What we're capturing here are the parameters from and to that are supplied to the To method (that lot's of to's too...). Since closures in C# capture lvals (mimicking copy by ref semantics) there's a code-window where the variables can change and where that change is propagated into the closure. Assume our To-implementation would look like this:

public static Action<Action<int>> To(this int from, int to)
{
    Action<Action<int>> res = a => { for (int i = from; i <= to; i++) a(i); };
    from++; to--;
    return res;
}

when calling To(1,3)(i => { Console.WriteLine(i); }); you'd now see only 2 getting printed on the screen. Why? The locals from and to are getting captured by the closure (also known as captured outer variables, see C# specification §14.5.15.3.1), so wherever one refers to from and to in the local scope the captured variables are getting referenced instead. So by the time a call is made through To(1,3) the captured values have both changed to 2 (from++, to--). However, this closure doesn't propagate outside the scope of the To method, in other words - and again assuming the original implementation of To - you won't see the effects of it when writing code like this:

int f = 1;
int t = 3;
var loop = f.To(t);
f++;
t--;
loop(i => { Console.WriteLine(i); });
loop(i => { Console.WriteLine(i + " again!"); });

This will still print all 6 expected lines. Let's eliminate our To method for a moment and try to write everything compacted in one place, like this:

Func<int, int, Action<Action<int>>> To = (from, to) => a => { for (int i = from; i <= to; i++) a(i); };
To(1, 3)(i => { Console.WriteLine(i); });
To(1, 3)(i => { Console.WriteLine(i + " again!"); });

Again 6 lines will be printed to the screen. Notice how the (inline) To "method" above has the same signature as our previous extension method To: we take in two ints and return an Action<Action<int>>. Also notice how lambda arrows are right associative, you should read it as:

(from, to) => (a => { for (int i = from; i <= to; i++) a(i); })

What now with closures? Actually, nothing changes. I did say closures capture the outer scope; however, from and to used in the body of the inner lambda refer to the locals from and to defined in the outer lambda, so when calling To(f, t) below:

int f = 1;
int t = 3;
var loop = To(f, t);
f++;
t--;
loop(i => { Console.WriteLine(i); });
loop(i => { Console.WriteLine(i + " again!"); });

the values f and t are copied into the anonymous method of the outer lambda; where they get captured in a closure used in the inner lambda's body. When you'd loosen the abstraction of the To method like this:

int from = 1;
int to = 3;

Action<Action<int>> To = a => { for (int i = from; i <= to; i++) a(i); };

from++;
to--;

To(i => { Console.WriteLine(i); });
To(i => { Console.WriteLine(i + " again!"); });

there's just one lambda left for which the outer scope is the directly surrounding method, so from and to are captured by a closure and changing them will affect the operation of To.

The closure inside the To method doesn't really gain us anything. Obviously the question is which behavior one wants to realize: one where the loop's boundaries can be changed afterwards (much like closures would allow us to do) or one where the loop object is immutable. To realize the former - if you'd really insist - some creativity is required. 1.To(3) could return an object with properties From and To while also exposing a method called Invoke to invoke the loop with the specified Action<int>. An object with an Invoke method looks pretty much like a delegate, so geeks could hack up IL to create a delegate with From and To properties. Not worth the effort IMO (apart from being a very interesting experiment), immutability is great and this definitely applies to this particular case. However (:-)) if you still insist, there's another escape valve: perform one level of indirection to the arguments to the iterator itself:

public static Action<Action<int>> To(this Func<int> from, Func<int> to)
{
return a => { for (int i = from(); i <= to(); i++) a(i); };
}

Notice the orthogonal structure between functions/classes (code versus data) and lifted functions/pointers (=> versus * and - the reverse - () versus *). Calling it doesn't look pretty anymore though (partially because the left-hand side used in an extension method doesn't work with a lambda expression since a lambda has no type by itself, it could either be a Func<...> or an Expression<Func<...>> depending on its - in this case non-existent - assignment):

int b = 3;
var loop = (new Func<int>(() => 1)).To(() => b);
b = 2;
loop(i => { Console.WriteLine(i); });
loop(i => { Console.WriteLine(i + " again!"); });

but here b is caught by a closure, so changing it after obtaining the loop variable will change it's semantics. Brrrr...

A dynamic approach

Sticking with immutable internal iterators, we could eliminate the closure and produce the delegate at runtime using Reflection.Emit. This would look as follows:

public static Action<Action<int>> To(this int from, int to)
{
    DynamicMethod m = new DynamicMethod("", null, new Type[] { typeof(Action<int>) });
    ILGenerator ilgen = m.GetILGenerator();

    Label loop = ilgen.DefineLabel();
    Label ret = ilgen.DefineLabel();

    //
    // for (int i = from; i <= to; i++) { a(i); } return;
    //      ^^^^^^^^^^^^
    //
    var var_i = ilgen.DeclareLocal(typeof(int));
    ilgen.Emit(OpCodes.Ldc_I4, from);
    ilgen.Emit(OpCodes.Stloc, var_i);

    //
    // for (int i = from; i <= to; i++) { a(i); } return;
    //                         ^^
    //
    var var_to = ilgen.DeclareLocal(typeof(int));
    ilgen.Emit(OpCodes.Ldc_I4, to);
    ilgen.Emit(OpCodes.Stloc, var_to);

    //
    // for (int i = from; i <= to; i++) { a(i); } return;
    // ^^^^
    //
    ilgen.MarkLabel(loop);

    //
    // for (int i = from; i <= to; i++) { a(i); } return;
    //                    ^^^^^^^
    //
    ilgen.Emit(OpCodes.Ldloc, var_i);
    ilgen.Emit(OpCodes.Ldloc, var_to);
    ilgen.Emit(OpCodes.Cgt);
    ilgen.Emit(OpCodes.Brtrue, ret);

    //
    // for (int i = from; i <= to; i++) { a(i); } return;
    //                                  ^ ^^^^^
    //
    ilgen.Emit(OpCodes.Ldarg_0);
    ilgen.Emit(OpCodes.Ldloc, var_i);
    ilgen.Emit(OpCodes.Callvirt, typeof(Action<int>).GetMethod("Invoke"));

    //
    // for (int i = from; i <= to; i++) { a(i); } return;
    //                             ^^^
    //
    ilgen.Emit(OpCodes.Ldloc, var_i);
    ilgen.Emit(OpCodes.Ldc_I4_1);
    ilgen.Emit(OpCodes.Add);
    ilgen.Emit(OpCodes.Stloc, var_i);

    //
    // for (int i = from; i <= to; i++) { a(i); } return;
    //                                          ^
    //
    ilgen.Emit(OpCodes.Br, loop);

    //
    // for (int i = from; i <= to; i++) { a(i); } return;
    //                                            ^^^^^^^
    //
    ilgen.MarkLabel(ret);
    ilgen.Emit(OpCodes.Ret);

    return (Action<Action<int>>)m.CreateDelegate(typeof(Action<Action<int>>));
}

Performance-wise you'll see that the latter obviously is slower (and actually on the functional level you don't gain anything since the redundant closure is harmless as we have proven higher up - also concerning memory allocation we're trading closure objects for DynamicMethod and other Reflection.Emit object instances). It shows however how a 3rd party compiler (or interpreter) could emit IL code that realizes an internal iterator with very little code involved (only 17 IL instructions).

Other iterators

Of course the "To" operator iterator is just one of the many possibilities. Here's just one of the many:

public static Action<Action<T>> ForEach<T>(this IEnumerable<T> source)
{
return a => { foreach (T item in source) a(item); };
}

where the indirection of actions is a little artificial, agreed:

new int [] { 1, 2, 3 }.ForEach()(i => { Console.WriteLine(i); });

This is a place where extension properties would come in handy, or obviously we could just write the following instead:

public static void ForEach<T>(this IEnumerable<T> source, Action<T> action)
{
foreach (T item in source) action(item);
}

Enjoy!

Parallel Extensions - Using Futures to Calculate Pi in Hexadecimal

bart — Thu, 03 Jul 2008 18:25:25 GMT

Introduction

Last month we released the June 08 CTP of the Parallel Extensions to the .NET Framework. For more information and to get the latest updates, see http://msdn.microsoft.com/concurrency and the team blog at http://blogs.msdn.com/pfxteam. In this post (of a longer series) I want to highlight one particular feature called futures. But first, to get started: download the CTP, install it, open VS 2008 and create a new Console Application (I'll be using C#) and add a reference to the System.Threading.dll assembly that gets installed by the Parallel Extensions:

There's a bunch of stuff in this CTP, as you can see from the Object Browser:

I'll be covering quite some of this in subsequent posts, but for now we simply stick with System.Threading.Tasks.Future<T>. So, what's a future? In short, a future is a task that's supposed to produce a value some time in the future. Question becomes: what's a task? One can think of a task as a modern thread, maintained by a task manager which implements a (work-stealing) scheduler. Without going in details for now, it suffices to think of tasks as the parallel version of procedures while futures play the role of parallel equivalents to functions. Actually, a future is a task with just something more: a value.

The Future<T> 101

Using a future is simple. To create one, use the Future.Create factory method:

All you have to supply is a function that returns a value of type T. That function can take all the time it wants to calculate that particular value without blocking other "work" in the application. This obviously only holds till someone needs the value being produced by the future. Let's make an easy sample:

Here we have a lottery mechanism that picks a ball with numbers from 1-42 which takes between 1 and 10 seconds to complete. To specify the future's code, we're using a C# 3.0 lambda expression although the 2.0 style "delegate" keyword would be appropriate here too. The important thing here is the fact the "Lottery in progress..." message will be shown while the future is calculating its value. In other words, the main thread isn't blocked by the background calculation, till we call the Value property on the future which waits for the value to be calculated in order to obtain it. Obviously, a lottery would be more complicated since the system has to wait for more balls to get picked (let's not discuss whether or not the numbers need to be unique; uniqueness gives some interesting concurrent collection access worries depending on how you implement it). A possible refinement is this:

Here we use 6 futures to represent the 6 balls in the lottery and we wait for all balls to get picked using the (new in the last CTP) WaitAll method. I'll leave it as an exercise to figure out what it would take to print the selection of balls to the screen immediately as soon as they arrive (tip: WaitAny goes in the right direction but the array might not be appropriate).

An ancient passion: calculating PI

It has been done before but it's still an attractive business for math freaks: calculating PI. There are lots of algorithms that do this based on the development of series (e.g. by rewriting PI in terms of arctan functions which can be represented using infinite McLaurin series). One more recent algorithm is the Bailey-Borwein-Plouffe (shorthand BBP - On the Rapid Computation of Various Polylogarithmic Constants) algorithm which has some interesting characteristics:

Non-decimal: calculates PI in base 16 hexadecimal.
Random access: allows to calculate an individual digit without having to calculate the digits that precede it.
Distribution friendly: can be used to calculate portions of PI in parallel.

The formula looks like this and is based on infinite series:

The crux - due to Plouffe - is the 16^k in the denominator which is precisely what base 16 fractionals look like, e.g.:

In other words, to calculate the digit at a given position it suffices to calculate the following:

with the overbar notation standing for "fraction of". Obviously the left-hand side stands for the digit at position pos in the (hexadecimally represented) value of PI. The right-hand side is a simple rewrite of the original formula multiplied by 16^pos, allowing for the following refactoring:

where

This allows for efficient implementation using some binary exponentiation techniques for the power evaluations and with some modulo calculus. I tried to document the code as much as possible to illustrate how it works:

/// <summary>
/// Calculation of PI using the BBP (Bailey-Borwein-Plouffe) formula.
/// </summary>
static class Pi
{
    /// <summary>
    /// Powers of two. Used in the binary exponentiation algorithm (Knuth Vol II - 4.6.3).
    /// </summary>
    static int[] s_powsOf2;

    /// <summary>
    /// Hexadecimal characters.
    /// </summary>
    static string HEX = "0123456789ABCDEF";

    /// <summary>
    /// Static constructor.
    /// </summary>
    static Pi()
    {
        s_powsOf2 = new int[25];

        //
        // Set powers of two for use in binary exponentiation algorithm.
        //
        s_powsOf2[0] = 1;
        for (int i = 1; i < s_powsOf2.Length; i++)
            s_powsOf2[i] = s_powsOf2[i - 1] * 2;
    }

    /// <summary>
    /// Calculates a given number of hexadecimal digits of PI from the given start position.
    /// </summary>
    /// <param name="start">Hexadecimal position to start calculating hexadecimal digits from.</param>
    /// <param name="length">Number of hexadecimal digits to calculate. Needs to be multiple of 10.</param>
    /// <returns>Requested hexadecimal digits of PI.</returns>
    public static string Calculate(int start, int length)
    {
        if (start < 0)
            throw new ArgumentException("start");

        if (length < 0 || length % 10 != 0)
            throw new ArgumentException("length");

        StringBuilder sb = new StringBuilder();

        //
        // Calculate in chunks of 10 given our precision.
        //
        for (int pos = start; pos < start + length; pos += 10)
        {
            double val = 4 * Sum(1, pos) - 2 * Sum(4, pos) - Sum(5, pos) - Sum(6, pos);
            val = val - (int)val + 1;
            sb.Append(ToHex(val));
        }

        return sb.ToString();
    }

    /// <summary>
    /// This method calculates the fractional part of SUM[i = 0..+INF](1 / (16^i * (8 * i + j))).
    /// </summary>
    /// <param name="j">See formula.</param>
    /// <param name="pos">Starting position for requested hexadecimal part of PI's fraction.</param>
    /// <returns>See formula.</returns>
    static double Sum(int j, int pos)
    {
        /*
         * Implementation based on the following observation:
         *
         *   SUM[i = 0..+INF](1 / (16^i * (8 * i + j)))
         *
         *   =   SUM[k = 0..d]((16^(d - k) mod (8 * k + j)) / (8 * k + j)))
         *     + SUM[k = d + 1..+INF](16^(d - k) / (8 * k + j)))
         */

        double res = 0.0;

        int k = 0;

        //
        // First part of the sum using binary exponentiation with modulo operation.
        //
        for (; k < pos; k++)
        {
            double n = 8 * k + j;
            res += PowMod(16.0, pos - k, n) / n;
            res -= (int)res;
        }

        //
        // For the remainder terms, go till we reach the precision of 10^-17,
        // which allows to reach the required precision in hexadecimals.
        //
        for (; ; k++)
        {
            double t = Math.Pow(16.0, pos - k) / (8 * k + j);
            if (t < 1e-17)
                break;
            res += t;
            res -= (int)res;
        }

        return res;
    }

    /// <summary>
    /// Returns a specified number raised to the specified power, module the given modulus.
    /// </summary>
    /// <param name="x">A double-precision floating-point number to be raised to a power.</param>
    /// <param name="y">A double-precision floating-point number that specifies a power.</param>
    /// <param name="m">A double-precision floating-point number that specified the modulus.</param>
    /// <returns>x^y mod m</returns>
    static double PowMod(double x, double y, double m)
    {
        if (m == 1.0)
            return 0.0;

        //
        // We look for the largest bit position used by the exponent.
        // E.g. 16^9 mod 9 = (16 * 16^(2^3)) mod 9
        //                               ^
        //
        int i;
        for (i = 0; i < s_powsOf2.Length; i++)
            if (s_powsOf2[i] > y)
                break;

        double pow2 = s_powsOf2[i - 1];

        //
        // Set remaining number of exponentiations and result to initial values.
        //
        double rem = y;
        double res = 1.0;

        for (int j = 0; j < i; j++)
        {
            //
            // "Remainder" steps that do not fit in binary exponentiation.
            //
            // j   res             res'
            // -- -------------- ----
            // 0   16^0 mod 9 = 1 16^1 mod 9 = (1 * 16) mod 9 = 7
            // 3   16^8 mod 9 = 4 16^9 mod P = (4 * 16) mod 9 = 1
            //
            if (rem >= pow2)
            {
                res = (res * x) % m;
                rem -= pow2;
            }

            pow2 /= 2;

            //
            // Binary exponentation step.
            //
            // j   res             res'
            // -- -------------- ------------------------------
            // 0   16^1 mod 9 = 7 16^2 mod 9 = (7 * 7) mod 9 = 4
            // 1   16^2 mod 9 = 4 16^4 mod 9 = (4 * 4) mod 9 = 7
            // 2   16^4 mod 9 = 7 16^8 mod 9 = (7 * 7) mod 9 = 4
            //
            if (pow2 >= 1.0)
            {
                res = (res * res) % m;
            }
        }

        return res;
    }

    /// <summary>
    /// Converts the fractional part of the specified double-precision floating-point number
    /// to hexadecimal representation.
    /// </summary>
    /// <param name="d">Double-precision floating-point number in base 10.</param>
    /// <returns>String representation of the number's fractional part in base 16.</returns>
    /// <example>
    /// Sample: d := 0.14159265358979334
    ///
    ///    f := (d - (int)d )   16 * f               Hex((int)(16 * f))
    ///    ------------------- ------------------- ------------------
    /// 0. 0.14159265358979334   2.2654824574366934 2
    /// 1. 0.26548245743669340   4.2477193189870945 4
    /// 2. 0.24771931898709450   3.9635091037935126 3
    /// 3. 0.96350910379351260 15.4161456606962020 F
    /// 4. 0.41614566069620200   6.6583305711392313 6
    /// 5. 0.65833057113923130 10.5332891382277010 A
    /// 6. 0.53328913822770100   8.5326262116432190 8
    /// 7. 0.53262621164321900   8.5220193862915039 8
    /// 8. 0.52201938629150390   8.3523101806640625 8
    /// 9. 0.35231018066406250   5.6369628906250000 5
    ///
    /// Reverse: h := 0.243F6A8885
    ///
    ///    Weight       Value
    ///    ----------- -----------
    /// 0. 2 * 16^-1    0.12500000000000000000
    /// 1. 4 * 16^-2    0.01562500000000000000
    /// 2. 3 * 16^-3    0.00073242187500000000
    /// 3. F * 16^-4    0.00022888183593750000
    /// 4. 6 * 16^-5    0.00000572204589843750
    /// 5. A * 16^-6    0.00000059604644775391
    /// 6. 8 * 16^-7    0.00000002980232238770
    /// 7. 8 * 16^-8    0.00000000186264514923
    /// 8. 8 * 16^-9    0.00000000011641532183
    /// 9. 5 * 16^-10   0.00000000000454747351
    ///                +----------------------
    ///                 0.14159265358921400000
    ///                   ^^^^^^^^^^^^
    /// </example>
    static string ToHex(double d)
    {
        char[] c = new char[10];

        for (int i = 0; i < c.Length; i++)
        {
            d = 16 * (d - (int)d);
            c[i] = HEX[(int)d];
        }

        return new string(c);
    }
}

Putting futures to work

The actual implementation is actually of little interest in this context; using it with futures is more of interest now. Here's a sample use of it:

And here's the result:

The parallel version only takes 58% of the original sequential execution! Before going any further, there's a little interesting thing in the implementation above: some manual partitioning. The first future calculates from 0 to 7000 and the second one from 7000 to 10000. In general with work-stealing applied in the scheduler such partitioning can be eliminated as long as the individual work items that get executed by tasks or futures do not have a clear predictable relative execution duration. For this particular case however, we have intrinsic knowledge about the algorithm and the fact it actually scales linearly based on the position of the hexadecimal digits requested. In particular, if you'd plot the duration of calculations of chunks against the time it takes, you'd see something along those lines:

To partition the total work correctly it suffices to solve one quadratic equation derived from an integration so that the yellow (0 to x) and blue (x to 10000) portions have the same surface:

You'll find x to be about 7000 in this case which indicates the optimum partitioning for calculation of digits 0 to 10000. If you'd partition around 5000, it's clear that the second future would have a longer execution time than the first one as seen from the surface under the curve (line) in the graph above. Also, the fact we're partitioning in two halves implies we're not optimizing for anything beyond dual core (higher-order partitioning of the problem is less trivial but still possible). Also, with arbitrary inputs from the user we'd have to calculate the partitioning at runtime instead.

So, how does execution look like?

Clearly, in the sequential case (between the first two red lines) not all processors are busy but in the case with futures (between the last two red lines), both processors go up to 100% utilization and as one can observe, the algorithm runs faster. In terms of threads you'll see this in the Performance Monitor:

As soon as the parallel execution kicks in, three additional threads are created (of which two are doing work for our futures). In the curve above this is observed by the jump from 6 to 9 threads.