alt Hacker NewsCan't you solve it using hash trees (or Merkle trees) ?
You tag each computation nodes with a hash of its dependencies and some constant salt, that gives you an ID which identifies the results that the computation node would produce; before running it.
You can then use those IDs to index the computations results in a cache; whenever you query a computation results, as long as you update the IDs of each leaf of the computation graph, you will only re-compute the nodes that need to be updated
What you're describing is akin to a basic pull-based incremental engine, akin to salsa. The base design is straightforward, but you need some additional logic to avoid following the whole execution tree when hashing. Their downsides is that sometimes you do have to follow the whole execution tree, even if nothing changed.
Push-based designs instead "push" changes to their dependants, which can be quite efficient especially in the case where the update doesn't propagate much. However it has the downside of potentially requiring to update nodes that are no longer used, or updating nodes multiple times.