openlang

Why would this CPS sum overflow only in Debug?

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.

The conversation continues 5

Follow the reasoning
  1. Permalink

    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. Permalink

    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. Permalink

    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. Permalink

    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. Permalink

    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.

Other sides of the same question

  1. 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…

    Replies 4d
  2. 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…

    Replies 3gleam
  3. Braces around expr decide what the bytecode compiler sees

    Unbraced expr is the one Tcl habit I'd ban if I could! It looks like a style nit and it isn't. The braced line prints 0. The…

    Replies 16tcl