Creating a command line splitting parser in F#

I found myself in need of a way to split a line of text into a sequence of strings, using whitespace characters to delineate each string, but allowing spaces within quoted sections, and also allowing for quotes using an escape sequence. So, a few examples:

    'this is a test' -> 'this';'is';'a';'test'
    'this "is a" test' -> 'this';'is a';'test'
    'this ""is"" a test' -> 'this';'"is"';'a';'test'

I’ll write some unit tests for the above scenarios.

[<Test>]
member x.``empty line``() =
    let line = ""
    let result = LineParser.SpaceSeperatedParser.Parse(line) |> Array.ofSeq
    Assert.AreEqual([| |], result)

[<Test>]
member x.``plain line parses correctly``() =
    let line = "hello F#ers, how are you?"
    let result = LineParser.SpaceSeperatedParser.Parse(line) |> Array.ofSeq
    Assert.AreEqual([| "hello"; "F#ers,"; "how"; "are"; "you?" |], result)

[<Test>]
member x.``line with quoted section parses correctly``() =
    let line = "hello F#ers, \"how are you?\""
    let result = LineParser.SpaceSeperatedParser.Parse(line) |> Array.ofSeq
    Assert.AreEqual([| "hello"; "F#ers,"; "how are you?" |], result)

[<Test>]
member x.``line with an escaped quote parses correctly``() =
    let line = "hello \"\"F#ers\"\", how are you?"
    let result = LineParser.SpaceSeperatedParser.Parse(line) |> Array.ofSeq
    Assert.AreEqual([| "hello"; "\"F#ers\","; "how"; "are"; "you?" |], result)

[<Test>]
member x.``line with unclosed quoted section keeps last block``() =
    let line = "hello F#ers, \"how are you?"
    let result = LineParser.SpaceSeperatedParser.Parse(line) |> Array.ofSeq
    Assert.AreEqual([| "hello"; "F#ers,"; "how are you?" |], result)

[<Test>]
member x.``line with quotes within a word treats them like escaped``() =
    let line = "hello F\"ers, how are you?"
    let result = LineParser.SpaceSeperatedParser.Parse(line) |> Array.ofSeq
    Assert.AreEqual([| "hello"; "F\"ers,"; "how"; "are"; "you?" |], result)

[<Test>]
member x.``quotes in word in quoted section treated as escape``() =
    let line = "hello \"F#ers, how a\"re\" you?"
    let result = LineParser.SpaceSeperatedParser.Parse(line) |> Array.ofSeq
    Assert.AreEqual([| "hello"; "F#ers, how a\"re"; "you?" |], result)

[<Test>]
member x.``line starting with a quote``() =
    let line = "\"hello F#ers,\" how are you?"
    let result = LineParser.SpaceSeperatedParser.Parse(line) |> Array.ofSeq
    Assert.AreEqual([| "hello F#ers,"; "how"; "are"; "you?" |], result)

[<Test>]
member x.``line starting with an escape``() =
    let line = "\"\"hello F#ers, how are you?"
    let result = LineParser.SpaceSeperatedParser.Parse(line) |> Array.ofSeq
    Assert.AreEqual([| "\"hello"; "F#ers,"; "how"; "are"; "you?" |], result)

[<Test>]
member x.``line ending with a quote``() =
    let line = "hello F#ers, \"how are you?\""
    let result = LineParser.SpaceSeperatedParser.Parse(line) |> Array.ofSeq
    Assert.AreEqual([| "hello"; "F#ers,"; "how are you?" |], result)

[<Test>]
member x.``line ending with an escape``() =
    let line = "hello F#ers, how are you?\"\""
    let result = LineParser.SpaceSeperatedParser.Parse(line) |> Array.ofSeq
    Assert.AreEqual([| "hello"; "F#ers,"; "how"; "are"; "you?\"" |], result)

A few edge cases here to be dealt with. This is going to need a fair amount of code, right? In the end, I thought it would be nice to create a configurable parser, which takes a number of functions for checking whether characters are seperators, quotes or escape sequences, and thus throw in a CSV parser as well

type LineParser(sepTest:char -> bool, quotTest:char -> bool,
                escTest:char * char -> bool,escRepl:char * char -> char) =

    static let isComma(c) = c = ','
    static let isSpace(c) = Char.IsWhiteSpace(c)
    static let isQuot(c) = c = '\'' || c = '\"'
    static let isEscQuot(c,d) = (c = '\"' && d = '\"') || (c = '\'' && d = '\'')

    static member CommaSeperatedParser = 
        LineParser( isComma, isQuot, isEscQuot, fst)
    static member SpaceSeperatedParser = 
        LineParser( isSpace, isQuot, isEscQuot, fst)

    member x.Parse(line:string) =

        let rec parse (underway:char list,inquotes:bool) (remain:char list) = 
            seq {
                let getString(cl:char list) =
                    new System.String(cl |> Array.ofList |> Array.rev)
                match remain,underway,inquotes with
                | q::[],y,true when quotTest(q) 
                                    -> yield getString(y)
                | [],y,_            -> yield getString(y)
                | q::w::x,y,z when escTest(q,w) 
                                    -> yield! x |> parse ((escRepl(q,w))::y, z)
                | c::q::w::x,y,false 
                    when sepTest(c) && quotTest(q) && not(escTest(q,w))
                                    -> yield getString(y)
                                       yield! (w::x) |> parse ([],true)
                | q::c::x,y,true when sepTest(c) && quotTest(q) 
                                    -> yield! (c::x) |> parse (y,false)
                | c::x,y,true when sepTest(c) 
                                    -> yield! x |> parse (c::y, true)
                | c::x,y,false when sepTest(c) 
                                    -> yield getString(y)
                                       yield! x |> parse ([], false)
                | c::x,y,z          -> yield! x |> parse (c::y, z)
                }
        match(line.ToCharArray() |> List.ofArray) with
        | [] -> Seq.empty
        | q::w::x when quotTest(q) && not(escTest(q,w)) 
                                -> (w::x) |> parse ([],true)
        | x -> x |> parse ([],false)

Yes, I’m sure I could probably come up with something simpler using a regular expression, but I’m playing around with parsers at the moment. I like the fact that using a combination of a sequence expression, a match statement, and a few lambda parameters, I can come up with a really general implementation like this. If you can think of ways to tidy the code even further, I’m open to suggestions!

Creating composable UI with F# and Prism

I’ve seen a lot of great demos recently of F# being used to create UI for WPF, Silverlight and Windows Phone. In all cases, this has been a very lightweight UI developed for one specific purpose. This is certainly a valid way to develop user interfaces – no need to overcomplicate, but I wondered if there is also a place for a more “grown up” solution, suitable for building complex applications from the ground up, using F#.

I have recently created a number of full blown user interfaces in C# using Microsoft Patterns & Practices Prism library. This library provides the building blocks for building maintainable yet complex user interfaces for WPF, Silverlight, Windows Phone. This is typically achieved through a central “shell” application, and a number of loosely coupled modules which contain parts of the user interface and other services.

I am going to attempt to write an F# silverlight application using Prism. This series will describe that process, but won’t necessarily go into detail about how Prism applications themselves work. I would highly recommend that anyone new to Prism watch Mike Taulty’s excellent series of videos on this subject, and then refer to the MSDN Developer’s Guide to Microsoft Prism.

Step 1 – Create the Shell Application

The first step will be to create the basic shell application, without any content. This will be a silverlight application, using F#, so ensure you download Microsoft Silverlight 4 Tools for Visual Studio 2010. I also installed the F# Silverlight Application Template so that I could create the initial silverlight application easily.

With the above installed, I created a silverlight app project named FSharpPrismShell and a Web application project, named Web.Host as a very basic host for this single silverlight app.

When I tested this basic setup, I discovered that the web application project, whilst allowing me to add my silverlight application in the “Silverlight Applications” tab of project properties, didn’t actually copy this over to ClientBin for some unknown reason. Instead, I just added a manual copy to the pre-build events:

xcopy /Y /R $(SolutionDir)FSharpPrismShell\Bin\Debug\FSharpPrismShell.xap $(ProjectDir)ClientBin

This allowed me to launch my empty silverlight application correctly in the browser.

Step 2 – Make the Shell Application a Prism Shell

Now we need to add Prism to the silverlight application project. I will do this using NuGet. If you don’t have NuGet yet, you should download and install this (in VS2010 use Tools –> Extension manager, then search for and install NuGet Package Manager).

From the Silverlight application project, right click and select Manage NuGet Packages:

Search the online packages for Prism. This should give the above list, so select and install Prism and Prism.UnityExtensions using this.

The contruction of all the elements required in a Prism application is managed by a Bootstrapper. I now need to change my application initialisation to create and run this Bootstrapper, which in turn will create and initialise the shell view (ie the root silverlight control).

So, I’ll firstly modify the default Page.xaml / MainPage combination to create Shell.xaml and Shell.fs.

<Grid x:Name="LayoutRoot" Background="Red">
 <TextBlock HorizontalAlignment="Center" VerticalAlignment="Bottom">The red area is from the Shell</TextBlock>
</Grid>

namespace FSharpPrismShell
open System
open System.Windows 
open System.Windows.Controls

type Shell() as this =
    inherit UserControl()
    do
        Application.LoadComponent(this, new System.Uri("/FSharpPrismShell;component/Shell.xaml", System.UriKind.Relative))
    let layoutRoot : Grid = downcast this.FindName("LayoutRoot")

    do 
        ()

Note that I have made the background red, and added the textbox to allow us to later see what belongs to the shell, and what belongs to the plug-in module. Next I’ll create the bootstrapper PrismBootStrapper.fs:

namespace FSharpPrismShell
open System
open System.Windows 
open System.Windows.Controls
open Microsoft.Practices.Prism.UnityExtensions
open Microsoft.Practices.Prism.Modularity

type PrismBootStrapper() =
    inherit UnityBootstrapper()

    override this.InitializeShell() =
        base.InitializeShell()
        Application.Current.RootVisual <- downcast this.Shell
        ()

    override this.CreateShell() =
        new Shell() :> DependencyObject

Finally I need to modify Program.fs to initialise and run this bootstrapper, rather than creating the shell directly itself:

let startup () =
    let bootStrapper = new PrismBootStrapper()     
    bootStrapper.Run()

I can now build and run this application. Note: I’m observing another weird issue – I seem to need to rebuild all before running each time, otherwise the browser launches with the previous version. Not sure if this is an issue with cassini or a problem with the pre-build steps.

Therefore, I have a working Prism shell application. The next step is to create a plug-in module for this, and wire the two halves together, so that the plug-in appears within this shell.

Step 3 – Create the Basic Plug-in Module

The most basic plug-in for Prism is a module which exposes a single view to be composed within the shell. This is what we will implement today. Create a second silverlight application project and name this one FSharpPrismModule.

Refactor the default Page.xaml / MainPage combination into MainView.xaml and MainView.fs:

<Grid x:Name="LayoutRoot" Background="Green">
    <TextBlock HorizontalAlignment="Center" VerticalAlignment="Center" FontSize="36">Hello, Modular UI</TextBlock>
    <TextBlock HorizontalAlignment="Center" VerticalAlignment="Bottom">The green area is from the Module</TextBlock>
</Grid>

type MainView() as this =
    inherit UserControl()
    do
        Application.LoadComponent(this, new System.Uri("/FSharpPrismModule;component/MainView.xaml", System.UriKind.Relative))
    let layoutRoot : Grid = downcast this.FindName("LayoutRoot")

    do 
        ()

Now create the discoverable type which implements IModule – this is the core of a Prism module, and will be used to register this module with the shell application later. We’ll call this ModuleDef.fs:

type ModuleDef(regionManager: IRegionManager) =

    interface IModule with
        member this.Initialize() =
            regionManager.RegisterViewWithRegion("ShellContent", typeof<MainView>) 
            |> ignore

What we do here is register a view which Prism will automatically use for any regions defined in the shell named “ShellContent”. Also note that the constructor parameter of type IRegionManager is automatically wired by Prism/Unity when the module is loaded. This is true of any interfaces registered with unity, and is the standard method for providing core services to loaded modules.

This will build and run fine, but we won’t yet see the module for two reasons – it hasn’t been registered with Prism, and we haven’t defined a region in the shell into which its UI should be placed.

Step 4 – Register the Module with the Shell

Firstly we need to update Shell.xaml to add a control which will act as the placeholder, into which Prism will inject the view from our module:

...
xmlns:Regions="http://www.codeplex.com/prism"
...

<Grid x:Name="LayoutRoot" Background="Red">
    <ContentControl Margin="20,20"
                 HorizontalAlignment="Stretch" VerticalAlignment="Stretch"
                 HorizontalContentAlignment="Stretch" VerticalContentAlignment="Stretch"
                 Regions:RegionManager.RegionName="ShellContent" />
    <TextBlock HorizontalAlignment="Center" VerticalAlignment="Bottom">The red area is from the Shell</TextBlock>
</Grid>

Now we need to create a module catalog, which is a xaml file defining the list of modules which Prism should make available as plug-ins. Note that this can also be achieved programmatically within the bootstrapper. We’ll create a file called modules.xaml and include this as content within the shell project.

<Modularity:ModuleCatalog 
    xmlns="http://schemas.microsoft.com/winfx/2006/xaml/presentation"
    xmlns:x="http://schemas.microsoft.com/winfx/2006/xaml"
    xmlns:sys="clr-namespace:System;assembly=mscorlib"
    xmlns:Modularity="clr-namespace:Microsoft.Practices.Prism.Modularity;assembly=Microsoft.Practices.Prism">
    <Modularity:ModuleInfo
        Ref="FSharpPrismModule.xap"
        ModuleName="FSharpPrismModule"
        ModuleType="FSharpPrismModule.ModuleDef, FSharpPrismModule, Version=1.0.0.0, Culture=neutral, PublicKeyToken=null">
    </Modularity:ModuleInfo>
</Modularity:ModuleCatalog >

Note that we are actually including the FSharpPrismModule xap file here, and specifying the type to be loaded within this xap file. Prism works out all the complexity of one xap file (the shell) including another xap file (the module) on our behalf.

In order for this to be found, I will need to update the prebuild step to xcopy this new xap file into the ClientBin directory

xcopy /Y /R $(SolutionDir)FSharpPrismModule\Bin\Debug\FSharpPrismModule.xap $(ProjectDir)ClientBin
xcopy /Y /R $(SolutionDir)FSharpPrismShell\Bin\Debug\FSharpPrismShell.xap $(ProjectDir)ClientBin

This said, I was initially banging my head against a wall when the runtime continued to fail to load FSharpPrismModule.ModuleDef. Eventually (with help from .NET Reflector) I realised that the generated module had the version number 0.0.0.0, so I added an AssemblyInfo.fs file to the module project:

open System.Reflection
open System.Runtime.CompilerServices
open System.Runtime.InteropServices

// The following GUID is for the ID of the typelib if this project is exposed to COM
[<assembly: Guid("06725367-D5EE-4D48-BC6B-827211C133A6")>]
[<assembly: AssemblyVersion("1.0.0.0")>]
[<assembly: AssemblyFileVersion("1.0.0.0")>]

()

In order for the module itself to be loaded, we need to ensure that the bootstrapper knows how to find the modules. In order to achieve this, I added another override to PrismBootStrapper.fs:

override this.CreateModuleCatalog() =
    let catalog = ModuleCatalog.CreateFromXaml(new Uri("modules.xaml", UriKind.Relative))
    catalog :> IModuleCatalog

So finally, Prism can find our module, load it, and determine that it can provide a view for the placeholder control within our shell. If we now run this application, the result will be:

That’s enough Prism for now. What we have is a very simple composed user interface written entirely in F#. It isn’t very useful yet, as we only have one module, we don’t have any additional services, or communication between the shell and the module or between modules. I’ll endeavour to expand this into something more useful in the near future, but for the moment this is a reasonable start.

Source code is available for download from bitbucket.

Creating a no-thrills custom type provider in F# 3.0 – some progress

I thought I would come at this from a different angle today. Following on from comments on the previous post, I decided it would make sense to try and find out what F#/Visual Studio does when I add a reference to my type provider.

So I have added a separate solution TypeProviderConsumer and opened that in another instance of VS 11. I create an empty F# console app project, and then go back to my type provider solution. Having corrected the omission that Ramon mentioned in a comment on my previous post, my type provider now looks like this:

using System;
using System.Reflection;
using Microsoft.FSharp.Core;
using Microsoft.FSharp.Core.CompilerServices;
    
[Serializable, TypeProvider, CompilationMapping(SourceConstructFlags.ObjectType)]
public class BasicTypeProvider : ITypeProvider, IProvidedNamespace, IDisposable
{
    Type baseType;

    public BasicTypeProvider(TypeProviderConfig config)
    {
        baseType = typeof(StaticType);
    }

    public Type ApplyStaticArguments(Type typeWithoutArguments, string typeNameWithArguments, object[] staticArguments)
    {
        return baseType;
    }

    public System.Linq.Expressions.Expression GetInvokerExpression(System.Reflection.MethodBase syntheticMethodBase, System.Linq.Expressions.ParameterExpression[] parameters)
    {
        return null;
    }

    public IProvidedNamespace[] GetNamespaces()
    {
        return new IProvidedNamespace[] { (IProvidedNamespace) this };
    }

    public System.Reflection.ParameterInfo[] GetStaticParameters(Type typeWithoutArguments)
    {
        return new ParameterInfo[] { };            
    }

    public event EventHandler Invalidate;

    public void Dispose()
    {
    }

    public IProvidedNamespace[] GetNestedNamespaces()
    {
        return new IProvidedNamespace[] { };
    }

    public Type[] GetTypes()
    {
        return new Type[] { baseType };
    }

    public string NamespaceName
    {
        get { return "TestTypeProvider"; }
    }

    public Type ResolveTypeName(string typeName)
    {
        if (string.Equals(typeName, "StaticType"))
        {
            return this.baseType;
        }
        return null;
    }
}

I set breakpoints in every method and property above, then choose Debug, Attach to Process and attach to the other instance of Visual Studio:

Switching back to the other instance, I add a reference to my custom type provider, and bam, we hit the first breakpoint. Awesome. Progress.

Checking out what config gets passed into our constructor:

If I keep hitting F5, it hits the breakpoints in this order:

GetNamespaces()
NamespaceName { get; }
GetTypes()
GetNestedNamespaces()

Then it repeats once more, starting at the constructor.

This is all good news – it means that I’m not missing some strange attribute or other construct. My type provider is being initialised and queried, so I guess at the moment I get the “This is not a provided type” message because I’m not implementing some or all of ITypeProvider or IProvidedNamespace correctly. This is something I can work on by getting my head back into FSharp.Data.TypeProviders. Watch this space.

As an aside – notice the TemporaryFolder property in the config above. If I take a look into the location to which it points, I find a number of generated dlls for the past few days. It turns out these are generated by the Linq to SQL type provider (which I have been testing alongside this investigation) in pairs – one for the type that I generate in my F# code (dbSchema) and another which contains the actual DataContext class and classes for each table in my database. This is good – I understand some more about what is generated under the hood for type providers, and should help me with the next stage of the investigation.

Creating a no-thrills custom type provider in F# 3.0 – attempt 1

F# 3.0 was released this week at the Microsoft Build conference as part of the Visual Studio 11 Developer Preview. Full details are available on the F# team blog – I recommend you read through this and have a play with the new features – it’s a really feature packed release.

I’m interested specifically in Type Providers, which are a new direction in F#, and provide some of the power of dynamic languages (types generated on the fly to wrap some form of structured data, such as XML from an OData service) but without the performance issues or late binding that come with these. Type Providers are actually an extensibility mechanism for the compiler, which allow for the compiler to query the type provider assembly, which does exactly that – provides types on the fly, which both the compiler and VS Intellisense can make use of. This all happens at compile time, and therefore whilst the code has features with a dynamic flavour, the result remains statically typed.

What I want to do is to create the simplest possible example of a custom type provider. Essentially I would like to create one which provides only one type, and that itself is just a static type within the type provider assembly, no Emit code this time around.

FSharp.Data.TypeProviders

There doesn’t appear to be much (any?) information available yet concerning custom type providers, so my first port of call is to crack open the key F# type providers assembly – FSharp.Data.TypeProviders.dll using Reflector, and see what I can find.

The key touch point appears to be in Microsoft.FSharp.Data.TypeProviders.DesignTime.DataProviders -

[Serializable, TypeProvider, CompilationMapping(SourceConstructFlags.ObjectType)]
public class DataProviders : ITypeProvider, IProvidedNamespace, IDisposable
{
// ...
}

And the key interface here, defined in Microsoft.FSharp.Core.CompilerServices is:

public interface ITypeProvider : IDisposable
{
    // Events
    [CLIEvent]
    event EventHandler Invalidate;

    // Methods
    Type ApplyStaticArguments(Type typeWithoutArguments, string typeNameWithArguments, object[] staticArguments);
    Expression GetInvokerExpression(MethodBase syntheticMethodBase, ParameterExpression[] parameters);
    IProvidedNamespace[] GetNamespaces();
    ParameterInfo[] GetStaticParameters(Type typeWithoutArguments);
}

So I should be able to create an assembly (in C# to start off with) containing a class of my own which implements this above interface, and that should give me a type provider, right?

using System;
using System.Reflection;
using Microsoft.FSharp.Core;
using Microsoft.FSharp.Core.CompilerServices;
    
[Serializable, TypeProvider, CompilationMapping(SourceConstructFlags.ObjectType)]
public class BasicTypeProvider : ITypeProvider, IProvidedNamespace, IDisposable
{
    Type baseType;

    public BasicTypeProvider()
    {
        baseType = typeof(StaticType);
    }

    public Type ApplyStaticArguments(Type typeWithoutArguments, string typeNameWithArguments, object[] staticArguments)
    {
        return baseType;
    }

    public System.Linq.Expressions.Expression GetInvokerExpression(System.Reflection.MethodBase syntheticMethodBase, System.Linq.Expressions.ParameterExpression[] parameters)
    {
        return null;
    }

    public IProvidedNamespace[] GetNamespaces()
    {
        return new IProvidedNamespace[] { (IProvidedNamespace) this };
    }

    public System.Reflection.ParameterInfo[] GetStaticParameters(Type typeWithoutArguments)
    {
        return new ParameterInfo[] { };            
    }

    public event EventHandler Invalidate;

    public void Dispose()
    {
    }

    public IProvidedNamespace[] GetNestedNamespaces()
    {
        return new IProvidedNamespace[] { };
    }

    public Type[] GetTypes()
    {
        return new Type[] { baseType };
    }

    public string NamespaceName
    {
        get { return "RegistryTypeProvider"; }
    }

    public Type ResolveTypeName(string typeName)
    {
        if (string.Equals(typeName, "StaticType"))
        {
            return this.baseType;
        }
        return null;
    }
}

Note that I have included the same attributes as used in the FSharp.Data.TypeProviders assembly, as I assume they’re important, and in all the implementations I just shunt around the StaticType type (which is just a POCO class with a couple of properties, for demo purposes). I don’t know how to handle GetInvokerExpression at the moment, so I’ll return null here, and just hope I get away with it.

Now I build this assembly, and then create a new F# console application project to act as the consumer of this type provider. Add a reference to the type provider assembly and then create a simple use in Program.fs -

open TestTypeProvider

[<Generate>]
type myType = TestTypeProvider.BasicTypeProvider

Sadly this doesn’t work. I get red squigglies under TestTypeProvider.BasicTypeProvider and the message “This is not a provided type. Consider removing the ‘Generate’ attribute from this type definition.” Thanks. Actually I’d prefer to have a working type provider, if you don’t mind.

If I look back at FSharp.Data.TypeProviders.dll I can see an assembly level attribute which might be important:

... 
[assembly: TypeProviderAssembly]
...

So I add that to my type provider project, rebuild (and looks like I need to remove the type provider assembly reference from my consumer project, and then restart visual studio in order to avoid problems with the type provider assembly being locked).

Nope. “This is not a provided type. Consider removing the ‘Generate’ attribute from this type definition.”

I’ve now tried many tweaks to the attributes and restarted VS many times but no luck getting around this error message. I think I will take a look at this again in the morning, and dig around inside Reflector to see what else I can discover.

SharpLines: a Sparklines library in F# for Silverlight

A few years back when considering data visualisation, I came across the works of Edward Tufte and specifically his amazing book Beautiful Evidence. This book is a treasure trove of information about the presentation of data, with examples from across the ages of charts, drawings, maps etc., where particular care has been taken in the way we visualise data. One particular technique that leapt out of the pages was the idea of Sparklines. A Sparkline is, to quote, “a small intense, simple, word-sized graphic with typographic resolution”.

A quick look through the comments following the Sparklines article above shows that there are plenty of implementations out there, and indeed an implementation is included in Excel 2010 (albeit with a certain degree of controversy due to Microsoft seeking to patent this technology). However I feel there is room for a library of lightweight, tight Sparklines controls for Silverlight (and maybe WPF), with implementation in F#.

Kicking this Off

Before cracking into any code, I want to decide upon some goals for the project. The essential goals are: Simple, Clean, Lightweight, as follows:

Simple – Initially design just two controls – the canonical Sparklines Line chart, as shown above, and also a gain/loss Bar chart.
Clean – Use the minimum of clutter in the visual representations. Sparklines are influenced greatly by typography, so the implementation must be clean, crisp and uncluttered, making it easy to see the essence of the data presented.
Lightweight – This will be a library of controls for use in Silverlight applications, so the smaller the better.

SharpLines Line Chart

For the line chart, we want a simple line graph representation, with a thin, clear, line drawn from the start datum to the end datum via the intervening points. We can highlight the start and end points with a small circle, and we can also highlight the local minimum and maximum.

Note that the grid shown above is for illustrative purposes only. The final representation will be just the line itself, and optionally up to four highlight circles. As per Tufte’s book, the ideal representation of these should read like a word – i.e. to be the same sort of size and shape as an average length word. Through experimentation I have determined this to be around 18 x 60 pixels, but we wont restrict the controls to one size – we can allow them to be scaled however the user desires.

I’m now ready to do some coding. What I need to start with is just taking a set of data points (an IEnumerable is all we need for this) and we will scale from the vertical range of this (min value to max value) to the vertical bounds of the control, and from the number of available data points to the horizontal bounds of the control.

Prime Numbers – Building the EulerMaths library in F#

Those of you who are doing Project Euler know what I am talking about by the EulerMaths library. There are certain fundamentals which crop up again and again in the questions and it is important to work these into a reusable and performant library.

The first and most obvious of these is the Prime Number generator. Many questions rely on generating a sequence of primes, or on determining whether or not an individual number is a prime. In this post I will step through a number of potential solutions, starting from the most naive, and going to my current state of the art.

Generating a Sequence of Primes – the Naive Solution

The algorithm for this solution is simple. Starting with what we know to be the lowest prime (2), count up to the highest number we want to test (which we call hp) , for each candidate we then test whether or not it is a prime. Lets look at that latter part first:

let isPrime n =
    let rec testAllDivisors d =
        if n = d then true
        else if n%d = 0 then false
                else testAllDivisors (d+1)
    testAllDivisors 2

This is a very common recursive pattern, we have an outer function with the simple parameter – n – the number to test, then define a recursive function with local scope. This recursive function steps through all possible divisors of n, starting from 2. If we find a divisor on the way, the number is not prime, if we reach n, then the number must be prime.

Note that the inner function uses tail recursion – the very last statement is the recursive call, and it performs no calculations with the result. This means the compiler can optimise out stack usage by removing the return address of each successive call to testAllDivisors, which effectively means the last call will return directly to isPrime, not to each of the previous execution of testAllDivisors. This means we can recurse as deep as we need, and will never see a StackOverflowException.

We can test performance of this routine with successively larger primes, and with timed mode on in F# Interactive (use the #time;; command to enable).

Digits	Prime	Time (ms)
5	50069	0
6	509203	2
7	5048423	23
8	50943779	295
9	506977979	2440
10	2147483647	9863

So with primes up to 7 digits or so, the performance isn’t too bad for one off tests, but you can see that if we were building a sequence of primes from this, the performance would degrade exponentially. Lets try this now.

let allPrimesUpTo hp =
    let rec testEachPrime n = seq {
        if n <= hp then
            if isPrime n then yield n
            yield! testEachPrime (n+1)
    }
    testEachPrime 2

So this function makes use of our prime test to obtain a sequence of primes up to a given maximum. This uses the recursive sequence generation pattern of yield followed by yield! and the tail recursive call, which is a really nice way of building sequences. When testing the timing of this, don’t forget that F# interactive will only iterate over the first 4 elements of the sequence, so you need to ensure that the entire sequence is enumerated when testing out the times. I used something like:

allPrimesUpTo 100000 |> Seq.length

Which forces enumeration of the entire sequence. So lets try that now, using a steadily increasing maximum:

Max	Highest Prime	Time (ms)
1000	997	2
10000	9973	30
100000	99991	2808
500000	499979	52644
1000000	999983	187455

What did I tell you! So this is acceptable for generating sequences of the lower primes, but becomes unusable very quickly. As many Euler problems are designed to weed out poorly optimised algorithms, you won’t get very far with this implementation.

Going Parallel

The next option we have is to keep the same brute force approach, but to identify a means to partition the calculations and run in parallel. If we firstly change testEachPrime to support a subrange of the overall range, and yield a sequence within this range:

let rec testEachPrime (f,t) = seq {
    if f <= t then
        if (isPrime f) then yield f
        yield! testEachPrime ((f+1),t)
}

What we also need to do it partition an overall range, of say 2 .. 100000 into a set of subranges which can be used for each parallel task. I make a few assumptions here, the main one being that the overall range will be many times larger than the number of tasks we will run, so an uncomplicated implementation will suffice:

let divideWork f t nd =
    let range = (t+1) - f
    if range < nd then failwith "Range is less than the number of divisions"
    let delta = range/nd
    [| 0 .. nd-1 |] |> Array.map (fun i -> let ti = ((i+1)*delta)-1
                                         ((i*delta)+f),(if i >= (nd-1) then t else ti+f))

This takes the overall range f..t and number of required divisions, returning an array of tuples representing the f..t of each subdivision. Because the division isn’t going to be perfect every time, the last pair will be truncated to ensure that its last value will always be the given t. So trying out our example from above we get:

> divideWork 2 100000 16;;
val it : (int * int) [] =
[|(2, 6250); (6251, 12499); (12500, 18748); (18749, 24997); (24998, 31246);
    (31247, 37495); (37496, 43744); (43745, 49993); (49994, 56242);
    (56243, 62491); (62492, 68740); (68741, 74989); (74990, 81238);
    (81239, 87487); (87488, 93736); (93737, 100000)|]

This is all we need now to divide our work up into subtasks, so piecing it together we get:

let allPrimesUpTo hp =
    let getResultsTask (f,t) =
        let rec testEachPrime (f,t) = seq {
            if f <= t then
                if (isPrime f) then yield f
                yield! testEachPrime ((f+1),t)
        }
        testEachPrime (f,t) |> Array.ofSeq

    let ntasks = System.Environment.ProcessorCount * 16

    if hp < (ntasks * 10) then
        getResultsTask (2,hp)
    else
        let taskArgs = divideWork 2 hp ntasks

        let results = 
            Async.Parallel [ for taskNo in 0 .. (ntasks-1) -> async { return getResultsTask taskArgs.[taskNo] } ]
            |> Async.RunSynchronously
        results |> Array.concat

Note first that we package testEachPrime into getResultsTask, which converts the sequence into an array. This is very important, as it ensures that the enumeration (and therefore calculations) are performed whilst running parallel. If you return just a sequence, the Async.Parallel does no work, and it all ends up running sequentially during the final call to Array.concat.

Next, we determine a number of tasks to run based on the CPU (or more specifically the number of cores). I will demonstrate later where the *16 comes in. If the prime we are looking for isn’t much lower than the number of tasks we will run, we don’t bother with the overhead of scheduling to threads, and instead just run the whole thing synchronously.

So finally, if we do want to run in parallel, we get the array of subranges, then setup and run an async workflow for each task, passing in this range as its parameter. This collates the task results into an array of arrays (which luckily is in the same order as our tasks run), which we can then concat into a single array of results. See Don Syme’s Blog for much more detail about how this works.

Determining how many Tasks to run

This will depend on each circumstance, and probably also has a lot to do with the individual processor architectures. My main machine has 8 cores (which is what System.Environment.ProcessorCount returns), but if I run with just 8 tasks, the workload doesn’t balance out too well:

You can see the falloff isn’t sharp, and some cores are clearly done before others. By gradually increasing the number of tasks, we hit a sweet spot at CPUs * 16, which gives us a more balanced looking load, without too much overhead (and we get the quickest overall times at this level).

This clearly looks much better, with clean ramp up and ramp down on each core. So with this in place, we can repeat our performance test from the previous implementation, and look again at the results, side by side:

Max	Highest Prime	Time (Naive) ms	Time (Parallel, 8 cores) ms	Speed up
1000	997	2	1	x2
10000	9973	30	7	x4
100000	99991	2808	372	x7.5
500000	499979	52644	6947	x7.5
1000000	999983	187455	26016	x7.2

This is great, more or less exactly the speed up we would expect, as there will always be a certain amount of overhead in spinning up threads, and in the concatenation of results once all tasks complete. However, this is only useful if you happen to have a nice big multi-core box, and clearly once we go beyond 10s of millions, we will be needing a cray if we stick with the brute force method.

Do it With a Sieve

There are occasions where the brute force approach is enough. However there is a much more elegant way to generate a sequence of primes, called the Sieve of Eratosthenes – which is explained better than I can, by means of an animated diagram, on the wikipedia entry.

Lets first implement a very functional version of this sieve:

let eratosthenesSieve =
    let allNaturalsFrom2 = Seq.initInfinite ((+)1) |> Seq.filter ((<=)2)
    let rec sieveNext sq = seq {
        let n = sq |> Seq.nth 0
        yield n
        let newSq = sq |> Seq.filter (fun i -> i%n <> 0)
        yield! sieveNext newSq
    }
    sieveNext allNaturalsFrom2

In this implementation we start with an infinite sequence of natural numbers, excluding 1, then pass this into the sieve which yields the first element (which is 2 to start with), and recurses using a new sequence which excludes all members in the originals sequence which are multiples of 2, then does 3, 5, …

It works great, but look at the times:

> eratosthenesSieve |> Seq.take 100 |> Seq.nth 99;;
Real: 00:00:00.133, CPU: 00:00:00.124, GC gen0: 1, gen1: 0, gen2: 0
val it : int = 541
> eratosthenesSieve |> Seq.take 200 |> Seq.nth 199;;
Real: 00:00:01.782, CPU: 00:00:01.778, GC gen0: 6, gen1: 0, gen2: 0
val it : int = 1223
> eratosthenesSieve |> Seq.take 300 |> Seq.nth 299;;
Real: 00:00:08.443, CPU: 00:00:08.455, GC gen0: 16, gen1: 1, gen2: 0
val it : int = 1987
> eratosthenesSieve |> Seq.take 400 |> Seq.nth 399;;
Real: 00:00:25.824, CPU: 00:00:25.786, GC gen0: 29, gen1: 1, gen2: 0
val it : int = 2741

This clearly is not going to be much use for us. Perhaps if we make the sequences finite, the results will improve?

let eratosthenesSieveFinite hp =
    let allNaturalsFrom2 = seq [2..hp]
    let rec sieveNext sq = seq {
        if (sq |> Seq.length) > 0 then
            let n = sq |> Seq.nth 0
            yield n
            let newSq = sq |> Seq.filter (fun i -> i%n <> 0)
            yield! sieveNext newSq
    }
    sieveNext allNaturalsFrom2

Lets try this with the same sizes of sequence (we use the biggest prime returned above to ensure the sequence sizes are the same:

> eratosthenesSieveFinite 541 |> Seq.take 100 |> Seq.nth 99;;
Real: 00:00:00.387, CPU: 00:00:00.390, GC gen0: 4, gen1: 0, gen2: 0
val it : int = 541
> eratosthenesSieveFinite 1223 |> Seq.take 200 |> Seq.nth 199;;
Real: 00:00:05.262, CPU: 00:00:05.382, GC gen0: 22, gen1: 1, gen2: 1
val it : int = 1223
> eratosthenesSieveFinite 1987 |> Seq.take 300 |> Seq.nth 299;;
Real: 00:00:25.003, CPU: 00:00:25.006, GC gen0: 50, gen1: 3, gen2: 0
val it : int = 1987

Wow, that’s MUCH worse. Postulating that dealing with enumerable sequences rather than cold, hard arrays sucks our perf, lets try this same solution, but using arrays instead of sequences. Also, I realise we should stop eliminating once n passes sqrt(hp) so we can add a check for that:

let eratosthenesSieveArrays hp =
    let allNaturalsFrom2 = [|2..hp|]
    let limit = int(sqrt(float(hp)))
    let rec sieveNext sq = [|
        if (sq |> Array.length) > 0 then
            let n = sq.[0]
            if n > limit then
                for n in sq -> n
            else
                yield n
                let newSq = sq |> Array.filter (fun i -> i%n <> 0)
                yield! sieveNext newSq
    |]
    sieveNext allNaturalsFrom2

Which is a vast improvement. Lets merge the new perf results into our performance grid:

Max	Highest Prime	Time (Naive) ms	Time (Parallel, 8 cores) ms	Time (Array Sieve) ms
1000	997	2	1	1
10000	9973	30	7	45
100000	99991	2808	372	176
500000	499979	52644	6947	2164
1000000	999983	187455	26016	2853

So now the functional sieve approach is generally faster than even the 8 core parallel approach. One final approach we should try is to go for a slightly more imperative style – create a mutable array containing all potential primes, and then step through the sieve crossing out elements in the array (setting to 0), finally returning a sequence of all non-zero elements from the array.

let eratosthenesSieveImperative hp =
    let limit = int(sqrt(float(hp)))
    let primes = [| 0 .. hp |]
    primes.[1]     let rec iterate n =
        if n < limit then
            [2*n .. n .. hp ] |> Seq.iter (fun i -> primes.[i]             let n = primes |> Seq.filter ((<)n) |> Seq.nth 0
            iterate n
    iterate 2
    primes |> Seq.filter ((<>)0)

This gives the best results so far:

Max	Highest Prime	Time (Naive) ms	Time (Parallel, 8 cores) ms	Time (Array Sieve) ms	Time (Imperative Sieve) ms
1000	997	2	1	1	8
10000	9973	30	7	45	7
100000	99991	2808	372	176	54
500000	499979	52644	6947	2164	267
1000000	999983	187455	26016	2853	616

This goes to show that sometimes you need to sacrifice some of the beauty of functional code to glean that last step in performance. Here we have a mutable array being used for working, but we still follow best practices by not exposing this mutable data to the caller of this function. One thing to bear in mind with this approach though, is that we are creating an in-memory array, so if you go much higher than a few million primes, you will risk running out of memory.

Parallel isPrime

Sometimes all we want to do is check a single number for prime, and especially if this number is very large, we don’t want to generate a sequence or run out of memory by using a sieve, so lets use our knowledge about parallelising tasks, and create a parallel version of isPrime:

let isPrimeParallel n =
    let getResultsTask (f,t) =
        let rec testAllDivisors (f,t) =
            if f = t then true
            else if n%f = 0 then false
                 else testAllDivisors (f+1,t)
        testAllDivisors (f,t)

    let ntasks = System.Environment.ProcessorCount * 16

    if n < (ntasks * 10) then
        getResultsTask (2,n)
    else
        let taskArgs = divideWork 2 n ntasks

        let results = 
            Async.Parallel [ for taskNo in 0 .. (ntasks-1) -> async { return getResultsTask taskArgs.[taskNo] } ]
            |> Async.RunSynchronously
        not(results |> Seq.exists ((=)false))

So the logic here is to divide up the problem space again, and run the prime test logic on subsets, collate the results, and only return true if each subtask returned true (i.e. none of them found a divisor). Lets compare the perf of this with the original.

Digits	Prime	Original Time (ms)	Parallel (ms)
5	50069	0	4
6	509203	2	1
7	5048423	23	3
8	50943779	295	45
9	506977979	2440	305
10	2147483647	9863	1285

Conclusion

I wouldn’t suggest you need to do this depth of analysis on all problems, but for very critical parts of your Euler toolset, it is clearly worth digging into the options. There are still optimisations we could do here – for example the parallel isPrime could support cancellation, so that all tasks abort as soon as we find a divisor, as we know then that the number is not a prime.

My First F# Post

I have been experimenting with F# for a couple of years now, occasionally solving problems from Project Euler but have never got around to posting a blog entry on this subject. Recently I have been lucky enough to spend some time with Don Syme and the people of the excellent F#unctional Londoners user group, a number of whom complained that I don’t have an F# blog, so I thought I had better put my money where my mouth is and put a post together.

Getting Started

F# is a functional programming language based on OCaml which combines the best of both worlds in terms of the pure functional aspects of ML and pragmatic use of imperative / object oriented language features. F# is now a first class member of the .NET languages and is part of Visual Studio 2010.

If you are new to F#, my recommended training list is as follows:

Firstly, get a taster by following Don’s excellent introductory series on Channel 9.
After that, learn what functional programming is all about in Real World Functional Programming by Tomas Petricek and Jon Skeet.
Finally, read Expert F# 2.0 by Don Syme himself, Adam Granicz and Antonio Cisternino which does what it says on the cover.

There are also a number of (proper) blogs on F#, such as Don’s (linked above), Tomas Petricek, Robert Pickering, Luca Bolognese and Phillip Trelford.

What’s it all About?

I have already worked through over 50 of the puzzles in Project Euler, most of which I solved using F#. This is a fantastic way to improve both your F# and your maths skills (by the way several people have told me they don’t do Project Euler because their F#/maths skills aren’t good enough – if you think this, you have got it backwards, you will improve both as you work your way through).

Regarding Project Euler – if you have come to this post simply to find the solution, then I feel sorry for you, you have missed the point. I would really recommend that you have a good stab at the solution yourself before reading any further. The sense of achievement as you increment that score one by one is strangely addictive, and if you just copy the work of others, you miss out on all of that.

That said, this post will take you through my solution for Euler 54, which (somewhat unusually) isn’t a particularly mathematical problem, but turns out to be a great way to demonstrate some of the features of the F# language. The basic principle of this problem is to compare two hands of cards in the game of poker, and to determine which is the winning hand.

Representing the Cards

The first step is to come up with a representation for the playing cards themselves, as well as some functions for parsing from a plain text description (which is what the Euler problem provides) and for evaluating individual cards. The representation here uses discriminated unions, and is similar to that shown in chapter 3 of Programming F# by Chris Smith.

type Suit =<br>    | Hearts<br>    | Diamonds<br>    | Clubs<br>    | Spades<br><br>type Card =<br>    | Ace of Suit<br>    | King of Suit<br>    | Queen of Suit<br>    | Jack of Suit<br>    | Value of int * Suit<br>

These two discriminated unions allow us to represent any of the cards found in a deck of playing cards, eg Ace(Spades) or Value(2,Hearts). Next we need a function to take the string representation of a card (such as “AS”, “2H”, “TC”) and return a value of the relevant discriminated union.

let parseCard (s:string) =<br>    let parseSuit (c:char) =<br>        match c with<br>        | 'H' -> Hearts<br>        | 'D' -> Diamonds<br>        | 'C' -> Clubs<br>        | 'S' -> Spades<br>        | _ -> failwith "Unknown suit"<br>    let charVal (c:char) = int(c)-48<br>    if s.Length <> 2 then failwith "Card should be 2 characters in length"<br>    let suit = parseSuit s.[1]<br>    match s.[0] with<br>    | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9' -> Value(charVal(s.[0]),suit)<br>    | 'T' -> Value(10,suit)<br>    | 'J' -> Jack(suit)<br>    | 'Q' -> Queen(suit)<br>    | 'K' -> King(suit)<br>    | 'A' -> Ace(suit)<br>    | _ -> failwith "Unknown rank"<br>

Talking through this routine, you can see we have a helper function (which is local in scope to the function itself) called parseSuit which takes a single character and attempts to parse this into a suit by using a pattern matching expression. Within the main body of the routine we ensure that the string is 2 characters, no more, no less, get the suit, and then finally pattern match the rank of the card. For the numeric characters we use the tried and tested technique of subtracting the ASCII value of ’0′ in order to convert the char into a numeric value.

Playing with these functions in the enormously useful F# Interactive REPL window, we can check they work as expected:

> parseCard "KS";;<br>val it : Card = King Spades<br>> parseCard "3D";;<br>val it : Card = Value (3,Diamonds)<br>> parseCard "ZD";;<br>System.Exception: Unknown rank<br>at FSI_0008.parseCard(String s) in C:\Svn\roundthecampfire\trunk\ProjectEuler\EulerHost\Euler54.fs:line 46<br>at <StartupCode$FSI_0011>.$FSI_0011.main@()<br>Stopped due to error

And to conclude this section, lets create a function to load the two hands (as a tuple) from a single line of 10 cards as per the supplied poker.txt file, and then try that function on a couple of lines from the file.

let parseHands (sl:string) =<br>    let parts = sl.Split(' ')<br>    if parts.Length <> 10 then failwith "Hands must be 10 cards"<br>    else<br>        let comb = parts |> Array.map parseCard<br>        (Array.sub comb 0 5 |> List.ofArray),(Array.sub comb 5 5 |> List.ofArray)<br>

This is our first use of some of the really cool F# higher order functions, such as Array.map and List.ofArray, as well as the forward pipe |> operator. Essentially this function gets an array of the individual 2 char strings, and projects these using Array.map and parseCard into a set of 10 cards. These cards are then split into two hands of 5 cards using Array.sub.

> parseHands "8C TS KC 9H 4S 7D 2S 5D 3S AC";;<br>val it : Card list * Card list =<br>([Value (8,Clubs); Value (10,Spades); King Clubs; Value (9,Hearts);<br>    Value (4,Spades)],<br>[Value (7,Diamonds); Value (2,Spades); Value (5,Diamonds); Value (3,Spades);<br>    Ace Clubs])<br>> parseHands "5C AD 5D AC 9C 7C 5H 8D TD KS";;<br>val it : Card list * Card list =<br>([Value (5,Clubs); Ace Diamonds; Value (5,Diamonds); Ace Clubs;<br>    Value (9,Clubs)],<br>[Value (7,Clubs); Value (5,Hearts); Value (8,Diamonds); Value (10,Diamonds);<br>    King Spades])

Functions to Determine the Rank of a Hand

Now that we have our hands of cards, we need a way to determine the highest rank to which a hand belongs, and giving us enough data to be able to compare two hands of the same rank, by checking the highest card which is part of the rank (e.g. a two pairs of Ace,Ace and 9,9 is higher than two pairs of King,Kind and 10,10) or highest cards which aren’t part of the rank (e.g. pair of Kings with Ace high is better than pair of Kings with Jack high).

Before we do this, we need a function to return the relative value of cards as per 2,3,4,5,6,7,8,9,T,J,Q,K,A and a function which returns just the suit for a given card (so we can check for flushes).

let valueOf (c:Card) =<br>    match c with<br>    | Ace(_) -> 12<br>    | King(_) -> 11<br>    | Queen(_) -> 10<br>    | Jack(_) -> 9<br>    | Value(n,_) -> n - 2<br><br>let suitOf (c:Card) =<br>    match c with<br>    | Ace(s) | King(s) | Queen(s) | Jack(s) | Value(_,s) -> s<br>

As you can see, valueOf means nothing in terms of any card game, but allows us to easily see that valueOf(Value(9,Spades)) < valueOf(King(Clubs)) for example.

Now it gets tricky, bear with me through this, hopefully this para and following examples will clarify. I decided to come up with a standard type for each rank matching function. Each function needs to take a list of cards as its input, returning firstly true or false to indicate whether the hand matches that rank, but also returning two arrays of card values each in descending order – the first array is the values which are part of the rank (eg for two pairs, 9s and Aces, the array would be [| 12; 7 |]); and the second array is any cards which remain that are not in the rank (eg for a hand 9H 9C AS TD 2C this matches a pair of 9s with remaining array of [| 12; 8; 0 |]).

So the type of these functions is Card list -> bool * int [] * int [] – we can use this to build a list of the ranking functions from highest (a royal flush) to the lowest (single card high), allowing us to try each in turn until one or both hands matches, and thus compare the hands. First I will define a few more helper functions that we will use in the ranking functions:

let desc n = -n<br><br>let allSameSuit (hand:Card list) =<br>    (hand |> Seq.map suitOf |> Seq.distinct |> Seq.length) = 1<br>

The desc function is used for Seq.sortBy to reverse the order of an integer based sequence simply by negating the input, and allSameSuit is a predicate to determine when all the cards in a given hand belong to just one suit.

MatchHighCard

The lowest rank is X-High, meaning that the hand only contains single cards, and when comparing two hands of this rank, we compare card by card, until one hand has the higher card. Therefore any hand (which doesn’t match a higher rank) will match this rank, and all cards in the hand are included in the rank, so appear in the first array, the second array being empty (as there are no remaining cards after those which belong to the rank are removed).

let matchHighCard (hand:Card list) : (bool*int []*int []) =<br>    true, (hand |> Seq.map valueOf |> Seq.sortBy desc |> Array.ofSeq), [||]<br>

So the implementation is pretty simple, true, followed by the card values in descending order.

MatchTwoPairs

The next example is for two pairs. Here we have two sets of two cards which are in the rank, and a single remaining card.

let matchTwoPairs (hand:Card list) : (bool*int []*int []) =<br>    let matches =<br>        hand |> Seq.map valueOf |> Seq.groupBy (fun n -> n)<br>             |> Seq.map (fun (n,s) -> n,(Seq.length s))<br>             |> Seq.sortBy (fun (_,l) -> -l) |> Array.ofSeq<br>    if (Seq.length matches) <> 3 || (matches.[0] |> snd) <> 2 || (matches.[1] |> snd) <> 2 then false,[||],[||]<br>    else true,([| fst(matches.[0]); fst(matches.[1]) |] |> Array.sortBy desc),[| fst(matches.[2]) |]<br>

This is one of the more complex implementations. We firstly get the card values and group by those values. Seq.groupBy gives us a sequence of tuples, the first value being the card value itself, the second is itself a sequence of each matching value (which is a bit nugatory in this case, as these are just sequences of the same value, hence in the following Seq.map we collapse these into just the number of occurrences). At this point we sort by the sequence length descending (using a custom lambda here as we are dealing with tuple values) and convert to an array for ease of indexing.

You probably need to see an example now. If the original hand was something like “9S JC 2D 2H JS”, we get a value sequence of seq [ 7; 9; 0; 0; 9 ]. Following all our mappings we are left with an array of tuples [| (9,2); (0,2); (7,1) |].

Now we can check this array to see if it represents two pairs. It must have three elements, and the first two elements must represent pairs (the snd function gets the second value from the tuple, which is the number of occurrences of the given value). If these do not match, this isn’t a rank of Two Pairs, so we return false and empty arrays.

If this is a match, we return true, with an array of two values (the highest of the pairs, then the lowest of the pairs), and finally the single remaining card value.

MatchStraightFlush

This is the last of my examples. A straight flush means the cards are all consecutive values, starting at any value, and they are all of the same suit.

let matchStraightFlush (hand:Card list) : (bool*int []*int []) =<br>    let values = hand |> List.map valueOf |> List.sort |> Seq.distinct |> Array.ofSeq<br>    if (Array.length values) <> 5 || (values.[4] - values.[0]) <> 4 || not (allSameSuit hand) then false,[||],[||]<br>    else true, [|values.[4]|], [||]<br>

First we get the values, sort and remove duplicates (if there are dups, it can’t be a straight – we check for this next). So now, if we don’t have 5 cards, this isn’t a match, or if the highest value – lowest value is not 4, then they are not consecutive, so not a match, or if they are not all the same suit, it isn’t a match.

Where we have a match, the value of the highest card in the straight is returned.

Comparing the Hands

Lets define a utility function first. This takes two arrays, comparing item by item until a difference is found, returning negative to indicate the first array is greater, positive if the second array is greater, 0 if they are equal. We will use this to compare cards when two hands are of the same rank.

let compArrays (a:int [], b:int []) =<br>    if Array.length(a) <> Array.length(b) then failwith "Array lengths differ"<br>    let rec innerCompArrays (a:int [], b:int [],n) =<br>        if n = Array.length(a) then 0<br>        else<br>            if a.[n] <> b.[n] then b.[n] - a.[n]<br>            else innerCompArrays(a,b,(n+1))<br>    innerCompArrays(a,b,0)<br>

Note the array lengths must be equal, and we assume they are both in the same order. We use a simple recursive function to step through item by item until the end of the array is reached, or a difference is found.

Now we can define our ordered list of match functions (note there are more than shown above, other implementations left as an exercise for the reader):

let matchFuncs =<br>    [   matchRoyalFlush<br>        matchStraightFlush<br>        matchFourOfAKind<br>        matchFullHouse<br>        matchFlush<br>        matchStraight<br>        matchThreeOfAKind<br>        matchTwoPairs<br>        matchAPair<br>        matchHighCard<br>    ]<br>

We finally have everything we need to do the comparison of two poker hands. We can bring this all together in a single function which itself iterates over the above list of functions until a match is found for one or both hands, then, if needed, comparing the cards in the hand and then remaining cards to find a winner:

type matchFunc = (Card list) -> (bool * int [] * int [])<br><br>let compareHands (hands:string) =<br>    let rec innerCompareHands (handA:Card list, handB:Card list, funcs:matchFunc list) =<br>        match funcs with<br>        | [] -> failwith "No Winning Hand!"<br>        | f::tail -><br>            let mtchA,incA,remainA = f(handA)<br>            let mtchB,incB,remainB = f(handB)<br>            match mtchA,mtchB with<br>            | true,false -> 1<br>            | false,true -> -1<br>            | true,true -><br>                let c = compare incA incB<br>                if c <> 0 then c<br>                else compare remainA remainB<br>            | false,false -><br>                innerCompareHands (handA,handB,tail)<br>    let handA, handB = parseHands(hands)<br>    if innerCompareHands (handA, handB, matchFuncs) > 0 then 1 else 2<br>

UPDATE: Realised that the compArrays function was redundant, as the F# compare function works as well with lists and arrays as it does with simpler values. Updated the above accordingly.

Here we parse the string containing the two hands into the separate hands, then iterate over this using the inner recursive function. We work through each function in the list, testing both hands, then the inner pattern match checks the two match results side by side to find an outright winner (false,true or true,false) a draw (true,true) in which case we compare first the cards in the matching rank, then the remaining cards if still a draw. If there are no matches for this function, we move to the next rank and test for that. Note that the check for no remaining functions isn’t ever going to be exercised as matchHighCard will always match. The final result indicates a win for player 1 or player 2

> compareHands "JH 2D 3S JC AS 7D 3C AH 7C 7S";;<br>val it : int = 2<br>> compareHands "TS JS QS KS AS 7D 3C AH 7C 7S";;<br>val it : int = 1

We can see this works fine – in the first example the second hand (three 7s) beats the first (pair of Jacks), and in the second example, the first hand wins as it is a Royal Flush.

Conclusion

We can see that F# code really lends itself to breaking down a problem like this. We use discriminated unions to represent our model very succinctly. We use pattern matching for parsing and checking card values, we use higher order functions on sequences and arrays to concisely compose our rank matching functions, and we use an array of these functions just as easily as any other data type to build our final comparison routine.

With some work, I could probably make this even more succinct, maybe by using active patterns to replace the recursion over the array of functions with a pattern matching expression instead, but hopefully the above demonstrates that a “good enough” solution has been achieved. In case you are interested, the final result is calculated in 188ms, including reading the file.

Building an OData consumer for Windows Phone 7 Series, Part 2

In Part 1 I talked about the rough outline of the application – a WP7S app which talks to a publically available OData service (the NerdDinner service) and presents a master detail view of this, with geographical data. We looked at installing the tools, building a WP7S application, and walked around the architecture of the application.

Today I will add the OData service call and implement binding from the master view to the data retrieved, and make sure that this data is rendered in the list in a pleasing manner.

Calling the OData Service

If you haven’t done so already, download the OData client library and unzip the files into a local directory. Add a reference from the NerdDinnerFinder project to System.Data.Services.Client.dll.
Currently there is no documentation available specifically for WP7S, but this blog post by Well Phani describes how to add a service reference using the DataSvcutil.exe tool in the framework 4.0 directory.

Using an Admin command prompt, navigate to the NerdDinnerFinder project directory, then execute this command:

%WINDIR%\Microsoft.NET\Framework\v4.0.30128\DataSvcUtil.exe /?

This gives the following output:

Microsoft (R) DataSvcUtil version 4.0.0.0<br>Copyright (C) 2008 Microsoft Corporation. All rights reserved.<br><br>DataSvcUtil Options<br>/in:<file>               The file to read the conceptual model from<br>/out:<file>              The file to write the generated object layer to<br>/language:CSharp         Generate code using the C# language<br>/language:VB             Generate code using the VB language<br>/Version:1.0             Accept CSDL documents tagged with<br>m:DataServiceVersion=1.0 or lower<br>/Version:2.0             Accept CSDL documents tagged with<br>m:DataServiceVersion=2.0 or lower<br>/DataServiceCollection   Generate collections derived from DataServiceCollection<br>/uri:<URL>               The URI to read the conceptual model from<br>/help                    Display the usage message (short form: /?)<br>/nologo                  Suppress copyright message<br><br>Examples<br>To generate code from a data service.<br>DataSvcUtil /out:"data.cs" /uri:"http://localhost/data.svc"<br><br>To generate code from a conceptual model file.<br>DataSvcUtil /out:"data.cs" /in:"file.csdl"<br><br>To generate code from a entity design model file.<br>DataSvcUtil /out:"data.cs" /in:"file.edmx"

So using the blog post above as guidance, we can generate our classes directly from the live OData service by using the command”:

%WINDIR%\Microsoft.NET\Framework\v4.0.30128\DataSvcUtil.exe
/uri:http://www.nerddinner.com/Services/OData.svc/
/DataServiceCollection /Version:2.0 /out:nerdDinnerService.cs

This creates the file nerdDinnerService.cs which we can now directly include in our project, and take a look at. What we have is a fairly standard looking codegen file with three classes: NerdDinnerEntities, Dinner and RSVP under the NerdDinnerModel namespace. The NerdDinnerEntities class is our entry point, and derives from DataServiceContext in System.Data.Services.Client. The other two classes are our data objects.

Experimenting with the NerdDinnerEntities class, there doesn’t appear to be any obvious ‘Linqy’ way to deal with the data. If I try to directly bind to the Dinners collection it comes back with an opaque NotSupportedException which isn’t much help. Just for the sake of getting things moving, lets use the BeginExecute and EndExecute methods:

private void MainPage_Loaded(object sender, RoutedEventArgs e)<br>{<br>    // Reset page transition<br>    ResetPageTransitionList.Begin();<br><br>    context = new NerdDinnerEntities(new Uri(<a href="http://www.nerddinner.com/Services/OData.svc">http://www.nerddinner.com/Services/OData.svc</a>));<br>    context.BeginExecute<Dinner>(new Uri("/Dinners",UriKind.Relative), DinnerReady, null);<br>}<br><br>private void DinnerReady(IAsyncResult asyncResult)<br>{<br>    Deployment.Current.Dispatcher.BeginInvoke(<br>        () =><br>        {<br>            IEnumerable<Dinner> results = context.EndExecute<Dinner>(asyncResult).ToList() as IEnumerable<Dinner>;<br>            lstDinners.ItemsSource = results;<br>        }<br>        );<br>}

This seems heavy handed, as we have to hand code the relative URI, but it does seem to work. In order to get this to display correctly, we will need to make some changes to the xaml (we should change the name of the list box, and make some changes to the ItemTemplate in order to get the sample listbox to bind to the data we are returning). Replace the entire ListBox element with the following:

<ListBox x:Name="lstDinners" MouseLeftButtonUp="ListBoxOne_MouseLeftButtonUp" <br>        Style="{StaticResource PhoneListBox}"><br>    <ListBox.ItemTemplate><br>        <DataTemplate><br>            <StackPanel x:Name="DataTemplateStackPanel" Orientation="Vertical"><br>                <TextBlock Text="{Binding Title}" Style="{StaticResource PhoneTextLargeStyle}" /><br>                <TextBlock Text="{Binding Description}" Style="{StaticResource PhoneTextNormalStyle}" /><br>            </StackPanel><br>        </DataTemplate><br>    </ListBox.ItemTemplate><br></ListBox>

So we change the name, remove the declarative data binding from ItemsSource and update the ItemTemplate with a more simple view onto our Dinner items. If we run this now, we should get a sensible result:

This is our master view, now we need to change the item selection event handler to navigate from this page to the detail page – it already does, but we need to pass in the Id of the selected dinner, so some tweaks are required.

private void ListBoxOne_MouseLeftButtonUp(object sender, MouseButtonEventArgs e)<br>{<br>    // Capture selected item data<br>    selectedItem = (sender as ListBox).SelectedItem as Dinner;<br><br>    // Start page transition animation<br>    PageTransitionList.Begin();<br>}<br><br>private void PageTransitionList_Completed(object sender, EventArgs e)<br>{<br>    // Set datacontext of details page to selected listbox item<br>    NavigationService.Navigate(new Uri(String.Format("/DetailsPage.xaml?id={0}",selectedItem.DinnerID), UriKind.Relative));<br>}

Note the change to NavigationService.Navigate – by passing in the id as a query string parameter, we can ensure that the navigation will work even with application dehydration/rehydration. With this in place we can make the corresponding change in DetailsPage.xaml.cs and then we are ready to implement the details view.

<Grid x:Name="LayoutRoot" Background="{StaticResource PhoneBackgroundBrush}" d:DataContext="{Binding Items[0]}"><br>    <Grid.RowDefinitions><br>        <RowDefinition Height="Auto"/><br>        <RowDefinition Height="*"/><br>    </Grid.RowDefinitions><br><br>    <!--TitleGrid is the name of the application and page title--><br>    <Grid x:Name="TitleGrid" Grid.Row="0"><br>        <Grid.Projection><br>            <PlaneProjection/><br>        </Grid.Projection><br>         <br>        <TextBlock Text="NERD DINNER FINDER" Style="{StaticResource PhoneTextPageTitle1Style}"/><br>        <TextBlock Text="{Binding Title}" Style="{StaticResource PhoneTextPageTitle2Style}"/><br>    </Grid><br><br>    <!--ContentGrid contains the details--><br>    <Grid x:Name="ContentGrid" Grid.Row="1"><br>        <Grid.Projection><br>            <PlaneProjection/><br>        </Grid.Projection><br><br>        <StackPanel Orientation="Vertical"><br>            <TextBlock Text="{Binding Description}" Margin="20,0,20,0" TextWrapping="Wrap" Style="{StaticResource PhoneTextSmallStyle}"/><br>            <StackPanel Orientation="Horizontal"><br>                <TextBlock Text="Hosted by " Style="{StaticResource PhoneTextBodyTextStyle}"/><br>                <TextBlock Text="{Binding HostedBy}" Style="{StaticResource PhoneTextBodyTextStyle}"/><br>            </StackPanel><br>        </StackPanel><br>    </Grid><br></Grid>

This ensures that the current item (which is bound to the page itself) is used to populate the various text boxes on this page. The result gets us where we need to be for today:

Round Up

Today we have installed the OData client library, struggled a little bit in understanding the model this exposes (a little documentation here would help a lot), and come up with a 50% elegant solution for bringing in the data we need and binding this within the master view and the detail view.

In the final article, I will try and make use of the geographical data we get back from this service to enable an inset map showing the location of the event on the details page.

Building an OData consumer for Windows Phone 7 Series, Part 1

Having recently returned from MIX 2010, two of the technologies which stuck in my mind were OData (and specifically the latest incarnation of project Astoria – WCF Data Services) and of course the first CTP of the Windows Phone 7 series SDK.

I am already working on a WP7S application for the marketplace, but I thought it would be an interesting aside to put together a bit of a mash-up application which consumes an OData service, presents a pleasing view over this data using silverlight, and supports viewing location data using Bing maps. I will document the construction of this application in three parts, this being the first.

Finding an OData Service

We could, of course, write our own OData service against the Northwind database or similar, but for the sake of simplicity, I thought it would be better to consume one of the sample services from the OData site. For this demonstration I will use the NerdDinner Service.

As you can see, this is a pretty basic service at the moment, but will suffice for this demonstration. What we would like to do is drill down into the Dinners category, present a list of available dinners, and then provide an interface to drill down into a particular dinner and show the details (including the location).

Getting Started

In order to develop this application you will need to download and install the following components:

The first link will download everything you need to develop for WP7S – Visual Studio 2010 Express Edition, the WP7S Emulator, Silverlight SDK and XNA Game studio. Note that if you already have an edition of VS 2010 installed, it will also install the necessary project templates for that.

Creating the Application

We can make use of existing project templates to get us started quickly. Launch VS2010 and create a new project from Visual C# > Silverlight for Windows Phone > Windows Phone List Application. Name the project & solution NerdDinnerFinder.

This will create a new windows phone project which contains the application (App.xaml) and two silverlight pages (MainPage.xaml and DetailsPage.xaml). If we open up the designer for MainPage.xaml, we can see the design view of the page as it would look on the phone, side by side with the xaml code.

Notice that this has already created us a master/details view in effect, so all we need to do is plumb in the OData service to these xaml pages. If you build and run this application as it stands, it will launch the WP7S emulator (which takes about a minute to load the first time, but thereafter very quick as long as you leave it running).

Examining the Build Output

It’s always good to try and ensure we get a deeper understanding of what happens under the hood. Lets take a look at the artifacts produced by this build, and see what they have to show us:

The NerdDinnerFinder.xap file is actually the single file which will be deployed to the device. We can use a trick from the silverlight development toolbox to see what this file contains – simply rename it with a .zip extension and open it in explorer. Within this we can see the same files, and one additional – WMAppManifest.xml.

We therefore have two .png files to store various size of icon imagery for the use of the phone OS, we have the actual dll and pdb for our single project, then two manifest files.

AppManifest.xaml simply describes the application and the binary files of which it is comprised:

<Deployment xmlns="http://schemas.microsoft.com/client/2007/deployment" <br>    xmlns:x="http://schemas.microsoft.com/winfx/2006/xaml" <br>    EntryPointAssembly="NerdDinnerFinder" <br>    EntryPointType="NerdDinnerFinder.App" <br>    RuntimeVersion="3.0.40624.0"><br>    <Deployment.Parts><br>        <AssemblyPart x:Name="NerdDinnerFinder" Source="NerdDinnerFinder.dll" /><br>    </Deployment.Parts><br></Deployment><br>

The other file WMAppManifest.xml would appear to be the means of defining the resources and capabilities of the app from the point of view of the OS, i.e. as the place where it can get icons and images for the app:

<Deployment xmlns="http://schemas.microsoft.com/windowsphone/2009/deployment" AppPlatformVersion="7.0"><br>    <App xmlns="" ProductID="{45a8bc14-719e-4920-bce2-57e11d08e8bb}" Title="NerdDinnerFinder" RuntimeType="SilverLight" Version="1.0.0.0" Genre="NormalApp"    Author="" Description="" Publisher=""><br>        <IconPath IsRelative="true" IsResource="false">ApplicationIcon.png</IconPath><br>        <Capabilities><br>        </Capabilities><br>        <Tasks><br>            <DefaultTask Name="_default" PlaceHolderString="Default task"/><br>        </Tasks><br>        <Tokens><br>            <PrimaryToken TokenID="NerdDinnerFinderToken" TaskName="_default"><br>                <TemplateType5><br>                    <BackgroundImageURI IsRelative="true" IsResource="false">Background.png</BackgroundImageURI><br>                    <Count>0</Count><br>                    <Title>NerdDinnerFinder</Title><br>                </TemplateType5><br>            </PrimaryToken><br>        </Tokens><br>    </App><br></Deployment><br>

I thought maybe we could influence some of the attribute settings under App by modifying the project preferences as follows:

But recompiling using these settings showed no change in the WMAppManifest.xml file. My guess would be this is the file in which the Windows Phone Marketplace team will put all the metadata and code signing stuff when your app gets approved.

Anatomy of the Windows Phone 7 Series DLL

Now we have looked at the contents of the .xap file, lets crack open the NerdDinnerFinder.dll file and see if there is anything unexpected in there:

As we might expect, we have a Page class for the two pages, some viewmodel classes and the App class. We also have all the .xaml files packaged as resources. The TargetFramework assembly level attribute shows “Silverlight,Version=v4.0,Profile=WindowsPhone”. This is slightly strange, as the standard line in MIX was that WP7S is silverlight 3 with some extra bits, whereas this seems to indicate we have silverlight 4, but with some bits taken away…

Structure of the Windows Phone Application

Lets dig around the solution in visual studio now, starting with App.xaml.

App.xaml

This defines the application itself, and is configured in the project settings (see previous section) as the startup object for the solution. The file created by the visual studio template is quite large, as it is used to define a large number of xaml resources for use throughout the application, but starts like so:

<Application <br>    x:Class="NerdDinnerFinder.App"<br>    xmlns="http://schemas.microsoft.com/winfx/2006/xaml/presentation"     <br>    xmlns:x="http://schemas.microsoft.com/winfx/2006/xaml"<br>    xmlns:system="clr-namespace:System;assembly=mscorlib"<br>    xmlns:mpc="clr-namespace:Microsoft.Phone.Controls;assembly=Microsoft.Phone.Controls"<br>    xmlns:phoneNavigation="clr-namespace:Microsoft.Phone.Controls;assembly=Microsoft.Phone.Controls.Navigation"><br><br>    <!--RootFrame points to and loads the first page of your application--><br>    <Application.RootVisual><br>        <phoneNavigation:PhoneApplicationFrame x:Name="RootFrame" Source="/MainPage.xaml"/><br>    </Application.RootVisual><br><br>    <!-- Resources for following the Windows Phone design guidelines --><br>    <Application.Resources><br>        <!--************ THEME RESOURCES ************--><br>        <!-- Color Resources --><br>        <Color x:Key="PhoneBackgroundColor">#FF1F1F1F</Color><br>        <Color x:Key="PhoneContrastForegroundColor">Black</Color><br>...<br></Application>

Deconstructing this file, we can see there are two main purposes – firstly it defines the root visual, or “entry page” for the application as MainPage.xaml, secondly it defines resources for the rest of the application.

There is a codebehind file, App.xaml.cs, which currently is used to hook up an event handler for all unhandled exceptions.

MainPage.xaml

This is just a standard xaml page, derived from PhoneApplicationPage and defines a simple layout with headings and a list box with an ItemTemplate. The codebehind, MainPage.xaml.cs, defines a transition effect to occur when a list item is clicked, and in the completion handler calls NavigationService.Navigate to move to the detail page.

Summary

So far we have determined what we want to demonstrate with this application, installed the required development tools, created a basic application from the windows phone list application template, and taken a look around this application.

Next up, we will hook up an OData client within this application and bind this to the listbox.

Using DGML in Visual Studio 2010 to visualise a financial model

Having just installed the new RC of Visual Studio 2010, and prompted by this video by Chris Lovett and these blog posts by Cameron Skinner it prompted me to experiment with an idea I had a while ago – the ability to generate a diagram showing the calculations and the flow of values for a financial model.

In this experiment I will create a simplistic bond pricer in C#, create a logging mechanism for this model to output values at the various stages, and then implement a means to transform these values into a DGML model file which we can then visualise.

Create a logging mechanism

All we need is a means to generate an XML document containing the Inputs, Simple calculations, and iterated calculations (this is enough to satisfy the requirements of the simple bond pricer)

    public class XmlLogger : ICalcLogger<br>    {<br>        public XDocument LoggedValues { get; private set; }<br><br>        public XmlLogger()<br>        {<br>            LoggedValues = new XDocument();<br><br>            LoggedValues.Add(new XElement("Results",<br>                new XElement("Inputs"),<br>                new XElement("SingleCalcs"),<br>                new XElement("IteratedCalcs")));<br>        }<br><br>        public void Save(string filename)<br>        {<br>            File.WriteAllText(filename, LoggedValues.ToString());<br>        }<br><br>        public void LogInput(string name, object value)<br>        {<br>            LoggedValues.Element("Results").Element("Inputs").Add(<br>                new XElement("Input",<br>                    new XAttribute("name", name),<br>                    new XAttribute("category", "Inputs"),<br>                    new XAttribute("value", value)));<br>        }<br><br>        public void LogSingleCalc(string name, string category, string formula, object value)<br>        {<br>            LoggedValues.Element("Results").Element("SingleCalcs").Add(<br>                new XElement("SingleCalc",<br>                    new XAttribute("name", name),<br>                    new XAttribute("category", category),<br>                    new XAttribute("formula", formula),<br>                    new XAttribute("value", value)));<br>        }<br><br>        public void LogIteratedCalc(string name, string category, int iteration, string formula, object value)<br>        {<br>            LoggedValues.Element("Results").Element("IteratedCalcs").Add(<br>                new XElement("IteratedCalc",<br>                    new XAttribute("name", name),<br>                    new XAttribute("category", category),<br>                    new XAttribute("iteration", iteration),<br>                    new XAttribute("formula", formula),<br>                    new XAttribute("value", value)));<br>        }<br>    }

Create the Bond Pricer model

With the logging in place, we can now create an implementation of the bond pricer which makes use of this logging:

    // very basic clean price calculation based on http://en.wikipedia.org/wiki/Bond_pricing<br>    public class SimpleBondPricer<br>    {<br>        private double F;<br>        private double C;<br>        private double r;<br>        private int T;<br>        private int n;<br>        private ICalcLogger logger;<br><br>        public SimpleBondPricer(double F, double C, double r, int T, int n, ICalcLogger logger)<br>        {<br>            this.F = F;<br>            this.C = C;<br>            this.r = r;<br>            this.T = T;<br>            this.n = n;<br>            this.logger = logger;<br><br>            logger.LogInput("F", F);<br>            logger.LogInput("C", C);<br>            logger.LogInput("r", r);<br>            logger.LogInput("T", T);<br>            logger.LogInput("n", n);<br>        }<br><br>        public double CalculatePrice()<br>        {<br>            double coupons = CalculateCoupons(logger);<br>            double discountedFace = CalculatedDiscountedFaceValue(logger);<br><br>            double result = discountedFace + coupons;<br>            logger.LogSingleCalc("Pc", "Results", "Sm+DF", result);<br>            return result;<br>        }<br><br>        private double CalculatedDiscountedFaceValue(ICalcLogger logger)<br>        {<br>            double result = F / Math.Pow(1.0 + r, T);<br>            logger.LogSingleCalc("DF", "ParCalcs", "F / (1+r)^T", result);<br>            return result;<br>        }<br><br>        private double CalculateCoupons(ICalcLogger logger)<br>        {<br>            int m = n * T;<br>            logger.LogSingleCalc("m", "CouponCalcs", "n.T", m);<br><br>            double u = Math.Pow(1.0 + r, 1.0 / n);<br>            logger.LogSingleCalc("u", "CouponCalcs", "(1 + r) ^ (1 / n)", u);<br><br>            double result = 0.0;<br>            for (int t = 1; t <= m; t++)<br>            {<br>                double iterationResult = C / Math.Pow(u, t);<br>                logger.LogIteratedCalc("S", "CouponCalcs", t, "C/u^t", iterationResult);<br>                result += iterationResult;<br>            }<br><br>            logger.LogSingleCalc("Sm", "CouponCalcs", "Sum[t=1..m](C/u^t)", result);<br>            return result;<br>        }<br>    }

So we ensure all inputs are logged once we get them, and each stage in the calculation we log the formula used and the results obtained. So a simple invocation such as:

    var logger = new XmlLogger();<br><br>    var bp = new SimpleBondPricer(100.0, 0.08, 0.045, 3, 2, logger);<br>    double result = bp.CalculatePrice();<br><br>    logger.Save(@"C:\BondPricerCalcs.xml");

Will generate the following calculations log:

    <Results><br>      <Inputs><br>        <Input name="F" category="Inputs" value="100" /><br>        <Input name="C" category="Inputs" value="0.08" /><br>        <Input name="r" category="Inputs" value="0.045" /><br>        <Input name="T" category="Inputs" value="3" /><br>        <Input name="n" category="Inputs" value="2" /><br>      </Inputs><br>      <SingleCalcs><br>        <SingleCalc name="m" category="CouponCalcs" formula="n.T" value="6" /><br>        <SingleCalc name="u" category="CouponCalcs" formula="(1 + r) ^ (1 / n)" value="1.0222524150130437" /><br>        <SingleCalc name="Sm" category="CouponCalcs" formula="Sum[t=1..m](C/u^t)" value="0.444727984347155" /><br>        <SingleCalc name="DF" category="ParCalcs" formula="F / (1+r)^T" value="87.629660405490938" /><br>        <SingleCalc name="Pc" category="Results" formula="Sm+DF" value="88.074388389838091" /><br>      </SingleCalcs><br>      <IteratedCalcs><br>        <IteratedCalc name="S" category="CouponCalcs" iteration="1" formula="C/u^t" value="0.078258558087122954" /><br>        <IteratedCalc name="S" category="CouponCalcs" iteration="2" formula="C/u^t" value="0.076555023923444987" /><br>        <IteratedCalc name="S" category="CouponCalcs" iteration="3" formula="C/u^t" value="0.07488857233217508" /><br>        <IteratedCalc name="S" category="CouponCalcs" iteration="4" formula="C/u^t" value="0.0732583960989904" /><br>        <IteratedCalc name="S" category="CouponCalcs" iteration="5" formula="C/u^t" value="0.071663705581028789" /><br>        <IteratedCalc name="S" category="CouponCalcs" iteration="6" formula="C/u^t" value="0.070103728324392739" /><br>      </IteratedCalcs><br>    </Results>

Generating the DGML markup

The XML above contains all we need to create the nodes for our diagram. I considered using XSLT or hand crafting some C# to transform this into DGML, but then thought this is a great use for T4 templates – we just need to iterate over the elements in this XML document, and generate the corresponding DGML nodes.

In VS 2010 I add a new Text Template file to the solution and populate it as follows:

<#@ template language="C#" #><br><#@ output extension="dgml" #><br><#@ assembly name="System.Core" #><br><#@ assembly name="System.Xml" #><br><#@ assembly name="System.Xml.Linq" #><br><#@ import namespace="System.Linq" #><br><#@ import namespace="System.Xml.Linq" #><br><#<br>    var doc = XDocument.Load(@"C:\BondPricerCalcs.xml");<br>#><br><?xml version="1.0" encoding="utf-8"?><br><DirectedGraph xmlns="http://schemas.microsoft.com/vs/2009/dgml"><br>  <Nodes><br><#<br>    foreach (var element in doc.Element("Results").Element("Inputs").Descendants("Input"))<br>    {<br>        string name = element.Attribute("name").Value;<br>        string category = element.Attribute("category").Value;<br>        string value = element.Attribute("value").Value;<br>#><br>    <Node Id="<#= name #>" Category="<#= category #>" Description="<#= value #>" Label="<#= name #>" /><br><#<br>    }<br>#><br><#<br>    foreach (var element in doc.Element("Results").Element("SingleCalcs").Descendants("SingleCalc"))<br>    {<br>        string name = element.Attribute("name").Value;<br>        string category = element.Attribute("category").Value;<br>        string formula = element.Attribute("formula").Value;<br>        string value = element.Attribute("value").Value;<br>#><br>    <Node Id="<#= name #>" Category="<#= category #>" Description="<#= formula #> = <#= value #>" Label="<#= name #>" /><br><#<br>    }<br>#><br><#<br>    foreach (var element in doc.Element("Results").Element("IteratedCalcs").Descendants("IteratedCalc"))<br>    {<br>        string name = element.Attribute("name").Value;<br>        string category = element.Attribute("category").Value;<br>        string iteration = element.Attribute("iteration").Value;<br>        string formula = element.Attribute("formula").Value;<br>        string value = element.Attribute("value").Value;<br>#><br>    <Node Id="<#= name #><#= iteration #>" Category="<#= category #>" Description="<#= formula #>[<#= iteration #>] = <#= value #>" Label="<#= name #>[<#= iteration #>]" /><br><#<br>    }<br>#><br>    <Node Id="Coupons" Category="CouponCalcs" Group="Expanded" Label="Coupons" /><br>  </Nodes><br>  <Links><br>    <Link Source="DF" Target="Pc" /><br>    <Link Source="F" Target="DF" /><br>    <Link Source="m" Target="Sm" /><br>    <Link Source="n" Target="m" /><br>    <Link Source="n" Target="u" /><br>    <Link Source="r" Target="DF" /><br>    <Link Source="r" Target="u" /><br>    <Link Source="Sm" Target="Pc" /><br>    <Link Source="T" Target="DF" /><br>    <Link Source="T" Target="m" /><br>    <Link Source="Coupons" Target="Sm" Category="Contains" /><br><#<br>    var m = (from calc in doc.Element("Results").Element("SingleCalcs").Descendants("SingleCalc")<br>             where calc.Attribute("name").Value == "m"<br>             select int.Parse(calc.Attribute("value").Value)).First();<br>    for(int t = 1; t <= m; t++)<br>    {<br>#><br>    <Link Source="C" Target="S<#= t #>"/><br>    <Link Source="u" Target="S<#= t #>"/><br>    <Link Source="S<#= t #>" Target="Sm"/><br>    <Link Source="Coupons" Target="S<#= t #>" Category="Contains" /><br><#<br>    }<br>#><br>  </Links><br>  <Categories><br>    <Category Id="Contains" Label="Contains" CanBeDataDriven="False" CanLinkedNodesBeDataDriven="True" IncomingActionLabel="Contained By" IsContainment="True" OutgoingActionLabel="Contains" /><br>    <Category Id="Inputs" Label="Inputs" IsTag="True" /><br>    <Category Id="CouponCalcs" Label="Coupon Calcs" IsTag="True" /><br>    <Category Id="ParCalcs" Label="Par Calcs" IsTag="True" /><br>    <Category Id="Results" Label="Results" IsTag="True" /><br>  </Categories><br>  <Styles><br>    <Style TargetType="Node" GroupLabel="Coupon Calcs" ValueLabel="Has category"><br>      <Condition Expression="HasCategory('CouponCalcs')" /><br>      <Setter Property="Background" Value="#FFFFFF00" /><br>    </Style><br>    <Style TargetType="Node" GroupLabel="Par Calcs" ValueLabel="Has category"><br>      <Condition Expression="HasCategory('ParCalcs')" /><br>      <Setter Property="Background" Value="Green" /><br>    </Style><br>    <Style TargetType="Node" GroupLabel="Inputs" ValueLabel="Has category"><br>      <Condition Expression="HasCategory('Inputs')" /><br>      <Setter Property="Background" Value="White" /><br>    </Style><br>    <Style TargetType="Node" GroupLabel="Results" ValueLabel="Has category"><br>      <Condition Expression="HasCategory('Results')" /><br>      <Setter Property="Background" Value="Blue" /><br>    </Style><br>  </Styles><br></DirectedGraph>

So this basically iterates over the XML first to generate all the diagram nodes, then adds all the static links (the ones which don’t change no matter what the model inputs are), and finally the links for the individual coupon calcs. Whenever this file is saved, it will generate a code-behind file as per the output directive, i.e. with a .dgml extension. If you open up this file, we see the DGML source:

<?xml version="1.0" encoding="utf-8"?><br><DirectedGraph xmlns="http://schemas.microsoft.com/vs/2009/dgml"><br>  <Nodes><br>    <Node Id="C" Category="Inputs" Description="0.08" Label="C" /><br>    <Node Id="Coupons" Category="CouponCalcs" Group="Expanded" Label="Coupons" /><br>    <Node Id="DF" Category="ParCalcs" Description="F / (1+r)^T = 87.629660405490938" Label="DF" /><br>    <Node Id="F" Category="Inputs" Description="100" Label="F" /><br>    <Node Id="Pc" Category="Results" Description="Sm+DF = 88.074388389838091" Label="Pc" /><br>    <Node Id="S1" Category="CouponCalcs" Description="C/u^t[1] = 0.078258558087122954" Label="S[1]" /><br>    <Node Id="S2" Category="CouponCalcs" Description="C/u^t[2] = 0.076555023923444987" Label="S[2]" /><br>    <Node Id="S3" Category="CouponCalcs" Description="C/u^t[3] = 0.07488857233217508" Label="S[3]" /><br>    <Node Id="S4" Category="CouponCalcs" Description="C/u^t[4] = 0.0732583960989904" Label="S[4]" /><br>    <Node Id="S5" Category="CouponCalcs" Description="C/u^t[5] = 0.071663705581028789" Label="S[5]" /><br>    <Node Id="S6" Category="CouponCalcs" Description="C/u^t[6] = 0.070103728324392739" Label="S[6]" /><br>    <Node Id="Sm" Category="CouponCalcs" Description="Sum[t=1..m](C/u^t) = 0.444727984347155" Label="Sm" /><br>    <Node Id="T" Category="Inputs" Description="3" Label="T" /><br>    <Node Id="m" Category="CouponCalcs" Description="n.T = 6" Label="m" /><br>    <Node Id="n" Category="Inputs" Description="2" Label="n" /><br>    <Node Id="r" Category="Inputs" Description="0.045" Label="r" /><br>    <Node Id="u" Category="CouponCalcs" Description="(1 + r) ^ (1 / n) = 1.0222524150130437" Label="u" /><br>  </Nodes><br>  <Links><br>    <Link Source="C" Target="S1" /><br>    <Link Source="C" Target="S2" /><br>    <Link Source="C" Target="S3" /><br>    <Link Source="C" Target="S4" /><br>    <Link Source="C" Target="S5" /><br>    <Link Source="C" Target="S6" /><br>    <Link Source="Coupons" Target="S1" Category="Contains" /><br>    <Link Source="Coupons" Target="S2" Category="Contains" /><br>    <Link Source="Coupons" Target="S3" Category="Contains" /><br>    <Link Source="Coupons" Target="S4" Category="Contains" /><br>    <Link Source="Coupons" Target="S5" Category="Contains" /><br>    <Link Source="Coupons" Target="S6" Category="Contains" /><br>    <Link Source="Coupons" Target="Sm" Category="Contains" /><br>    <Link Source="DF" Target="Pc" /><br>    <Link Source="F" Target="DF" /><br>    <Link Source="S1" Target="Sm" /><br>    <Link Source="S2" Target="Sm" /><br>    <Link Source="S3" Target="Sm" /><br>    <Link Source="S4" Target="Sm" /><br>    <Link Source="S5" Target="Sm" /><br>    <Link Source="S6" Target="Sm" /><br>    <Link Source="Sm" Target="Pc" /><br>    <Link Source="T" Target="DF" /><br>    <Link Source="T" Target="m" /><br>    <Link Source="m" Target="Sm" /><br>    <Link Source="n" Target="m" /><br>    <Link Source="n" Target="u" /><br>    <Link Source="r" Target="DF" /><br>    <Link Source="r" Target="u" /><br>    <Link Source="u" Target="S1" /><br>    <Link Source="u" Target="S2" /><br>    <Link Source="u" Target="S3" /><br>    <Link Source="u" Target="S4" /><br>    <Link Source="u" Target="S5" /><br>    <Link Source="u" Target="S6" /><br>  </Links><br>  <Categories><br>    <Category Id="Contains" Label="Contains" CanBeDataDriven="False" CanLinkedNodesBeDataDriven="True" IncomingActionLabel="Contained By" IsContainment="True" OutgoingActionLabel="Contains" /><br>    <Category Id="CouponCalcs" Label="Coupon Calcs" IsTag="True" /><br>    <Category Id="Inputs" Label="Inputs" IsTag="True" /><br>    <Category Id="ParCalcs" Label="Par Calcs" IsTag="True" /><br>    <Category Id="Results" Label="Results" IsTag="True" /><br>  </Categories><br>  <Properties><br>    <Property Id="CanBeDataDriven" Label="CanBeDataDriven" Description="CanBeDataDriven" DataType="System.Boolean" /><br>    <Property Id="CanLinkedNodesBeDataDriven" Label="CanLinkedNodesBeDataDriven" Description="CanLinkedNodesBeDataDriven" DataType="System.Boolean" /><br>    <Property Id="Description" Label="Description" Description="Description" DataType="System.String" /><br>    <Property Id="Group" Label="Group" Description="Display the node as a group" DataType="Microsoft.VisualStudio.Progression.GraphModel.GroupStyle" /><br>    <Property Id="IncomingActionLabel" Label="IncomingActionLabel" Description="IncomingActionLabel" DataType="System.String" /><br>    <Property Id="IsContainment" DataType="System.Boolean" /><br>    <Property Id="IsTag" DataType="System.Boolean" /><br>    <Property Id="Label" Label="Label" Description="Displayable label of an Annotatable object" DataType="System.String" /><br>    <Property Id="OutgoingActionLabel" Label="OutgoingActionLabel" Description="OutgoingActionLabel" DataType="System.String" /><br>  </Properties><br>  <Styles><br>    <Style TargetType="Node" GroupLabel="Coupon Calcs" ValueLabel="Has category"><br>      <Condition Expression="HasCategory('CouponCalcs')" /><br>      <Setter Property="Background" Value="#FFFFFF00" /><br>    </Style><br>    <Style TargetType="Node" GroupLabel="Par Calcs" ValueLabel="Has category"><br>      <Condition Expression="HasCategory('ParCalcs')" /><br>      <Setter Property="Background" Value="Green" /><br>    </Style><br>    <Style TargetType="Node" GroupLabel="Inputs" ValueLabel="Has category"><br>      <Condition Expression="HasCategory('Inputs')" /><br>      <Setter Property="Background" Value="White" /><br>    </Style><br>    <Style TargetType="Node" GroupLabel="Results" ValueLabel="Has category"><br>      <Condition Expression="HasCategory('Results')" /><br>      <Setter Property="Background" Value="Blue" /><br>    </Style><br>  </Styles><br></DirectedGraph>

And we can also view the diagram. Note that we create a collapsible group for the iterated calculations, which could be hierarchical for very complicated models allowing you to visualise an entire set of calculations and drill down as required in order to investigate errors or inconsistencies.

Future Improvements

There is a spillover of model-specific logic in the T4 template. With a bit of thought, we could should be able to create XML loggers which hold all the model specific logic, and related XML format and then generate a T4 template which is model agnostic.

We perform the calculations and logging separately. Instead, we could encode all calculations we perform as expression trees, and walk these trees to not only calculate the values, but also perform the logging (including automatically generating the string representations of each formula). This is way beyond the scope of this article, however.