[Haskell-cafe] Re: FRP for game programming / artifical life simulation

[Ben]

thanks for the comments, i'll try to respond to them all.  but to
start off with, let me mention that my ultimate goal is to have a way
of writing down causal and robust (restartable) computations which
happen on infinite streams of data "in a nice way" -- by which i mean
the declarative / whole-meal style ala Bird.  loosely, these are
functions [a] -> [b] on infinite lists; the causal constraint just
means that the output at time (index) t only depends on the inputs for
times (indices) <= t.

the catch is the robust bit.  by robust, i mean i need to be able to
suspend the computation, and restart it where it left off (the data
might be only sporadically or unreliably available, the computation
needs to be able to survive machine reboots.)  unfortunately the
obvious way (to me) of writing down such suspendible computations is
to use explicit state-machines, e.g. to reify function computation as
data, and save that.  this is unfortunately very piece-meal and
imperative.

so i tried to turn state-machine computations on streams into an
arrow.  as an exercise for myself i tried to implement instances of
ArrowChoice, ArrowLoop, and ArrowCircuit for other various versions of
"stream arrows."  i was successful with automatons / mealy machines

newtype Auto a b = Auto { unAuto : a -> (b, Auto a b) }

functions on infinite lists (Data.Stream)

newtype InfSF a b = ISF { unISF : Stream a -> Stream b }

and length-preserving functions on finite lists

newtype SF a b = SF { unSF : [a] -> [b] }

this was promising, if elementary (these are all well-known.)  but
none of these are particularly interruptible, at least in GHC -- i
can't save a mealy machine, and the list versions are not particularly
causal.  so i tried state machines of a sort

newtype STAuto s a b = STAuto { unSTAuto : (a, s) -> (b, s) }

where the interruptibility would come from being able to save out the
state s.  i was not successful, unfortunately, in this level of
generality.  the fully-polymorphic state doesn't work, because one
needs to be able to compose arrows, which means composing state, so
like Hughes (see below) one needs some way of nesting states inside
one another.  also, to implement delay in ArrowCircuit, one needs to
be able to store in the state s something of type a.  this is a
dependency i was not able to model right.

perhaps i have entirely the wrong approach -- if anyone can think of a
way of writing such a robust program in a declarative style, i would
love to know it!  of interest are the coalgebraic / comonadic
approaches, and the CCA stuff of liu et al.

Peter G : i have looked at the original CGI Arrow, it's a nice paper.
i don't think i understand all the subtleties, but my impression is
that he has a less polymorphic state type, and i don't know if he
addressed ArrowCircuit.  also he was unable to get it to work,
entirely, at least in that paper -- there were some type issues iirc.

Chris H : in my state-machine setup, saving the "state" of pure
functions is not exactly necessary -- as stream arrows, pure functions
lift to stateless gadgets, e.g. lift = map.  on the other hand, if i
was able to save functions / closures, or whole state of the program,
it would certainly suffice (i could use mealy machines or the
continuation monad), but is probably more than i need.

Peter V, Chris E : the CGI Arrow paper that Peter G mentioned may be
of interest to you.

the rest of you haskellers -- sorry, this is like the tenth time i've
posed this question, in one form or another!  i keep on feeling like
i've made a little progress, but then....

Best, Ben

On Wed, Apr 28, 2010 at 11:49 AM, Chris Eidhof <chris at eidhof.nl> wrote:
> I agree. This would be an extremely useful feature, not only for game development, but also for web development. We often use continuations as a way to add state to the web, but this fails for two reasons: whenever the server restarts, or when we scale to multiple machines.
>
> However, I think it is not easy to do this: traversing the heap should be relatively simple, however: what if a function implementation changes?
>
> An interesting approach is taken by the Clean guys: they use dynamics, which can store a function, a type representation and the heap to disk. See also this old thread: http://www.mail-archive.com/haskell-cafe@haskell.org/msg34054.html
>
> -chris
>
> On 28 apr 2010, at 19:50, Peter Verswyvelen wrote:
>
>> Interesting topic. I find it a bit annoying that Haskell doesn't
>> provide support to save functions. I understand this is problematic,
>> but it would be very nice if the Haskell runtime provided a way to
>> serialize (part of) the heap, making sure that pointers to compiled
>> functions get resolved correctly.
>>
>>
>>
>> On Wed, Apr 28, 2010 at 6:42 PM, Christopher Lane Hinson
>> <lane at downstairspeople.org> wrote:
>>>
>>> On Wed, 28 Apr 2010, Ben wrote:
>>>
>>>> I want to save the state of the system to disk, I want to be able to
>>>> play the game, pick a point to stop, freeze it and turn off the
>>>> computer, and then come back later and resume.  Why is that unwise?
>>>> What are the alternatives?
>>>>
>>>> B
>>>>
>>>>> On Tue, 27 Apr 2010, Ben wrote:
>>>>>
>>>>>> slightly off topic, but how does one handle pausing / saving /
>>>>>> restarting in the FRP framework, especially the arrowized version?
>>>
>>> If we're about Arrow FRP, remember that the arrow typeclass includes a
>>> function, 'arr', that admits any function as a parameter, and these are in
>>> general impossible to serialize to disk. Since Arrow FRP ends up roughly in
>>> a form of: FRP a b c = a b (c, FRP a b c), an Arrow instance is actually the
>>> state of the system.  There are a few tactics that would get us around this
>>> limitation, but they are rather severe.   You could render 'arr' useless in
>>> several ways, or you could save all the input to a system and replay it.
>>>
>>> But I would argue that even if you wanted to do this, "saving an FRP system"
>>> is, to me, like "saving a system in the IO monad," (which, there are tactics
>>> that would let you do this, too).  It's probablematic in part because the
>>> FRP system probably has active hooks into the user interface, such as
>>> windows and other widgits that it owns, and possibly other devices (such as
>>> physical rocket engines).  Even if the FRP system is completely pure and can
>>> be referenced by a single pointer, it is easily and rightfully aware of
>>> specific details of the hardware it is embedded in.
>>>
>>> So it seems to me that what we actually want, to do complex simulations with
>>> persistance, is not an FRP system that interacts with the outside world, but
>>> a "self-contained, self-interacting, differential equation hairball."  Such
>>> a system would be very cool, but I think that the numerical algorithms
>>> needed exceed what an FRP system should try to provide.
>>>
>>> Friendly,
>>> --Lane
>>> _______________________________________________
>>> Haskell-Cafe mailing list
>>> Haskell-Cafe at haskell.org
>>> http://www.haskell.org/mailman/listinfo/haskell-cafe
>>>
>> _______________________________________________
>> Haskell-Cafe mailing list
>> Haskell-Cafe at haskell.org
>> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
>