dotnet
[<TailCall>] attribute gives incorrect warning in many examples
This code compiles fine:
[<TailCall>]
let rec fib a b = seq {
yield a
yield! fib b (a + b)
}
let fibonacci = fib 0 1
But the following minor change produces the message: The member or function 'fib' has the 'TailCallAttribute' attribute, but is not being used in a tail recursive way.
[<TailCall>]
let rec fib a b = seq {
yield a
if true then
yield! fib b (a + b)
}
let fibonacci = fib 0 1
Related information
Provide any related information (optional):
- Pop!_OS 22.04
- VS Code: 1.102.2
- TargetFramework: net9.0
This issue might be related to #16477, which is fixed and closed.
As with #16477, if I reverse the if test, I don't get the warning. So, the following code gives the warning:
[<TailCall>]
let rec fib a b = seq {
yield a
if true then
yield! fib b (a + b)
}
But this code does not give the warning.
[<TailCall>]
let rec fib a b = seq {
yield a
if false then () else
yield! fib b (a + b)
}
Also, as with #16477, this example only happens with a Debug build.
However, my actual code is slightly more complicated and still gives warnings in a Release build. The code compares two sorted arrays using a compare function.
Because I can't apply the [<TailCall>] attribute to a nested function (attributes on nested functions are not supported), I have the recursive function inside a separate type.
type Diff<'a,'b> =
| A of 'a
| B of 'b
| AB of 'a * 'b
module SortedArray =
type private CompareWith<'a,'b> (compare, itemsA: array<'a>, itemsB: array<'b>) =
let countA = Array.length itemsA
let countB = Array.length itemsB
[<TailCall>]
let rec loop a b =
seq {
if a < countA && b < countB then
let itemA = itemsA[a]
let itemB = itemsB[b]
let test = compare itemA itemB
if test < 0 then
yield A itemA
yield! loop (a + 1) b
elif test > 0 then
yield B itemB
yield! loop a (b + 1)
else
yield AB (itemA, itemB)
yield! loop (a + 1) (b + 1) // no warning for this one
elif a < countA then
yield A itemsA[a]
yield! loop (a + 1) b
elif b < countB then
yield B itemsB[b]
yield! loop a (b + 1)
}
member _.Exec () = loop 0 0
let compareWith compare itemsA itemsB = CompareWith(compare, itemsA, itemsB).Exec()
When I compile, I get warnings for 4 of the yield! loop calls, but not for the one in the else branch. I get these warnings for both Debug and Release.
If I change each of those yield! loop calls into if false then () else yield! loop, the warnings are not shown with a Debug build, but they still appear with a Release build.
The following version does not produce warnings in either Debug or Release:
module SortedArray =
type private CompareWith<'a,'b> (compare, itemsA: array<'a>, itemsB: array<'b>) =
let countA = Array.length itemsA
let countB = Array.length itemsB
[<TailCall>]
let rec loop a b =
seq {
match a < countA, b < countB with
| true, true ->
let itemA = itemsA[a]
let itemB = itemsB[b]
let test = compare itemA itemB
if test < 0 then
yield A itemA
yield! loop (a + 1) b
elif test > 0 then
yield B itemB
yield! loop a (b + 1)
else
yield AB (itemA, itemB)
yield! loop (a + 1) (b + 1)
| true, false ->
yield A itemsA[a]
yield! loop (a + 1) b
| false, true ->
yield B itemsB[b]
yield! loop a (b + 1)
| false, false -> ()
}
member _.Exec () = loop 0 0
let compareWith compare itemsA itemsB = CompareWith(compare, itemsA, itemsB).Exec()
So this is a workaround for this case for me. But I have other cases that give false warnings, which are a bit harder to reduce to something concise I can show here.
Here is another case. This is cut down from the actual code, so in this form it does nothing useful and is only a test case for the compiler.
module TailCall =
type State =
| Text
| Backslash
| Ampersand
type Expand (chars: seq<char>) =
let en = chars.GetEnumerator ()
[<TailCall>]
let rec loop _state =
let gobble ch =
seq {
match ch with
| '\\' -> yield! loop Backslash
| '&' -> yield! loop Ampersand
| _ ->
yield ch
yield! loop Text
}
seq {
if en.MoveNext () then
yield! gobble en.Current
}
In either a Debug or Release build, all 3 yield! loop calls in the gobble function produce the warning:
warning FS3569: The member or function 'loop' has the 'TailCallAttribute' attribute, but is not being used in a tail recursive way.
This one is a bit more involved. As before, this is reduced from the actual code, but serves as a test case for the compiler.
type SimpleLazy<'t> (getValue: unit -> 't) =
let mutable getValue = ValueSome getValue
let mutable value = Unchecked.defaultof<'t>
[<DebuggerBrowsable(DebuggerBrowsableState.Never)>]
member _.Value =
match getValue with
| ValueNone -> value
| ValueSome f ->
value <- f ()
getValue <- ValueNone
value
member _.IsValueCreated = getValue.IsNone
module TailCall =
[<NoEquality; NoComparison>]
type LazyList<'t> =
| LazyCons of 't * SimpleLazy<LazyList<'t>>
| LazyEmpty
type Example<'t> (source: seq<'t>) =
let en = source.GetEnumerator ()
[<TailCall>]
let rec loop () =
if en.MoveNext () then
LazyCons (en.Current, SimpleLazy loop) // warning FS3569 here
else
en.Dispose ()
LazyEmpty
In this case, I get the warning at the line commented above, but only in a Release build.
I assume [<TailCall>] works according to the RFC-1011 spec, which says:
All uses of an attributed function within its recursive scope would need to be in tail position. Thus passing the function as a higher-order argument would not be allowed. This can potentially limit the utility of such a function.
Is SimpleLazy loop an example of passing the function as a higher-order argument, even though SimpleLazy just stores the function for later use?
Is
SimpleLazy loopan example of passing the function as a higher-order argument, even thoughSimpleLazyjust stores the function for later use?
Well it is passed to the constructor. The function is not really recursive at all, as it is not calling itself.
Here is a much simpler version of the SimpleLazy code, which shows the problem with a Debug or Release build.
module TailCall =
type Wrapper (create: unit -> Wrapper) =
member _.Create = create
[<TailCall>]
let rec loop () =
Wrapper loop // warning FS3569 here
But this alternative version does not give the warning:
module TailCall =
type Wrapper = Wrapper of (unit -> Wrapper)
[<TailCall>]
let rec loop () =
Wrapper loop // no warning
In the first example, the constructor might contain code that does things other than simply storing the function, whereas in the second example, this is not possible. But still, I don't understand why this isn't tail recursive.
@dawedawe are you the expert in this area?
Above, I've provided 3 examples of when the [<TailCall>] attribute incorrectly (as I see it) warns that the function is not tail-recursive.
I suspect that since most recursive functions are nested functions, and the [<TailCall>] attribute can't be applied to a nested function, people are therefore not using the attribute, so bugs are not found and reported. This is just my hunch.
It occurred to me to use a private type to work around this limitation, and now that I am doing so, I am discovering these bugs.
As I still feel responsible for the code, I'll look into it. But for good reasons it's unlikely to happen soon.
Here's another case for you.
type Example () =
[<TailCall>]
let rec getZero i =
match i with
| 0 -> 0
| i -> getZero (i - 1)
[<TailCall>]
let rec loop x =
if x < 0 then
loop -x
else
let zero = getZero 123 // warning FS3569 here
let one = zero + 1
one
According to the RFC-1011 spec:
All uses of an attributed function within its recursive scope would need to be in tail position.
But the getZero call is not within its recursive scope. It is within the recursive scope of a different function. If you remove the [<TailCall>] attribute from the loop function, the warning goes away.
Interestingly, I don't get the warning if this is a module, rather than a type.
module Example =
[<TailCall>]
let rec getZero i =
match i with
| 0 -> 0
| i -> getZero (i - 1)
[<TailCall>]
let rec loop x =
if x < 0 then
loop -x
else
let zero = getZero 123 // no warning
let one = zero + 1
one
Here is another case. This is cut down from the actual code, so in this form it does nothing useful and is only a test case for the compiler.
module TailCall = type State = | Text | Backslash | Ampersand type Expand (chars: seq<char>) = let en = chars.GetEnumerator () [<TailCall>] let rec loop _state = let gobble ch = seq { match ch with | '\\' -> yield! loop Backslash | '&' -> yield! loop Ampersand | _ -> yield ch yield! loop Text } seq { if en.MoveNext () then yield! gobble en.Current }In either a Debug or Release build, all 3
yield! loopcalls in thegobblefunction produce the warning:warning FS3569: The member or function 'loop' has the 'TailCallAttribute' attribute, but is not being used in a tail recursive way.
Restructuring the code as follows, avoids the tail call warning in both Debug and Release builds:
module TailCall =
type State =
| Text
| Backslash
| Ampersand
type Expand (chars: seq<char>) =
let en = chars.GetEnumerator ()
[<TailCall>]
let rec loop _state =
seq {
if en.MoveNext () then
yield! gobble en.Current
}
and [<TailCall>] gobble ch =
seq {
match ch with
| '\\' -> yield! loop Backslash
| '&' -> yield! loop Ampersand
| _ ->
yield ch
yield! loop Text
}