Beyond FRP: physics-inspired programming abstractions?

I've been doing a lot of physics and graphics programming lately, and it seems like many physics concepts might make good programming language abstractions. This idea is sort of in the same spirit of how functional-reactive programming makes time-varying values direct abstractions in the programming language.

One such abstraction could be force. Basically, force acts to change a stateful value over time. In this way, a force is very different from a signal, which more or less specifies a transformation of a stateless value according to time. Although we can fake physical effects such as bouncing using Penner Easing Equations (e.g., BounceEaseOut), real simulation of physical processes requires that we basically abandon signals and use forces instead (possibly through a physics engine). In WPF, this means rather than databind a property, we update periodically in the render loop.

Compared to signals, the nice thing about a force is that it they are composable: the effects of multiple forces can be combined, while a value can't really be bound to multiple signals. E.g., a body's velocity (and ultimately its position) could be affected by gravity and one or more spring forces. Such forces could possibly be extended to other non-physical domains; e.g., market price modeling (just as many physicists use their skills on Wall Street). Collision detection and resolution techniques could be a nice way of dealing more efficiently with detecting the many kinds of events that can occur in a complicated system.

A physics-inspired programming language could entail a drastically different object organization that occurs currently. Possibly, objects would not interact unless some physical connection between them (collision) possibly provided by the environment (e.g., via diffusion ala Repenning's anti-objects). The implementation of a such a language would forgo a traditional interpreter for a physics engine, which could then be accelerated by the GPU using CUDA or through parallelization across multiple cores.

Any thoughts? Crazy idea, plausible PL research direction, or leave this kind of thing to the graphics community?

I don't get it...

I looked at Penner's Easing Equations, and I'm not sure why you are giving him so much credit. His book is likely useful for animators using Actionscript, and possibly GUI developers, but certainly not for anybody doing serious physics simulations. Take his bouncing code for example:

class com.robertpenner.easing.Bounce {
	static function easeOut (t:Number, b:Number, c:Number, d:Number):Number {
		if ((t/=d) < (1/2.75)) {
			return c*(7.5625*t*t) + b;
		} else if (t < (2/2.75)) {
			return c*(7.5625*(t-=(1.5/2.75))*t + .75) + b;
		} else if (t < (2.5/2.75)) {
			return c*(7.5625*(t-=(2.25/2.75))*t + .9375) + b;
		} else {
			return c*(7.5625*(t-=(2.625/2.75))*t + .984375) + b;
		}
        }
       /*snipped for brevity*/
}

This obviously isn't physically accurate, except possibly in very special cases when you choose the "correct" b, c, and d, the fourth bounce is too small to be relevant to the ongoing simulation, you don't call this function with ever increasing values of t, and whatever other convoluted assumptions you need to get this to work.

As for signals versus state, I don't see what you are getting at. Say you have brownian motion simulator with n particles, something that also involves collisions. Unlike the "bouncing" example above, I don't know of any efficient way to calculate the state of a system as a function of time given initial conditions, and would be surprised that such an algorithm exists. However, given the state of a system at time t, I can certainly calculate the state of the system at time t + d with reasonable efficiency. (for an appropriately small value of d, and assuming there isn't significant inter-particle forces at play causing time complexities similar to the n-body problem.)

Signals can be modelled using streams, and corecursive stream equations are a powerful technique for dealing with state. For example, corecursive streams are rather attractive way of modelling digital circuits with delayed feedback, i.e. state. I haven't done a brownian motion simulator based on this idea, though I'm sure I could.

By Leon P Smith at Mon, 2008-07-28 00:21 | login or register to post comments

I should have qualified this

I should have qualified this that I'm primarily interested in UI rather than in actual physical simulations. In UI, Penner's equations are used to simulate physical effects although no physical simulation is being performed. Also, a penner equation can easily be used to transform a signal, e.g.,

rectangle.top = bounceEaseOut(clock) * extent

So that the rectangle appears to bounce as clock goes from 0 to 1. If you want a better bounce effect in your UI, then the obvious path is through true physical simulation.

I've never dealt with co-recursive stream equations. The signal systems that I have played with are asynchronous and live in imperative environments (Scheme, Java, .NET) where signals definitely cannot be modeled as streams. Granted, this is the other world of more formally loose form of FRP that focuses on efficiency over purity.

By Sean McDirmid at Mon, 2008-07-28 01:53 | login or register to post comments

Functional reactive systems theory

I have to admit that I don't have much experience with FRP, so perhaps I'm missing something here. But I don't really see why forces cannot be accounted for as signals in the usual FRP model. The FRP model, as far as I'm aware, draws heavily on classical systems theory: signals are functions from time to some set of values, systems transform signals to signals (input to output). Memoryless systems produce an output based only on the present input. Systems with memory (stateful systems) produce an output that depends on previously received inputs as well as the current input. What's different about forces, as you've described them, is not that they can't be treated as signals, but that they (usually) act on systems that have memory. The position and velocity of a body depend both on the current force input, and on the state of the body (which is the result of previous force inputs). So simulation of physical processes doesn't require abandoning signals, it just requires stateful systems to transform the signals.

A simple example of a stateful system in an FRP context appears in Wan and Hudak's FRP from 1st Principles, on page 5>

  > integral :: Behavior Real -> Behavior Real
  > integral fb = 
  >   \ts@(t:ts') -> 0 : loop t 0 ts' (fb ts)
  >       where loop t0 acc (t1:ts) (a:as)
  >           = let acc' = acc + (t1-t0)*a
  >             in acc' : loop t1 acc' evs ts as

If the input signal was a time varying force, the output signal from the integrator would be the momentum (mass x velocity) of the body represented by the integrator system.

By Allan McInnes at Mon, 2008-07-28 01:06 | login or register to post comments

True continuous time varying

True continuous time varying values don't seem to work well performance-wise, judging by the Haskell work switching focus to event based models. Once you go to step-wise functions, true physics goes away. I didn't really understand how they could achieve true continuous values without theorem proving in the first place (ex: pulling on integral(sin(t)) isn't enough), and that's important (more realistic ex: an event that occurs when a moving point crosses a line - sampling might skip it). Losing integrals and derivatives would hurt for writing complex animation and layout. OTOH, using the same concepts of time-varying values and limiting the operations or primitive values might work.

I'm trying to figure out how to make layout & typical GUI animations parallel this summer, and have been thinking along these lines (in particular, some combination of linear constraints, physics, and data flow or frp). Sounds like you're going along similar lines :) One recurring thought has been on where the precision is really necessary in all of this.

Somewhat related is the prefuse/flare libraries, which seem to be some of the best for creating charts & graphs by using force-directed layout. This may be important for many UIs going forward, esp. for animation, but as I mentioned, mixing it with more typical constraints seems key to making it more generally applicable. Perhaps I'll finally do something useful ;-)

By lmeyerov at Mon, 2008-07-28 11:16 | login or register to post comments

Simply efficient functional

Simply efficient functional reactivity claims to provide efficient continuous values.

By naasking at Mon, 2008-07-28 23:21 | login or register to post comments

that was what I was

that was what I was referring to: it introduces reactive values, which move away from them (push based), afaict

By lmeyerov at Mon, 2008-07-28 23:59 | login or register to post comments

confusion about reactive values and continuous time

Continuous time is still very important to me, for natural, simple, and composable modeling. The "simply" paper doesn't move away from continuous time. Rather, it shows how to decompose the specification of continuous reactive behaviors into two simpler notions: reactive values and time functions, with no loss of expressiveness.

A few of us are working on the Reactive library currently. It will be in good shape by the end of the summer.

By Conal Elliott at Tue, 2008-07-29 18:32 | login or register to post comments

Re: summer

that is pretty exciting; i hope i can get time to try to get my head around it all. many thanks for the efforts.

By raould at Wed, 2008-07-30 02:00 | login or register to post comments

Coupled states ..

I find FrTime and FRP in general a bit difficult to think with when it comes to coupled states - which feature in many systems where the physics is of interest. For example, consider two masses connected by a spring. The (x,p) states of either mass is coupled to the other using the spring's force function.

For such systems, the update cycle goes something like this -
1. Compute forces using current (x,p)
2. Apply force to each p
3. Apply p to each x.
4. Step time
* Repeat.
(2&3 can be combined)

How would you express this naturally using FRP?

By Srikumar Subramanian at Wed, 2008-07-30 15:45 | login or register to post comments

your example if expanded out

your example if expanded out is just a set of differential equations, which can be expressed almost as it is in FRP. I don't see a problem here at all. In fact an iterative representation of the same algorithm (like you stated) is less abstract.

By alanine at Wed, 2008-07-30 20:32 | login or register to post comments

can you give an example ..

Is is interesting that you see otherwise. Will it be possible for you to give an example - say in FrTime, using two masses coupled by a spring in 1 dimension? .. with spring constant k.

.. for which the hamiltonian is p1^2/2m1 + p2^2/2m2 + 1/2 k * (x2-x1)^2.

.. and my intention is to draw the two masses.

By Srikumar Subramanian at Thu, 2008-07-31 07:53 | login or register to post comments

It's to solve the following

It's to solve the following set of equations:

x1 = x10 + integral v1
x2 = x20 + integral v2
v1 = v10 + integral a1
v2 = v20 + integral a2
a1 = F / m1
a2 = -F / m2
F = -k * ((x2 - x1) - l)

where x10, x20, v10, v20 are initial values, and l is the equibrium length of the spring.

I'm not familar with FrTime, so I'm not sure if it can directly express recursive definitions. But in original FRP and Yampa, you can write a program almost identical to the above equations.

By alanine at Thu, 2008-07-31 11:50 | login or register to post comments

thanks ..

.. and Yampa looks neat.

By Srikumar Subramanian at Fri, 2008-08-01 05:58 | login or register to post comments

Numerical errors aside, the

Numerical errors aside, the precision problem can be overcome by taking a prediction approach rather than sampling. Generating a (time-ordered) queue of future events would guarrantee none will be missed. It's an implementation issue.

A physics engine used in games and simulations pretty much does it too. To find out whether something has happened between two frames, it calculates exact time an event takes place, and compensates in the next frame if the exact moment has been missed.

By alanine at Tue, 2008-07-29 18:19 | login or register to post comments

Conservative Logic

Conservative logic is a comprehensive model of computation which explicitly reflects a number of
fundamental principles of physics, such as the reversibility of the dynamical laws and the
conservation of certain additive quantities (among which energy plays a distinguished role). Because
it more closely mirrors physics than traditional models of computation, conservative logic is in a
better position to provide indications concerning the realization of high-performance computing
systems, i.e., of systems that make very efficient use of the "computing resources" actually offered by
nature. In particular, conservative logic shows that it is ideally possible to build sequential circuits
with zero internal power dissipation. After establishing a general framework, we discuss two specific
models of computation. The first uses binary variables and is the conservative-logic counterpart of
switching theory; this model proves that universal computing capabilities are compatible with the
reversibility and conservation constraints. The second model, which is a refinement of the first,
constitutes a substantial breakthrough in establishing a correspondence between computation and
physics. In fact, this model is based on elastic collisions of identical "balls," and thus is formally
identical with the atomic model that underlies the (classical) kinetic theory of perfect gases. Quite
literally, the functional behavior of a general-purpose digital computer can be reproduced by a perfect
gas placed in a suitably shaped container and given appropriate initial conditions

By Greg Buchholz at Mon, 2008-07-28 03:12 | login or register to post comments

forces via FRP

Force is indeed a nice simple abstraction and one that is very easy to code up as in FRP. Just use a bit of arithmetic and a couple of integrals.

By Conal Elliott at Tue, 2008-07-29 18:36 | login or register to post comments

With collision detection and

With collision detection and impulse-based collision response? I don't really see how that could work, I'm not sure how integrals could possibly work in say a system with 100 circles bouncing off the wall and each other. Once we have simulate collisions as impulses, I think you'd have to get rid of integrals. The alternative would be modeling the collision precisely, which would be too expensive for real time use.

By Sean McDirmid at Wed, 2008-07-30 05:25 | login or register to post comments

Ha, nice that you mentioned

Ha, nice that you mentioned it. I've exactly the same example application of 100 balls bouncing off wall and each other written in Yampa-like FRP. Indeed I'm putting together a serie of samples to be a tutorial for FRP, so I'm looking for ideas of such suitable applications.

And yes, I modelled collisions precisely, and I don't see any problem to do it in real time. There is still much room to improve in terms of algorithms, as I'm not exactly using a queue for future events. A nice optimization would be to use a priority queue.

By alanine at Wed, 2008-07-30 23:39 | login or register to post comments

future events?

How would the "queue for future events" interact with real time input?

To extend the example application, let's say there are 100 balls bouncing off walls and each other and an object controlled by a human or an external system. How does this fit in your model?

By e at Thu, 2008-07-31 03:12 | login or register to post comments

A queue for future events is

A queue for future events is merely a prediction, which can be modified accordingly if real-time input is also considered.

E.g., if a person only controls the force (acceleration), the movement of the object can still be predicted (either assuming no more input, or same input from the person), and hence future collision is calculated. Whenever the input changes, a new prediction is made to replace the old one.

If the location also comes from real-time input, then it's really a discrete signal. In this case, what do we mean by two objects collide? It may require a different definition.

By alanine at Thu, 2008-07-31 03:47 | login or register to post comments

In a physics engine,

In a physics engine, collisions are detected via a conservative broad phase and a more accurate narrow phase. A broad phase can involve swept shapes to predict if bodies could have or will collide during the time period that the physics engine is skipping over.

By Sean McDirmid at Thu, 2008-07-31 06:35 | login or register to post comments

Cool. I'm looking forward to

Cool. I'm looking forward to reading the brief! There is a sort of big disconnect between the more pure arrow-based FRP of Yampa and the more lightweight FRP-like systems I'm more familiar with (SuperGlue, FrTime). Its definitely possible that the pure FRP systems are more expressive and can represent this. In an lightweight FRP system, I mostly have to fall back on state and leave the language.

By Sean McDirmid at Thu, 2008-07-31 03:17 | login or register to post comments

Lambda the Ultimate

User login

Navigation