Tuesday, September 20, 2016

Prog F# Sneak Preview


It’s official! I’ve been given the opportunity to prsent a workshop at the upcoming Progressive F# Tutorials. This is a fantastic event and something which seems almost unique to F# as a language — I’ve certainly not heard of the like in the C# world!

It’s taking place on 5th-6th December at the excellent CodeNode facility of Skills Matter. As well as being a super-cool place, it has the added bonus of being just around the corner from my office.

To get you in the mood (early bird tickets are still available!) I thought I’d give you a sneak peek into the event by answering a few questions that the hosts have put to me:

I am excited to joining Prog F# where I will be sharing my thoughts on…

FinTech in F#!

This is an area that I work with every day at Redington, where we’re trying to make 100 million people financially secure, and I think it has the potential to improve people’s lives — if applied properly!

The problem in a nutshell?

Most of us aren’t saving enough for our future.

This isn’t something that’s going to go away - we’re living longer and many of us are underestimating how much money we need for a comfortable retirement.

How can we help solve this problem?

By harnessing the power of F# to deliver clear and easy-to-understand advice and recommendations that takes you on a journey from confused to confident.

Over the last couple of years, robo-advisors have emerged as a platform for automating this advice as one part of the Fintech revolution.

If you come along to my workshop, you’ll get to build a fully functioning web-based robo advisor that will tell you if you’re on track to hit your savings goals, and give you recommendations if you aren’t quite there yet.

The best thing about being part of the F# community is…

The sheer number of incredibly useful open-source projects that people dedicate their free time to. You’ll see them used in any F# talk or workshop, whoever the speaker, and I plan to be no exception!

Ones that spring to mind are Ionide, Paket, Fake and Suave. Each one solves a real problem that F~ developers have and hugely improved the experience of F# devs, new and old!

At Progressive F# Tutorials, I most look forward to learning about…

How F# can be used for Web development. I’ll admit to having used the language primarily for back-end work - domain modelling, business logic, financial calculations, etc.

What I’d love to get out of the upcoming tutorials tutorials is a bit more understanding of how to get F# playing nicely with the internet — I’m told it’s the future, after all.

My talk will be enjoyed by…

Anyone who wants to see the power and flexibility of F# as a language.

Ever wondered how to really model your domain as it is in real-life? I’ll show you how, using F#’s algebraic data types.

Still wrangling with csv files to get your data into your app and creating fiddly charts? F# can help by way of a type provider and a brilliant charting library.

Unsure how to get your content onto the web without using a big heavy framework? Enter Suave and WebSharper!

I think the most anticipated/exciting development for the F# community over the next 12 months will be…

The evolution of the community-driven projects that I mentioned previously, into the ‘dominant’ tool or framework in their area. I think they are tantalisingly close to replacing the out-of-the-box tools that you get form something like Visual Studio, and am looking forward to the day that they do so!


Wrap-up

I’m pretty excited about giving this workshop — I get to show off the power of F#, and use it to build something that I think could really help people!

Thursday, September 01, 2016

The United States of Monad


A couple of months ago I was chatting with approximately half of my readership about Monads, and more specifically this post which asked: Why do we have monads?

Two of the reasons I gave were exception handling and state. I have already touched on the former, and again refer you to Railway Oriented Programming for a brilliant explanation of how to handle exceptions in a purely functional manner.

What you’ll learn today

  • Why we need to handle state functionally in the first place
  • How to convert imperative for and while loops to functional ones that embed the local state
  • How this can be formalised using the State monad and F# computation expressions
  • How to extend this to keep track of a global state without resorting to a mutable variable

As ever, the code is on GitHub.


Handling state functionally

State is a funny old thing. It seems pretty harmless in small doses, but trying to control state globally and across threads and processes is a nightmare.

If we handle state using purely functional techniques we can control this — we will see how it is threaded through our computations rather than simply ambient, which allows us to make stronger statements about the concurrency and parallelism of our program.

Before we see that, let’s go back to basics and look at handling state in the smallest scope possible, a loop.


Keeping it in the loop

Let’s consider a very simple example. We have an action, say printing to the console, that we want to do a set number of times. Each time we do it, we want to also print how many times we’ve done it, i.e. the state of the computation. Keeping it even simpler, let’s fix the number of iterations:

let startVal = 1
let endVal = 10

We can achieve our goal in a number of ways, the first being a standard for loop. This doesn’t look like it’s impure, but we have a variable i below that will be mutated on each iteration of the loop body:

let forLoop act = 
    for i = startVal to endVal do
        act (i)

The first step towards a functional approach is to notice that a for loop is the same as a while loop that has a mutable integer variable. We thus rewrite:

let whileLoop act = 
    let mutable i = startVal
    while i <= endVal do
        act (i)
        i <- i + 1

We have seen how to eliminate these kind of variables before using an inner recursive function. In the method below we are threading the state through the computation as the second parameter of our aux function:

let recLoop act = 
    let rec aux i = 
        match i > endVal with
        | true -> ()
        | _ -> 
            act (i)
            aux (i + 1)
    aux startVal

We now have state being treated in a pure, functional method. No variables are being mutated,

Let’s run the code:

let action i = printf "%d " i

forLoop action
printf "%s" System.Environment.NewLine
whileLoop action
printf "%s" System.Environment.NewLine
recLoop action
printf "%s" System.Environment.NewLine

Thankfully, the output is exactly the same in each case!

What have we learnt?

We can handle state in a functional manner by recursive function calls that take the state as an input.


Monads, monads everywhere

What on earth does the above have to do with monads?

Let’s take our example a step further and say that we want to do something really complicated, like summing a list of integers. In this instance, all of the ‘temporary’ state (i.e. the ‘sum so far’) is contained entirely within the loop construct, totally hidden from the consumer of the function. We can do this once more using for, while or rec:

let forSum list = 
    let mutable sum = 0
    for elt in list do
        sum <- sum + elt
    sum

let whileSum list = 
    let mutable sum = 0
    let mutable i = 0
    while i < List.length list do
        sum <- sum + list.[i]
        i <- i + 1
    sum

let recSum list = 
    let rec aux remainderOfList sumSoFar = 
        match remainderOfList with
        | [] -> sumSoFar
        | head :: tail -> aux tail (sumSoFar + head)
    aux list 0

The key thing to note above is that in the recursive example, nothing is marked as mutable. This means we’ve now seen a technique that helps us:

  1. Run loops without introducing a mutable variable
  2. Keep track of temporary state whilst keeping functional purity

This quickly breaks down when doing anything non-local — imagine how you might update a global variable from inside a pure function that itself returns a value. To do this, we combine what we’ve seen before and can write the function such that it takes in the global state as an input, and returns the (updated) global state as well as whatever other value the function returns:

let sumListAndUpdateState list state = 
    (recSum list, state)

The above shows that you can update global state fairly simply by returning a tuple of the function result plus updated state.

How do we generalise this so that we don’t have to explicitly pass around the state on every function call? The answer is the state monad. There are many explanations of it out there, but I will walk you through the F# one myself. It all looks pretty complicated, but I’m hoping you get the gist rather than get bogged down by the details — we’re creating a way to thread state silently through any computation.

Being precise, the state monad is based on a type — one that encodes a function taking a state of type 'a and returns a state-result tuple where the result is of type 'b':

type StateMonad<'a,'b> = 'a -> ('a * 'b)

To be classed as a monad, we need to be able to do some stuff with it. First, we need to be able to create an instance of it from an initial state:

let returnS a = (fun s -> a, s)

We also need to be able to combine an instance of it with the result of a previous computation:

let (>>=) x f = 
    (fun s0 -> 
    let a, s = x s0
    f a s)

Finally, we want to combine two instances of it:

let (>=>) m1 m2 = 
    (fun s0 ->
    let _, s = m1 s0
    m2 s)            

Done as an F# computation expression, this looks like:

type StateBuilder() = 
    member m.Bind(x, f) = x >>= f
    member m.Return a = returnS a
    member m.ReturnFrom(x) = x

let state = new StateBuilder()

We can then define some helper functions that we can use in our state computation expressions: the first gets the current state; the second sets it; the third executes our computation and returns the final state.

let getState = (fun s -> s, s)
let setState s = (fun _ -> (), s)
let Execute m s = m s |> snd

Now that we have the concept of threading state through a function encoded in a generic type, let’s put it to use!

A contrived example is our previous one summing a list — it’s overkill for a monad as it only ever used local state, but here goes:

let stateSum list = 
    let rec aux t = 
        state { 
            match t with
            | head :: tail -> 
                let! s = getState
                do! setState (s + head)
                return! aux tail
            | [] -> return ()
        }
    Execute (aux list) 0

Let’s focus on the aux computation expression. The most obvious thing is that the state isn’t an input! This is because aux actually returns a function — one that takes in the initial state and returns the final state plus the function return value (which in this case is unit but could be anything)

Behind the scenes it is going to call Bind to combine the recursive calls to aux into one big computation, each stage of which will take the sum of the list so far plus the tail of the list as inputs. When we have an empty list, we return the state plus the function ‘return value’. Here, the state is the value we want so we can just return unit.

Of course, passing around an integer as a state isn’t necessary. We can write a generic fold function using our state computation expression as follows:

let fold aggregator initialValue list = 
    let rec aux t = 
        state { 
            match t with
            | head :: tail -> 
                let! s = getState
                do! setState (aggregator s head)
                return! aux tail
            | [] -> return ()
        }
    Execute (aux list) initialValue

Now we are passing in everything we need to control the aggregation, and we have left with a function that takes in an initial state, a list, and a way to update the state from the list, returning the final state. Complicated, but beautiful to reason about.

Next, let’s see how we can handle global state.


Globalisation

So far, we have shown a number of ways in which local state can be handled. This is a fundamentally different problem (and easier) than that of global state.

Let’s use the example of a function that will only run an action five times. On the sixth run it will instead perform a failure action.

Here’s how it looks normally: we create a mutable variable and read that from inside the (impure, yuck) function:

let mutable globalCounter = 0

let canOnlyRunFiveTimes passAction failAction = 
    match globalCounter < 5 with
    | true ->            
        passAction globalCounter
        globalCounter <- globalCounter + 1
    | false -> 
        failAction globalCounter
        globalCounter <- -1

Using our state monad, we can do exactly the same thing but we have controlled the impurity:

let monadicCounter = 0

let canOnlyRunFiveTimesWithStateMonad passAction failAction = 
        state { 
            let! s = getState
            match s < 5 with
            | true -> 
                passAction s
                do! setState (s + 1)
            | false -> 
               failAction s
               do! setState (- 1)
        }

The best way to see this in action is by running some tests.

First, let’s run our function five times using the version that reads from a global mutable variable. It should return 5! Then run it a sixth time; it should return -1 to signify an error.

[<Test>]
let ``Global mutable state``() = 
  for _ in 1 .. 5 do canOnlyRunFiveTimes (printf "Run %d \r\n") (printf "Not run %d \r\n")
  globalCounter =! 5
  canOnlyRunFiveTimes (printf "Run %d \r\n") (printf "Not run %d \r\n")
  globalCounter =! -1

Here’s how it looks using global monadic state (no mutable keyword, whoop!!). We use our >=> operator from before that glues together two monad thingies to run the computation more than once:

[<Test>]
let ``Global monadic state``() =
  let monadicCounter = 0
  let m = canOnlyRunFiveTimesWithStateMonad (printf "Run %d \r\n") (printf "Not run %d \r\n") 
  let composedFiveTimes =  m >=> m >=> m >=> m >=> m
  let composedSixTimes =  composedFiveTimes >=> m
  Execute composedFiveTimes monadicCounter =! 5
  Execute composedSixTimes monadicCounter =! -1

The results are exactly the same!


Recap

Let’s look at what I promised you:

What you’ll learn today

  • Why we need to handle state functionally in the first place
  • How to convert imperative for and while loops to functional ones that embed the local state
  • How this can be formalised using the State monad and F# computation expressions
  • How to extend this to keep track of a global state without resorting to a mutable variable

I hope that you feel satisfied that you know these things now — if you don’t, let me know which bits are a struggle and how I can improve my explanation!

Sunday, June 19, 2016

Functional Creational Patterns


Much is made in the object-oriented world of applying Design Patterns. The majority of the time, the pattern in question is one from the canonical ‘Gang of Four’ book of the same name. I feel that I use these patterns in the manner intended — reusing a solution that has worked in the past to solve a new problem.

When learning a new paradigm, in my case functional programming with F#, I naturally had no previous solutions to fall back on, and thus no set of design patterns stored in my brain, patiently waiting their turn. This got me thinking about how well-known C# patterns can be applied to F# code, so I did a bit of searching and came up with a related talk by Scott Wlaschin. Whilst helpful, it was more about taking yourself out of an OO mindset as opposed to trying to reimagine existing patterns. I was still curious to answer this, which brought me to the question I’m about to answer in this post:

What do C# design patterns look like in F#?

I will do this in three installments to mirror those in the book: first Creational Patterns, then Structural Patterns and finally Behavioural Patterns.

The code can be found on GitHub.


Creational Patterns


A creational pattern abstracts the process of instantiating objects, decoupling a system from how its objects are represented and created.

There are five such patterns listed in the Gang of Four book. For each, I will:

  • briefly state the goal of the pattern (that is, what problem it is trying to solve);
  • show some minimal C# code using the pattern;
  • present some F# code solving the same problem; and
  • discuss the differences.

Quick links:


Abstract Factory


The goal:

This allows us to create families of related objects without specifying their concrete classes.

C# code:

using System;
namespace DesignPatterns
{
    public class UseAbstractFactoryPattern
    {
        public void Run ()
        {
            var printer = new ComponentInformationPrinter (new Type1Factory ());
            printer.PrintInformation ();
        }
    }

    public class ComponentInformationPrinter
    {
        public ComponentInformationPrinter (ComponentFactory componentFactory)
        {
            this.ComponentFactory = componentFactory;
        }

        private ComponentFactory ComponentFactory { get; }

        public void PrintInformation ()
        {
            var component = this.ComponentFactory.CreateComponent ();
            Console.WriteLine (component.Type ());
            Console.WriteLine (component.Category ());
        }
    }

    public abstract class ComponentFactory
    {
        public abstract Component CreateComponent ();
    }

    public abstract class Component
    {
        public abstract int Type ();
        public abstract string Category ();
    }

    public class Type1Component : Component
    {
        public override int Type () => 1;
        public override string Category () => "Category 1";
    }

    public class Type1Factory : ComponentFactory
    {
        public override Component CreateComponent () => new Type1Component ();
    }

    public class Type2Component : Component
    {
        public override int Type () => 2;
        public override string Category () => "Category 2";
    }

    public class Type2Factory : ComponentFactory
    {
        public override Component CreateComponent () => new Type2Component ();
    }
}

F# code:

module AbstractFactory

type Component = 
    | Type1Component
    | Type2Component

type ComponentFactory = 
    { Component : Component }

let getComponent (componentFactory : ComponentFactory) = componentFactory.Component

let getType = 
    function 
    | Type1Component -> 1
    | Type2Component -> 2

let getCategory = 
    function 
    | Type1Component -> "Category 1"
    | Type2Component -> "Category 2"

let printInformation componentFactory = 
    let componentInst = getComponent componentFactory
    printfn "%d" (getType componentInst)
    printfn "%s" (getCategory componentInst)

do printInformation { Component = Type1Component }

Discussion:

The code is more easily read if we distill it into the essence of what it is trying to achieve:

We want to specify the type of component we want, and in return be given a way to print information about the component.

In the C# version, this is done using inheritance and constructor injection: we create a ComponentInformationPrinter that accepts a ComponentFactory in its constructor, and then delegates to that factory to create the components which it then queries for their information. In turn, the components inherit from an abstract base class and provide their own implementation of the information-giving functions.

Whilst I could have made the F# code very similar (it does have classes, after all), the point of this post is to figure out what such patterns look like in a functional paradigm. Instead, I decided to use pattern matching functions to handle different types of components, which are defined using a discrimiated union.

This has the effect that, were we to add another type of component, we would need to update all of these functions to handle that particular case (or provide a degenerate catch-all case in the match function). Note that nothing on the factory side of things need be changed — in fact, the factory is simple a record type that wraps the underlying Component.

This is in stark contrast to the C# approach where we instead define a new class that inherits from Component, implement any required abstract functions, and then write a new factory class that inherits from ComponentFactory in order to get the new type back.

So which is better?

I think it really depends on the use case. The functional approach has the advantage that the factory definition is almost implicit, and we can define new factories on-the-fly. However, it has the disadvantage that we need to modify existing code to add a new type of Component.

This is unsuitable for (e.g.) distributing to third parties as a library, who will not then have the capability to extend the functionality. One way around this would be to define an interface with two methods, GetType and GetCategory, which clients could implement themsleves using object expressions.

On the whole, the patterns don’t look too dissimilar in a functional language, but I’m not sure the F# implementation really solves a real-world requirement in the same way that it does in C# — we could dispense with the factory altogether in F# and it wouldn’t really change anything from a caller’s perspective. I think the C# version is thus more of a ‘complete’ pattern.


Builder


The goal:

To make constructing a complex object independent of its representation, meaning that we can construct different representations via the same process.

C# code:

using System;
namespace DesignPatterns
{
    public class UseBuilderPattern
    {
        public void Run ()
        {
            var director = new ItemDirector ();

            var builder = new YellowItemBuilder ();

            director.Construct (builder);

            var builtItem = director.Construct (builder);

            builtItem.ShowParts ();
        }
    }

    public class ItemDirector
    {
        public Item Construct (ItemBuilder builder)
        {
            builder.BuildFirstPart ();
            builder.BuildSecondPart ();
            return builder.GetItem ();
        }
    }

    public abstract class ItemBuilder
    {
        public abstract void BuildFirstPart ();
        public abstract void BuildSecondPart ();
        public abstract Item GetItem ();
    }

    public class YellowItemBuilder : ItemBuilder
    {
        private readonly Item item = new Item ();

        public override void BuildFirstPart ()
        {
            item.FirstPartName = "YellowFirstPart";
        }

        public override void BuildSecondPart ()
        {
            item.SecondPartName = "YellowSecondPart";
        }

        public override Item GetItem () => item;
    }

    public class GreenItemBuilder : ItemBuilder
    {
        private readonly Item item = new Item ();

        public override void BuildFirstPart ()
        {
            item.FirstPartName = "GreenFirstPart";
        }

        public override void BuildSecondPart ()
        {
            item.SecondPartName = "GreenSecondPart";
        }

        public override Item GetItem () => item;
    }

    public class Item
    {
        public string FirstPartName;
        public string SecondPartName;

        public void ShowParts () => Console.WriteLine ($"{FirstPartName}, {SecondPartName}.");
    }
}

F# code:

module Builder

type Item = {mutable FirstPart : string; mutable SecondPart : string} 
    with member this.ShowParts() = sprintf "%s, %s." this.FirstPart this.SecondPart

type ItemBuilder =
    abstract member BuildFirstPart : unit->unit
    abstract member BuildSecondPart : unit->unit
    abstract member GetItem : unit -> Item
    abstract member item : Item

let yellowItemBuilder =  { new ItemBuilder with
      member this.item = {FirstPart = ""; SecondPart = ""}
      member this.BuildFirstPart() = this.item.FirstPart <- "YellowFirstPart"
      member this.BuildSecondPart() = this.item.FirstPart <- "YellowSecondPart"  
      member this.GetItem() = this.item }

let construct(builder:ItemBuilder) =
    builder.BuildFirstPart()
    builder.BuildSecondPart()
    builder.GetItem()

let run = 
    let item = construct yellowItemBuilder
    item.ShowParts()

Discussion:

The F# code took me an unreasonable amount of time to write, with lots of failed attempts to ‘make it more functional’ along the way. Diving into the literature, one suggested way to implement the Builder pattern in F# is to pass in a list of creation/processing functions to the director.

However, to me this is at odds with one of the main points of the pattern, that the director gets to choose the ordering of steps. If it takes a list of functions in, then the caller gets to choose the order.

Overall, I struggled to see how to solve this particular problem in a functional way. After all, the Builder pattern relies fundamentally on mutating things, which doesn’t sit nicely in the functional world.


Factory Method


The goal:

To allow subclasses to decide what type of class to instantiate.

This is a similar but subtly distinct goal from that of the Abstract Factory pattern above — to see the precise differences I am reusing the code from that example and showing only those sections that have changed.

C# code:

public class UseFactoryMethod
{
    public void Run ()
    {
        var printer = new ComponentInformationPrinter ();
        printer.PrintInformation ();
    }
}

public class ComponentInformationPrinter
{
    public virtual Component CreateComponent () =>  null;
    public void PrintInformation ()
    {
        var component = CreateComponent ();
        Console.WriteLine (component.Type ());
        Console.WriteLine (component.Category ());
    }
}

public class Type1Printer : ComponentInformationPrinter
{
    public override Component CreateComponent () => new Type1Component ();
}

public class Type2Printer : ComponentInformationPrinter
{
    public override Component CreateComponent () => new Type2Component ();
}

F# code:

let printInformation createComponent = 
    let componentInst = createComponent()
    printfn "%d" (getType componentInst)
    printfn "%s" (getCategory componentInst)

do printInformation (fun () -> Type1Component)

Discussion:

It should be clear from the code that this is really a subtle mutation of the Abstract Factory case which essentially gets rid of the factory class and moves the ‘hook’ into the ComponentInformationPrinter itself (i.e. to CreateComponent).

As such, the conclusions are much the same too — the patterns do broadly the same thing in both C# and F#.


Prototype

The goal:

To be able to create new objects by copying a prototypical instance.

C# code:

using System;
namespace DesignPatterns.Prototype
{
    public class UsePrototypes
    {
        public void Run ()
        {
            Component prototype = new Type1Component();
            var printer = new ComponentInformationPrinter (prototype);
            printer.PrintInformation ();
        }
    }

    public class ComponentInformationPrinter
    {
        public ComponentInformationPrinter (Component prototype)
        {
            this.prototype = prototype;
        }

        private Component prototype { get; }

        public void PrintInformation ()
        {
            var component = this.prototype.Clone ();
            Console.WriteLine (component.Type ());
            Console.WriteLine (component.Category ());
        }
    }

    public abstract class Component
    {
        public abstract int Type ();
        public abstract string Category ();
        public abstract Component Clone ();
    }

    public class Type1Component : Component
    {
        public override int Type () => 1;
        public override string Category () => "Category 1";
        public override Component Clone () => new Type1Component ();
    }

    public class Type2Component : Component
    {
        public override int Type () => 2;
        public override string Category () => "Category 2";
        public override Component Clone () => new Type1Component ();
    }
}

F# code:

let printInformation createComponent = 
    let componentInst = createComponent()
    printfn "%d" (getType componentInst)
    printfn "%s" (getCategory componentInst)

do printInformation (fun () -> Type1Component)

Discussion:

We can actually implement this pattern as another variation on the Abstract Factory pattern, this time injecting any required prototypes into the constructor of ComponentInformationPrinter and augmenting the Component class with a Clone() method.

In more complex examples of classes with data as well as behaviour, Clone() would have to decide exactly how much information to copy over (deep vs. shallow etc.), but here we simply have some baked-in behaviour that will transfer over.

The eagle-eyed amongst you will have noticed that the F# code is identical to that used for the Factory Method pattern. This is because the createComponent function was not only a factory method but also a prototype — this is because we were modelling Component as a discriminated union and so whatever we created was an immutable instance of that union.


Singleton


The goal:

Ensure that only one instance of a particular class can exist.

C# code:

public sealed class Singleton
{
    private static readonly Singleton instance = new Singleton ();

    static Singleton (){ }

    private Singleton () { }

    public static Singleton Instance => instance;
}

F# code:

type Singleton private() =
    static let instance = lazy(Singleton())
    static member Instance with get() = instance

Discussion:

The C# version looks deceptively simple. However, there are so many other versions of trying the same thing that run into problems with thread-safety, double locks, etc. that the pattern becomes slightly dangerous to use, especially for the less experienced developer.

I find it unlikely that someone who hasn’t written lots of singletons before will remember that they require static constructor so that the CLR marks the class as beforeFieldInit, and that deadlocking and performance are real possiblities, so to me this pattern doesn’t look ideal in C#.

On the other hand, the F# code is supposed to be less idiomatic, but actually looks better in my eyes thanks to static let bindings. It’s shorter and much clearer — we have a ‘thing’ (instance) and a way to get the one version of it that get ever exist, and that’s it!

Overall, this very common pattern is short & sweet in F#.


Conclusion & Next Time


Object creation looks quite different in C# and F#, and this flows through to the use of creational design patterns. As F# is an impure functional language, it has often felt like I have been using the less idiomatic parts of the language to write these object-oriented constructs. I suppose this is reassuring in a way — after all, the patterns were designed with OO in mind!

Next time we will look at Structural Patterns, and I expect there to be much bigger differences.

Monday, May 30, 2016

What's in a Monad?


Over the last few months I’ve progressed from the basics of functional programming to writing real-life, production code in F#. Inevitably, the concept of monads has come up.

Trying to learn what these slippery things are has been tough. The tutorials out there range from a lovely pictorial representation of Haskell monads to an example-driven series showing how common C# types are in fact monads to focusing on the actual functions that monads have in F#.

It’s fair to say that no single article or ever series of posts made me sit up and think ‘ah, so that’s what a monad is!’, which seems to tally with other people’s experience. For me, what made things click was asking the right question:

Why do we have monads?


Back to the start


It sounds a little strange when you put it like this, but so much of what I initially read on the topic focused on more esoteric questions that, to me, didn’t get to the crux of the matter, things like:

  • What is a monad?
  • What are the monad laws?
  • What does [insert monad name here] look like in Haskell/F#/…

I wanted to know why. Something must have driven computer scientists to look at category theory and think ‘maybe these will help us write programs!’

To understand this reasoning, I went back to the start. This meant reading the original paper that introduced monads back in 1996.

If this sounds scary to you, I don’t blame you, but bear with me. The paper is so nicely written and well explained that it made a huge difference to my understanding, and finally got my brain to connect the dots.

It did this by starting with a problem, and ending with the solution. So when I sat down to write my first production F# code, and I immediately came across a very similar problem, I already knew what the answer was.

In this post, I’m going to walk you through not only how I used monads to solve a real-world programming problem, but also say why they are such a good fit for the solution technique

This is going to be in three sections:

  • What is the problem we want to solve
  • How to we normally solve it in an object-oriented or imperative fashion
  • How can monads help us solve it more functionally?

A Common Problem


I write financial applications, and wanted a way for someone to select some asset data in Excel and send it to a central database. In more detail, this meant:

  • getting the input from a user through an ExcelDNA function;
  • validating that the input was correctly formed;
  • checking the exsiting database for similar records;
  • checking that links to other applications were valid; and
  • posting the data to the database

I realised quickly that this looked pretty similar to an example on Scott Wlaschin’s site, in which he uses the Either Monad to do something pretty similar, using the concept of a railway to explain things.

First though, I’ll outline how we would typically solve this in an imperative fashion, using C# as an example.


The Imperative Approach


In C#, this kind of thing might typically be done like this:

    [ExcelFunction (IsMacroType = true)]
    public static object StoreAssetData ([ExcelArgument] object [,] inputAllocation)
    {
        bool isValid = ValidateInput (inputAllocation);

        if (!isValid) 
        {
            return ExcelError.ExcelErrorValue;
        }

        bool similarDataAlreadyExists;
        try 
        {
            similarDataAlreadyExists = CheckExistingDatabase (inputAllocation);
        } 
        catch 
        {
            return ExcelError.ExcelErrorValue;
        }


        if(similarDataAlreadyExists) 
        {
            return ExcelError.ExcelErrorValue
        }

        bool linksToOtherAppsAreValid;
        try 
        {
            linksToOtherAppsAreValid = CheckOtherServices (inputAllocation);
        } 
        catch 
        {
            return ExcelError.ExcelErrorValue;
        }

        if (!linksToOtherAppsAreValid) 
        {
            return ExcelError.ExcelErrorValue;
        }

        try
        { 
            PostDataToDatabase(inputAllocation);
        } 
        catch
        {
            return ExcelError.ExcelErrorValue;
        }

        return "Done!";
    }

To me, there are a couple of problematic areas here. First, the control flow is hard to follow, and we keep getting forced to return early from the method if one bit fails. Second, operations that might throw exceptions need to be wrapped in fairly generic try-catch blocks, with the result of those operations defined outside of the block to be accessible elsewhere. Third, your focus is lost amongst the outline of the curly braces and you can’t easily figure out what the method wants to do.

Specifics aside, the imperative style looks at the core operations as then rather than and. That is, we are saying ‘validate this, then check that, then do this’, which has the problem that we need to check what state we’re in after each operation.

From a logical standpoint, we want to be able to say ‘validate and check and…’, and once it’s all done, tell me if it’s worked or not.

To do this, we need composition.


How Do Monads Help?


As scary as they sound, monads are exactly about this kind of things — composition, chaining, pipelining, and all these good functional things.

To help with our problem we need to be able to do a couple of very specific things:

  • Parallel composition: in this example we’ve got an array of entries to validate. Ideally we want to check every column of every row and tell the user about all of their mistakes, not just the first one.
  • Sequential composition: here we’ve got several steps that check for inconsistencies with existing data. However, if the data input to the function is malformed then there’s no point in doing this so we want some way of ‘skipping’ certain steps if previous ones failed (without exiting early from the routine and proliferating our curlies)
  • Result extraction: we want to get right to the end of the method and be able to say ‘this is the result’. Moreover if it’s not good news, we want to have as much information to give to the user about what went wrong as we can.

Fortunately, it turns out that we can do all of this with monads.


Briefly Introducing Result


type Result<'TSuccess, 'TFailure> = 
    | Success of 'TSuccess
    | Failure of 'TFailure

Here’s the type that we will be using to ease all of our pains. The idea is simple: the result of doing something is either Success or Failure, and in each case we include some data — the success case carries the input data that we want to feed to the next operation, and the failure case carries error messages.

This is beautiful in its simplicity and actually gives us everything we wanted. We have a way to compose operations that are successful by passing whatever we want in the success case, and a way to signal prior failure by passing through error messages in our failure wrapper

All we need to do now is see exactly how this composition works.


Parallel Composition: apply


let plusResult addSuccess addFailure result1 result2 = 
    match result1, result2 with
    | Success x1, Success x2 -> Success(addSuccess x1 x2)
    | Failure y1, Success _ -> Failure y1
    | Success _, Failure y2 -> Failure y2
    | Failure y1, Failure y2 -> Failure(addFailure y1 y2)

let apply f result = plusResult id (@) f result

let (<*>) = apply

Composing things in parallel is done with apply. In English, we take the results of two things (result1 and result2, each of which will either be Success or Failure), and say what to do in each of the possible cases:

  • If we’ve got two successes, return whatever was in the first case using the identity function id.
  • If we’ve got one failure and one success, return the Failure along with its error data.
  • If we’ve got two failures, return a new Failure with the error messages from each concatenated using infix list concatenation (@).

The infix version <*> is handy for neatening up the syntax, so we can write f1 <*> f2 <*> f3 rather than apply f1 (apply f2 f3).


Sequential Composition: bind


let either successFunc failureFunc = 
    function 
    | Success x -> successFunc x
    | Failure y -> failureFunc y

let bind f = either f Failure

let (>>=) x f = bind f x

This is even easier: we are passing in something to a function, if the thing is Success then apply the function to do data within, if it’s Failure then return the existing error messages.


Result Extraction: either


Getting the result out at the end of our computation is simply a more general case of sequencing things together — we do what we did for bind but allow the user to pass in whatever success or failure functions they want.

This has other benefits, for example testing — let’s say that in production we want a popup displaying either the error message or a happy success one. When we test, we’ve already abstracted the nasty UI/popup concerns and can inject our own tests implementations.


Putting It Into Practice


It looks like we’ve got the pieces that we need — and I haven’t even had to mention the monad laws! It’s deceptively simple stuff once you boil it down to exactly why you need each individual part of a monad.

And so to an actual solution. This is how we read our raw input rows contianing data:

let getRows (rows : obj [,]) = 
    seq { 
        for i in 0..(rows.GetLength(0) - 1) do
            let asset = readRow rows.[i, *]
            match asset with
            | Success x -> yield Success x
            | Failure failureMessages -> 
                yield Failure(sprintf "Row %d has problems: " i + String.concat "; " failureMessages)
    }

For each row, we read it. If the data is good, we yield it. If it’s not, we aggregate all the failure messages that we got back from reading it and yield a new one with some more contextual information.

Here’s how we read a single row:

let readRow (row : obj []) = 
        let createAsset displayName portfolioName marketValue collateral Fund Strategy = 
        { DisplayName = displayName
          PortfolioName = portfolioName
          MarketValue = marketValue
          CollateralClassification = collateral
          FundName = Fund
          StrategyName = Strategy }
    Success createAsset 
    <*> getString [ "DisplayName was missing or empty" ] row.[DisplayNameColumn] 
    <*> getStringOption row.[PortfolioNameColumn] 
    <*> getDouble [ (sprintf "MarketValue (%O) was not a valid number" row.[MarketValueColumn]) ]  row.[MarketValueColumn] 
    <*> getStringOption row.[CollateralColumn] 
    <*> getStringOption row.[FundColumn]
    <*> getStringOption row.[StrategyColumn]

We use the infix version of apply to read each column in turn and aggregate any problems we may have together. The helper functions getString, getStringOption and getDouble do pretty much what you would expect — they take an individual element of the input array and if they are of the desired type return Success, otherwise they return Failure with the injected error message.

We combine these with our result creation using bind:

let readAssetData inputAssetData = 
inputAssetData.InputAssets
|> getRows
|> foldResults
>>= createAssetData

where the createAssetData function is just a factory method to format the result, and foldResults simply combines the sequences yielded by getRows into one.

To spice things up a little, extracting the result can be done in C# by calling into the either function (in F#) we saw earlier:

public static class ResultExtensions
{
    internal static TResult Result<TSuccess, TFailure, TResult>(
        this Result<TSuccess, TFailure> twoTrackInput,
        Func<TSuccess, TResult> successFunc,
        Func<TFailure, TResult> failureFunc)
    {
        var sucessConverter = new Converter<TSuccess, TResult>(successFunc);
        var failureConverter = new Converter<TFailure, TResult>(failureFunc);

        var onSuccess = FSharpFunc<TSuccess, TResult>.FromConverter(sucessConverter);
        var onFailure = FSharpFunc<TFailure, TResult>.FromConverter(failureConverter);

        var result = either(onSuccess, onFailure, twoTrackInput);

        return result;
    }
}

This is a little verbose but shows how the language interop works, and means that we can use higher-order fucntions in C# (yay!) to do things like logging and error handling.

Adding logging

Let’s say we want to add logging to our application. We could use something like aspect-oriented programming and bring in loads of heavyweight third-party frameworks, or we could use monads:

    public static readonly Func<string, object> LogFailure = errorMessage =>
    {
        Logger.Log(errorMessage);
        return ExcelError.ExcelErrorValue;
    };

This function is passed into Result as the failureFunc parameter, and magically logs all of our failure messages!


Wrapping Up


In this post we’ve seen how a common imperative solution to a standard business problem can be transformed into something much neater and more scalable using some functional programming concepts.

The fact that these concepts have their roots in semi-obscure mathematical theory should not put you off using them — to see this, begin with the why.

Ask yourself why monads are useful, and with a bit of reading you will figure it out. Then next time you see a problem like this one, you’ll know exactly what to do.

Sunday, May 22, 2016

SOLID - F# vs. C#


Do you want to write code that’s more testable, maintainable, extensible? Of course you do!

However much you think you already code in such a fashion, how many of you have worked on a shared codebase where:

  • a) there are so many thousands of classes, layers of indirection or abstraction that you just don’t know what does what?
  • b) a crisp, clean piece of architecture that you originally constructed has been slowly mangled by less experienced team members?
  • c) everything important goes through one massive ‘God class’ and you just know that what a change needs making, that class is the one to look at first?

I’m going to guess that most of you would put your hand up.

What if I told you there was a way to stop any of these things happening in your codebases? The traditional answer might be SOLID. Mine is functions. By the end of this post, I hope to have convinced you!


Background

Last week, I watched Mark Seemann’s excellent Pluralsight course on Encapsulation and SOLID.

It in, he talks about there being some duality between applying Uncle Bob’s SOLID principles of object-oreitned design, and using functional programming. He, and others, have also blogged in similar veins:

http://blog.ploeh.dk/2014/03/10/solid-the-next-step-is-functional/
http://gorodinski.com/blog/2013/09/18/oop-patterns-from-a-functional-perspective/
https://neildanson.wordpress.com/2014/03/04/it-just-works/

These posts have been pretty good in giving some idea as to why the two concepts are similar, but I want to approach the issue from another angle: learning.


The Woes of the Junior Developer

As someone that’s recently had to learn object-oriented programming (self-directed, from scratch), I can safely say I haven’t seen a ‘beginners’ guide to SOLID that has any chance of teaching an inexperienced developer how to write code that adheres to these principles.

It’s hard enough trying to write code in an existing codebase that matches whatever million-tiered architecture the original authors came up with, and to learn the right time to create an abstraction, how to use polymorphism effectively, ensure you are encapsulating things properly, etc.

Then, someone tells you that objects in a program should be replaceable with instances of their subtypes without altering the correctness of that program, and you think that’s all well and good, but what on earth does that mean in terms of real code?

The same applies in less or greater measure to the remaining four principles — they clearly work and result in maintainable, flexible, testable code, but when you’re starting down the barrel of a couple of million lines of someone else’s handiwork, it’s nigh-on impossible to figure out how to ‘solidify’ what you’re looking at.

On the other hand, I said before that there is a duality between SOLID and functional programming. So how easy is it to teach the relevant concepts in a functional language? The rest of this post will show you that the answer is: very!


Why does this matter?

I’ve just told you that you can get the same results (flexibility, testability, extensibility, maintainability, …) that applying the SOLID principles give, but do so in a way that’s


What’s up next?

I will now:

  • Give a very quick introduction to each of the SOLID principles.
  • Show an example of violating the principle in C#.
  • See how we can fix the problems using object-oriented code.
  • Present an alternative, functional approach in F#.
  • Explain why the functional approach is easier to learn and teach.

All of the code for the examples below can be found at https://github.com/douglasbruce88/SOLID


Single Responsibility Principle

What is it?

A class or module should one do one thing (and hopefully do it well!)

Give me an example of breaking it

The class below both counts the number of commas in a given string, and logs that number. It thus does two things.

public class DoesTwoThings
{
    public int NumberOfCommas (string message)
    {
        int count = 0;
        foreach (char c in message)
        {
            if (c == '/') count++;
        }
        return count;
    }

    public void Log (string message)
    {
        Console.WriteLine ($"The string you gave me has { NumberOfCommas(message) } commas");
    }
}
How can I fix it in C#?

Assuming that we actually wanted the class to do the comma counting, we use dependency injection to stick in a logger and delegate the logging functionality to that. This involves creating an interface, a non-default constructor, and a class field.

public class DoesOneThing
{
    readonly ILogger Logger;

    public DoesOneThing (ILogger logger)
    {
        this.Logger = logger;
    }

    public int NumberOfCommas (string message)
    {
        int count = 0;
        foreach (char c in message) {
            if (c == '/') count++;
        }
        return count;
    }

    public void Log (string message)
    {
        this.Logger.Log($"The string you gave me has { NumberOfCommas (message) } commas");
    }
}

public interface ILogger
{
    void Log (string message);
}
What about F#?

I will admit that the code to count the number of commas is not strictly in functional style, but I wanted to keep it as similar to the C# variant as I could. The more functional approach using recursion can be found with the rest of the blog code.

All we do to solve the SRP issue is use higher-order functions, i.e. the logger. This logger can be any function with the required signature (in this case string -> unit). It doesn’t need to implement an interface (which can be tough if the code doesn’t adhere to the ISP principle, more on which to follow), we don’t need a constructor or a field in the module.

module DoesOneThing = 

  let numberOfCommas (s : string) = 
     let mutable count = 0
     for c in s do if c = '/' then count <- count + 1
     count

  let log logger (message : string) = 
      logger (sprintf "The string you gave me has %i commas" (numberOfCommas message))
      |> ignore
Why is this easier?

Contrast the OO approach:

Oh, you didn’t know about dependency injection? Here, let me explain using about twelve open-source frameworks and a 400-page book. Once you’re finished with that (not on company time, mind!), you can easily solve the problem we had.

… and by the way, the ILogger interface actually has eight methods that you need to implement, not just the one. Enjoy!

… with the functional approach

Use a higher-order function for the logger. As long as the signature matches, you’re good to go!

FP: one; OO: nil.


Open/Closed Principle

What is it?

A class or module should be open for extension, but closed for modification.

Give me an example of breaking it

Let’s say we are playing Monopoly. The rules say that if we roll a double, we get to roll again, so we write the code below. Looking more closely at the rules, three doubles in a row sends us to jail.

To make the code adhere to this rule, we have to modify the CanRollAgain method, so the class isn’t closed for modification.

public class OpenForModification
{
    public bool CanRollAgain (int firstDieScore, int secondDieScore)
    {
        return firstDieScore == secondDieScore;
    }
}
How can I fix it in C#?

One way is to make the class and implementation of the rules abstract, and then allow someone to extend the functionality by inheriting from the class.

public abstract class ClosedForModification
{
    public bool CanRollAgain (int firstDieScore, int secondDieScore)
    {
        return CanRollAgainImpl (firstDieScore, secondDieScore);
    }

    public abstract bool CanRollAgainImpl (int firstDieScore, int secondDieScore);
}

public class ThreeDoubles : ClosedForModification
{
    readonly bool LastTwoRollsAreDoubles;
    public ThreeDoubles (bool lastTwoRollsAreDoubles)
    {
        this.LastTwoRollsAreDoubles = lastTwoRollsAreDoubles;
    }

    public override bool CanRollAgainImpl (int firstDieScore, int secondDieScore)
    {
        return !LastTwoRollsAreDoubles && (firstDieScore == secondDieScore);
    }
}
What about F#?

Use a higher-order function. We allow the caller to inject an arbitrary rule function that takes in two integers and returns a bool.

let canRollAgain (firstRoll : int) (secondRoll : int) ruleSet : bool = 
    ruleSet firstRoll secondRoll
Why is this easier?

Contrast the OO approach:

So you’ll need to be able to figure out whether it’s best to use an abstract base class with an abstract implementation method, or a non-abstract base class with a virtual method and some default behaviour. Maybe go and learn about inheritance first, and then ask yourself why we didn’t use polymorphism instead.

… with the functional approach

Use a higher-order function for the rules. As long as the signature matches, you’re good to go!

FP: two; OO: nil.


Liskov Substitution Principle

What is it?

You should be able to swap an interface with any implementation of it without changing the correctness of the program.

Give me an example of breaking it

Let’s use the ILogger interface that we introduced in the Single Responsibility Principle section. Clearly the two implementations do quite different things.

public class ConsoleLogger : ILogger
{
    public void Log (string message)
    {
        Console.WriteLine (message);
    } 
}

public class NewLogger : ILogger
{
    public void Log (string message)
    {
        throw new NotImplementedException ();
    }
}
How can I fix it in C#?

In a way, you can’t. Whilst you can do something more sensible in NewLogger, it doesn’t stop someone coming along a few months later and writing

public class AnotherLogger : ILogger
{
    public void Log (string message)
    {
        throw new NotImplementedException ();
    }
}
What about F#?

Going back to the F# version, we had this injected function logger with a signature of string -> unit that we had to match.

It gets a little woolly here — there is nothing stopping you from writing

let logger : string -> unit = raise (new NotImplementedException())

In a more pure functional language such as Haskell, you wouldn’t be able to implicitly throw such an exception. However in F#, the real solution is to use something like Railway-Oriented Programming which uses the Either monad (also known as the Exception monad) to ensure that you always return something from your functions.

This relies on the developer adhering the the design principle of not throwing exceptions. Whilst this is certainly easier to do in a functional language, it’s still something else to remember.

Why is this easier?

It’s a little harder to justify here, but to me the solution is much firmer in F# — the concept of not throwing exceptions is more natural in a language where we can create constructs (such as the Either monad) to show us another way of handling exceptional situations.


Interface Segregation Principle

What is it?

A client of an interface should not be made to depend on methods it doesn’t use.

Give me an example of breaking it

Using the logging example again (and thinking about to NUnit’s version of ILogger), if we have an interface as below and want to do some kind of tracing on the method, we have no need for the LogError method on ILogger

interface ILogger
{
    void LogError (string message);

    void LogDebug (string message);
}

public class ClientWithLogging
{
    readonly ILogger Logger;

    public ClientWithLogging (ILogger logger)
    {
        this.Logger = logger;
    }

    public int NumberOfCommasWithLogging (string message)
    {
        this.Logger.LogDebug ($"Counting the number of commas in {message}");
        int count = 0;
        foreach (char c in message) {
            if (c == '/') count++;
        }

        this.Logger.LogDebug ($"{message} has {count} commas.");
        return count;
    }
}
How can I fix it in C#?

Prefer a Role Interface over a Header Interface. That is, define two interfaces doing one job each.

public interface IErrorLogger
{
    void LogError (string message);
}

public interface IDebugLogger
{
    void LogDebug (string message);
}

public class ClientWithLogging
{
    readonly IDebugLogger Logger;

    public ClientWithLogging (IDebugLogger logger)
    {
        this.Logger = logger;
    }

    public int NumberOfCommasWithLogging (string message)
    {
        this.Logger.LogDebug ($"Counting the number of commas in {message}");
        int count = 0;
        foreach (char c in message) {
            if (c == '/') count++;
        }

        this.Logger.LogDebug ($"{message} has {count} commas.");
        return count;
    }
}

There’s a slight twist to this one, though. These kind of single-method interfaces are essentially just delegates, and delegates are just encapsulations of function signatures.

The delegate form looks like this:

public delegate void DebugLogger (string message);

public class ClientWithLogging
{
    readonly DebugLogger LogDebug;

    public ClientWithLogging (DebugLogger debugLogger)
    {
        this.LogDebug = debugLogger;
    }

    public int NumberOfCommasWithLogging (string message)
    {
        this.LogDebug ($"Counting the number of commas in {message}");
        int count = 0;
        foreach (char c in message) {
            if (c == '/') count++;
        }

        this.LogDebug ($"{message} has {count} commas.");
        return count;
    }
}

The function form looks like this:

public class ClientWithLogging
{
    readonly Action<string> LogDebug;

    public ClientWithLogging (Action<string> debugLogger)
    {
        this.LogDebug = debugLogger;
    }

    public int NumberOfCommasWithLogging (string message)
    {
        this.LogDebug ($"Counting the number of commas in {message}");
        int count = 0;
        foreach (char c in message) {
            if (c == '/') count++;
        }

        this.LogDebug ($"{message} has {count} commas.");
        return count;
    }
}
What about F#?

We don’t have to change any of our code! The higher-order logger function with signature string -> unit looks suspiciously like the Action<string> method that we introduced in C#.

Why is this easier?

OO:

First, you need to read a few articles about interfaces, like those by Martin Fowler to which I linked earlier. Then, you need to know that single-method interfaces are the same as delegates. Then go and research delegates in C#.

Then realise that they are just a function encapsulation so you can use one of them instead.

Oh, but your method returns void, so you can’t use the flexible Func, you need to use the specific Action.

FP:

Higher-order functions, again. You already know about them, right?

Another win for FP!


Dependency Inversion Principle

What is it?
  • High-level modules should not depend on low-level modules. Both should depend on abstractions.
  • Abstractions should not depend on details. Details should depend on abstractions.
Give me an example of breaking it

You’ve seen this already in the very first code of the article — as well as doing two things, the high-level class below depends on the low-level behaviour of logging to the console.

public class DoesTwoThings
{
    public int NumberOfCommas (string message)
    {
        int count = 0;
        foreach (char c in message)
        {
            if (c == '/') count++;
        }
        return count;
    }

    public void Log (string message)
    {
        Console.WriteLine ($"The string you gave me has { NumberOfCommas(message) } commas");
    }
}
How can I fix it in C#?

You’ve seen this too! We use Inversion of Control to make sure that the logging implementation is abstracted

public class DoesOneThing
{
    readonly ILogger Logger;

    public DoesOneThing (ILogger logger)
    {
        this.Logger = logger;
    }

    public int NumberOfCommas (string message)
    {
        int count = 0;
        foreach (char c in message) {
            if (c == '/') count++;
        }
        return count;
    }

    public void Log (string message)
    {
        this.Logger.Log($"The string you gave me has { NumberOfCommas (message) } commas");
    }
}

public interface ILogger
{
    void Log (string message);
}
What about F#?

Well, this wasn’t a problem to begin with — we passed in a logger function that abstracted the logging bit.

Why is this easier?

I think I’ve covered most of this in the discussion of the Single Responsibility Principle. In essence, to satisfy the Dependency Inversion Principle you need to learn about several object-oriented principles, some of which are quite advanced such as Dependency Injection (yes, the book is 584 pages long).

In contrast, we only need to learn about one thing (higher-order functions) to solve the issues in F#.

Another win for FP — might just be a whitewash?


Conclusion

I hope I’ve shown in this post that the SOLID principles of object-oriented design can be satisfied in a functional programming using nothing but functions.

This is a huge contrast to an object-oriented language where a developer needs to understand a huge range of topics to implement the principles properly.

Now ask yourself which set of techniques you want to teach your next Junior Developer, and how much time, effort and money you could save by switching to a functional approach.

Thursday, May 12, 2016

Excel calculations in F# - Functional Testing

We’ve now seen the guts of a codebase that does Excel calculations. On it’s own it isn’t too revealing to look at algorithms and functions, so I thought it wise to show some of the tests that I wrote.

I’ll start by referencing the Test Pyramid:

Test Pyramid

The long and short of it is that we want to write more Unit tests than Component tests, more Component tests than Integration tests, and so on.


The Test Pyramid and Functional Programming

I’ve found functional programming to fit quite nicely into this paradigm — its emphasis on composition and pipelining means that a Component is quite often made up of a handful of composed Units, with multiple Components integrated together by composition once more. By testing each unit, we then feel sufficiently comfortable that we almost only need to smoke-test the component.

That is, if we have something like

let function1 = ...
let function2 = ...
let function3 = ...

let composite = function1 >> function2 >> function 3

and we thoroughly test function1, function2 and function3, we barely need to test composite. Granted, this security is partly due to the fantastic compile-time type system that F# gives us — the mere fact that the code above compiles is a reasonably strong indicator that the behaviour of composite is correct!

Having seen how good functional architecture leads us naturally on to good testing practices, let’s talk about the available testing tools in F#.


NUnit, NCrunch, and Unquote

Fans of C# might look at the above and think: well I know what the first two are, they are a formidable combination for continuous testing in Visual Studio, but how do they work in F#, and what is Unquote?

Taking a step back, if you are a .NET developer and don’t use NCrunch, start using it now!! Even if you aren’t doing Test-Driven Development, it will give you the confidence to know which bits of your code are tested, which aren’t, and whether your last one-line chance has broken anything. In terms of F# support, well, it just works like it does with C#!

The new boy on the block, Unquote, is pretty cool too. It uses two really nice features of F# that we haven’t looked a much yet, Code Quotations and Custom Operators. The resulting test syntax is beautiful and very readable — more that can be said about things like NUnit Assertions.

The easiest way to see it in action (other than trying it yourself) is to look at some real tests. Casting your mind back to the first bits of code we looked at last time, we had this function called StringToTokenList that took the contents of an Excel formula and turned it into a list of Token items that were strongly typed.

Here’s the first test for that function:

[<Test>]
let ``StringToTokenList 1+2``() = 
    StringToTokenList "1+2" =! [ Val(float 1)
                                 Operator Operator.Add
                                 Val(float 2) ]

A couple of nice things here are that:

  • We don’t have to bother with the tedious Arrange/Act/Assert pattern that pervades object-oriented tests. We simply write what we want to be taken as true, and use Unquote’s equality operator =!.
  • We can name the tests with as much verbosity as required, thanks to F#’s double-backtick notation. I’m not sure I am using this to full potential yet — maybe I’m stuck in the C# way of terse test names!
  • In this simple example I didn’t use a code quotation, but if the test setup were more complex I could do that rather than use a custom equality operator.
  • It’s a minor thing, but being able to initialise arrays using separate lines and no semi-colons is handy.

It carries on and gets more complicated — we can include whitespace, brackets, references, etc. in the expression, but the tests look exactly the same:

[<Test>]
let ``StringToTokenList multi digit integers``() = 
    StringToTokenList "( 123 + 321 )" =! [ LeftBracket
                                           Val(float 123)
                                           Operator Operator.Add
                                           Val(float 321)
                                           RightBracket ]

[<Test>]
let ``StringToTokenList A1 + A2 * BB312``() = 
    StringToTokenList "A1 + A2 * BB312" =! [ Ref { col = 1
                                                   row = 1 }
                                             Operator Operator.Add
                                             Ref { col = 1
                                                   row = 2 }
                                             Operator Operator.Multiply
                                             Ref { col = 54
                                                   row = 312 } ]

I’ve introduced you to the tools and frameworks I’ll use for testing, and hopefully you have some idea of what a Token list looks like, so let’s look at some more of the code tests before we move on to the working system!


Testing the Operators, Parser, and Calculator

I said last time that I had made the operators work on lists as well as numbers, and that it would be easy to extend this functionality to other types.

To test the Shunting-Yard algorithm, I was slightly naughty and used the example on the Wikipedia page. Here’s what my test looked like:

[<Test>]
let ``InfixToPostfix 5 + ((1 + 2) * 4) - 3``() = 
    InfixToPostfix [ Val (float 5)
                     Operator Operator.Add
                     LeftBracket
                     LeftBracket
                     Val (float 1)
                     Operator Operator.Add
                     Val (float 2)
                     RightBracket
                     Operator Operator.Multiply
                     Val (float 4)
                     RightBracket
                     Operator Operator.Subtract
                     Val (float 3) ]
    =! PostFixList([ Val (float 5)
                     Val (float 1)
                     Val (float 2)
                     Operator Operator.Add
                     Val (float 4)
                     Operator Operator.Multiply
                     Operator Operator.Add
                     Val (float 3)
                     Operator Operator.Subtract ])

Believe it or not, this one test managed to root out enough issue with my original implementation of the algorithm that all the subsequent tests passed first time — I guess that’s why it’s on the Wikipedia page!

For the raw operator functions such as add, I briefly experiemented with Property-Based Testing, but to be honest I struggled to grasp the nuances straight away. The code for those tests is here, and whislt it works for things like addition for which we have a good understanding of the required properties, I couldn’t easily translate it to higher-level concepts such as operator precedence.

The ‘normal’ tests I wrote were pretty basic, e.g.

[<Test>]
let ``Add x y works on values``() = Add (Val 1.0) (Val 2.0) =! Val 3.0

The calculator tests were slightly more interesting (but not much). Taking the previous example used to test the Shunting-Yard algorithm, we have

[<Test>]
let ``Calculate 5 + ((1 + 2) * 4) - 3 = 14``() = 
    Calculate(PostFixList([ Val(float 5)
                            Val(float 1)
                            Val(float 2)
                            Operator Operator.Add
                            Val(float 4)
                            Operator Operator.Multiply
                            Operator Operator.Add
                            Val(float 3)
                            Operator Operator.Subtract ]))
    =! ValResult(float 14)

Pretty basic tests — the idea of showing you some of them was to give a more intuitive feel of what the output code looked like.


System Tests: using the functions in Excel!

Excel Screenshot

The screenshot above shows a few examples of our calculator replicating Excel functionality, which serves to show that it does roughly what it should! The bottom example shows a vector calculation

RA Screenshot

This next shot shows something a bit more complex. If you look at the formula bar, you will see that it’s doing more than just arithmetic with numbers. It’s taking a reference to a cell containing 10,000 Monte Carlo simulations, performing a calculation on them to account for changes in exchange rates, and saving the results (10,000 new simulations) in a single cell.

Whilst this is very much a prototype, I think it’s a long way towards solving the problem that I originally wanted to solve. Sure, it needs a bit more TLC to be race-ready, but I think I’ve learned a decent amount about both Excel and F# in the process!


Next Time

Something a little different from the usual. I’ll be talking about the SOLID prinicples of object-oriented design and how they are much more compatible with functional programming that first meets the eye.

Monday, May 02, 2016

Excel calculations in F# - The Code, Part II

I promised a bit of a geek-out this time around; I hope you won’t be disappointed.

So far, we’ve seen how to take a general Excel expression of the form =Calculate(expression), extract the relevant bit of text from it using existing Excel interop libraries, and then put whatever result we get from the calculation back onto an Excel sheet.

All that’s left is the core of the matter: doing the calculation. The top-level code looks like this:

let rec CalcFormulaFromText = 
    StringToTokenList
    >> InfixToPostfix
    >> Calculate

At this stage it’s worth introducing some of the domain constructs that I created for the project. The first is that of a Token, which represents an individual unit that can be evaluated. I’ve used a discriminated union to model it as shown below.


The domain model, in brief

type Token = 
    | Operator of Operator
    | LeftBracket
    | RightBracket
    | ValList of float list
    | Val of float
    | Ref of Ref
    | Handle of string

where I’ve gone on to define the subtypes Ref and Operator as

type Ref = 
    { col : int
      row : int }

type Operator = 
    | Exponent = '^'
    | Divide = '/'
    | Multiply = '*'
    | Add = '+'
    | Subtract = '-'

A couple of questions probably cropped up as you scanned through these types:

  • Why are left and right brackets treated differently than other mathematical operators?
    • This is a particular quirk of the algorithm that I’m about to explain which is used in the InfixToPostfix function to convert our expression to Reverse Polish Notation. Basically, it strips brackets from the final form of the expression.
  • Why is Ref even included as a Token? After all, if it just points to another Excel cell, don’t we have the same problem of not being able to directly evaluate it?
    • A valid point. One of the first things I would do to refactor the solution would be to recurse over any references to other cells and replace the reference with the raw expression
  • What’s the obsession with float?
    • This is clearly unjustified, and was put purely for demo purposes. In reality I want to be able to deal with a more arbitrary type of value object, and would probably model things differently.

Parsing a string into a token list

Fundamentally though, I hope you understand the basic domain. We’ve got some operators, and some different kinds of stuff on which they can operate.

So how do we convert a plain old string to a list of these Token instances? I’d like to say that the code was simple, but it’s not. You can find the raw source in ExpressionParser.fs, and I’ll try to pick out some highlights of it here.

let readToken (ts : char list) = 
    match ts with
    | [] -> None
    | _ -> 
        let token = String.Concat(Array.ofList (List.rev ts))
        match token with
        | IsVal v -> Some(Val v)
        | IsRef r -> Some r
        | IsHandle h -> Some(Handle h)
        | _ -> None

let StringToTokenList(str : string) = 
    let rec handleOp op tail currentToken tokens = 
        let token = readToken currentToken
        match token with
        | None -> readChars tail (op :: tokens) List.empty
        | Some token -> readChars tail (op :: token :: tokens) List.empty

    and readChars chars tokens currentToken = 
        match chars with
        | [] -> 
            let token = readToken currentToken
            match token with
            | None -> tokens
            | Some token -> token :: tokens
        | h :: t -> 
            match h with
            | Op -> handleOp (Operator(asOperator h)) t currentToken tokens
            | Space -> readChars t tokens currentToken
            | LBracket -> handleOp LeftBracket t currentToken tokens
            | RBracket -> handleOp RightBracket t currentToken tokens
            | Other -> readChars t tokens (h :: currentToken)

    List.rev (readChars (Array.toList (str.ToCharArray())) List.empty List.empty)

These two functions, StringToTokenList and ReadToken, are the workhorses of the algorithm. The logic works roughly as follows:

  • Start with a string, represented by a list of characters.
  • Take the first character of the string.
    • If it’s an operator then add that to the output Token list
    • If it’s whitespace, ignore it and move onto the next character
    • Otherwise, put the character into a temporary local list and move onto the next.
  • Each time we add an operator to the list, we also check the temporary local list of characters and call readToken to figure out what it is. This function uses Active Patterns to see if we’ve got an int, float, etc.
  • Carry on doing this until the string is empty. At this point, figure out what it is we’ve got left.
  • After a final reverse, we end up with a list of tokens that correspond to our original string. Neat, huh?

The other cool thing is the way we set up our active patterns. Remember we’re treating all numbers as floating points, and so to see if the string we’ve got can be treated as one, we write

let (|IsVal|_|) str = 
    match Int32.TryParse(str) with
    | (true, int) -> Some(float int)
    | _ -> 
        match Double.TryParse(str) with
        | (true, float) -> Some(float)
        | _ -> None

Personally, I think this is a great way to figure out whether you’re dealing with a valid number, and much better than the C# equivalent.


Dijkstra’s shunting-yard

Now we’ve got a list of token items, how do we evaluate them? They’ve got all sorts of operators with different precedences, brackets, etc. You can probably guess the answer already: we can use shunting-yard algorithm to convert our Infix list to a Postfix (i.e. Reverse Polish Notation) list, at which stage the calculation becomes much easier (hint: we’ve done it before!!).

Without further ado, here’s my shunting-yard code:

type PostFixList = PostFixList of Token list

let InfixToPostfix ts = 
    let rec handleOperator operator tokens opStack outQueue = 
        match opStack with // add brackets to the Operator type?
        | [] -> readTokens tokens (Operator operator :: opStack) outQueue
        | Operator head :: tail -> 
            match associativity operator with
            | Left -> 
                if precedence operator <= precedence head then 
                    handleOperator operator tokens tail (outQueue @ [ Operator head ])
                else readTokens tokens (Operator operator :: opStack) outQueue
            | Right -> 
                if precedence operator < precedence head then 
                    handleOperator operator tokens tail (outQueue @ [ Operator head ])
                else readTokens tokens (Operator operator :: opStack) outQueue
        | _ -> readTokens tokens (Operator operator :: opStack) outQueue

    and transferOperators opStack outQueue = 
        match opStack with
        | [] -> outQueue
        | head :: tail -> 
            match head with
            | _ -> transferOperators tail (outQueue @ [ head ])

    and handleBrackets tokens opStack outQueue = 
        match opStack with
        | [] -> []
        | LeftBracket :: t -> readTokens tokens t outQueue
        | h :: t -> handleBrackets tokens t (outQueue @ [ h ])

    and readTokens tokens opStack outQueue = 
        match tokens with
        | head :: tail -> 
            match head with
            | Operator op -> handleOperator op tail opStack outQueue
            | LeftBracket -> readTokens tail (head :: opStack) outQueue
            | RightBracket -> handleBrackets tail opStack outQueue
            | _ -> readTokens tail opStack (outQueue @ [ head ])
        | [] -> transferOperators opStack outQueue

    PostFixList (readTokens ts List.empty List.empty)

One of the first things I did when coding this up was to tag my output type as a PostFixList to make absolutely sure I didn’t get it confused with my input list in the algorithm. This advanced type-safety was immeasurably helpful; I got the work done so much quicker for it, and with far fewer bugs.

The rest of the code is complicated but follows the logic of the Wikipedia article. it uses all the awesome bits of F#: mutual recursion, pattern matching, discriminated unions. I’ll admit it’s not readable but then again it’s not the kind of code that you write every day!


Finally, some actual calculation!

The final bit of the original top-level function does the final calculation. The evaluation code is pretty similar to the RPN calcualtor we did before:

let Eval(PostFixList ls) = 
    let solve items current = 
        match (current, items) with
        | Handle h, _ -> ValList(EvaluateHandleAsFloatList h) :: items
        | Ref r, _ -> (EvaluateReference r) :: items
        | Operator Operator.Add, y :: x :: t -> Add x y :: t
        | Operator Operator.Subtract, y :: x :: t -> Subtract x y :: t
        | Operator Operator.Multiply, y :: x :: t -> Multiply x y :: t
        | Operator Operator.Divide, y :: x :: t -> Divide x y :: t
        | Operator Operator.Exponent, y :: x :: t -> Exponent x y :: t
        | _ -> current :: items
    (ls |> List.fold solve []).Head

The one really great thing I managed to do here was to abstract addition, subtraction etc. from the main function. Rather than saying ‘when we have two things and the Add operator, do x + y, I wrote a custom function Add that is defined as let Add x y = ApplyInfixOperator x y (+), and then created an extensible way to add different types of values (int, float, list):

let rec ApplyInfixOperator x y op =         
    match (x, y) with
    | (Val xv, Val yv) -> Val(xv |> op <| yv)
    | (ValList xvs, Val yv) -> ValList(List.map (fun elt -> elt |> op <| yv) xvs)
    | (Val xv, ValList yvs) -> ValList(List.map (fun elt -> xv |> op <| elt) yvs)
    | (ValList xvs, ValList yvs) -> ValList(List.map2 (fun x y -> x |> op <| y) xvs yvs)
    | (Handle xh, Handle yh) -> ApplyInfixOperator (ValList(EvaluateHandleAsFloatList xh)) (ValList(EvaluateHandleAsFloatList yh)) op
    | (Handle xh, _) -> ApplyInfixOperator (ValList(EvaluateHandleAsFloatList xh)) y op
    | (_, Handle yh) -> ApplyInfixOperator x (ValList(EvaluateHandleAsFloatList yh)) op
    | _ -> raise InvalidInput

This relatively simple function is remarkably powerful: we have used it to do vector addition and multiplication, and can trivially extend it to matrix addition and multiplication, or whatever we like.

I think this might be the most important part of the whole project, as if I want to be able to add two instances of some internal type, all I need to do is add a branch to this function and we’re away.


Next Time

Whilst I haven’t mentioned it here, I tried to do a lot of the algorithm development using a test-driven methodology. Next time, we’ll look at some of the tests and more generally at F#’s support for testing frameworks. This should give a much more intuitive feel of what these Token lists and other domain concepts look like!