4 ms·

Tail calls in F#

62 points by clockwork_189 15y ago

fuzzythinker 15y ago
Looks like it's a confirmed feature in 2.12 Mono too: http://www.mono-project.com/Mono_Project_Roadmap http://www.mono-project.com/Mono_Project_Roadmap
- gtani 15y ago
  And you can crank up the stack size (tho this SO has a link to Duffy talking about increasing stack on the CLR) http://stackoverflow.com/questions/7538584/f-vs-ocaml-stack-overflow http://stackoverflow.com/questions/7538584/f-vs-ocaml-stack-...
nxn 15y ago
> For instance, use bindings implicitly generate a try-finally around the code that follows them to ensure that the Dispose method is called on the bound value. This means that no calls following a use binding will be tail calls. Reading that just kind of made me break out into a cold sweat. I imagine I will be looking at some IL tonight because of this. I still don't quite get the reason for why try-catch or try-finally blocks cannot have a tail call in them?
- kenjackson 15y ago
  The point of the tail call is to not push an item on the stack frame. That is why tail call is an optimization you can perform when there are no other operations after the tail call. You can jump to the next instruction and be done with it. But if the tail call is in a try-finally block the "tail call" is not actually the tail. There is more code that needs to be run after the execution of the tail call. The code has to return back from the tail call and execute the finally code. What you thought was a tail call is actually no longer a tail call at all.
  - nxn 15y ago
    I was under the impression that the article stated that a CALL to a recursive function inside of the try-* block would prevent it from being done with a tail call, and not that the recursive function contained a wrapping try-* block in its body. I think I may have understood wrong what the article was saying.
    - kenjackson 15y ago
      I was under the impression that the article stated that a CALL to a recursive function inside of the try- block would prevent it from being done with a tail call* Yes, that statement is correct and what we're talking about. Having a try-finally in the body of the tail-call function shouldn't make a difference. To be clear: try { ... tailcall(...); } finally { ... } That could block tail call optimization.
      - profquail 15y ago
        According to the .NET CLR spec, you're not allowed to have a tailcall within a protected ("try") block or it's handler. On the other hand, tail-calls can be optimized into a while loop, and the F# compiler does this in some cases (check out the IL it produces), so then you could have a recursive tail-call within a try/finally there, it just wouldn't be using the 'tail.call' / 'tail.callvirt' / 'tail.calli' OpCode.
      - nxn 15y ago
        Right, I completely see how that would prevent it from qualifying as a tail call, my misunderstanding was still different though. For some reason I thought that even if the recursive function was defined within the try-catch block (as below) it would prevent it from using a tail call: try let rec func ... = ... func( ... ) let result = func( ... ) with | ex -> ... I don't know exactly how I ended up thinking that, seems a bit silly in retrospect.
- flatline 15y ago
  Elaborating a bit on kenjackson's reply, the code in a finally block is guaranteed to run after the code in the try block, which is the whole point of finally. A use block unrolls into a try/finally block where the finally cleans up the resource declared in the use initializer. I'm not sure about try/catch without the finally, perhaps there is some error check that occurs in the IL after the body of the try block?
  - profquail 15y ago
    In MSIL, there's actually no such thing as a try/catch/finally -- only try/catch, try/finally (and the lesser-known try/fault and try/filter). When you write a try/catch/finally in C#, the compiler generates a try/catch inside of a try/finally.
abhijitr 15y ago
Looking at the MSIL emitted by the compiler is not a reliable way to tell that a tail call will be used at runtime. It's ultimately at the discretion of the JIT whether to compile the 'tail.callvirt' into an actual tail call in x86.

62 points by clockwork_189 15y ago

Looks like it's a confirmed feature in 2.12 Mono too: http://www.mono-project.com/Mono_Project_Roadmap http://www.mono-project.com/Mono_Project_Roadmap

gtani 15y ago
And you can crank up the stack size (tho this SO has a link to Duffy talking about increasing stack on the CLR) http://stackoverflow.com/questions/7538584/f-vs-ocaml-stack-overflow http://stackoverflow.com/questions/7538584/f-vs-ocaml-stack-...

nxn 15y ago

> For instance, use bindings implicitly generate a try-finally around the code that follows them to ensure that the Dispose method is called on the bound value. This means that no calls following a use binding will be tail calls. Reading that just kind of made me break out into a cold sweat. I imagine I will be looking at some IL tonight because of this. I still don't quite get the reason for why try-catch or try-finally blocks cannot have a tail call in them?

kenjackson 15y ago
The point of the tail call is to not push an item on the stack frame. That is why tail call is an optimization you can perform when there are no other operations after the tail call. You can jump to the next instruction and be done with it. But if the tail call is in a try-finally block the "tail call" is not actually the tail. There is more code that needs to be run after the execution of the tail call. The code has to return back from the tail call and execute the finally code. What you thought was a tail call is actually no longer a tail call at all.
- nxn 15y ago
  I was under the impression that the article stated that a CALL to a recursive function inside of the try-* block would prevent it from being done with a tail call, and not that the recursive function contained a wrapping try-* block in its body. I think I may have understood wrong what the article was saying.
  - kenjackson 15y ago
    I was under the impression that the article stated that a CALL to a recursive function inside of the try- block would prevent it from being done with a tail call* Yes, that statement is correct and what we're talking about. Having a try-finally in the body of the tail-call function shouldn't make a difference. To be clear: try { ... tailcall(...); } finally { ... } That could block tail call optimization.
    - profquail 15y ago
      According to the .NET CLR spec, you're not allowed to have a tailcall within a protected ("try") block or it's handler. On the other hand, tail-calls can be optimized into a while loop, and the F# compiler does this in some cases (check out the IL it produces), so then you could have a recursive tail-call within a try/finally there, it just wouldn't be using the 'tail.call' / 'tail.callvirt' / 'tail.calli' OpCode.
    - nxn 15y ago
      Right, I completely see how that would prevent it from qualifying as a tail call, my misunderstanding was still different though. For some reason I thought that even if the recursive function was defined within the try-catch block (as below) it would prevent it from using a tail call: try let rec func ... = ... func( ... ) let result = func( ... ) with | ex -> ... I don't know exactly how I ended up thinking that, seems a bit silly in retrospect.
flatline 15y ago
Elaborating a bit on kenjackson's reply, the code in a finally block is guaranteed to run after the code in the try block, which is the whole point of finally. A use block unrolls into a try/finally block where the finally cleans up the resource declared in the use initializer. I'm not sure about try/catch without the finally, perhaps there is some error check that occurs in the IL after the body of the try block?
- profquail 15y ago
  In MSIL, there's actually no such thing as a try/catch/finally -- only try/catch, try/finally (and the lesser-known try/fault and try/filter). When you write a try/catch/finally in C#, the compiler generates a try/catch inside of a try/finally.

abhijitr 15y ago

Looking at the MSIL emitted by the compiler is not a reliable way to tell that a tail call will be used at runtime. It's ultimately at the discretion of the JIT whether to compile the 'tail.callvirt' into an actual tail call in x86.