I meant that the graph (DAG) structure is not necessary need to be sealed and defined upfront. It could be computed and changed on the fly by the same function that computes node's value. Assuming that the node value computation function is a pure function without side effects (e.g. it's output depends purely on inputs) the function may read other node values directly, and the act of reading would establish graph edges transparently for the user. The next time compute function is being invoked it could re-subscribe on the different nodes hence changing graph structure on the fly. The user also can remove or add new nodes in between of the node values materialization. In other words, the act of subscription between nodes in the incremental computation system is typically tracked more transparently for the user than in the system with explicit observer-subscriber primitives. Even though, this is implementation dependent. The observable pattern could be designed transparently too. Perhaps, "flexibility" would be better term.
How do you consistently update a DAG, like you describe in your medium article, if the functions corresponding to the nodes in the graph are free to create new dependencies willy-nilly? It seems like this would have to be pretty restricted and/or performance killing, because you'd have to evaluate the graph under the assumption that any node could depend on any other node (unless that dependency creates a cycle, presumably). This overhead may not matter if the node functions are expensive relative to the cost of managing the graph, though.
In the article it is assumed that the object of the node owns a vector of it's dependencies locally. We don't need to access the entire edges set all at once. The evaluation process is recursive. Once the node's function re-evaluate, the vector is being updated. Though, the re-evaluation is not happening for every node every time due to the caching system based on the node's value hash comparison and the two-layer monotonic versioning in case of present algorithm. Other incremental computation algorithm have different approaches in verifying on whether the node's function needs to be re-evaluated. Each approach have pros and cons.
You are right, it is assumed that in general the average node function evaluation is more expensive than the cost of graph management. It's not too expensive, but if by chance node's function is notably cheaper, this approach could be suboptimal in certain cases.
The key insight here is that it is assumed the end user don't need to actualize the entire graph each time any random input is being changed. The user observes only a small portion of the graph nodes in real time, and the incremental computation system ensures to minimize required evaluations. If this local observability is not a goal the system is not incremental by definition. For example, in case of Spreadsheets the entire table could be 10000x10000 cells, however the end user typically sees only a small portion of the table on the screen. On a general note the incremental computation systems are closely tied to the GUI-related tasks.
I meant that the graph (DAG) structure is not necessary need to be sealed and defined upfront. It could be computed and changed on the fly by the same function that computes node's value. Assuming that the node value computation function is a pure function without side effects (e.g. it's output depends purely on inputs) the function may read other node values directly, and the act of reading would establish graph edges transparently for the user. The next time compute function is being invoked it could re-subscribe on the different nodes hence changing graph structure on the fly. The user also can remove or add new nodes in between of the node values materialization. In other words, the act of subscription between nodes in the incremental computation system is typically tracked more transparently for the user than in the system with explicit observer-subscriber primitives. Even though, this is implementation dependent. The observable pattern could be designed transparently too. Perhaps, "flexibility" would be better term.
How do you consistently update a DAG, like you describe in your medium article, if the functions corresponding to the nodes in the graph are free to create new dependencies willy-nilly? It seems like this would have to be pretty restricted and/or performance killing, because you'd have to evaluate the graph under the assumption that any node could depend on any other node (unless that dependency creates a cycle, presumably). This overhead may not matter if the node functions are expensive relative to the cost of managing the graph, though.
In the article it is assumed that the object of the node owns a vector of it's dependencies locally. We don't need to access the entire edges set all at once. The evaluation process is recursive. Once the node's function re-evaluate, the vector is being updated. Though, the re-evaluation is not happening for every node every time due to the caching system based on the node's value hash comparison and the two-layer monotonic versioning in case of present algorithm. Other incremental computation algorithm have different approaches in verifying on whether the node's function needs to be re-evaluated. Each approach have pros and cons.
You are right, it is assumed that in general the average node function evaluation is more expensive than the cost of graph management. It's not too expensive, but if by chance node's function is notably cheaper, this approach could be suboptimal in certain cases.
The key insight here is that it is assumed the end user don't need to actualize the entire graph each time any random input is being changed. The user observes only a small portion of the graph nodes in real time, and the incremental computation system ensures to minimize required evaluations. If this local observability is not a goal the system is not incremental by definition. For example, in case of Spreadsheets the entire table could be 10000x10000 cells, however the end user typically sees only a small portion of the table on the screen. On a general note the incremental computation systems are closely tied to the GUI-related tasks.