A Spell-Binding Tale of Three Recursions

One coding problem that often arises is the need to package a tail recursive function in some syntactic wrapper. Tail recursive functions often involve accumulators, continuations, and other values which are not really of concern to the ultimate users of those functions. These can often be curried away or otherwise hidden from the ultimate user. This post looks at three obvious techniques for doing so (there are some more that are less obvious), the differences between the three techniques, etc.

(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