openlang

Почему эта сумма в стиле CPS переполняет стек только в Debug?

Проверьте, пожалуйста, правильно ли я это понимаю. Сумма в стиле передачи продолжений, написанная как упражнение.

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 печатает 1000000. Обычный dotnet run, то есть Debug, падает с переполнением стека. Тот же исходник, та же машина. Подозреваю хвостовые вызовы, ведь все вызовы там в хвостовой позиции, но не знаю, какая часть сборки это решает. Может, честное решение - что-то включить для Debug, а может, код вообще не должен на это полагаться.

Переведено с английскогоПоказать оригинал

Разговор продолжается 5

Следуя доводам
  1. Ссылка на ответ

    В Debug хвостовые вызовы выключены, в Release включены. Вызов sumK самой себя в любом случае компилируется в переход, так что цепочка строится нормально. Переполняется k (s + x), вызов через замыкание в хвостовой позиции. Без хвостовых вызовов это обычный callvirt без префикса tail., и когда наконец выполняется k 0, миллион замыканий добавляют по кадру. Переключатель - свойство Tailcalls в проекте, в командной строке --tailcalls.

    Переведено с английскогоПоказать оригинал
  2. Ссылка на ответ

    Выходит, один и тот же текст в одной конфигурации - работающая программа, а в другой - падение. Гарантия хвостового вызова оказывается на уровне сборки, а это странный уровень для того, от чего зависит смысл программы. Атрибут [<TailCall>] выглядит решением на правильном уровне. Если пометить им sumK, требование будет записано в исходнике, так что Debug-сборке тоже придётся выдавать префикс.

    Переведено с английскогоПоказать оригинал
  3. Ссылка на ответ

    На это была надежда, и это первое, что пошло в ход. [<TailCall>] только добавляет проверку. Компилятор предупреждает, если рекурсивный вызов помеченной функции не в хвостовой позиции, а генерируемый код не меняется. На sumK он молчит, потому что рекурсивный вызов и так в хвостовой позиции, и Debug-сборка переполняется точно так же. К тому же проблемные замыкания вообще не являются помеченной функцией.

    Переведено с английскогоПоказать оригинал
  4. Ссылка на ответ

    Debug их выключает просто по привычке или есть причина? Подозреваю, что дело в стеке вызовов. Кадр, замещённый хвостовым вызовом, исчезает, и отладчик и трассировки исключений эти шаги пропускают, а ради этого вида Debug и запускают. Если так, то включить Tailcalls в Debug значит отдать часть этого вида за работающую программу, и это скорее решение для конкретного проекта, чем умолчание, которое стоит менять везде.

    Переведено с английскогоПоказать оригинал
  5. Ссылка на ответ

    Похоже на правду. В этом проекте программа сама зависит от хвостовых вызовов, так что они включены в обеих конфигурациях, и Debug теперь тоже печатает 1000000.

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

    Возможно, библиотеке лучше переписать sumK так, чтобы префикс был не нужен, ведь настройки сборки выбирают её пользователи.

    Переведено с английскогоПоказать оригинал

Другие стороны того же вопроса

  1. CTFE срабатывает там, где этого требует объявление

    У меня долго была неправильная картина CTFE в D. Казалось, что если функция годится для вычисления при компиляции, компилятор…

    Ответы 4d
  2. Один Int, две платформы, два ответа

    Это всплыло при запуске одного и того же модуля Gleam на обеих целевых платформах, и это скорее факт о среде выполнения, чем…

    Ответы 3gleam
  3. Фигурные скобки вокруг expr решают, что видит компилятор байткода

    expr без фигурных скобок - единственная привычка в Tcl, которую хочется запретить! Выглядит как придирка к стилю, а на деле н…

    Ответы 16tcl