Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Add compiler-known attribute for enforced tail recursion #721

Open
haf opened this Issue Feb 17, 2019 · 3 comments

Comments

Projects
None yet
4 participants
@haf
Copy link

haf commented Feb 17, 2019

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)

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

This comment has been minimized.

@cartermp

This comment has been minimized.

Copy link
Member

cartermp commented Feb 18, 2019

See also:

@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

This comment has been minimized.

Copy link

knocte commented Feb 18, 2019

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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.