F# has tail call elimination?

Question

In this talk, in the first 8 minutes, Runar explains that Scala has problems with tail call elimination, this makes me wonder whether F# has similar problems ? If not, why not ?

Coarctate

CLR supports tail call optimization via tail opcode (.NET 4 had some improvements), and as far as I know JVM does not support tail calls yet. – Etrem

@PatrykĆwiek I can't figure out, is that just tail-recursive calls? Or all kind of tail calls, e.g., tail calls in mutual recursive functions, like odd/even. – Shelter

@IonuțG.Stan From this blog post it seems that mutually recursive functions use tail opcode too. – Etrem

@PatrykĆwiek thanks. Then it has better support than the JVM. – Shelter

Answer 1

The problem with Proper Tail Calls in Scala is one of engineering trade-offs. It would be easily possible to add PTCs to Scala: just add a sentence to the SLS. Voilà: PTCs in Scala. From a Language Design perspective, we are done.

Now the poor compiler writers need to implement that spec. Well, compiling into a language with PTCs is easy … but unfortunately, the JVM byte code isn't such a language. Okay, so what about GOTO? Nope. Continuations? Nope. Exceptions (which are known to be equivalent to Continuations)? Ah, now we are getting somewhere! So, we could use exceptions to implement PTCs. Or, alternatively, we could just not use the JVM call stack at all and implement our own stack.

After all, there are multiple Scheme implementations on the JVM, all of them support PTCs just fine. It's a myth that you cannot have PTCs on the JVM, just because the JVM doesn't support them. After all, x86 doesn't have them either, but nonetheless, there are languages running on x86 that have them.

So, if implementing PTCs on the JVM is possible, then why doesn't Scala have them? Like I said above, you could use exceptions or your own stack to implement them. But using exceptions for control flow or implementing your own stack means that everything which expects the JVM call stack to look a certain way would no longer work.

In particular, you would lose pretty much all interoperability with the Java tooling ecosystem (debuggers, visualizers, static analyzers). You would also have to build bridges to interoperate with Java libraries, which would be slow, so you lose interop with the Java library ecosystem as well.

But that is a major design goal of Scala! And that's why Scala doesn't have PTCs.

I call this "Hickey's Theorem", after Rich Hickey, the designer of Clojure who once said in a talk "Tail Calls, Interop, Performance – Pick Two."

You would also present the JIT compiler with some very unusual byte code patterns that it may not know how to optimize well.

If you were to port F# to the JVM, you would basically have to make exactly that choice: do you give up Tail Calls (you can't, because they are required by the Language Spec), do you give up Interop or do you give up 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 complex than that, and the implementation of Tail Calls in MSIL is buggy in some corner cases.)

This poses the question: why not add Tail Calls to the JVM? Well, this is very hard, due to a design flaw in the JVM byte code. The designers wanted the JVM byte code to have certain safety properties. But instead of designing the JVM byte code language in such a way that you cannot write an unsafe program in the first place (like, say, in Java, for example, where you cannot write a program that violates pointer safety, because the language just doesn't give you access to pointers in the first place), JVM byte code in itself is unsafe and needs a separate byte code verifier to make it safe.

That byte code verifier is based on stack inspection, and Tail Calls change the stack. So, the two are very hard to reconcile, but the JVM simply doesn't work without the byte code verifier. It took a long time and some very smart people to finally figure out how to implement Tail Calls on the JVM without losing the byte code verifier (see A Tail-Recursive Machine with Stack Inspection by Clements and Felleisen and tail calls in the VM by John Rose (JVM lead 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 do have intra-method direct tail-recursion. However, that is pretty boring, implementation-wise: it is just a while loop. Most targets have while loops or something equivalent, e.g. the JVM has intra-method GOTO. Scala also has the scala.util.control.TailCalls object, which is kind-of a re-ified trampoline. (See Stackless Scala With Free Monads by Rúnar Óli Bjarnason for a more general version of this idea, which can eliminate all use of the stack, not just in tail-calls.) This can be used to implement a tail-calling algorithm in Scala, but this is then not compatible with the JVM stack, i.e. it doesn't look like a recursive method call to other languages or to 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 the recur special form, which is also an explicit trampoline.

Haslam

+1 interesting write-up, thanks. Can you provide any references for "some very smart people to finally figure out how to implement Tail Calls on the JVM without losing the byte code verifier"? I'd be interested in the details. – Sateen

@StephenSwensen: The paper is A Tail-Recursive Machine with Stack Inspection by Clements and Felleisen. See also tail calls in the VM by John Rose (JVM lead designer). – Jonna

It might be worth mentioning Scala's @tailrec – Proceed

@bbarker: intra-method direct tail-recursion is boring (from an implementation perspective). It's just a while loop, which is supported by most targets. (Or more precisely, the JVM has intra-method GOTO, which is the same thing.) – Jonna

Answer 2

F# does not have a problem with tail calls. Here is what it does:

• If you have a single tail-recursive function, the compiler generates a loop with mutation because this is faster than generating the .tail instruction

• In other tail-call positions (e.g. when using continuations or two mutually recursive functions), it generates the .tail instruction and so the tail call is handled by the CLR

• By default, tail-call optimization is turned off in Debug mode in Visual Studio, because this makes debugging easier (you can inspect the stack), but you can turn it on in project properties if needed.

In the old days, there used to be problems with the .tail instruction on some runtimes (CLR x64 and Mono), but that all of those have now been fixed and everything works fine.

Botel

"all of those have now been fixed and everything works fine." That is advertised to be the case, but sadly it is not true. – Virgilio

This is a good summary, but there are some exceptions to be mindful of. See blogs.msdn.com/b/fsharpteam/archive/2011/07/08/… for the gory details. – Gumm

Answer 3

It turns out that for proper tail calls, you have to either compile in "Release Mode" as opposed to the default "Debug Mode", or to open your project properties, and in the Build menu, scroll down and check "Generate tail calls". Thanks to Arnavion on IRC.freenode.net #fsharp for the tip.

Quadruplicate