Incremental – A library for incremental computations

[dead]

my understanding of FRP is the inverse of your description, I use the same definition of “functional reactive programming” as in this Jane Street blog post on the subject https://blog.janestreet.com/breaking-down-frp/ : FRP is history sensitive and wants to compute over some stream of events explicitly - and the sort of events we expect the system to handle are UI events like mouse motions, clicks, and FRP is expected to turn those into application semantics. Self-adjusting computation (like Incremental or js “signals” like alien-signals) is mostly history-insensitive by default because it’s lazy and seeks to recompute a node once during stabilize() no matter how many times an input changed since the last stabilize(). I definitely do not think “signals” in the JS/TC39 formulation of the concept is FRP: not nearly enough attention paid to first-class events.

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

Is anyone aware of a version of this focused on very speed sensitive, low-level incremental computation? Like perhaps a compiler that generated a kernel for doing an incremental computation on a static graph?

You might want to go over the original Elliot/Hudak work? It’s a bit obtuse since it’s all in Haskell, but signals were never meant to be historical accumulators unless you set them up that way. Signals are continuous values, they don’t reveal discrete events like streams do, that’s the main distinction between them, your signal computations then can be viewed as a continuous value derived from other continuous values.

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.

[flagged]