Comment by jitl | Hacker News Reader

Comment by jitl | Hacker News Reader

Parent Full thread

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.

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

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.

I assume you mean "Functional Reactive Animation" (1997) by Conal Elliott and Paul Hudak? While searching for this, I found a great collection of papers on this topic of Functional Reactive Programming in the Haskell language wiki. Most are by Elliot and/or Hudak. Good stuff!

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.

here’s a page with a very unscientific benchmark that runs a computed signal for every pixel of a {320p, 480p, 720p, 1080p, 4k} canvas and tries to recompute 10% of the graph per frame. on my m4 macbook pro, dalien-signals manages the highest fps and lowest heap out of libraries i could find to test. i think there’s still room for improvement though, im not satisfied with cache locality of graph under heavy churn; iirc i only compact/move stuff on resize or a large deallocation batch. so theres potential for original js-heap-allocated alien-signals to be faster in spots where moving GC becomes an advantage. lemme know if my library ends up being a win for you!

https://justjake.github.io/dalien-signals/

Yes definitely for compilation. Memoizing the tree and then repairing parsing and type information on each edit is how you get super fast responsiveness with code completion. It was relevant a couple of decades ago, things are different now with AI.

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.

It looks as if there is a significant difference in treating updates to complex objects, and probably scheduling as well.

Reply on news.ycombinator.com