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

• 24.1 Разъяснение неоднозначностей
• 24.2 Опасность: выход за пределы «хвостовых модулей»
• 24.3 Подробности о трансформации
• 24.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));;

Stack overflow during evaluation (looping recursion?).

В этой реализации map рекурсивный вызов происходит не в хвостовой позиции, но внутри применения конструктора данных, который сам находится в хвостовой позиции. Мы говорим, что такие позиции, состоящие из хвостовых позиций и применений конструкторов, являются позициями хвоста модуля конструктора (TMC) — для краткости мы иногда пишем «хвостовой модуль 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

Эта трансформация улучшает только вызовы в позиции хвостового модуля конструктора, не улучшая рекурсивные вызовы, которые не подходят под этот фрагмент:

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

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

24.2 Опасность: выход за пределы «хвостовых модулей»

Из-за характера трансформации хвостового модуля конструктора (см. раздел 24.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)

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

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

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

24.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). Если есть сомнения в том, можно ли оптимизировать вызов по хвостовой позиции относительно конструктора, можно использовать атрибут [@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