Pushing and Pulling: Three Reactivity Algorithms
15 points by Johz
15 points by Johz
This is the kind of blog post I come here for.
Cool article! Gives me lots of parallels to Build Systems a la Carte, with the same minimal (efficient & fine grained) and dynamic parameters.
Specifically, the build systems are starting with a pull-based model: build this task by finding and building dependencies. The section on dirty bits seems to match the Push-Pull mix: when an item is modified it is marked as dirty and in addition, all transitive dependencies are marked as dirty.
I've heard the push-pull described as "push invalidation, pull updates".
There should be some kind of formalization (like an 'algebra') of reactivity where your discoveries could be rigorously stated and proved, if it hasn't been already. Anyway, it's a great write-up, looking forward to the follow-ups.
I've seen some of these ideas formalised in "incremental computation", which at least has a lot of overlap with reactive systems. Incremental computation may actually be more fundamental than reactivity. For example, a reactive programming library was built using the incremental computing library "Adapton"[1].
[1]: Hammer, M. A., Phang, K. Y., Hicks, M., & Foster, J. S. (2014). Adapton: Composable, demand-driven incremental computation. ACM SIGPLAN Notices, 49(6), 156-166.
A breath of fresh air among the vibecoding drama :-)
(Could use some editing to make the text less verbose though…)
Its interesting to see the final result characterized as a push pull system. The algorithm laid out has a lot of similarities with the red-green algorithm which I believe falls pretty squarely in the pull category.
When you adapt the red green algorithm to a libe environment you have to introduce a revision and track changed at and verified at revisions for each query. Perhaps the eager dirtying of the graph avoids that complexity?