[<TailCall>] not used in suggested version example

[JasonKleban]

Type of issue

Typo

Description

This is given as the Tail Call Optimized version of fib but it doesn't actually use the TailCallAttribute. Furthermore, it is unobvious to me if [<TailCall>] should be placed on fib or on the inner recursive loop binding.

I don't think the attribute can even be applied on loop binding, but fib isn't actually recursive. If putting the attribute on fib is correct, that suggests that any function inside fib would have this TailCall constraint which seems like an inappropriate restriction.

let fib n =
    let rec loop acc1 acc2 n =
        match n with
        | 0 -> acc1
        | 1 -> acc2
        | _ ->
            loop acc2 (acc1 + acc2) (n - 1)
    loop 0 1 n

Can you please clarify in this example where to use [<TailCall>]? And discuss any interesting side-topics about that placement regarding propagation of the constraint?

Page URL

https://learn.microsoft.com/en-us/dotnet/fsharp/language-reference/functions/recursive-functions-the-rec-keyword

Content source URL

https://github.com/dotnet/docs/blob/main/docs/fsharp/language-reference/functions/recursive-functions-the-rec-keyword.md

Document Version Independent Id

4aececf7-7876-3bc1-f722-1004b25fe05d

Platform Id

e195630b-53b2-2298-0270-c4ba6e3a3bd9

Article author

@KathleenDollard

Metadata

• ID: 029d87c5-6502-8151-c903-dec53a570b0a
• PlatformId: e195630b-53b2-2298-0270-c4ba6e3a3bd9
• Service: dotnet-fsharp

Related Issues

[BillWagner]

tagging @T-Gro for his thoughts.

[T-Gro]

In the content right below it, it is explained what TailCallAttribute does - it is only about emitting a warning, a function can be tail recursive without it just fine.

Starting with F# 8.0, you can use the TailCall attribute to explicitly state your intention of defining a tail-recursive function to the compiler. The compiler will then warn you if your function makes non-tail recursive calls. You can use the attribute on methods and module-level functions.
For example, using it on the first fib definition:

We will for sure be happy for any suggestion on how to make that more clear if needed.

Regarding the inner function - indeed, attributes cannot be placed on inner function as of now (since those functions can get inlined and for a class of attributes, this would lead to unmet expectations - imagine putting ASP.NET related attributes but then at runtime it would inlined and removed...)

[JasonKleban]

Since this is the documentation about the TailCallAttribute, I think it's fair to expect to see an example where it is used properly in a passing scenario, no?

Perhaps this can work as a simple, low-value example:

[<TailCall>]
let rec factorial n accumulator = 
    match n with
    | 0u | 1u -> accumulator
    | _ -> factorial (n - 1u) (n * accumulator)

But then the original example would be more valuable to discuss. This is incorrect, but what is the suggested fix?

[<TailCall>]  /// ❌ "warning FS3861: The TailCall attribute should only be applied to recursive functions."
let fib n =
    let rec loop acc1 acc2 n =
        match n with
        | 0 -> acc1
        | 1 -> acc2
        | _ -> loop acc2 (acc1 + acc2) (n - 1)
    loop 0 1 n

Must we do this?

[<TailCall>]
let rec loop acc1 acc2 n =
    match n with
    | 0 -> acc1
    | 1 -> acc2
    | _ -> loop acc2 (acc1 + acc2) (n - 1)
    
let fib n =
    loop 0 1 n

[T-Gro]

Yes, it must be lifted to a top level function in order for attributes to be allowed.
The TailCall documentation is in the same page, just below your sample - if you have a proposal for merging the texts together, this can be a solution 👍