Когда нет ТШО, когда беспокоиться о том, чтобы унести стек?

14

Каждый раз, когда обсуждается новый язык программирования для JVM, неизбежно появляются люди, которые говорят что-то вроде:

«JVM не поддерживает оптимизацию хвостового вызова, поэтому я предсказываю множество взрывающихся стеков»

Есть тысячи вариаций на эту тему.

Теперь я знаю, что некоторые языки, такие как Clojure, например, имеют специальную конструкцию recur, которую вы можете использовать.

Что я не понимаю, так это: насколько серьезным является отсутствие оптимизации хвостового вызова? Когда я должен беспокоиться об этом?

Мой основной источник путаницы, вероятно, связан с тем фактом, что Java является одним из самых успешных языков за всю историю, и довольно много языков JVM работают довольно хорошо. Как это возможно , если отсутствие TCO действительно из любой озабоченности?

Седрик Мартин
источник
4
если у вас достаточно глубокая рекурсия, чтобы взорвать стек без TCO, у вас возникнут проблемы даже с TCO
чокнутый урод
18
@ratchet_freak Это чепуха. Схема даже не имеет циклов, но поскольку спецификация требует поддержки TCO, рекурсивная итерация по большому набору данных не дороже, чем императивный цикл (с тем бонусом, что конструкция Scheme возвращает значение).
itbruce
6
@ratchetfreak TCO - это механизм, позволяющий рекурсивным функциям, написанным определенным образом (т. е. хвостово-рекурсивно), быть полностью неспособным перебить стек, даже если они этого захотят. Ваше утверждение имеет смысл только для рекурсии, которая не написана хвостовой рекурсией, и в этом случае вы правы, и TCO вам не поможет.
Evicatos
2
Последнее, что я посмотрел, 80x86 также не выполняет (нативную) оптимизацию хвостового вызова. Но это не остановило разработчиков языков от переноса языков, которые его используют. Компилятор определяет, когда он может использовать переход по сравнению с JSR, и все счастливы. Вы можете сделать то же самое на JVM.
kdgregory
3
@kdgregory: Но у x86 есть GOTO, а у JVM нет. И x86 не используется в качестве платформы взаимодействия. У JVM нет, GOTOи одной из основных причин выбора платформы Java является взаимодействие. Если вы хотите реализовать TCO на JVM, вы должны что- то сделать со стеком. Управляй им сам (т.е. вообще не используй стек вызовов JVM), используй батуты, используй исключения как GOTO, что-то вроде этого. Во всех этих случаях вы становитесь несовместимыми со стеком вызовов JVM. Невозможно быть совместимым со стеком с Java, иметь TCO и высокую производительность. Вы должны пожертвовать одним из этих трех.
Йорг Миттаг

Ответы:

16

Подумайте об этом, скажем, мы избавились от всех циклов в Java (авторы компиляторов бастуют или что-то в этом роде). Теперь мы хотим написать факториал, чтобы мы могли исправить что-то вроде этого

int factorial(int i){ return factorial(i, 1);}
int factorial(int i, int accum){
  if(i == 0) return accum;
  return factorial(i-1, accum * i);
}

Теперь мы чувствуем себя довольно умно, нам удалось написать наш факториал даже без циклов! Но когда мы тестируем, мы замечаем, что при любом значении разумного размера мы получаем ошибки переполнения стека, поскольку TCO отсутствует.

В реальной Java это не проблема. Если у нас когда-либо есть хвостовой рекурсивный алгоритм, мы можем преобразовать его в цикл и все будет в порядке. Однако как насчет языков без петель? Тогда ты просто накрылся. Вот почему у clojure есть такая recurформа, без нее она даже не завершается (не существует бесконечных циклов).

Класс функциональных языков, нацеленных на JVM, Frege, Kawa (Scheme), Clojure, всегда старается справиться с отсутствием хвостовых вызовов, потому что в этих языках TC является идиоматическим способом создания циклов! Если перевести на Схему, этот факториал выше будет хорошим факториалом. Было бы ужасно неудобно, если зацикливание 5000 раз приводило к краху вашей программы. Однако это можно обойти, используя recurспециальные формы, аннотации, намекающие на оптимизацию собственных вызовов, прыжки на батуте, что угодно. Но все они вызывают либо снижение производительности, либо ненужную работу программиста.

Теперь Java тоже не становится бесплатной, поскольку для TCO есть нечто большее, чем просто рекурсия, как насчет взаимно рекурсивных функций? Они не могут быть прямо переведены в циклы, но все еще не оптимизированы JVM. Это делает невероятно неприятным пытаться писать алгоритмы с использованием взаимной рекурсии с использованием Java, поскольку, если вы хотите приличную производительность / диапазон, вы должны делать темную магию, чтобы она вписывалась в циклы.

Итак, в целом, это не так уж важно для многих случаев. Большинство хвостовых вызовов либо выполняются только на один стек, с такими вещами, как

return foo(bar, baz); // foo is just a simple method

или рекурсия. Однако для класса TC, который не вписывается в это, каждый язык JVM чувствует боль.

Однако есть веская причина, по которой у нас пока нет TCO. JVM дает нам трассировки стека. С TCO мы систематически исключаем стековые фреймы, которые, как мы знаем, «обречены», но JVM может на самом деле захотеть их позже для трассировки стека! Скажем, мы реализуем FSM, как это, где каждое состояние вызывает следующий. Мы удалили бы все записи о предыдущих состояниях, чтобы обратная связь показывала нам, в каком состоянии, но не о том, как мы туда попали.

Кроме того, и что еще более актуально, большая часть проверки байт-кода основывается на стеке, что исключает то, что позволяет нам проверять байт-код, не является приятной перспективой. Между этим и тем, что в Java есть циклы, TCO выглядит немного сложнее, чем это стоит инженерам JVM.

Даниэль Гратцер
источник
2
Самая большая проблема - это проверка байтового кода, которая полностью основана на проверке стека. Это серьезная ошибка в спецификации JVM. 25 лет назад, когда проектировалась JVM, люди уже говорили, что было бы лучше, если бы язык байт-кода JVM был в первую очередь безопасным, а не небезопасным, а затем полагался на проверку байтового кода после этого. Тем не менее, Матиас Феллайзен (одна из ведущих фигур в сообществе Scheme) написал документ, демонстрирующий, как можно добавить хвостовые вызовы в JVM при сохранении верификатора байтового кода.
Йорг Миттаг
2
Интересно, что J9 JVM от IBM действительно выполняют совокупную стоимость владения.
Йорг Миттаг
1
@jozefg Интересно, что никто не заботится о записях stacktrace для циклов, поэтому аргумент stacktrace не содержит воды, по крайней мере для хвостовых рекурсивных функций.
Инго
2
@MasonWheeler В этом и заключается моя точка зрения: трассировка стека не сообщает вам, в какой итерации это произошло. Вы можете увидеть это только косвенно, проверив переменные цикла и т. Д. Так зачем вам хотеть несколько записей трассировки стека hundert хвостовой рекурсивной функции? Интересно только последнее! И, как и в случае с циклами, вы можете определить, какая это была рекурсия, проверив локальные переменные, значения аргументов и т. Д.
Инго
3
@Ingo: если функция рекурсивна только сама с собой, трассировка стека может показывать немного. Однако, если группа функций является взаимно рекурсивной, то трассировка стека может иногда показывать много.
суперкат
7

Оптимизация вызовов хвоста в основном важна из-за рекурсии хвоста. Однако есть аргумент, почему на самом деле хорошо, что JVM не оптимизирует хвостовые вызовы: поскольку TCO повторно использует часть стека, трассировка стека из исключения будет неполной, что усложнит отладку.

Есть способы обойти ограничения JVM:

  1. Простая хвостовая рекурсия может быть оптимизирована до цикла компилятором.
  2. Если программа в стиле продолжения продолжения, то тривиально использовать «прыжки на батуте». Здесь функция возвращает не конечный результат, а продолжение, которое затем выполняется снаружи. Эта методика позволяет составителю компилятора моделировать произвольно сложный поток управления.

Это может потребовать большего примера. Рассмотрим язык с замыканиями (например, JavaScript или аналогичный). Мы можем написать факториал как

def fac(n, acc = 1) = if (n <= 1) acc else n * fac(n-1, acc*n)

print fac(x)

Теперь мы можем сделать так, чтобы он возвращал обратный вызов:

def fac(n, acc = 1) =
  if (n <= 1) acc
  else        (() => fac(n-1, acc*n))  // this isn't full CPS, but you get the idea…

var continuation = (() => fac(x))
while (continuation instanceof function) {
  continuation = continuation()
}
var result = continuation
print result

Теперь это работает в пространстве с постоянным стеком, что довольно глупо, потому что в любом случае это хвостовая рекурсия. Тем не менее, этот метод может сгладить все хвостовые вызовы в пространстве постоянного стека. И если программа находится в CPS, то это означает, что callstack в целом является постоянным (в CPS каждый вызов является хвостовым вызовом).

Основным недостатком этого метода является то, что его намного сложнее отладить, немного сложнее реализовать и менее производительно - увидеть все замыкания и косвенные указания, которые я использую.

По этим причинам было бы гораздо предпочтительнее, чтобы виртуальная машина реализовала операторы хвостового вызова, такие как Java, у которых есть веские причины не поддерживать хвостовые вызовы, которые бы не использовали его.

Амон
источник
1
«Поскольку TCO повторно использует часть стека, трассировка стека от исключения будет неполной», - да, но тогда и трассировка стека внутри цикла также не завершена - она ​​не записывает частоту выполнения цикла. - Увы, даже если JVM будет поддерживать правильные вызовы хвоста, можно все равно отказаться, скажем, во время отладки. А затем для производства включите TCO, чтобы быть уверенным, что код выполняется с 100 000 или 100 000 000 хвостовых вызовов.
Инго
1
@ Нет. (1) Когда циклы не реализованы как рекурсия, для них нет смысла показываться в стеке (хвостовой вызов ≠ прыжок ≠ вызов). (2) TCO является более общим, чем оптимизация хвостовой рекурсии. Мой ответ использует рекурсию в качестве примера . (3) Если вы программируете в стиле, основанном на TCO, отключение этой оптимизации не вариант - полная TCO или трассировка полного стека либо являются языковой функцией, либо нет. Например, Scheme удается сбалансировать недостатки TCO с помощью более совершенной системы исключений.
Амон
1
(1) полностью согласен. Но по той же причине нет никакого смысла хранить сотни и тысячи записей трассировки стека, которые все указывают return foo(....);в методе foo(2), конечно, полностью согласуются. Тем не менее, мы принимаем неполное отслеживание из циклов, присваиваний (!), Последовательностей операторов. Например, если вы найдете неожиданное значение в переменной, вы наверняка захотите узнать, как оно туда попало. Но вы не жалуетесь на отсутствие следов в этом случае. Поскольку в нашем мозгу как-то выгравировано, что а) это происходит только на вызовах, б) это происходит на всех вызовах. И то и другое не имеет смысла, ИМХО.
Инго
(3) Не согласен. Я не вижу причин, по которым должно быть невозможно отладить мой код с проблемой размера N, так как некоторые N достаточно малы, чтобы уйти с обычным стеком. А затем, чтобы включить коммутатор и включить TCO - эффективно снимается ограничение на размер пробника.
Инго
@ Инго «Не согласен. Я не вижу причин, по которым должно быть невозможно отладить мой код с проблемой размера N, так как некоторые N достаточно малы, чтобы уйти с обычным стеком ». Если TCO / TCE предназначен для преобразования CPS, то его отключение приведет к переполнению стека и падению программы, поэтому отладка невозможна. Google отказался от внедрения TCO в V8 JS, поскольку эта проблема возникла случайно . Они хотели бы иметь специальный синтаксис, чтобы программист мог объявить, что он действительно хочет TCO и потерю трассировки стека. Кто-нибудь знает, если исключения также ввернуты TCO?
Шелби Мур III
6

Значительную часть вызовов в программе составляют хвостовые вызовы. У каждой подпрограммы есть последний вызов, поэтому у каждой подпрограммы есть хотя бы один хвостовой вызов. Хвостовые вызовы имеют характеристики производительности, GOTOно безопасность вызова подпрограммы.

Наличие правильных вызовов в хвосте позволяет вам писать программы, которые вы не можете написать иначе. Взять, к примеру, конечный автомат. Конечный автомат может быть реализован очень напрямую, если каждое состояние будет подпрограммой, а каждый переход состояния - вызовом подпрограммы. В этом случае вы переходите из состояния в состояние, делая вызов после вызова после вызова, и вы фактически никогда не возвращаетесь! Без правильных коллировок вы бы сразу взорвали стек.

Без PTC вы должны использовать GOTOили батуты или исключения как поток управления или что-то в этом роде. Это намного уродливее, и не столько прямое представление конечного автомата 1: 1.

(Обратите внимание, как я ловко избегал использовать скучный пример «цикла». Это пример, когда PTC полезны даже в языке с циклами.)

Я намеренно использовал здесь термин «правильные вызовы», а не ТШО. TCO - это оптимизация компилятора. PTC - это языковая функция, которая требует от каждого компилятора выполнения TCO.

Йорг Миттаг
источник
The vast majority of calls in a program are tail calls. Нет, если «подавляющее большинство» вызываемых методов выполняют более одного собственного вызова. Every subroutine has a last call, so every subroutine has at least one tail call. Это легко продемонстрировать как ложное return a + b. (Если, конечно, вы не на каком-то безумном языке, где базовые арифметические операции определены как вызовы функций.)
Мейсон Уилер
1
«Добавление двух чисел - это добавление двух чисел». За исключением языков, где это не так. Как насчет операции + в Lisp / Scheme, где один арифметический оператор может принимать произвольное количество аргументов? (+ 1 2 3) Единственный разумный способ реализовать это как функцию.
Evicatos
1
@ Мейсон Уилер: Что вы имеете в виду под инверсией абстракции?
Джорджио
1
@MasonWheeler Это, без сомнения, самая волнистая статья в Википедии на техническую тему, которую я когда-либо видел. Я видел некоторые сомнительные записи, но это просто ... вау.
Evicatos
1
@MasonWheeler: Вы говорите о функциях длины списка на страницах 22 и 23 On Lisp? Хвостовая версия примерно в 1,2 раза сложнее, далеко не в 3 раза. Мне также неясно, что вы имеете в виду под инверсией абстракции.
Майкл Шоу
4

«JVM не поддерживает оптимизацию хвостового вызова, поэтому я предсказываю множество взрывающихся стеков»

Любой, кто говорит это, либо (1) не понимает оптимизацию хвостового вызова, либо (2) не понимает JVM, либо (3) оба.

Я начну с определения хвостовых вызовов из Википедии (если вам не нравится Википедия, вот альтернатива ):

В информатике хвостовой вызов - это вызов подпрограммы, который происходит внутри другой процедуры как ее конечное действие; он может произвести возвращаемое значение, которое затем немедленно возвращается вызывающей процедурой

В приведенном ниже коде вызов bar()является хвостовым вызовом foo():

private void foo() {
    // do something
    bar()
}

Оптимизация хвостового вызова происходит, когда языковая реализация, видя хвостовой вызов, не использует нормальный вызов метода (который создает фрейм стека), а вместо этого создает ветвь. Это оптимизация, потому что для стекового фрейма требуется память, и для этого требуется, чтобы циклы ЦП выдвигали информацию (например, адрес возврата) в фрейм, а также потому, что для пары вызов / возврат предполагается больше циклов ЦП, чем для безусловного перехода.

TCO часто применяется к рекурсии, но это не единственное ее использование. Это не относится ко всем рекурсиям. Например, простой рекурсивный код для вычисления факториала не может быть оптимизирован хвостовым вызовом, потому что последнее, что происходит в функции - это операция умножения.

public static int fact(int n) {
    if (n <= 1) return 1;
    else return n * fact(n - 1);
}

Для реализации оптимизации хвостового вызова вам понадобятся две вещи:

  • Платформа, которая поддерживает ветвление в дополнение к вызовам подпрограмм.
  • Статический анализатор, который может определить, возможна ли оптимизация хвостового вызова.

Вот и все. Как я уже отмечал в другом месте, у JVM (как и у любой другой полной по Тьюрингу архитектуры) есть начало. Это имеет безусловный переход , но функциональность может быть легко реализована с использованием условного перехода.

Часть статического анализа - вот что сложно. В пределах одной функции это не проблема. Например, вот хвостовая рекурсивная функция Scala для суммирования значений в List:

def sum(acc:Int, list:List[Int]) : Int = {
  if (list.isEmpty) acc
  else sum(acc + list.head, list.tail)
}

Эта функция превращается в следующий байт-код:

public int sum(int, scala.collection.immutable.List);
  Code:
   0:   aload_2
   1:   invokevirtual   #63; //Method scala/collection/immutable/List.isEmpty:()Z
   4:   ifeq    9
   7:   iload_1
   8:   ireturn
   9:   iload_1
   10:  aload_2
   11:  invokevirtual   #67; //Method scala/collection/immutable/List.head:()Ljava/lang/Object;
   14:  invokestatic    #73; //Method scala/runtime/BoxesRunTime.unboxToInt:(Ljava/lang/Object;)I
   17:  iadd
   18:  aload_2
   19:  invokevirtual   #76; //Method scala/collection/immutable/List.tail:()Ljava/lang/Object;
   22:  checkcast   #59; //class scala/collection/immutable/List
   25:  astore_2
   26:  istore_1
   27:  goto    0

Обратите внимание goto 0на в конце. Для сравнения, эквивалентная Java-функция (которая должна использовать функцию Iteratorимитации поведения разбиения списка Scala на голову и хвост) превращается в следующий байт-код. Обратите внимание, что последние две операции теперь являются вызовом , за которым следует явный возврат значения, созданного этим рекурсивным вызовом.

public static int sum(int, java.util.Iterator);
  Code:
   0:   aload_1
   1:   invokeinterface #64,  1; //InterfaceMethod java/util/Iterator.hasNext:()Z
   6:   ifne    11
   9:   iload_0
   10:  ireturn
   11:  iload_0
   12:  aload_1
   13:  invokeinterface #70,  1; //InterfaceMethod java/util/Iterator.next:()Ljava/lang/Object;
   18:  checkcast   #25; //class java/lang/Integer
   21:  invokevirtual   #74; //Method java/lang/Integer.intValue:()I
   24:  iadd
   25:  aload_1
   26:  invokestatic    #43; //Method sum:(ILjava/util/Iterator;)I
   29:  ireturn

Хвост оптимизации вызова одной функции тривиальна: компилятор может видеть , что не существует кода , который использует результат вызова, так что он может заменить Invoke с goto.

Жизнь становится сложнее, если у вас есть несколько методов. Инструкции по ветвлению JVM, в отличие от процессора общего назначения, такого как 80x86, ограничены одним методом. Это все еще относительно просто, если у вас есть закрытые методы: компилятор может встраивать эти методы соответствующим образом, поэтому он может оптимизировать хвостовые вызовы (если вам интересно, как это может работать, рассмотрите общий метод, который использует a switchдля управления поведением). Вы даже можете распространить эту технику на несколько открытых методов в одном классе: компилятор вставляет тела методов, предоставляет методы открытого моста, а внутренние вызовы превращаются в переходы.

Но эта модель ломается, когда вы рассматриваете публичные методы в разных классах, особенно в свете интерфейсов и загрузчиков классов. Компилятору исходного уровня просто не хватает знаний для реализации оптимизации хвостовых вызовов. Однако, в отличие от "голых" реализаций, * JVM (имеет информацию для этого в виде компилятора Hotspot (по крайней мере, это делает компилятор ex-Sun). Я не знаю, выполняет ли он на самом деле Оптимизация хвостового вызова, и подозреваю, что нет, но это возможно .

Что подводит меня ко второй части вашего вопроса, которую я перефразирую как «нам все равно?»

Понятно, что если ваш язык использует рекурсию в качестве единственного примитива для итерации, вам все равно. Но языки, которым нужна эта функция, могут ее реализовать; единственная проблема заключается в том, может ли компилятор для указанного языка создать класс, который может вызываться и вызываться произвольным классом Java.

Вне этого случая я собираюсь пригласить отрицательные голоса, говоря, что это не имеет значения. Большая часть рекурсивного кода, который я видел (и я работал со многими графическими проектами) , не оптимизирована с помощью хвостового вызова . Как и простой факториал, он использует рекурсию для построения состояния, а хвостовая операция является комбинацией.

Для кода, оптимизируемого с помощью хвостового вызова, часто просто перевести этот код в итеративную форму. Например, ту sum()функцию, которую я показал ранее, можно обобщить как foldLeft(). Если вы посмотрите на источник , вы увидите, что он фактически реализован как итерационная операция. У Jörg W Mittag был пример конечного автомата, реализованного посредством вызовов функций; Есть много эффективных (и поддерживаемых) реализаций конечного автомата, которые не полагаются на вызовы функций, переводимые в переходы.

Я закончу с чем-то совершенно другим. Если вы выберете Google из сносок в SICP, вы можете оказаться здесь . Я лично считаю, что это гораздо более интересное место, чем замена моего компилятора JSRна JUMP.

kdgregory
источник
Если существовал код операции хвостового вызова, почему для оптимизации хвостового вызова потребовалось бы что-то еще, кроме наблюдения на каждом сайте вызова, должен ли метод, выполняющий вызов, выполнить какой-либо код впоследствии? Может случиться так, что в некоторых случаях оператор like return foo(123);может быть лучше выполнен с помощью встраивания, fooчем путем генерации кода для управления стеком и выполнения перехода, но я не понимаю, почему tail-call будет отличаться от обычного вызова в что касается
суперкат
@supercat - я не уверен, что твой вопрос. Первая точка этого поста заключается в том, что компилятор не может знать, как может выглядеть кадр стека всех потенциальных вызываемых (помните, что кадр стека содержит не только аргументы функции, но и ее локальные переменные). Я полагаю, вы могли бы добавить код операции, который проверяет совместимость фреймов во время выполнения, но это подводит меня ко второй части поста: какова реальная ценность?
kdgregory