Какие движки JavaScript хвост вызова оптимизирован?

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

6 88
javascript functional-programming tail-recursion

6 ответов:

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

http://lambda-the-ultimate.org/node/3047

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

http://www.paulbarry.com/articles/2009/08/30/tail-call-optimization

по существу, используя шаблон аккумулятора выполнить то же самое эффект.

46

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

26

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

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

12

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

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

на данный момент (05-01-2018) следующие двигатели поддерживают оптимизацию хвостового вызова:

  • Safari 10
  • iOS 10
  • Kinoma XS6

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

  • узел 6.5
  • Chrome 54 / Opera 41 текущая версия таблицы compat больше не содержит ее
8

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

3

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

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

https://gist.github.com/mcfedr/832e3553964a014621d5

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

https://gist.github.com/mcfedr/63ad08370d856bad3694

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

2