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:


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


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

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 = {
    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()

        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() = ()

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 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.