¿Optimización de recurrencia de cola para JavaScript?

algorithm optimization

Question

Mis disculpas a todos por las versiones anteriores de que esto sea vago. Alguien ha decidido tener lástima de la nueva chica y ayudarme a reescribir esta pregunta; aquí hay una actualización que espero que aclare las cosas (y, gracias a todos los que han sido tan generosos con las respuestas hasta el momento):

El problema

Soy un nuevo estudiante de informática en mi primer año en Uni. Para el proyecto final de mi clase Algorithms, podemos seleccionar cualquier lenguaje que deseemos e implementar un algoritmo de "refinamiento" / "eficiencia" que se encuentre de forma nativa (¿internamente?) En otro idioma, pero que falte en el idioma que elijamos.

Recientemente estudiamos la recursividad en clase y mi profesor mencionó brevemente que JavaScript no implementa Tail Recursion . De mi investigación en línea, la nueva especificación ECMA script 6 incluye esta característica, pero no está en ninguna (/ la mayoría de) versiones / motores de JavaScript actualmente? (Lo siento si no estoy seguro de cuál es cuál ... Soy nuevo en esto).

• Encontré algunas publicaciones interesantes como esta .

• Y otra pregunta sobre el desbordamiento de la pila: https://stackoverflow.com/questions/3660577/are-any-javascript-engines-tail-call-optimized

• Y finalmente, ¿qué es un emulador ECMA Script 6 realmente genial llamado Continuum?

Mi tarea es proporcionar 2 opciones para (codificar a) TRABAJAR ALREDEDOR de la característica que falta.

Entonces, mi pregunta es ... ¿alguien, mucho más inteligente y experimentado que yo, tiene algún pensamiento o ejemplo sobre cómo podría implementar un:

¿TRABAJAR ALREDEDOR por la falta de Optimización de Recursión de Cola?

Answer 1

Muchos de los lenguajes más comunes carecen de optimización de recursividad de cola, porque simplemente no esperan que use la recursión para resolver problemas lineales.

La optimización de recursión de cola solo se aplica si una llamada recursiva es lo último que hace su función, lo que significa que no hay nada que tenga que mirar el contenido de la pila actual y, por lo tanto, no es necesario conservarla agregando otro marco de pila.

Cualquier algoritmo de este tipo se puede adaptar a una forma iterativa. Por ejemplo (psuedocode):

 int factorial(int x) {
      return factTail(x,1);
 }

 int factTail(int x, int accum) {
      if(x == 0) {
          return accum;
      } else {
          return(factTail (x-1, x * accum);
      }
 }

... es una implementación de factorial() que se ha diseñado para garantizar que la última declaración devuelva el resultado de una llamada recursiva. Un motor que sabía sobre TCO optimizaría esto.

Una versión iterativa que hace las cosas en el mismo orden:

  int factorial(int x) {
      int accum = 1;
      for(int i=x; i>0; i--) {
          accum *= i;
      }
      return accum;
 }

(Lo hice contar hacia atrás para aproximar el orden de ejecución de la versión recursiva; en la práctica, probablemente no harías esto para factorial)

Está bien usar llamadas recursivas si sabes que la profundidad de recursión no será enorme (en este ejemplo, valores grandes de x ).

A menudo, la recursividad conduce a especificaciones muy elegantes de una solución. Jugando con el algoritmo para obtener una llamada de cola disminuye de eso. Vea cómo el factorial anterior es más difícil de entender que el clásico:

 int factorial(int x) {
     if(x == 1) {
         return 1;
     } else {
         return factorial(x-1) * x;
     }
 }

... sin embargo, esta forma clásica está hambrienta de pilas, para una tarea que no debería necesitar una pila. Entonces, podría argumentarse que una forma iterativa es la forma más clara de resolver este problema en particular.

Debido a la forma en que se enseña la programación, la mayoría de los programadores de hoy están más cómodos con las formas iterativas que con los métodos recursivos. ¿Hay algún algoritmo recursivo en particular con el que tenga problemas específicos?

Answer 2

Una posible optimización de la recursión es evaluar de forma perezosa, es decir, devolver un "cálculo" (= función) que devolverá un valor en lugar de la computación y lo devolverá de inmediato.

Considere una función que resume los números (de una manera bastante tonta):

function sum(n) {
    return n == 0 ? 0 : n + sum(n - 1)
}

Si lo llamas con n = 100000 , excederá la pila (al menos, en mi Chrome). Para aplicar dicha optimización, primero conviértalo en verdadero recursivo de cola, para que la función devuelva solo una llamada a sí misma y nada más:

function sum(n, acc) {
    return n == 0 ? acc : sum(n - 1, acc + n)
}

y envuelva esta auto llamada directa con una función "floja":

function sum(n, acc) {
    return n == 0 ? acc : function() { return sum(n - 1, acc + n) }
}

Ahora, para obtener el resultado de esto, repetimos el cálculo hasta que devuelve una no función:

f = sum(100000, 0)
while(typeof f == "function")
    f = f()

Esta versión no tiene problemas con n = 100000, 1000000, etc.

Answer 3

Como mencioné en mi comentario, siempre puedes convertir tu programa en un estilo de paso de continuación y luego usar llamadas a funciones asíncronas para lograr una verdadera optimización de las llamadas finales. Para llevar este punto a casa, considere el siguiente ejemplo:

function foldl(f, a, xs) {
    if (xs.length === 0) return a;
    else return foldl(f, f(a, xs[0]), xs.slice(1));
}

Claramente esta es una función recursiva de la cola. Entonces, lo primero que tenemos que hacer es convertirlo en un estilo de paso de continuación, que es realmente simple:

function foldl(f, a, xs, k) {
    if (xs.length === 0) k(a);
    else foldl(f, f(a, xs[0]), xs.slice(1), k);
}

Eso es. Nuestra función ahora está en el estilo de paso de continuación. Sin embargo, todavía hay un gran problema: no hay una optimización de la cola de llamadas. Sin embargo, esto se puede resolver fácilmente usando funciones asincrónicas:

function async(f, args) {
    setTimeout(function () {
        f.apply(null, args);
    }, 0);
}

Nuestra función foldl optimizada para llamadas de cola ahora se puede escribir como:

function foldl(f, a, xs, k) {
    if (xs.length === 0) k(a);
    else async(foldl, [f, f(a, xs[0]), xs.slice(1), k]);
}

Ahora todo lo que necesitas hacer es usarlo. Por ejemplo, si desea encontrar la suma de los números de una matriz:

foldl(function (a, b) {
    return a + b;
}, 0, [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], function (sum) {
    alert(sum); // 55
});

Poniendolo todo junto:

function async(f, args) {
    setTimeout(function () {
        f.apply(null, args);
    }, 0);
}

function foldl(f, a, xs, k) {
    if (xs.length === 0) k(a);
    else async(foldl, [f, f(a, xs[0]), xs.slice(1), k]);
}

foldl(function (a, b) {
    return a + b;
}, 0, [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], function (sum) {
    alert(sum); // 55
});

Por supuesto, el estilo de continuación de paso es un dolor escribir en JavaScript. Afortunadamente, hay un lenguaje realmente agradable llamado LiveScript que agrega la diversión a las devoluciones de llamada. Las mismas funciones escritas en LiveScript:

async = (f, args) ->
    setTimeout ->
        f.apply null, args
    , 0

foldl = (f, a, xs, k) ->
    if xs.length == 0 then k a
    else async foldl, [f, (f a, xs.0), (xs.slice 1), k]

do
    sum <- foldl (+), 0, [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
    alert sum

Sí, es un nuevo idioma que se compila con JavaScript, pero vale la pena aprenderlo. Especialmente dado que las llamadas hacia atrás (es decir, <- ) le permiten escribir devoluciones de llamadas fácilmente sin funciones de anidamiento.