Sunday, 30 September 2012

Tailrec in Scala

One of the more tricky aspects to functional programming is optimising your code. This is because you are typically working at a higher level of abstraction than procedural languages. The code you write isn't necessarily a natural fit to the way the processor works. For example, if you want to compare the factorial function in C# vs Scala:

C#:

public void Factorial(int n) 
{
    var result = 0;
    for (int i = n; i > 0; i--)
    {
        result *= i;
    }
    return result;
}

Scala:

def factorial(n: Int): Int = 
    if (n == 0) 1
    else n * factorial(n - 1)

The big difference here is that in a procedural language you'll tend to write a loop that side effects on a variable where as in a functional language you'll tend to use recursion or a higher order function to write side-effect free code. Processors are really good at the former.

What we see here is a compromise between performance and readability. The C# code will be quicker because the code will do all its work in the same stack frame. The Scala version will create n stack frames while calling itself recursively. However, the Scala version is easier to reason about because there are no side effects, i.e. you're not rewriting result in a loop. You may disagree for such a simple example, but once you have a couple of loops and several variables, procedural code becomes very difficult to follow.

Most functional languages address this issue by performing an optimisation called tail-call optimisation. However, some languages are better at it than others. In Scala you need to make sure that your recursive call is in the tail position (i.e. the recursive call is the last expression). In the factorial example above, it isn't the tail expression is actually n * factorial(n - 1). (You can read about this in more detail here and here.)

Reasoning about whether recursive functions will or won't be optimised is a problem for beginners because it isn't always obvious what qualifies for optimisation. There are other criteria to take into account such as the call must be a local function and the function must be final. A great feature of Scala is an annotation, @tailrec, that raises a compile error you if your function won't be optimised:

import scala.annotation.tailrec

@tailrec
def factorial(n: Int): Int = 
    if (n == 0) 1
    else n * factorial(n - 1)

This will generate a compile error in this case because the recursive function can't be tail-call optimised.

To allow the compile to optimise this, you will need to find a way to have the tail call be the recursive call, for example:

def factorial(n: Int): Int = {
    @tailrec
    def recFac(n: Int, acc: Int): Int = 
        if (n == 0) acc
        else recFac(n - 1, acc * n)
    recFac(n, 1)
}

I learnt about @tailrec through Martin Odersky's Scala course on Coursera. The course is fantastic, Odersky's lectures are very interesting and tie theory into practical applications very neatly. The practical assignments really take me back to my first year of university.

Saturday, 15 September 2012

Odd MSBuild platform behaviour

I came across some odd behaviour with msbuild this week. I was building a solution from the command line and setting the platform to Any CPU. This worked find and the whole solution built. I then built one of the projects in the solution on its own (to create a clickonce installer), again with the platform set to Any CPU, and this time it failed. The error I got was that I was trying to build for an unknown platform.

It turns out that the actual platform described in the .csproj is AnyCPU (i.e. without a space) and that when building a solution Any CPU gets translated to Any CPU. So to build a solution you need to use Any CPU and to build a project you need to use AnyCPU. How bizarre.

Saturday, 8 September 2012

Alternative dependency injection in F#

Dependency injection is a pattern where a dependency of a class is passed to an instance of the class at runtime and is not created by the class itself. This is very useful for decoupling code, especially when you are unit testing and want to mock a dependency.

In OO languages like C# and Java, this is mostly often done with constructor injection, i.e.:

interface IB
{
        void DoB();
}

class A
{
        public A(IB b)
        {
                this.b = b;
        }

        public DoA()
        {
                this.b.DoB();
        }

        private IB b;
}

The same thing can be done in F#, but there's an alternative. You could have your dependency be an abstract member and use an object expression to create a concrete instance that has the correct dependency.

type IB =
    abstract DoB : unit -> unit

type B() =
    interface IB with
        member this.DoB() = ()

[<AbstractClass>]
type A() = 
    abstract b : IB
    member this.doA() = this.b.DoB()

let implA = 
    { new A() with 
        member x.b = B() :> IB
    }

This isn't a better way of doing dependency injection. It's a more complicated way of achieving pretty much the same thing, but it does remind me a little of the Scala cake pattern.

Sunday, 2 September 2012

MarkdownPreview 0.2.0

I've uploaded a new version of MarkdownPreview. You can pick it up here. This includes:

  • A better HTML render. The main benefit is that scrolling doesn't go back to the top when the Markdown source is reloaded.
  • Syntax highlighting. This uses Google prettify. You can add syntax to a code block by putting {{cs}} (for csharp, see here) at the top of your code block.

Saturday, 1 September 2012

MarkdownPreview

MarkdownPreview is a small Windows utility to watch a text file written in Markdown for changes and to render it to HTML. You can download it or visit the project page.

MarkdownPreview 0.1.0

I write my blog posts in Markdown using Vim. I wanted to be able to preview what I was writing as I was writing it. While there are some Markdown enabled editors out there, I wanted to stick to Vim, so I wrote a small utility to watch my markdown file for changes and re-render to HTML whenever I save it.

I think this is my first open-source effort (MIT license)! It's only about an hours worth of work, so there may well be problems. Let me know if you find any. The main problems now are:
  • The page scrolls back to the top when it reloads
  • The links are followed in MarkdownPreview, not externally
  • There is annoying sound-effect when the page reloads
  • No syntax highlighting
I'll take a look at these soon.

Monday, 27 August 2012

The object-oriected TDD journey

When you start practicing TDD for real, one of the first problems you'll come across is dependency management. Chances are, that before you were TDDing, whenever you needed to use class A from class B, B would create it's own instance of A or A might be a singleton.

class B
{
    private A instanceA = new A();
}

You soon find that you want to mock A and the best way to get the mock of A into an instance of B (your SUT), is to pass it into the constructor. This is called Dependency Injection:

class B
{
    public B(A a)
    {
        instanceA = a;
    }

    private readonly A instanceA;
}

You also find that you don't want a dependency on A because creating an instance of the mock of A is going to call the constructor of A. So you solve that by having A implement an interface IA and pass IA to B instead.

class B
{
    public B(IA a)
    {
        instanceA = a;
    }

    private readonly IA instanceA;
}

Your next problem comes along when you actually want to create an instance of B. Say the constructor of A takes an instance of IC, you will need to do the following when you want a new B:

B instanceB = new B(new A(new C))

For a large application, this step will be a horror of nested news. So you will then learn about Inversion Of Control and this will help you manage your dependencies:

IocContainer container = new IocContainer();
container.Register<B>();
container.Register<IA>().ImplementedBy<A>();
container.Register<IC>().ImplementedBy<C>();
B instanceB = container.Resolve<B>();

Here the IOC framework is responsible for figuring out the dependencies of B and creating the required instances recursively.

Now you find that you're making a mess becase your IOC framework is letting you create a dependency from any class in your system to any other. You now pay attention to group your classes into modules with small, well-defined interfaces between them.

When working on a piece of code you will try and break it down into small coherent modules that look like stand-alone libraries. They will ideally have a very small set of public interfaces. The IOC registration will be done by the module itself and classes external to the module should only use the public interfaces. This prevents a spaghetti of inter-class dependencies.

Sunday, 26 August 2012

Rich Hickey on Debugging

I was reading Micheal Fogus' interview with Rich Hickey, the man behind Clojure. When asked why he is considered an excellent debugger, his answer was fantastic. It often surprises me that this isn't how many programmers approach debugging.

Fogus: I’ve spoken with a few of your former co-workers, and they described you as a trouble-shooting and debugging master. How do you debug? 
Hickey: I guess I use the scientific method. Analyze the situation given the available information, possibly gathering more facts. Formulate a hypothesis about what is wrong that fits the known facts. Find the smallest possible thing that could test the hypothesis. Try that. Often this will involve constructing an isolated reproducing case, if possible. If and only if the hypothesis is confirmed by the small test, look for that problem in the bigger application. If not, get more or better facts and come up with a different idea. I try to avoid attempting to solve the problem in the larger context, running in the debugger, just changing things to see effects, etc.
Ideally, you know you have solved the problem before you touch the computer, because you have a hypothesis that uniquely fits the facts.