recursive stack overflow with exceptions in F#

Question

let's look at that code:

let rec doSomething () =
 let d = GetSomeDataFromSomewhere()
 match d with
 | Some x -> x
 | None -> doSomething()

so that's some form of non stop polling..

but now the following form:

let rec doSomething () =
 try 
 let d = GetSomeDataFromSomewhereButItCouldCrash()
 match d with
 | Some x -> x
 | None -> doSomething()
 with _ ->
 doSomething()

that one will lead to a stack overflow if there are a lot of exceptions.

Can someone explain the mechanics at play that make the two versions behave differently?

• Fyodor Soikin: Why do you think that the second option will lead to a stack oveflow?
• Thomas: I did such a loop in some debug code and it would regularly overflow, the non exception version didn't overflow though. Could I be wrong and the overflow doesn't come from the exception itself? tests seems to indicate that but I'm using Rider as an IDE and it's kicking me out of the debugger, so I can't see details.
• Fyodor Soikin: Can you try moving the match from under the try?
• Thomas: @FyodorSoikin, I just tried: no stack overflow; I did the GetSomeData.. call within a try block and the match outside. Why does it behave differently?
• Fyodor Soikin: It must be that the tail call cannot be tail call inside the try

Answer 1

The issue is that the first call in your second version is not in a tail-call position. This is not entirely obvious, because the recursive call is the "last thing the function does", but the runtime still has to keep the stack frame around, because it needs to keep the associated exception handler.

let rec doSomething () =
 try 
 let d = GetSomeDataFromSomewhereButItCouldCrash()
 match d with
 | Some x -> x
 | None -> doSomething() // This is not a tail call!
 with _ ->
 doSomething() // This is a tail call

If you handle exceptions directly when calling GetSomeDataFromSomewhere and turn them into None, then you can keep the same logic, but make it tail recursive:

let rec doSomething () =
 let d = try GetSomeDataFromSomewhereButItCouldCrash() with _ -> None
 match d with
 | Some x -> x
 | None -> doSomething()

• Thomas: yes, that was the suggestion of Fyodor, in the comments. It is definitely what is happening but it's not very clear. This may be a good place for a compiler warning.