Add compiler-known attribute for enforced tail recursion

[haf]

Enforce tail-recursion with attribute

I propose we add a new attribute [<TailRecursive>], applicable to functions that:

1. Makes the compiler enforce tail-recursion, or rewrite-to-loop behaviour, or else trampoline behaviour
2. Errors if the compiler fails at proving tail recursion, e.g. when having use _ = ... statements above the supposed-to-be recursive call.
3. If the runtime doesn't support tail-recursion, like most JS engines, rewrites the function to be trampoline based

The existing way of approaching this problem in F# is to think hard about the problem every time, and when that fails, we get this stuff: Hopac/Hopac#193

Pros and Cons

The advantages of making this adjustment to F# are correctness, speed, saving memory/stack space. Also, this issue mostly only crops up under load, after chewing through a few gigabytes of memory, so it's hard to spot during development and the crashes from OOM are not always the most clear crashes. Furthermore, in prod, a fix would be to read the code well and then "fix" it in the obvious way, and then redeploy, hoping that 4 hours later, there's no crash.

The disadvantages of making this adjustment to F# are: another attribute, more compiler complexity and the trampoline may be advanced enough to warrant splitting out to another feature. Furthermore, the compiler could in the initial implementation require such functions to be private (to be able to reason about all calls to them being "full" and not curried).

Extra information

Example from Logary, that I would like to have the compiler prove for me:

[<TailRecursive>]
let rec private receiveLoop (next: Ingest) (inSocket: UdpClient) =
  job {
    let! msg = inSocket.getMessage()
    let! res = next (Ingested.ofBytes msg)
    ignore res // nothing to do; UDP is fire-and-forget
    return! receiveLoop next inSocket
  }

Estimated cost (XS, S, M, L, XL, XXL): S-M

Related suggestions: (put links to related suggestions here)

• Proper tail calls rust-lang/rfcs#1888
• guaranteed tail call elimination rust-lang/rfcs#271
• https://www.scala-lang.org/api/2.12.3/scala/annotation/tailrec.html

Affidavit (please submit!)

Please tick this by placing a cross in the box:

• This is not a question (e.g. like one you might ask on stackoverflow) and I have searched stackoverflow for discussions of this issue
• I have searched both open and closed suggestions on this site and believe this is not a duplicate
• This is not something which has obviously "already been decided" in previous versions of F#. If you're questioning a fundamental design decision that has obviously already been taken (e.g. "Make F# untyped") then please don't submit it.

Please tick all that apply:

• This is not a breaking change to the F# language design
• I or my company would be willing to help implement and/or test this — primarily by means of load testing the result with Hopac and trying to solve the Hopac bug I linked. I can't promise more engineering time than that.

[NinoFloris]

Related work https://twitter.com/matthewwarren/status/1097462499941801984?s=19

[cartermp]

See also:

• Enable a compiler-warning when a recursive algorithm is not tail-recursive [ RFC FS-1011 ] #147 and RFC for related attribute
• Trial implementation by @AviAvni: [WIP] Tail recursion warning and attribute dotnet/fsharp#1976

@haf If you're interested, I think it would be productive to flesh out the existing RFC a bit more. There were some open design questions that the trial implementation produced that you might also want to consider.

Also tagging as fable-inspired to capture that is different behavior involved when JS is the runtime.

[knocte]

It would be great if this could be tweaked to be able to be forced at the assembly level (e.g. via compiler flag), not only at method level via attribute.

[BentTranberg]

Usually I want functions that are totally tail recursive, but sometimes in some branch I accept a non-tail recursive call because I know that the particular branch will only be called one or a few times. Using an attribute on the function level won't cover this case.

[bigjonroberts]

Would/should this be extensible to cover Adyncseq and Taskseq ?

[edgarfgp]

Was wondering that now that we have the [<TailRecursive>] attribute in the compiler, can this suggestion be closed ? Cc @vzarytovskii

[vzarytovskii]

Was wondering that now that we have the [<TailRecursive>] attribute in the compiler, can this suggestion be closed ? Cc @vzarytovskii

Yeah, I think so. Any additional requests should come via separate issues, thanks.

[jwosty]

For future readers, here's the current RFC location: https://github.com/fsharp/fslang-design/blob/main/FSharp-8.0/FS-1011-warn-on-recursive-without-tail-call.md

And the accepted implementation: dotnet/fsharp#15503