Глава 26 Трансформация программы «Конструктор хвоста по модулю»

• 26.1 Разъяснение неоднозначности
• 26.2 Опасность выхода за пределы преобразований хвоста по модулю
• 26.3 Подробности преобразования
• 26.4 Текущие ограничения

(Введено в 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.

# List.length (map Fun.id (List.init 1_000_000 Fun.id));;

- : int = 1000000

В этой реализации 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 из исходного кода в исходный код, поскольку оно зависит от изменяемого состояния нетипизированными способами. В отличие от этого, версии в стиле с продолжениями можно написать вручную, возможно, используя удобную монодическую нотацию.

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

26.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 positionin 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 positionin 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 positionin 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)

26.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 не имеет версии в стиле передачи в целевой параметр, вызов преобразуется в не-хвостовой вызов.

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

Локальное преобразование первого порядка

Когда функция преобразуется с помощью tail-mod-cons, генерируются два определения: одно обеспечивает интерфейс прямого стиля, а другое — версию в стиле передачи в целевой параметр. Однако не все вызовы этой функции в хвостовой модульно-конструкторной позиции будут использовать версию в стиле передачи в целевой параметр и станут хвостовыми вызовами:

• Преобразование локальное: только хвостовые модульно-конструкторные вызовы foo в том же модуле компиляции, что и foo, становятся хвостовыми вызовами.
• Преобразование первого порядка: только прямые вызовы известных функций tail-mod-cons в хвостовой модульно-конструкторной позиции становятся хвостовыми вызовами, а не вызовы параметрам функций.

Например, рассмотрим вызов Option.map foo x: даже если foo вызывается в хвостовой модульно-конструкторной позиции внутри определения Option.map, этот вызов никогда не станет хвостовым вызовом. (Так бы было даже если бы вызов Option.map находился внутри модуля Option.)

Как правило, это ограничение не является проблемой для рекурсивных функций: первый вызов из внешнего модуля или высшего порядка функции будет потреблять место в стеке, но последующие рекурсивные вызовы в хвостовой модульно-конструкторной позиции будут оптимизированы. Например, если List.map определена как функция tail-mod-cons, вызовы извне модуля List не станут хвостовыми вызовами, когда находятся в хвостовой позиции, но рекурсивные вызовы внутри определения List.map находятся в хвостовой модульно-конструкторной позиции и становятся хвостовыми вызовами: обработка первого элемента списка будет потреблять место в стеке, но все последующие элементы обрабатываются в постоянном пространстве.

Эти ограничения могут возникнуть в более сложных ситуациях, когда взаимная рекурсия происходит между функциями, некоторые функции не аннотированы tail-mod-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-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