Re: Is F# ready for serious work without mandatory tail call elimination in the CLR?

[Nathan Schultz]

The problem isn't isolated to F#; LINQ in C# is also a functional .NET
language.
But I'm yet to encounter a problem related to the compiler in it either.
Like in LINQ, stack overflows have always been caused by me inappropriately
calling a .ToList() on a IEnumerable for example.
And it's a same for F#... what you describe just doesn't seem to be an
issue in practice when likewise using appropriate tail-recursive code (at
least that I've experienced).

And there are a few fairly large users of F# around the place that use it
critically:
For example; GameSys uses F# for their social gaming department (i.e.
Facebook games). I know Yan Cui mentioned they get 250 million requests per
day.
Likewise, the opponent rating and matching system on X-Box Live is written
in F#. And Jane Street uses F# for stock-analysis.
The e-Commerce site, Jet.com has also likewise adopted F# for their
price-matching algorithms.
And consider "The Gamma" (http://thegamma.net/) which is a 'big data'
project in Data Journalism.

All of these use F# to crunch some pretty large sets of data. In fact type
providers seem to make F# a good fit for these sorts of things.
So the compiler implementation seems to be doing the right thing. And given
the rate at which big-data is growing, I'd be surpised if there isn't
additional focus in the future.

Nathan Schultz

On 7 October 2015 at 10:37, Thomas Koster  wrote:

> Piers,
>
> On 8 September 2015 at 15:58, Thomas Koster  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  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 
> 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 

Re: Is F# ready for serious work without mandatory tail call elimination in the CLR?

[Thomas Koster]

Piers,

On 8 September 2015 at 15:58, Thomas Koster  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  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  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

Re: Is F# ready for serious work without mandatory tail call elimination in the CLR?

[Piers Williams]

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."
On 17 Sep 2015 2:47 pm, "Thomas Koster"  wrote:

> On 8 September 2015 at 15:58, Thomas Koster  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  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  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
>

Re: Is F# ready for serious work without mandatory tail call elimination in the CLR?

[Thomas Koster]

On 8 September 2015 at 15:58, Thomas Koster  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  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  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

Re: Is F# ready for serious work without mandatory tail call elimination in the CLR?

[Thomas Koster]

Nathan,

On 8 September 2015 at 15:58, Thomas Koster  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  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).
>
> I've never run into an issue myself, although infrequently I have heard of
> corner-cases that still pose issues (e.g.
> http://blogs.msdn.com/b/dotnet/archive/2015/07/28/ryujit-bug-advisory-in-the-net-framework-4-6.aspx).
> However, I've also heard it said that when it comes to tail-end recursion F#
> is in a better place with the CLR than Scala is with the JVM. And both are
> used in production even in financial institutions.
>
> Given that I (rarely) still run into other bugs in the .Net framework with
> C#, I don't see this as anything different; testing (including on different
> platforms) is a necessary part of application development, and with F# it's
> no different.

Thanks for your response.

I readily believe that the JVM is a worse place for functional languages
than the CLR. But both seem to share the same weakness when it comes to
implementing functional languages: they both support only one evaluation
strategy, namely the stack-based, strict, call-by-value evaluation
strategy of the curly brace langauges (and their predecessors). The
opcodes needed to implement other strategies efficiently are missing.

I am starting to see that I may have over-estimated the number of ways
space leaks caused by tail calls can creep into an F# program. But since
F# uses a strict evaluation order where tail call elimination is
absolutely necessary to avoid excessive space usage, the discretionary
nature of the ".tail" opcode prefix still makes me uneasy and I would
rather not have to write tests to verify the correctness of the F#
compiler, let alone the JIT compiler.

So for now, for me, F# remains just an intellectual curiosity.

--
Thomas Koster

Re: Is F# ready for serious work without mandatory tail call elimination in the CLR?

[Nathan Schultz]

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).

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 16 September 2015 at 15:31, Thomas Koster  wrote:

> Nathan,
>
> On 8 September 2015 at 15:58, Thomas Koster  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  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).
> >
> > I've never run into an issue myself, although infrequently I have heard
> of
> > corner-cases that still pose issues (e.g.
> >
> http://blogs.msdn.com/b/dotnet/archive/2015/07/28/ryujit-bug-advisory-in-the-net-framework-4-6.aspx
> ).
> > However, I've also heard it said that when it comes to tail-end
> recursion F#
> > is in a better place with the CLR than Scala is with the JVM. And both
> are
> > used in production even in financial institutions.
> >
> > Given that I (rarely) still run into other bugs in the .Net framework
> with
> > C#, I don't see this as anything different; testing (including on
> different
> > platforms) is a necessary part of application development, and with F#
> it's
> > no different.
>
> Thanks for your response.
>
> I readily believe that the JVM is a worse place for functional languages
> than the CLR. But both seem to share the same weakness when it comes to
> implementing functional languages: they both support only one evaluation
> strategy, namely the stack-based, strict, call-by-value evaluation
> strategy of the curly brace langauges (and their predecessors). The
> opcodes needed to implement other strategies efficiently are missing.
>
> I am starting to see that I may have over-estimated the number of ways
> space leaks caused by tail calls can creep into an F# program. But since
> F# uses a strict evaluation order where tail call elimination is
> absolutely necessary to avoid excessive space usage, the discretionary
> nature of the ".tail" opcode prefix still makes me uneasy and I would
> rather not have to write tests to verify the correctness of the F#
> compiler, let alone the JIT compiler.
>
> So for now, for me, F# remains just an intellectual curiosity.
>
> --
> Thomas Koster
>

Re: Is F# ready for serious work without mandatory tail call elimination in the CLR?

[Nathan Schultz]

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).

I've never run into an issue myself, although infrequently I have heard of
corner-cases that still pose issues (e.g.
http://blogs.msdn.com/b/dotnet/archive/2015/07/28/ryujit-bug-advisory-in-the-net-framework-4-6.aspx
).
However, I've also heard it said that when it comes to tail-end recursion
F# is in a better place with the CLR than Scala is with the JVM. And both
are used in production even in financial institutions.

Given that I (rarely) still run into other bugs in the .Net framework with
C#, I don't see this as anything different; testing (including on different
platforms) is a necessary part of application development, and with F# it's
no different.


On 8 September 2015 at 13:58, Thomas Koster  wrote:

> Hi friends,
>
> When I first heard of F# a few years ago I laughed out loud, but its
> popularity is exploding, and .NET pays the bills, so I am forced to take
> it a little bit more seriously these days.
>
> Tail call elimination in .NET is a *hint only* that JIT is free to
> ignore in many situations [1], including:
> - in debug builds,
> - when calling virtual methods,
> - when calling a method in a different security trust group,
> - in any other case where an "implementation-specific restriction
>   prevents the 'tail.' prefix from being obeyed."
>
> Yet tail call elimination is *essential* to the correct functioning of
> programs written in any functional programming language.
>
> 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?
>
> [1] "Common Language Infrastructure (CLI)" 6e, ECMA-335, III.2.4
>
> --
> Thomas Koster
>

Is F# ready for serious work without mandatory tail call elimination in the CLR?

[Thomas Koster]

Hi friends,

When I first heard of F# a few years ago I laughed out loud, but its
popularity is exploding, and .NET pays the bills, so I am forced to take
it a little bit more seriously these days.

Tail call elimination in .NET is a *hint only* that JIT is free to
ignore in many situations [1], including:
- in debug builds,
- when calling virtual methods,
- when calling a method in a different security trust group,
- in any other case where an "implementation-specific restriction
  prevents the 'tail.' prefix from being obeyed."

Yet tail call elimination is *essential* to the correct functioning of
programs written in any functional programming language.

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?

[1] "Common Language Infrastructure (CLI)" 6e, ECMA-335, III.2.4

--
Thomas Koster