If you follow me on Twitter attentively, you know that a while ago I realized that functional reactive programming (FRP) and self-adjusting computation (SAC) are related, but I didn’t know what the difference is. I have now figured it out.
Functional reactive programming is programming with values that change over time. For example, if you want to move a sprite on the screen, the position of the sprite changes as a function of time.
Umut Acar, whose PhD thesis was the original work on self-adjusting computation, describes SAC thus:
Self-adjusting computation refers to a model of computing where computations can automatically respond to changes in their data. […] Perhaps the most important idea in self-adjusting computation is the treatment of computation as a “first-class” mathematical and computational object that can be remembered, re-used, and adapted to changes in its environment.
So, both FRP and SAC are about computations with changing inputs. What’s the difference?
The best explanation I’ve found comes from the blog post Breaking down FRP by Yaron Minsky: FRP is history-sensitive and SAC is not. In FRP, the values that change over time, called behaviors, can be defined in terms of the history of their inputs. In SAC, only the current state can be used.
It can be helpful to thinking about the context where FRP and SAC were developed. FRP’s roots are in animations in virtual reality. SAC was developed for efficiently implementing algorithms where part of the input changes and you do not want to recalculate everything. Also, there’s an answer on Theoretical Computer Science StackExchange that explains when to use FRP, SAC and partial evaluation.