Tail call elimination is an essential feature for functional programming languages. This feature simply refers to the ability for one function to end with a function call without leaking stack space. Tail call elimination can be essential in heavily functional code such as parser combinators and libraries written in continuation passing style.
Lack of tail calls on the defacto-standard JVM has raised concerns around languages like Scala and Clojure. Fortunately, work is underway to address this issue by implementing tail call elimination on MLVM/OpenJDK.
Microsoft's .NET has had tail call elimination for eight years and the Mono project is designed to replicate the Common Language Infrastructure (CLI) that is responsible for this feature. The Mono team have been advertising tail call elimination on their VM for many years.
However, when we tested the elimination of tail calls on several VMs we discovered that tail calls are seriously broken on Mono but work on other VMs including .NET, LLVM and, of course, OCaml. Specifically, we ran the following trivial F# program that relies upon a tail call to a dynamic location, a function odd that is passed as an argument to the higher-order even function:
let even odd n = odd(n+1)
let odd n =
printf "%d\n" n
even odd (n+1)
let (_: int) =
even odd 0
This program prints odd integers indefinitely in OCaml or F# on .NET but attempting to run the executable generated by F# on Mono 2.2 results in a stack overflow almost immediately, as Mono leaks stack space until the stack is exhausted. So Mono cannot be relied upon to execute any functional programs correctly including F# programs.
This is of particular interest to us because several people have asked us for customer support when trying to run our F# code, such as the code from our book F# for Scientists, under Mono. Our advice is to steer well clear of Mono until it becomes stable and feature complete.
Interestingly, we also tried the same test on LLVM 2.2, writing the program in LLVM IR, and the tail calls are handled flawlessly provided the fast calling convention is used. As we have shown before, LLVM also generates vastly faster code than Mono 2.2.