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 calls in the CLR treats tail call elimination as an
> optimization. This might be fine

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: Re-request - Office chair again

[Piers Williams]

Some high end office fitouts use the Mirra, not the Aeron (which comes in
three different sizes and needs setup, whereas pretty much all you need to
do is sit in a Mirra and it's right). Caveat: I'm not lucky enough to have
used either outside of the showroom.

http://www.hermanmiller.com/products/seating/performance-work-chairs/mirra-2-chairs.html
On 16 Sep 2015 6:22 am, "Dave Walker"  wrote:

> Hi, sure.
>
> I started that convo and ended up going with an Aeron
> http://www.hermanmiller.com/products/seating/performance-work-chairs/aeron-chairs.html
> - so far it's amazing. Never even notice it's there vs my chair at work
> which causes me regular lower back pain.
>
> Other options included the Steelcase Leap
> http://www.steelcase.com/products/office-chairs/leap/
>
> I can't remember any others these were two top two for me.
>
>
> On 16 September 2015 at 10:18, Paul Glavich 
> wrote:
>
>> Hi all,
>>
>>
>>
>> I know there was a thread on office chairs here not so long ago and I
>> remember Greg Low and a few others recommend a particular brand which I had
>> intended to look into. Recent spinal issues have caused me to revisit this
>> sooner rather than later but I have since lost the email and was wondering
>> if someone could just send (off or on list) that chair recommendation again
>> please?
>>
>>
>>
>> -  Glav
>>
>>
>>
>
>

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
>