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