Глава 27 Преобразование программы «Tail Modulo Constructor»
(Добавлено в OCaml 4.14)
Примечание. Эта возможность считается экспериментальной, и в следующих нескольких выпусках языка её интерфейс может меняться с учётом отзывов пользователей.
Рассмотрим естественную реализацию функции List.map:
let rec map f l =
match l with
| [] -> []
| x :: xs ->
let y = f x in
y :: map f xs
Хорошо известное ограничение этой реализации состоит в том, что рекурсивный вызов map f xs не находится в хвостовой позиции. Среде выполнения нужно сохранить информацию о том, что после возврата значения r вызов должен продолжиться с y :: r, поэтому при каждом рекурсивном вызове эта функция расходует некоторое количество места в стеке вызовов. Использование стека вызовом map f li пропорционально длине li. На системах с ограниченным объёмом стека это может приводить к проблемам корректности при обработке больших списков — к печально известному исключению Stack_overflow.
# let with_stack_limit stack_limit f =
let old_gc_settings = Gc.get () in
Gc.set { old_gc_settings with stack_limit };
Fun.protect ~finally:(fun () -> Gc.set old_gc_settings) f
;;
val with_stack_limit : int -> (unit -> 'a) -> 'a = # with_stack_limit 20_000 (fun () ->
List.length (map Fun.id (List.init 1_000_000 Fun.id))
);;
Stack overflow during evaluation (looping recursion?). В этой реализации map рекурсивный вызов выполняется в позиции, которая не является хвостовой в программе, но находится внутри применения конструктора типа данных, которое само расположено в хвостовой позиции. Мы называем позиции, составленные из хвостовых позиций и применений конструкторов, позициями tail modulo constructor (TMC); для краткости иногда используется название tail modulo cons.
Программы можно преобразовать так, чтобы позиции tail modulo cons стали хвостовыми позициями; после такого преобразования приведённая выше реализация map станет хвостово-рекурсивной, то есть будет потреблять лишь постоянное количество места в стеке. Компилятор OCaml выполняет это преобразование по запросу, используя атрибут [@tail_mod_cons] или [@ocaml.tail_mod_cons] функции, которую нужно преобразовать.
let[@tail_mod_cons] rec map f l =
match l with
| [] -> []
| x :: xs ->
let y = f x in
y :: map f xs
# List.length (map Fun.id (List.init 1_000_000 Fun.id));; - : int = 1000000
Это преобразование улучшает только вызовы в позиции tail modulo cons; оно не улучшает рекурсивные вызовы, которые не соответствуют этому шаблону:
(* does *not* work: addition is not a data constructor *) let[@tail_mod_cons] rec length l = match l with | [] -> 0 | _ :: xs -> 1 + length xs Warning 71 [unused-tmc-attribute]: This function is marked @tail_mod_cons but is never applied in TMC position.
Разумеется, преобразование [@tail_mod_cons] можно применять к функциям, содержащим одни рекурсивные вызовы в позиции tail modulo cons, а другие — в произвольных позициях. Только хвостовые вызовы и вызовы в позиции tail modulo cons будут потреблять постоянное количество места в стеке.
Общая концепция
Эта возможность предоставляется как явное преобразование программы, а не как неявная оптимизация. Преобразование управляется аннотациями: ожидается, что пользователь выразит своё намерение, добавив в программу атрибуты, а в неоднозначных ситуациях ему будет предложено это сделать.
Мы ожидаем, что этой возможностью будут пользоваться главным образом опытные пользователи OCaml, которым необходимо гарантировать определённое поведение своих программ с точки зрения использования стека. Мы рекомендуем использовать аннотацию [@tailcall] для всех мест вызова, которые не должны потреблять место в стеке. Аннотация [@tail_mod_cons] расширяет набор функций, вызовы которых можно аннотировать как хвостовые, помогая в большем количестве случаев гарантировать использование стека.
Производительность
Стандартный способ получить хвостово-рекурсивную версию List.map — использовать аккумулятор для сбора выходных элементов и обратить список в конце обхода.
let rec map f l = map_aux f [] l
and map_aux f acc l =
match l with
| [] -> List.rev acc
| x :: xs ->
let y = f x in
map_aux f (y :: acc) xs
Эта версия хвостово-рекурсивна, но заметно медленнее простой версии без хвостовой рекурсии. В отличие от неё, преобразование tail modulo cons обеспечивает реализацию с производительностью, сопоставимой с исходной версией, даже на небольших входных данных.
Порядок вычисления
Следует учитывать, что преобразование tail modulo cons влияет на порядок вычисления: аргумент конструктора, преобразованный в хвостовую позицию, всегда будет вычисляться последним. Рассмотрим следующий пример:
type 'a two_headed_list =
| Nil
| Consnoc of 'a * 'a two_headed_list * 'a
let[@tail_mod_cons] rec map f = function
| Nil -> Nil
| Consnoc (front, body, rear) ->
Consnoc (f front, map f body, f rear)
Из-за преобразования [@tail_mod_cons] вызовы f front и f rear будут вычислены до map f body. В частности, этот порядок, вероятно, будет отличаться от порядка вычисления версии без аннотации. (Порядок вычисления аргументов конструктора в OCaml не определён, однако во многих реализациях обычно используется порядок слева направо или справа налево.)
Это влияние на порядок вычисления — одна из причин, по которым преобразование tail modulo cons должно явно запрашиваться пользователем, а не применяться автоматически как оптимизация.
Почему tail modulo cons?
Другие преобразования программ, в частности преобразование в стиль передачи продолжений (CPS), позволяют сделать хвостово-рекурсивными все функции, а не только небольшой класс функций. Ниже перечислены некоторые причины встроенной поддержки менее универсального преобразования tail modulo cons:
- Преобразование tail modulo cons сохраняет производительность исходной версии без хвостовой рекурсии, тогда как преобразование в стиль передачи продолжений создаёт измеримые постоянные накладные расходы.
- Преобразование tail modulo cons нельзя выразить как преобразование программ OCaml из исходного кода в исходный, поскольку оно опирается на изменяемое состояние небезопасным с точки зрения типов образом. В отличие от него, версии в стиле передачи продолжений можно написать вручную, возможно, используя удобную монаду.
Примечание. Размер стека вызовов OCaml
В OCaml 4.x и более ранних версиях байт-кодовые программы учитывают конфигурацию параметра среды выполнения stack_limit (задаваемую с помощью Gc.set, как в примере выше) или настройку l переменной OCAMLRUNPARAM. Программы с машинным кодом игнорируют эти настройки и учитывают только ограничение размера стека, установленное операционной системой, например с помощью ulimit в Unix. В большинстве операционных систем по умолчанию действует относительно небольшое ограничение размера стека, поэтому переполнение стека в функциях без хвостовой рекурсии — распространённая ошибка программирования.
Начиная с OCaml 5.0, машинный код больше не использует системный стек для вызовов функций OCaml, поэтому размер системного стека операционной системы на него не влияет; и машинные, и байт-кодовые программы учитывают собственное ограничение среды выполнения OCaml. По умолчанию это ограничение гораздо выше, чем размер стека в большинстве операционных систем, — не менее 512 МиБ, поэтому на практике переполнение стека должно происходить гораздо реже. По умолчанию ограничение на размер стека всё ещё существует, поскольку оно позволяет быстро обнаруживать ошибки в зацикленных функциях без хвостовой рекурсии. Без такого ограничения пришлось бы ждать, пока стек займёт всю память и программа аварийно завершится; это может занять много времени и привести к зависанию системы.
Это означает, что в OCaml 5 преобразование tail modulo constructor менее важно: в некоторых случаях оно заметно повышает производительность, но для базовой корректности в большинстве сценариев использования оно не требуется.
1 Устранение неоднозначности
Может оказаться, что несколько аргументов конструктора являются рекурсивными вызовами функции tail modulo cons. Преобразовать в хвостовой вызов можно только один из них. Компилятор не будет делать выбор неявно, а попросит пользователя явно устранить неоднозначность.
Рассмотрим такой тип синтаксических выражений (предполагая, что уже определён некоторый тип var для переменных-выражений):
type var (* some pre-existing type of variables *) type exp = | Var of var | Let of binding * exp and binding = var * exp
Рассмотрим функцию map для переменных. Её прямое определение содержит два рекурсивных вызова в аргументах конструктора Let, поэтому компилятор отклонит его как неоднозначное.
let[@tail_mod_cons] rec map_vars f exp =
match exp with
| Var v -> Var (f v)
| Let ((v, def), body) ->
Let ((f v, map_vars f def), map_vars f body)
Error: [@tail_mod_cons]: this constructor application may be TMC-transformed
in several different ways. Please disambiguate by adding an explicit
[@tailcall] attribute to the call that should be made tail-recursive,
or a [@tailcall false] attribute on calls that should not be
transformed.
This call could be annotated.
This call could be annotated. Чтобы устранить неоднозначность, пользователь должен добавить атрибут [@tailcall] к тому рекурсивному вызову, который следует преобразовать в хвостовую позицию:
let[@tail_mod_cons] rec map_vars f exp =
match exp with
| Var v -> Var (f v)
| Let ((v, def), body) ->
Let ((f v, map_vars f def), (map_vars[@tailcall]) f body)
Учтите, что полученная функция не является хвостово-рекурсивной: рекурсивный вызов для def будет потреблять место в стеке. Однако деревья выражений обычно имеют наклон вправо (много конструкций Let в последовательности, а не вложенных друг в друга), поэтому перевод вызова для body в хвостовую позицию — полезное улучшение по сравнению с наивным определением: использование стека будет ограниченным, если предположить, что глубина вложенности конструкций Let ограничена.
При использовании конфликтующих аннотаций, требующих поместить в хвостовую позицию два аргумента конструктора, также возникнет ошибка:
let[@tail_mod_cons] rec map_vars f exp =
match exp with
| Var v -> Var (f v)
| Let ((v, def), body) ->
Let ((f v, (map_vars[@tailcall]) f def), (map_vars[@tailcall]) f body)
Error: [@tail_mod_cons]: this constructor application may be TMC-transformed
in several different ways. Only one of the arguments may become a TMC
call, but several arguments contain calls that are explicitly marked
as tail-recursive. Please fix the conflict by reviewing and fixing the
conflicting annotations.
This call is explicitly annotated.
This call is explicitly annotated. 2 Внимание: выход из tail modulo cons
Из-за особенностей преобразования tail modulo cons (описание преобразования приведено в разделе 27.3):
- Вызовы из функции tail modulo cons к другой функции tail modulo cons, объявленной в той же группе рекурсивных привязок, преобразуются в хвостовые вызовы, если в исходной функции они находятся в хвостовой позиции или в позиции tail modulo cons.
- Вызовы из функции, не аннотированной как tail modulo cons, к функции tail modulo cons или, наоборот, из функции tail modulo cons к функции, не являющейся tail modulo cons, преобразуются в нехвостовые вызовы, даже если синтаксически в исходной программе они находятся в хвостовой позиции.
Неожиданно, но вызовы, находящиеся в хвостовой позиции в исходной программе, могут стать нехвостовыми, если они ведут из функции tail modulo cons в функцию, не являющуюся tail modulo cons; преобразование выдаст об этом предупреждение.
Например:
let[@tail_mod_cons] rec flatten = function
| [] -> []
| xs :: xss ->
let rec append_flatten xs xss =
match xs with
| [] -> flatten xss
| x :: xs -> x :: append_flatten xs xss
in append_flatten xs xss
Warning 71 [unused-tmc-attribute]: This function is marked @tail_mod_cons
but is never applied in TMC position.
Warning 72 [tmc-breaks-tailcall]: This call is in tail-modulo-cons position
in a TMC function, but the function called is not itself specialized for
TMC, so the call will not be transformed into a tail call.
Please either mark the called function with the [@tail_mod_cons] attribute,
or mark this call with the [@tailcall false] attribute to make its
non-tailness explicit. Здесь вспомогательная функция append_flatten не аннотирована атрибутом [@tail_mod_cons], поэтому вызовы append_flatten xs xss и flatten xss не будут хвостовыми. Правильное решение — аннотировать append_flatten как tail modulo cons.
let[@tail_mod_cons] rec flatten = function
| [] -> []
| xs :: xss ->
let[@tail_mod_cons] rec append_flatten xs xss =
match xs with
| [] -> flatten xss
| x :: xs -> x :: append_flatten xs xss
in append_flatten xs xss
Это же предупреждение возникает, когда append_flatten — функция, не являющаяся tail modulo cons, в той же рекурсивной группе: использование преобразования tail modulo cons определяется для отдельных функций, а не для целых рекурсивных групп.
let[@tail_mod_cons] rec flatten = function | [] -> [] | xs :: xss -> append_flatten xs xss and append_flatten xs xss = match xs with | [] -> flatten xss | x :: xs -> x :: append_flatten xs xss Warning 71 [unused-tmc-attribute]: This function is marked @tail_mod_cons but is never applied in TMC position. Warning 72 [tmc-breaks-tailcall]: This call is in tail-modulo-cons position in a TMC function, but the function called is not itself specialized for TMC, so the call will not be transformed into a tail call. Please either mark the called function with the [@tail_mod_cons] attribute, or mark this call with the [@tailcall false] attribute to make its non-tailness explicit.
И здесь решение — также специализированно преобразовать append_flatten:
let[@tail_mod_cons] rec flatten = function | [] -> [] | xs :: xss -> append_flatten xs xss and[@tail_mod_cons] append_flatten xs xss = match xs with | [] -> flatten xss | x :: xs -> x :: append_flatten xs xss
Атрибут [@tail_mod_cons] можно добавлять и к нерекурсивным функциям; это обычно полезно для локальных привязок рекурсивных функций.
Неправильный вариант:
let[@tail_mod_cons] rec map_vars f exp =
let self exp = map_vars f exp in
match exp with
| Var v -> Var (f v)
| Let ((v, def), body) ->
Let ((f v, self def), (self[@tailcall]) body)
Warning 51 [wrong-tailcall-expectation]: expected tailcall
Warning 51 [wrong-tailcall-expectation]: expected tailcall
Warning 71 [unused-tmc-attribute]: This function is marked @tail_mod_cons
but is never applied in TMC position. Рекомендуемое решение:
let[@tail_mod_cons] rec map_vars f exp =
let[@tail_mod_cons] self exp = map_vars f exp in
match exp with
| Var v -> Var (f v)
| Let ((v, def), body) ->
Let ((f v, self def), (self[@tailcall]) body)
В других случаях преобразование вызываемой функции в tail modulo cons либо не принесёт пользы, либо невозможно. Например, функция может быть параметром (преобразование работает только с прямыми вызовами известных функций).
Рассмотрим, например, функцию подстановки для двоичных деревьев:
type 'a tree = Leaf of 'a | Node of 'a tree * 'a tree
let[@tail_mod_cons] rec bind (f : 'a -> 'a tree) (t : 'a tree) : 'a tree =
match t with
| Leaf v -> f v
| Node (left, right) ->
Node (bind f left, (bind[@tailcall]) f right)
Warning 72 [tmc-breaks-tailcall]: This call is in tail-modulo-cons position
in a TMC function, but the function called is not itself specialized for
TMC, so the call will not be transformed into a tail call.
Please either mark the called function with the [@tail_mod_cons] attribute,
or mark this call with the [@tailcall false] attribute to make its
non-tailness explicit. Здесь f — параметр-функция, а не прямой вызов; текущая реализация поддерживает только функции первого порядка и не обрабатывает аргументы tail modulo cons. В этом случае пользователь должен явно указать, что понимает: вызов f v на самом деле не является хвостовым, используя (f[@tailcall false]) v.
type 'a tree = Leaf of 'a | Node of 'a tree * 'a tree
let[@tail_mod_cons] rec bind (f : 'a -> 'a tree) (t : 'a tree) : 'a tree =
match t with
| Leaf v -> (f[@tailcall false]) v
| Node (left, right) ->
Node (bind f left, (bind[@tailcall]) f right)
3 Подробности преобразования
Чтобы использовать эту расширенную возможность, полезно знать, что в результате преобразования функции создаётся специализированная функция в стиле передачи результата по назначению.
Вспомним наш пример с map:
let rec map f l =
match l with
| [] -> []
| x :: xs ->
let y = f x in
y :: map f xs
Ниже приведено описание преобразованной программы в псевдосинтаксисе OCaml: некоторые операции невозможно выразить в исходном коде OCaml. (На самом деле преобразование выполняется над промежуточным представлением Lambda компилятора OCaml.)
let rec map f l =
match l with
| [] -> []
| x :: xs ->
let y = f x in
let dst = y ::{mutable} Hole in
map_dps f xs dst 1;
dst
and map_dps f l dst idx =
match l with
| [] -> dst.idx <- []
| x :: xs ->
let y = f x in
let dst' = y ::{mutable} Hole in
dst.idx <- dst';
map_dps f xs dst' 1
Исходная версия map преобразуется в две функции: версию в прямом стиле, которая также называется map, и версию в стиле передачи результата по назначению (DPS), называемую map_dps. Версия в стиле передачи результата по назначению не возвращает результат напрямую, а записывает его в область памяти, указанную двумя дополнительными параметрами функции: dst (блок памяти) и i (позиция внутри блока памяти).
Исходный вызов y :: map f xs преобразуется в создание изменяемого блока y ::{mutable} Hole, второй параметр которого представляет собой неинициализированную дыру. Затем этот блок передаётся в map_dps как параметр назначения (со смещением 1).
Обратите внимание, что map не вызывает себя рекурсивно, а вызывает map_dps. Затем map_dps вызывает себя рекурсивно, причём хвостовым образом.
Вызов из map в map_dps не является хвостовым (в будущем это можно будет улучшить); однако этот вызов выполняется только один раз при вызове map f l, а все элементы списка после первого обрабатываются функцией map_dps с постоянным использованием стека.
Это объясняет тонкости, связанные с «выходом из tail modulo cons». Рассмотрим предыдущий пример с взаимной рекурсией между функциями flatten и append_flatten.
let[@tail_mod_cons] rec flatten l =
match l with
| [] -> []
| xs :: xss ->
append_flatten xs xss
Вызов append_flatten, который синтаксически находится в хвостовой позиции, преобразуется по-разному в зависимости от того, доступна ли для функции версия в стиле передачи результата по назначению, то есть аннотирована ли она сама атрибутом [@tail_mod_cons]:
(* if append_flatten_dps exists *)
and flatten_dps l dst i =
match l with
| [] -> dst.i <- []
| xs :: xss ->
append_flatten_dps xs xss dst i
(* if append_flatten_dps does not exist *)
and rec flatten_dps l dst i =
match l with
| [] -> dst.i <- []
| xs :: xss ->
dst.i <- append_flatten xs xss
Если для append_flatten нет версии в стиле передачи результата по назначению, вызов преобразуется в нехвостовой.
4 Текущие ограничения
Чисто синтаксический критерий
Как и понятие хвостового вызова в целом, понятие позиции tail modulo constructor является чисто синтаксическим; при простом рефакторинге вызовы могут выйти из позиции tail modulo constructor.
(* works as expected *)
let[@tail_mod_cons] rec map f li =
match li with
| [] -> []
| x :: xs ->
let y = f x in
y ::
(* this call is in TMC position *)
map f xs
(* not optimizable anymore *)
let[@tail_mod_cons] rec map f li =
match li with
| [] -> []
| x :: xs ->
let y = f x in
let ys =
(* this call is not in TMC position anymore *)
map f xs in
y :: ys
Warning 71 [unused-tmc-attribute]: This function is marked @tail_mod_cons
but is never applied in TMC position. Локальное преобразование первого порядка
При преобразовании функции с помощью tail modulo cons создаются два определения: одно предоставляет интерфейс в прямом стиле, а другое — версию в стиле передачи результата по назначению. Однако не все вызовы этой функции в позиции tail modulo cons будут использовать версию в стиле передачи результата по назначению и становиться хвостовыми:
- Преобразование является локальным: хвостовыми становятся только вызовы foo в позиции tail modulo cons, находящиеся в той же единице компиляции, что и foo.
- Преобразование поддерживает только функции первого порядка: хвостовыми в позиции tail modulo cons становятся только прямые вызовы известных функций tail modulo cons, но не вызовы параметров-функций.
Рассмотрим, например, вызов Option.map foo x: даже если foo вызывается в позиции tail modulo cons внутри определения Option.map, этот вызов никогда не станет хвостовым. (Так будет, даже если вызов Option.map находится внутри модуля Option.)
Обычно это ограничение не представляет проблемы для рекурсивных функций: первый вызов из внешнего модуля или функции высшего порядка потребит место в стеке, но последующие рекурсивные вызовы в позиции tail modulo cons будут оптимизированы. Например, если List.map определена как функция tail modulo cons, вызовы из-за пределов модуля List не станут хвостовыми, даже если находятся в хвостовой позиции, но рекурсивные вызовы внутри определения List.map находятся в позициях tail modulo cons и становятся хвостовыми: обработка первого элемента списка потребит место в стеке, но все остальные элементы будут обработаны с постоянным использованием памяти.
В более сложных случаях эти ограничения могут стать проблемой, если функции взаимно рекурсивны, некоторые из них не аннотированы как tail modulo cons, определены в разных модулях или вызываются косвенно, например через параметры-функции.
Неточные вызовы функций с кортежными аргументами
В OCaml выполняется неявная оптимизация для функций, принимающих один параметр-кортеж: «кортежных» функций вида let f (x, y, z) = .... При прямых вызовах таких функций с литералом кортежа в качестве аргумента (например, f (a, b, c)) параметры передаются непосредственно в кортежную функцию, а сам кортеж не создаётся. Другие вызовы — как косвенные, так и передающие более сложное значение-кортеж (например, let t = (a, b, c) in f t) — компилируются как «неточные» вызовы через обёртку.
Преобразование [@tail_mod_cons] поддерживает кортежные функции, но оптимизирует только «точные» вызовы в хвостовой позиции; прямые вызовы с аргументом, отличным от литерала кортежа, хвостовыми не становятся. Пользователь может вручную распаковать кортеж, чтобы сделать вызов «точным»: let (x, y, z) = t in f (x, y, z). Если есть сомнения в том, можно ли оптимизировать вызов с помощью tail modulo cons, можно использовать атрибут [@tailcall] вызываемой функции: компилятор выдаст предупреждение, если преобразование невозможно.
let rec map (f, l) =
match l with
| [] -> []
| x :: xs ->
let y = f x in
let args = (f, xs) in
(* this inexact call cannot be tail-optimized, so a warning will be raised *)
y :: (map[@tailcall]) args
Warning 51 [wrong-tailcall-expectation]: expected tailcall
© 1995-2026 INRIA.
https://ocaml.org/manual/5.5/tail_mod_cons.html
