4 ms·

CLR also supports proper tail calls, where the JVM does not (yet).

mastazi 11y ago
Yes, surprisingly this feature, which is very important (see how Scala had to find a way around it [1]), has been overlooked. To me, it seems like a list put together in a non-systematic way. [1] https://medium.com/binary-dreams/from-java-to-scala-tail-recursion-a6acdd71a94d#.fs6lythj2 https://medium.com/binary-dreams/from-java-to-scala-tail-rec...
MichaelGG 11y ago
CLR .tail prefix is only a hint and not guaranteed. And traditionally it's had a ton of restrictions and limitations and was slow enough that F# stopped emitting it except when needed. (A lot of code ends up tail call optimizable, even if not recursive or designed that way.) Is rather have the JVM's compressed pointers and escape analysis.
jdmichal 11y ago
Though it's important to note that it's only a suggestion for the CLR runtime. For instance, in .NET v2 (which as an engine also covers v3) it was rare for tail call optimization to trigger in 64-bit mode. They finally fixed this in .NET v4 to make F# viable. https://blogs.msdn.microsoft.com/clrcodegeneration/2009/05/11/tail-call-improvements-in-net-framework-4/ https://blogs.msdn.microsoft.com/clrcodegeneration/2009/05/1...
- MichaelGG 11y ago
  Though note F# avoids .tail and turns recursive calls into loops when able.
  - deleted 11y ago
    [deleted]
  - jdmichal 11y ago
    I think it's the .NET JIT that turns the self-recursive calls into loops. But yes, this is all covered in the link I included.
    - MichaelGG 11y ago
      Well since .tail is only a hint, F# must do it in some cases. Try writing a simple recursive function in tail call style and look at the IL produced by fsc.
      - jdmichal 11y ago
        I was basing my statement on this line from the MSDN blog I linked: > This is such an important concept that the JIT has a special path just for turning functions that call themselves in a tail recursive manner into loops. However, it looks like (in at least some cases) that fsc unrolls the recursion prior to the JIT: let rec fact n acc = match n with | 0 -> acc | _ -> fact (n-1) (acc*n) .method assembly static int32 fact@1(int32 n, int32 acc) cil managed { // Code size 24 (0x18) .maxstack 5 IL_0000: ldarg.0 IL_0001: switch ( IL_0016) IL_000a: ldarg.0 IL_000b: ldc.i4.1 IL_000c: sub IL_000d: ldarg.1 IL_000e: ldarg.0 IL_000f: mul IL_0010: starg.s acc IL_0012: starg.s n IL_0014: br.s IL_0000 IL_0016: ldarg.1 IL_0017: ret } // end of method TailTest::fact@1

Yes, surprisingly this feature, which is very important (see how Scala had to find a way around it [1]), has been overlooked. To me, it seems like a list put together in a non-systematic way. [1] https://medium.com/binary-dreams/from-java-to-scala-tail-recursion-a6acdd71a94d#.fs6lythj2 https://medium.com/binary-dreams/from-java-to-scala-tail-rec...

MichaelGG 11y ago

CLR .tail prefix is only a hint and not guaranteed. And traditionally it's had a ton of restrictions and limitations and was slow enough that F# stopped emitting it except when needed. (A lot of code ends up tail call optimizable, even if not recursive or designed that way.) Is rather have the JVM's compressed pointers and escape analysis.

jdmichal 11y ago

Though it's important to note that it's only a suggestion for the CLR runtime. For instance, in .NET v2 (which as an engine also covers v3) it was rare for tail call optimization to trigger in 64-bit mode. They finally fixed this in .NET v4 to make F# viable. https://blogs.msdn.microsoft.com/clrcodegeneration/2009/05/11/tail-call-improvements-in-net-framework-4/ https://blogs.msdn.microsoft.com/clrcodegeneration/2009/05/1...

MichaelGG 11y ago
Though note F# avoids .tail and turns recursive calls into loops when able.
- deleted 11y ago
  [deleted]
- jdmichal 11y ago
  I think it's the .NET JIT that turns the self-recursive calls into loops. But yes, this is all covered in the link I included.
  - MichaelGG 11y ago
    Well since .tail is only a hint, F# must do it in some cases. Try writing a simple recursive function in tail call style and look at the IL produced by fsc.
    - jdmichal 11y ago
      I was basing my statement on this line from the MSDN blog I linked: > This is such an important concept that the JIT has a special path just for turning functions that call themselves in a tail recursive manner into loops. However, it looks like (in at least some cases) that fsc unrolls the recursion prior to the JIT: let rec fact n acc = match n with | 0 -> acc | _ -> fact (n-1) (acc*n) .method assembly static int32 fact@1(int32 n, int32 acc) cil managed { // Code size 24 (0x18) .maxstack 5 IL_0000: ldarg.0 IL_0001: switch ( IL_0016) IL_000a: ldarg.0 IL_000b: ldc.i4.1 IL_000c: sub IL_000d: ldarg.1 IL_000e: ldarg.0 IL_000f: mul IL_0010: starg.s acc IL_0012: starg.s n IL_0014: br.s IL_0000 IL_0016: ldarg.1 IL_0017: ret } // end of method TailTest::fact@1