[Haskell-cafe] Re: FRP for game programming / artifical life simulation
Peter Verswyvelen wrote: Actually, I believe that many Yampa examples do separate the drawing from the update... The arrow provides the game data that *can* be rendered. If you provide interpolators for that game data, you can still achieve the same as is explained in fix your timesteps (in my own FRP experiments I have an update thread and a render thread). But the arrow implementation determines the dt at which the arrows ~ (Time - a) - (Time - b) are sampled, no? The end result of a Yampa arrows is a graphic, after all. But IMHO fix your timestep still misses an important detail, in that the delta-time that is measured is the duration of the previous frame, and it assumed that the next frame will take as long as the previous (who says that integrate from the article won't take longer than dt?). Now say you are updating at 100 FPS = 10ms, but the next frame actually takes longer, say 20ms. That actually means that you should have passed 20ms as the delta-time of the this frame, because the real time is ahead now! This is really noticeable as little jerky frame hick-up in the motion. In my first game (1987), I added an estimator to compute how long the delta-time of the next frame would be, which results in much smoother motion: you notice that the frame-sampling-rate drops, but you don't see a frame hick-up. I rarely see this in modern games, most PC and even console games suffer from frame hick-up (which could be defined as the real-time moving ahead of the game-time for a brief moment) I'm not sure I follow, could you elaborate on what exactly causes the frame hick-up? As far as I understand it, the approach of fix your time-step is that you have a physics simulation and a rendering engine. To ensure numerical stability, the physics are calculated with a fixed time step dt which can be larger than the rendering frame rate. In particular, one step of physics simulation should take less than dt real time, because otherwise you're screwed. The graphics engine just draws as fast as possible. To ensure smoothness, it interpolates slightly into the future. The FPS number measures the frequency of drawn graphics, not the rate of physics updates. There may be multiple physics steps per drawing when the latter is slow, or the other way round, when the latter is fast. Regards, Heinrich Apfelmus -- http://apfelmus.nfshost.com ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: FRP for game programming / artifical life simulation
On Sun, May 2, 2010 at 6:23 PM, Ben midfi...@gmail.com wrote: hello -- i'm putting the finishing touches on a cabal package based on what felipe gave, i've managed to make it an arrow transformer which is nice. i have a few issues though. 1) i know it is not possible to add class constraints on an existential type when declaring instances, but how do you get around that? for example, given the data type data Foo where Foo :: (Binary s) = s - Foo i would like to do something like instance Monoid s = Monoid Foo where this obviously doesn't make sense as it stands . the real-life example is that i want to derive ArrowZero and ArrowPlus instances for arrows lifted to StreamStateT where the underlying arrow already has ArrowZero and ArrowPlus instances. but to make sense of this i need to have a zero state element as well as a way to add state elements, e.g. a monoid instance on the state, which unfortunately is existential (as it stands.) You'd need to make container data types, since you're obscuring what information is held about the internal data type data FooMonoid m where FooMonoid :: (Binary s, Monoid s) = s - Foo data FooNum m where FooNum :: (Binary s, Num s) = s - Foo This of course, probably plays hell with your level of desired abstraction. 2) is it possible to add class constraints on unnamed type parameters when declaring instances? No, it isn't. There are hacks that get something like this, but they require you to basically rebuild the class in a 'restricted' form. Check out Ganesh's rmonad package on hackage for a general feel for the approach. 3) this is more of a style question, but how would you model a potentially infinite stream of data where the values are expensive to construct or are only sporadically available, in the arrow context? an example would be the stream of data from an experiment. my initial thought is to use the type [m a] for a monad m (as opposed to m [a].) i can walk the list and evaluate the monadic actions on-demand -- i can write functions analogous to your applyN function that work monadically, and this works great with the StreamState arrows. That seems like a reasonable starting point. applyMN :: Int - StreamState a b - [m a] - m ([b], (StreamState a b, [m a])) but it is a little weird mixing this with lifted arrows -- what is the signature there? applyLN :: Int - StreamStateT arr a b - [m a] . ?? It shouldn't be appreciably different, perhaps just: applyLN :: Arrow arr = Int - StreamStateT arr a b - [m a] - m ([b], StreamStateT arr a b, [m a]) -Edward Kmett ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: FRP for game programming / artifical life simulation
hello --
i'm putting the finishing touches on a cabal package based on what
felipe gave, i've managed to make it an arrow transformer which is
nice. i have a few issues though.
1) i know it is not possible to add class constraints on an
existential type when declaring instances, but how do you get around
that? for example, given the data type
data Foo where
Foo :: (Binary s) = s - Foo
i would like to do something like
instance Monoid s = Monoid Foo where
this obviously doesn't make sense as it stands . the real-life
example is that i want to derive ArrowZero and ArrowPlus instances for
arrows lifted to StreamStateT where the underlying arrow already has
ArrowZero and ArrowPlus instances. but to make sense of this i need
to have a zero state element as well as a way to add state elements,
e.g. a monoid instance on the state, which unfortunately is
existential (as it stands.)
2) is it possible to add class constraints on unnamed type parameters
when declaring instances?
for example, given the data type
data StreamState a b where
SS :: (Binary s) = s - ((a,s) - (b,s)) - StreamState a b
with instances of Arrow, ArrowLoop, etc, i'd like to create the instance
instance ArrowCircuit StreamState where
delay a = (SS a f)
where f (x, s) = (s, x)
where the delay arrow saves the first element of the stream into the
state. but this requires that the arrow has input (and output) which
is an instance of Binary. i can't put that constraint in the instance
head as the input and output types are not mentioned. i would prefer
not to add it as a constraint on the data type itself, as it would
restrict it's usefulness, and anyways it makes problems for the other
instances. so i'm forced to create a shadow class
class ArrowLoop a = ArrowBinaryCircuit a where
delay :: (Binary b) = b - a b b
and make an instance of that.
3) this is more of a style question, but how would you model a
potentially infinite stream of data where the values are expensive to
construct or are only sporadically available, in the arrow context?
an example would be the stream of data from an experiment.
my initial thought is to use the type [m a] for a monad m (as opposed
to m [a].) i can walk the list and evaluate the monadic actions
on-demand -- i can write functions analogous to your applyN function
that work monadically, and this works great with the StreamState
arrows.
applyMN :: Int - StreamState a b - [m a] - m ([b], (StreamState a b, [m a]))
but it is a little weird mixing this with lifted arrows -- what is the
signature there?
applyLN :: Int - StreamStateT arr a b - [m a] . ??
perhaps it is not a good idea to mix monads and arrows in this way?
best regards, b
On Thu, Apr 29, 2010 at 11:08 AM, Ben midfi...@gmail.com wrote:
Felipe --
Thanks! I tried using existential types but didn't get far -- the
GADT syntax makes them much clearer, thanks. In my defense this is my
first time working with a lot of these sexy type gadgets!
I think what you have written will work great for me. In particular I
think I can write down computations for lagged time series nicely
using a lagging arrow which saves the window as it's state, and laying
the real computations on top of that. So in particular you can
restart the computation without having to replay old data, it's nice.
I think I can also make an instance of ArrowCircuit.
A technical question: it seems like the instance of ArrowLoop is too
strict (this is something I've wondered about in Liu's paper too.)
Shouldn't it be
instance ArrowLoop SFAuto where
loop (SFAuto s f) = SFAuto s f'
where
f' (b, s1) = let (~(c, d), s2) = f ((b, d), s1)
in (c, s2)
or do I misunderstand lazy pattern matching?
Best, B
Date: Thu, 29 Apr 2010 00:09:22 -0300
From: Felipe Lessa felipe.le...@gmail.com
Subject: Re: [Haskell-cafe] Re: FRP for game programming / artifical
life simulation
To: haskell-cafe@haskell.org
Message-ID: 20100429030922.ga7...@kira.casa
Content-Type: text/plain; charset=us-ascii
On Wed, Apr 28, 2010 at 04:16:08PM -0700, Ben wrote:
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.
You may try encapsulating the state within an existential:
{-# LANGUAGE GADTs #-}
import Prelude hiding ((.), id)
import Control.Category
import Control.Arrow
data SFAuto a b where
SFAuto :: (Read
Re: [Haskell-cafe] Re: FRP for game programming / artifical life simulation
On Fri, Apr 30, 2010 at 3:37 AM, Daniel Fischer daniel.is.fisc...@web.de wrote: Am Donnerstag 29 April 2010 20:08:00 schrieb Ben: A technical question: it seems like the instance of ArrowLoop is too strict (this is something I've wondered about in Liu's paper too.) Shouldn't it be instance ArrowLoop SFAuto where loop (SFAuto s f) = SFAuto s f' where f' (b, s1) = let (~(c, d), s2) = f ((b, d), s1) in (c, s2) Let-bindings are already lazy, so the '~' makes no difference here. Apart from the readability, both are the same as where f' (b,s1) = let x = f ((b, snd $ fst x),s1) in (fst $ fst x, snd x) Ben's version is slightly lazier - even though the let binding is lazy, pattern matching is strict. so (let ((x,y).z) = (undefined, hello) in z) will exception out, but (let (~(x,y),z) = (undefined, hello) in z) will not. I don't know if you need that level of laziness, though. Antoine ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: FRP for game programming / artifical life simulation
Am Freitag 30 April 2010 17:23:19 schrieb Antoine Latter: On Fri, Apr 30, 2010 at 3:37 AM, Daniel Fischer daniel.is.fisc...@web.de wrote: Am Donnerstag 29 April 2010 20:08:00 schrieb Ben: A technical question: it seems like the instance of ArrowLoop is too strict (this is something I've wondered about in Liu's paper too.) Shouldn't it be instance ArrowLoop SFAuto where loop (SFAuto s f) = SFAuto s f' where f' (b, s1) = let (~(c, d), s2) = f ((b, d), s1) in (c, s2) Let-bindings are already lazy, so the '~' makes no difference here. Apart from the readability, both are the same as where f' (b,s1) = let x = f ((b, snd $ fst x),s1) in (fst $ fst x, snd x) Ben's version is slightly lazier - even though the let binding is lazy, pattern matching is strict. so (let ((x,y).z) = (undefined, hello) in z) will exception out, but (let (~(x,y),z) = (undefined, hello) in z) will not. I don't know if you need that level of laziness, though. Probably not. Although, you're right, if only s2 is ever looked at and not c, Ben's version can give a result where the library instance throws an exception. Was fooled by the use of c in the result. Antoine ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: FRP for game programming / artifical life simulation
FYI i got the lazy pattern match from Patterson's Programming with Arrows, so I'm assuming it makes a difference. (I'll work out a real example later.) B On Fri, Apr 30, 2010 at 8:45 AM, Daniel Fischer daniel.is.fisc...@web.de wrote: Am Freitag 30 April 2010 17:23:19 schrieb Antoine Latter: On Fri, Apr 30, 2010 at 3:37 AM, Daniel Fischer daniel.is.fisc...@web.de wrote: Am Donnerstag 29 April 2010 20:08:00 schrieb Ben: A technical question: it seems like the instance of ArrowLoop is too strict (this is something I've wondered about in Liu's paper too.) Shouldn't it be instance ArrowLoop SFAuto where loop (SFAuto s f) = SFAuto s f' where f' (b, s1) = let (~(c, d), s2) = f ((b, d), s1) in (c, s2) Let-bindings are already lazy, so the '~' makes no difference here. Apart from the readability, both are the same as where f' (b,s1) = let x = f ((b, snd $ fst x),s1) in (fst $ fst x, snd x) Ben's version is slightly lazier - even though the let binding is lazy, pattern matching is strict. so (let ((x,y).z) = (undefined, hello) in z) will exception out, but (let (~(x,y),z) = (undefined, hello) in z) will not. I don't know if you need that level of laziness, though. Probably not. Although, you're right, if only s2 is ever looked at and not c, Ben's version can give a result where the library instance throws an exception. Was fooled by the use of c in the result. Antoine ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: FRP for game programming / artifical life simulation
Chris Eidhof 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. Note that for web development, you could also store a log of client responses on the client side and replay that whenever a request is made to get some kind of persistent session. This is only suited for lightweight use cases, of course. I've implemented a small demonstration as part of the operational package, it's the WebSessionState.lhs on http://projects.haskell.org/operational/examples.html Regards, Heinrich Apfelmus -- http://apfelmus.nfshost.com ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: FRP for game programming / artifical life simulation
On Wed, 28 Apr 2010, Ben wrote:
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.
Ben,
Do you want this?
{-# LANGUAGE TypeFamilies, Rank2Types, GeneralizedNewtypeDeriving #-}
module Hairball
(Operator(..),Hairball,Value,alpha,beta,Operation,apply,buildHairball) where
import Control.Monad
import Control.Monad.State
class Operator o where
type Domain o :: *
operation :: o - Domain o - Domain o - (Domain o,o)
data Hairball o = Hairball {
hair_unique_supply :: Int,
hair_map :: [(Int,Int,Int,o)],
hair_output :: Int }
deriving (Read,Show)
data Value e = Value { address :: Int }
alpha :: Value e
alpha = Value 0
beta :: Value e
beta = Value 1
newtype Operation e o a = Operation { fromOperation :: State (Hairball o) a }
deriving (Monad,MonadFix)
apply :: o - Value e - Value e - Operation e o (Value e)
apply op v1 v2 =
do hair - Operation get
Operation $ put $ hair {
hair_unique_supply = succ $ hair_unique_supply hair,
hair_map = (hair_unique_supply hair,address v1,address v2,op)
: hair_map hair }
return $ Value $ hair_unique_supply hair
buildHairball :: (forall e. Operation e o (Value e)) - Hairball o
buildHairball o = hair { hair_output = address v, hair_map = reverse $ hair_map
hair }
where (v,hair) = runState (fromOperation o) (Hairball 2 [] $ error Hairball:
impossible: output value undefined)
instance Operator o = Operator (Hairball o) where
type Domain (Hairball o) = Domain o
operation hair v1 v2 = (fst $ results !! hair_output hair, hair { hair_map
= drop 2 $ map snd results })
where results = (v1,undefined):(v2,undefined):flip map (hair_map hair)
(\(i,s1,s2,o) -
let (r,o') = operation o (fst $ results !! s1) (fst
$ results !! s2)
in (r,(i,s1,s2,o')))
{-# LANGUAGE TypeFamilies, DoRec #-}
module Numeric () where
import Prelude hiding (subtract)
import Hairball
data Numeric n = Add | Subtract | Multiply | Delay n deriving (Read,Show)
instance (Num n) = Operator (Numeric n) where
type Domain (Numeric n) = n
operation Add x y = (x+y,Add)
operation Subtract x y = (x-y,Subtract)
operation Multiply x y = (x*y,Multiply)
operation (Delay x) x' _ = (x,Delay x')
type NumericOperation e n = Operation e (Numeric n)
type NumericHairball n = Hairball (Numeric n)
add :: Value e - Value e - NumericOperation e n (Value e)
add v1 v2 = apply Add v1 v2
subtract :: Value e - Value e - NumericOperation e n (Value e)
subtract v1 v2 = apply Subtract v1 v2
multiply :: Value e - Value e - NumericOperation e n (Value e)
multiply v1 v2 = apply Multiply v1 v2
delay :: n - Value e - NumericOperation e n (Value e)
delay initial_value v1 = apply (Delay initial_value) v1 alpha
integratorProgram :: String
integratorProgram = show $ buildHairball $
do rec prev_beta - delay 0 beta
d_beta - subtract beta prev_beta
add_alpha - multiply alpha d_beta
prev_sum - delay 0 sum
sum - add prev_sum add_alpha
return sum
runNumericProgram :: (Read n,Show n,Num n) = String - n - n - (n,String)
runNumericProgram program value time = (result,show hairball')
where hairball :: (Read n) = NumericHairball n
hairball = read program
(result,hairball') = operation hairball value time
numericStream :: (Read n,Show n,Num n) = [(n,n)] - (n,String) - (n,String)
numericStream [] (n,s) = (n,s)
numericStream ((a,t):ats) (_,s) = numericStream ats $ runNumericProgram s a t
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: FRP for game programming / artifical life simulation
Peter --
Thanks for the pointers. Have you seen
Uustalu T., Vene V. The Essence of Dataflow Programming
?
Can't say I understand it all but it is a compelling picture. I do
like the notion of distributive laws between monads and comonads.
B
On Wed, Apr 28, 2010 at 9:58 PM, Peter Gammie pete...@gmail.com wrote:
Ben,
On 29/04/2010, at 6:16 AM, Ben wrote:
[...]
newtype STAuto s a b = STAuto { unSTAuto : (a, s) - (b, s) }
As Felipe observes in detail, this can be made to work. He uses Read and Show
for serialisation, but clearly you can use whatever you like instead.
I just wanted to add that one can go to town with the approach: after you
understand Felipe's stuff, take a look at Caspi and Pouzet's coalgebraic
streams stuff. (I'd recommend looking at both the tech report and the
published paper, and there is some Haskell code too.)
BTW I was referring (off-list) to the original Arrows paper by John Hughes.
cheers
peter
--
http://peteg.org/
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: FRP for game programming / artifical life simulation
Felipe --
Thanks! I tried using existential types but didn't get far -- the
GADT syntax makes them much clearer, thanks. In my defense this is my
first time working with a lot of these sexy type gadgets!
I think what you have written will work great for me. In particular I
think I can write down computations for lagged time series nicely
using a lagging arrow which saves the window as it's state, and laying
the real computations on top of that. So in particular you can
restart the computation without having to replay old data, it's nice.
I think I can also make an instance of ArrowCircuit.
A technical question: it seems like the instance of ArrowLoop is too
strict (this is something I've wondered about in Liu's paper too.)
Shouldn't it be
instance ArrowLoop SFAuto where
loop (SFAuto s f) = SFAuto s f'
where
f' (b, s1) = let (~(c, d), s2) = f ((b, d), s1)
in (c, s2)
or do I misunderstand lazy pattern matching?
Best, B
Date: Thu, 29 Apr 2010 00:09:22 -0300
From: Felipe Lessa felipe.le...@gmail.com
Subject: Re: [Haskell-cafe] Re: FRP for game programming / artifical
lifesimulation
To: haskell-cafe@haskell.org
Message-ID: 20100429030922.ga7...@kira.casa
Content-Type: text/plain; charset=us-ascii
On Wed, Apr 28, 2010 at 04:16:08PM -0700, Ben wrote:
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.
You may try encapsulating the state within an existential:
{-# LANGUAGE GADTs #-}
import Prelude hiding ((.), id)
import Control.Category
import Control.Arrow
data SFAuto a b where
SFAuto :: (Read s, Show s) = s - ((a, s) - (b, s)) - SFAuto a b
instance Category SFAuto where
id = SFAuto () id
(SFAuto s f) . (SFAuto r g) = SFAuto (s, r) h
where h (x, (s, r)) = let (gx, r') = g (x, r)
(fgx, s') = f (gx, s)
in (fgx, (s', r'))
instance Arrow SFAuto where
arr f = SFAuto () (\(x, _) - (f x, ()))
first (SFAuto s f) = SFAuto s f'
where
f' ((x, y), s1) = let (fx, s2) = f (x, s1)
in ((fx, y), s2)
instance ArrowChoice SFAuto where
left (SFAuto s f) = SFAuto s f'
where
f' (Right x, s1) = (Right x, s1)
f' (Left x, s1) = first Left $ f (x, s1)
instance ArrowLoop SFAuto where
loop (SFAuto s f) = SFAuto s f'
where
f' (b, s1) = let ((c, d), s2) = f ((b, d), s1)
in (c, s2)
Now, if you want to serialize an (SFAuto a b), you may if you
know where the original arrow is. I mean, if you have
something :: SFAuto a b
something = ...
and you want to apply it to a huge list, you may
A1) 'applyN k', where k is adjustable.
A2) Save the results so far, the remaining input and the
current state (which is Showable and Readable in my
example, but could be an instance of Binary, for example).
A3) Go to A1.
If anything bad happens, to recover:
B1) Read results, input, and last state.
B2) 'changeState something stateThatWasRead'
B3) Go to A1.
Helper functions mentioned above:
applyN :: Int - SFAuto a b - [a] - ([b], (SFAuto a b, [a]))
applyN 0 sf xs = ([], (sf, xs))
applyN _ sf [] = ([], (sf, []))
applyN n (SFAuto s f) (x:xs) =
let (fx, s') = f (x,s)
in first (fx :) $ applyN (n-1) (SFAuto s' f) xs
changeState :: SFAuto a b - String - SFAuto a b
changeState (SFAuto _ f) str = SFAuto (read str) f
I don't have any idea if this is what you're looking for, but I
hope it helps :).
Cheers,
--
Felipe.
On Wed, Apr 28, 2010 at 9:58 PM, Peter Gammie pete...@gmail.com wrote:
Ben,
On 29/04/2010, at 6:16 AM, Ben wrote:
[...]
newtype STAuto s a b = STAuto { unSTAuto : (a, s) - (b, s) }
As Felipe observes in detail, this can be made to work. He uses Read and Show
for serialisation, but clearly you can use whatever you like instead.
I just wanted to add that one can go to town with the approach: after you
understand Felipe's stuff, take a look at Caspi and Pouzet's coalgebraic
streams stuff. (I'd recommend looking at both the tech report and the
published paper, and there is some Haskell code too.)
BTW I was referring (off-list) to the original Arrows paper by John Hughes.
cheers
peter
--
http://peteg.org/
___
Haskell-Cafe mailing list
Re: [Haskell-cafe] Re: FRP for game programming / artifical life simulation
Lane --
Thanks for the suggestion, I'll take a closer look shortly. At the
moment I have to confess to not exactly understanding what your code
is doing, it's a little hairy for me? Right now I'm going to focus
on what Felipe has given me, it fits in nicely with the arrow
framework, which I'm excited about.
Thanks all for your help. I'm sure I'll have more questions soon enough!
Best, B
On Thu, Apr 29, 2010 at 10:06 AM, Christopher Lane Hinson
l...@downstairspeople.org wrote:
On Wed, 28 Apr 2010, Ben wrote:
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.
Ben,
Do you want this?
{-# LANGUAGE TypeFamilies, Rank2Types, GeneralizedNewtypeDeriving #-}
module Hairball
(Operator(..),Hairball,Value,alpha,beta,Operation,apply,buildHairball) where
import Control.Monad
import Control.Monad.State
class Operator o where
type Domain o :: *
operation :: o - Domain o - Domain o - (Domain o,o)
data Hairball o = Hairball {
hair_unique_supply :: Int,
hair_map :: [(Int,Int,Int,o)],
hair_output :: Int }
deriving (Read,Show)
data Value e = Value { address :: Int }
alpha :: Value e
alpha = Value 0
beta :: Value e
beta = Value 1
newtype Operation e o a = Operation { fromOperation :: State (Hairball o) a
} deriving (Monad,MonadFix)
apply :: o - Value e - Value e - Operation e o (Value e)
apply op v1 v2 =
do hair - Operation get
Operation $ put $ hair {
hair_unique_supply = succ $ hair_unique_supply hair,
hair_map = (hair_unique_supply hair,address v1,address
v2,op) : hair_map hair }
return $ Value $ hair_unique_supply hair
buildHairball :: (forall e. Operation e o (Value e)) - Hairball o
buildHairball o = hair { hair_output = address v, hair_map = reverse $
hair_map hair }
where (v,hair) = runState (fromOperation o) (Hairball 2 [] $ error
Hairball: impossible: output value undefined)
instance Operator o = Operator (Hairball o) where
type Domain (Hairball o) = Domain o
operation hair v1 v2 = (fst $ results !! hair_output hair, hair {
hair_map = drop 2 $ map snd results })
where results = (v1,undefined):(v2,undefined):flip map (hair_map
hair) (\(i,s1,s2,o) -
let (r,o') = operation o (fst $ results !! s1)
(fst $ results !! s2)
in (r,(i,s1,s2,o')))
{-# LANGUAGE TypeFamilies, DoRec #-}
module Numeric () where
import Prelude hiding (subtract)
import Hairball
data Numeric n = Add | Subtract | Multiply | Delay n deriving (Read,Show)
instance (Num n) = Operator (Numeric n) where
type Domain (Numeric n) = n
operation Add x y = (x+y,Add)
operation Subtract x y = (x-y,Subtract)
operation Multiply x y = (x*y,Multiply)
operation (Delay x) x' _ = (x,Delay x')
type NumericOperation e n = Operation e (Numeric n)
type NumericHairball n = Hairball (Numeric n)
add :: Value e - Value e - NumericOperation e n (Value e)
add v1 v2 = apply Add v1 v2
subtract :: Value e - Value e - NumericOperation e n (Value e)
subtract v1 v2 = apply Subtract v1 v2
multiply :: Value e - Value e - NumericOperation e n (Value e)
multiply v1 v2 = apply Multiply v1 v2
delay :: n - Value e - NumericOperation e n (Value e)
delay initial_value v1 = apply (Delay initial_value) v1 alpha
integratorProgram :: String
integratorProgram = show $ buildHairball $
do rec prev_beta - delay 0 beta
d_beta - subtract beta prev_beta
add_alpha - multiply alpha d_beta
prev_sum - delay 0 sum
sum - add prev_sum add_alpha
return sum
runNumericProgram :: (Read n,Show n,Num n) = String - n - n - (n,String)
runNumericProgram program value time = (result,show hairball')
where hairball :: (Read n) = NumericHairball n
hairball = read program
(result,hairball') = operation hairball value time
numericStream :: (Read n,Show n,Num n) = [(n,n)] - (n,String) -
(n,String)
numericStream [] (n,s) = (n,s)
numericStream ((a,t):ats) (_,s) =
Re: [Haskell-cafe] Re: FRP for game programming / artifical life simulation
Am Donnerstag 29 April 2010 20:08:00 schrieb Ben: A technical question: it seems like the instance of ArrowLoop is too strict (this is something I've wondered about in Liu's paper too.) Shouldn't it be instance ArrowLoop SFAuto where loop (SFAuto s f) = SFAuto s f' where f' (b, s1) = let (~(c, d), s2) = f ((b, d), s1) in (c, s2) Let-bindings are already lazy, so the '~' makes no difference here. Apart from the readability, both are the same as where f' (b,s1) = let x = f ((b, snd $ fst x),s1) in (fst $ fst x, snd x) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: FRP for game programming / artifical life simulation
Ah, thanks! b On Thu, Apr 29, 2010 at 11:37 AM, Daniel Fischer daniel.is.fisc...@web.de wrote: Am Donnerstag 29 April 2010 20:08:00 schrieb Ben: A technical question: it seems like the instance of ArrowLoop is too strict (this is something I've wondered about in Liu's paper too.) Shouldn't it be instance ArrowLoop SFAuto where loop (SFAuto s f) = SFAuto s f' where f' (b, s1) = let (~(c, d), s2) = f ((b, d), s1) in (c, s2) Let-bindings are already lazy, so the '~' makes no difference here. Apart from the readability, both are the same as where f' (b,s1) = let x = f ((b, snd $ fst x),s1) in (fst $ fst x, snd x) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: FRP for game programming / artifical life simulation
Basically, this is the differential equation hairball I mentioned earlier. You can
define a set of Operators -- a modification of Mealy automata that accepts two inputs -- and any
mapping of inputs to outputs within the Operation monad.
The Operation monad uses an existentially quantified parameter for the same
purpose as the 'ST' monad, to prevent the introduction of foreign values.
Within the 'Hairball' type, (Int,Int,Int,o) means (destination address, first
source address, second source address, automaton). I don't actually use the
destination address because the list is built in indexable order anyway.
'alpha' and 'beta' correspond to the two inputs that every automaton receives.
The Hairball is itself a valid automaton.
This is roughly the system I imagine people should be used when I keep saying,
don't use FRP to implement something that isn't I/O. The whole thing is
trivially readable, writable, recursive, and actually a stream processor. On the
downside you need to specify an entire interpreted DSL just to use it.
In the 'Numeric' example, 'alpha' is the variable and 'beta' is time. Or it
least it integrates alpha with respect to beta.
That's all the non-obvious stuff that comes to mind for the moment.
Friendly,
--Lane
On Thu, 29 Apr 2010, Ben wrote:
Lane --
Thanks for the suggestion, I'll take a closer look shortly. At the
moment I have to confess to not exactly understanding what your code
is doing, it's a little hairy for me? Right now I'm going to focus
on what Felipe has given me, it fits in nicely with the arrow
framework, which I'm excited about.
Thanks all for your help. I'm sure I'll have more questions soon enough!
Best, B
On Thu, Apr 29, 2010 at 10:06 AM, Christopher Lane Hinson
l...@downstairspeople.org wrote:
On Wed, 28 Apr 2010, Ben wrote:
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.
Ben,
Do you want this?
{-# LANGUAGE TypeFamilies, Rank2Types, GeneralizedNewtypeDeriving #-}
module Hairball
(Operator(..),Hairball,Value,alpha,beta,Operation,apply,buildHairball) where
import Control.Monad
import Control.Monad.State
class Operator o where
type Domain o :: *
operation :: o - Domain o - Domain o - (Domain o,o)
data Hairball o = Hairball {
hair_unique_supply :: Int,
hair_map :: [(Int,Int,Int,o)],
hair_output :: Int }
deriving (Read,Show)
data Value e = Value { address :: Int }
alpha :: Value e
alpha = Value 0
beta :: Value e
beta = Value 1
newtype Operation e o a = Operation { fromOperation :: State (Hairball o) a
} deriving (Monad,MonadFix)
apply :: o - Value e - Value e - Operation e o (Value e)
apply op v1 v2 =
do hair - Operation get
Operation $ put $ hair {
hair_unique_supply = succ $ hair_unique_supply hair,
hair_map = (hair_unique_supply hair,address v1,address
v2,op) : hair_map hair }
return $ Value $ hair_unique_supply hair
buildHairball :: (forall e. Operation e o (Value e)) - Hairball o
buildHairball o = hair { hair_output = address v, hair_map = reverse $
hair_map hair }
where (v,hair) = runState (fromOperation o) (Hairball 2 [] $ error
Hairball: impossible: output value undefined)
instance Operator o = Operator (Hairball o) where
type Domain (Hairball o) = Domain o
operation hair v1 v2 = (fst $ results !! hair_output hair, hair {
hair_map = drop 2 $ map snd results })
where results = (v1,undefined):(v2,undefined):flip map (hair_map
hair) (\(i,s1,s2,o) -
let (r,o') = operation o (fst $ results !! s1)
(fst $ results !! s2)
in (r,(i,s1,s2,o')))
{-# LANGUAGE TypeFamilies, DoRec #-}
module Numeric () where
import Prelude hiding (subtract)
import Hairball
data Numeric n = Add | Subtract | Multiply | Delay n deriving (Read,Show)
instance (Num n) = Operator (Numeric n) where
type Domain (Numeric n) = n
operation Add x y = (x+y,Add)
operation Subtract x y = (x-y,Subtract)
operation Multiply x y = (x*y,Multiply)
operation (Delay x) x' _ = (x,Delay x')
Re: [Haskell-cafe] Re: FRP for game programming / artifical life simulation
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, Apr 27, 2010 at 9:28 PM, Christopher Lane Hinson l...@downstairspeople.org wrote: I'm not sure exactly what you want to do. It should certainly be easy to freeze an FRP program by lying about the amount of time that is passing and witholding all events. Do you want to save an FRP system instance to disk (generally unwise), or something else (what?). Friendly, --Lane 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? i've only been able to do this via explicit (or monadic) state-passing, e.g. imperative / piecemeal versus declarative / wholemeal, which seems against the spirit of FRP. b ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: FRP for game programming / artifical life simulation
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@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: FRP for game programming / artifical life simulation
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 l...@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@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: FRP for game programming / artifical life simulation
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 l...@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@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: FRP for game programming / artifical life simulation
On Apr 28, 2010, at 3:41 PM, Limestraël wrote: I think the problem with function serialization is that unlike languages which run over a virtual machine, bytecode generated by GHC is platform-specific (just as compilated C or C++) and therefore can run directly on top of the system, which is far faster but less portable. Is this true? I thought that ghc has separate machine code and byte-code modes, and inferred that the latter was platform-independent. Is the latter platform-specific because it is just a different way of organizing different ways of (unlinked) machine code, or because parts of the byte-code depend on things like the size of integers in the compilation machine that are platform-dependent? Also, it is worth noting that Clean supports serialization of values including closures. It's not entirely clear to me how they do this, but looks like some combination of seeing whether a referenced routine is already in the current executable, then seeing whether it is in a nearby library, and then finally just-in-type compiling the serialized platform-independent bytecode into native code. Cheers, Greg ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: FRP for game programming / artifical life simulation
As a side note, it's interesting that C# doesn't allow serialization of closures (anonymous delegates). The compiler-generated name assigned to an anonymous delegate can be different after each re-compilation. This is also really annoying in C#/.NET, since one must explicitly add a named method if serialization is needed. So I wander how Clean solves this. I mean, consider data MyData = MD (Int-Int) myFunc x = x+1 myState1 = MyData myFunc myState2 = MyData (\x - x+1) I can imagine that serializing myState1 is not too difficult, since it should be possible to lookup the name of the compiled function myFunc. However, what about serializing myState2? The lambda function has no name, and it is not obvious to me how to give it a name that is unique enough to survive a couple of iterations of source code modifications. On Wed, Apr 28, 2010 at 9:56 PM, Gregory Crosswhite gcr...@phys.washington.edu wrote: On Apr 28, 2010, at 3:41 PM, Limestraël wrote: I think the problem with function serialization is that unlike languages which run over a virtual machine, bytecode generated by GHC is platform-specific (just as compilated C or C++) and therefore can run directly on top of the system, which is far faster but less portable. Is this true? I thought that ghc has separate machine code and byte-code modes, and inferred that the latter was platform-independent. Is the latter platform-specific because it is just a different way of organizing different ways of (unlinked) machine code, or because parts of the byte-code depend on things like the size of integers in the compilation machine that are platform-dependent? Also, it is worth noting that Clean supports serialization of values including closures. It's not entirely clear to me how they do this, but looks like some combination of seeing whether a referenced routine is already in the current executable, then seeing whether it is in a nearby library, and then finally just-in-type compiling the serialized platform-independent bytecode into native code. Cheers, Greg ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: FRP for game programming / artifical life simulation
I think y'all are talking past each other, a little bit. There are two ways to serialize a function: 1) Serialize the bytecode for the function. 2) Serialize a persistant reference to a function that resides inside the executable. Personally, I think that either strategy is dubious. If you really need this, I would recommend building a DSL to support your specific needs. When I was working in Java I trusted the default serializer about as far as I could physically throw it, and IIRC my associates at the time had the same instinct. Functions in general can contain references to any data, including objects such as MVar's who's behavior is actually determined by unreachable entities. There's no amount of type system magic that can hold off monsters like _|_ or things like lazy bytestrings that are finite but never intended to be fully resident in memory. Or do we intend to serialize unevaluated thunks? Friendly, --Lane On Wed, Apr 28, 2010 at 6:42 PM, Christopher Lane Hinson l...@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@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe On Wed, 28 Apr 2010, Peter Verswyvelen wrote: As a side note, it's interesting that C# doesn't allow serialization of closures (anonymous delegates). The compiler-generated name assigned to an anonymous delegate can be different after each re-compilation. This is also really annoying in C#/.NET, since one must explicitly add a named method if serialization is needed. So I wander how Clean solves this. I mean, consider data MyData = MD (Int-Int) myFunc x = x+1 myState1 = MyData myFunc myState2 = MyData (\x - x+1) I can imagine that serializing myState1 is not too difficult, since it should be possible to lookup the name of the compiled function myFunc. However, what about serializing myState2? The lambda function has no name, and it is not obvious to me how to give it a name that is unique enough to survive a couple of iterations of source code modifications. On Wed, Apr 28, 2010 at 9:56 PM, Gregory Crosswhite gcr...@phys.washington.edu wrote: On Apr 28, 2010, at 3:41 PM, Limestra?l wrote: I think the problem with function serialization is that unlike languages which run over a virtual machine, bytecode generated by GHC is platform-specific (just as compilated C or C++) and therefore can run directly on top of the system, which is far faster but less portable. Is this true? I thought that ghc has separate machine code and byte-code modes, and inferred that the latter was platform-independent. Is the latter platform-specific because it is just a different way of organizing different ways of (unlinked) machine code, or because parts of the byte-code depend on things like the size of integers in the compilation machine that are platform-dependent? Also, it is worth noting that Clean supports serialization of values including closures. It's not entirely clear to me how they do this, but looks like some combination of seeing whether a
Re: [Haskell-cafe] Re: FRP for game programming / artifical life simulation
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 ch...@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
l...@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
Re: [Haskell-cafe] Re: FRP for game programming / artifical life simulation
On Wed, Apr 28, 2010 at 04:16:08PM -0700, Ben wrote:
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.
You may try encapsulating the state within an existential:
{-# LANGUAGE GADTs #-}
import Prelude hiding ((.), id)
import Control.Category
import Control.Arrow
data SFAuto a b where
SFAuto :: (Read s, Show s) = s - ((a, s) - (b, s)) - SFAuto a b
instance Category SFAuto where
id = SFAuto () id
(SFAuto s f) . (SFAuto r g) = SFAuto (s, r) h
where h (x, (s, r)) = let (gx, r') = g (x, r)
(fgx, s') = f (gx, s)
in (fgx, (s', r'))
instance Arrow SFAuto where
arr f = SFAuto () (\(x, _) - (f x, ()))
first (SFAuto s f) = SFAuto s f'
where
f' ((x, y), s1) = let (fx, s2) = f (x, s1)
in ((fx, y), s2)
instance ArrowChoice SFAuto where
left (SFAuto s f) = SFAuto s f'
where
f' (Right x, s1) = (Right x, s1)
f' (Left x, s1) = first Left $ f (x, s1)
instance ArrowLoop SFAuto where
loop (SFAuto s f) = SFAuto s f'
where
f' (b, s1) = let ((c, d), s2) = f ((b, d), s1)
in (c, s2)
Now, if you want to serialize an (SFAuto a b), you may if you
know where the original arrow is. I mean, if you have
something :: SFAuto a b
something = ...
and you want to apply it to a huge list, you may
A1) 'applyN k', where k is adjustable.
A2) Save the results so far, the remaining input and the
current state (which is Showable and Readable in my
example, but could be an instance of Binary, for example).
A3) Go to A1.
If anything bad happens, to recover:
B1) Read results, input, and last state.
B2) 'changeState something stateThatWasRead'
B3) Go to A1.
Helper functions mentioned above:
applyN :: Int - SFAuto a b - [a] - ([b], (SFAuto a b, [a]))
applyN 0 sf xs = ([], (sf, xs))
applyN _ sf [] = ([], (sf, []))
applyN n (SFAuto s f) (x:xs) =
let (fx, s') = f (x,s)
in first (fx :) $ applyN (n-1) (SFAuto s' f) xs
changeState :: SFAuto a b - String - SFAuto a b
changeState (SFAuto _ f) str = SFAuto (read str) f
I don't have any idea if this is what you're looking for, but I
hope it helps :).
Cheers,
--
Felipe.
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: FRP for game programming / artifical life simulation
Ben,
On 29/04/2010, at 6:16 AM, Ben wrote:
[...]
newtype STAuto s a b = STAuto { unSTAuto : (a, s) - (b, s) }
As Felipe observes in detail, this can be made to work. He uses Read and Show
for serialisation, but clearly you can use whatever you like instead.
I just wanted to add that one can go to town with the approach: after you
understand Felipe's stuff, take a look at Caspi and Pouzet's coalgebraic
streams stuff. (I'd recommend looking at both the tech report and the published
paper, and there is some Haskell code too.)
BTW I was referring (off-list) to the original Arrows paper by John Hughes.
cheers
peter
--
http://peteg.org/
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: FRP for game programming / artifical life simulation
slightly off topic, but how does one handle pausing / saving / restarting in the FRP framework, especially the arrowized version? i've only been able to do this via explicit (or monadic) state-passing, e.g. imperative / piecemeal versus declarative / wholemeal, which seems against the spirit of FRP. b ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: FRP for game programming / artifical life simulation
I'm not sure exactly what you want to do. It should certainly be easy to freeze an FRP program by lying about the amount of time that is passing and witholding all events. Do you want to save an FRP system instance to disk (generally unwise), or something else (what?). Friendly, --Lane 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? i've only been able to do this via explicit (or monadic) state-passing, e.g. imperative / piecemeal versus declarative / wholemeal, which seems against the spirit of FRP. b ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: FRP for game programming / artifical life simulation
2010/4/25 Patai Gergely patai_gerg...@fastmail.fm: (in my own FRP experiments I have an update thread and a render thread). I wonder how to nicely deal with state that requires communication with the outer world, even though it is functional at heart. For instance, if you want to change a vertex buffer or a texture or whatever during the update, how do you organise your code? Do you maintain separate pure and impure state information blocks? I don't have a vertex buffers or texture in my update loop. These are low level details, left to the render loop. Indeed I maintained a pure information block in the update. If you really wanted to have low-level access in the update loop, I wouldn't know how to do that, although keeping two copies could work. Now my experiments were really simple 2D games, so not really state of the art. Deciding between push and pull according to profiling results is a nice idea. :) It might be too expensive to do it adaptively during runtime (the overhead might easily distort the results and thus render them invalid), but treating it as just a flag could give us an interesting architecture to play with. Yes, I see it more in the line of profile based optimization, where a compiler performs static optimization based on a previous profile. I kind of abandoned the FRP thing because Haskell just feels a bit too complicated/abstract for me. It might also be that for the average person to learn Haskell really well, one needs a mentor. I would love to follow courses about it actually :) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: FRP for game programming / artifical life simulation
Luke Palmer wrote:
The workhorse of our game has so far been generalized differentials.
While not entirely rigorous, they have provided a very nice framework
in which to express our thoughts and designs, and are very good at
highly dynamic situations which appear in games. For example, with
arrows it is painful to maintain a list of moving actors such that can
be added and removed. With differentials this is quite natural.
Interesting! I've experimented with writing a game in Haskell recently,
albeit in a rather traditional imperative style, and I have a few
thoughts on what your style does and does not accomplish.
A differential is implemented as a function that takes a timestep and
returns an update function. Don't expose the D constructor; step is
okay to expose, it's kind of a generalized linear approximation.
newtype D a = D { step :: Double - a - a }
instance Monoid (D a) where
mempty = D (const id)
mappend da db = D (\dt - step da dt . step db dt)
Given a differential for a component of a value, we can construct a
differential for that value.
accessor :: Acc.T s a - D a - D s
accessor acc da = D (Acc.modify acc . step da)
product :: D a - D b - D (a, b)
product da db = D (\dt (x,y) - (step da dt x, step db dt y))
comonad :: (Comonad w) = (w a - D a) - D (w a)
comonad f = D (\dt - let h w = step (f w) dt (extract w) in extend h)
I appears to me that your differentials are just functional references
/ state updates (a - a) , the interesting conceptual interpretation
notwithstanding. The telltale sign is that your main logic is given by
dGameState , which is, in essence, just a function that updates the
global game state:
dGameState :: Input - D GameState
dGameState = ... -- built out of simpler Ds of its components
On one hand, this is disappointing because it's all too close to the
imperative style, but on the other hand, the idea of treating state
changes as *first class values* gives rise to powerful combinators like
comonad and clearly exceeds what imperative languages usually offer.
In a sense, it is quite ironic that imperative languages don't abstract
over what they are best at doing, namely updating state.
The interpretation as differentials is, unfortunately, not fundamental.
The only part where it would come to fruition, namely the definition of
continuous functions
The arrow we are using is implemented in terms of differentials:
data Continuous a b = forall s. Continuous s (s - a - (b, D s))
mainGame = proc input - do
gameState - integral initialGameState - dGameState input
returnA - drawGameState gameState
only appears as driver code at the very end and does not have any
impact; you can just as well implement your game loop in the traditional
imperative fashion:
mainGame = loop initialGameState
where
loop s = do
i - getInput
s' - dGameState i dt s
drawGameState s'
loop s'
In fact, it is preferable to do so because physics simulations usually
require a fixed time step dt which is slightly tricky to synchronize
to the clock on the wall, see also
Glenn Fiedler. Fix your timestep!
http://gafferongames.com/game-physics/fix-your-timestep/
Arrows don't help with that, in fact, it is difficult to do this with
arrow style FRP! That's because FRP tends to mingle game state updates
and drawing, but you have to separate them if you want decent interpolation.
Thus, it is no accident that your main loop factorizes into updating and
drawing, and that the arrows pretty much disappear from your code, Luke.
So, in my opinion, this style is a traditional imperative approach,
though with a proper and powerful abstraction for state updates.
But since we're also on a quest to find the functional game programming
nirvana, can we do better? I have no answer, but for starters, I think
I can explicitly describe two qualities that FRP has and that are not
available in Luke's approach:
1) In FRP, there is no global *type* GameState that stores the whole
game state. Rather, the game state is implicit in the collection of
active computations. This is also why state updating and drawing is
woven together in FRP, which is good syntactically, but hard to
disentangle for interpolation.
2) In FRP, all dependencies that may influence the evolution of a value
in time are made explicit in its definition. In contrast, a state update
can change *any* value later on; the only protection against unwanted
change are the combinators. For instance,
product :: D a - D b - D (a,b)
guarantees that the D b argument cannot change the a component of
the pair (a,b) .
Maybe the nirvana is closer if we could somehow incorporate one of these.
Note that these are purely syntactic qualities. In fact, I am
convinced that it's not a good idea to focus on the semantics of FRP,
the key focus should be on the syntax, on the way of expressing a given
thought in computer words.
Re: [Haskell-cafe] Re: FRP for game programming / artifical life simulation
1) In FRP, there is no global *type* GameState that stores the whole game state. Rather, the game state is implicit in the collection of active computations. This is also why state updating and drawing is woven together in FRP, which is good syntactically, but hard to disentangle for interpolation. I disagree somewhat with this. FRP should be thought of like the IO monad, out of which everything that can be lifted, should be, especially the GameState. I like to imagine that the FRP's job is to observe the GameState and reenact changes therein. Some changes take a little while to act out, and the FRP element that is doing the action can signal that it isn't ready for the next transition. Or, if no changes occur, the actors can stand around doing idle animations. Friendly, --Lane ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: FRP for game programming / artifical life simulation
Actually, I believe that many Yampa examples do separate the drawing from the update... The arrow provides the game data that *can* be rendered. If you provide interpolators for that game data, you can still achieve the same as is explained in fix your timesteps (in my own FRP experiments I have an update thread and a render thread). But IMHO fix your timestep still misses an important detail, in that the delta-time that is measured is the duration of the previous frame, and it assumed that the next frame will take as long as the previous (who says that integrate from the article won't take longer than dt?). Now say you are updating at 100 FPS = 10ms, but the next frame actually takes longer, say 20ms. That actually means that you should have passed 20ms as the delta-time of the this frame, because the real time is ahead now! This is really noticeable as little jerky frame hick-up in the motion. In my first game (1987), I added an estimator to compute how long the delta-time of the next frame would be, which results in much smoother motion: you notice that the frame-sampling-rate drops, but you don't see a frame hick-up. I rarely see this in modern games, most PC and even console games suffer from frame hick-up (which could be defined as the real-time moving ahead of the game-time for a brief moment) Regarding FRP, I like to look at this as a kind of a data flow system (a network of signal transformers, or just nodes). However, it is not clear if you want to pull or push such a network: if side effects are not present, there should be no difference in the game state if you push or pull it, but one can be far more optimal than the other. Of example, nodes connected to an analog joystick would most likely benefit from a pull approach, since the joystick always moves a little. But nodes connected to a timer that changes once each second clearly should benefit from a push approach. Although sometimes a static change frequency could help to determine wether to push or pull, I believe this can only be determined with profiling. So in a sense, push or pull should be some kind of attribute... Okay, a bit off topic :) On Sun, Apr 25, 2010 at 5:09 PM, Christopher Lane Hinson l...@downstairspeople.org wrote: 1) In FRP, there is no global *type* GameState that stores the whole game state. Rather, the game state is implicit in the collection of active computations. This is also why state updating and drawing is woven together in FRP, which is good syntactically, but hard to disentangle for interpolation. I disagree somewhat with this. FRP should be thought of like the IO monad, out of which everything that can be lifted, should be, especially the GameState. I like to imagine that the FRP's job is to observe the GameState and reenact changes therein. Some changes take a little while to act out, and the FRP element that is doing the action can signal that it isn't ready for the next transition. Or, if no changes occur, the actors can stand around doing idle animations. Friendly, --Lane ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: FRP for game programming / artifical life simulation
(in my own FRP experiments I have an update thread and a render thread). I wonder how to nicely deal with state that requires communication with the outer world, even though it is functional at heart. For instance, if you want to change a vertex buffer or a texture or whatever during the update, how do you organise your code? Do you maintain separate pure and impure state information blocks? However, it is not clear if you want to pull or push such a network From what I've seen so far, I think you really need both at the same time. Pull for continuous signals and push for events. The tricky part is that events can be derived from signals (cf. Fran's predicate events), and you really don't want the signals depending on these events to be reevaluated even when there are no occurrences. The best you can do with pull is to explicitly keep the previous output when there's no incoming event. However, if you fmap over this output, the function will be evaluated in every step regardless of the lack of change, since functions are not memoised. I believe this is a problem Grapefruit aims to solve with its notion of segmented signals [1]. Deciding between push and pull according to profiling results is a nice idea. :) It might be too expensive to do it adaptively during runtime (the overhead might easily distort the results and thus render them invalid), but treating it as just a flag could give us an interesting architecture to play with. Gergely [1] http://hackage.haskell.org/packages/archive/grapefruit-frp/0.0.0.0/doc/html/FRP-Grapefruit-Signal-Segmented.html -- http://www.fastmail.fm - A fast, anti-spam email service. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
