(For reference purposes, I compiled the examples using Microsoft F# 2.0, Compiler build 4.0.30319.1 and examined the results using Red Gate’s .NET Reflector v.6.0.0.918. And, as always: presented “as-is” and without warranty or implied fitness; use at your own risk.)

Assuming no side effects are added to them, the three bindings below compile to code which can produce identical results. In this case, it is a simple integer sum. The first version calls an internal function, while the second and third versions return a curried internal function. (In each of the examples, note that the code for the internal function sum’ is identical.)

`let sum1 n =`

let rec sum' a n =

match n with

| _ when n<=0 -> a

| _ -> sum' (a+n) (n-1)

sum' 0 n

let sum2 =

let rec sum' a n =

match n with

| _ when n<=0 -> a

| _ -> sum' (a+n) (n-1)

sum' 0

let sum3 () =

let rec sum' a n =

match n with

| _ when n<=0 -> a

| _ -> sum' (a+n) (n-1)

sum' 0

So what are the differences? Major, as it turns out.

But first, let’s add some side effects and some test code that makes this apparent:

`open System`

open System.Collections.Generic

let sum1 n =

Console.WriteLine("1: Instantiating HashSet")

let h = new HashSet<int>()

let rec sum' a n =

Console.WriteLine("1: Add {0} -> {1} ",n,(h.Add n))

match n with

| _ when n<=0 -> a

| _ -> sum' (a+n) (n-1)

sum' 0 n

let sum2 =

Console.WriteLine("2: Instantiating HashSet")

let h = new HashSet<int>()

let rec sum' a n =

Console.WriteLine("2: Add {0} -> {1} ",n,(h.Add n))

match n with

| _ when n<=0 -> a

| _ -> sum' (a+n) (n-1)

sum' 0

let sum3 () =

Console.WriteLine("3: Instantiating HashSet")

let h = new HashSet<int>()

let rec sum' a n =

Console.WriteLine("3: Add {0} -> {1} ",n,(h.Add n))

match n with

| _ when n<=0 -> a

| _ -> sum' (a+n) (n-1)

sum' 0

System.Console.WriteLine ("------- Starting test calls. -------")

System.Console.WriteLine ("1: ---------------- Result={0} ",(sum1 2))

System.Console.WriteLine ("2: ---------------- Result={0} ",(sum2 2))

System.Console.WriteLine ("3: ---------------- Result={0} ",(sum3() 2))

System.Console.WriteLine ("1: ---------------- Result={0} ",(sum1 2))

System.Console.WriteLine ("2: ---------------- Result={0} ",(sum2 2))

System.Console.WriteLine ("3: ---------------- Result={0} ",(sum3() 2))

System.Console.ReadLine() |> ignore

And here is the result of compiling and running the above:

`2: Instantiating HashSet`

------- Starting test calls. --------

1: Instantiating HashSet

1: Add 2 -> True

1: Add 1 -> True

1: Add 0 -> True

1: ----------------- Result=3

2: Add 2 -> True

2: Add 1 -> True

2: Add 0 -> True

2: ----------------- Result=3

3: Instantiating HashSet

3: Add 2 -> True

3: Add 1 -> True

3: Add 0 -> True

3: ----------------- Result=3

1: Instantiating HashSet

1: Add 2 -> True

1: Add 1 -> True

1: Add 0 -> True

1: ----------------- Result=3

2: Add 2 -> False

2: Add 1 -> False

2: Add 0 -> False

2: ----------------- Result=3

3: Instantiating HashSet

3: Add 2 -> True

3: Add 1 -> True

3: Add 0 -> True

3: ---------------- Result=3

After adding side effects, the first and third versions produce similar results (though they are very different under the hood, as is hinted at by the different means of calling the third version). The second version produces a different result. To show why this is so, let me try to state, in plain terms, what each of the three bindings does.

Example one binds sum1 to a function that takes a single argument, n. When this function is executed, it: 1) instantiates a HashSet, 2) calls the internally defined function sum’ with arguments 0 and n, with the HashSet captured in a closure, and 3) returns the result.

Example two: 1) instantiates a HashSet, and 2) binds sum2 to a curried version of an internal function sum’ which captures that hash set in a closure and is curried with an argument of 0. When sum2 is called with an argument, that curried function is called.

Example three binds sum3 to a function with no arguments. When that function is executed, it: 1) instantiates a HashSet, 2) returns a curried version of an internal function sum’ which captures that hash set in a closure and is curried with an argument of 0. When the result of executing sum3 is called with an argument, that curried function is called.

Example 1 comes closest to what we normally think of as a function call. Every time it is executed, it instantiates a new local copy of a HashSet and then calls an internal function. Examining the code in IL or (or decompiling it using some tool like Red Gate’s .NET Reflector) will show that this is a good description of its internal behavior as well.

Example 2 comes closer to behaving like a traditional object. It instantiates one HashSet which, like an object property, is shared across all the calls to the returned function. It’s a little bit like returning a delegate which accesses a static property, and if one looks at the IL, this is very much how it is implemented. (An class is created to represent the binding, but HashSet is made into a property of the main program class.)

Example 3 combines the behavior of the two. Like example 2, rather than binding to a function, it binds to something that returns a function. However, like example 1, the instantiation of the HashSet occurs when the function is executed rather than when the symbol is bound.

So which to choose?

Obviously, if you need some set of side effects to occur on every function call, either method 1 or method 3 is an obvious choice. If, on the other hand, you need some set of side effects to occur once, method 2 is probably your best bet.

And being me, when picking an algorithm, once the criteria of correctness, appropriateness, and maintainability are met, my next most important consideration is…

Benchmarks!

So I did a simple test of the three methods, removing the side effects and simply doing the summation. The results after some myriad iterations of each on the same data are:

Method 1: 2.42 seconds.

Method 2: 2.81 seconds.

Method 3: 10.92 seconds.

Methods 1 and 2 are the clear winners, with method 3 a distant third. These results are also predictable from an examination of the source code. Clearly, unless some application demands method 3, the others are superior. However, methods 1 and 2 are close enough in performance that (if side-effects are not a consideration) the choice can be made based on which best represents the underlying concepts the code is intended to represent.

[I’m relatively new to F#, and my grad-school lambda calculus is rusty, I welcome any corrections of fact or terminology to the above.]

-Neil

## 3 comments:

Thanks for this post Neil. I had never considered the difference between these three styles before.

Thanks for reading. To me, one of the most interesting things about F# is the richness of expression possible by combining simple, basic constructs. It can make for tough coding choices! Looking at the details makes it easier to aim the apple of discord.

Post a Comment