Signal Loops / Generalised State: an API proposal

[Jeff Smits]

Hi all,

It's been a while since I've discussed the Signal Loops idea on the list. I'll try recap the idea for those who don't remember, or haven't seen the previous discussions or the video. I start out a little slow on the video but I think it's the best description I've given of this feature so far. However! It discusses the details of implementing the idea, which you don't need to know for this discussion.

Ok, I'm moving the recap to the end of this post because it's a wall of text. The point of this thread is to get feedback on the API proposal. So first see if you understand it the API proposal and tell me if you think it's a good idea. If you can't figure stuff out without a more info on the whole idea, scroll down to the recap or watch the video :)

API proposal

I'm doing this introduction by example :) I'm not good at making up examples so I stole one from another thread, a game loop pattern:
- Set Fixed update interval constant in milliseconds (based loosely on desired *minimal* framerate)

- Loop

  - Calculate Lag variable based on Fixed interval constant + time since last loop

  - Get input

  - Update (No delta. Update function knows of fixed size and always "moves" the game the same amount)

    - Lag = Lag minus Fixed

    - Run Update again if lag is too high, repeat *just the* Update function until lag cleared

  - Render (Ideally with offset (Lag divided by Fixed) to help visual issues)

divMod a b = (a `div` b, a `mod` b)

-- fixed timestep
fixed = second / 30

-- time since last render

timeDeltas : Signal Float

-- game logic

update : Input -> State -> State

-- rendering

render : State -> Element

-- input signal

inputs : Signal Input

repeat n f i = if n > 0 then repeat (n-1) f (f i) else i

Proposed API

signalUnzip : Signal (a,b) -> (Signal a, Signal b)
signalUnzip s = (fst <~ s, snd <~ s)

-- game loop

old lag = 0

(lag,noOfUpdates) = signalUnzip <| (\l td -> divMod (l + td) fixed) <~ old lag ~ timeDeltas

old state = startState

state = repeat <~ noOfUpdates ~ (lift2 update inputs) ~ old state

-- uncomplicated main function

main = render <~ state

The way you do it now with foldp

-- game loop
loop (time, input) (oldLag, state) =
  let (noOfUpdates,lag') = (oldLag + time) `divMod` fixed

  in (lag', repeat noOfUpdates (update input) state)

-- foldp

main = render <~ (snd <~ foldp loop (0, startState) inputs)

Explanation of the API

Ok, so the example is tiny, which is why the foldp implementation is smaller (and perhaps makes more sense here). But at least you can see that the different things you may want to keep track of can be split up now! And this can be done even when they depend on each others old value to calculate the new value :)

The basic idea is to add a single keyword to the language: old. I'm not very attached to the name, but I do quite like the way this thing works. Either way, feel free to suggest something better if you think of it.

`old memorableSignal = initialValue` defines a signal that track the normal signal `memorableSignal`, but lag behind by one. This is the way you introduce state.

It is an error to not define `memorableSignal` when you have defined the old version.

To use the old (remembered) value instead of the current one, use the expression `old memorableSignal`, which has the same type as `memorableSignal`.

Final note: You should be able to use this definition of `old memorableSignal = initialValue` in a let block. That way you can encapsulate it and do data abstraction or whatever the pattern was called.

Benefits

1. You can name your state at a top-level if you want, but there is an obvious connection between it and the normal signal.
   
2. You can also easily model state with complicated dependencies and throw in some filters if you like.
3. You can easily introduce some new state when you find out you need it, without refactoring. This is mostly because the state definition and use sites are decoupled.
   (In contrast a generalised foldp' : (Signal a -> Signal b -> Signal b) -> b -> Signal a -> Signal b still encapsulates the state)
   

Pitfalls

1. Forgetting to use the old keyword at usage site. But this most likely results in a compile-time error because of recursively defined signals.

END OF API PROPOSAL

------------------------------------------------------ <hr> <!-- :) --> </hr> ------------------------------------------------------

Recap of Generalised State
Signal Loops hints at the way this feature may be implemented so perhaps a better name would be generalised state. Right now we have foldp : (a -> b -> b) -> b -> Signal a -> Signal b to introduce "state" in the form of that b in the type. Though I expect you to be familiar with foldp, let me explicate it's behaviour:
foldp : (a -> b -> b) -> b -> Signal a -> Signal b
resultSig = foldp stepFunc initialVal inputSig
You give it a initialVal to begin with. That's the initial value of the result resultSig.
It remembers (state!) that last value of the result signal for you, so you can use it in step when inputSig gives you a new input value.
When inputSig gives you a new a and foldp supplies the old b, step can calculate the new b. Then that new b is sent on the outputSig, and foldp remembers it for when inputSig gives a new event again.

Awesome. But.. Do you ever feel weird about cramming all your inputs together, all your state together, all you logic together to make it fit in that one foldp? Most of the time there is too much that depends on each other to do the stuff in stages so in stead you split your logic into functions but then compose them all together and use one "big" foldp to keep your whole state. And that feels like a code pattern that doesn't scale to larger applications, at least to me. Of course "it feels like" is not a very good motivation to complain. But I'm so bad at making up examples...

What I can give you an example of is something you cannot currently do in Elm. It has to do with foldp and filters like keepWhen. Your logic inside the foldp is a pure function. So you can't use a filter inside. But say you have a game that pauses on game logic (e.g. someone scores a point in a game of Pong). Since your game is paused, you only need to listen to the input with which the player unpauses the game (e.g. spacebar). The rest of the inputs, including an fps 60 signal that's keeping your CPU occupied, can be filtered so your game doesn't get rendered at 60 frames per second while nothing changes.

If you don't follow the example any more and need to see some actual code, have a look at the attachment (example1.elm). It's code I also used in the slides of my talk.

Ok, so you want to filter (keepWhen) on the pause signal (part of the state calculated by foldp), but what you want to filter is fps 60, which is an input of the foldp. Now you have a circular dependency, or perhaps you'd call it recursively defined signal. Anyway, it's not possible (in the most general case) to define these in Elm because you cannot calculate the initial value (among other things):

a = constant 1
b = merge b a -- the initial value of b = the initial value of merge = the initial value of the first argument = the initial value of b...

So at this point you might think, why is he trying to use keepWhen? Can't you just use dropRepeats on the state since it doesn't change when paused?

To that I say: sure, but in general I feel limited in the ease of expressing myself in Elm, I suspect foldp to be the problem, and now I have at least one "real-world" example of something that foldp seems to prohibit, indirectly, for no good reason.

Get to the point...

Right. So we want something more general than foldp, that allows more than pure functions (filters, merge, sampleOn). And we also want something that doesn't have us put all the logic stuff together.
Is this even possible?
YES it is! With this Signal Loops idea. But I won't explain the details because this text is way too long already. Basically it requires you to give an initial value to the state (like foldp requires) and the rest is handled internally. 

[John Nilsson]

Not sure if I have anything to add to this, but since you asked.

It seems to me that reserving a keyword is a high tax for any feature. This one in particular feels a bit to specific to warrant a new keyword. If I understand the feature you are essentially giving the programmer a very constrained access to the time input of the signal function, otherwise reserved for the runtime to play with? But why not go for a more general access, why just lag by one step?

In any case, I don't think I understand the problem correctly because it seems like you can do this already without adding any new features. I gave it a shot and came up with this:

windowAdd: Int -> a -> [a] -> [a]
windowAdd size a window = take size (a :: window)

buffer: Int -> Signal a -> Signal [a]
buffer size = foldp (windowAdd size) []

lastOr: a -> [a] -> a
lastOr a l = last (a :: l)

lag: Int -> a -> Signal a -> Signal a
lag skip init s = (lastOr init) <~ buffer (skip+1) s

old: a -> Signal a -> Signal a
old init = lag 1 init

On the other hand, this is more or less the first elm code I've actually written, so don't take it to seriously ;)

BR,
John

--
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/d/optout.

[Max Goldstein]

So, since you asked....

I think that sometimes a unified/monolithic state type can be a good thing, since it keeps you from "cheating": you have to define exactly what constitutes an event and a state. But yes, as your application gets bigger, you want to separate things out. This is partially what the Event : State -> State design pattern attempts to do, avoiding the need for inextensible ADTs and for spreading logic across event handlers and the transition function. And if your transition function wants to not produce an event based on state, then just produce the given event, and use dropRepeats (or your optimization that does so automatically). At least as long as your state contains no functions, which as it grows bigger it is more likely to do....

What I'm trying to say is that this API might not let me do anything I couldn't do before, but it might let me do it in a nicer way. If someone can write a program using signal loops that just cannot be written with foldp, I'd like to see it and would support signal loops very strongly. A nice refactor of an existing example would be nice as well.

For all that wall of text, if I understand you correctly all you want is to introduce the keyword old to store the previous value of a signal. If I use old on a signal more than once, is only one copy retained? Is there value to doing this in Elm or am I missing something that requires it to be part of the language? Because, like John, I can do it with foldp without too much trouble (though his solution is generalized over the number of events to lag):

old : a -> Signal a -> Signal a

old d sig = snd <~ foldp (\new (prev,_) -> (new,prev)) (d,d) sig

This breaks us away from a single state type linchpinned through a single foldp, to many foldps (implicit in old). I suspect the best use of this decentralized state will be in refactoring: you won't be able to tell what needs to be broken out as you start typing. Or maybe my brain just doesn't work that way yet. I guess what I'm trying to say is, used poorly signal loops can make for worse code, and used well they can make for better code.

If my definition of old does what you want, it may be best to add it to the standard libraries (or a third party one) rather than introduce a new keyword. If you can argue why my implementation falls short, I still would like to see about a standard, native (JS) definition rather than a keyword. Basically, I think this is a good idea, but I want to implement it in the least invasive way possible.

[John Mayer]

What happens currently if I try to define a circular signal?

[Jeff Smits]

Thanks for your response John! You indeed don't understand the problem completely, so I haven't explained the feature well enough.

You are correct that old signalA lags behind by one round, compared to signalA.* The significant difference with your old function is that with this feature, you can define signalA in terms of old signalA. Right now Elm can't handle these recursive signals definitions.

Because of the lag by 1 and the recursive definitions, you get a more general form of state than you have with foldp. At that point I think it does warrant reserving a keyword.

The more general form of state can be illustrated with the Pong example. Pong has a large state ( :Game) that models the places where different objects ( :Ball and Player) are. It also models whether the game is paused or not ( :State).

If the game were pausable only by pressing the spacebar, you wouldn't have to put State into the Game. You could simply filter the input signal using the separate state of whether the game is paused or not. The reason playing/paused is in Game is that you also want to pause the game when the game-logic decides it's time to pause the game. Now suddenly you can't filter the input anymore. If you want the render function to stop being called at 35 fps when the game is paused, you'll have to add dropRepeats the gameState signal.

In general, foldp gets in the way of being able to use a filter where you might like one, because it takes a pure step function (first argument :input -> state -> state). With refactoring and clever use of dropRepeats you can probably still express the same program behaviours most of the time (only example I know that has observably different behaviour involves fps instead of fpsWhen, and the observable difference is the strain on the CPU, not the actual events that come through main).

But I prefer programs that are easily extensible, without refactoring the whole mess that's crammed inside a foldp. And by splitting definition and use of state like in this API proposal, you get the decoupling needed for those modular programs.

I have an example of this refactoring mess. Say you have a program that has two counters. If the spacebar is pressed down, the one counter updates every second. If the spacebar is not pressed, the other counter updates every second:
import Keyboard

input = every second

i1 = keepWhen Keyboard.space 0 input
c1 = count i1

i2 = dropWhen Keyboard.space 0 input
c2 = count i2

result = ((,) <~ c1 ~ c2)

main = asText <~ result

Now I want to add the functionality that when you hit enter, the counter with the lower value updates to the value of the other counter:
import Keyboard

input = every second

- i1 = keepWhen Keyboard.space 0 input
- c1 = count i1
-
- i2 = dropWhen Keyboard.space 0 input
- c2 = count i2
-

- result = ((,) <~ c1 ~ c2)

+ onSpace b (c1,c2) =
+   if b then (c1+1,c2) else (c1,c2+1)
+
+ onEnter b (c1,c2) =
+   if b then (max c1 c2, max c1 c2) else (c1,c2)
+
+ inputs = merge (onSpace <~ (sampleOn input Keyboard.space)) (onEnter <~ Keyboard.enter)

result = foldp (<|) (0,0) inputs

main = asText <~ result

Almost a full rewrite. You'll have to do your own (subjective) extrapolation because small examples are bad at showing how complicated this may get in a larger program. I think it will be a problem in the future for larger applications.

* In value old signalA lags behind by one round. When you start looking at changes and reacting to changes things get more complicated. You'll find that foldp only changes the state (and output signal) when the input signal changes. This also feels right in generalised state when you use recursively defined signals that lag by 1. But with your implementation of lag, changes to the state can by itself be the reason the state changes for the next round. Because of this and other reasons, the implementation is more subtle and cannot be done in Elm.

[Jeff Smits]

Thanks for responding Max :)

I agree that a monolithic state type is great when you have a small application. It gives you a single place in your code to look at when you want to know what state the program has. But with larger programs it is likely to become unwieldy in one way or another.

[...] this API might not let me do anything I couldn't do before, but it might let me do it in a nicer way.

I think that's a good summary. I know of only one example (as mentioned in my reply to John Nilsson) where a particular behaviour cannot be obtained without this feature. And that's not even behaviour that visible in the output of the program, but only in inefficient use of resources.

If you want me to refactor an example from the website using this proposed API, pick one, and I will gladly refactor it. I have time, so feel free to pick one of the larger examples. That'll only be better as a showcase the API.

I've also posted an example usecase of this API combined with the async function/keyword (not implemented in the current JS runtime) in another thread.

As I've written in my response to John, a pure Elm implementation is not possible. A Native implementation is also not possible. It really requires changes to the runtime. But I don't want to go into too much detail about the why in this thread because that scared people off before. If you have time, try watching my presentation from the Elm Workshop. I think I explain most of the implementation details there.

I suspect the best use of this decentralized state will be in refactoring

I agree

I guess what I'm trying to say is, used poorly signal loops can make for worse code, and used well they can make for better code.

Yes, this will give you more rope to hang yourself with. But I think you can already write confusing and messy code in Elm as it is. When you know the State/Input/Update pattern, functional programming conventions and foldp will automatically steer you towards it. But if you don't, or even within that pattern, you can still write "bad" code. With the power that comes from this feature, you can shoot yourself in the foot in more ways. The API I'm proposing is deliberately designed to remove as many footguns as possible though.

If I use old on a signal more than once, is only one copy retained?

I don't understand this question. Can you rephrase it? Or give an example?

[Jeff Smits]

Currently the compiler happily compiles your code without checking for recursively defined values (including recursively defined signals). What you get is code at fails immediately at startup giving you unhelpful error messages (though with recursive signals it tells you (in the developers console) to report the issue on GitHub).

What it should do is give you a compile-time error that you cannot recursively define a signal. A recursively defined signal, if built correctly would not do anything because it would wait for Change/NoChange messages from all the signals it depends on before doing a calculation and sending its own Change/NoChange message, but it depends on itself, therefore it waits indefinitely.

[Max Goldstein]

If I use old on a signal more than once, is only one copy retained?

I don't understand this question. Can you rephrase it? Or give an example?

mySignal = fps 30

oldCopy1 = old mySignal

oldCopy2 = old mySignal

oldCopy3 = old mySignal

...

Is the cost of these signals made with old linear or constant, i.e. do you memoize or cache the values?

Hmm, it's not possible to make runtime changes that are invoked by old as a function, not a keyword?

[Jeff Smits]

The cost of using old multiple time like that would be constant. Each of those expressions old mySignal would basically refer to the same thing.

It's possible to change the API to a single function old : a -> Signal a -> Signal a instead of a keyword old for definition and use. But I think that opens up pitfalls like accidentally nesting old calls. That's a valid but unlikely usecase, to have your state lag behind 2 rounds on the current of a signal. Accidentally doing that makes for nasty, hard to find bugs.

Whereas with the current proposal, a nested old call would need to be explicitly done like so:

old mySignal = 0
old oldMySignal = 0
mySignal = fps 30

oldMySignal = old mySignal

Another upside to splitting definition and use sites is that you can still define all state in a module in one place (like you define your State type in one place now). But I guess that's also possible when using a function.
Maybe a better argument is that this API forces you to always name you state. You can hide it inside a function, but you can't just plug it into any expression without first adding a definition old mySignal = .... So you still have to be deliberate when you add more state to your program, which is not a bad thing I think. 

[John Mayer]

Might I suggest that we fix the compiler behavior for recursively defined signals first?

[John Mayer]

Sorry, that was quite abrupt. I mean to say that I feel that this behavior should also be fixed as part of any loop proposal.

[Jeff Smits]

Sure, recursively defined values should be statically disallowed so problems with that don't confuse people. There is a GitHub issue open about this. I guess that issue should be resolved before adding this feature.

That reminds me: Another nice thing about having a keyword marking the use of an old signal is that you can treat it as one unit that refers to the definition old signal = ..., therefore the compiler doesn't actually "see" the recursion and can trivially exclude any problems with the analysis that would disallow it as a recursive signal.

[Alexey Zlobin]

Probably I missed something in conversation above. But I can't understand why a new keyword is needed here. Wouldn't function  which performs delay or pairs current value with previous (similar to Reactive's withPrevE/withNextE [1]) do exactly the same as proposed language structures?

[1] http://hackage.haskell.org/package/reactive-0.11.5/docs/FRP-Reactive-Reactive.html

[Dobes Vandermeer]

Hi Jeff,

My thoughts, since you asked:

1. Personally I like lumping all the input and state into one big pure automaton, so you lost me at the "why" part
2. I don't like the idea of taking a wonderfully common and useful word like "old" for this purpose

Why would I like lumping all the input together into one structure?

If I write my components as a pure library I can fire it up and pass in whatever I want, use it in unit tests with "fake" inputs, use it multiple times or just once, stuff like that.  The pure language is more re-usable than the signal language.

Passing around the inputs as an extensible record is no more difficult than passing around I/O in Haskell and I think it's worth the trouble because it gives more control.

I think the need for "dropRepeats" to avoid CPU use when a game is paused can be addressed in other ways.

Perhaps because the language is pure, `lift` could use the same mechanism used by "dropRepeats" to cache the previous result, since the lifted function is guaranteed to produce the same output given the same input (I think?).  Since there are relatively few types of signals that are stateful (foldp, automaton) signals could have a special update type that indicates that the signal was "touched" but the output was a repeat.  Stateless signals can propagate this if all their inputs are also only touched, much like how they propagate the "no change" events now.  I think this may not affect the semantics but would improve performance.

[John Mayer]

Agree with this. Rather than add the keyword, let's fix recursive signals now (with an appropriate error) and then introduce old (or some other name) as a function that allows an escape hatch.

Personally I favor the introduction of GADT style annotations: using natural numbers for topological depth to prevent recursive loops, and a boolean is-from-a-loop tags on looped signals to enforce the use of sampleOn to prevent infinite change-event churning. I know that this adds significant cognitive overhead, so maybe a different implementation is more appropriate, but those are the two invariants that I believe we ought to plug.

[Dobes Vandermeer]

I think an API like this might work:

-- f: function that builds the signal subgraph, accepts the signal of the previous value returned from that subgraph and returns a signal that outputs the new value of the subgraph

-- k: Initial value of the signal passed to the function

Signal.loop : (Signal b -> Signal b) -> b -> Signal b

Signal.loop f k = ... magic ...

Although I don't have a formal proof, I think it is possible to convert any signal graph or subgraph into one that gathers all inputs into a single object (record or tuple) and passes that into foldp.

The idea here is to generalize foldp to operate over a signal subgraph so that you can benefit from the signal combinators like dropWhile, keepIf, dropRepeats, and so on.

I think this would achieve a similar effect as the "old" keyword in that it gives access to old values of signals.

[John Mayer]

Yes I have also preferred that one Dobes. The implementation is by and large the same stuff but I much prefer this API. You don't have to worry about the recursive signal problem since you've inverted the API; though you still get the infinite hamster wheel of change events. But it's not a new idea.

Evan, what are the things you must see to start to consider adding this?

[Dobes Vandermeer]

John,

I think it should use the same rules as foldp; that is, if foldp doesn't have a hamster wheel problem then neither should this approach. But I'm not sure I understand the issue with the hamster wheel of change events, so I could be wrong about that.

Cheers,

Dobes

[John Mayer]

What happens when you have:

f = merge (constant 0)

Is the output value always change or nochange? I would argue the latter; this would happen anytime the output signal is an unsampled descendent of the top of the loop.

Are we even interested in forbidding this behavior? It's a problem with every loop proposal thus far that doesn't enhance the signal type.

[John Mayer]

Er, sorry, in the previous email I meant former, that it would necessarily be always a change event. And I think that's fine and that simply documenting works. I think this applies to both Jeff's and Dobes's API.

[Alexander Berntsen]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA256

On 07/07/14 18:56, Dobes Vandermeer wrote:
> 1. Personally I like lumping all the input and state into one big

> pure automaton, so you lost me at the "why" part

I'm with Dobes on this.

- --
Alexander
alex...@plaimi.net
https://secure.plaimi.net/~alexander
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v2.0.22 (GNU/Linux)
Comment: Using GnuPG with Thunderbird - http://www.enigmail.net/

iF4EAREIAAYFAlO7qVoACgkQRtClrXBQc7WQYwD/S88jY4KUsR1FTjByWcxgfknG
C867zHw35pDRT9jeOyEA/1eGaynT53zk1IPBV4ZKPlE87wA2ZsOJFJTvV+JKP656
=IENT
-----END PGP SIGNATURE-----

[Jeff Smits]

I was responding to each message separately, but referring to other posts a lot so I think I'll try a unified response to your messages.

First a note: I was hoping to have a discussion with normal Elm users (do we have those already?) to see if this API made sense, but instead I got all the knowledgeable people reconsidering if the feature is even wanted. Not what I had in mind, but still very much appreciated! I'm glad you're all taking the time to think about this, so thank you.

Start of responses

"Tuples in Signals": Whenever I see tuple in a Signal in Elm I think of the "change" information that is lost by using a Signal of tuples instead of a tuple of Signals. It's usually some kind of stateful computation that forces you to use datastructures inside signals instead of loose signals (the other common situation is that functions can only have a single result).

Of course optimisations in the compiler and runtime can alleviate at least some of the information loss. But for general datastructures, incremental computation is still very much in the research phase (at least, if my knowledge is up-to-date). And Reactive programming made for better incrementality of code. So taking a short-cut through normal datastructure sounds dirty to me, a code smell. And this is not just a feeling. But more on optimisations and code smells later.

Alexey:
I think withPrevE is like John Nilsson's buffer. As such it is indeed related to this feature. But note that FRP in Haskell usually just supports recursive definitions, which is not so simple in Elm. That's the powerful part of this feature I think. As for the syntax: I think decoupled definition and use of a previous value is nice while programming. See also above about why I dislike "Tuples in Signals".

Dobes:

Personally I like lumping all the input and state into one big pure automaton, so you lost me at the "why" part

I like that style too but I don't think it scales and I run into issues like having to add more to the input type, more to the state type, do more threading of the new input through different logic functions, add another logic function for the new feature based on the new input, find out where to add that new function in the composition chain that's put into the foldp... I feel like it's too much work and can only be alleviated with extensible records and State monads up to a point. So since my mental model says it's much easier to add a filter, I considered whether that would be nice. And I think it really is for modularity of your code. That's why I think generalised state fixes a fundamental problem in the language. I'll try to come up with more examples. For now though, have you seen the refactoring example I gave earlier?

If I write my components as a pure library I can fire it up and pass in whatever I want, use it in unit tests with "fake" inputs, use it multiple times or just once, stuff like that.  The pure language is more re-usable than the signal language.

If we add this feature, we can pull state up out of a module. Then the module is a bunch of input and output signals, some of which you might want to connect to get state that is completely under your control. By making it possible to write "pure" (in this case I mean stateless) code in the signal language, it makes the signal language just as testable as the pure language.

Perhaps because the language is pure, `lift` could use the same mechanism used by "dropRepeats" to cache the previous result, since the lifted function is guaranteed to produce the same output given the same input (I think?).  Since there are relatively few types of signals that are stateful (foldp, automaton) signals could have a special update type that indicates that the signal was "touched" but the output was a repeat.  Stateless signals can propagate this if all their inputs are also only touched, much like how they propagate the "no change" events now.  I think this may not affect the semantics but would improve performance.

This sounds familiar :) If I understand correctly you (re)invented an optimisation technique I recently shared with the list and later implemented. The PR was not merged because it made the internals of the Signal library quite complicated, and I didn't have benchmarks to prove performance increase. I'm working on simplifying the internals of the Signal library now. Then I'm going to reimplement the optimisation. Meanwhile I hope to extend Michael's elm-benchmark to be able to measure signal throughput and the like. Then I can benchmark the performance and hopefully have some nice results to show with my next PR.

John:

let's fix recursive signals now (with an appropriate error) [...]

 Agreed

[...] and then introduce old (or some other name) as a function that allows an escape hatch.

I'm open to other names. But a function makes it too easy to accidentally use it nested, which gives strange behaviour and hard to find bugs. Separate definition and use can also be ordered in a linear way, making it more easily visible that this is an acceptable way to refer a signal in the definition of that signal.

Personally I favor the introduction of GADT style annotations: using natural numbers for topological depth to prevent recursive loops, and a boolean is-from-a-loop tags on looped signals to enforce the use of sampleOn to prevent infinite change-event churning. I know that this adds significant cognitive overhead, so maybe a different implementation is more appropriate, but those are the two invariants that I believe we ought to plug.

I agree with the invariants and with the significant cognitive overhead part. I believe we can implement this fully in the compiler/runtime and spare Elm users some headaches.

Evan, what are the things you must see to start to consider adding this?

I spoke to Evan in Budapest after my presentation and he asked for a formal write-up for the feature. On-and-off I've spent some time on that. It's not even close to done, but I hope to have more time to spend on it this month and the next. 

Dobes:

Signal.loop : (Signal b -> Signal b) -> b -> Signal b

While think about the formal write-up, I considered using this at the most basic primitive. I called it fix because it's a Signal fixpoint computation, but it's otherwise the same. It's also very similar to loop from ArrowLoop. I already have a full translation to CML in the same style as Evan uses in his thesis, but then I figured there is something that's not so nice about this primitive. Like Arrows and foldp, this fixpoint for Signals will still need to use tuples to express a situation like this:

​(Oh, and I believe this situation might occur and be handy)

John:

Yes I have also preferred that one Dobes. The implementation is by and large the same stuff but I much prefer this API. You don't have to worry about the recursive signal problem since you've inverted the API

I actually added the keyword to the API, instead of using like magic functions like the Input library uses, because this will make the recursive signal problem easier. When going for the decoupled definition and use API, I think the keyword is the best/nicest way.

From the responses so far, it seems people are generally against adding new syntax. Which is fine in general. But I believe that adding this feature would mean a fundamentally more powerful language and a change in code-style. For something that big, I would argue that adding one extra keyword is justified and a rather light change.

Dobes:

I think it should use the same rules as foldp; that is, if foldp doesn't have a hamster wheel problem then neither should this approach.

I completely agree. foldp has the intuitive behaviour that only if the input signal changes, does the output signal and the state change. This feature is based on making the state look like a signal. But the behaviour of that state signal should be as intuitive as foldp. This goal is what makes the internals for this feature complicated.

John:

Are we even interested in forbidding this behavior? It's a problem with every loop proposal thus far that doesn't enhance the signal type.

I plan to enhance the Event type under the hood to forbid the behaviour of changes when none of the relevant inputs changed. Otherwise any use of this feature would be accompanied with boilerplate sampleOn code.

[John Mayer]

So let me put on my user hat:

I do want to see this and there is definitely a use case for signal loops instead of just foldp loops. The pause fps example is a good one.

I don't like the keyword and would prefer a function: you mention nesting... what's actually wrong with nesting? Maybe nesting is what I need for my use case... can you explain why you think nesting should be forbidden? How does the keyword forbid nesting?

As a (power) user, I also don't care a ton about the invariants: let me worry about hamster wheel safety and recursive signal definitions. (Here I have changed my mind. I'm skeptical that we should add this sort of static analysis to the compiler anyway: unlike the original CFRP paper,  there's nothing special about the signal type or the signal combinators in the Elm implementation.)

So as I put my implementer hat back on, as far as the API, I'm leaning towards the simplest, but with the behavior you describe.

Signal.loop : a -> Signal a -> Signal a

[Dobes Vandermeer]

I'm not sure I completely follow your example, here.

Are you asking what happens if the loop body doesn't refer to the looping value?  As in:

loop (\ looped -> (lift id constant 0)) 0

And you are asking whether the "looped" signal containing the "old" values should issue a CHANGE or NOCHANGE signal?

It's an interesting question.  I haven't really thought it through, and I don't think I understand that system well enough to make that call.

[Jeff Smits]

@John:

It's good to know you still want this feature to happen. Most people on this thread argued against adding it at all.

I understand the power-user POV of letting the user handle the dangerous edge-cases. And it would be a simple Native library to add what you're suggesting (although I don't understand what your loop function would do exactly).

I myself prefer a safe solution though, as long as we don't lose anything. I'm sure you would also like to have a solution that "just works" without boilerplate. I believe we can keep Elm as easy-to-use (with respect to Signals) as it is now, and I doubt Evan will accept anything less.

Of course I'm very biased because I spent a lot of time on developing ways to make this thing "just work". But I'm also a fan of static analysis making the programmers life easier.

[John Mayer]

I think we're making progress, but we should hop on a hangout. The main problem as I see it is that the compiler doesn't know much about the signal graph structure. I'd want to double back to the thesis for guidance on whether we can start to design improvements that make signal graph structure static analysis possible.

[John Nilsson]

Just for the record. Lacking sufficient experience in the language to actually feel the need. The only possible feedback I could offer was from a theoretical stand point, which kind of turns into probing to see what it adds. I'm not in a position to actually have an opinion on wether it is useful or not, so don't take my input as a vote against it.

The example with counters was very enlightening. Playing around with it made it very obvious how foldp, or any history dependent signal value for that matter, struggles somewhat if trying to attack it from a continuos time function (which I kind of feel drawn to and tried to do). Is it even possible to give foldp a reasonable interpretation with such signals?

In any case, I assume that elm takes the position that all signals are sampled at some frequency, so even a constant signal would have an epsilon to differentiate current value and old value?

Oh well I see the details of this is already being discussed, so to add something to that. As a potential user of elm the implicit triggering of events caused by a change in value makes me uneasy for two reasons

1. Equality, especially involving JavaScript, is not always clear so I expect this to be a source of frustration when debugging an error that would manifest as oddities in the time dimension, caused by a non time related function. Example of this would be a signal of not normalized Unicode strings.

2. The implicitness of exactly such things is what I'm trying to get away from when contemplating to switch to a language focusing on making time and change first class and disciplined.

So those are thing I will ponder on, how to make reactivity explicit and distinct from pure signals, and/or if that is actually warranted, have nothing constructive to add yet though.

BR

John

 

—
Sent from Mailbox

[Jeff Smits]

@John NIlsson: Good to know your vote is not against. I'll be happy to hear about any results of your pondering :)

@John Mayer: I'm on vacation, so I prefer not to do any video conferencing right now. I don't know the details of the compiler, but I imagine that to find the signal graph structure, you only need the AST(s) and name resolution. Then you can start at the sink nodes of the graph (main and any output ports) and follow the edges of the graph backwards by discovering calls in the AST to primitive Signal functions and resolving names to other expressions with primitive Signal functions.

[Becky Conning]

Has there been any movement towards this or any other way to use infinite signal graphs yet? I'd love to use elm or purescript but i've never made an application that didn't require continuous long polling. 

At the moment I use javascript with tcomb and kefir to create runtime type checked async data flow streams of changes. These are used to create async data flow properties which represent the current state of a collection. 

Obviously i'd rather use something that has the syntax of elm or purescript but this is a major limitation.

[Jeff Smits]

Sorry, no movement on generalised state. I think about this every so often but I don't really have time to commit to it. I can say with relative certainly that I won't have time for this stuff until November/December.

However, long polling is, as you mentioned, asynchronous. So you might be able to do that with the Promises business that comes out in Elm 0.15, which I expect will come out a lot sooner than generalised state.

[Evan Czaplicki]

There's progress on websockets, http, and sending messages in potentially loopy ways.