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 (for more: https://docs.rs/adapton/0.3.17/adapton/#demand-driven-change-propagation).
In a parallel setting, you may want to clean the graph in parallel. Suppose that you know, a priori, that for a given node, two of its successors are independent, in that the output from the first does not flow into the second, and the second is not conditionally executed depending on the outcome of the first.
E.g., (λx. λy. (foo(x), bar(y))) or (λx. λy. foo(x) + bar(y))
But not things like this: (λx. λy. if predicate(x) then foo(x) else bar(y) ) nor (λx. λy. let z = foo(x) in bar(z, y))
I’m not sure how to phrase this kind of node in terms of combinators from Incr, but presumably there’s some way to introduce plumbing where a node accepts two inputs and combines them somehow in a parallel way.
When traversing the induced graph to clean it, we can clean these parallel edges in parallel.
Since the DAG generally permits sharing, these “independent” sub graphs may actually share some common dependencies. In this case, one might want some smart work-stealing algorithm for processing the DAG in parallel. I admit that I don’t know the best way of solving that problem, but Umut seems to be thinking a lot about that sort of thing these days.
Regardless of how its scheduled, I think a critical piece is having nodes whose immediate dependencies are parallel ones, and knowing that the node’s semantics have this property (again, "for a given node, two of its successors are independent, in that the output from the first does not flow into the second, and the second is not conditionally executed depending on the outcome of the first”).
Also, if you still wanted to maintain the partial order in a way where you could query the DAG order of any two nodes, you could use these local edge orderings (or lack of orderings, for parallel edges) to define that two-total-order representation (the A/Z orderings we were describing before).