Incremental – A library for incremental computations

mempko

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.

RandomBK

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?

fadesibert

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

runtime_lens

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.

raphinou

I think websharper's Var are similar to this, and it is really great to develop dynamic web interfaces (in fsharp).

dh2022

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#?

djtango

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

jitl

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/...