F # has tail call elimination?

Question

In this talk, for the first 8 minutes Runar explains that Scala has problems eliminating the tail call, it makes me wonder if F # has similar problems? If not, why not?

Answer 1

The problem with the right tail calls in Scala is one of the technical tradeoffs. It would be easy to add PTC to Scala: just add the sentence to SLS. Voilà: PTC in Scala. In terms of language design, we are done.

Now poor compilers must implement this specification. Well, compiling a language with PTC is easy ... but, unfortunately, the JVM bytecode is not such a language. OK, so what about GOTO ? Nope. Continuation? Nope. Exceptions (which are known to be equivalent to continuations)? Ah, now we get somewhere! Thus, we could use exceptions to implement PTC. Or, alternatively, we could just not use the JVM call stack at all and implement our own stack.

After all, the JVM implements several Schema implementations, all of which support PTCs just fine. It is a myth that you cannot have PTC on the JVM, just because the JVM does not support them. After all, x86 also doesn't have them, but nonetheless, on x86 there are languages ​​that have them.

So, if implementing PTC on the JVM is possible, then why don't they have Scala? As I said, you can use exceptions or your own stack to implement them. But using exceptions for control flow or implementing your own stack means that everything that expects the JVM call stack to look a certain way will no longer work.

In particular, you will lose almost all compatibility with the ecosystem of Java tools (debuggers, visualizers, static analyzers). You will also have to create bridges to interact with Java libraries, which would be slow, so you will also lose interaction with the Java library ecosystem.

But this is the main goal of Scala design! And so Scala does not have PTC.

I call this “Hickey's theorem” after rich Hickey, the designer of Clojure, who once said in a conversation, “Tail calls, interaction, performance - the second choice.”

You will also introduce a JIT compiler with very unusual byte code patterns that may not know how to optimize.

If you were to port F # to the JVM, you would basically have to make this choice: do you refuse Tail Calls (you cannot, because they are required by Language Spec), do you refuse Interop or do you refuse performance? On .NET, you can have all three, because Tail Calls in F # can simply be compiled into Tail Calls in MSIL. (Although the actual translation is more complicated than that, and the implementation of Tail Calls in MSIL is erroneous in some cases.)

The question is: why not add Tail Calls to the JVM? Well, this is very complicated due to lack of design in the JVM bytecode. Designers wanted the JVM bytecode to have certain security features. But instead of developing the JVM byte code language in such a way that you cannot write an unsafe program in the first place (for example, in Java, where you cannot write a program that violates pointer security because the language simply does not give you access to pointers first), the JVM bytecode itself is unsafe and requires a separate bytecode verifier to make it safe.

This byte code verifier is based on a stack check, and tail calls change the stack. Thus, the two are very difficult to reconcile, but the JVM just doesn't work without a byte code verifier. It took a long time, and some very smart people finally figured out how to implement Tail Calls on the JVM without losing the bytecode verifier (see A Tail-Recursive Clements and Felleisen Stack Checker and VM tail calls from John Rose (lead JVM designer ) ), so we have now moved from the stage where it was an open research problem to the stage where it is “just” an open engineering problem.

Note that Scala and some other languages ​​have direct tail recursion inside the method. However, this is pretty boring, realistic: it's just a while . Most targets have while loops or something similar, for example. JVM has GOTO method. Scala also has an object scala.util.control.TailCalls , which is a kind of trampoline with repeated intervention. (See Stackless Scala With the free Monads by Rúnar Óli Bjarnason for a more general version of this idea that can eliminate all stack usage, not just tail calls.) This can be used to implement the tail call algorithm in Scala, but this is then incompatible with JVM i.e. it doesn't look like a recursive method call to other languages ​​or a debugger:

 import scala.util.control.TailCalls._ def isEven(xs: List[Int]): TailRec[Boolean] = if (xs.isEmpty) done(true) else tailcall(isOdd(xs.tail)) def isOdd(xs: List[Int]): TailRec[Boolean] = if (xs.isEmpty) done(false) else tailcall(isEven(xs.tail)) isEven((1 to 100000).toList).result def fib(n: Int): TailRec[Int] = if (n < 2) done(n) else for { x <- tailcall(fib(n - 1)) y <- tailcall(fib(n - 2)) } yield (x + y) fib(40).result 

Clojure has a recur special shape , which is also an explicit trampoline.

Answer 2

F # has no problem with tail calls. Here is what he does:

• If you have one tail recursion function, the compiler generates a loop with the mutation because it is faster than generating the .tail

• In other positions of the tail call (for example, when using continuations or two mutually recursive functions), it generates the .tail command, and therefore the tail call is processed using the CLR

• By default, tail call optimization is disabled in debug mode in Visual Studio because it makes debugging easier (you can check the stack), but you can enable it in the project properties if necessary.

In the old days, there were problems with the .tail for some .tail (CLR x64 and Mono), but they are all fixed and everything works fine.

Answer 3

It turns out that for the right tail calls, you either need to compile the “Release Mode” and not the default “Debug Mode” or open the project properties, and in the “Build” menu scroll down and check “Create tail calls”. Thanks to Arnavion on IRC.freenode.net #fsharp for the tip.