Hacker News Reader

Comment by Eliah_Lakhin | Hacker News Reader

It depends on how you define the observable pattern.

The fundamental components here are laziness and weak connections between graph nodes. Node values are getting materialized only when you observe them, and the system is flexible for live structural changes.

Usually, you don't need to materialize the entire graph when you need to observe just some nodes. Additionally, you can halt computations at any point in time leaving the graph in semi-actualized state, make extra changes to the inputs, and continue materialization of the nodes of interest. The algorithm will sort out all changes for you.

Essentially, incremental computations is just a term covering these features. You can organize the same system in terms of observers and subscribers.

Perhaps, classical Excel spreadsheets is the best illustration of the idea. Also, see my article on the topic: https://medium.com/@eliah.lakhin/salsa-algorithm-explained-c...

View on HN

> You can organize the same system in terms of observers and subscribers.

Also, the differences between "hot" and "cold" observers and the use of schedulers.

I like that about the observable pattern that while hot versus cold is confusing, it is generally "explicit" in the dance of observers/subscribers. I also tend to like the way that observable schedulers and scheduling operators are often usefully explicit in halting computations while still being largely automated in the time domain.

Certainly my gut instinct with this specific library is seeing if the stuff being done with it might be a cleaner fit in something like RxOcaml, but I realize I'm in something of a minority in preferring explicit observable operators over implicit "computation signals".

Laziness and weak connections makes sense as differentiators.

However I'm not sure Excel is such a great illustration in that case, as it's neither lazy nor weakly connected; at least at the surface.

So I remember having physics homework a quarter century ago at university where we had to use Excel to determine a static electric potential field, by defining all cells in the grid as "the average value of the four surrounding cells", except the edge cells and source/sink cells which would get actual concrete values.

I distinctly remember being amazed that it would just iterate until it reached equilibrium (maybe we had to change some setting somewhere first though, I never really used Excel before or after that). I think you could change a value mid-iteration, and the grid would just continue on with the previously calculated cell values, instead of start over from scratch. That's basically "weakly connected", isn't it?

(anyway, the real challenge is to find a practical use for Excel's hidden fractal powers https://www.youtube.com/watch?v=b-Fa6HtvGtQ)

What does weak connections mean in this context?

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.

Reply on news.ycombinator.com