This post is part of our F# 8 series, in which we'll be digging into a few of the best features in the latest version of the language.
One of the core principles of functional programming is immutability by default. Gone are the days of 'why is this value all of a sudden different than what it was before?'. As a result, things that are traditionally done in loops are generally done with recursive functions.
The problem of recursive code
Let's take a look at one of these recursive functions, that calculates the length of a list:
let rec length input =
match input with
| _ :: tail -> length (tail) + 1
| [] -> 0
This seems like a pretty innocent piece of code, but let's see what happens if we call it with a large input:
> length [0..999999];;
Stack overflow.
Repeat 9638 times:
...
That's no good! As with any other function, the first call to a recursive function can only finish once all other recursive calls are finished; we get a stack overflow.
Using tail recursion to avoid stack overflows
One way of avoiding this is by making your functions tail recursive. You make sure that there are no operations that take place after the recursive function call. In itself, this does not solve the problem, but the F# compiler uses tail call optimalization to convert these functions into regular loops. A common way of making your functions tail recursive is passing in an accumulator.
let rec length input acc =
match input with
| _ :: tail -> length tail (acc + 1)
| [] -> acc
If we run it with the same argument that we used for the non-tail recursive function, we don't run into issues:
> length2 [0..999999] 0;;
val it: int = 1000000
In fact, we never will!
The TailCall attribute
But how do we ensure we don't actually write non-tail recursive code that will lead to stack overflows in production? Introducing the [<TailCall>]
> compiler attribute! Add this to a function, and you'll be notified if it is not tail recursive. If you add it to the first iteration of our reverse function, you'll get the following warning:
warning FS3569: The member or function 'reverse' has the 'TailCallAttribute' attribute, but is not being used in a tail recursive way.
This is a brand new F# 8 feature. You can read all about how this feature came to life on the Microsoft .Net blog
An uncovered case
While writing this post, I noticed that, when using the TailCall attribute, the compiler would not warn me of all cases where a recursive call is not in the tail position. The following function would not trigger a warning, but is not tail recursive, and can still lead to stack overflows:
let rec reverse (input: list<'t>) =
match input with
| head :: tail -> [ yield! reverse tail; head ]
| [] -> []
I created a GitHub issue, and within a week, Dawe had fixed the issue.
The TailCall check recursively goes through all operations in the AST of the function to see if they somehow prove the function is not tail recursive. One of these AST operations, Coerce, is now used to prove that a function is not tail recursive.
Conclusion
Tail calls can help you avoid stack overflows in recursive functions, and you can now let the compiler check whether function uses tail recursion.
This compiler feature is a great example of how an open source project with a active community can grow and improve. Want to get involved in F# open source projects? Amplifying F# can help you make your first steps!