[RFC FS-1011 Discussion] Warn when recursive function is not tail-recursive

[neoeinstein]

This is the discussion thread for "under review" RFC Warn when recursive function is not tail-recursive

[wallymathieu]

I think it could be useful to get a "warning" of level 4 when recursive functions are not tail-recursive. It's not such a big issue (in normal business code), but it could potentially get you into trouble. However, if you have marked a method as "tailcall" then it sounds like a compiler error?

[wallymathieu]

That is, perhaps having an information level warning about non tail recursive function in general?

[TheInnerLight]

If this going to be done via an attribute then it absolutely should be a compiler error, not just a warning. I can't see any circumstance where it would be advantageous to tag a function with effectively a tail call suggestion.

A compiler error would be useful when working on your own projects because it allows you to impose useful constraints but it becomes, in my opinion, an absolute necessity when library code is considered.

Imagine working with a library and seeing [<TailCall>] attached to a function. You could be forgiven for assuming that function would be tail recursive. If the library author ignored the warning and published the code anyway, the attribute would suddenly become actively harmful because it now provides misinformation.

If, by contrast, [<TailCall>] generated a compiler error when the function it is attached to is not tail recursive, you would only ever see that attribute attached to functions where that optimisation was successfully applied.

I would also add that I think that adding 'suggestions' that aren't applied at the cost of preventing compilation seems very much at odds with the spirit of type-safe functional programming which is all about compile-time guarantees.

[wallymathieu]

Yes. That would make more sense @TheInnerLight . It would break existing code though. Could you mark an assembly in some way to get the extra type safety?

[jack-pappas]

I realized today that the solution I had in mind (which I've detailed a little before, but not well enough) is specifically geared towards warning on non-tail-recursive calls, rather than the more-general case of detecting non-tail-calls. Anyway, here's what I have in mind for the non-tail-recursive call detection:

If we can build up a call graph, or rather, a call multigraph, where edges are labeled by some information identifying a specific call site (and nodes are methods/functions), we can use something like Johnson's algorithm to identify all of the simple cycles -- each cycle will represent some chain of recursive calls (which could be as simple as a function calling itself).

Any call sites which aren't part of a cycle can immediately be dropped from consideration; they may warrant further analysis to see if they should/could be made tail calls, but for the purposes of detecting recursion they're irrelevant. Any call sites where we've detected a cycle should be tail calls -- if they're not, we'll issue a warning (since there could be unbounded recursion which ends up overflowing the stack). I think this simple analysis could be a useful start to this analyzer, as it would detect the most obviously-wrong cases that may trip up inexperienced F# developers.

The analysis could be extended and refined too, by doing some static analysis to detect cycles in the call graph where e.g., some higher-order function accepts a function-typed parameter and calls it; if we consider (for the analysis) functions which are passed into that parameter, we can be pessimistic and warn the user when there's a possibility the call site could lead to unbounded recursion (assuming the higher-order function isn't public; if it is, we have to switch to being optimistic since we can't know everything that could be passed in).

Note that the analysis I described doesn't require any additional keywords or attributes, it can be implemented for today's F# code.

[KevinRansom]

@jack-pappas

I think in general a way of identifying non-tail calls is interesting, but at best it's a hint to the developer that we may be able to tail call since we don't have access to the information that the Jit has we won't be able to guarantee that the call will treated as tail-recursive by the Jit.

What's more, support for tailcall optimizations and the .tail opcodes are not required in a cli compatible runtime project N for example still doesn't support F# style TCO.

I am in favor of warning that for let rec foo = .... we are sure the code won't be tailcall optimized, however, a separate keyword seems really iffy given how vague the promise that TCO will happen anyway.

I don't have a large care factor whether it is directly in the compiler or as an analyzer. However it should be noted that as an Analyzer we can build much nicer IDE experiences around it, and make enabling it and disabling it much simpler. If it is in the compiler then it will be emitted every let rec that isn't possible to TCO and that will get old fast and likely be an automatic disable on most projects.

Warning levels is a possible enabling mechanism in the compiler, however it's not really clear that we have done a good job of being systematic about warning levels. Developers seem to select one of two options "the default --- whatever the system gives you for warning levels if you do nothing" or "the highest --- if they think they gain some benefit from it"

Attributes may be interesting if the IDE does a Clippy and says "I notice that you have used

let rec foo = blah

Should it require TCO?, then the IDE can mark it correctly as you type it ... or something

Anyway my 2 cents and worth everything you paid ....

Kevin

[KevinRansom]

This is the design thread in fslang-design for

[RFC FS-1011 Discussion] Warn when recursive function is not tail-recursive

Okay there is a huge and interesting thread over here: dotnet/fsharp#1976 (comment)

A little mention for everyone who participated so they get to see this design thread.

@AviAvni, @abelbraaksma, @vasily-kirichenko, @forki, @thinkbeforecoding, @vladima, @theimowski, @TeaDrivenDev, @OnurGumus, @OnurGumus, @0x53A, @isaacabraham, @matthid, @ncave, @rojepp, @jack-pappas @dsyme @cartermp

Thanks

Kevin

[matthid]

Just to add to the discussion. I feel like when adding this attribute no matter if we emit a warning or an error the compiler should tell me WHY it is not considered tail recursive. For example I've just seen some code here where apparently the code was not tail recursive and after some magic change (removing a parameter) it worked.

In other words: If I add the attribute to the linked code-fragment I expect the compiler to tell me why this would not work (might be a good test-case if this was by design) and not just fail with a generic error message (even if that would be already progress).

[Happypig375]

I'd like to add that for mutual tail recursion, a simple attribute of [<TailRec>] would have ambiguities.

type TailRec() = inherit System.Attribute()
let rec [<TailRec>] a x =
    if x = 0 then 0
    else
        printfn "${x}"
        a (x-1) // Direct optimisation into a loop
let rec [<TailRec>] b x =
    if x < 10 then a x // No tail. instruction here and not a tail call
    elif x < 100 then b (x/2) // Direct optimisation into a loop, is a tail call
    else c (x/2) // tail. instruction here, is a tail call
and [<TailRec>] c x =
    if x < 10 then a x // No tail. instruction here and not a tail call
    elif x < 100 then c (x/2) // Direct optimisation into a loop, is a tail call
    else b (x/3) // tail. instruction here, is a tail call

What will [<TailRec>] mean for each function? Will a x case in both b and c be warned or will mutual recusion not be checked by [<TailRec>]? This is what happens when we use attribute level [<TailRec>]. Instead, if we annotated the reserved tailrec keyword at the call site, everything becomes obvious.

let rec a x =
    if x = 0 then 0
    else
        printfn "${x}"
        tailrec a (x-1) // Verified: Direct optimisation into a loop
let rec b x =
    if x < 10 then a x
    elif x < 100 then tailrec b (x/2) // Verified: Direct optimisation into a loop
    else tailrec c (x/2) // Verified: tail. instruction here
and c x =
    if x < 10 then a x
    elif x < 100 then tailrec c (x/2) // Verified: Direct optimisation into a loop
    else tailrec b (x/3) // Verified: tail. instruction here

Can we still modify the design to allow call site tagging?

[vzarytovskii]

I personally would rather much prefer compiler figuring out when recursive or mutually recursive function is getting called, and (info-)warn if it's not tail recursive. Without user having to do anything.

[vzarytovskii]

I mean I guess one downside, that without a hint, the analysis can be quite expensive, if the recursion is deeply nested between multiple mutually recursive functions? And another is it might be confusing for users who intend a non-tail-recursive recursive call, will get a warning.

[dsyme]

@Happypig375 You are correct that, in the limit, callsite attribution is required if you really want to markup all places where you want tail calling to be checked. That said, the general plan was simply not to aim this high - but rather be able to attribute functions at their declaration site.

I don't think the current design is umbiguous: if you add the attribute, it means all calls to the function within its recursive scope must be in tailcall position (including any recursive scope via type scope, or module rec or namespace rec) . I do agree the current design "isn't enough" in some circumstances - both too limited, and too blunt.

@vzarytovskii Note this is about verification of tail calling. The compiler can't tell whether the user intends tail-recursion and wants it verified. There are many situations where you need non-tail-recursive calls, e.g. consider this:

type Tree = Tree of Tree list

​let rec depth (Tree(nodes)) =
    nodes |> List.sumBy depth // non-tail-recursive

Either

1. call sites have to opt-in to saying "this must be a tailcall" or
2. definition sites must declare "this must always be tailcalled within its recursive scope".

The compiler can detect what is/isn't a tailcall. However there's no way to determine intent - that is, to determine callsites that are "meant" to be tail-calls (but aren't), not functions that are "meant" to always be called in a tail-recursive way in their recursive scope (but aren't). We need some declaration of intent.

Happypig is right that in the limit is to allow this attribution to

[vzarytovskii]

Yeah, I guess there are more such cases than I initially thought of.

[dsyme]

Revisiting this design, there are two choices to express intent:

A. call sites declare "this must be a tailcall" or
B. definition sites declare "this thing must always be tailcalled within its recursive scope".

Do people think (A) or (B) is better?

🚀Pro/cons for A (callsite attribution):

• Pro: more complete - captures all scenarios
• Con: feels less declarative
• Con: you forget to add the attribute, nothing happens, no warning, no error 🤷
• Pro: obviously related to implementation
• Pro: can apply to indirect calls (e.g. calls to a function parameter value f)

🎉 Pro/cons for B (defintion-site attribute):

• Pro: only one declaration is needed.
• Con: it doesn't (and can't) capture all intent, e.g. for code where some of the recursive calls are legitimately non-tail-recursive (common in the F# compiler or any recursion over syntax trees)
• Con: I think people look at the attribute and think it means "all callers in all situations must call the thing using a tail call". This isn't true - it means only callers in the recursive scope have to do this
• Con: These days the recursive scope can be enormous by using namespace rec or module rec or type with large member declarations or large let rec. This means it's basically impossible to express tailcall intent in such code

Please give comments below and/or react 🚀 for A (attribute callsites with tailcall) and 🎉 for B (attribute definitions with [<TailRec>])

[vzarytovskii]

@vzarytovskii "call site" is mentioned. It's something like

let rec tailRecusrive x =
    if x = 0 then printfn "a" else rec tailRecursive (x-1) // Note "rec" here

Ah I see. Use of the rec kw on the callsite. Interesting.

[dsyme]

@theprash @vzarytovskii @nojaf @Happypig375 @dawedawe Please check your votes, the icons were mixed up

[Lanayx]

I've voted for [<TailRec>], however it feels that it will be cleaner to add new keyword tailrec in place of rec:

let tailrec f x = f (x +1)

[Happypig375]

@dsyme what are the concerns against having both?

[Happypig375]

A design for having both:
Callsite attribution overrides declaration site attribution.

let rec [<TailRec>] a x = // Should be tail called
    if x = 0 then 0
    else
        printfn "${x}"
        a (x-1) // Checked because of attribute
let rec [<TailRec>] b x = // Should be tail called
    if x < 10 then tailrec a x // Both keyword and attribute are allowed
    elif x < 100 then b (x/2) + 1 // Warn - checked because of attribute
    else not tailrec c (x/2) // Warn - this is a tail call
and c x = // No attribute
    if x < 10 then not tailrec a x // Warn - this is a tail call
    elif x < 100 then c (x/2) + 1 // Not checked
    else not tailrec b (x/3) + 1 // Keyword overrides attribute here

[dawedawe]

@dsyme I'm afraid there's a mixup in the icons. The pro/cons icon usage is different from the last sentence.

[dsyme]

Fixed, thanks!

[dawedawe]

I guess, as some of the stack overflows are prevented by the rewrites done by the optimizer, we need to decide how to handle that, too.

From the top of my head, I see two options:

1. Try to antecepate what the Optimizer does and depending on that, only warn in Debug builds if needed.
   (Not sure, how the chances are, to get this right. Maybe implementing the warnings in the Optimizer itself is a reasonable approach, I'm looking into that.)
2. Error on the side of caution and always warn, regardless of Debug or Release

Does this line of thought make sense?
Do you see other options?

[dawedawe]

For people interested in this topic, this might be an interesting issue:
dotnet/runtime#87393

[dawedawe]

I guess, as some of the stack overflows are prevented by the rewrites done by the optimizer, we need to decide how to handle that, too.

From the top of my head, I see two options:

1. Try to antecepate what the Optimizer does and depending on that, only warn in Debug builds if needed.
   (Not sure, how the chances are, to get this right. Maybe implementing the warnings in the Optimizer itself is a reasonable approach, I'm looking into that.)

2. Error on the side of caution and always warn, regardless of Debug or Release

Does this line of thought make sense? Do you see other options?

dotnet/fsharp#15503 goes with a third option. Doing the analysis after the optimization.
Please give it a spin if you can.