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