Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Signals, the push-pull based algorithm

willybrauner.com

Post reply on HN
Print view View original

31–40 of 42 posts

Re: Signals, the push-pull based algorithm

#31

Post by qprofyeh »

willybrauner wrote: post #14
fabianholzer wrote: post #4

I do not want to distract from the content of the article, which is highly relevant for folks who built UIs with frameworks that are conceptually based on signals, but the way that the reading experience is designed really great, in particular the guided reading flow through the instructive code path is something that I rarely have seen done at all, and this even works pretty well on mobile. It's a delightful reminde…

I searched for the "right way" to explain this algorithm, and ultimately parsing the code was the clearest for me. This isn't always true; sometimes a graph or an interactive module has more impact; it really depends on the topic. Thanks for the feedback.

Kudos! Minor detail: the code could use a border or bg color different than the text, so that they’re more distinct.

Re: Signals, the push-pull based algorithm

#33

Post by boxfire »

xkbear89 wrote: post #30
noelwelsh wrote: post #5

Overall, very nice article. A few notes: * I think the first implementation in JS land was Flapjax, which was around 2008: https://www.flapjax-lang.org/publications/ * The article didn't discuss glitch-freedom, which I think is fairly important.

[flagged]

So yeah topological sorting is one element, but that global stack is a data race! You need to test set inclusion AND insert into it in an ordered way. Global mutex is gross. To do so lock-free could maybe be done with a lock free concurrent priority queue with a pair of monatomic generation counters for the priorities processed then next, then some memo of updates so that the conflicting re-update is invalidated by violation the generation constraint. I see no less than 3 CAS, so updates across a highly contentious system get fairly hairy. But still, a naive approach is good enough for the 99% so let there be glitches!

Re: Signals, the push-pull based algorithm

#34

Post by dunham »

I know it is out of scope for this article, but there are variants where the operations are monadic rather than applicative and the shape of the graph can change depending on values. And also variations with state - where history can be taken into account.

Jane street briefly summarizes some options here: https://blog.janestreet.com/breaking-down-frp/

And they have an interesting talk on the trade-offs and how their own system, incremental, evolved: https://blog.janestreet.com/seven-implementations-of-increme...

Re: Signals, the push-pull based algorithm

#35

Post by [deleted] »

boxfire wrote: post #33
xkbear89 wrote: post #30

Earlier quoted context omitted.

[flagged]

So yeah topological sorting is one element, but that global stack is a data race! You need to test set inclusion AND insert into it in an ordered way. Global mutex is gross. To do so lock-free could maybe be done with a lock free concurrent priority queue with a pair of monatomic generation counters for the priorities processed then next, then some memo of updates so that the conflicting re-update is invalidated by v…

[deleted]

Re: Signals, the push-pull based algorithm

#36

Post by aatd86 »

boxfire wrote: post #33
xkbear89 wrote: post #30

Earlier quoted context omitted.

[flagged]

So yeah topological sorting is one element, but that global stack is a data race! You need to test set inclusion AND insert into it in an ordered way. Global mutex is gross. To do so lock-free could maybe be done with a lock free concurrent priority queue with a pair of monatomic generation counters for the priorities processed then next, then some memo of updates so that the conflicting re-update is invalidated by v…

Can the reactive graph even be updated concurrently if the UI depends on it though? Because the UI is likely to run in its own single thread...

Re: Signals, the push-pull based algorithm

#39

Post by mananaysiempre »

mpweiher wrote: post #29
mananaysiempre wrote: post #19

Earlier quoted context omitted.

I wrote a whole screed here about how glitches are evil and Rx is evil for teaching people they’re normal, but then I thought about it a bit more— The system as described isn’t actually glitchy, is it? It doesn’t eagerly run any user computations, just dirtying, and that is idempotent so the order is irrelevant. It’s also a bit useless because it only allows you to pull out values of your own initiative, not subscrib…

> whether push-pull as TFA understands it has much to do with Conal Elliott’s definition. Virtually nothing that is getting sold/branded as "FRP" has anything to do with Conal Eliott's definition. I once gave a long talk about this here in Berlin, but I don't remember if there was a video. I've also explained it on twitter a bunch of times, including this memorable sequence: https://x.com/mpweiher/status/135371692632…

>> whether push-pull as TFA understands it has much to do with Conal Elliott’s definition.

> Virtually nothing that is getting sold/branded as "FRP" has anything to do with Conal Eliott's definition.

True but not what I meant. The article implicitly (and, in the links at the end, explicitly) refers to his 2009 paper “Push-pull functional reactive programming”, which describes a semantic model together with an specific implementation strategy.

So I was wondering if TFA’s “push-pull” has anything to do with Elliott 2009’s “push-pull”. I don’t think so, because I remember the latter doing wholly push-based recomputation of discrete reactive entities (Events and Reactives) and pull-based only for continuous entities that require eventual sampling (Behaviors).

With that said, I find it difficult to squeeze an actual algorithm out of Elliott’s high-level, semantics-oriented discussion, and usually realize that I misunderstood or misremembered something whenever I reread that paper (every few years). So if the author went all the way to reference this specific work out of all the FRP literature, I’m willing to believe that they are implying some sort of link that I’m not seeing. I would just like to know where it is.

Re: Signals, the push-pull based algorithm

#40

Post by Groxx »

aatd86 wrote: post #36
boxfire wrote: post #33

Earlier quoted context omitted.

So yeah topological sorting is one element, but that global stack is a data race! You need to test set inclusion AND insert into it in an ordered way. Global mutex is gross. To do so lock-free could maybe be done with a lock free concurrent priority queue with a pair of monatomic generation counters for the priorities processed then next, then some memo of updates so that the conflicting re-update is invalidated by v…

Can the reactive graph even be updated concurrently if the UI depends on it though? Because the UI is likely to run in its own single thread...

yea, this is in javascript. it's inherently single-threaded in almost all contexts (e.g. node.js shared memory where you're intentionally bypassing core semantics for performance, and correctness is entirely on you)
Post reply on HN