Changing the past in open systems
One important step towards a more systematic approach to online update is to make the dimension of interaction explicit. This is one of the things I’ve focused on in my own research, which I call interactive programming, although that term has probably already been laid claim to. I allow the user to step sideways in time, into a “counterfactual” execution where it is “as though” the program had been written differently from the outset. Inspired by Demaine etal‘s retroactive data structures, which are imperative data structures which permit modifications to the historical sequence of operations performed on them, I’ll refer to this notion of online update as retroactive update. Retroactive update allows the “computational past” to be changed. Self-adjusting computation (SAC) is another system based on retroactive update. SAC explores another crucial aspect of online update: efficient update, via an algorithm called change propagation. SAC’s commitment to retroactivity appears in the correctness of change propagation, which is defined as consistency with a from-scratch run under the modified code.