Consider this naïve implementation of the Ackermann-Péter function:
tailrec fun a( m: Int, n: Int ): Int =
if( m < 1 ) n + 1
else if( n < 1 ) a( m - 1, 1 )
else a( m - 1, a( m, n - 1 ))
Why do I need to declare tailrec? The compiler should easily be able to detect the calls it where it can reuse the current stack frame, instead of extending it. And this independently of whether a function calls itself or another one (possibly with a multi-hop tail recursion, which this keyword is not even capable of).
Why do I need to declare return type : Int? Only one branch terminates non-recursively. So only that one can determine the return type. Instead the compiler goes into a recursion problem.
This fulfills the documented requirement a function must call itself as the last operation it performs. It doesn’t say must only ever call itself…, and there wouldn’t seem to be a need for such a restriction. Yet it warns about the nested call: Recursive call is not a tail call
Implicit tailrec optimization is very fragile and error-prone. People make mistakes and tailrec modifier is here to explicitly declare programmer’s intent to define a tailrec function. You (as a programmer) declare your intent and compiler verifies it. It also serves as a helpful piece of documentation for future readers and maintainers of your code. If they accidentally break it, they’ll get caught by compiler.
Kotlin’s type inference is deliberately limited to allow for fast compilation. You have to declare types in Kotlin in some cases where it could have figured out type with a more complicated type inference implementation, but the more complicated implementation would have considerably slowed down compilation. That is a conscious tradeoff.
“Recursive call is not a tail call” is just a warning to protect programmers from making a common mistake of thinking they have a tail call, but messing something up in their code, so this is not an actual tail call. This error is hard to catch otherwise, especially in functions like Ackermann’s, where there is no chance you’ll ever catch the actual absence of tail call optimizing by performing any kind of unit test.
The common pattern for tailrec functions is to always make a recursive tail call. In the rare cases, like the Ackermann function, you want to have some non-tail calls, too. Press “Alt+ENTER” on this warning and choose a quick-fix to suppress this warning for this particular function. That serves as your (programmer’s) confirmation to compiler and future readers that you’ve intended it to be this way.
Most C/C++ compilers have successfully done tail call optimization for years, and have been covering more edge cases over time. But of course those are fragile niche languages, which can’t compete with Kotlin The optimizations are all safe, except for some aggressive ones to cheat in benchmarks – not speaking of core dumps, which have other reasons.
It’s merely an optimization, which (apart from allowing far deeper “recursion” and allowing to implement state machines where the transitions are tail function calls – impossible in Kotlin currently without other-function call optimization) is completely transparent semantically. So it has no business to be mentioned in the code!
What in the world would be lost by checking if a function verifiably called last (with no closures remaining open, etc.) could be jumped to instead?
What in the world would be lost by checking if a function verifiably called last (with no closures remaining open, etc.) could be jumped to instead?
Nothing is lost. Declare your intent with tailrec and it will be. I think that I’ve provided a pretty detailed explanation on why this declaration of intent is needed for safer and more readable code. Sorry, but there is nothing more I can help you with.
I’m not sure what to think of the JVM (never having been a Java fanboy, I don’t know it). Some seem to suggest it’s possible, while others say it can’t be done, because goto only works inside one function Do they still think it’s a Java-only platform? And even Java would profit, if they did it after virtual function lookup…
Here’s a simple example of a state machine that (potentially endlessly) tail calls other functions: Programming in Lua : 6.3
You don’t explain. You just claim that it’s fragile and error-prone – quite an assertion in the face of various languages and compilers that just DTRT succesfully.
Then you go on to say that of all the possible optimizations that the compiler can perform behind the scenes, this one should be made explicit via a hinting key word in the source code.
I thought Kotlin was supposed to be elegant, but you want to make it artificially cumbersome.
But you’re right, people do make mistakes and will forget that stupid keyword. Then the program will run fine with some test data, but explode the stack with real life data, once it’s loaded to production
I used to find it irritating in C# to be forced to declare override, but the first time I removed an overridden method from the base class and got surprising behaviour, I understood why it was a good thing. We’ve changed our C++ coding guidelines to require that, too - to help us avoid mistakes. I think requiring an explicit tailrec is a good idea for the same reason.
Kotlin is elegant because it capture’s programmer intent succinctly, not because it guesses programmer intent.
One of the problems with Java and C# is a lack of transparency – it’s often hard to tell if a section of code will actually be performant or not because of the JITing behavior of the JVM. Escape analysis and method inlining (among numerous other JIT optimizations), while good for performance, make it hard to reason about what the program is actually going to do at runtime.
Admittedly, since Kotlin runs on the JVM, we still have that problem, but we’re given additional tools to add some determinism. inline, for instance, forces that method to be inlined at compile time, instead of hoping it’ll be inlined at runtime. That’s quite nice. It’s more verbose, but enables the developer to specify exactly what they want. And it’s just one keyword. tailrec is another.
The problem with tail recursive calls is that it’s way more than a matter of performance. (I’m not really familiar with the algorithm you chose for your example, so I’ll use fibonacci instead). If you implement a naive fibonacci-calculating function recursively, you’ll probably want to use tailrec. Then you can say fibonacci(10), or fibonacci(100), and it’ll still work. The latter might be slow, but it’ll work. Now, if tail recursion was implicit…well, it might still work. But what if you make an “optimization” to your algorithm? Try to make it a bit faster, but still hoping that Kotlin/JVM will use tail recursion. If you’re wrong, the program will crash with StackOverflowError randomly for certain inputs, inputs you might not even be testing for! It introduces a “denial of service” vector to your function. On the other hand, if you knew you had to have tail recursion for this function (because you wrote it a certain way and know the stack might otherwise get too deep), then the tailrec keyword will ensure you won’t hit that dreaded StackOverflowError ever again. Anything that acts as guard rails to keep our software running smoothly I’m quite in favor of, even if it means an extra keyword.
Could You please provide some examples of “very fragile and error-prone” code with tail recursion? I never saw any special keyword for tail recursive functions in functional languages except for JVM-based languages, and AFAIR it is only because of JVM does not support TCO by itself. Even not-so-functional Common Lisp has no macro or special form for tail recursive functions although some implementations (like SBCL e.g.) can do TCO while it is not specified by CL Standard.
The optimizations are all safe, except for some aggressive ones to cheat in benchmarks – not speaking of core dumps, which have other reasons.
Do they still think it’s a Java-only platform? And even Java would profit, if they did it after virtual function lookup…