Lambda the Ultimate

I think the intention is that "self-adjusting computation" implies the combined strategies of dependency tracking (with memoization) and dynamic tracing (with replay).

This is how I understand it currently.

I've long thought that a general *efficient* solution is impossible, but I've never seen a reference to that effect (my best example are cryptographic functions). Do you have a reference?

I don't believe an efficient solution is possible without some form of checkpointing/logging. But there is no evidence for this; just that fighting against increased entropy and the arrow of time is often a losing battle.

There are already obvious computations where precise deltas can be easily captured. Consider sum: if some element of the sum goes from N to N', the repair to the sum is to add (N' - N) to it. Easy. Now do MAX, not so easy anymore.

I would guess that the class of differentiable computations is similar, if not the same, as reversible ones, which isn't very general at all.

For max I guess you would need an update function of type (input: A) -> (inputDelta: dA) -> (oldOutput: B) -> (newOutput: B) (i.e. dB = B -> B). Would that work in practice?

dB = B -> B makes some sense, but then it's hard to use dB to compute a further dC — since you can't pattern match on the function, you end up computing the "new B" and doing the whole computation on it.

Max is an associative fold, and there are general techniques for those. Hence, you can compute it using divide-and-conquer, and remember the tree of intermediate results (which will be balanced). Changing one element will now affect just the intermediate results depending on it (its "ancestors" in the tree), of which there's a logarithmic number — so you can process those updates in log. time.
Making updates efficient for insertion and deletion is trickier, and requires a randomized division process (see Umut Acar's PhD thesis, Sec. 9.1).

This is an instance of a general pattern: with self-adjusting computation, you just need to write your base computation so that its "computation tree" is balanced — then SAC's memoized change propagation will take care of updating the computation tree and the result when some input changes.

Actually I was thinking about something simpler. If the type of the update function is:

A -> dA -> B -> B

the max update function could be written for example as:

updateMax (input: Set Int, change: {added: Set Int, removed: Set Int}, oldResult: Int) = if change.removed.contains(oldResult) then max(input) else max(oldResult, max(change.added))

So if the previous max element has been removed a full re-calculation would be required, but otherwise a new max value can be calculated incrementally.

To guarantee composition, you need to combine A × dA → B × dB and B × dB → C × dC. This means you might need an instance of B and C — but that was computed during the base computation, so you *just* need to remember it! (Ahem, this is the very basic idea).
Then, you need to avoid using the base inputs *so much* that your incremental computation is too slow.

Indeed, even with self-adjusting computation, incrementalizing a program takes some program-specific effort.

However, I think we want to have DSLs with primitives that are already well-incrementalized (and somewhat general), so that users can "simply" write their programs in terms of those primitives. Then the effort is to support more and more reasonable primitives, and allow for composition.

I'm at work on all of this, so hopefully you'll hear more soon.

Please keep us posted.