¿Existe un paradigma para componer funciones de "actualización incremental" en un estilo de flujo de datos puro?

No sé la terminología correcta para hacer esta pregunta, así que la describiré con muchas palabras, tengan paciencia conmigo.

Antecedentes , solo para estar en la misma página: los programas a menudo contienen cachés, una compensación de tiempo / memoria. El error de un programador común es olvidar actualizar un valor almacenado en caché después de cambiar una de sus fuentes / precedentes ascendentes. Pero el paradigma de programación de flujo de datos o FRP es inmune a tales errores. Si tenemos varias funciones puras, y las conectamos en un gráfico de dependencia dirigido, entonces los nodos pueden tener su valor de salida almacenado en caché y reutilizado hasta que cambie cualquiera de las entradas de la función. Esta arquitectura de sistema se describe en el documento Almacenamiento en caché en entornos basados ​​en flujo de datos y en un lenguaje imperativo es más o menos análogo a la memorización.

Problema : cuando una de las entradas de una función cambia, todavía tenemos que ejecutar la función como un todo, desechar su salida en caché y volver a calcular desde cero. En muchos casos, esto me parece un desperdicio. Considere un ejemplo simple que genera una lista de "los 5 mejores". Los datos de entrada son una lista sin clasificar de lo que sea. Se pasa como entrada a una función que genera una lista ordenada. Lo que a su vez es entrada a una función que toma solo los primeros 5 elementos. En pseudocódigo:

input = [5, 20, 7, 2, 4, 9, 6, 13, 1, 45]
intermediate = sort(input)
final_output = substring(intermediate, 0, 5)

La complejidad de la función de clasificación es O (N log N). Pero considere que este flujo se usa en una aplicación donde la entrada solo cambia un poco a la vez, agregando 1 elemento. En lugar de volver a ordenar desde cero cada vez, sería más rápido, de hecho, O (N), usar una función que actualice la lista ordenada en caché anterior insertando el nuevo elemento en la posición correcta. Este es solo un ejemplo: muchas funciones "desde cero" tienen esas contrapartes de "actualización incremental". Además, tal vez el elemento recién agregado ni siquiera aparecerá en la salida final porque está después de la quinta posición.

Mi intuición sugiere que podría ser posible de alguna manera agregar tales funciones de "actualización incremental" a un sistema de flujo de datos, junto con las funciones existentes "desde cero". Por supuesto, volver a calcular todo desde cero siempre debe dar el mismo resultado que un montón de actualizaciones incrementales. El sistema debe tener la propiedad de que si cada uno de los pares FromScratch-Incremental primitivas individuales siempre dan el mismo resultado, a continuación, las funciones compuestas más grandes construidas a partir de ellos deben también dar automáticamente el mismo resultado.

Pregunta : ¿Es posible tener un sistema / arquitectura / paradigma / meta-algoritmo que pueda soportar tanto las funciones FromScratch como sus contrapartes incrementales, cooperando para la eficiencia y compuestas en grandes flujos? Si no, ¿por qué? Si alguien ya investigó este paradigma y lo publicó, ¿cómo se llama? ¿Puedo obtener un breve resumen de cómo funciona?

Este campo se ha inventado muchas veces y tiene muchos nombres, como:

• Algoritmos en línea .
• Algoritmos de transmisión , consultas de transmisión, consultas continuas.
• Estructuras de datos dinámicos.
• Cálculo autoajustable (según Andrej).

(Y posiblemente más.) Esos no son lo mismo, pero están relacionados.

Parafraseando a Cai et al (1): hay dos formas principales de implementar algoritmos en línea de forma genérica (es decir, sin referencia a ningún problema algorítmico específico):

• Incrementalización estática. Los enfoques estáticos analizan un programa en tiempo de compilación y producen una versión incremental que actualiza eficientemente la salida del programa original de acuerdo con las entradas cambiantes. Los enfoques estáticos tienen el potencial de ser más eficientes que los enfoques dinámicos, ya que no se requiere contabilidad en tiempo de ejecución. Además, las versiones incrementales calculadas a menudo se pueden optimizar utilizando técnicas de compilación estándar, como el plegado o la alineación constante. Este es el enfoque investigado en (1).

• Incrementalización dinámica. Los enfoques dinámicos crean gráficos de dependencia dinámicos mientras el programa se ejecuta y propaga los cambios a lo largo de estos gráficos. El enfoque más conocido es el cálculo autoajustable de Acar. La idea clave es simple: los programas se ejecutan en la entrada original en un entorno de tiempo de ejecución mejorado que rastrea las dependencias entre valores en un gráfico de dependencia dinámico; Los resultados intermedios se almacenan en caché. (Como puede imaginar, esto tiende a usar mucha memoria, y mucha investigación en este campo trata sobre cómo limitar el uso de la memoria). Más tarde, los cambios en la entrada se propagan a través de gráficos de dependencia de entradas cambiadas a resultados, actualizando tanto intermedios como intermedios. resultados finales; Este procesamiento es a menudo más eficiente que el recálculo. Sin embargo, la creación de gráficos de dependencia dinámica impone una gran sobrecarga de factor constante durante el tiempo de ejecución, que varía de 2 a 30 en los experimentos informados.

Además, uno siempre puede tratar de encontrar 'a mano' una versión en línea de un algoritmo dado. Esto puede ser dificil.

^{(1) Y. Cai, PG Giarrusso, T. Rendel, K. Ostermann, A Theory of Changes for Higher-Order Languages: Incrementalizing λ-Calculi by Static Diferenciation .}

Probablemente esté buscando una programación adaptativa . Ver también la tesis doctoral de Umut Acar . No estoy actualizado con esta área de trabajo, pero debería ayudarlo a comenzar, puede buscar referencias.