Loop feature discussion

[Jeff Smits]

Let's see if I can summarize the two previous threads about loops in Elm, this time without asking the reader to have read Evans thesis (though you should, it is a good read). I think this post is still going be easier to follow if you read the thesis though... I'm starting this thread not as a feature request, but more as a discussion, because there are some issues to be resolved before this can be implemented

Summary
Previous threads
The previous threads are:

my feature request (lengthy discussion, and the feature turned out to lack the capabilities I was looking for); 

evans records suggestion, which summarises most of the discussion in my feature request. For even earlier discussions look at the links in my feature request post under background material. 

Why
So why even want signal loops? Because not everything can be expressed without them. Here's an example of something youcan't express in Elm right now:
Say you create a game with some animations, which pauses itself. Then you can't use fpsWhen because you'll get a circular dependency. 

Dangers

The problem with defining signal loops, in Elm as well as in reality, is that the behaviour might get out of control. Take, for example, a sound feedback loop: when you point a microphone at its speaker, you get this annoying, high pitch. This is not the behaviour you'd want. But a controlled loop can be really useful. With the sound example, you can kill that annoying sound by applying a filter to the mic signal which takes out the really high frequencies (not sure it's really that easy in reality but it makes good example). In Elm a similar thing is used to provide a safe loop. The kind of loop I'm talking about is foldp, and I think having that function may well be the reason not everyone has missed loop functionality before.

Foldp, a very constrained loop

You can consider foldp f b s to be a lift2 f s over the output signal which is sampled on s. So the output of foldp, is its own input again but cannot by itself trigger another update. This notion is rather important, but when I wrote my feature request I hadn't realised it yet. I thought a sampleOn functionality like foldp at the definition of the loop would be enough.

The main idea

Envisioned capabilities

So my feature request focussed on a few things. 

1. I want the circular dependent signal in the pauseable game example to work. 
   
2. I want (and still this an important one) to not have to pack/unpack signals when I need another signal inside the loop or another output signal based on some part of the loop.
   It becomes a chore to have to change the datastructure you're using for the loop signal, and changing the functions using that loop signal, just handing it over in one, ignoring it in the other. 

I wish I had a specific code example but I don't have one right now :( Maybe these diagrams can help illustrate the idea: 

(open in a separate window to enlarge, they're svgs :) )

legend: 

hexagon = signal source

arrow = signal

trapezoid = lifted function; but I use it for signal functions in the right drawings (sorry for that mess)

circle = split from a circular signal

Behavioural issues
An update to a signal that is part of a loop is propagated but does not cause that same signal to update again on its own. That's the behaviour a standard loop should have I think... It's what I'm after for the game example anyway, and I thought about that loop without thinking hard, more relying on intuition. Loop behaviour may be confusing for a newbies, so using naive intuition as a possible definition for the behaviour seems like a start...

There are some problems hidden in the details of the behaviour of the envisioned loop. Imagine a loop like this:

First, do we (for example) specify the starting value for o1 and then calculate the values of o2 and o3 from the functions and the signal source defaults? Do we recalculate o1 from this too and then stop?
The next problem: say we get the situation that i1 changes to the value 2, and the others stay the same. o1 obviously changes to what o3 was with 2 prepended to it. But now what do we do with o2 and o3? Do they just get an extra 2 and 3 prepended? And if they don't change, how would you implement that in general?
Then the final problem: what if two signals change at the same time? Which change goes first? Or does it not make sense to do this deterministic? I personally prefer it... But it's hard, especially when you consider a runtime system in which every f is a separate thread and the signals are actual queues with messages. 

My brain answered me these questions with a headache, so I hope I'm not giving you one too... 
I did think in the direction of not considering all parts of the equal. You can't write it that way in code anyway. So instead look at the circular signal as an actual signal, look at it as a linear thing with a special loop-back part:

Does this depiction inspire you to a good idea of how this should behave? I hope so, because whatever I thought was handy about looking at it like this just slipped my mind :( 

So, that's the end of my post. Please consider replying with what you think of:

1. The whole idea of a signal loop as a feature in Elm. 
2. The capabilities I came up with. 
3. The behavioural problems. 

[Jeff Smits]

So, it's been a rather busy week on the mailing list. But nobody has responded here... So what's up? Is this subject not interesting? Are the questions I ask just hard to answer? 

I put quite some time and effort into this, so I would appreciate a warning if this is never going to be used.

Anyway, I thought a little more about the behavioural problems I mentioned in my previous post. I explained it to a friend and in explaining the situation I figured out that an arbitrary loop may be too generic. The third problem with the two changes at the same time are a problem which only exists for arbitrary loops. If arbitrary loops are not a good idea, the packing/unpacking problems may be a different problem all together. 

I took another look at foldp as a loop, and the loop I would like for the game example and I noticed something which might be important. Before I show the diagrams, let me give you a proper legend first:

(source: "Elm: Concurrent FRP for Functional GUIs")

(the filter/sample primitives that are in the language today)

Now the way I drew foldp as a loop in a previous thread was incorrect. Because the behaviour of foldp is that only a change in the input changes the loop/output, not a change from the loop. So using sampleOn to depict this behaviour:

As you can see, the loopback signal b cannot cause a change in the value of the signal to f(a change in the value of s changes the values of the signals to f). In the game example I would like to work, there is a similar situation:

It's a little more complicated with the different loops to different places, but the gameState signal can be seen as a foldp loopback signal and ignored for now. The playing signal is what's interesting. It connected to a filter in such a way that it's not responsible for the actual changes that loop back (just stops some of them sometimes). Just like a loopback in foldp is not responsible for changes of the loopback signal. 

Does this make sense? I feel like I'm closing in on a solution :) As long as the loopback signal doesn't directly instigate a change it's ok. So loopback signals can only be used on filter/sample functions. Would it be a good idea to add a supertype to signal which also has a subtype LoopbackSignal? I'm particularly using loopback, not loop, because I mean the arrows that go up in stead of down and end on a filter/sample block in my diagrams, and not every arrow that is part of a cycle. 

[John Mayer (gmail)]

I think this is an important topic. Some thoughts:

I think you're right when you say that filtered loops and sampled loops are the two main, safe use cases. It has been demonstrated that both can be implemented using a more primitive loop construct. I suggest that we make concrete the semantics of the general, unsafe loop that will inevitably be represented in the underlying runtime, and then independently discuss the merits of how much should be exposed to the programmers.

Would it be possible to create a flag for the compiler that quits early and prints the entire signal graph? (even in XML or something, doesn't need to be pretty) Where is the Signal graph represented in the compiler, and how is it checked? How does the runtime actually propagate signals, and whats the difference between "resolving a signal DAG atomically" and "handling an event external to the local DAG"?

Sent from my iPhone

On May 18, 2013, at 10:00 AM, Jeff Smits <jeff....@gmail.com> wrote:

So, it's been a rather busy week on the mailing list. But nobody has responded here... So what's up? Is this subject not interesting? Are the questions I ask just hard to answer? 

I put quite some time and effort into this, so I would appreciate a warning if this is never going to be used.

Anyway, I thought a little more about the behavioural problems I mentioned in my previous post. I explained it to a friend and in explaining the situation I figured out that an arbitrary loop may be too generic. The third problem with the two changes at the same time are a problem which only exists for arbitrary loops. If arbitrary loops are not a good idea, the packing/unpacking problems may be a different problem all together. 

I took another look at foldp as a loop, and the loop I would like for the game example and I noticed something which might be important. Before I show the diagrams, let me give you a proper legend first:

<elm_primitives.png>(source: "Elm: Concurrent FRP for Functional GUIs")

<filter_sample_primitives.svg>(the filter/sample primitives that are in the language today)

Now the way I drew foldp as a loop in a previous thread was incorrect. Because the behaviour of foldp is that only a change in the input changes the loop/output, not a change from the loop. So using sampleOn to depict this behaviour:

<elm_fold_in-correct.svg>

As you can see, the loopback signal b cannot cause a change in the value of the signal to f(a change in the value of s changes the values of the signals to f). In the game example I would like to work, there is a similar situation:

<game_loop.svg>

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

[John Mayer]

This was my previous attempt to implement the unsafe loop. I had hoped to get some comments so I could learn about Signals in the runtime. I argue that all of your examples could be implemented in pure Elm on top of this feature.

https://gist.github.com/johnpmayer/5464492

--
/*
 * John P Mayer, Jr
 * BS, Computer and Information Science, 2011
 * MSE, Embedded Systems, 2012
 * School of Engineering and Applied Science
 * The University of Pennsylvania
 * Philadelphia, PA
 */

[Evan Czaplicki]

I also agree that it is important, but I didn't have any good new ideas.

Jeff, I like the visualization of the signal filter primitives :)

Hmm, in thinking about implementation I thought of a potential problem. The loop would be easy to implement, but in the simplest unsafe case, it'd need to be implemented just like the async feature. The loop would go to the GED and then get sent back into an input. This allows synchronization that permits concurrency and parallelization.

That means that event could occur between the triggering event and the looped event, perhaps changing some foldp and making the looped event irrelevant or wrong. I think this would ba a problem for all proposals so far.

Printing out the signal graph would not be too hard. It could be done with some JS in Init.js that crawls over the "inputs" array and then crawls through their "kids" arrays. You could build up a list of directed edges easily.

On Saturday, May 18, 2013, John Mayer wrote:

This was my previous attempt to implement the unsafe loop. I had hoped to get some comments so I could learn about Signals in the runtime. I argue that all of your examples could be implemented in pure Elm on top of this feature.

https://gist.github.com/johnpmayer/5464492

On Sat, May 18, 2013 at 1:45 PM, John Mayer (gmail) <thgy...@gmail.com> wrote:

I think this is an important topic. Some thoughts:

I think you're right when you say that filtered loops and sampled loops are the two main, safe use cases. It has been demonstrated that both can be implemented using a more primitive loop construct. I suggest that we make concrete the semantics of the general, unsafe loop that will inevitably be represented in the underlying runtime, and then independently discuss the merits of how much should be exposed to the programmers.

Would it be possible to create a flag for the compiler that quits early and prints the entire signal graph? (even in XML or something, doesn't need to be pretty) Where is the Signal graph represented in the compiler, and how is it checked? How does the runtime actually propagate signals, and whats the difference between "resolving a signal DAG atomically" and "handling an event external to the local DAG"?

Sent from my iPhone

On May 18, 2013, at 10:00 AM, Jeff Smits <jeff....@gmail.com> wrote:

So, it's been a rather busy week on the mailing list. But nobody has responded here... So what's up? Is this subject not interesting? Are the questions I ask just hard to answer? 

I put quite some time and effort into this, so I would appreciate a warning if this is never going to be used.

Anyway, I thought a little more about the behavioural problems I mentioned in my previous post. I explained it to a friend and in explaining the situation I figured out that an arbitrary loop may be too generic. The third problem with the two changes at the same time are a problem which only exists for arbitrary loops. If arbitrary loops are not a good idea, the packing/unpacking problems may be a different problem all together. 

I took another look at foldp as a loop, and the loop I would like for the game example and I noticed something which might be important. Before I show the diagrams, let me give you a proper legend first:

<elm_primitives.png>(source: "Elm: Concurrent FRP for Functional GUIs")

<filter_sample_primitives.svg>(the filter/sample primitives that are in the language today)

Now the way I drew foldp as a loop in a previous thread was incorrect. Because the behaviour of foldp is that only a change in the input changes the loop/output, not a change from the loop. So using sampleOn to depict this behaviour:

<elm_fold_in-correct.svg>

As you can see, the loopback signal b cannot cause a change in the value of the signal to f(a change in the value of s changes the values of the signals to f). In the game example I would like to work, there is a similar situation:

<game_loop.svg>

It's a little more complicated with the different loops to different places, but the gameState signal can be seen as a foldp loopback signal and ignored for now. The playing signal is what's interesting. It connected to a filter in such a way that it's not responsib

/*

 * John P Mayer, Jr
 * BS, Computer and Information Science, 2011
 * MSE, Embedded Systems, 2012
 * School of Engineering and Applied Science
 * The University of Pennsylvania
 * Philadelphia, PA
 */

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

--
Sent from Gmail Mobile

[Evan Czaplicki]

Also, there is no runtime checks of the signal graph because the language can only describe safe graphs.

I think we should rephrase this discussion as "signal sources and sinks". I think that's a better mental model for what we are trying to do and the loop diagrams can be quite confusing.

[John Mayer]

What about doing something like this:

setTimeout(0, function() { dispatch the loopback })

This let's the current updates "settle", and the new value comes back in the "next round".

[Jeff Smits]

@John:

I suggest that we make concrete the semantics of the general, unsafe loop that will inevitably be represented in the underlying runtime, and then independently discuss the merits of how much should be exposed to the programmers.

 

This was my previous attempt to implement the unsafe loop. I had hoped to get some comments so I could learn about Signals in the runtime. I argue that all of your examples could be implemented in pure Elm on top of this feature.  

https://gist.github.com/johnpmayer/5464492

 

I believe building the unsafe loop into the language is not a good idea. If the programmer really wants it, it is already available through the FFI. 

I think a general safe loop -- i.e. a loop update doesn't cause another loop update -- is unattainable. I don't see how you can define deterministic semantics for it. 

Speaking of the FFI, I do like how you just need to import at the start and export at the end to connect a signal as a loop. Perhaps that can be kept as the usage in the eventual loop feature. 

I think you're right when you say that filtered loops and sampled loops are the two main, safe use cases. 

I don't see what other safe use case there are for loops actually. I would suggest that we don't try to generalise beyond these cases and just implement them in some safe combinable way. 

@Evan:

Jeff, I like the visualization of the signal filter primitives :)

Thanks ^_^

Hmm, in thinking about implementation I thought of a potential problem. The loop would be easy to implement, but in the simplest unsafe case, it'd need to be implemented just like the async feature. The loop would go to the GED and then get sent back into an input. This allows synchronization that permits concurrency and parallelization.

Well, one of the unsafe situations would be that you don't implement the unsafe loop with async (you would have to put an event on the queue of a loopback signal before the start of the execution), which would result in a loop that hangs indefinitely. If you do implement it using async, you can still get the whole 'loop update causes another loop update' situation though.

That means that event could occur between the triggering event and the looped event, perhaps changing some foldp and making the looped event irrelevant or wrong. I think this would ba a problem for all proposals so far.

Did you mean to write "That means that an event could occur..."? I wouldn't implement foldp with a loop using async but using the sampleOn. 

Printing out the signal graph would not be too hard. It could be done with some JS in Init.js that crawls over the "inputs" array and then crawls through their "kids" arrays. You could build up a list of directed edges easily.

Easy as that may be (https://gist.github.com/Apanatshka/5608341) there isn't a lot of info in that graph to link it to the source code.

I think we should rephrase this discussion as "signal sources and sinks". I think that's a better mental model for what we are trying to do and the loop diagrams can be quite confusing.

Can you explain what you mean by "signal source and sinks"? I don't really get what you mean by that.. Should I think them as the export/import of the FFI? 

I'm comfortable with the mental model of a loop, but making it less confusing for others is a good idea. (I usually look at the loopback signal of foldp as a pull-based signal instead of a normal push-based one. )

To unsubscribe from this group and stop receiving emails from it, send an email to elm-discuss+unsubscribe@googlegroups.com.

For more options, visit https://groups.google.com/groups/opt_out.
 
 

[Evan Czaplicki]

John, I think an event could still occur in the time between trigger and retrigger, even with a timeout of zero.

Jeff, I think we are in agreement about the need to go through the GED? I agree that without it, you would hang, waiting for a change or no change message.

With signal sources and sinks, yes, it is more like the FFI model where you have a source of signals (import) and a sink (export). These are terms from the max-flow graph algorithms. Seems like it's not super intuitive to call it this :)

I have always drawn foldp as a simple node with one input and one output. It holds some state inside. I find this more intuitive because an update goes through every signal node exactly once, and I think drawing a loop (or even thinking of it that way) makes that property less clear. The loop-less visualization also matches the implementation.

So I'd draw "loops" like this:

A   *    C

 \ /    /

  D    E

   \  /

    F

   / \

main  *

Where the * input comes from the * output.

This better captures the fact that the message has to go through the GED and it makes the structure of the program much more apparent to me. I.e. a "loop" is just another kind of input, it just happens that those input events are produced by the program itself. The FFI method matches this way of thinking.

Stepping back, I think implementing the two or three known safe loops is a reasonable way to do this. The opportunity for events occurring before the loop event is triggered needs to be considered more carefully though. I feel like this could have surprising effects.

[John Mayer (gmail)]

Is it not the case that the GED will wait for a signal subgraph to "settle"?

Sent from my iPhone

[Evan Czaplicki]

It is not the case in an ideal scenario. The signal graph will allow many updates to flow through at the same time, ordering is maintained by the change and no-change messages. In JS, it does wait for things to settle, but that is because JS does not have good concurrency support.

[Jeff Smits]

Evan, actually we don't agree there, I think you can do without the GED in the special cases I think we should implement. As you said, using the GED will be problematic in some cases, which means you can't recreate the foldp behaviour you have now. 

Do you have time to chat on IRC? 

[John Mayer (gmail)]

Well yes that was my hunch, that we do rely on the fact that JavaScript is single threaded and cooperative (non preemptive), right? Nothing ever can "interrupt" the flow of updates in a connected signal graph. That's sort of the point. It's not a hindrance, it's a feature! And it makes everything easy.

Later on, if we really want parallel performance, it would be good to try and put each signal graph in a web worker, accessible only via the sources and sinks. That way, we have a very clear actor-model implementation, and the GED is the "main" loop.

Sent from my iPhone

[Jeff Smits]

So Evan and I talked on IRC and found that the "loopback part" of a cycle needs a waiting event if you don't want to involve the GED. Not using the GED will make the loop feature general enough to make your own implementation of foldp. 

We were talking about how a loop implementation of foldp might not even require a sampleOn at the start but I'm not so sure about that anymore. Because a loopback could have a Change event which can instigate another Change even without a Change event from the outside signal. And always making an event on the loopback a NoChange wouldn't work with other situations where the loopback is put into a filter. 

I think a loopback can be safely allowed in situations where it is connected to the non-starred(*) input in the second image of my second post on this thread. (Sorry for the clumsy referral, but I can't seem to add an SVG image anymore..?)

I think that would be the most natural point to have one anyway. Does anyone disagree? Or maybe know a more general and still handy and safe way to allow loopbacks?

Otherwise I'd really like to start talking about how to syntactically allow these kinds of loops

[John Mayer (gmail)]

I still think the easiest implementation is to use the GED as follows. All other versions can be built on top. It precludes cycles in the "current round". 

It is up to the implementation of the wrappers to ensure loops don't cascade across multiple rounds. Those safe wrappers could be exposed.

I argue that putting the "code to be looped" in the signal function both forces the programmer to be deliberate and makes implementation easier.

loop : (Signal a -> Signal a) -> a -> Signal a

loop transform initial =

Native JS Psuedocode: 

Create a hidden Input signal "loopback"

Apply "transform" to "loopback" to get a new signal, "output"

Add an additional listener to "output" which triggers "loopback" via setTimeout and notify. This would happen during the next "round" 

Return "output" to the programmer

Sent from my iPhone

<irc#elm.log>

[Rick Richardson]

I have been into Elm for three days or so, so I'm just getting the feel of things, but this seems like a great way to approach the problem. Like signals themselves, a filtered Loop mechanism would encapsulate theoretically impure, otherwise unmanageable things. The result of the Loop is a signal, but how that signal is generated would be akin to how sausage is generated, the system would rather not know about it. 

Functionality could still be composable, but not as loops/signals, but merely as functions that would have to be applied into the loop. 

Given that one shouldn't put too much functionality in these loops if possible, I wouldn't recommend it, but one could also treat this as an applicative functor to make composition of functions within the loop possible.

[John Mayer (gmail)]

Here's what I've come up with. Please compare its implementation to that of delay in Native.Signal, which uses the GED in a very similar fashion. 

function loop(transform, initial) {

  var loopback = Signal.constant(initial);

  var output = transform(loopback);

  output.kids.push({

    recv : function(_timestep, changed, _parentID) {

      if (changed) {

        window.setTimeout(function(){

elm.notify(loopback.id, output.value);

}, 0)

      }

      return changed;

    }

  });

  return output;

}

Sent from my iPhone

[Evan Czaplicki]

Implementing this feature is not the hard part. I am not satisfied that we have thoroughly explored the possibilities for doing this.

I think it might be possible to annotate updates to make sure that they only cause N loops. This would be theoretically nicer, but I don't know if this will be nicer to use and to think about. In any case, I think we should figure that out before implementing stuff.

I think this is an important feature, but because of the roadmap I want, I cannot properly do this theoretical work right now. And I think the theory needs to be explored more fully before an approach is chosen.

[John Mayer]

Not sure what you mean by theory; loops are going to be a runtime hack no matter what. But here's an intuition pump that might help the discussion. We can go ~more~ general as follows. Change the Input node constructors to actually return a tuple of the Signal and a typed handle. Then, introduce a function

linkNotify : Signal a -> Handle a -> ()

This would construct a little pseudo-node that, on receiving a change event from the signal, would add to the JavaScript queue a notification of a change event to the input node referenced by the handle. Great! We get all of the same functionality, maybe a bit more. We can build many of the looping proposals using it. It's as primitive as we can get for linking two arbitrary nodes in the DAG. However,

We should enforce that these links go "backwards" up the Signal graph, perhaps by tagging signal nodes with the Naturals, obeying the DAG relation. We should enforce that only input nodes expose their handles, because they're the only ones who can receive notify events in an elm runtime module anyway. And we should probably enforce that these links don't cause an exponential growth, I.E. an Input change causing two linked notifications coming back to it. And oh crap, we have to now support a new type, "Handle".

So the trick to my implementation is that it's really a safe "linkNotify". The Input node and the psuedo-node are hidden from the programmer, it's guranteed to travel backwards, it's one-to-one, and there are no changes to the type system.

And since I couldn't resist:

If you want to magically link a source and a sink, you don't have to think! Just provide a signal function, and with a wink, the runtime wizard will wire it up safely before you blink. I'm tickled pink!

[Evan Czaplicki]

Haha, nice :P I think this is the core idea of all of our proposals so far, so it is nice to have it stated simply. Each of our ideas are just ways of making this a bit safer. I think it may be possible to be more clever about the Change/NoChange signals though.

Instead of just having:

data Update a = Change a | NoChange a

We could maybe have:

data Update a = Change Int a | NoChange a

The Int would carry the number of loops permitted. Say we only allow one loop. A click event would start out as (Change 1 ()) and if it causes a looped event with value 42, the new event is (Change 0 42). The zero tells us not to trigger any more looped events.

This gives us a way to reliably limit the number of loops that occur. Then we don't have to worry about "safe" loops because all loops are bounded. I don't know if this would end up being nice to use, but I think we need to explore this kind of approach.

[Evan Czaplicki]

The loop constructs could even give some access to the loop limit.

data Update a = Change (Maybe Int) a | NoChange a

A click would be (Change Nothing ()).

The resulting event would be (Change (Just n) 42) where n is set by whatever looping construct is exposed.

We also should look at Real-Time FRP which was theoretically similar to Elm and had recursive signals.

[John Mayer]

Yes I think Maybe Int is perfect for this. 

Note that, for the JavaScript implementation, assuming resolving an entire signal graph is an atomic op, the "decay factor" of all change events are constant throughout the entire "round". So it could actually be a property of the round stored in the elm object, and simply updated there each time "notify" is called.

[John Mayer]

rcf https://github.com/johnpmayer/Elm/compare/topic;loop_n

[Jeff Smits]

I think it's not a good idea to concentrate on the JS implementation this feature. When we work out the specifics in terms of the theoretical model of a concurrent system with message queues of Change/NoChange messages, the implementation in JS should be straightforward. 

I think it might be possible to annotate updates to make sure that they only cause N loops. This would be theoretically nicer, but I don't know if this will be nicer to use and to think about. In any case, I think we should figure that out before implementing stuff.

 

I thought of loops where the message goes round a limited amount, even before I made my feature request post. But that only makes sense when you use an asynchronous loop (which I'm still very much against because you can create one using a synchronous loop and an async). Even then I don't see what you would need this for and why you can't use a pure function to repeat whatever computation you want to do multiple times multiple times. That is, unless you really want the loop to output NoChange for N-1 rounds and use the input message of N rounds to compute the result. 

I think this is an important feature, but because of the roadmap I want, I cannot properly do this theoretical work right now. And I think the theory needs to be explored more fully before an approach is chosen.

 

We also should look at Real-Time FRP which was theoretically similar to Elm and had recursive signals. 

I'd love to do the theoretical exploration! Are there any other pointers besides Real-Time FRP recursive signals you can give me? And what exactly do you want explored? Shall I write a document containing everything I've found on FRP concepts related to this loop discussion with references? Should I also list all possible features (e.g. the N rounds) I can think of? Can you think of anything else you'd like to know?

[John Mayer (gmail)]

Async doesn't exist yet in the runtime. "link" is a primitive (i argue the most primitive) that makes async possible in JS. (To me, then, loop is just a special case of an async "eating its own tail")

I still don't understand how a synchronous loop would work, nor the motivation for wanting to avoid the GED. You mention the ability to reimplement foldp, but not overall why that is important, necessary, or desirable. I feel like I've missed that piece of your argument. Loop being async seems very natural to me.

At a more general level, I see each synchronous sub-graph as an actor, which is currently concurrent, but can also be made parallel using web workers. erlang and golang will be good examples to research.

Sent from my iPhone

[Jeff Smits]

I've tried writing this answer two times before, but couldn't find the words to easily describe the semantics of the synchronous loopback. So in stead I've made some diagrams of an example use:

0:1:2:

3:4:5:

The scenario is consists of a few steps in which input source i1 changes to value 3, and immediately after to value 2. The images show the states between these steps:

0: Before the start of the program a Change message is added to the queue of the loopback (with the loopbacks initial value). This is key to make the synchronous loop work. 

1: Input source i1 changes to value 3 and sends Change messages to the queues. 

2: The sampleOn can compute it's outgoing message because the ingoing are both there. Meanwhile input source i1 changes to value 2 and sends more change messages.

3: The lifted (+) can be executed for the first time. Note that the new Change 2 message from i1 is still waiting for the result of this (+). This is the synchronous behaviour of the loop in action. 

4: Because the loopback had a message ready again, the sampleOn could be executed. 

5: The last (+) is executed. This is the last state. It looks a lot like state 0, but with a different message ready at the loopback and some messages available at the output signal (the one pointing downwards). 

Does that make the semantics of the synchronous loopback clear?

The asynchronous loopback is definitely something very different from anything you might do with foldp, because that kind of a loop might happily work with incoming messages and an old version of the state. And when the new state finally arrives through the asynchronous loopback, it might get ignored. Example like the last one:

0:1:2:3:4:

5:6:7:8:

I know this is not the kind of thing you would write with an asynchronous loopback, but these kinds of situations may arise from it's use and I find them very unintuitive. I think it's a dangerous pitfall. 

My most important argument for a synchronous loop is:

Signals are in a synchronisation system. You can break from that system with `async`, but the standard behaviour is synchronous. If you implement a loopback fitting in the synchronisation system, it will fit better with the rest of the language. And using async, you can easily get the ansynchronous loop if you want. 

Reimplementing foldp is a test to check the capabilities of the feature. It also a use case for the feature. (Apart from that I secretly hope not to need foldp anymore once this feature is added. It may still be desirable in some situations, but I get annoyed over having to rewrite most of my code when I expand the functionality and it needs a form of state. )

--
You received this message because you are subscribed to a topic in the Google Groups "Elm Discuss" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/elm-discuss/mDhgg1cbX4M/unsubscribe?hl=en.
To unsubscribe from this group and all its topics, send an email to elm-discuss...@googlegroups.com.

[John Mayer (gmail)]

Ah, ok!

So the synchronous loop makes the change to the loop back always available at the beginning of a round, but it never triggers a new round itself.

Yes, I do see how that simplifies it. And yes there is significant benefit to keeping the sub-graph self contained. You're right, there is a significant risk for re-ordering to get lost with asynchronous stuff. I'll try to pivot my work of link/notify towards an implementation of async itself.

In the mean time I will vote in favor for synchronous loop. I will, however, continue to argue for the higher order type signature that takes a signal function and an initial value as an argument.

John 

Sent from my iPhone

On Jun 6, 2013, at 2:58 PM, Jeff Smits <jeff....@gmail.com> wrote:

I've tried writing this answer two times before, but couldn't find the words to easily describe the semantics of the synchronous loopback. So in stead I've made some diagrams of an example use:

0:<synchronous_loop1.svg>1:<synchronous_loop2.svg>2:<synchronous_loop3.svg>

3:<synchronous_loop4.svg>4:<synchronous_loop5.svg>5:<synchronous_loop6.svg>

The scenario is consists of a few steps in which input source i1 changes to value 3, and immediately after to value 2. The images show the states between these steps:

0: Before the start of the program a Change message is added to the queue of the loopback (with the loopbacks initial value). This is key to make the synchronous loop work. 

1: Input source i1 changes to value 3 and sends Change messages to the queues. 

2: The sampleOn can compute it's outgoing message because the ingoing are both there. Meanwhile input source i1 changes to value 2 and sends more change messages.

3: The lifted (+) can be executed for the first time. Note that the new Change 2 message from i1 is still waiting for the result of this (+). This is the synchronous behaviour of the loop in action. 

4: Because the loopback had a message ready again, the sampleOn could be executed. 

5: The last (+) is executed. This is the last state. It looks a lot like state 0, but with a different message ready at the loopback and some messages available at the output signal (the one pointing downwards). 

Does that make the semantics of the synchronous loopback clear?

The asynchronous loopback is definitely something very different from anything you might do with foldp, because that kind of a loop might happily work with incoming messages and an old version of the state. And when the new state finally arrives through the asynchronous loopback, it might get ignored. Example like the last one:

0:<asynchronous_loop1.svg>1:<asynchronous_loop2.svg>2:<asynchronous_loop3.svg>3:<asynchronous_loop4.svg>4:<asynchronous_loop5.svg>

5:<asynchronous_loop6.svg>6:<asynchronous_loop7.svg>7:<asynchronous_loop8.svg>8:<asynchronous_loop9.svg>

[Evan Czaplicki]

I'd also look into:

• Event-Driven FRP. E-FRP is quite similar to Elm. Does not have loops, but is an incremental improvement of Real-Time FRP and they even propose adding recursive signals.
• Loops in Arrowized FRP. This feature is really confusing, even after you understand what is going on with arrows. The point is that exists and allows loops. Furthermore, AFRP can be embedded in Elm, and it may be possible to convert between (Signal a -> Signal b) and (Automaton a b).
• Concurrent ML which is a really nice way to do concurrency and gives insight into what is really going on in the runtime system conceptually. One solution is to permit this kind of concurrency and make a well-defined way for it to interact with signals. This is the most powerful solution, but it does not give any nice guarantees.
  

I'd be most curious about RT-FRP, E-FRP and loops in Arrowized FRP. This was something I did not focus on while doing my thesis, so I wonder if there are things I just missed.

Is it fair to say that "synchronous" loops are for different use cases? In any case, I hesitate to call them "synchronous". I am not sure what the right word is, but that seems to imply that the looped value will be a new event that directly follows the triggering event (which I don't think is possible). Maybe productive and non-productive loops? Indicating whether they create a new event or not?

[John Mayer (gmail)]

Synchronous in the sense that it all happens in one round. Rounds are delimited by the GED. 

Sent from my iPhone

[Evan Czaplicki]

The GED never has to wait for an event to propagate through the signal graph. This is the feature that allows concurrency and asynchrony. Many updates can be in progress at the same time. The word synchronous makes it sound like the GED is actually waiting to see the results of an update before starting the next round.

When compared to what synchronization means in the Elm runtime, I think this use of the word is either a different use or misuse. We should use a different term in this case.

Creating a new event that goes through the GED is inherently asynchronous. As I understand, the key distinction is in whether the loop sends events to the GED or not. The production vs. not-production of events is the key distinguishing factor, not anything to do with synchrony or asynchrony which are handled separately.

[John Mayer]

> The GED never has to wait for an event to propagate through the signal graph. This is the feature that allows concurrency and asynchrony. Many updates can be in progress at the same time.

Can't let you get away with that one. The current runtime always waits for propagation, because JavaScript is single-threaded and non-preemptive. No more than one update can be in progress at the same time, in the strictest interpretation of "at the same time". However, we're still able to achieve concurrency.

Could you describe a runtime that actually behaves in this way? And perhaps more importantly, will it be possible in browsers anytime soon?

[Evan Czaplicki]

Tone? It's not like I am being tricky and "getting away" with things. I think loops are a research topic right now. During exploration, we should aim for a solution that is theoretically satisfying.

I'd re-emphasize that sentence "The current runtime always waits..."

Elm and the implementation of Elm are not necessarily the same, and I do not think the limitations of JS should guide the design of Elm. Furthermore, the whole industry recognizes the limitations of JS and is working as quickly as possible to find solutions (Dart, asm.js, native client, type script, etc.) Furtherfurthermore, JS is not the only platform that I'd ever want to target.

The description of such a runtime is in my thesis and in the PLDI paper (which should be required reading for this loop discussion). Both papers provide Concurrent ML code that implements a concurrent runtime. For testing, I also wrote a concurrent runtime in Haskell that implemented the core signal primitives from the papers.

[Evan Czaplicki]

I think the priority now should be doing a comprehensive literature review, not design, and definitely not implementation.

[John Mayer]

Fair enough, sorry for the call out.

I think my main frustrations is that these are all fairly easy to implement, and we can let them stand on their merit in real world code. However, the only way for them to get widely tried and tested is if they're accepted in the standard library. I'd much rather be announcing these as competing public libraries with Native code than arguing about them on the list.

John

[Juan Felipe Garcia Catalan]

I've only played a bit with Elm and read some literature here and there but here's my (imprecise and too intuitive) two cents about this issue:

Maybe a good place to find a model for loop control is Circuit simulation. CPUs seem to me the ultimate reactive systems, but most current FRP systems are only good for modeling the combinational parts of a CPU: I can come up with a decent ALU simulator in Elm but registers, counters or feedback loops (ie the whole sequential and control aspects) are poorly or not at all supported by the underlying DAG model.

Currently if I want to make a simple CPU emulator using Elm I have to stuff the whole state (registers, program counter, memory...) in  a big fat signal that I thread throug the DAG, and I find that a bit pointless. I'd find more natural to be able to use a more detailed description that is closer to the actual thing. 

So thinking about asynchronous sequential circuits as a model might help here. Or even looking at circuit simulation and verification DSLs like Lava on Haskell.

[Jeff Smits]

@Evan

Exposing Concurrent ML-like events would be a bad move IMHO. Now you have a nice high level concurrency system with Signals, where the programmer hardly has to worry about concurrency. Added CML-like events --- even when you define an interface with Signal --- would complicate the language and ruin the guarantees of a well-behaving system that you have now. 

I'll start reading about E-FRP and A-FRP. Should I look into RT-FRP too when I'm already looking at E-FRP?

I don't like the names productive and non-productive loops. Synchronous still makes the most sense to me. It is in sync with the "message waves" or steps or rounds of the GED. Since you don't find the name intuitive, maybe we should think the name over. But productive and non-productive are unintuitive to me. 

@John

I get your frustration. Try things out and seeing how it goes is an approach you can take. But I agree with Evan that a good literature review is a better investment of time. This feature we've been discussing might have been documented and improved upon. Or something related may bring new insights. 

[John Mayer]

Can we revisit the following version? It was dismissed very early on when we first started talking about loops because it didn't use "pure functions", but it looks fine to me. It seems to perfectly describe the pictures at the top of this thread (yes it can be chained).

(Signal a -> Signal b -> Signal b) -> b -> Signal a  -> Signal b

I just implemented it in the current runtime, and I'm almost positive is causes no problems in a "pipelined", or non-synchronous implementation.

John