What Is The Current State of Tail-Call-Optimization for F# on Mono (2.11)

F# tail call optimization issues on Mono

I tested a Fibonacci implementation passing an accumulator instead of a function (continuation) like this:

let fib n = 
   let rec _fib i (a,b) =
      match i with 
      | 0 -> a
      | _ -> _fib (i-1) (b, a+b)
   _fib n (0,1)

which worked fine on Mono, i.e. no stack overflow.
So I guess it's only an issue with TCO when using continuations. There's a Xamarin ticket from June 2013 addressing this.

Does the mono runtime already handle tail call optimisation as required by the IL spec?

No, not yet. There's some work-in-progress on adding it, though : http://www.mail-archive.com/mono-devel-list@lists.ximian.com/msg24438.html (wish me luck ;-) ).

What would the jvm have to sacrifice in order to implement tail call optimisation?

Whilst different (in that the il instructions existed already) it's worth noting the additional effort the .Net 64 bit JIT team had to go through to respect all tail calls.

I call out in particular the comment:

The down side of course is that if you have to debug or profile optimized code, be prepared to deal with call stacks that look like they’re missing a few frames.

I would think it highly unlikely the JVM could avoid this either.

Given that, in circumstances where a tail call optimization was requested, the JIT should assume that it is required to avoid a stack overflow this is not something that can just be switched off in Debug builds. They aren't much use for debugging if they crash before you get to the interesting part. The 'optimization' is in fact is a permanent feature and an issue for stack traces affected by it.

It is worth pointing out that any optimization which avoids creating a real stack frame when doing an operation which the programmer conceptually describes/understands as being a stack operation (calling a function for example) will inherently cause a disconnect between what is presented to the user when debugging/providing the stack trace and reality.

This is unavoidable as the code that describes the operation becomes further and further separated from the mechanics of the state machine performing the operation.

---

Related Topics