More on delayed switching
Hello all, I opened a thread some time ago where I asked whether it's enough to have only immediate switching. But it dawned on me that Reactive switches are actually all delayed, since even though the delay is infinitesimal in principle, we still have to wait for the next point of observation until we can see its effect. This is a huge problem in practice, because this way every stateful signal imposes a delay equal to the length of the period between observations. Here's a simple test case for illustration:
import Control.Applicative import FRP.Reactive
tick :: Event () tick = atTimes [0..]
behs :: [Behavior Double] behs = pure 1 : map (integral tick) behs
eventList :: Event a -> [a] eventList e = x : eventList e' where (x,e') = firstRestE e
testBeh :: Behavior a -> [a] testBeh b = take 10 $ eventList (snapshot_ b tick)
test :: IO () test = mapM_ (print . testBeh) (take 5 behs)
Running test prints the following: [1.0,1.0,1.0,1.0,1.0,1.0,1.0,1.0,1.0,1.0] [0.0,0.0,1.0,2.0,3.0,4.0,5.0,6.0,7.0,8.0] [0.0,0.0,0.0,1.0,3.0,6.0,10.0,15.0,21.0,28.0] [0.0,0.0,0.0,0.0,1.0,4.0,10.0,20.0,35.0,56.0] [0.0,0.0,0.0,0.0,0.0,1.0,5.0,15.0,35.0,70.0] I ran into the very same problem when working on the first version of Elerea. Transfer functions in version 0.1.0 behave exactly the same way, and I switched to immediate transfer functions from 0.2.0. The difference is obvious if you look at the breakout example in action: in 0.1.0, the ball takes long to react to collisions, since the dependency cycle consists of three items (bricks, velocity, position), so any change takes just as many frames to propagate. From 0.2.0 onwards, collisions are much more accurate without any change in the example code. Sure, it is possible to work around the delay by combining the switching value with the one that caused its switch, but this adds a lot of complexity to the code on the user end. You can make life easier by introducing immediate versions as helper functions, but then you just reintroduced this distinction. Of course this is not surprising, since neither delayed nor immediate switching is sufficient on its own. But this means that Reactive should support both out of the box and not encourage ad hoc workarounds that are likely to break in unexpected ways. Also, immediate switching seems the more sensible default, because it's more straightforward to derive the delayed version from it than the other way around, and it is what we need most of the time. Are there any plans to address this problem? Or a completely new angle to look at it from? Gergely -- http://www.fastmail.fm - Faster than the air-speed velocity of an unladen european swallow
I think what you're describing results from a worst-case combination of
three factors:
1. Infinitesimal delay semantics of switch
2. Euler integration
3. Exact synchronization of numerical integration time samples with display
samples
Of these three factors, I see the first one as benign and semantically
ideal. The imposed delay is the theoretical minimum (infinitesimal) while
still allowing meaningful specification of self-reactive and
mutually-reactive systems. And it's consistent with differentially
specified continuous behavior. On the other hand, the second and third
factors are implementation artifacts rather than desirable semantics.
Moreover, they're artifacts that cause the implementation to stray from the
semantic ideal.
My inclination is to embrace 1 and somehow fix 2 & 3. I'm guessing 3 is
easy and 2 is hard.
For 3, I know of no benefit to having integration sample times correspond to
display times, or even to match the frequency. I implemented it that way
just for simplicity, and now I see it was a terrible idea. My intention is
to use a variable-step-size method that adapts to both the nature of the
behavior being integrated and to the available compute cycles.
As for 2, I've used much better integration methods in the past. What's
tricky here is getting an integration method that works for self- or
mutully-recursive integration (i.e. ODE systems) *without* the ability to
see the cycles. Euler is easy but is terribly inaccurate or
inefficient&instable.
- Conal
2009/7/7 Patai Gergely
Hello all,
I opened a thread some time ago where I asked whether it's enough to have only immediate switching. But it dawned on me that Reactive switches are actually all delayed, since even though the delay is infinitesimal in principle, we still have to wait for the next point of observation until we can see its effect. This is a huge problem in practice, because this way every stateful signal imposes a delay equal to the length of the period between observations. Here's a simple test case for illustration:
import Control.Applicative import FRP.Reactive
tick :: Event () tick = atTimes [0..]
behs :: [Behavior Double] behs = pure 1 : map (integral tick) behs
eventList :: Event a -> [a] eventList e = x : eventList e' where (x,e') = firstRestE e
testBeh :: Behavior a -> [a] testBeh b = take 10 $ eventList (snapshot_ b tick)
test :: IO () test = mapM_ (print . testBeh) (take 5 behs)
Running test prints the following:
[1.0,1.0,1.0,1.0,1.0,1.0,1.0,1.0,1.0,1.0] [0.0,0.0,1.0,2.0,3.0,4.0,5.0,6.0,7.0,8.0] [0.0,0.0,0.0,1.0,3.0,6.0,10.0,15.0,21.0,28.0] [0.0,0.0,0.0,0.0,1.0,4.0,10.0,20.0,35.0,56.0] [0.0,0.0,0.0,0.0,0.0,1.0,5.0,15.0,35.0,70.0]
I ran into the very same problem when working on the first version of Elerea. Transfer functions in version 0.1.0 behave exactly the same way, and I switched to immediate transfer functions from 0.2.0. The difference is obvious if you look at the breakout example in action: in 0.1.0, the ball takes long to react to collisions, since the dependency cycle consists of three items (bricks, velocity, position), so any change takes just as many frames to propagate. From 0.2.0 onwards, collisions are much more accurate without any change in the example code.
Sure, it is possible to work around the delay by combining the switching value with the one that caused its switch, but this adds a lot of complexity to the code on the user end. You can make life easier by introducing immediate versions as helper functions, but then you just reintroduced this distinction. Of course this is not surprising, since neither delayed nor immediate switching is sufficient on its own. But this means that Reactive should support both out of the box and not encourage ad hoc workarounds that are likely to break in unexpected ways. Also, immediate switching seems the more sensible default, because it's more straightforward to derive the delayed version from it than the other way around, and it is what we need most of the time.
Are there any plans to address this problem? Or a completely new angle to look at it from?
Gergely
-- http://www.fastmail.fm - Faster than the air-speed velocity of an unladen european swallow
_______________________________________________ Reactive mailing list Reactive@haskell.org http://www.haskell.org/mailman/listinfo/reactive
Of these three factors, I see the first one as benign and indeed what I see as ideal semantics. The imposed delay is the theoretical minimum (infinitesimal) while still allowing meaningful specification of self-reactive and mutually-reactive systems. Yes, that's definitely true. But you also need the appropriate combinators to be able to exploit this potential.
For 3, I know of no benefit to having integration sample times correspond to display times, or even to match the frequency. The fact that the test uses integral is really beside the point. We can talk about any arbitrary behaviour and its changes.
The heart of the problem is that according to the current Reactive approach there's no way to derive an event solely from behaviours, since we inevitably need sampling events to get to the values. In order to avoid unnecessary delays in the presence of mandatory infinitesimal delays, we'd have to make sure that if A depends on B, then A is switched only after some non-zero time elapsed since the switch of B, otherwise we'll observe the propagation of delays as in the example. It is big enough of a problem to generate appropriate sampling events all around the system that take the dynamically changing dependencies into consideration (in fact, this is a huge burden on the programmer!), but there's obviously no way to do so in the presence of a dependency cycle. And again, we arrive at the need of breaking cycles somehow. You even have to be explicit about the place of this break if you want a deterministic system. Because of all this, I believe that Fran's predicate events make much more sense at least in the semantic basis. You're among the most knowledgeable about all the issues concerning them, and I'm sure you had a fleet of good reasons to give up on this approach, but the Reactive way doesn't seem to be the right answer either.
to use a variable-step-size method that adapts to both the nature of the behavior being integrated and to the available compute cycles. I'm afraid there's no way that would fit every application, so any kind of advanced sampling can only be an option. After all, even a single application can have wildly different stability properties if you start tweaking some parameters. And you have to be able to tell apart desired behaviour from unwanted artifacts. If you look at a real-time physics engine, you'll see trade-offs everywhere. For instance, allowing some interpenetration between supposedly solid objects improves stability when there are lots of collisions around without resorting to extreme supersampling. It is up to you how much (both in time and space) inconsistency you can live with for the sake of real-time reactivity.
In short, I don't think adaptive time step is the real solution here. You'll have to be able to express trade-offs in general in order to get a practical system, and playing around with the sampling rate is just one special case. Committing to it means not letting the programmer decide whether they prefer smooth or accurate animation, or more precisely put, where on that scale their preference lies.
As for 2, I've used much better integration methods in the past. As I said, this is not really about integration, which only served as an example. It's about reactivity in general.
Gergely -- http://www.fastmail.fm - The way an email service should be
participants (2)
-
Conal Elliott -
Patai Gergely