In a program I'm writing, I'm faced with a recursive type that I want to go through recursively (it seems necessary). Out of curiosity, I wanted to try and write a tail recursive version of my code, so as to avoid stack overflows when the data to be traversed is deeply recursive (I'll skip the details). I arrived at a version where, to achieve my goal, I had to implement continuations so that in the end my code is tail recursive or "continuation recursive" (i.e. the continuation is the last operation of an execution branch). I don't know how F# / .NET would optimize this style of code (i.e. recursive continuation), that's why I tried.
I then stumbled for a long time over a particular behavior that I've only just put my finger on. My continuation is of the following type: cont: option<int> -> 'a, but I know that in the end the generic type 'a is simply a unit. By replacing this deduced type myself, the runtime behavior changes:
- When I specify the type,
cont: option<int> -> unit, the code overflows the stack. - When I do not specify the type and leave it generic,
cont: option<int> -> 'a, the code doesn't overflow and terminates.
I don't understand what produces such behavior. I tried to produce a minimal version of my real code and came up with a code that is quite different but shows the same behavior:
type Expr =
| Number of int
| Add of Expr * Expr
| Multiply of Expr * Expr
module Evaluator =
let rec private evalCPS expr (cont: int option -> 'a) = // I speak about this continuation
match expr with
| Number n ->
cont (Some n)
| Add(left, right) ->
let continuation leftResult =
match leftResult with
| Some leftVal ->
evalCPS right (fun rightResult ->
match rightResult with
| Some rightVal -> cont (Some(leftVal + rightVal))
| None -> cont None)
| None -> cont None
evalCPS left continuation
| Multiply(left, right) ->
let continuation leftResult =
match leftResult with
| Some leftVal ->
evalCPS right (fun rightResult ->
match rightResult with
| Some rightVal -> cont (Some(leftVal * rightVal))
| None -> cont None)
| None -> cont None
evalCPS left continuation
let evaluate expr =
let mutable result = None
evalCPS expr (fun r -> result <- r)
result
// Generates a structure of specified complexity for testing purpose.
let generateExpr n =
let random = Random()
let rec generate size =
if size <= 1 then
Number(random.Next(1, 10))
else
let leftSize = random.Next(1, size)
let rightSize = size - leftSize
match random.Next(2) with
| 0 -> Add(generate leftSize, generate rightSize)
| _ -> Multiply(generate leftSize, generate rightSize)
generate n
let expr = generateExpr 50_000 // big depth for the test
let result = Evaluator.evaluate expr
printfn "%d" result
I'm not really interested in whether or not this code is idiomatic or improvable since it's not my real code. I'm only interested in why specifying the actual type rather than leaving it generic in a higher-order function produces a stack overflow when the version with generic doesn't. So that's my question: why? How ? And what could we learn from this from the user's point of view?
I'm not sure if this is F#-specific behavior because I know that generics still live in .NET bytecode, and I wouldn't be surprised if the reason for this behavior originated there, but I don't know C# so I can't write equivalent code.
I use dotnet 9.0.102 on Linux Manjaro and run the code with dotnet run --configuration Release. In the case where the code is compiled in debug rather than in release, in both cases the code produces an overflow.
