Demand-driven change propagation
If you have a DAG where for each node, you have some local computation (internal to the node) and some external dependencies (other nodes in the DAG that I’ll call the “successors”) and some dependents (other DAG nodes that I’ll call the “predecessors”) then we can consider doing change propagation over this via Adapton’s demand-driven algorithm:
— Dirty the graph (perhaps in parallel) when a reference cell (e.g., input cell) changes, by traversing all dependent (predecessor) edges and marking them dirty. An invariant is that if an edge is dirty, all preceding edges are dirty too, so we can stop dirtying early.
— Clean the graph on demand (of a node in the DAG) by traversing its successor edges that are dirty, until we reach a node that depends directly on a changed input. Re-evaluate that node. If its return value changes, then we need to re-evaluate its predecessors, and so on. Change propagation here is demand-driven, and follows the original order of execution (fo