Switch in Arrowized FRP

[Evan Czaplicki]

Can someone explain when the switch operators in Yampa and NetWire come in handy? I get the idea of being able to switch in Signal Functions or Wires dynamically, but I just cannot see how I would actually end up using any of the functions they provide.

Is the idea of (-->) in NetWire that you would chain a bunch of them together? If so, that is quite nice.

Switching in Yampa seems to be pretty messy. Not sure what usage pattern they were going for.

Any thoughts?

[John Mayer]

I don't know how much is transferable. 

First, we don't really have a notion of a Signal that inhibits. All Signals in Elm have a value from the start of the program and always afterwards. This is not necessarily a bad thing, as it's one of the reasons why Elm maps so nicely onto the theory of event-triggered synchronous reactive components.

Second, it seems like you'd run into the issue of not being able to implement monadic signals in Elm, though that's just a hunch and I haven't attempted a rigorous proof.

Third, I think something similar can be built as a layer already:

x :: Signal (Maybe Int)

y :: Signal Int

f :: Maybe a -> b -> Either a b

f (Just v) _ = Left v

f Nothing v = Right v

andThen :: Signal (Maybe a) -> Signal b -> Signal (Either a b)

andThen = lift2 f

Note: If a and b happen to be the same type, then you can probably chain many "andThen" together.

Don't leave it up to me to find out how it might be useful thought ;-)

John

[Evan Czaplicki]

Oh, I should have clarified that this question is in the context of the Automaton library which uses the same computational model as Yampa and NetWire. I just have not added a switch function to it yet because my background was with Yampa, which did not really clarify how to create a nice API.

Monads should work fine using the record encoding for typeclasses (I sent the list a link on this a while ago). I didn't design the automaton library with this in mind, but there is no reason the majority of NetWire would not work in Elm afaik. I think the only meaningful limitation is that you can't use the IO monad, since that requires compiler support which I don't want to add at this point.

[Hank]

Unless my understanding of 'switch' is not correct ... I guess a simple but construed example would be to switch between controlling a UI element by keyboard and by mouse. E.g. add a toggle button UI element to the MovingBox Elm example which lets you alternate between moving the box by arrow keys or by dragging it with the mouse with left mouse button down.

A more realistic example I guess would be dynamically changing larger sections of the flow graph. E.g. a reactive implementation of the TCP protocol would receive a signal of IP packets from the network interface, split them into separate signals one for each remote address (IP + port), process each of them separately (e.g. transform a SYN packet into a SYN-ACK packet and using foldp for connection state), and then combining all resulting IP packet signals back into one that gets sent out the network interface. This graph will basically have to be rejigged for every new or expiring remote address, replacing the splitter, connection signals and combiner each time. Of course the new graph should include the connection signals of the old graph (minus expired ones) including their state in any foldp ongoing operations.

[John Mayer (gmail)]

This is currently possible in Elm.

First, rewrite your UI Element to respond to Either Keyboard Mouse. Then lift the keyboard using the Left data constructor, and the mouse using the Right data constructor. These signals are now the same type, so merge them. Lift that merged signal into a tuple with your toggle Book signal. Finally, use Signal.dropWhile or similar to filter the type of input based on the current state of your toggle predicate.

Note that this can scale to an arbitrary number of switched inputs; you would just need a custom either-like and predicate abstract data types.

Sent from my iPhone

--
You received this message because you are subscribed to the Google Groups "Elm Discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to elm-discuss...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
 
 

[Hank]

Of course, technically that's possible. However it defeats the point of FRP to devote computational resources only to where they are needed. Let's say I switch the toggle button to keyboard so that I can use the mouse for another purpose. Then the merging of the two signals and the dropWhile processing happens anyway with every mouse move. Those functions would constantly be churning data with no end result.

The TCP example makes this clearer because it is more extreme. Similar to what you are suggesting, let's replace the dynamic graph with a hypothetical static FRP graph in which the incoming IP packet signal is consumed by 2^48 different filter (drop) functions that each filter the IP packets for one of 2^48 possible combinations of remote IP address (2^32) and port (2^16), each producing a signal that can then be processed further special to the state of the protocol for that remote IP/port. Given only a few remote hosts are ever connected to the sever, few of the functions would actually ever pass on IP packets to their output signal ... on a busy server let's say 1000. The other 2^48 - 1000 will be churning, dropping packets to no avail.

A good analogy for "switch" would possibly that we want the FRP system to "focus on" or "only pay attention to" certain inputs. Don't pay attention to the mouse if all we want is the keyboard, don't pay attention to IP addresses/ports that we are not receiving data from.

[Evan Czaplicki]

Both of you are saying true things :) Arrowized FRP can be fully embedded in Elm, meaning adding switch or some variation is a matter of adding a few lines to this file. In other words, both approaches described here will work fine in Elm.

My initial question was more about API design. I see how switch is useful. Another example would be a game with many many screens (pause screen, actual game, item lookup, etc.) and this might benefit from breaking each component into an Automaton (or wire or SF or whatever). I am primarily curious about the operators that NetWire and Yampa use for switching.

For example, I find Yampa's API for switching extremely difficult to figure out. I know what I want to do with it, but it is unclear how I'd go about using abcSwitchBW to do that. Similarly with NetWire, I know the general wins I can acheive, but I don't know how to encode it with their API. So what would such a switchy thing look like in NetWire or in Yampa? What is better? Is there a better way than both?

The goal of the question was to figure out what the Automaton library should look like going forward. You currently have to implement a custom switch if you want to have this very switchy behavior (which I did here), but I'd like to formalize this into a nice general API.

How is Arrowized FRP different from FRP in Elm:

I think Arrowized FRP is a EDSL on a fundamental level. That is, AFRP has no way to talk about inputs within itself. It is just a series of pipes. Thus AFRP in Haskell must ultimately live in an IO monad that manages the mouse/keyboard/time/etc and, with NetWire, also determines when to push updates. The vision of FRP in Elm is to be able to manage the entire program in terms of signals. One benefit here is that you don't have to muck around with the IO monad to use AFRP, and you can design as much or as little of your program using AFRP, depending on your needs. So for Hank's example, it'd be a great fit. For anything with a fairly fixed signal graph, you would not need to AFRP, and I think that is a huge win for accessibility and learnability.

However it defeats the point of FRP to devote computational resources only to where they are needed.

I found this assertion questionable :) A majority of FRP research used a continuous semantics, meaning that an unmoving mouse would still cause updates as quickly as possible. This is not true in only one published paper (Event-driven FRP) which happened to be influential on the design of Elm. At most, I'd say that having no way to do this "weakens the argument" for FRP, but I designed things such that AFRP and Elm can live happily together!

[Hank]

On Wednesday, February 6, 2013 5:32:04 AM UTC+11, Evan wrote:

Both of you are saying true things :) Arrowized FRP can be fully embedded in Elm, meaning adding switch or some variation is a matter of adding a few lines to this file. In other words, both approaches described here will work fine in Elm.

I would be very interested to see the switch implementation in the Automaton file and a modified MovingBox with toggle button based on said switch.
 

However it defeats the point of FRP to devote computational resources only to where they are needed.

I found this assertion questionable :) A majority of FRP research used a continuous semantics, meaning that an unmoving mouse would still cause updates as quickly as possible.

Not sure the semantics are saying something about updates ... updates are an implementation choice as far as I understand. However in any case in my example the mouse isn't "unmoving". It's moving very well, its signal is just not contributing to the output.

[gerold.m...@gmail.com]

I've been using Yampa in some small private game projects. Switching comes in handy for games when you create and destroy game objects. You don't know how many objects (enemies, bullets, particles) will be in the game upfront, so on every event you just switch into a new set of signals. Though I think you're perfectly fine without them but you have to know the amount of signal networks upfront (pooling) and just disable everyone you don't need.

As for the Arrows. I think they make perfect sense in FRP and if you're looking for a framework that produces correct code ("no time and space leaks"), Arrows are a better choice than Monads. It took me some time to grasp them however. Larger signal networks are also very hard to read without Arrow-notation, thus you would also need some sort of precompiler for Elm.

[Evan Czaplicki]

I think I misrepresented my question in the original email. I understand arrows, why FRP cannot be a monad, why AFRP is useful, and why switching is useful. I designed FRP in Elm with all of these considerations in mind, ensuring that AFRP could be embedded and making switching possible. This is all in my thesis.

This question was meant to be about figuring out the best API for adding some sort of switch function to the Automaton library. I was mainly unsure how the switch APIs in Yampa and NetWire were intended to be used (i.e. what would the actual code look like?). Can you show me what it looks like to use these switches in Yampa? Do you know of any good example code?

--

[John Mayer (gmail)]

I don't really understand what switch is supposed to do.

Sent from my iPhone

[Evan Czaplicki]

It's just a more structured way to do things you can already do.

AFRP is a slightly more modular version of Signals. In Elm Signals are always running because they are inherently hooked up to an input. The idea of "on/off" does not really make sense for them. With AFRP, you do not provide an input, so it is just a pipe for values to run through. You can them give them inputs whenever you want.

So if you wanted to make a game with many bad-guys, you might create:

badGuy : Automaton Input BadGuyState

Then you can have a set of bad guys that grows and shrinks as necessary:

badGuys : [Automaton Input BadGuyState]

This is called a "dynamic collection" in the literature.

Now say you want an object to update differently if it is in water or on land:

landStep : Automaton Input Delta

waterStep : Automaton Input Delta

Now you can just switch those step functions in and out as necessary. And later if your character can fly, it is easy to add skyStep.

Again, all of this can be represented in Elm already. AFRP is just a more structured way to do it.

Does that clarify?

[Izzet Pembeci]

This question was meant to be about figuring out the best API for adding some sort of switch function to the Automaton library. I was mainly unsure how the switch APIs in Yampa and NetWire were intended to be used (i.e. what would the actual code look like?). Can you show me what it looks like to use these switches in Yampa? Do you know of any good example code?

Evan, what you need may lie in the earliest versions of FRP. The simplest API for switch may be the untilB function defined in this paper. The paper also provides some basic examples. Don't worry about the complex Yampa switch functions. First, you need to adapt the core switch functionality of untilB into your Automaton datatype. Since events (discrete signals) are not a seperate family in Elm, I am not sure how you can proceed. You may try to code these examples in Elm and then see if using Automaton would make sense (i.e. more concise/readable code). Once you get this basic switch done, you can add the more fancy switch functions based on your solution.

iZzeT

[Hank]

This here is interesting if it holds what the title promises: "Simple and Efficient Higher-Order Reactive Programming" It mentions shortcomings of AFRP and event-driven FRP in the introduction. Note that this is very recent research, a similar paper on the same subject has only been published last year. It is not clear to me whether it allows "dynamic switching" or whether all the signals participating in a switch have to be known from the start. The mathematical language is a mouthful, would need some time to get one's head wrapped around.

[Dobes Vandermeer]

Thanks, that is very interesting.  Here's my attempt to understand and boil it down:

It seems like they are trying avoid some of the leak issues found in other FRP while retaining the ability to create/destroy the data flow graph based on the fly.

They introduce the concept of a "future type" and you can have, for example, a cons cell where the tail is a "delayed value" and can't be accessed immediately.  So a stream of values becomes a list of values where the head is the "current" value and the tail is a delayed computation of the tail.  The consumer of the stream can observe the head value and keep a reference to the tail value for use the "next" time it gets another input for itself.  

The delayed computation closes over the state of a signal-generating function so that's how you keep your state - put a recursive invokation into a delayed expression and you now have a recursive stream.

Since the recursive invokation is delayed until a future time step, it allows an otherwise infinitely recursive function to run in lockstep with its consumer(s) rather than use up all the resources.

I believe their "unfold" function there roughly corresponds to the automaton in Elm - it takes a function that returns two values, one is the output to use and the other is the parameter to use in the next call.  That function can generate an infinite stream of arbitrary "stable" values.

Their "delayed value" mechanism does allow the data flow graph to vary dynamically; the streams are similar to a list and so you can just start pulling values from a different list when conditions change.  You can have a dynamically sized list of streams that produces a dynamically sized list of values.

The type system avoids memory leaks by blocking the use of past and future values; future values are kept as a lazy computation and past ones can be garbage collected.  You can still manually buffer up past or future values, as long as they are "stable", but the compiler won't do it for you behind the scenes, you have to create that leak explicitly.  This would reduce accidentally created memory leaks.

It seems like they were thinking of a strict implementation but I didn't find any mention of that in the text.

I'd guess the whole point of the research they are doing is to prevent the programmer from accidentally creating a memory leak in their FRP program by forcing the programmer to leak memory themselves, if that's what they really want.  Memory leaks must have been a big problem in the past.

If my memory serves, a big part of Elm's design is that signals have to be defined ahead of time in the application and must always have a value, and that this also relates to the memory leak issues of other FRP implementations.

Somehow I'm not connecting with the point of having switching done at the level of a stream or a signal; the Elm approach seems to be fine.  To manage a bunch of entities whose number varies over time I don't need a signal/automaton for each one, I can just have one automaton with a list of entities as part of its state.  The data flow graph would really only vary if program itself was changing structure a lot.

The concern with switching I feel from this thread is actually about performance rather than capabilities - what if we're "wasting time" reading inputs or updating automaton states that won't be used for the current screen.  I guess the way that I design my game - basically one giant automaton accepting all inputs - I can easily ignore inputs I'm not using and avoid code that isn't relevant to the current state.  The cost of reading unused inputs seems small compared to everything else that is going on.

[Hank]

Thanks for translating the article into somewhat more understandable terms. I will yet have to put some thinking into it. Did you understand what they mean by "quasi-imperative" (this term appears in the second paper linked to which is a variation of the first). I flinch when I see "imperative" because of all the reasons mentioned in the introduction of the same paper -- it makes reasoning about the system a lot harder. I wonder whether their quasi-imperative approach doesn't negate the advantages of the otherwise pure functional approach.

W.r.t. to the "point of having switching done at the level of a stream or a signal", you are right that it's "about performance rather than capabilities". See my example earlier in this thread (TCP protocol implementation) for an example where the simple approach of reading inputs that won't be used won't scale. A TCP implementation written this way would not just be slow, it would be unfeasible.

[Dobes Vandermeer]

Hi Hank,

I don't remember seeing the term quasi-imperative but I didn't read any further referenced papers and the language they described in that paper appeared to be a functional language.  It does require an imperative runtime system to support it, though.

I think that the TCP example could be done as a list (or hash) of remote IP/port combinations and their state rather than as a signal for each inbound connection.  Then the system has a single signal for all inbound packets and routes them to the appropriate piece of state.  The input signal of packets doesn't have to split the packets into separate signals, it can just dispatch each packet to an appropriate handler.  Since the original signal is just one signal that accepts all packets, it's probably pretty quick .. I think? 

[Hank]

The term "quasi-imperative" is in the second paper directly mentioned by me in above post (http://www.mpi-sws.org/~neelk/popl074-krishnaswami.pdf), not in any referenced paper.

Your solution is still computationally very inefficient, e.g. this data structure that includes connection state would have to be updated any time any of the connections change state, so that includes lookups and modifying a large structure (or rather computing a new large structure from an old one in the functional paradigm). Connection-specific signals don't have that. It gets worse further downstream if you have connection specific functionality -- i.e. the next layer in the protocol which can be HTTP for one and FTP for another connection. Here again the logical higher-order solution is to create new signals with domain specific operator pipelines.

[Hank]

Btw, this whole concept of "future types", recursive generating functions etc. is exactly how lazy sequences work in Clojure. The "future type" is called LazySeq and in a stream generating function like iterate (source), f is an example for a recursive invocation in a delayed expression. If that's what they mean by quasi-imperative, I don't have a problem with that.

Not clear to me yet how that solves the original problem as they depict in the introduction of both their papers. If you hold onto the head of the stream you have yourself a memory ("space") leak, if you don't, how do you start consuming the stream in the middle of something?

On Tuesday, February 19, 2013 6:42:41 AM UTC+11, Dobes Vandermeer wrote:

[John Mayer (gmail)]

Lookups and state updates happen no matter what. Think of a standard home router - single processor and a bit of memory. I'm willing to bet those use a global hash of sockets to connection states. I'd argue that there are actually very few efficiency gains to your approach.

I still think that the benefits of CFRP for language implementors outweigh the limitations placed on programmers. Adopting something else (another FRP pattern) would literally be a full rewrite of the runtime. Not that's that's a bad thing: as I understand Fay is looking for a good FRP library.

Sent from my iPhone

[Dobes Vandermeer]

Hi Hank,

At least in the "future types" approach the type checker doesn't allow you to hold onto the head of the stream without copying the values out of it into a new array.  So you can still create a space leak yourself, but it makes it a bit more difficult.  I didn't read the other papers so I don't know what their approach to the problem is.

For the TCP thing, you are going to need some kind of lookup / update mechanism no matter what, using a signal per connection isn't going to change that, it just changes how it is done.  If you use an appropriate data structure it's not too inefficient to update just the parts of it that are affected by an event and leave the rest alone.  I think this is what John Mayer was saying, too.

Cheers,

Dobes