Оптимизация хвостового вызова 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);

Я немного покопался и нашел это. Здесь, кажется, говорят, что я должен написать это так:

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

foo(100000);

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

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

  1. Node.js делает TCO или нет?
  2. Как это волшебно yield вещь работает в Node.js?
Источник

4 ответа

Решение

Здесь есть два довольно четких вопроса:

  • Node.js делает TCO или нет?
  • Как работает эта волшебная вещь в Node.js?

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

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

Подробности:

Оптимизация Tail-Call (TCO) является обязательной частью спецификации ES2015 ("ES6"). Таким образом, его поддержка, прямо, не вещь NodeJS, это то, что движок JavaScript V8, который должен использовать NodeJS, должен поддерживать.

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

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

Если вы хотите проверить свою установку, вот тесты, которые использует http://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());

$ # Только определенные версии Node, особенно не 8.x или (в настоящее время) 9.x; см выше
$ node --harmony tco.js
правда
правда

Как это волшебно 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 флаг и value, Если done флаг false, value это значение, полученное от yield заявление.
  • Каждый звонок it.next() продвигает состояние внутри counter к следующему yield,
  • Когда звонок в it.next() марки counter Finish и Return, объект состояния, который мы получаем, имеет 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 проверяет нас.

Источник

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

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

Источник

6.2.0 - с использованием "строгого" и "--harmony_tailcalls"

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

7.2.0 с "используйте строгий" и "--harmony"

флаг работает легко и быстро даже при 99999999999999 звонках.

Источник

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

ТШО работает. Это не пуленепробиваемый, но он очень приличный. Вот факториал (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, хотя.

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

Источник
Другие вопросы по тегам