On 8 September 2015 at 15:58, Thomas Koster <[email protected]> wrote: > F# appears to eliminate tail calls to self by program transformation > where it is trivial to do so, but relies entirely on the CLR for > optimizing tail calls in general. This would mean that the stability and > reliability of programs written for the CLR in F# is uncertain, and that > debug builds of F# programs are always unreliable. I would want much > stronger guarantees about space complexity if I were to seriously > consider F# as a programming language for paid work. > > So if anybody has used F# in the real world, what's the story?
On 14 September 2015 at 18:06, Nathan Schultz <[email protected]> wrote: > IIRC, as you said, for most tail-end recursion, you'll find that the IL that > F# generates is actually a simple loop with a mutable variable. In cases > where there's continuations involved or more complex scenarios with multiple > recursive functions, F# will automatically provide the CLR with the .tail > instruction. Work has gone into the CLR to better support tail end > recursion, and there have been lots of fixes in recent versions (e.g. going > back a couple of years, there used to be scenarios where the JIT would > ignore the flag, but have been fixed). On 17 September 2015 at 14:54, Nathan Schultz <[email protected]> wrote: > There's some discussion of it here: > http://stackoverflow.com/questions/15864670/generate-tail-call-opcode > > In particular, look at Tomas Petricek's answer (he is an F# MVP). It appears > the F# compiler (in release mode) does give guarantees about tail-recursion > (it's the C# compiler that cannot). This is interesting because Petricek contradicts ECMA-335 here. (I checked both 5th ed and 6th ed.) I'm not asking that you defend his claims; I'm just making a comment here :) I accept prima facie that the F# compiler guarantees that it will emit the ".tail" opcode prefix before all function calls in tail position, but Petricek makes a stronger claim that I cannot find any supporting evidence for. He says, "the compiler generates a tail-call instruction that tells the JIT that it *must* use a tail call". However, the CLR does not actually have to honour the ".tail" opcode prefix in all situations as he claims. Secondly, he gives an example that is exactly one of the situations where ECMA-335 says an implementation is permitted to ignore the ".tail" opcode: a virtual method call. ECMA-335 justifies this relaxation of the rules because CAS usually need a proper stack frame to work correctly. It is possible that Petricek knows some secrets about Microsoft's JIT compiler that we don't. If he does, he should back up his claims with them or I will have to go with what ECMA-335 says and assume that the JIT compiler will ignore all the ".tail" opcodes at any time that ECMA-335 says it is allowed to ignore them. I know this sounds pessimistic, and usually I don't care so much about code that I can fix myself, but when it comes to the compiler and the runtime, I expect strong guarantees. One of the first things my CS lecurer said long ago was that I should never rely on optimizations performed by the compiler for correct behaviour. -- Thomas Koster
