openlang
编译器、运行时与小语言

Why would this CPS sum overflow only in Debug?

后续讨论 5 ↓

Could someone check my reading of this? A continuation-passing sum, written as an exercise.

let rec sumK (xs: int list) (k: int -> int) =
    match xs with
    | [] -> k 0
    | x :: rest -> sumK rest (fun s -> k (s + x))

let xs = List.replicate 1_000_000 1
printfn "%d" (sumK xs id)

dotnet run -c Release prints 1000000. A plain dotnet run, which is Debug, dies with a stack overflow. Same source, same machine. I suspect tail calls, since every call in there is in tail position, but I don't know which part of the build decides it. Maybe the honest fix is to turn something on for Debug, or maybe the code should stop relying on it.

后续讨论 5

顺着彼此的依据读下去

  1. Debug builds have tail calls off, and Release has them on. sumK calling itself is compiled to a jump either way, so building the chain is fine. The overflow is k (s + x), a call through a closure in tail position. Without tail calls it is a plain callvirt with no tail. prefix, and when k 0 finally runs, a million closures each add a frame. The switch is the Tailcalls property in the project, --tailcalls on the command line.

  2. 接着前面的回复 ↗

    So the same text is a working program in one configuration and a crash in the other. That puts the tail call guarantee at the build layer, which is an odd layer for something the program's meaning depends on. The [<TailCall>] attribute looks like the fix at the right layer. Mark sumK with it and the requirement is written in the source, so the Debug build has to emit the prefix too.

  3. 接着前面的回复 ↗

    I hoped so too and tried it first. [<TailCall>] only adds a check. The compiler warns when a recursive call to the marked function isn't in tail position, and what it emits stays the same. On sumK it stays silent, because the recursive call already is in tail position, and the Debug build overflows exactly as before. The closures that would need covering aren't the marked function anyway.

  4. 接着前面的回复 ↗

    Is there a reason Debug turns them off beyond habit? My guess is the call stack. A frame replaced by a tail call is gone, so the debugger and exception stack traces skip those steps, and that view is what people open Debug for. If that's it, turning Tailcalls on for Debug trades some of that view for a program that runs, which feels like a decision per project rather than a default to flip everywhere.

  5. 接着前面的回复 ↗

    That sounds right to me. For this project the program itself depends on tail calls, so they're on for both configurations now, and Debug prints 1000000 too.

    <PropertyGroup>
  <Tailcalls>true</Tailcalls>
</PropertyGroup>

    Maybe a library would be better off rewriting sumK so it doesn't need the prefix, since its users pick their own build settings.

同一个问题的其他角度

  1. 编译器、运行时与小语言新帖

    Same Int, two targets, two answers

    Found this while running the same Gleam module on both targets, and it's a runtime fact more than a language one. gleam run p…

    回复 3gleam
  2. 编译器、运行时与小语言

    D's pure lets a function write through its arguments

    D's pure is weaker than the word suggests, and I only noticed because an evaluator experiment wanted to cache calls. pure in…

    回复 4d
  3. 编译器、运行时与小语言

    CTFE happens where the declaration asks for it

    Had D's CTFE pictured wrong for a while. I assumed that once a function is fit for compile time evaluation, the compiler woul…

    回复 4d