为何泛型Lambda延续无栈溢出，指定类型则触发？

问题现象 #

我在处理递归类型时，为避免深层递归导致栈溢出，用延续传递风格（CPS）实现尾递归版本，但发现一个特殊现象：

• 当延续函数类型设为泛型cont: option<int> -> 'a时，代码无栈溢出且正常终止；
• 手动指定类型为cont: option<int> -> unit时，程序触发栈溢出。

测试环境：dotnet 9.0.102，Linux Manjaro，Release模式运行；Debug模式下两种情况都会溢出。我只想搞懂这个现象的原因，以及背后的.NET/F#优化机制，不关心代码是否符合惯用写法。

复现代码 #

type Expr = 
    | Number of int
    | Add of Expr * Expr  
    | Multiply of Expr * Expr

module Evaluator =
    let rec private evalCPS expr (cont: int option -> 'a) =   // 这里是关键的延续参数
        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

// 生成指定复杂度的测试表达式结构
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 // 生成深度足够大的测试表达式
let result = Evaluator.evaluate expr
printfn "%d" result.Value

原因分析 #

1. 泛型延续触发尾递归优化（TCO） #

当延续函数是泛型'a类型时，F#编译器会将evalCPS的所有尾位置调用识别为真正的尾递归。因为泛型返回值的不确定性，编译器无法提前推断延续函数的行为，只能严格按照尾递归的规则处理：将递归调用转换为循环结构，复用当前栈帧，避免栈帧累积，因此不会出现栈溢出。

2. unit类型延续破坏尾递归结构 #

当延续指定为unit类型时，编译器会进行激进的内联优化，但反而打破了尾递归的条件：

• 返回unit意味着函数没有有意义的返回值，编译器会尝试将延续函数直接内联到调用点，导致原本的尾调用变成嵌套的函数调用，栈帧无法被复用。
• 此外，编译器可能认为unit返回的延续不需要保留栈帧复用的结构，转而采用普通递归调用的方式，随着递归深度增加，栈帧不断累积，最终触发栈溢出。

从中总结的.NET/F#优化机制 #

• 尾递归优化的触发前提：F#编译器只对真正的尾调用进行优化——即函数的最后一个操作是调用自身，且当前栈帧后续没有需要执行的逻辑。泛型延续的不确定性让编译器更倾向于保留尾递归结构，而具体类型的延续可能因内联等优化破坏这一结构。
• Debug与Release模式的差异：Debug模式下编译器会禁用几乎所有优化（包括TCO），保留完整的栈帧用于调试，因此两种情况都会栈溢出；Release模式下才会启用优化策略，体现出两种延续类型的差异。
• 延续类型对优化的影响：泛型延续能给编译器足够的灵活性，确保尾递归优化触发；而具体类型的延续可能因编译器的特殊处理，导致尾调用结构失效。

内容的提问来源于stack exchange，提问作者Foxy