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/...
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.
but yeah to zoom out, the semantic boundaries and even definitions of terms in this area are kind of fuzzy and i don’t think it’s interesting to try too hard to sort stuff into a taxonomy unless you’re going to define all the parts of your taxonomy and provide a bunch of examples; these terms are not well-defined enough otherwise and arguing about ill-defined semantics is not my idea of a good time.
For example how to taxonomize something like Signia, which has fair bit of history sensitivity but is mostly concerned with diffs (https://signia.tldraw.dev/docs/incremental#using-diffs-in-co...), like Incremental uses logical clocks for validation, but is much more “pull” oriented in its recomputation/“stabilize” algorithm? To me it sounds like you’d put it in the “incremental computation” bucket because deltas; but Incremental itself doesn’t seem too concerned with deltas at the root of the library, i didn’t find any mention of them in the into docs and think it sounds more like js “signals”. https://github.com/janestreet/incremental/blob/master/src/in...
In early FRP systems, you could just plug in a t and compute a signal network (well, behavior) at any point in time, so the entire history of values needed to be saved. Modern FRP abondons first class time and focuses more on change propagation (you are told when your signal computation changes at some end point, otherwise no history is saved).
Anyways, it’s been a decade since I’ve done this stuff. Erik Miejer kind of muddied the waters with his observable stream work, and people started calling that FRP instead. I see the Jane street blog post is based on Evan’s work, I don’t remember much about it.
I’ve always implemented purely non-history preserving signals (Modern FRP) just because they are incredibly easy/efficient to implement and give you 99.9% of what you want and…first class time is just not useful unless you are doing simulations or something (I’ve never called my work FRO, just FRP inspired). It’s also easier to explain to people a continuous time function (the UI label changes as the values it is bound to change). I even have some work where I translate it down to WPF data binding in C# using the DLR to compile signal expressions.
The incremental computation landscape is pretty vast, but I always found that memoizing sub-trees of a computation and then doing a standard damage and repair algorithm to recompute subtrees that depend on changed values works well enough for most use cases. Again, not really related to FRP, but I somehow got involved in both worlds a couple of decades ago. You could try to define a function over the delta, but it’s incredibly dependent on the domain unless you restrict yourself to a differentiable programming language.
https://wiki.haskell.org/Research_papers/Functional_reactive...
This feels related to many other topics and various strategies, like incremental parsing/compilation/computation, reactivity, CRDTs (conflict-free replicated data type) and distributed computing. About coordinating state changes, reconciling differences, managing dependencies and derived values.
@jitl, the "Data oriented signal library", dalien-signals, looks very interesting and useful, particularly for efficient UI rendering like large tables or maybe editors. I'll enjoy exploring it.
[dead]
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.
[dead]
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
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.
Some things to search for:
JP Morgan Athena BofA Quartz Kirat Singh Mark Higgins
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]
[2] Signals And Threads episode on the subject https://signalsandthreads.com/build-systems/
Redirect to a 2k USD stripe payment with no explanation when clicking on the main callout button is a pretty baller move.
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
The benchmark of 2m black-scholes evals/sec is meaningless without additional context. Also seems a couple orders of magnitude slower than what I’d expect even for a single core. What exact transformations are being done, and what’s the throughput in GB/sec? Is it multi threaded? Benchmark against the equivalent query in kdb+ and ClickHouse?
Not true as of last deployment.
> but zero technical detail
What additional technical detail would you be interested in?
> Also seems a couple orders of magnitude slower than what I’d expect even for a single core.
1) it's more than 2m/s on a MacBook AIR 2) Most of the latency is networking. This was a preliminary setup with a client / server over websockets where the book of 1m contracts combination of (strike, exp_date). Each insert only after a corresponding query has been returned (over the wire) from the previous insert. I can agree the eval isn't great; as in, the throughput is much higher.
> What exact transformations are being done
This is provided in the blog post.
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?
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...
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".
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.
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)
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.
There's a really good talk from Ron Minsky here: https://www.janestreet.com/tech-talks/seven-implementations-...
Can help map out the landscape.
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.
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
The closest thing to Electric (IMO) is SolidJS, but frontend only: https://www.solidjs.com/
[deleted]
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.
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
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.
[dead]
I do not understand what is the big deal with Increment. Is it more efficient because it is written in OCaml rather than C#?
[dead]
At that point I'd guess most projects start to build up their own set of primitives (e.g., containing subsets of particular graphs) that they can hand-optimize better than these general purpose computation graphs. That's what I ended up doing so I could better control the tradeoff around which operations should be batched, heuristics around how cheap certain operations are (especially based on the elements at the time), more complex dependency tracking when working with data outside the graph, etc.
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
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.
[deleted]
TL;DR: OCaml is usually going to be a bit slower than C++, but faster than Java, while rivaling Rust and Haskell in terms of expressive power.
Caveat: a lot of the power comes from the tooling. Last I checked, syntax extensions were external preprocessors, just with standardized APIs. And you need those extensions for things that are handled by (in-language) macros in Rust (like deriving string representation for a record). Without the tooling, OCaml can get a bit tedious/boilerplate-y. OTOH, after a period of instability and competing solutions, the tooling mostly settled down, and enabling the important parts is often a single line in the config. It's not a situation unique to OCaml, but if you look at the language docs only, you'll miss half of what OCaml development normally offers.
Very satisfying to use when you manage to find a problem that is suited to this type of approach.
[dead]
[dead]
[dead]
[dead]
[dead]
[dead]
[dead]