Подтвердить что ты не робот

Node.js оптимизация хвостового вызова: возможно или нет?

Мне нравится JavaScript до сих пор и решил использовать Node.js как мой движок частично из-за этого, который утверждает, что Node.js предлагает TCO, Однако, когда я пытаюсь запустить этот (явно хвостовой) код с Node.js, он вызывает переполнение стека:

function foo(x) {
    if (x == 1) {
        return 1;
    }
    else {
        return foo(x-1);
    }
}

foo(100000);

Теперь я сделал рытье, и я нашел this. Здесь, кажется, я должен написать это следующим образом:

function* foo(x) {
    if (x == 1) {
        return 1;
    }
    else {
        yield foo(x-1);
    }
}

foo(100000);

Однако это дает мне синтаксические ошибки. Я пробовал различные перестановки, но во всех случаях Node.js кажется чем-то недовольным.

По существу, я хотел бы знать следующее:

  • Есть ли или не Node.js сделать TCO?
  • Как эта магическая вещь yield работает в Node.js?
4b9b3361

ОТВЕТЫ

Ответ 1

Здесь есть два довольно разных вопроса:

  • Есть ли или не Node.js сделать TCO?
  • Как эта магическая способность работает в Node.js?

Есть ли или не Node.js сделать TCO?

TL; DR: Больше нет, начиная с Node 8.x. Это было какое-то время, за одним флагом или другим, но на момент написания этой статьи (ноябрь 2017 года) это уже не так, потому что основной движок V8 JavaScript, который он использует, больше не поддерживает TCO. Подробнее см. этот ответ.

Подробнее:

Оптимизация Tail-call (TCO) - это требуемая . Таким образом, поддержка этого не является, прямо-таки, задачей NodeJS, это то, что поддерживает V8 JavaScript-движок, который поддерживает NodeJS.

Как и в случае с Node 8.x, V8 не поддерживает TCO, даже не за флагом. Он может сделать (снова) в какой-то момент в будущем; см. этот ответ, чтобы узнать больше об этом.

Node 7.10 до 6.5.0 по крайней мере (мои заметки говорят 6.2, но node.green не согласен) поддерживала TCO за флаг (--harmony в 6.6.0 и выше, --harmony_tailcalls ранее) только в строгом режиме.

Если вы хотите проверить свою установку, вот тесты node.green (обязательно используйте флаг, если вы используя соответствующую версию):

function direct() {
    "use strict";
    return (function f(n){
      if (n <= 0) {
        return  "foo";
      }
      return f(n - 1);
    }(1e6)) === "foo";
}

function mutual() {
    "use strict";
    function f(n){
      if (n <= 0) {
        return  "foo";
      }
      return g(n - 1);
    }
    function g(n){
      if (n <= 0) {
        return  "bar";
      }
      return f(n - 1);
    }
    return f(1e6) === "foo" && f(1e6+1) === "bar";
}

console.log(direct());
console.log(mutual());

$ # Only certain versions of Node, notably not 8.x or (currently) 9.x; see above
$ node --harmony tco.js
true
true

Как эта магическая вещь yield работает в Node.js?

Это еще одна вещь ES2015 ( "функции генератора" ), поэтому снова нужно что-то, что V8 должен реализовать. Он полностью реализован в версии V8 в Node 6.6.0 (и был для нескольких версий) и не отстает от каких-либо флагов.

Функции генератора (те, что написаны с помощью function* и с помощью yield) работают, поскольку они могут останавливать и возвращать итератор, который фиксирует их состояние и может использоваться для продолжения своего состояния в последующем случае. У Алекса Раушмайера есть углубленная статья о них здесь.

Вот пример использования итератора, явно возвращаемого функцией генератора, но вы обычно этого не сделаете, и мы сразу увидим, почему:

"use strict";
function* counter(from, to) {
    let n = from;
    do {
        yield n;
    }
    while (++n < to);
}

let it = counter(0, 5);
for (let state = it.next(); !state.done; state = it.next()) {
    console.log(state.value);
}

У этого вывода есть:

0
1
2
3
4

Вот как это работает:

  • Когда мы вызываем counter (let it = counter(0, 5);), начальное внутреннее состояние вызова counter инициализируется, и мы немедленно возвращаем итератор; ни один из фактического кода в counter не работает (пока).
  • Вызов it.next() запускает код в counter через первый оператор yield. В этот момент counter приостанавливает и сохраняет свое внутреннее состояние. it.next() возвращает объект состояния с флагом done и a value. Если флаг done равен false, value - это значение, предоставляемое оператором yield.
  • Каждый вызов it.next() продвигает состояние внутри counter к следующему yield.
  • Когда вызов it.next() завершает и возвращает counter, возвращаемый объект состояния имеет done, установленный в true и value, для возвращаемого значения counter.

Наличие переменных для итератора и объекта состояния и выполнения вызовов it.next() и доступа к свойствам done и value - это все шаблоны, которые (как правило) мешают тому, что мы пытаемся сделать, поэтому ES2015 предоставляет новый оператор for-of, который убирает все это для нас и просто дает нам каждое значение. Здесь тот же самый код, написанный с помощью for-of:

"use strict";
function* counter(from, to) {
    let n = from;
    do {
        yield n;
    }
    while (++n < to);
}

for (let v of counter(0, 5)) {
    console.log(v);
}

v соответствует нашему предыдущему примеру state.value, при этом for-of выполняет все вызовы it.next() и done для нас.

Ответ 2

node.js, наконец, поддерживает TCO с 2016.05.17, версия 6.2.0.

Он должен быть выполнен с флагами --use-strict --harmony-tailcalls для работы TCO.

Ответ 3

6.2.0 - с использованием "use strict" и "--harmony_tailcalls"

работает только с небольшими оптимизированными с хвостом рекурсиями 10000 (как в вопросе), но не работает функция вызывает себя 99999999999999 раз.

7.2.0 с 'use strict' и '--harmony'

Флаг

работает плавно и быстро даже с вызовами 99999999999999.

Ответ 4

Более краткий ответ... с его даты реализации, как упоминалось...

Работа TCO. Это не пуленепробиваемый, но очень приличный. Здесь Factorial (7000000,1).

>node --harmony-tailcalls -e "'use strict';function f(n,t){return n===1?t:f(n-1,n*t);}; console.log(f(7000000,1))"
Infinity

И здесь это без TCO.

>node -e "'use strict';function f(n,t){return n===1?t:f(n-1,n*t);}; console.log(f(15669,1))"
[eval]:1
function f(n,t){return n===1?t:f(n-1,n*t);}; console.log(f(15669,1))
      ^

RangeError: Maximum call stack size exceeded
at f ([eval]:1:11)
at f ([eval]:1:32)
at f ([eval]:1:32)
at ...

Это все равно до 15668.

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