Re: [Haskell-cafe] A few ideas about FRP and arbitrary access in time

Patai Gergely

3 Mar 2010 3 Mar '10

5:33 a.m.

...Are hereby presented at: http://www.ee.bgu.ac.il/~noamle/_downloads/gaccum.pdf

Comments are more than welcome. (P.S Thanks to a whole bunch of people at #haskell for educating me about this, but most notably Conal Elliott)

Well, my impression is that trying to unite events and behaviours in this manner is not the solution we're looking for. If you follow the WWRD principle, you have to forget about events as fundamental building blocks, because the concept of event is an abstraction over continuous phenomena. Reality has a trivial solution: throw extreme parallelism at the problem, set an extremely high sampling rate and shamelessly 'recalculate' unchanging parts of the system all the time (which is exactly why you don't want to use Yampa or Elerea for GUI programming: they are pull-based, so they'll keep the CPU churning even in the absence of events; note also that both solve the problem of unlimited access to the past). In this framework, events can only be introduced as high-level abstractions that require much more computational power than what would seem necessary. It is a bit like using a large and complex neural network to perform basic arithmetic. Also, if you think about the applicative, monad etc. type class morphisms, you'll see that what makes sense for behaviours is completely useless for events. For instance, the applicative instance for behaviours (time functions) gives us a neat point-wise function application. However, if you define events as functions that are undefined almost everywhere, point-wise application of two events is only defined at the times where both events yield a value simultaneously. Same for monads: they capture the act of sampling for behaviours, but they can't do much for temporal values that are mostly undefined if interpreted as the reader monad. This suggests that events and behaviours have a different nature. Either only behaviours have a meaningful monad instance, or their meaningful monad instances are different. The unified system you're describing very much reminds me of Lucid Synchrone, if we think of behaviours as signals synchronised to the base clock, while events as signals with a slower clock. It might be interesting to think about how clock calculus interacts with the type class instances. However, that still doesn't say anything about the fact that the set of operations meaningful for behaviours and events are different, with only some overlap. Gergely -- http://www.fastmail.fm - Does exactly what it says on the tin

Show replies by date

sinelaw

3 Mar 3 Mar

2:45 p.m.

New subject: A few ideas about FRP and arbitrary access in time

...

Well, my impression is that trying to unite events and behaviours in this manner is not the solution we're looking for. If you follow the WWRD principle, you have to forget about events as fundamental building blocks, because the concept of event is an abstraction over continuous phenomena.

I'm not sure I want to follow WWRD all the way. I do want events, for example mouse clicks (for which there doesn't seem to be any logical behavior representation). As you note the pull-based approach does a lot more work in those cases than seems necessary. In any case, what I'm discussing in that report is mostly centered on the continuous-time values, so I'm more concerned with what we call behaviors. The question is how to model memory-full operations with point-wise operations. The only answer I've found for that in the Yampa framework is feedback with "pre", whose semantics seem to be the value after a "very short delay". This doesn't seem to hold water, when we really want to take the idea of continuous time seriously.

...

Reality has a trivial solution: throw extreme parallelism at the problem, set an extremely high sampling rate and shamelessly 'recalculate' unchanging parts of the system all the time (which is exactly why you don't want to use Yampa or Elerea for GUI programming: they are pull-based, so they'll keep the CPU churning even in the absence of events; note also that both solve the problem of unlimited access to the past). In this framework, events can only be introduced as high-level abstractions that require much more computational power than what would seem necessary. It is a bit like using a large and complex neural network to perform basic arithmetic.

Right. You'll agree that it would be nice to have a general approach? How will that work? That's what I'd like to find out.

...

Also, if you think about the applicative, monad etc. type class morphisms, you'll see that what makes sense for behaviours is completely useless for events. For instance, the applicative instance for behaviours (time functions) gives us a neat point-wise function application. However, if you define events as functions that are undefined almost everywhere, point-wise application of two events is only defined at the times where both events yield a value simultaneously. Same for monads: they capture the act of sampling for behaviours, but they can't do much for temporal values that are mostly undefined if interpreted as the reader monad. This suggests that events and behaviours have a different nature. Either only behaviours have a meaningful monad instance, or their meaningful monad instances are different.

Interesting points, I didn't consider that at all when writing that report. I'd like things to be unified, so maybe playing with the idea of a total function to 'Maybe a' for events is the right direction. I think this was already explored by some FRP incarnations, but I don't recall what came out of it.

...

The unified system you're describing very much reminds me of Lucid Synchrone, if we think of behaviours as signals synchronised to the base clock, while events as signals with a slower clock. It might be interesting to think about how clock calculus interacts with the type class instances. However, that still doesn't say anything about the fact that the set of operations meaningful for behaviours and events are different, with only some overlap.

But isn't Lucid Synchrone essentially discrete-timed? Also, events shouldn't be semantically constrained to multiples of some basic clock, they are defined over continuous time. Regarding the type classes - again I haven't thought in that direction much.

...

Gergely

P.S Thanks for the feedback!

Peter Verswyvelen

6 Mar 6 Mar

6:01 p.m.

New subject: A few ideas about FRP and arbitrary access in time

On Wed, Mar 3, 2010 at 8:45 PM, sinelaw wrote:

...

But isn't Lucid Synchrone essentially discrete-timed? Also, events

Maybe reality itself can also be modeled using discrete timesteps? If so, then a discrete clock calculus might make a lot of sense. I don't know much about theoretical physics - I think general relativity still is the "best" model for time, and it's continuous in that model - but maybe the people with a PhD in physics know more about it :-)

sinelaw

7 Mar 7 Mar

4:01 a.m.

New subject: A few ideas about FRP and arbitrary access in time

On Mar 7, 1:01 am, Peter Verswyvelen wrote:

...

On Wed, Mar 3, 2010 at 8:45 PM, sinelaw wrote:

...
But isn't Lucid Synchrone essentially discrete-timed? Also, events

Maybe reality itself can also be modeled using discrete timesteps? If so, then a discrete clock calculus might make a lot of sense. I don't know much about theoretical physics - I think general relativity still is the "best" model for time, and it's continuous in that model - but maybe the people with a PhD in physics know more about it :-)

I don't think a deep knowledge of physics is what we lack here, at least for the question of continuous vs. discrete time. Maybe the best physical model for nature really does involve discrete time steps. However, for our everyday experiences (and maybe for anything that's not on a the tiny quantum scale?) continuous time is the most natural model to follow. And when modeling changing values such as mouse position (the perpetual example...), animations, sound, etc. continuous time seems much more natural. Don't forget to check out the link Conal posted, his short blog post about the subject: http://conal.net/blog/posts/why-program-with-continuous-time/

Peter Verswyvelen

2:33 p.m.

New subject: A few ideas about FRP and arbitrary access in time

On Sun, Mar 7, 2010 at 10:01 AM, sinelaw wrote:

...

I don't think a deep knowledge of physics is what we lack here, at least for the question of continuous vs. discrete time. Maybe the best physical model for nature really does involve discrete time steps. However, for our everyday experiences (and maybe for anything that's not on a the tiny quantum scale?) continuous time is the most natural model to follow. And when modeling changing values such as mouse position (the perpetual example...), animations, sound, etc. continuous time seems much more natural.

Don't forget to check out the link Conal posted, his short blog post about the subject: http://conal.net/blog/posts/why-program-with-continuous-time/

Sure, using continuous time sounds obvious, but the principle "What Would Reality Do" feels scary, because we really don't know what Reality is when it comes to time; or anything really, all we have is mathematical models that work good enough, and sometimes we have two different models that are used depending on how we want approach a certain problem (e.g. light: wave versus particle) I'm a game developer and I don't care to much about reality. But when I'm not in hacking mode to Get Things Done, I do care about composable, maintainable, and beautiful pieces software, and the way games are developed today are IMO far from that, so hopefully FRP will solve this one day and be efficient enough to run on average hardware.

...

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

Brandon S. Allbery KF8NH

9:25 p.m.

New subject: A few ideas about FRP and arbitrary access in time

On Mar 7, 2010, at 04:01 , sinelaw wrote:

...

I don't think a deep knowledge of physics is what we lack here, at least for the question of continuous vs. discrete time. Maybe the best

There is a discrete time quantum. But unless you're doing simulations at the quantum level, you really don't want to go there (even ignoring that one second of real time would take a really long time to calculate on current hardware :); stick to macrocosmic physics, which is statistically continuous. -- brandon s. allbery [solaris,freebsd,perl,pugs,haskell] allbery@kf8nh.com system administrator [openafs,heimdal,too many hats] allbery@ece.cmu.edu electrical and computer engineering, carnegie mellon university KF8NH

Aaron Denney

9 Mar 9 Mar

12:23 a.m.

New subject: A few ideas about FRP and arbitrary access in time

On 2010-03-08, Brandon S. Allbery KF8NH wrote:

...

There is a discrete time quantum. But unless you're doing simulations at the quantum level, you really don't want to go there (even ignoring that one second of real time would take a really long time to calculate on current hardware :); stick to macrocosmic physics, which is statistically continuous.

That's ... contentious. In both quantum mechanics and GR, time is completely, flattly, continuous. In certain extremely speculative frameworks attempting to combine the regimes in which they are applicable, that may not be the case. But for accepted physics models, time really is continous. -- Aaron Denney -><-

John Meacham

12:34 p.m.

New subject: A few ideas about FRP and arbitrary access in time

On Tue, Mar 09, 2010 at 05:23:56AM +0000, Aaron Denney wrote:

...

On 2010-03-08, Brandon S. Allbery KF8NH wrote:

...
There is a discrete time quantum. But unless you're doing simulations at the quantum level, you really don't want to go there (even ignoring that one second of real time would take a really long time to calculate on current hardware :); stick to macrocosmic physics, which is statistically continuous.

That's ... contentious. In both quantum mechanics and GR, time is completely, flattly, continuous. In certain extremely speculative frameworks attempting to combine the regimes in which they are applicable, that may not be the case. But for accepted physics models, time really is continous.

Hmm.. I thought something interesting happened on the scale of the plank time, 10^-44 seconds or so. Or is that only relevant to our ability to _measure_ things at that scale and not the continuity of time itself as far as QM is concerned? John -- John Meacham - ⑆repetae.net⑆john⑈ - http://notanumber.net/

Heinrich Apfelmus

3:18 p.m.

New subject: A few ideas about FRP and arbitrary access in time

John Meacham wrote:

...

On Tue, Mar 09, 2010 at 05:23:56AM +0000, Aaron Denney wrote:

...
On 2010-03-08, Brandon S. Allbery KF8NH wrote:

...
There is a discrete time quantum. But unless you're doing simulations at the quantum level, you really don't want to go there (even ignoring that one second of real time would take a really long time to calculate on current hardware :); stick to macrocosmic physics, which is statistically continuous.

That's ... contentious. In both quantum mechanics and GR, time is completely, flattly, continuous. In certain extremely speculative frameworks attempting to combine the regimes in which they are applicable, that may not be the case. But for accepted physics models, time really is continous.

Hmm.. I thought something interesting happened on the scale of the plank time, 10^-44 seconds or so. Or is that only relevant to our ability to _measure_ things at that scale and not the continuity of time itself as far as QM is concerned?

It may sound strange, but continuous quantities are often an approximation. For instance, a bar of steel is composed of a finite number of atoms, but if you want to know how it behaves under load (theory of elasticity), you can model it as a continuous mass just fine because the number of atoms is huge. Same goes for time. It doesn't really matter what happens in minuscule time scale; for the purpose of Newtonian mechanics, time is continuous. (It's continuous for the purpose of modeling more fundamental theories as well.) The key point is that this is not "absolute" reality, it's just a model. Regards, Heinrich Apfelmus -- http://apfelmus.nfshost.com

Gregory Crosswhite

3:41 p.m.

New subject: A few ideas about FRP and arbitrary access in time

On Mar 9, 2010, at 9:34 AM, John Meacham wrote:

...

Hmm.. I thought something interesting happened on the scale of the plank time, 10^-44 seconds or so. Or is that only relevant to our ability to _measure_ things at that scale and not the continuity of time itself as far as QM is concerned?

Quantum mechanics itself does not have a natural time scale at which "interesting things" start to happen, but some theories built using quantum mechanics do. It helps if you think of quantum mechanics as being like Newton's laws: it is not a theory itself so much as a metatheory that provides ground rules for how to construct theories of nature. (And yes, I actually am a quantum physicist. :-) ) Cheers, Greg

Donn Cave

3 Mar 3 Mar

3:50 p.m.

New subject: A few ideas about FRP and arbitrary access in time

Kind of a long shot, from what I can make out, but Timber might be interesting - Haskell-like programming language with a "reactive" model that supports time as a sort of event. http://www.timber-lang.org/ Certainly not much like what we're talking about, but I haven't picked up on the application domain of `behaviors' - for all I know that's just about working around the lack of support for time events. Donn

sinelaw

4:02 p.m.

New subject: A few ideas about FRP and arbitrary access in time

On Mar 3, 10:50 pm, Donn Cave wrote:

...

Kind of a long shot, from what I can make out, but Timber might be interesting - Haskell-like programming language with a "reactive" model that supports time as a sort of event. http://www.timber-lang.org/

Certainly not much like what we're talking about, but I haven't picked up on the application domain of `behaviors' - for all I know that's just about working around the lack of support for time events.

Donn

Thanks, timber looks interesting and definitely worth looking at . Behaviors are used to represent values that change continuously with time. Even if the implementation is discrete (as all digital hardware), it may be more natural to treat things such as a temperature sensor, mouse position, and perhaps even video as functions of continuous time, values that vary continuously. So behaviors are not a workaround at all, in this sense.

Conal Elliott

6:56 p.m.

New subject: A few ideas about FRP and arbitrary access in time

...

Even if the implementation is discrete (as all digital hardware), it may be more natural to treat things such as a temperature sensor, mouse position, and perhaps even video as functions of continuous time, values that vary continuously. So behaviors are not a workaround at all, in this sense.

Just as we program with infinite lists etc even though the implementation is finite. In this way, implementations serve abstractions/semantics/specifications, rather than vice versa. See also http://conal.net/blog/posts/why-program-with-continuous-time/ . - Conal

5552

Age (days ago)

5558

Last active (days ago)

List overview

Download

12 comments

10 participants

participants (10)

Aaron Denney
Brandon S. Allbery KF8NH
Conal Elliott
Donn Cave
Gregory Crosswhite
Heinrich Apfelmus
John Meacham
Patai Gergely
Peter Verswyvelen
sinelaw