f# - Elegir entre el estilo de pase de continuación y la memorización

functional-programming ocaml (2)

Un beneficio de CPS es el manejo de errores. Si necesita fallar, simplemente llame a su método de falla.

Creo que la situación más importante es cuando no estás hablando de cálculos, donde la memorización es excelente. Si en cambio está hablando de IO u otras operaciones, los beneficios de CPS están ahí, pero la memorización no funciona.

En cuanto a una instancia en la que CPS y memoialización son aplicables y CPS es mejor, no estoy seguro ya que los considero diferentes piezas de funcionalidad.

Finalmente CPS está un poco disminuido en F # ya que la recursividad de cola hace que todo el asunto de desbordamiento de pila ya no sea un problema.

Mientras escribía ejemplos para la memorización y las funciones de estilo de paso de continuación (CPS) en un lenguaje funcional, terminé usando el ejemplo de Fibonacci para ambos. Sin embargo, Fibonacci no se beneficia realmente de CPS, ya que el ciclo todavía tiene que ejecutarse exponencialmente a menudo, mientras que con la memo- rización es solo O (n) la primera vez y O (1) cada tiempo de seguimiento.

La combinación de CPS y memoria tiene un pequeño beneficio para Fibonacci, pero ¿hay ejemplos en los que CPS es la mejor manera de evitar que se quede sin pila y mejore el rendimiento y donde la memorización no sea una solución?

O: ¿hay alguna guía para cuándo elegir uno sobre el otro o ambos?

En CPS

Aunque CPS es útil como lenguaje intermedio en un compilador, en el nivel de idioma de origen es principalmente un dispositivo para (1) codificar flujo de control sofisticado (no relacionado realmente con el rendimiento) y (2) transformar una pila que no consume cola espacio en un espacio de pila consumidora de llamadas de cola que asigna continuación de continuación. Por ejemplo, cuando escribe (código no probado)

let rec fib = function | 0 | 1 -> 1 | n -> fib (n-1) + fib (n-2) let rec fib_cps n k = match n with | 0 | 1 -> k 1 | n -> fib_cps (n-1) (fun a -> fib_cps (n-2) (fun b -> k (a+b)))

El anterior fib (n-2) sin-cola fib (n-2) , que asignó un nuevo marco de pila, se convierte en la cola llamada fib (n-2) (fun b -> k (a+b)) que asigna el cierre fun b -> k (a+b) (en el montón) para pasarlo como argumento.

Esto no reduce asintóticamente el uso de memoria de su programa (algunas optimizaciones más específicas de dominio podrían, pero esa es otra historia). Solo está intercambiando espacio de pila por espacio de montón, lo cual es interesante en sistemas donde el espacio de pila está severamente limitado por el SO (no es el caso con algunas implementaciones de ML como SML / NJ, que rastrean su pila de llamadas en el montón en lugar de utilizando la pila del sistema), y potencialmente degradante del rendimiento debido a los costos adicionales de GC y la disminución potencial de la localidad.

Es poco probable que la transformación de CPS mejore mucho el rendimiento (aunque los detalles de su implementación y sistemas de tiempo de ejecución pueden hacerlo), y es una transformación generalmente aplicable que permite evitar el snark "" de funciones recursivas con una profunda pila de llamadas.

En Memoization

La memorización es útil para introducir el intercambio de subcalls de funciones recursivas. Una función recursiva típicamente resuelve un "problema" ("calcula fibonacci de n ", etc.) descomponiéndolo en varios "sub-problemas" estrictamente más simples (las subcadenas recursivas), con algunos casos base para los cuales el problema es solucionable de inmediato .

Para cualquier función recursiva (o formulación recursiva de un problema), puede observar la estructura del espacio del subproblema. ¿Qué instancias más simples de Fib(k) Fib(n) necesitarán Fib(n) para devolver su resultado? ¿Qué instancias más simples necesitarán esas instancias a su vez?

En el caso general, este espacio de subproblema es un gráfico (generalmente acíclico para fines de terminación): hay algunos nodos que tienen varios padres, es decir, varios problemas distintos para los cuales son subproblemas. Por ejemplo, Fib(n-2) es un subproblema tanto de Fib(n) como de Fib(n-2) . La cantidad de nodo compartido en este gráfico depende de las funciones recursivas / problema particulares. En el caso de Fibonacci, todos los nodos se comparten entre dos padres, por lo que se comparte mucho .

Una llamada recursiva directa sin memoria no podrá observar este intercambio. La estructura de las llamadas de una función recursiva es un árbol , no un gráfico, y los subproblemas compartidos como Fib(n-2) se visitarán en su totalidad varias veces (tantas como rutas desde el nodo de inicio hasta el nodo de subproblema en la gráfica). La memorización introduce el intercambio al permitir que algunas subcapas vuelvan directamente con "ya hemos calculado este nodo y aquí está el resultado". Para problemas que tienen mucho que compartir, esto puede resultar en una reducción dramática del cálculo (inútil): Fibonacci pasa de la complejidad exponencial a la lineal cuando se introduce la memorización. Tenga en cuenta que hay otras formas de escribir la función, sin utilizar la memo diferentes subcalls estructura, para tener una complejidad lineal.

let rec fib_pair = function | 0 -> (1,1) | n -> let (u,v) = fib_pair (n-1) in (v,u+v)

La técnica de usar alguna forma de compartir (generalmente a través de tablas grandes que almacenan los resultados) para evitar la duplicación inútil de subcomputaciones es bien conocida en la comunidad algorítmica, se llama Programación Dinámica . Cuando reconoce que un problema es susceptible a este tratamiento (nota que se comparte entre los subproblemas), esto puede proporcionar grandes beneficios de rendimiento.

¿Tiene sentido una comparación?

Los dos parecen en su mayoría independientes el uno del otro.

Hay muchos problemas donde la memorización no es aplicable, porque la estructura del gráfico de subproblemas no tiene ningún intercambio (es un árbol). Por el contrario, la transformación de CPS es aplicable para todas las funciones recursivas, pero no por sí misma conduce a beneficios de rendimiento (distintos de factores constantes potenciales debido a la implementación particular y el sistema de tiempo de ejecución que está utilizando, aunque es probable que hagan el código más lento que rápido).

Mejora del rendimiento mediante la inspección de contextos que no son de cola

Hay una técnica de optimización relacionada con CPS que puede mejorar el rendimiento de las funciones recursivas. Consisten en mirar los cálculos "por hacer" después de las llamadas recursivas (lo que se convertiría en una función en el estilo directo de CPS) y encontrar una representación alternativa más eficiente para él, que no da como resultado una asignación de cierre sistemática. Considera por ejemplo:

let rec length = function | [] -> 0 | _::t -> 1 + length t let rec length_cps li k = match li with | [] -> k 0 | _::t -> length_cps t (fun a -> k (a + 1))

Puede observar que el contexto de la llamada no recursiva, concretamente [_ + 1] , tiene una estructura simple: agrega un número entero. En lugar de representar esto como una función fun a -> k (a+1) , puede almacenar el número entero que se va a agregar correspondiente a varias aplicaciones de esta función, haciendo que k un entero en lugar de una función.

let rec length_acc li k = match li with | [] -> k + 0 | _::t -> length_acc t (k + 1)

Esta función se ejecuta en un espacio constante en lugar de lineal. Al convertir la representación de los contextos de cola de funciones en enteros, hemos eliminado el paso de asignación que hizo que el uso de la memoria sea lineal.

Una inspección minuciosa del orden en el que se realizan las adiciones revelará que ahora se realizan en una dirección diferente: primero se agregan los 1 que corresponden al principio de la lista, mientras que la versión cps agregó al final. Esta orden de reversión es válida porque _ + 1 es una operación asociativa (si tiene varios contextos anidados, foo + 1 + 1 + 1 , es válido comenzar a calcularlos desde adentro, ((foo+1)+1)+1 , o el exterior, foo+(1+(1+1)) ). La optimización anterior se puede usar para todos esos contextos "asociativos" en torno a una llamada sin seguimiento.

Ciertamente hay otras optimizaciones disponibles basadas en la misma idea (no soy experto en tales optimizaciones), que consiste en observar la estructura de las continuaciones involucradas y representarlas en una forma más eficiente que las funciones asignadas en el montón.

Esto está relacionado con la transformación de "desfuncionalización" que cambia la representación de las continuaciones de funciones a estructuras de datos, sin cambiar el consumo de memoria (un programa desfuncionalizado asignará un nodo de datos cuando se hubiera asignado un cierre en el programa original), pero permite expresar la versión CPS recursiva de cola en un lenguaje de primer orden (sin funciones de primera clase) y puede ser más eficiente en sistemas donde las estructuras de datos y la coincidencia de patrones son más eficientes que la asignación de cierre y las llamadas indirectas.