Consider the following scenario:
- You have a large volume of data - perhaps a graph, a large program, a database or large query result set.
- Over time this volume of data is subject to many (relatively) small changes.
- You are processing this volume of data in useful ways - delivering it across a network, performing expensive computations or queries, maintaining a UI, etc.
- You want to keep your work up-to-date with the volume; latency and real-time properties are important.
This scenario presents a challenge: how do you avoid recomputing whole volumes after every small change? An effective answer to this question is often important for efficiency and latency. The general class of answers to this challenge:
IncrementalAlgorithms. You process the changes, send only the difference across the network, draw only
DirtyRectangles. Video compression is based on this - send just the changes in the video frame (with occasional full frame to avoid degradation).
EventStreamProcessing is fundamentally about processing 'important' changes.
Unfortunately, there is no known solution general across domains. One cannot generally transform a non-incremental computation into an incremental one. Often, one needs to reduce expressiveness of the transforms to gain any real benefits, because a common issue is tracking how an update in one domain corresponds to an update in another. Incremental computation achieved by hand will almost never 'compose' - that is, after integrating with third-party modules developed in the same language you'll likely have lost incremental properties.
Some languages are relatively suitable for incremental computation, though. FunctionalReactiveProgramming can handle changes in the temporal dimension incrementally (no need to recompute the world every tick) but doesn't offer much help for incremental processing of very large 'volumes' in the spatial dimension, of the sort mentioned above. RelationalAlgebra is relatively incremental in the spatial dimension, making it suitable for ContinuousQueryLanguage. Each of these are valuable in a wide range of domains, and so offer some promise that a general purpose incremental programming language is feasible - even if we haven't quite figured out how to achieve it. Such a language would be a powerful tool for building huge-scale ReactiveProgramming systems such as reactive industrial-sized databases, command and control systems, and massively multi-player games; it would also help with LiveProgramming.
Incremental Invariants
- Abstract
- "Dynamic detection of likely invariants is a program analysis that generalizes over observed values to hypothesize program properties. The reported program properties are a set of likely invariants over the program, also known as an operational abstraction. Operational abstractions are useful in testing, verification, bug detection, refactoring, comparing behavior, and many other tasks."
- "Previous techniques for dynamic invariant detection scale poorly or report too few properties. Incremental algorithms are attractive because they process each observed value only once and thus scale well with data sizes. Previous incremental algorithms only checked and reported a small number of properties. This paper takes steps toward correcting this problem. The paper presents two new incremental algorithms for invariant detection and compares them analytically and experimentally to two existing algorithms. Furthermore, the paper presents four optimizations and shows how to implement them in the context of incremental algorithms. The result is more scalable invariant detection that does not sacrifice functionality."
- Slides
- Implementation
See:
Incremental Algorithms