Introducing Incremental (2015)
12 points by veqq
12 points by veqq
From https://dercuano.github.io/notes/powerful-primitives.html
Umut Acar's self-adjusting computation algorithm is a mechanical transformation you can apply to a batch algorithm to get an incremental algorithm (one which, given a set of changes in its inputs, propagates them to changes in its outputs) that is in many cases optimally asymptotically efficient. He uses ubiquitous memoization of a CPS-transformed version of the program, I think with hash consing, to do this, and uses a "virtual clock" to ensure that side effects do not invalidate the memoization when re-executing functions whose inputs have changed.
That is, the idea is that you run the transformed algorithm once to get its output, and then to update the output for a changed input, you re-execute only the parts of the program that are affected by the changed input. He's demonstrated speedups over the raw batch algorithm of several orders of magnitude, in exchange for a slowdown of a factor of 5 or so while running the trace of the initial execution.
This is a very interesting kind of decoupling: your code is decoupled from whether it is being used to compute the entire output or only a change to it. ... You could imagine using such an execution trace to replace a scalar input with a vector ... and to rapidly provide feedback to optimization algorithms which want to know which input changes will improve their utility function.
... Does it subsume backtracking, if the decisions taken at nondeterministic backtrack points are treated as input? Can we do all of this efficiently without using tens of gigabytes of RAM, perhaps by making more judicious choices of what to memoize?
Imagine a spreadsheet where updating one cell changes a bunch of other cells. The sheet doesn't ask every cell in the sheet to recompute itself when one cell changes, it tracks the relationship between the cells and only recomputes whatever depended on it, recursing outward from there.
You could use Incremental to implement that.
My declarative implementations sort of does this via :rule->deps but I need to refactor a bit to fit incremental/Feldera stuff in along with constraint logic programming where e.g. you make a rule like (< x y) and then redefine y to 3 so you have to check x.