It’s used by frameworks Vue, SolidJS, Svelte, Ember, Angular, and there’s a few different implementations for React like Mobx and Jotai. There’s a few different algorithms for how to propagate changes and evaluate the DAG, I believe SolidJS2 uses a height-based algorithm similar to Incremental.
There are a few of these for Rust as well, Leptos is an example in UI frameworks, and Salsa is an example in general incremental computing, used in rust-analyzer.
You can build some lightweight dependency graphs that flush out quickly. You don’t need to describe how the signal has changed, just that it might have changed, then flush dependencies on change (some listeners might be notified of a change they don’t care about anymore) and re-register them when they come back for fresh data again.
But incremental computation isn’t exactly functional reactive programming. They are different domains in practice that often get thrown together because the problem they address can overlap. Incremental computation explicitly derives a function that can operate on deltas, FRP might just use damage and repair instead.
As the authors highlight: "Noria is not a UI framework at its core. Instead, it’s a platform for incremental computations.". But currently they happen to use it to optimize gui rendering in JetBrains Air IDE.
Oh cool I was working on something similar awhile back and couldn’t find much precedent. The project got retired as our use case went away. But I’d love to revisit it. It’s still on npm as “data-rambler”.
Idea was a DSL that could be loaded into a JS runtime, then fed data streams. Your module would transform that data into various output streams which could then be fed to a separate reporting library. Powering dynamic reports based on a template.
Our first iteration was already pretty powerful but I had some big plans to bring it into a more JS feeling syntax to reduce complexity.
As far as I can tell, incremental the library aims to solve the problem of partially hydrating a computation graph when source data is altered. This approach is similar to the one pursued by (well designed) build systems and is common in the FP world. [2] This has many use cases and is very cool.
In addition, in the sphere of incremental computation, there exists Differential Dataflow, Timely Dataflow (adjacent), and DBSP. Systems like Feldera are built on DBSP. Materialize is lead by some DD guys.
Personally, I am pursuing an orthogonal approach specifically for the problem of financial data and financial workloads, There exists huge, very important problems to solve! [1]
Goldman took the same approach with instrument pricing ~30 years ago. I recall long discussions about "Node Purpling" in my ~13 year tenure there.
Computer Science has evolved, and AFAICT this is not a graph approach, but things like differentiation are computationally expensive, and therefore you want to minimize the number of times you do it to as close to the theoretical minimum.
The best description about how it became a problem is one of the paragraphs.
"New starters take an exceptionally long time to get up to speed - and that's if they don't resign in fit of pique as soon as they see the special, mandatory, in-house IDE (as I nearly did). Even months in, new starters are still learning quite fundamental new things: there is a lot that is different."
I think it took me til I was there around two and a half years to fully comprehend it when I was working on it. Not much modern training til they figured out they had to teach it again that was better. The worst part is to make an UI around it coding it and it wasn't approved for new projects.
Libraries like React are pretty efficient with skipping work by using Virtual Dom, but constructing this vdom still takes time. Bonsai makes the vdom incremental and it is pretty fun to work with.
I built a desktop UI library with it by targeting (now unmaintained) Revery. It is using a much older version of Bonsai however: https://github.com/ozanvos/bonsai_revery
I was very curious about Dataflow programming years ago - I think a lot of people were coming at this problem from various angles. This specific library immediately reminded me of Javelin from Clojure [0]
Over at Feldera, we focus on IVM for SQL, but incremental computing problems show up far and wide: UIs, spreadsheets, control planes, compilers and more.
One thing I've never fully grokked is how this differs from an observable pattern where one can publish new values to inputs, propagate that through the computation, and push newly computed values to listeners.
I guess there's probably optimizations around change detection and stopping the propagation if there's no change (though observables can do that as well). The stabilize command also makes things interesting as a way to batch changes together before recomputing (but again, doable with observables too).
Is the delta primarily coming from introspection and automatically building the compute graph? Or is there something more fundamental that I'm missing?
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.
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?
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.
Roughly, you subscribe and listen to an observable. Incrementals are more like a cache across some DAG of computation + state that lets you optimize by only recomputing what needs to be recomputed.
That's how I was thinking about it too. At first glance it feels very close to reactive programming with dependency tracking. I'm curious whether the real advantage is the API ergonomics or if there are optimizations under the hood that wouldn't be practical with a typical observable implementation.
I mean, it's fundamentally just a graph, but it's a way of correctly and efficiently computing changes in massive, dynamic graphs. Let's imagine you have a diamond shaped subgraph that fans out to hundreds of intermediary nodes before collapsing down again via and paths with different "lengths". And what if some of those paths have e.g. min(A, B) where the max side is the only one changing?
A naive observer approach will 1) compute that potentially exponential blow-up very inefficiently and 2) probably have "concurrency" issues. This library will be close to optimal and correct, even if you start dynamically changing the graph structure.
But yes, you can achieve the same thing with observers and other kinds of approaches. Most of them just a lot harder to get right while avoiding performance cliffs.
One thing i have always linked about Jane street projects is that they tend to package ideas that have existed in research or niche system into something developers can actually use. Even if you never adopt the library, the design docs are usually worth reading.
Can'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
Usually these kinds of systems either don't scale dynamically or have caching issues. The first example, a spreadsheet, is "easy" because there are a fixed amount of cells to track. A GUI can be a lot harder (imagine sub windows and sub-sub windows dynamically popping up and tracking some redundant and some unique "computations". Entities can appear and then be removed at random). Though the wording carefully says "constructing views" so maybe it doesn't handle dynamism
Jane street was/is a top user of ocaml, they kind of flushed their reputation down the toilet with they massive fraud in the asian markets. IIRC the entire company got banned from trading inside India, hongkong etc.
After they got caught most of their online posts/videos either got deleted, or locked so you could not comment on them.
I had hoped their front guy for ocaml, Ron Minsky had atleast made some sort of statement. Currently no ones know how deep that fraud went, but what we know ocaml was used in the fraud, damagine ocaml ecosystem too.
In C# a dependency graph that automatically updates only the affected dependencies can be implemented using events and/or functors and/or data binding.
I do not understand what is the big deal with Increment. Is it more efficient because it is written in OCaml rather than C#?
I have built something similar like this for my fund 7 years ago. We were doing parametric optimization on large computational graphs. I have never programmed Ocaml but my understanding is introspection is kind of a weak spot for the language. Curious language choice! I know Ocaml is fast, about 1-2x speed of C, on par with Java.
This style of reactive programming is quite popular in JavaScript UI frameworks these days under the moniker “signals”, with a proposal for standardization here: https://github.com/tc39/proposal-signals#-javascript-signals...
It’s used by frameworks Vue, SolidJS, Svelte, Ember, Angular, and there’s a few different implementations for React like Mobx and Jotai. There’s a few different algorithms for how to propagate changes and evaluate the DAG, I believe SolidJS2 uses a height-based algorithm similar to Incremental.
I’ve been fooling around with an implementation that uses an Int32Array arena to allocate nodes and link them together with linked lists without paying O(dependency edges) GC load: https://github.com/justjake/dalien-signals/tree/dalien-signa...
There are a few of these for Rust as well, Leptos is an example in UI frameworks, and Salsa is an example in general incremental computing, used in rust-analyzer.
Another way to look at this sort of thing is as a build system with automatically tracked dependencies. One such build system is tup, which instruments build jobs to detect what files they read to establish dependency relationships. Interesting reading from the author: https://gittup.org/tup/build_system_rules_and_algorithms.pdf, see also the classic Build Systems à la Carte https://www.microsoft.com/en-us/research/wp-content/uploads/...
You can build some lightweight dependency graphs that flush out quickly. You don’t need to describe how the signal has changed, just that it might have changed, then flush dependencies on change (some listeners might be notified of a change they don’t care about anymore) and re-register them when they come back for fresh data again.
But incremental computation isn’t exactly functional reactive programming. They are different domains in practice that often get thrown together because the problem they address can overlap. Incremental computation explicitly derives a function that can operate on deltas, FRP might just use damage and repair instead.
It looks as if there is a significant difference in treating updates to complex objects, and probably scheduling as well.
Another notable example: JetBrains Noria ( https://blog.jetbrains.com/fleet/2023/02/fleet-below-deck-pa... ).
As the authors highlight: "Noria is not a UI framework at its core. Instead, it’s a platform for incremental computations.". But currently they happen to use it to optimize gui rendering in JetBrains Air IDE.
Oh cool I was working on something similar awhile back and couldn’t find much precedent. The project got retired as our use case went away. But I’d love to revisit it. It’s still on npm as “data-rambler”.
Idea was a DSL that could be loaded into a JS runtime, then fed data streams. Your module would transform that data into various output streams which could then be fed to a separate reporting library. Powering dynamic reports based on a template.
Our first iteration was already pretty powerful but I had some big plans to bring it into a more JS feeling syntax to reduce complexity.
This is cool.
As far as I can tell, incremental the library aims to solve the problem of partially hydrating a computation graph when source data is altered. This approach is similar to the one pursued by (well designed) build systems and is common in the FP world. [2] This has many use cases and is very cool.
In addition, in the sphere of incremental computation, there exists Differential Dataflow, Timely Dataflow (adjacent), and DBSP. Systems like Feldera are built on DBSP. Materialize is lead by some DD guys.
Personally, I am pursuing an orthogonal approach specifically for the problem of financial data and financial workloads, There exists huge, very important problems to solve! [1]
[1] https://modolap.com
[2] Signals And Threads episode on the subject https://signalsandthreads.com/build-systems/
> https://modolap.com
Redirect to a 2k USD stripe payment with no explanation when clicking on the main callout button is a pretty baller move.
One man's baller is another man's insufficiently baller.
Email me for details, pricing & installations, or your target use case, would love to talk. In addition, if you have any feedback.
ron at modolap dot com
Goldman took the same approach with instrument pricing ~30 years ago. I recall long discussions about "Node Purpling" in my ~13 year tenure there.
Computer Science has evolved, and AFAICT this is not a graph approach, but things like differentiation are computationally expensive, and therefore you want to minimize the number of times you do it to as close to the theoretical minimum.
Edit: Related HN discussion https://news.ycombinator.com/item?id=36006737
Yea and this created "bank python" informally a good article is here.
https://calpaterson.com/bank-python.html
The best description about how it became a problem is one of the paragraphs.
"New starters take an exceptionally long time to get up to speed - and that's if they don't resign in fit of pique as soon as they see the special, mandatory, in-house IDE (as I nearly did). Even months in, new starters are still learning quite fundamental new things: there is a lot that is different."
I think it took me til I was there around two and a half years to fully comprehend it when I was working on it. Not much modern training til they figured out they had to teach it again that was better. The worst part is to make an UI around it coding it and it wasn't approved for new projects.
That article was fascinating, thanks for sharing it. I wonder if all banks use the same "bank Python" or if they all forked it in different ways?
If you find this interesting, also check out their UI library called Bonsai that built on top of Incremental: https://github.com/janestreet/bonsai/
Libraries like React are pretty efficient with skipping work by using Virtual Dom, but constructing this vdom still takes time. Bonsai makes the vdom incremental and it is pretty fun to work with.
I built a desktop UI library with it by targeting (now unmaintained) Revery. It is using a much older version of Bonsai however: https://github.com/ozanvos/bonsai_revery
I was very curious about Dataflow programming years ago - I think a lot of people were coming at this problem from various angles. This specific library immediately reminded me of Javelin from Clojure [0]
[0]: https://github.com/hoplon/javelin
Over at Feldera, we focus on IVM for SQL, but incremental computing problems show up far and wide: UIs, spreadsheets, control planes, compilers and more.
One thing I've never fully grokked is how this differs from an observable pattern where one can publish new values to inputs, propagate that through the computation, and push newly computed values to listeners.
I guess there's probably optimizations around change detection and stopping the propagation if there's no change (though observables can do that as well). The stabilize command also makes things interesting as a way to batch changes together before recomputing (but again, doable with observables too).
Is the delta primarily coming from introspection and automatically building the compute graph? Or is there something more fundamental that I'm missing?
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...
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.
https://www.scattered-thoughts.net/writing/an-opinionated-ma...
Can help map out the landscape.
Roughly, you subscribe and listen to an observable. Incrementals are more like a cache across some DAG of computation + state that lets you optimize by only recomputing what needs to be recomputed.
There's a really good talk from Ron Minsky here: https://www.janestreet.com/tech-talks/seven-implementations-...
Must make building backpropation algorithms really easy.
That's how I was thinking about it too. At first glance it feels very close to reactive programming with dependency tracking. I'm curious whether the real advantage is the API ergonomics or if there are optimizations under the hood that wouldn't be practical with a typical observable implementation.
I mean, it's fundamentally just a graph, but it's a way of correctly and efficiently computing changes in massive, dynamic graphs. Let's imagine you have a diamond shaped subgraph that fans out to hundreds of intermediary nodes before collapsing down again via and paths with different "lengths". And what if some of those paths have e.g. min(A, B) where the max side is the only one changing?
A naive observer approach will 1) compute that potentially exponential blow-up very inefficiently and 2) probably have "concurrency" issues. This library will be close to optimal and correct, even if you start dynamically changing the graph structure.
But yes, you can achieve the same thing with observers and other kinds of approaches. Most of them just a lot harder to get right while avoiding performance cliffs.
One thing i have always linked about Jane street projects is that they tend to package ideas that have existed in research or niche system into something developers can actually use. Even if you never adopt the library, the design docs are usually worth reading.
Electric Clojure does incremental rendering that crosses the client/server boundary: http://electric.hyperfiddle.net/
The closest thing to Electric (IMO) is SolidJS, but frontend only: https://www.solidjs.com/
Can'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
It might be worth reading this in concert with
https://hn.algolia.com/?q=flow+based+programming+
pardon my ignorance but is Ocaml performant enough? Why isn't something like this coded in say, C++?
For those interested in incremental systems, I recommend checking out DBSP. I thought it was pretty neat.
Where is it actually explained how it works..?
Usually these kinds of systems either don't scale dynamically or have caching issues. The first example, a spreadsheet, is "easy" because there are a fixed amount of cells to track. A GUI can be a lot harder (imagine sub windows and sub-sub windows dynamically popping up and tracking some redundant and some unique "computations". Entities can appear and then be removed at random). Though the wording carefully says "constructing views" so maybe it doesn't handle dynamism
Whenever I see something in OCaml I assume it's Jane Street and that ends up correct a surprising amount of the time.
Jane street was/is a top user of ocaml, they kind of flushed their reputation down the toilet with they massive fraud in the asian markets. IIRC the entire company got banned from trading inside India, hongkong etc.
After they got caught most of their online posts/videos either got deleted, or locked so you could not comment on them.
I had hoped their front guy for ocaml, Ron Minsky had atleast made some sort of statement. Currently no ones know how deep that fraud went, but what we know ocaml was used in the fraud, damagine ocaml ecosystem too.
I maintain a similar library more focused on data engineering needs: https://docs.metaxy.io/ maybe it is useful for more people.
I think websharper's Var are similar to this, and it is really great to develop dynamic web interfaces (in fsharp).
In C# a dependency graph that automatically updates only the affected dependencies can be implemented using events and/or functors and/or data binding.
I do not understand what is the big deal with Increment. Is it more efficient because it is written in OCaml rather than C#?
Another related but semantically distinct package with great developer ergonomics is the FRP library React -- https://erratique.ch/software/react/doc/React/index.html
Very satisfying to use when you manage to find a problem that is suited to this type of approach.
I have built something similar like this for my fund 7 years ago. We were doing parametric optimization on large computational graphs. I have never programmed Ocaml but my understanding is introspection is kind of a weak spot for the language. Curious language choice! I know Ocaml is fast, about 1-2x speed of C, on par with Java.
Not trying to be pedantic but do you mean half the speed of C?
This reminds me of https://github.com/electric-sql/d2ts. Not sure they're comparable, but they seem to be aiming at the same problem.
Kobe!