Introducción
Paul Barry nos explicaba recientemente cómo introducir el concepto de optimización de cola en Javascript para construir funciones recursivas sostenibles, un tipo de optimización necesaria cuando se desarrollan aplicaciones con una alta carga de cálculo matemático.
En este post, revisaremos sus planteamientos para comenzar a utilizarlos en nuestros propias aplicaciones.
La optimización de cola
La optimización de cola (también conocida como Recursión de Cola) es una técnica utilizada a menudo en lenguajes de programación funcional para facilitar el uso de la recursión evitando así los bucles imperativos para los cálculos durante las iteraciones.
Cuando decimos ‘bucles imperativos‘, nos referimos al uso de una variable local cuyo valor va cambiando a cada paso de la iteración. Una forma genérica de llamar a estas variables es mediante el término acumulador ya que únicamente funcionan guardando en cada paso el valor correspondiente al cálculo realizado.
Podemos tomar como ejemplo un simple problema de combinatoria que busque calcular la posibilidad de ganar en la lotería: la mayoría de estos concursos, consisten en elegir 5 números entre el 1 y el 50. Cada número solo puede ser escogido una sola vez y, si finalmente tenemos los cinco números correctos, ganamos. El orden no es significativo, solo necesitamos que aquellos que hemos escogido sean los ganadores.
La función en Javascript que se encarga de calcular las posibilidades sería:
function odds( n, p) { var acc = 1; for(var i = 0; i < n; i++) { acc *= (n - i) / (p - i); } return acc; } |
Los parámetros de esta función son n, el cual se corresponde al número de números que tenemos que escoget y p, que sería en este caso el límite superior de los posibles números. Así, para conocer las posibilidades de ganar cogiendo 5 números de 50, obtenemos 4.71974173573222e-7. El número está expresado en notación científica; para obtener un resultado más tradicional, si obtenemos su inverso, 1 / 4.71974173573222e-7, nos daría que tenemos en realidad, 1 probabilidad entre 2.118.760.
Problema del método clásico
Un problema con la función anterior es que usa una variable local para ir almacenando valores a cada iteración y, una máxima de los lenguajes imperativos es que este tipo de variables son malas. De hecho, algunos lenguajes como Clojure, Haskell o Erlang no permiten este tipo de variables por lo que tenemos que escribir nuestras funciones sin recurrir a un acumulador. La forma de conseguir esto es mediante recursión:
function odds(n, p) { if( n == 0 ) { return 1; } else { return ( n / p ) * odds( n - 1, p - 1 ); } } |
Esta es una solución interesante pero no funciona si tratamos de calcular la posibilidad en números grandes. Por ejemplo, si tratamos de calcular la probabilidad cogiendo 10.000 números de entre 100.000 obtendremos un desbordamiento de pila o un exceso de recursión. Esto es fácil de comprobar cuando estudiamos el funcionamiento interno del código anterior: por ejemplo, si queremos calcular odds( 5, 56), el valor final que devuelve la función es ( 5 / 56 ) * odds( 4, 55): el intérprete no puede evaluar esta expresión sin calcular primero odds(4, 55); es por esto que internamente, las series de expresiones que tiene que manejar son:
odds(5, 56) (5/56) * odds(4, 55) (5/56) * (4/55) * odds(3, 54) (5/56) * (4/55) * (3/54) * odds(2, 53) (5/56) * (4/55) * (3/54) * (2/53) * odds(1, 52) (5/56) * (4/55) * (3/54) * (2/53) * (1/52) * odds(0, 51) (5/56) * (4/55) * (3/54) * (2/53) * (1/52) * 1 |
Como vemos, los cálculos se complican a medida que avanzamos, lo que termina provocando el desbordamiento: este flujo muestra cómo funciona el intérprete. A cada nueva iteración, se consume una porción de memoria y, una vez que no hay más llamadas, se comienzan a evaluar las expresiones y liberar dicha memoria ocupada.
Pero, si este método no funciona para los cálculos grandes, ¿que es lo correcto? Es en este caso cuando utilizamos la optimización de cola.
Implementando la solución
Lo primero que tenemos que hacer es eliminar la variable de acumulación o, mejor dicho, transformarla: en lugar de funcionar almacenando valores, la utilizaremos como parámetro de la función. Para evitar que la función pueda ser llamada sin previamente tener preparado nuestro acumulador, crearemos dos independientes: una pública y otra privada:
(function(){ var odds1 = function(n, p, acc) { if(n == 0) { return acc } else { return odds1(n - 1, p - 1, (n / p) * acc) } } odds = function(n, p) { return odds1(n, p, 1) } })() |
NOTA: Para comprender el código anterior y ver cómo a partir del mismo se consiguen funciones (o métodos) públicos y privados, se recomienda leer los artículos Funciones autoejecutables en Javascript y el Patrón Módulo en Profundidad.
Con el ejemplo listo, cada vez que se llame a la función odd, ésta llamará a su vez a odd1 con un valor inicial de 1. En principio, parece que llegamos al mismo problema anterior, ya que al no disponer Javascript de una cola de optimización implementada, obtendríamos de nuevo un desbordamiento para cálculos (iteraciones) grandes. Sin embargo, la diferencia radica en que la función odd pasa tres parámetros a la siguiente, los cuales memorizan valores sin agregarlos a la ecuación.
Esto quiere decir que la nueva secuencia para calcular las posibilidades de extraer por ejemplo 5 números de entre 56, son internamente como sigue:
odds(5, 56)) odds1(5, 56, 1) odds1(4, 55, 5/56) odds1(3, 54, 1/154) odds1(2, 53, 1/2772) odds1(1, 52, 1/73458) odds1(0, 51, 1/3819816) |
Y esto es un cambio fundamental: a cada iteración, no se están agregando términos al cálculo, sino que siempre serán tres operandos con distintos valores (valores calculados en la iteración anterior).
Con este tipo de definición, el intérprete puede afrontar cualquier secuencia del tipo odd(1000, 100000) aunque necesite un tiempo significativo para completarla.
Conclusión
Con la optimización de cola, conseguimos crear funciones recursivas que operan con un número de argumentos y memoria constante evitando caer en desbordamientos de pila o realizando una y otra vez cálculos intermedios innecesarios.
Muy bueno tío jamás se me habría ocurrido!
No sé muy bien a dónde quieres llegar con esto, Carlos. Perdona que te lo diga pero el artículo original tiene bastante más sentido.
Lo digo porque pareces comentar como un simple detalle que Javascript **no realiza TCE**. Pero es que ese detalle hace que -si nos quedamos en Javascript- el cambio hecho a la estructura del código no sirva de nada, porque al intérprete/compilador le da igual que hayas puesto tu llamada en posición de cola, no va a aplicarle TCO.
Dices en tu conclusión que «Con la optimización de cola, conseguimos…» pero en realidad no conseguimos nada de eso puesto que no se realiza esa optimización. TCO/TCE es una optimización que realiza el compilador/intérprete. Si el estándar, la definición del comportamiento del lenguaje, no establece que se realice, da igual que nosotros escribamos el código de modo que se le pueda aplicar, porque no se le va a aplicar (es el caso de Javascript). Es por esto que P. Barry continúa el análisis pasando a un lenguaje que sí tenga TCO, porque si no, no tiene sentido, no existe la optimización.
Tienes que tener en cuenta, que TCO no se refiere simplemente a la organización de nuestro código. A lo que se refiere es a que el compilador/intérprete pueda optimizar la compilación de la vuelta de esa llamada. Y la optimización ahí no recae tanto sobre la necesidad de pila para un acumulador o una operación pendiente. Lo que realmente supone optimización es poder evitar recargar el contexto de la función anterior. Estamos hablando de un Number en cada llamada (unos pocos bytes) frente a un contexto entero, que incluye con toda probabilidad un buen número de punteros y registros (un estado completo del contexto de la función).
De cierto interés te puede resultar este enlace http://voodootikigod.com/paul-barry-shows-how-to-accomplish-tail-call
Mira el primer comentario, del propio Barry, en el que contesta a eso de «Paul Barry enseña cómo conseguir TCO en Javascript» con un:
– Oh, me encanta Javascript pero no debo haber dejado claro el asunto en mi artículo. No puedes *hacer* TCO en Javascript. De hecho no puedes *hacer* TCO en ningún lenguaje. Si está soportado por el lenguaje, entonces el intérprete hace TCO para ti, de forma transparente. Puedes escribir una función con la llamada recursiva en posición de cola, pero si el lenguaje no hace TCO, tu función eventualmente reventará la pila con un número suficiente de llamadas recursivas.
Me temo que entonces estoy en la mismo situación que Barry: no se ha entendido bien el motivo del artículo. Trataremos de aclarar conceptos en los comentarios:
No he creido conveniente resaltar con mayor detalle el hecho de que Javascript no realiza TCE de forma nativa; sin embargo, eso no quita el hecho de que podamos emularla en código como ya se ha hecho siempre hasta ahora (aquí o aquí por ejemplo).
Afirmar que se puede emular con código algo que el intérprete de otros lenguajes hace de forma interna, es una forma de que se entienda el propósito del artículo: el problema de la recursividad y su elevado coste en recursos. Implmentar una cola de procesos, supone en realidad ofrecer al compilador un modo alternativo de ejecución iterativa para un cierto tipo de implementaciones recursivas. Como Javascript no lo hace de forma nativa, la solución es optimizar estas funciones en tiempo de ejecución usando el propio lenguaje. A eso es lo que he llamado optimización de cola en Javacript. Guillaume Lathoud escribió hace algunos meses un artículo en la misma línea que podemos ver aquí.
Al final, de lo que se trata es de conseguir una mejora en el rendimiento importante gracias al uso de técnicas inteligentes en la arquitectura de los algoritmos. El mismo Lathoud, realizó una serie de tests que comparaban una serie de funciones con y sin optimización: hallar el módulo 3, el máximo común divisor de un número dado, un cálculo factorial… Sus resultados pueden verse aquí(junto al artículo completo) y de ellos se obtienen incrementos que van desde el 60% hasta un 220%. En todos los casos, siempre se ha mejorado a la función original.
El cómo llamemos estrictamente a esta técnica no es tan relevante como el resultado obtenido: es probable que no podamos hablar de una optimización estricta sobre algo que el intérprete no proporciona pero del mismo modo, hablamos otros muchos términos que no existen en la definición de Javascript (como las clases).
Gracias por la aportación;
un saludo!
Carlos, Lathoud está haciendo la optimización a mano! Es decir, http://glat.info/pub/tailopt-js/tailopt.js está *transformando* el código, sustituye la recursividad por iteración en tiempo de ejecución, llamando a tailopt(). Está realmente implementando esa funcionalidad que no tiene Javascript. Esto es algo completamente diferente de lo que tú has contado aquí.
Quiero decir, en tu artículo, te limitas a reescribir tu código de otro modo. Ese otro modo es *propenso a ser optimizado*, pero no está optimizado. Es decir, si tuvieras un compilador/intérprete (o una función como el tailopt() de Lathoud) este sería el primer paso y luego el segundo sería que ése hiciera su trabajo y optimizara tu llamada.
Sin embargo, en ausencia de esta funcionalidad, este primer paso que haces, el colocar la llamada en posición, no es una solución de nada. No optimiza las llamadas en absoluto.
Creo que es necesario realizar algunas puntualizaciones sobre el siguiente texto:
1. ¿Problema del método clásico? Problema no tiene ninguno. ¡Vivan los side effects!¡Viva el estado!
2. ¿Las variables locales son malas? ¡En ningún caso en ningún paradigma! ¡Santo Alonzo Church!
3. ¿Algunos lenguajes como Clojure, Haskell o Erlang no permiten este tipo de variables? Me remito al punto 2.
4. ¿Por lo que tenemos que recurrir nuestras funciones sin recurrir a un acumulador? Todo lo contrario, incluso en los lenguajes funcionales puros se busca la aparición de un acumulador para poder optimizar las llamadas en cola. Por ejemplo: http://www.haskell.org/haskellwiki/Performance/Accumulating_parameter
5. ¿La forma de conseguir esto es mediante recursión? Más bien se trata de que tenemos el capricho de convertir un algoritmo iterativo en un recursivo intentando no volar la pila por los aires.
Parece ser que el artículo trata precisamente sobre como transformar un proceso recursivo en uno iterativo, aunque no lo expresas claramente (ejemplo clásico del Abelson & Sussman).
Mas observaciones:
1. ¿Los cálculos se complican? Ni mucho menos, lo que ocurre es que cada invocación de función consume espacio en la pila. Eso no tiene nada que ver con los cálculos y sus complicaciones.
2. ¿Se comienzan a evaluar las expresiones? Si te refieres a esto
(5/56) * (4/55) * (3/54) * (2/53) * (1/52) * 1creo que puedes despistar bastante al lector, ya que todos los cocientes han sido ya evaluados.Ciertamente no se van dejando productos pendientes, pero si se van usando más y más statck frames, uno por invocación lo mismo que en la otra versión.