[Haskell-cafe] FRP, integration and differential equations.

Steve Lihn stevelihn at gmail.com
Thu Apr 23 08:51:29 EDT 2009 

Just my two cents. The open source project Maxima is a very successful
math engine dedicated to solving ODE PDE and integration among many
other things. It is implemented in LISP.

Steve


On 4/21/09, jean-christophe mincke <jeanchristophe.mincke at gmail.com> wrote:
> Peter, Paul,
>
>>But my question is, is FRP really the right setting in which to
>>explore a highly accurate ODE solver?
>
>>Well, solving the ODE is usually the task of a dedicated physics engine.
> But IMHO with FRP we try to reuse >small building blocks so we get very
> modular systems; a big physics black box seems to be against this principle?
>
> I believe it is a good question. My answer is why not. In fact when I
> discovered FRP I liked the way systems could be constructed from building
> blocks as Peter says. I have a previous experience in designing simulators
> for complex  dynamic systems and I often had to find solutions to build
> simulators from a smal set of building blocks and still keep an adequate
> accuracy.
>
> Doing so often leads to ODEs of the form:
>
> de/dt = f (de/dt, e, t)
>
> It is often possible to solve such ODE providing that we make some
> reasonable physical assumptions on the de/dt term appearing in f(). This
> comes with an acceptable decrease in accuracy. But modelling physical
> systems is always a matter of trade-off...
>
> Thus, a big physic black box containing large monolithic set of equations is
> not always needed.
>
> Regards
>
> J-C
>
>
> On Tue, Apr 21, 2009 at 1:32 PM, Peter Verswyvelen <bugfact at gmail.com>wrote:
>
>> Hey thanks for the Adam-Bashford tip, didn't know that one yet (although I
>> used similar techniques in the past, didn't know it had a name :-)
>>
>> Well, solving the ODE is usually the task of a dedicated physics engine.
>> But IMHO with FRP we try to reuse small building blocks so we get very
>> modular systems; a big physics black box seems to be against this
>> principle?
>>
>> On Tue, Apr 21, 2009 at 1:24 PM, Paul L <ninegua at gmail.com> wrote:
>>
>>> Adam-Bashford method can be easily implemented to replace Euler's. But
>>> to really get higher accuracy, one may need variable time steps and
>>> perhaps even back tracking, which is an interesting topic on its own.
>>> But my question is, is FRP really the right setting in which to
>>> explore a highly accurate ODE solver?
>>>
>>>
>>> On 4/21/09, Peter Verswyvelen <bugfact at gmail.com> wrote:
>>> > Well, the current FRP systems don't accurately solve this, since they
>>> just
>>> > use an Euler integrator, as do many games. As long as the time steps
>>> > are
>>> > tiny enough this usually works good enough. But I wouldn't use these
>>> FRPs
>>> > to
>>> > guide an expensive robot or spaceship at high precision :-)
>>> >
>>> >
>>> > On Tue, Apr 21, 2009 at 11:48 AM, jean-christophe mincke <
>>> > jeanchristophe.mincke at gmail.com> wrote:
>>> >
>>> >> Paul,
>>> >>
>>> >> Thank you for your reply.
>>> >>
>>> >> Integration is a tool to solve a some ODEs but ot all of them. Suppose
>>> >> all
>>> >> we have is a paper and a pencil and we need to symbolically solve:
>>> >>
>>> >>
>>> >>
>>> >> /
>>> >> t
>>> >> de(t)/dt = f(t)  -> the solution is given by e(t) = |      f(t) dt +
>>> >> e(t0)
>>> >>
>>> /
>>> >> t0
>>> >>
>>> >> de(t)/dt = f(e(t), t) -> A simple integral cannot solve it, we need to
>>> >> use
>>> >> the dedicated technique appropriate to this type of ODE.
>>> >>
>>> >>
>>> >> Thus, if the intention of the expression
>>> >>
>>> >>    e = integrate *something *
>>> >>
>>> >> is "I absolutely want to integrate *something* using some integration
>>> >> scheme", I am not convinced that this solution properly covers the
>>> second
>>> >> case above.
>>> >>
>>> >> However if its the meaning is "I want to solve the ODE : de(t)/dt =*
>>> >> something* " I would be pleased if the system should be clever enough
>>> to
>>> >> analyse the *something expression* and to apply or propose the most
>>> >> appropriate numerical method.
>>> >>
>>> >> Since the two kinds of ODEs require 2 specific methematical solutions,
>>> I
>>> >> do
>>> >> not find suprising that this fact is also reflected in a program.
>>> >>
>>> >> I have not the same experience as some poster/authors but I am curious
>>> >> about the way the current FRPs are able to accurately solve the most
>>> >> simple
>>> >> ODE:
>>> >>
>>> >>     de(t)/dt = e
>>> >>
>>> >> All I have seen/read seems to use the Euler method. I am really
>>> >> interested
>>> >> in knowing whether anybody has implemented a higher order method?
>>> >>
>>> >> Regards
>>> >>
>>> >> J-C
>>> >>
>>> >>
>>> >> On Tue, Apr 21, 2009 at 5:03 AM, Paul L <ninegua at gmail.com> wrote:
>>> >>
>>> >>> Trying to give different semantics to the same declarative definition
>>> >>> based
>>> >>> on whether it's recursively defined or not seems rather hack-ish,
>>> >>> although
>>> >>> I can understand what you are coming from from an implementation
>>> angle.
>>> >>>
>>> >>> Mathematically an integral operator has only one semantics regardless
>>> >>> of what's put in front of it or inside. If our implementation can't
>>> >>> match
>>> >>> this
>>> >>> simplicity, then we got a problem!
>>> >>>
>>> >>> The arrow FRP gets rid of the leak problem and maintains a single
>>> >>> definition
>>> >>> of integral by using a restricted form of recursion - the loop
>>> operator.
>>> >>> If you'd rather prefer having signals as first class objects, similar
>>> >>> technique
>>> >>> existed in synchronous languages [1], i.e., by using a special rec
>>> >>> primitive.
>>> >>>
>>> >>> Disclaimer: I was the co-author of the leak paper [2].
>>> >>>
>>> >>> [1] A co-iterative characterization of synchronous stream functions,
>>> >>> P
>>> >>> Caspi, M Pouzet.
>>> >>> [2] Plugging a space leak with an arrow, H. Liu, P. Hudak
>>> >>>
>>> >>> --
>>> >>> Regards,
>>> >>> Paul Liu
>>> >>>
>>> >>> Yale Haskell Group
>>> >>> http://www.haskell.org/yale
>>> >>>
>>> >>> On 4/20/09, jean-christophe mincke <jeanchristophe.mincke at gmail.com>
>>> >>> wrote:
>>> >>> > In a post in the *Elerea, another FRP library *thread*,* Peter
>>> >>> Verswyvelen
>>> >>> > wrote:
>>> >>> >
>>> >>> > *>I think it would be nice if we could make a "reactive benchmark"
>>> or
>>> >>> > something: some tiny examples that capture the essence of reactive
>>> >>> systems,
>>> >>> > and a way to compare each solution's >pros and cons.* *
>>> >>> > *
>>> >>> > *>For example the "plugging a space leak with an arrow" papers
>>> reduces
>>> >>> the
>>> >>> > recursive signal problem to
>>> >>> > *
>>> >>> > *
>>> >>> > *
>>> >>> > *>e = integral 1 e*
>>> >>> > *
>>> >>> > *
>>> >>> >  *>Maybe the Nlift problem is a good example for dynamic
>>> collections,
>>> >>> but I
>>> >>> > guess we'll need more examples.*
>>> >>> > *
>>> >>> > *
>>> >>> > *>The reason why I'm talking about examples and not semantics is
>>> >>> > because
>>> >>> the
>>> >>> > latter seems to be pretty hard to get right for FRP?*
>>> >>> >
>>> >>> > I would like to come back to this exemple. I am trying to write a
>>> >>> > small
>>> >>> FRP
>>> >>> > in F# (which is a strict language, a clone of Ocaml) and I also
>>> >>> > came
>>> >>> across
>>> >>> > space and/or time leak. But maybe not for the same reasons...
>>> >>> >
>>> >>> > Thinking about these problems and after some trials and errors, I
>>> came
>>> >>> to
>>> >>> > the following conclusions:
>>> >>> >
>>> >>> > I believe that writing the expression
>>> >>> >
>>> >>> >       e = integral 1 *something*
>>> >>> >
>>> >>> >       where e is a Behavior (thus depends on a continuous time).
>>> >>> >
>>> >>> > has really two different meanings.
>>> >>> >
>>> >>> > 1. if *something *is independent of e, what the above expression
>>> means
>>> >>> is
>>> >>> > the classical integration of a time dependent function between t0
>>> and
>>> >>> t1.
>>> >>> > Several numerical methods are available to compute this integral
>>> and,
>>> >>> > as
>>> >>> far
>>> >>> > as I know, they need to compute *something *at t0, t1 and,
>>> >>> > possibly,
>>> >>> > at
>>> >>> > intermediate times. In this case, *something *can be a Behavior.
>>> >>> >
>>> >>> > 2. If *something *depends directly or indirectly of e then we are
>>> >>> > faced
>>> >>> with
>>> >>> > a first order differential equation of the form:
>>> >>> >
>>> >>> >        de/dt = *something*(e,t)
>>> >>> >
>>> >>> >     where de/dt is the time derivative of e and  *something*(e,t)
>>> >>> indicates
>>> >>> > that *something* depends, without loss of generality, on both e and
>>> t.
>>> >>> >
>>> >>> > There exist specific methods to numerically solve differential
>>> >>> > equations
>>> >>> > between t0 and t1. Some of them only require the knowledge of e at
>>> t0
>>> >>> (the
>>> >>> > Euler method), some others needs  to compute *something *from
>>> >>> intermediate
>>> >>> > times (in [t0, t1[ ) *and *estimates of e at those intermediary
>>> times.
>>> >>> >
>>> >>> > 3. *something *depends (only) on one or more events that, in turns,
>>> >>> > are
>>> >>> > computed from e. This case seems to be the same as the first one
>>> where
>>> >>> the
>>> >>> > integrand can be decomposed into a before-event integrand and an
>>> >>> after-event
>>> >>> > integrand (if any event has been triggered). Both integrands being
>>> >>> > independent from e. But I have not completely investigated this
>>> >>> > case
>>> >>>  yet...
>>> >>> >
>>> >>> > Coming back to my FRP, which is based on residual behaviors, I use
>>> >>> > a
>>> >>> > specific solution for each case.
>>> >>> >
>>> >>> > Solution to case 1 causes no problem and is similar to what is done
>>> in
>>> >>> > classical FRP (Euler method, without recursively defined
>>> >>> > behaviors).
>>> >>> Once
>>> >>> > again as far as I know...
>>> >>> >
>>> >>> > The second case has two solutions:
>>> >>> > 1. the 'integrate' function is replaced by a function 'solve' which
>>> >>> > has
>>> >>> the
>>> >>> > following signature
>>> >>> >
>>> >>> >        solve :: a -> (Behavior a -> Behavior a) -> Behavior a
>>> >>> >
>>> >>> >       In fact,  *something*(e,t) is represented by an integrand
>>> >>> > function
>>> >>> > from behavior to behavior, this function is called by the
>>> >>> > integration           method. The integration method is then free
>>> >>> > to
>>> >>> pass
>>> >>> > estimates of e, as constant behaviors, to the integrand function.
>>> >>> >
>>> >>> >       The drawbacks of this solution are:
>>> >>> >       - To avoid space/time leaks, it cannot be done without side
>>> >>> effects
>>> >>> > (to be honest, I have not been able to  find a solution without
>>> >>> > assignement). However these side effects are not visible from
>>> outside
>>> >>> > of
>>> >>> the
>>> >>> > solve function. ..
>>> >>> >       - If behaviors are defined within the integrand function,
>>> >>> > they
>>> >>> > are
>>> >>> not
>>> >>> > accessible from outside of this integrand function.
>>> >>> >
>>> >>> > 2. Introduce constructions that looks like to signal functions.
>>> >>> >
>>> >>> >       solve :: a -> SF a a -> Behavior a
>>> >>> >
>>> >>> >    where a SF is able to react to events and may manage an internal
>>> >>> state.
>>> >>> >    This solution solves the two above problems but make the FRP a
>>> bit
>>> >>> more
>>> >>> > complex.
>>> >>> >
>>> >>> >
>>> >>> > Today, I tend to prefer the first solution, but what is important,
>>> in
>>> >>> > my
>>> >>> > opinion, is to recognize the fact that
>>> >>> >
>>> >>> >     e = integral 1 *something*
>>> >>> >
>>> >>> > really addresses two different problems (integration and solving of
>>> >>> > differential equations) and each problem should have their own
>>> >>> > solution.
>>> >>> >
>>> >>> > The consequences are :
>>> >>> >
>>> >>> >    1. There is no longer any need for my FRP to be able to define a
>>> >>> Behavior
>>> >>> >    recursively. That is a good news for this is quite tricky in F#.
>>> >>> >    Consequently, there is no need to introduce delays.
>>> >>> >    2. Higher order methods for solving of diff. equations can be
>>> used
>>> >>> (i.e.
>>> >>> >    Runge-Kutta). That is also good news for this was one of my main
>>> >>> > goal
>>> >>> in
>>> >>> >    doing the exercice of writing a FRP.
>>> >>> >
>>> >>> > Regards,
>>> >>> >
>>> >>> > J-C
>>> >>> >
>>> >>>
>>> >>
>>> >>
>>> >> _______________________________________________
>>> >> Haskell-Cafe mailing list
>>> >> Haskell-Cafe at haskell.org
>>> >> http://www.haskell.org/mailman/listinfo/haskell-cafe
>>> >>
>>> >>
>>> >
>>>
>>>
>>> --
>>> Regards,
>>> Paul Liu
>>>
>>> Yale Haskell Group
>>> http://www.haskell.org/yale
>>>
>>
>>
>

-- 
Sent from my mobile device

More information about the Haskell-Cafe mailing list