{"id":49714,"date":"2023-12-28T10:05:00","date_gmt":"2023-12-28T18:05:00","guid":{"rendered":"https:\/\/devblogs.microsoft.com\/dotnet\/?p=49714"},"modified":"2023-12-28T10:05:00","modified_gmt":"2023-12-28T18:05:00","slug":"safer-recursion-in-fsharp","status":"publish","type":"post","link":"https:\/\/devblogs.microsoft.com\/dotnet\/safer-recursion-in-fsharp\/","title":{"rendered":"Safer recursion in F#"},"content":{"rendered":"
\n

This is a guest blog post by David Schaefer<\/strong>. David is a freelancing software developer with a focus on functional programming. He’s a member of the G-Research<\/a> Open Source Team. There he works on improving the F# ecosystem, mainly developer tooling. Furthermore, he helps maintaining various F# Open Source projects.<\/p>\n<\/blockquote>\n

It’s very common to define algorithms in a recursive way in functional programming. It fits very well with the mindset of avoiding mutation, and often there’s no performance downside. The compiler tries to rewrite recursive definitions into more efficient loops during its optimization phase. <\/p>\n

However, the compiler is not always able to do this transformation into loops. And here is where the danger starts.<\/p>\n

Stack frames vs. Production<\/h2>\n

Calling a function g<\/code> from inside a function f<\/code> normally creates a new stack frame on the call stack of the process. After the function g<\/code> is done, its stack frame isn’t needed anymore and its space can be reused.<\/p>\n

Now, with recursive functions, this stack frame creation can be vital to understand. In general, for every recursive call, a new stack frame is created. During development time, when problem sizes are rather small, this often doesn’t cause an issue. But later in production, with bigger problem sizes, the program crashes all of a sudden with a stack overflow.<\/p>\n

What happened? There were so many stack frames created for the recursive calls, that all space for the stack was used up and the runtime decided to stop it. To demonstrate this, take a look at this recursive function:<\/p>\n

let rec countDown1 n =\n    if n = 0\n    then 0\n    else\n        countDown1 (n - 1) + 1<\/code><\/pre>\n
The generated IL code for it looks like this:<\/p>\n
.method public static \n    int32 countDown1 (\n        int32 n\n    ) cil managed \n{\n    \/\/ Method begins at RVA 0x2050\n    \/\/ Header size: 1\n    \/\/ Code size: 17 (0x11)\n    .maxstack 8\n\n    IL_0000: nop\n    IL_0001: ldarg.0\n    IL_0002: brtrue.s IL_0006\n\n    IL_0004: ldc.i4.0\n    IL_0005: ret\n\n    IL_0006: ldarg.0\n    IL_0007: ldc.i4.1\n    IL_0008: sub\n    IL_0009: call int32 Program::countDown1(int32)\n    IL_000e: ldc.i4.1\n    IL_000f: add\n    IL_0010: ret\n} \/\/ end of method Program::countDown1<\/code><\/pre>\n
You can see the recursive call at IL_0009<\/code>. Calling coundDown1<\/code> with n = 1_000<\/code>, like one would casually do during development, terminates just fine, but calling it with n = 1_000_000<\/code> crashes with a stack overflow.<\/p>\n
Compare this to the following:<\/p>\n
let rec countDown2 n =\n    if n = 0\n    then 0\n    else\n        countDown2 (n - 1)<\/code><\/pre>\n
which results in:<\/p>\n
.method public static \n    int32 countDown2 (\n        int32 n\n    ) cil managed \n{\n    \/\/ Method begins at RVA 0x2064\n    \/\/ Header size: 1\n    \/\/ Code size: 13 (0xd)\n    .maxstack 8\n\n    \/\/ loop start\n        IL_0000: nop\n        IL_0001: ldarg.0\n        IL_0002: brtrue.s IL_0006\n\n        IL_0004: ldc.i4.0\n        IL_0005: ret\n\n        IL_0006: ldarg.0\n        IL_0007: ldc.i4.1\n        IL_0008: sub\n        IL_0009: starg.s n\n        IL_000b: br.s IL_0000\n    \/\/ end loop\n} \/\/ end of method Program::countDown2<\/code><\/pre>\n
The difference is that in countDown1<\/code> the returned value of the recursive call was used to construct the final value of the function by adding 1 to it. In contrast, in countDown2<\/code> the returned value of the recursive call is also the value of the function itself. Meaning, the recursive call is the last instruction in the function definition – a style known as tail recursion<\/a>. This style allowed the compiler to transform the function into a loop, thus eliminating the need to create new stack frames.<\/p>\n
Besides the chance for the compiler to rewrite a recursive function into a loop, there’s another escape-door that opens up through the use of tail recursion: the IL prefix tail.<\/code> In ECMA-335<\/a>, it is explained like this:<\/p>\n
It indicates that the current method\u2019s stack frame is no longer required and thus can be removed before the call instruction is executed. Because the value returned by the call will be the value returned by this method, the call can be converted into a cross-method jump.<\/code><\/pre>\n
To demonstrate it, we use the example from RFC-1011<\/a>, more on that later. Consider the mutually recursive F# functions:<\/p>\n
let foo x =\n    printfn \"Foo: %x\" x\n\n[<TailCall>]\nlet rec bar x =\n    match x with\n    | 0 ->\n        foo x           \/\/ OK: non-tail-recursive call to a function which doesn't share the current stack frame (i.e., 'bar' or 'baz').\n        printfn \"Zero\"\n\n    | 1 ->\n        bar (x - 1)     \/\/ Warning: this call is not tail-recursive\n        printfn \"Uno\"\n        baz x           \/\/ OK: tail-recursive call.\n\n    | x ->\n        printfn \"0x%08x\" x\n        bar (x - 1)     \/\/ OK: tail-recursive call.\n\nand [<TailCall>] baz x =\n    printfn \"Baz!\"\n    bar (x - 1)         \/\/ OK: tail-recursive call.<\/code><\/pre>\n
Here we get the following IL code for case 1<\/code> in bar<\/code>:<\/p>\n
    ...\n    IL_0030: ldarg.0\n    IL_0031: ldc.i4.1\n    IL_0032: sub\n    IL_0033: call void Program::bar(int32)\n    IL_0038: nop\n    IL_0039: ldstr \"Uno\"\n    IL_003e: newobj instance void class [FSharp.Core]Microsoft.FSharp.Core.PrintfFormat`5<class [FSharp.Core]Microsoft.FSharp.Core.Unit, class [System.Runtime]System.IO.TextWriter, class [FSharp.Core]Microsoft.FSharp.Core.Unit, class [FSharp.Core]Microsoft.FSharp.Core.Unit, class [FSharp.Core]Microsoft.FSharp.Core.Unit>::.ctor(string)\n    IL_0043: stloc.0\n    IL_0044: call class [netstandard]System.IO.TextWriter [netstandard]System.Console::get_Out()\n    IL_0049: ldloc.0\n    IL_004a: call !!0 [FSharp.Core]Microsoft.FSharp.Core.PrintfModule::PrintFormatLineToTextWriter<class [FSharp.Core]Microsoft.FSharp.Core.Unit>(class [System.Runtime]System.IO.TextWriter, class [FSharp.Core]Microsoft.FSharp.Core.PrintfFormat`4<!!0, class [System.Runtime]System.IO.TextWriter, class [FSharp.Core]Microsoft.FSharp.Core.Unit, class [FSharp.Core]Microsoft.FSharp.Core.Unit>)\n    IL_004f: pop\n    IL_0050: ldarg.0\n    IL_0051: tail.\n    IL_0053: call void Program::baz(int32)\n    IL_0058: ret\n    ...<\/code><\/pre>\n
Because the call to baz<\/code> happens in a tail recursive way, the compiler can use the tail.<\/code> prefix for it in IL_0051<\/code>. Compare this to the call to bar<\/code> in  IL_0033<\/code>.<\/p>\n
Let the compiler understand your intent<\/h2>\n
So, all we have to do to keep using elegant recursive functions is to define them in the tail recursive style, right?<\/p>\n
Well, easier said than done. Making sure a function is defined in a tail recursive way can be a challenge as the complexity of the function increases and various programmers work on the code. So it would be desirable that the compiler warns about a function which isn’t tail recursive but should be according to the stated intend of the developer.<\/p>\n
This is exactly what happened with RFC-1011<\/a>. A new attribute, [<TailCall>]<\/code>, was implemented in the F# compiler. Developers can use it to make their intent clear – that a function should be tail recursive. Functions annotated with this attribute are checked if they are really tail recursive and if not, a warning is emitted. <\/p>\n
The analysis for the warning is made after the optimization phase of the compiler, so any rewrite of a recursive function has already been applied. Otherwise, a false warning could be emitted about a function that the compiler is able to rewrite into a loop, for example. During the analysis the typed abstract syntax tree (TAST) is traversed and recursive calls to functions with the new attribute are checked if they happen in a tail recursive manner. An example of a characteristic that would render a function call non-tail recursive would be the first position in a Sequential<\/code> expression.<\/p>\n
Applying this new attribute to countDown1<\/code> would look like this:<\/p>\n
[<TailCall>]\nlet rec countDown1 n =\n    if n = 0\n    then 0\n    else\n        countDown1 (n - 1) + 1<\/code><\/pre>\n
With F# 8, the compiler warns about the non-tail recursive definition of the function:<\/p>\n
Program.fs(6,9): warning FS3569: The member or function 'countDown1' has the 'TailCallAttribute' attribute, but is not being used in a tail recursive way. [tailrec_blog.fsproj]<\/code><\/pre>\n
With this feature of the compiler, developers should be able to concentrate more on the domain of their work and\nworry less about technical details of the compiled code.<\/p>\n
Acknowledgements<\/h2>\n
So far, implementing this warning was my biggest contribution to the F# compiler. I had to try different approaches until the PR<\/a> was approved. A few bug fixes followed which didn’t make the cut for .NET 8, but should be in the first patch release.<\/p>\n
I want to thank everyone who helped me along the way and I want to thank Avi Avni<\/a> for opening the first PR<\/a> of this feature many years ago.<\/p>\n","protected":false},"excerpt":{"rendered":"
Tail recursion is a new F# compiler feature which helps to avoid stack overflows.<\/p>\n","protected":false},"author":139675,"featured_media":49715,"comment_status":"open","ping_status":"","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"footnotes":""},"categories":[685,636],"tags":[7778,73,7777],"class_list":["post-49714","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-dotnet","category-fsharp","tag-algorithms","tag-f","tag-recursion"],"acf":[],"blog_post_summary":"
Tail recursion is a new F# compiler feature which helps to avoid stack overflows.<\/p>\n","_links":{"self":[{"href":"https:\/\/devblogs.microsoft.com\/dotnet\/wp-json\/wp\/v2\/posts\/49714","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/devblogs.microsoft.com\/dotnet\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/devblogs.microsoft.com\/dotnet\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/dotnet\/wp-json\/wp\/v2\/users\/139675"}],"replies":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/dotnet\/wp-json\/wp\/v2\/comments?post=49714"}],"version-history":[{"count":0,"href":"https:\/\/devblogs.microsoft.com\/dotnet\/wp-json\/wp\/v2\/posts\/49714\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/dotnet\/wp-json\/wp\/v2\/media\/49715"}],"wp:attachment":[{"href":"https:\/\/devblogs.microsoft.com\/dotnet\/wp-json\/wp\/v2\/media?parent=49714"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/dotnet\/wp-json\/wp\/v2\/categories?post=49714"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/dotnet\/wp-json\/wp\/v2\/tags?post=49714"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}