Piers, On 8 September 2015 at 15:58, Thomas Koster <tkos...@gmail.com> 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 17 September 2015 at 14:54, Nathan Schultz <milish...@gmail.com> wrote: > Here's the blog post from the Visual Studio F# team on it (although it's > getting old now): > http://blogs.msdn.com/b/fsharpteam/archive/2011/07/08/tail-calls-in-fsharp.aspx On 7 October 2015 at 01:14, Piers Williams <piers.willi...@gmail.com> wrote: > At the very end of that F# team blog post Nathan linked they say: > > "Most of these restrictions have been lifted in .NET 4.0." > > ... and if you read the linked article .. > > "For CLR 4 the fact that the x64 JIT would sometimes not honor the “tail.” > prefix prevented functional languages like F# from being viable. So we > worked to improve the x64 JIT so that it could honor the “tail.” prefix all > of the time and help make F# a success. Except where explicitly called out, > x86 and IA64 remain unchanged between CLR 2 and CLR 4, and the remainder of > this document refers solely to the x64 JIT. Also this is specific to CLR 4, > all other versions of the runtime or JIT (including service packs, QFEs, > etc.) might change this in any number of ways." Thanks. This post is the most technical description of CLR4's improvements I have read yet. For others, this post by Richins is at: http://blogs.msdn.com/b/clrcodegeneration/archive/2009/05/11/tail-call-improvements-in-net-framework-4.aspx Again, I am going to make some general comments about what I've read for the benefit of the list. I am not being critical of your responses, which have been very helpful in locating all the literature out there about this issue. Richins says many, but not all, restrictions mentioned in ECMA-335 are lifted in CLR4. The wart that remains is CAS, which seems to be unpopular anyway. This is reassuring. Richins's post precedes the 6th edition of ECMA-335 by at least two years and the 6th edition still contains the original vague relaxations of the rules. ECMA-335 is probably just being conservative in the name of portability, but do I treat a blog post as more authoritative than an ECMA standard? This highlights a second concern: ECMA-335 does not prescribe the precise semantics and deliberately leaves them up to the implementation, but as far as I can tell, Microsoft .NET lacks an authoritative manual documenting the precise semantics of their implementation. If I were writing a compiler, I would be nervous about targeting the CLR going solely on ECMA-335. If I target IA-64, Intel gives me thousands of pages of excruciating detail about the platform. Even JavaScript's so-called standard is more detailed than ECMA-335 (see ECMA-262). Where is this detail for Microsoft's CLR? If such a document exists, it should answer all my questions about F# on Microsoft .NET. Generally, I guess the problem I have is that everybody who blogs online about tail calls in the CLR treats tail call elimination as an optimization. This might be fine for procedural languages, but it is an unhealthy attitude for functional languages. Tail call elimination is *much* more important than any optimization, because without it, no program written in a functional language could traverse a recursive data structure (e.g. a list or tree) in constant space. Nobody writing about the CLR seems to get that ***tail call elimination is MANDATORY*** for the correct functioning of most non-trivial programs in any functional programming language. Put another way, the way I see it, whenever a compiler for a functional language emits a jump instruction (or "tail.call") for entering a closure arising out of a letrec, it is incorrect/unsafe to make an ordinary stack-consuming call instead, unless you can prove that the nesting of calls is bounded, which I believe requires you to solve the halting problem. -- Thomas Koster
