[neel_k]

Surprisingly, FRP doesn't have anything to do with dataflow constraints at all.

In FRP, a program is fundamentally a function of type Stream Input → Stream Output. That is, a program transforms a stream of inputs into a stream of outputs. If you think about this a bit more, you realise that any implementable function has to be one whose first k outputs are determined by at most the first k inputs -- i.e., you can't look into the future. That is, these functions have to be causal.

The causality constraint implies (with a not-entirely trivial proof) that every causal stream function is equivalent to a state machine (and vice-versa) -- i.e., a current state s, and an update function f : State × Input → State × Output. You get the stream by using the update function to produce a new state and an output in response to each input. (This is an infinite-state Mealy machine for the experts.)

Note that there is no dataflow here: it's just an ordinary state machine. As a result, the GUI paradigm that traditional FRP lends itself to the best are immediate mode GUIs. (FRP can be extended to handle asynchronous events, but doing so in a way that has the right performance model is not trivial. Think about how you'd mix immediate and retained mode to get an idea about the issues.)

When I first started working on FRP I thought it had to be dataflow -- my first papers on it are actually about signals libraries like the one in the post. However, I learned that basing it on dataflow and/or incremental computation was both unnecessary and expensive. IMO, we should save that for when we really need it, but shouldn't use it by default.

[mpweiher]

A couple of notes:

1. You seem to be confusing "dataflow constraints" with "dataflow". Though related, they are not the same.

2. Yes, the implementation of Rx-style "FRP" (should have used the scare quotes to indicate I am referring to the common usage, not actual FRP as defined by Conal Elliott) has deviated. And has deviated before. This also happened with Lucid.

3. However, the question is which of the two is the unnecessary bit. As far as I can tell, what people actually want from this is "it should work like a spreadsheet", so dataflow constraints (also known as spreadsheet constraints). This is also how people understand when used practically. And of course dataflow is also where all this Rx stuff came from (see Messerschmitt's synchronous dataflow)

4. Yes, the synchronous dataflow languages Lustre and Esterel apparently can be and routinely are compiled to state machines. In fact, if I understood the papers correctly the synchronous dataflow languages are seen as a convenient way to specify state machines.

5. It would probably help if you added some links to your papers.

[inglor]

Also, as someone who both works on open source reactive stuff (like MobX) and literally works on a spreadsheet app (Excel) I can say what we do is entirely different from what these systems do because of different constraints and both are reactive.

[aatd86]

I'm curious. How so?

[inglor]

In a gist: MobX just keeps the whole dependency graph of what data needs to update when what computed runs. Excel can't do that because it has to be able to work on large files with impartial data.

[aatd86]

Aren't excel formulas the expression of data dependency graphs?

In which case it is kept in the document?

[coldtea]

Isn't the Excel document still in memory?

[inglor]

Mathematically, RxJS and Vue/Solid Qwik like FRP are equivalent. There is interesting proof by Meijer (who invented Rx) in the famous "duality and the end of reactive". https://www.youtube.com/watch?v=SVYGmGYXLpY

[mpweiher]

> Mathematically, RxJS and Vue/Solid Qwik like FRP are equivalent.

Yes, these are basically the same thing. However, they have little to do with Conal Elliott's "FRP". Which itself is also badly named.

> Meijer (who invented Rx)

Well "invented". What's a bit surprising is that with both Rx and the Rx-style "FRP", there either is no public history of the ideas at all (Rx) or it is patently wrong (Rx-style "FRP"). Or a bit of both.

For example, the "Reactive" part of Rx-style FRP appears to come from the definition of system styles by Harel. Both the connection of synchronous dataflow with the term "Reactive" and with FP languages are made in the paper on Lustre, which is a language that integrates synchronous dataflow into an FP language. But there is nothing inherently FP-ish about synchronous dataflow, it was previously integrated into to the imperative language Esterel, and they also made a variant of C with synchronous dataflow.

Again, nobody mentions this, it is all presented as having been invented out of thin air and the principles of Functional Programming. (Or as having come from Conal Elliott's FRP, which is not true. Ask Conal Elliott).

Once I figured out the connections, I asked Erik Meijer, who has "I am the original inventor of Rx..." in his bio. He admitted that he was "inspired" by synchronous dataflow. And of course that is pretty much all it is. Except they dropped the requirement for it to be synchronous.

What do you get when you drop "synchronous" from "synchronous dataflow"? FRP, obviously ;-)

Just like Objective-C is Smalltalk + C, and Objective-C - C is ... Swift?

Controlling narratives is important.

[inglor]

All this is documented in Meijer's actual paper though? (Your mouse is a database) as well as his aformentioned talk (duality and the end of reactive).

He for sure invented observables (as we know it and as the mathematically dual of enumerables) - that doesn't mean it was the first ever reactive system or the concept of data being dependent of other data.

If I remember correctly he also explicitly talks abut Conal FRP and notations in https://www.youtube.com/watch?v=pOl4E8x3fmw if interested

[mpweiher]

I have seen plenty of Erik's talks and certainly read Your mouse is a database a bunch of times.

What is "documented" there is the alternate history of all this coming out of fundamental insights into FP and dualities and all that.

But that isn't the case, it just sounds a lot better than "I found a really complicated way to map dataflow onto FP concepts".

But we as an industry just love complicated.

[Paradigma11]

I think the important contribution of Meijer and RX is realizing the duality of IEnumerable and IObservable which enabled them to use the same programming constructs. The meat of RX is in all the combinators so you can express complex behaviours very succinctly.

[mpweiher]

Hmm...Smalltalk had the same iteration methods over streams and collections since at least Smalltalk-80, so not sure what the important contribution here is.

(Waiting for the LISPers to chime in...)

[inglor]

An observable is not the same as a Smalltalk stream, directionality wise. Smalltalk streams are like unix streams or a C stream.

[duped]

> Note that there is no dataflow here: it's just an ordinary state machine.

It sounds like you've converted data-flow to its state-space form. It's still data flow, just in a variant that might be easier to compute.

FWIW you probably need a pair of functions :

    next state = F(input, current state)  
    output     = G(input, current state)

Which in the signal-processing/control systems world is

    s = Ax + Bs
    y = Cx + Ds

Aka the "state space" formulation where A, B, C, and D are matrices, x is the input, s is the state, and y is the output. There are infinite ways to formulate the state space and infinite equivalent signal flow graphs that represent the same thing.

[Joker_vD]

> any implementable function has to be one whose first k outputs are determined by at most the first k inputs -- i.e., you can't look into the future. That is, these functions have to be causal.

    def f(input_stream):
        i = next(input_stream)
        j = next(input_stream)
        yield i + j
        f(input_stream)

This function produces k outputs when given 2*k inputs, so it's either acausal or impossible to execute. Right?

[mananaysiempre]

For GP’s stream-transformer / state-machine equivalence to work, you need to sprinkle option types throughout so each input yields some kind of output, even if empty. So more like

  def co():
      i = yield None # hurray for off-by-one streams
      j = yield None
      while True:
          i = yield i + j
          j = yield None

This won’t help if the output stream produces more than one output item from each input item. You could sprinkle lists instead, but in reality multiple simultaneous events have always been a sore point for FRP—in some libraries you can have them (and that’s awkward in some cases), in some you can’t (and that’s awkward in others).

[Joker_vD]

But I am not criticizing his stream-transformer / state-machine equivalence, I am just curious why he thinks functions of Stream A -> Stream B have to produce exactly 1 output for exactly 1 input.

Now, I know that Haskell in its pre-monad days used to have main have signature [Response] -> [Request]: the lists being lazy, they're essentially streams. Each Request produced by the main would result in a Response being provided to it by the runtime. This model actually has to be strictly 1-to-1, and indeed, it was so easy to accidentally deadlock yourself that switching to IO monad was quite welcomed, according to SPJ in his "Tackling the Awkward Squad" paper.

[mananaysiempre]

I guess what I wanted to say was that to me (given that the comment was presumably targeted at people who already know how all of FRP, stream transformers, and state transducers work, or can at least make a good guess) it was within the limits of acceptable sloppiness to mix up (State, Input) -> (State, Output), (State, Input) -> (State, Maybe Output), and (State, Input) -> (State, [Output]), or the equivalent on the stream transformation side. The point of the comment does not really depend on what you choose here.

[agumonkey]

someone calls conal elliott