I suggest we ...

Enable a compiler-warning when a recursive algorithm is not tail-recursive

Add an TailRecursiveAttribute to enable a compiler-warning when a recursive algorithm is not tail-recursive. This should ideally also cover recursive seq { .. } and async { ... } expressions.

311 votes
Vote
Sign in
Check!
(thinking…)
Reset
or sign in with
  • facebook
  • google
    Password icon
    I agree to the terms of service
    Signed in as (Sign out)
    You have left! (?) (thinking…)
    knocteknocte shared this idea  ·   ·  Admin →

    I am generally in favour of addressing this in F# 4.x+. I would want seq { .. } and async { … } tailcalls to also be addressed.

    A more detailed design is needed and some trialling would be great. Jack’s work is a great start. However, this is not an easy piece of work to do in a non-invasive way and my own experiments in this area have not yet led to something I feel confident to include in the F# language design.

    An implementation and testing would need to be provided by someone in the F# community (possibly including Microsoft or Microsoft Research, though not limited to them).

    Currently, initial implementations of approved language design can be submitted as pull requests to the appropriate branch of https://github.com/Microsoft/visualfsharp. See http://fsharp.github.io/2014/06/18/fsharp-contributions.html for info on how to contribute to the F# language/core library design

    I encourage you to consider continue working towards a detailed proposal and a proposed implementation. I will gladly help.

    Don Syme, F# Language and Core Library Evolution

    23 comments

    Sign in
    Check!
    (thinking…)
    Reset
    or sign in with
    • facebook
    • google
      Password icon
      I agree to the terms of service
      Signed in as (Sign out)
      Submitting...
      • Yemi BeduYemi Bedu commented  · 

        Hello,
        So the example of add with embedded rebalance seems to be implemented as such just direct from an algorithm (add rebalanced sub trees). That would not be the same to say that anyone would *not* want a tail recursive version (if possible). Since you can not no in advance whether l or r is heavy, you sacrifice time loss with memory foot print and readability.

        So what would be of interest are examples yay or nay for constructing a tail recursive function. As well, an inspiration from other languages about implementation. I prefer an on by default warning.

        https://groups.google.com/forum/#!topic/javaposse/j8NioEUaCuc mentions Scala using annotations to help emit errors. http://www.scala-lang.org/api/current/scala/annotation/tailrec.html

        I like that because if I add that kind of attribute, I must really want such a property of my function. The local attribute would possibly focus static analysis too. A default warning would be nice for the rest of my code. that could help with faster feedback from tooling.

        So when someone comes across the warning, what will be the hint to fix it? Should it be recommended to look for folding or other deliberate loop constructs? Do we mention that it lacks the general semantics? Thank you. Good day.

      • AnonymousAnonymous commented  · 

        It is really "#1 must be" all this recursive stuff got failed on a big data if not optimized, but some times it is nontrivial to check is it ok or not.

      • exercitus virexercitus vir commented  · 

        I second the the idea of always issuing a warning. You can always disable it with an in-place compiler directive if you really don't require tail-recursion.

      • James HugardJames Hugard commented  · 

        I'm in agreement with Jack Pappas: use neither a keyword nor attribute; simply always issue a warning. In other words, relax the feature request to be:

        "F# compiler emits a warning at each non-tail recursive call site where a function is calling itself or some other function defined within a group of mutually-recursive functions."

        It is obviously bad practice, in general, to make non-tail calls to oneself or one's siblings due to the potential of a stack overflow. Therefore, such usage should be strongly discouraged by default and not only when a specific keyword modifier or attribute is supplied. Doubly so because beginners are more likely to make mistakes here and not even know to use a modifier or attribute as a compiler assist.

        For cases where one accepts the risks, the warning could easily be disabled.

        The documentation for that warning, though, would probably run to the long side; e.g., explaining how one could make the code tailcall friendly.

      • Eriawan KusumawardhonoEriawan Kusumawardhono commented  · 

        I agree to use the attribute. This will give different meaning and also context is more verbose than keyword.
        This will also minimize confusion whether a rec function is actually tailcall optimized or not.

      • Alfonso Garcia-CaroAlfonso Garcia-Caro commented  · 

        I would be in favour of using the keyword, the attribute looks much more verbose...

      • Eriawan KusumawardhonoEriawan Kusumawardhono commented  · 

        This tailcall CLR and recursive implementation should be transparent to the language, especially F#.
        Meaning that not only adding keywords or IDE realtime warning, but also should be available in other languages other than F# as well to use if there's a need to optimize recursive function calls.
        I vote +2 for this!

      • Don SymeDon Syme commented  · 

        I am generally in favour of addressing this in F# 4.0. I would want seq { .. } and async { ... } tailcalls to also be addressed.

        A more detailed design is needed and some trialling would be great. Jack's work is a great start.

        An implementation and testing would need to be provided by someone in the F# community (possibly including Microsoft or Microsoft Research, though not limited to them).Currently, initial implementations of approved language design can be submitted as pull requests to the "fsharp4" branch of https://visualfsharp.codeplex.com/SourceControl/latest.

        I encourage you to consider continue working towards a detailed proposal and a propopsed implementation. I will gladly help.

        I would tend towards using an attribute rather than a keyword, despite the fact that "tailcall" is reserved, simply because that is how things like this are generally added to the F# language since F# 2.0.

        [<TailCall>]
        let rec f x = .... f (x-1)

        [<TailCall>]
        let rec f x = .seq { ... yield! f (x-1) }

        [<TailCall>]
        let rec g x = .async { ... return g (x-1) }

        With regard to Jon's question - the checking would be much as described by Jack - i.e. only w.r.t. the control flow contructs that are syntactically present in the F# expression language (and hot combinator encodings of these).

        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 limts the utility of the method of course but it still remains useful, especially for beginners and teaching purposes.

      • bleis-tiftbleis-tift commented  · 

        F# has tailcall keyword as reserved-ident-keyword.
        So I think that the keyword is better than tailrec.

      • knocteknocte commented  · 

        @Jack: awesome work!

      • Jack PappasJack Pappas commented  · 

        I put together a little code sample demonstrating my proposal (see previous comment): https://gist.github.com/jack-pappas/9860949

        To elaborate a bit: the compiler would emit a warning at each call site to a function which shares the same stack frame as the current function -- in other words, when a function is calling itself, or some other function within a group of mutually-recursive functions.

      • Jack PappasJack Pappas commented  · 

        Requiring the compiler to warn you when an entire algorithm is not tail-recursive poses a significant challenge, as Jon and others have pointed out.

        If you relax the definition of this feature request to something like "emit a compiler warning for non-tail-recursive call sites within a 'rec' function", this becomes fairly simple to implement. In addition, you don't need additional keywords or functions to implement this -- it could be a standard compiler warning which is on by default, which means it'd be easy to turn off for those who wanted to do so.

      • Mastr MasticMastr Mastic commented  · 

        I agree with Philip on the keyword, it seems much more cleaner than an attribute.

      • Mastr MasticMastr Mastic commented  · 

        @Andrew Khmylov I cannot agree because imo `rec` is not for the compiler, it is for us, and to me very necessary.
        For instance when you re-bind a symbol for a function, to a function that uses it, how would you express yourself without using `rec` if you intend to call the previous binding or the new (recursive) one?

      • knocteknocte commented  · 

        @Philip, aha I understand. But I think if such keyword is proposed, I think it would be better if it's for opting-out the warning than opting-in.

      • Jon HarropJon Harrop commented  · 

        How would we handle mutual recursion or recursion via a function that was passed in?

        For example:

        let rec even n =
        odd(n-1)
        and odd n =
        even(n-1)

        or:

        let evenOne odd n = odd(n-1)
        let oddOne even n = even(n-1)
        let rec even n = evenOne (oddOne even) n

        Could we put this attribute on an entire module to check that all loops within the module require bounded stack space?

      • Jon HarropJon Harrop commented  · 

        @Andrew: "I think the compiler is smart enough"

        Consider:

        let f n = n+1
        let f n = f(n-1)

        is the latter definition of "f" recursive? Obviously it is impossible to tell. Hence the existence of the "rec" keyword.

        The alternative is to make everything recursive but then you must pollute your namespaces with, for example, "f1" and "f2" because you cannot supercede previous definitions.

      • Andrew KhmylovAndrew Khmylov commented  · 

        Philip, introducing another `tailrec` keyword doesn't sound like a good idea. It would make the code a lot more verbose IMO. I would rather get rid of `rec` keyword at all. I think the compiler is smart enough to figure out that the function is actually recursive, why should I type it myself?

      ← Previous 1

      F# Language

      Feedback and Knowledge Base