Оптимизированы ли какие-либо хвостовые вызовы движков JavaScript (TCO)?

91

У меня есть хвостовой рекурсивный алгоритм поиска пути, который я реализовал в JavaScript, и я хотел бы знать, могут ли какие-либо (все?) Браузеры получить исключения переполнения стека.

javascript functional-programming tail-recursion Clofresh
источник
2
Действительно ли это рекурсивный алгоритм или итерационный алгоритм, реализованный с помощью рекурсии? Насколько я понимаю, ТШО может помочь только с последним.
nmichaels
1
Я просто хочу добавить, что совокупная стоимость владения - это не onlyоптимизация. Его поддержка должна быть частью спецификации языка, а не компилятора / интерпретатора, поскольку код, написанный для одного интерпретатора / компилятора с TCO, вероятно, не будет работать с интерпретатором / компилятором без TCO.
Hoffmann
1
Вы можете увидеть текущую поддержку и наблюдать за ее развитием в разных движках в таблице совместимости Kangax с ES6 здесь: kangax.github.io/compat-table/es6/…
Рой Тинкер

Ответы:

47

Спецификация ECMAScript 4 изначально собиралась добавить поддержку TCO, но она была исключена:

Больше никаких хвостовых вызовов в JavaScript?

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

Оптимизация хвостового вызова

По сути, использование модели аккумулятора дает тот же эффект.

Тим Сильвестр
источник
1
К вашему сведению, у Rhino есть автоматическая TCO вместе с Continuations в «интерпретируемом» режиме (opt = -1) wiki.apache.org/cocoon/RhinoWithContinuations
Марк Портер
5
(извините за троллинг) ECMAScript 6 включил в спецификацию TCO, называемую надлежащими хвостовыми вызовами.
Frosty
@sclv: Что это за батут?
bukzor
39
Схема аккумулятора не дает того же эффекта, что и совокупная стоимость владения. Он просто преобразует рекурсивные алгоритмы в хвостовую рекурсивную форму. Это предварительное условие для возможности TCO, но не его замена. Вы все равно взорвете стек на языке, который не оптимизирует хвостовые вызовы.
Марсело Кантос
«ни одна из широко доступных реализаций JS в настоящее время не выполняет автоматическую совокупную стоимость владения», это неверно с Node 6.2.0, если вы передадите правильный флаг
Янус Троелсен,
26

На данный момент без радости, но, к счастью, правильные хвостовые вызовы запланированы для Harmony (ECMAScript версии 6) http://wiki.ecmascript.org/doku.php?id=harmony:proper_tail_calls

Господин спикер
источник
1
@MarkWilbur Вопрос касался конкретно браузеров , а не всех существующих реализаций ECMAScript.
Useless Code
1
@UselessCode Нет, это вопрос о "движках Javascript", так что ... не только о браузерах
BT
1
@BT Действительно существует много сред JS, не относящихся к браузеру, и в заголовке используются более общие «механизмы Javascript», но в теле вопроса указано «... хотел бы знать, могут ли какие-либо (все?) Браузеры получить стек исключения переполнения ".
Useless Code
Я должен возразить, «но в названии сказано…». Я думаю, поскольку он упоминает оба, вопрос касается обоих. Но вы правы, если утверждаете, что это не делает ответ устаревшим.
BT
4
@MarkWilbur Насколько мне известно, узел использует ту же версию v8, что и chrome, который в настоящее время не поддерживает TCO. У меня была суть в JS и оптимизированном ассемблере, который производит текущий V8 - gist.github.com/mcfedr / 832e3553964a014621d5
mcfedr 07
12

Практически в каждом браузере, с которым вы сталкиваетесь, "слишком много рекурсии". Вот запись в системе отслеживания ошибок V8, которую, вероятно, будет интересно прочитать.

Если это простая саморекурсия, вероятно, стоит приложить усилия для использования явной итерации, а не надеяться на устранение хвостового вызова.

Хэнк Гей
источник
Наконец-то ошибка была принята. Он находится под эпосом: «Согласование запросов функций». Надеюсь, это означает, что они планируют добавить его в поддержку ES6 в V8.
Txangel
Вы можете проголосовать за поддержку TCO в Internet Explorer здесь: wpdev.uservoice.com/forums/257854-internet-explorer-platform/…
Рой Тинкер,
12

Оптимизация хвостового вызова будет поддерживаться в строгом режиме ECMAScript 6 в будущем. Проверьте http://www.2ality.com/2015/06/tail-call-optimization.html для деталей.

Проверьте http://kangax.github.io/compat-table/es6/ для получения текущей поддержки движка.

На данный момент (18-07-2019) оптимизацию хвостового вызова поддерживают следующие движки:

  • Safari> = 10
  • iOS> = 10
  • Kinoma XS6
  • Дуктапе 2.3

поддержка, если включен флаг "экспериментальные функции JavaScript":

  • Узел 6.5
  • Chrome 54 / Opera 41 Текущая версия таблицы совместимости больше не отображает ее
Саймон Зикс
источник
3

Оптимизация хвостового вызова теперь доступна в LispyScript, который компилируется в JavaScript. Вы можете прочитать об этом здесь .

Сантош
источник
А как насчет взаимной рекурсии?
cat
2

В настоящее время ни одна реализация JavaScript не распознает хвостовую рекурсию. В ECMAScript 6 вносятся изменения , и, как говорили другие, есть открытый билет на V8 .

Здесь вы можете увидеть сгенерированный V8 ассемблер для функции хвостовой рекурсии:

Пример того, как V8 компилирует рекурсию

Сравните это с тем, как Clang скомпилировал ту же функцию на C

Пример хвостовой рекурсии компилятора C

V8 сохраняет рекурсивный вызов, тогда как компилятор C распознал хвостовую рекурсию и превратил ее в цикл.

McFedr
источник
«В настоящее время ни одна реализация JS не распознает хвостовую рекурсию». это неверно в Node 6.2.0, но вы должны передать флаг
Янус Троэльсен,