Is there a paradigm for composing "incremental update" functions in a pure dataflow style?

Question

I don't know the correct terminology for asking this question, so I'll describe it with lots of words instead, bear with me.

Background, just so we're on the same page: Programs often contain caches - a time/memory tradeoff. A common programmer's mistake is to forget to update a cached value after changing one of its upstream sources/precedents. But the dataflow or FRP programming paradigm is immune to such mistakes. If we have a number of pure functions, and connect them together in a directed dependency graph, then nodes can have their output value cached and re-used until any of the function's inputs change. This system architecture is described in the paper Caching In Dataflow-Based Environments and in an imperative language it's more or less analogous to memoization.

Problem: When one of the inputs to a function do change, we still have to execute the function as a whole, throwing away its cached output and re-calculating from scratch. In many cases, this seems wasteful to me. Consider a simple example that generates a "top 5 whatever" list. The input data is an unsorted list of whatever. It's passed as input to a function that outputs a sorted list. Which in turn is input to a function that takes the first 5 items only. In pseudocode:

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

The complexity of the sort function is O(N log N). But consider that this flow is used in an application where the input only changes a little bit at a time, by adding 1 element. Rather than re-sorting from scratch every time, it would be faster, in fact O(N), to use a function which updates the old cached sorted list by inserting the new element in the correct position. This is just one example - many "from scratch" functions have such "incremental update" counterparts. Also, maybe the newly added element won't even appear in the final_output because it's after the 5th position.

My intuition suggests it might be possible to somehow add such "incremental update" functions to a dataflow system, side by side with the existing "from scratch" functions. Of course, re-calculating everything from scratch must always give the same result as a doing bunch of incremental updates. The system should have the property that if each of the individual primitive FromScratch-Incremental pairs always give the same result, then the larger composite functions built from them should also automatically give the same result.

Question: Is it possible to have a system/architecture/paradigm/meta-algorithm which can support both FromScratch functions and their Incremental counterparts, cooperating for efficiency, and composed into large flows? If not, why? If someone has researched this paradigm already and published it, what is it called, and can I get a short summary of how it works?

Answer 1

This field has been invented many times, and goes under many names, such as:

• Online algorithms.
• Streaming algorithms, stream queries, continuous queries.
• Dynamic data structures.
• Self-adjusting computation (as per Andrej).

(And possibly more.) Those are not the same, but related.

Paraphrasing Cai et al (1): There are two core ways of implementing online algorithms generically (i.e. without reference to any specific algorithmic problem):

• Static incrementalisation. Static approaches analyse a program at compile-time and produce an incremental version that efficiently updates the output of the original program according to changing inputs. Static approaches have the potential to be more efficient than dynamic approaches, because no bookkeeping at runtime is required. Also, the computed incremental versions can often be optimised using standard compiler techniques such as constant folding or inlining. This is the approach investigated in (1).

• Dynamic incrementalisation. Dynamic approaches create dynamic dependency graphs while the program runs and propagate changes along these graphs. The most well-know approach is Acar's self-adjusting computation. The key idea is simple: programs execute on the original input in an enhanced runtime environment that tracks the dependencies between values in a dynamic dependence graph; intermediate results are cached. (As you might imagine, this tends to use a lot of memory, and much research in this field is about how to limit memory usage.) Later, changes to the input propagate through dependency graphs from changed inputs to results, updating both intermediate and final results; this processing is often more efficient than recomputation. However, creating dynamic dependence graphs imposes a large constant-factor overhead during runtime, ranging from 2 to 30 in reported experiments.

In addition, one can always try and come up 'by hand' with an online version of a given algorithm. This can be difficult.

---

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

Answer 2

You are probably looking for adaptive programming. See also Umut Acar's PhD thesis. I am not up-to-date with this area of work but it should get you started, you can chase up references.