javascript - Optimización de la llamada final de Node.js: ¿posible o no?

tail-call-optimization

Question

Me gusta JavaScript hasta ahora, y decidí usar Node.js como mi motor en parte debido a this , que afirma que Node.js ofrece TCO. Sin embargo, cuando trato de ejecutar este código (obviamente llamado de cola) con Node.js, se produce un desbordamiento de pila:

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

foo(100000);

Ahora, hice algunas excavaciones, y encontré this . Aquí, parece decir que debería escribirlo así:

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

foo(100000);

Sin embargo, esto me da errores de sintaxis. He probado varias permutaciones, pero en todos los casos, Node.js parece descontento con algo .

Esencialmente, me gustaría saber lo siguiente:

1. ¿Hace o no Node.js hace TCO?
2. ¿Cómo funciona esta cosa de yield mágico en Node.js?

Answer 1

6.2.0 - con ''use strict'' y ''--harmony_tailcalls''

funciona solo con pequeñas recursiones optimizadas de cola de 10000 (como en la pregunta), pero falla la función se llama a sí misma 99999999999999 veces.

7.2.0 con ''uso estricto'' y ''--armonia''

La bandera funciona a la perfección y rápidamente incluso con 99999999999999 llamadas.

Answer 2

Aquí hay dos preguntas bastante distintas:

• ¿Hace o no Node.js hace TCO?
• ¿Cómo funciona esta cosa de rendimiento mágico en Node.js?

¿Hace o no Node.js hace TCO?

TL; DR : Ya no, a partir del Nodo 8.x. Lo hizo por un tiempo, detrás de una bandera u otra, pero al momento de escribir esto (noviembre de 2017) ya no lo hace porque el motor de JavaScript V8 subyacente que usa ya no es compatible con el TCO. Ver esta respuesta para más sobre eso.

Detalles:

La optimización de llamada de cola (TCO) es una parte requerida de la especificación ES2015 ("ES6") . Por lo tanto, admitirlo no es, directamente, una cosa de NodeJS, es algo que el motor de JavaScript V8 que NodeJS usa necesita soportar.

A partir del Nodo 8.x, V8 no admite TCO, ni siquiera detrás de una bandera. Puede hacerlo (de nuevo) en algún momento en el futuro; ver esta respuesta para más sobre eso.

El nodo 7.10 hasta 6.5.0 al menos (mis notas dicen 6.2, pero node.green no está de acuerdo) admitió TCO detrás de una bandera ( --harmony en 6.6.0 y superior, --harmony_tailcalls anterior) solo en modo estricto.

Si desea verificar su instalación, aquí están las pruebas que usa node.green (asegúrese de usar la bandera si está usando una versión relevante):

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

¿Cómo funciona esta cosa de yield mágico en Node.js?

Esta es otra cosa de ES2015 ("funciones del generador"), así que de nuevo es algo que V8 tiene que implementar. Está completamente implementado en la versión de V8 en Node 6.6.0 (y ha estado en varias versiones) y no está detrás de ninguna bandera.

Las funciones del generador (aquellas escritas con la function* y utilizando el yield ) funcionan al detener y devolver un iterador que captura su estado y se puede usar para continuar su estado en una ocasión posterior. Alex Rauschmeyer tiene un artículo detallado sobre ellos here .

Este es un ejemplo del uso del iterador devuelto por la función del generador de forma explícita, pero normalmente no lo hará y veremos por qué en un momento:

"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);
}

Que tiene esta salida:

0 1 2 3 4

Así es como funciona:

• Cuando llamamos counter ( let it = counter(0, 5); ), el estado interno inicial de la llamada a counter se inicializa e inmediatamente recuperamos un iterador; ninguno de los códigos reales en el counter ejecuta (todavía).
• it.next() ejecuta el código de forma counter a través de la primera declaración de yield . En ese punto, el counter hace una pausa y almacena su estado interno. it.next() devuelve un objeto de estado con una it.next() done y un value . Si el indicador done es false , el value es el valor generado por la declaración de yield .
• Cada llamada a it.next() avanza el estado dentro del counter al siguiente yield .
• Cuando una llamada a it.next() hace que el counter finalice y regrese, el objeto de estado que recuperamos se ha establecido en true y el value establecido en el valor de retorno del counter .

Tener variables para el iterador y el objeto de estado y hacer llamadas a it.next() y acceder a las propiedades de done y value es un elemento clave que (normalmente) interfiere con lo que intentamos hacer, por lo que ES2015 proporciona la nueva Declaración de por qué nos lo guarda todo y nos da cada valor. Aquí está el mismo código escrito anteriormente con 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 corresponde a state.value en nuestro ejemplo anterior, con for-of hacer todas las llamadas it.next() y done comprobaciones por nosotros.

Answer 3

Respuesta más concisa ... a partir de la fecha de implementación, como se mencionó ...

TCO funciona. No es a prueba de balas, pero es muy decente. Aquí está el 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

Y aquí está sin 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 ...

Sin embargo, lo hace todo el camino hasta 15668.

En cuanto al rendimiento, ver otras respuestas. Probablemente debería ser una pregunta separada.

Answer 4

node.js finalmente soporta TCO desde 2016.05.17, versión 6.2.0 .

Es necesario que se ejecute con las --use-strict --harmony-tailcalls para que el TCO funcione.