I received a comment in my article about discriminated unions that the recursive function
calcLength was not tail call optimized.
Yikes I need to fix that, I had heard of tail call optimization but I had not really looked at it at this point.
Well, how hard could it be anyway, so I did some searching and looked at some articles. Recursion and Tail-recursion in F# by Karlkim Suwanmongkol, Tail calls in F# – MSDN Blogs and What is tail-recursion? – StackOverflow
After reading these articles, I realized that my recursive calls needed to be made as a single unit. A simple call with a simple return value. I needed a
Tail Call, a sub routine call performed as the last action of a function. A tail call to a recursive function can be optimized by the the F# into a loop.
That sounds simple enough, and for a seasoned expert I’m sure it is.
Here is the original stating point code:
let rec calcLength x = match x with | Circle (_,r) -> System.Math.PI * r * 2. | Ellipse (_,r1,r2) -> System.Math.PI * 2. * sqrt( (r1 * r1 ) + (r2 * r2 ) / 2.) | Square (_, w,_) -> w * 4. | MultiPrimitive  -> 0. | MultiPrimitive (head::tail) -> calcLength (MultiPrimitive tail) + (calcLength head)
There are are two problems with the code above, the first is that there are two calls to
calcLength. And the second is that even if there was only one call, the plus operator ties the final call to
calcLength to another value and so it would not be considered a tail call.
To make this function conform to the needs of tail call optimization it is necessary to change the last match for MultiPrimitive such that there is a single call to
| MultiPrimitive (head::tail) -> calcLength ...
So the solution is a simple as that, the trick is in filling in the dots.
Introducing CPS or Continuation Passing Style. This is a common pattern used in F# ( and other functional languages). The pattern is useful for tail call optimization because it allows computations to be passed along for somebody else to do. Using this pattern can allow a recursive function call to be simplified ( actually it looks more complex, but to compiler its simplified ) such that it qualifies for tail call optimization. In our case we need to call
calcLength once and pass all the other calculations along to be done later.
Well in order to pass off work, a function parameter should be included as an argument to
calcLength. From the examples I’ve seen using the pattern it is often named
cont for continuation function.
Starting with just the non recursive part, here is how the function now looks:
let rec calcLength x cont = match x with | Square (_, w,_) -> cont (w * 4.) let r = calcLength (Square( (10.,10.), 10., 45. )) (fun x -> x )
When square is matched, instead of just returning the result, it passes the result as a parameter to cont, then cont returns the result.
Diving in, here is
calcLength using CPS
let rec calcLength x cont = match x with | Circle (_,r) -> cont (System.Math.PI * r * 2.) | Ellipse (_,r1,r2) -> cont (System.Math.PI * 2. * sqrt( (r1 * r1 ) + (r2 * r2 ) / 2.)) | Square (_, w,_) -> cont (w * 4.) | MultiPrimitive  -> cont 0. | MultiPrimitive (h::t) -> calcLength h (fun hResult -> calcLength (MultiPrimitive t) (fun tResult -> cont (hResult + tResult)))
The base cases are the same as the
Square example above, they just pass there calculation result into the continuation method which intern returns the result.
The recursive part now calls
calcLength once just for the head. And it composes a function that computes the tail result and adds it to the head result. This composed function is passed with the head as the cont function.
Like the base cases, the composed function eventually ends up calling cont with the head result and the tail result added. But the main point is that every call to
calcLength is in the simple form as described above.
One tip I was given by Tomas Petricek was that if you are using Visual Studio, you need check
Generate tail calls in your project settings in order to get the tail calls optimized.
To be honest, looking at this final code causes me a double take, it is not nearly as simple as the original. Would this be a better candidate for a loop and a mutable variable? Personally I like code to be as simple as possible for the reader. However, it may be I’m just too new to F#, perhaps after some time you just instantly recognise this pattern and immediately understand what’s going on.
I would love to hear your comments and thoughts about this.