4 ms·

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 Out

by neel_k 3y ago

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.

agumonkey 3y ago
someone calls conal elliott
mpweiher 3y ago
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 3y ago
  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 https://www.youtube.com/watch?v=SVYGmGYXLpY
  - mpweiher 3y ago
    > 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.
    - Paradigma11 3y ago
      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.
Joker_vD 3y ago
> 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 3y ago
  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 3y ago
    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 3y ago
      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.
duped 3y ago
> 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.

by neel_k 3y ago

agumonkey 3y ago

someone calls conal elliott

mpweiher 3y ago

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 3y ago
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 https://www.youtube.com/watch?v=SVYGmGYXLpY
- mpweiher 3y ago
  > 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.
  - Paradigma11 3y ago
    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.

Joker_vD 3y ago

> 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 3y ago
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 3y ago
  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 3y ago
    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.

duped 3y ago

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