Глава 26 Преобразование программы «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 не находится в хвостовой позиции. Система выполнения должна запомнить, как продолжить с y :: r после возврата значения 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 рекурсивный вызов происходит не в хвостовой позиции программы, а в позиции приложения конструктора данных, который сам находится в хвостовой позиции. Говорят, что эти позиции, составленные из хвостовых позиций и приложений конструкторов, являются позициями хвоста по модулю конструктора (TMC) — иногда для краткости пишут хвост по модулю союза.
Можно переписать программы таким образом, что позиции хвоста по модулю союза станут хвостовыми позициями; после этого преобразования реализация 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
Это преобразование улучшает только вызовы в позиции хвоста по модулю союза, оно не улучшает рекурсивные вызовы, которые не подходят под этот фрагмент:
(* 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] для функций, содержащих некоторые рекурсивные вызовы в позиции хвоста по модулю союза и некоторые вызовы в других произвольных позициях. Только хвостовые вызовы и вызовы хвоста по модулю союза будут происходить в постоянном пространстве стека.
Общая конструкция
Эта функция предоставляется как явное преобразование программы, а не как неявная оптимизация. Она основана на аннотациях: ожидается, что пользователь выразит свои намерения, добавив аннотации в программу с помощью атрибутов, и ему будет предложено это сделать в любой неоднозначной ситуации.
Ожидается, что он будет использоваться в основном опытными пользователями 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
Эта версия хвостово-рекурсивна, но заметно медленнее, чем простая, не хвостово-рекурсивная версия. В отличие от этого, преобразование хвост-модуль-конс предоставляет реализацию, которая имеет сопоставимую производительность с исходной версией даже при небольших входных данных.
Порядок оценки
Следует быть осторожным, так как преобразование хвоста по модулю конструктора влияет на порядок оценки: аргумент конструктора, который преобразуется в хвостовую позицию, всегда оценивается последним. Рассмотрим следующий пример:
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 не определен, но многие реализации обычно используют слева направо или справа налево).
Это влияние на порядок оценки является одной из причин, по которой преобразование хвоста по модулю конструктора должно быть явно запрошено пользователем, а не применяться как автоматическая оптимизация.
Почему хвост по модулю конструктора?
Другие преобразования программ, в частности, преобразование в стиль с передачей продолжения (CPS), могут сделать все функции хвостово-рекурсивными вместо того, чтобы нацеливаться только на небольшой фрагмент. Некоторые причины для предоставления встроенной поддержки для менее общего хвоста по модулю конструктора следующие:
- Преобразование хвоста по модулю конструктора сохраняет производительность исходной, не хвостово-рекурсивной версии, в то время как преобразование в стиль с передачей продолжения влечет за собой измеримую постоянную накладные расходы.
- Преобразование хвоста по модулю конструктора нельзя выразить как преобразование исходного кода программ OCaml, поскольку оно зависит от изменяемого состояния нетипизированным образом. В отличие от этого, версии в стиле с передачей продолжения можно написать вручную, возможно, используя удобную монодическую нотацию.
Примечание: Размер стека вызовов OCaml
В OCaml 4.x и более ранних версиях программы байткода учитывают конфигурацию параметра времени выполнения stack_limit (как установлено с помощью Gc.set в примере выше) или настройку l переменной OCAMLRUNPARAM. Программы нативного кода игнорируют эти настройки и учитывают только ограничение стека операционной системы, установленное ulimit на системах Unix. Большинство операционных систем запускаются с относительно низким значением ограничения размера стека по умолчанию, поэтому переполнение стека в не хвостово-рекурсивных функциях — распространенная ошибка программирования.
Начиная с OCaml 5.0, код нативного уровня больше не использует системный стек для вызовов функций OCaml, поэтому он не зависит от размера системного стека операционной системы; и программы байткода, и программы нативного кода учитывают собственное ограничение времени выполнения OCaml. Предельное значение времени выполнения установлено по умолчанию на гораздо более высокое значение, чем большинство системных стеков операционных систем, с лимитом не менее 512 МБ, поэтому переполнение стека должно быть значительно реже на практике. По-прежнему существует предельное значение стека по умолчанию, поскольку оно по-прежнему полезно для быстрого выявления ошибок с циклическими не хвостово-рекурсивными функциями. Без предела стека приходится ждать, пока весь объем памяти не будет заполнен стеком, прежде чем программа аварийно завершит работу, что может занять много времени и сделать систему невосприимчивой.
Это означает, что преобразование «хвост по модулю конструктора» менее важно в OCaml 5: оно заметно улучшает производительность в некоторых случаях, но для базовой правильности в большинстве случаев оно не требуется.
1 Разрешение неоднозначностей
Может случиться, что несколько аргументов конструктора являются рекурсивными вызовами функции хвоста по модулю конструктора. Преобразование может преобразовать только один из этих вызовов в хвостовой вызов. Компилятор не будет делать неявного выбора, а попросит пользователя предоставить явное разрешение неоднозначности.
Рассмотрим этот тип синтаксических выражений (предполагая некоторый предварительно существующий тип 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 Опасность выхода за пределы хвостового-модуль-конса
Ввиду характера преобразования хвостового-модуль-конса (см. раздел 26.3 для представления преобразования):
- Вызовы из функции, помеченной хвостовым-модуль-консом, в другую функцию, помеченную хвостовым-модуль-консом, и объявленную в той же группе рекурсивных связей, преобразуются в хвостовые вызовы, как только они появляются в хвостовой позиции или хвостовой-модуль-конс позиции в исходной функции.
- Вызовы из функции, не помеченной хвостовым-модуль-консом, в функцию, помеченную хвостовым-модуль-консом, или, наоборот, из функции, помеченной хвостовым-модуль-консом, в функцию, не помеченную хвостовым-модуль-консом, преобразуются в не-хвостовые вызовы, даже если они синтаксически появляются в хвостовой позиции в исходной программе.
Тот факт, что вызовы в хвостовой позиции в исходной программе могут стать не-хвостовыми вызовами, если они переходят от функции, помеченной хвостовым-модуль-консом, к функции, не помеченной хвостовым-модуль-консом, является неожиданным, и преобразование будет предупреждать об этом.
Например:
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 как хвостовой-модуль-конс.
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 является функцией без аннотации хвостового-модуль-конса в той же группе рекурсии; использование преобразования хвостового-модуль-конса является свойством отдельных функций, а не целых рекурсивных групп.
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)
В других случаях нет пользы от того, чтобы сделать вызываемую функцию хвостовым-модуль-консом, или это невозможно: например, это параметр функции (преобразование работает только с прямыми вызовами известных функций).
Например, рассмотрим функцию подстановки для бинарных деревьев:
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 — параметр функции, а не прямой вызов, и текущая реализация строго первого порядка, она не поддерживает аргументы хвостового-модуль-конса. В этом случае пользователь должен указать, что этот вызов 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. (Преобразование фактически происходит в лямбда-представлении промежуточного кода компилятора 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.
Это объясняет тонкости «выхода за пределы хвостового-модуль-конса». Рассмотрим наш предыдущий пример, связанный с взаимной рекурсией между 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 Текущие ограничения
Чисто синтаксический критерий
Как и хвостовые вызовы в целом, понятие хвостовой-модуль-конс позиции является чисто синтаксическим; некоторые простые изменения перестановки перемещают вызовы за пределы хвостовой-модуль-конс позиции.
(* 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. Локальное преобразование первого порядка
Когда функция преобразуется с использованием хвостового-модуль-конса, генерируются два определения: одно предоставляющее интерфейс прямого стиля, а другое — версию стиля передачи в назначение. Однако не все вызовы этой функции в хвостовой-модуль-конс позиции будут использовать версию стиля передачи в назначение и станут хвостовыми вызовами:
- Преобразование является локальным: только вызовы хвостового-модуль-конса в foo в том же модуле компиляции, что и foo, становятся хвостовыми вызовами.
- Преобразование является первого порядка: только прямые вызовы известных функций с аннотацией хвостового-модуль-конса становятся хвостовыми вызовами, когда находятся в хвостовой-модуль-конс позиции, никогда не вызовы параметров функций.
Рассмотрим вызов Option.map foo x, например: даже если foo вызывается в хвостовой-модуль-конс позиции внутри определения Option.map, этот вызов никогда не станет хвостовым вызовом. (Это было бы верно, даже если вызов Option.map находился внутри модуля Option.)
В общем случае это ограничение не является проблемой для рекурсивных функций: первый вызов из внешнего модуля или функции высшего порядка будет потреблять место в стеке, но последующие рекурсивные вызовы в хвостовой-модуль-конс позиции будут оптимизированы. Например, если List.map определен как функция с аннотацией хвостового-модуль-конса, вызовы извне модуля List не станут хвостовыми вызовами, когда находятся в хвостовой позиции, но рекурсивные вызовы внутри определения List.map находятся в хвостовой-модуль-конс позициях и становятся хвостовыми вызовами: обработка первого элемента списка будет потреблять место в стеке, но все последующие элементы обрабатываются с постоянным размером.
Эти ограничения могут возникнуть в более сложных ситуациях, когда взаимная рекурсия происходит между функциями, некоторые функции не помечены как хвостовой-модуль-конс, или определены в разных модулях, или вызываются косвенно, например, через параметры функций.
Неточные вызовы к кортежным функциям
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-mod-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-2024 INRIA.
https://ocaml.org/manual/5.2/tail_mod_cons.html
