Warning for recursive functions without tailrec annotation

Hi all,

I would like to propose to change the compiler so that it emits a warning if it finds a recursive function without a @tailrec annotation.

Recursive functions are great. They allow to solve certain problems in a very elegant way but they are also a source of relatively obscure bugs when the recursive functions are not tail-recursive. Here is a typical example:

def sum(numbers: List[Int]): Int =
  numbers match {
    case Nil          => 0
    case head :: tail => head + sum(tail)
  }

sum works perfectly well for small lists, but we get a StackOverflow exception when a list has 10 000 items or more (with default stack settings).

The solution to the problem is well known (add an accumulator) and we can easily verify the function is stack-safe at compile time using a @tailrec annotation. However, one needs to know such annotation exists and remember to use it every for every recursive function.

On the other hand, if the compiler were to emit a warning, it would very simple to transform it into an error or ignore it using the new configurable warning options.

1 Like

I would find it pretty annoying if the compiler warns about every recursive function, even if I know that it’s safe because the input is of limited depth or because I’m using a trampolining monad.

A lint or separate compiler flag for enabling such warnings might be an option though. But even then I don’t see the value of warning about tail-recursive functions that don’t have @tailrec. I would make it the inverse of the current situation: instead of marking every function the compiler has to test, the compiler would test every function and you would have to mark every function which is safe despite not being tail-recursive.

2 Likes

Note that we already have linters for that. WarRemover, for instance, has the Recursion wart for exactly that purpose.

3 Likes

Correct, at the moment, we assume the depth of the recursion is fine by default which in my opinion is a dangerous default. If you know/assume the depth of the recursion to be small, then it is probably worth to be explicit about it. For example, it will make it much easier to discuss in code reviews. And if it is a warning, then it is easy to disable it locally, globally or even turn it into an error.

I am not necessarily proposing to verify each recursive function is tail-recursive by default. The compiler would only to verify a function call itself.

Probably 99% of the recursive functions I write are not tail recursive. Obviously this will vary across how different people use the language, but I don’t think that the tradeoff is worth it overall. Programmers in every language are trained to have to pay attention to stack sizes on overflow, and if you want to enforce that a recursive function cannot stack overflow, that’s what @tailrec is for.

Furthermore, if anyone really wants this, it seems like something a compiler plugin could easily add such a warning. If there was such a warning that was popular and widely used, that would be a stronger argument for adding it to the language proper (e.g. that’s what’s happened to kind-projector) but as far as I know there isn’t.

6 Likes

IntelliJ does this. I don’t think this should be a compiler warning, since the code is valid and there is no chance of confusion (only where I would expect a warning). This is where IDEs can help best.

1 Like

Programmers in every language are trained to have to pay attention to stack sizes on overflow, and if you want to enforce that a recursive function cannot stack overflow, that’s what @tailrec is for.

@lihaoyi I think that’s a problem. From my experience, both as a developer and as a teacher, very few people are aware of the StackOverflow issue or are able to recognise a tail-recursive implementation. And I don’t blame them, I believe it is really tricky issue, especially since recursions are not taught as well as imperative approaches.

@soronpo Warnings are exactly for this scenario: valid code that is likely to cause an issue. Furthermore, we can locally or globally configure warnings in Scala (out of the box since 2.13.2 I believe).

1 Like

:+1::+1:

Great idea. We can address @lihaoyi’s concern by turning it off by default (like most other warnings). Then sbt-tpolecat (not my project, despite the name) can enable it and those of us who like lots of warnings will enjoy having it.

5 Likes

We can easily reach stackoverflow issues with various non-tailrecursive codes. A tail recursive option seems to me to be too singular for the effort to warn about in the compiler, where again, the IDE can do this much nicer and better.

1 Like

Many warnings detect only specific cases of things. This is fine. Every little bit helps. How could there possibly be any harm in an optional warning? If you don’t like it, don’t turn it on.

Also if it’s in the compiler everyone benefits, not just IntelliJ users.

2 Likes

This seems like a great idea :+1:

FWIW I feel a little bad for co-opting your username for the project, but your blog posts about scalac options were great. :sweat_smile: Let me know if you’d like me to change it.

I really like this idea, but I think to make it usable with warnings as errors you will need something like @scala.annotation.shallowrec or something to silence warnings for cases (e.g. trees) where recursion is okay because it is log depth in the size of the structure.

some ideas:

@recursive
@nontailrec 
@shallowrec
1 Like

You can already use the @nowarn annotation to disable a warning locally, which could be used for the cases you mentioned.

I like it. If warnings were printed with a pointer to the @nowarn attribute, that would be a better dev experience too. E.g.,

error: could not optimize @tailrec annotated method len: it contains a recursive call not in tail position
See also https://www.scala-lang.org/api/current/scala/annotation/nowarn.html

The error message for tailrec should be changed to:

Did you mean @nowarn(msg="not in tail position")?

I hope they figure out how to make @tailrec and @nowarn available without import annotation._. That is, -Yimports:scala.annotation.

And also demote tailrec to a warning.

When JetBrains’ IntelliJ IDEA finds a tail recursive function it embellishes the gutter with an icon that points that out. Similarly for a recursive function that is not tail recursive. In the former case, it also suggests adding the tailrec annotation. See screenshots below:

Try it out on this code.

2 Likes

I also think there should be a way of silencing it, but (minor digression) I don’t think it has anything to do with “warnings as errors”. Not making warnings errors does not mean that warnings are okay… A healthy codebase is not supposed to dump warnings on compilation (and this should be checked in the CI).

That seems like terrible user experience.

As mentioned by @oscar, non-tail recursion is okay in many domains, such as when designing compilers and type systems — there, non-tail recursion occur everywhere, and it would be pretty bad having to write something like @nowarn(msg="not in tail position") every time. We’d need something much more lightweight like @rec.

3 Likes

I can see value in this but I definitely would not use it, probably ever. I would very much like it to be behind it’s own compiler flag, since @nowarn isn’t really an option for people who are cross building with older versions.

But to be clear, most functions I write are not tail recursive, and I’m very intentional about that. I also write a ton of functions which are not tail recursive and still operate on unbounded data because they have other guarantees which ensure this is safe (the IO run loop in cats effect is notably not tail recursive and can’t be, but still uses tightly bounded stack space). Trivially, all lazily recursive functions are safe but not tail recursive according to the compiler, and I write these quite often.

I think having the option of this warning would be nice, but it really does need to be individually configurable, because the cases I’m describing are not rare.

4 Likes

I have discussed this some with @julien-truffaut on Twitter, but it is probably worth mentioning on this thread so it can be seen by those who care and I can explain more clearly than is possible in Tweets.

TL;DR - This change is bad for teaching novice programmers, but might be acceptable in Scala 3 if students are also using @main.

I believe that this change causes problems for teaching Scala to novice programmers, especially under Scala 2. In my CS1 course, I generally cover recursion for iteration early. By early I mean about 4 weeks into the semester and before loops or other forms of iteration. (Sample schedule for a CS1 course for anyone interested: https://sites.google.com/a/trinity.edu/csci1320-f19/.) This course can involve students who have never programmed before. All they know is types, basic expressions, conditionals, and functions. That’s enough to start doing recursion, which is why I place it there. They don’t know annotations and in Scala 2 there is no reason to introduce annotations that early. Every language feature introduced has an additional cognitive load and the goal is understanding the logic, not knowing every language feature. Any extra syntax is a detrimental overhead that I want to avoid until it is really needed. I will note that little things like taking readInt and readLine out of Predef have already added to the syntactic cognitive load early on because they force a discussion on imports or using long, fully-specific names.

If this change were made, I’d either have to introduce annotations early or tell students to simply ignore the warning. Given that I work to get students to pay attention to warnings and not ignore them, the latter is clearly not ideal.

Even describing why they need to add the annotation is problematic. Students first learning about recursion after having only been programming a few weeks are not mentally equipped to try to take on what makes a function tail-recursive or not at the same time. So this is just going to make recursion even scarier than it normally is.

Scala 3 will likely change one aspect of this. In Scala 2, we use the scripting environment to allow students to write very simple programs with no overhead. It is quite possible that the introduction of top-level declarations and @main will change how we do a lot of our coding in CS1. If we make the switch from scripts, which isn’t a given if Ammonite is integrated into the default tooling, then we might introduce annotations for that purpose and they wouldn’t be completely new when we hit recursion. In that situation, the idea of a short annotation like @rec to suppress this warning seems like a reasonable solution. There is still the challenge that they aren’t equipped to understand tail-recursion, so to start off we’d probably have them put @rec on every recursive function.

As I mentioned on Twitter, my observation is that language evolution rarely favors the education of novices. Indeed, most changes to languages over time make things more complex in a way that is detrimental to teaching novices. It makes sense that the primary target of language changes is the developers who use the language daily to create things. However, I don’t think the impact on education should be ignored. As we have seen with both Java and Python, the truly broad adoption of a programming language is fueled by adoption in colleges. If every college taught Scala in some required course, the commonly heard argument that a project can’t use Scala because they can’t find developers who know it would go away.

3 Likes

I believe it is an option. The silencer plugin recognizes @nowarn. And scala-collection-compat provides a no-op @nowarn annotation, so you’ll get warnings on 2.11 and 2.12, but you can go warning-free on 2.13. (Probably you’ll only build on 2.11 and 2.12 on CI. And it’s easy to enable -Werror only on 2.13.)

Cross-building should not, and in fact does not, make us hesitant to add new warnings to the compiler.

(I’m not stating an opinion about whether this particular new warning is a good idea.)

2 Likes