Dreams of FRP

Here is a post about how I see programming a game in Functional Reactive Programming. It’s oriented toward people who already get the basics of FRP. It is based on the original paper, rather than the newer AFRP paper. The “circuitry” model doesn’t seem to fit into my head as well as behaviors and events do, but maybe I’ll see how arrows play into it once I explore the subject a bit more.

This is a dreamy post; I have not actually done any FRP yet (partly because I can’t get the AFRP library to build), but I have read and understood enough to do it in my head. I’m going to write code in the way I would like to be able to write it, and then sometimes correct it to how I would actually have to write it given lifting and all that bullcrap.

A little refresher: an Event is a just a value that “occurs” at some time (possibly in the “future”). Event is a monad, with its join operation defined by the the occurrence of the value (another event) that the event returns. a Behavior is a value that depends on time, for example the current position of the mouse or the action that draws the current frame. Behavior is a comonad, with its cojoin defined by projecting the time into its argument. I think Event and Behavior are nicely dual, but I haven’t really explored it.

The paper gives an example of a bouncing ball, which actually disgusted me for a minute. The “modular” 1-D bounce function’s workings were not obvious or clear, and it wasn’t quite so modular as they claimed. For example, it incorporated gravity. What the heck does gravity have to do with bouncing?

Upon further thought, I discovered that that is no limitation of FRP. Instead it was just a poor implementation of bouncing balls. Let’s try again.

What is the essence of bouncing? Impulses… which are strangely absent from their implementation. In a traditional model I would implement an impluse simple as a force divided by the delta time. But FRP explicitly abstracts over time deltas, so that won’t work. What is an impluse then? I’d encode it using an event containing a momentum delta vector.

In order to have events affect behavior, we’ll define a new type, an event stream:

```  newtype EventStream a = EventStream (Event (a, EventStream a))
```

It’s just an event which returns a value and a new event stream, containing all subsequent events. Then we can model the sequence of wall-bounces using an EventStream Double (remember we’re in 1-D) or some such.

To turn event streams back into behaviors, we want a function analogous to scanl for lists:

```  scanES :: (a -> Time -> b -> a) -> a -> EventStream b -> Behavior a
scanES f init (EventStream e) =
lift0 init `untilB` e +=> \ t (x,es) ->
scanES f (f init t x) es
```

It takes on the value of init until the first event happens, when it passes the value of the event and the current state to the folding function and takes on the result, etc. I have an inkling that this is not quite as general as it could be, but it’ll do for now.

Given this format, we can have the bounce function return a stream of impulses:

```  bounce :: (Double,Double)     -- boundaries
-> Double              -- radius
-> Behavior Double     -- position
-> Behavior Double     -- velocity
-> Time                -- initial time
-> EventStream Double  -- return impulses
bounce (minBound,maxBound) radius pos vel t0 =
stream t0
where
-- just a helper function so we don't have to repeat all those args
stream :: Time -> EventStream Double
stream t = EventStream (nextImpluse +=> \t' imp -> (imp,stream t'))

collideRight, collideLeft, collide :: Event ()
collideRight = predicate (pos + radius >= maxBound) t0
collideLeft  = predicate (pos - radius <= minBound) t0
collide      = collideRight .|. collideLeft

nextImpulse :: Event Double
nextImpulse = snapshot collide vel ==> \((),v) -> -2*v
```

Which I find quite a bit nicer than their version. To get to the bouncing balls:

```  integrateES :: (Num a) => EventStream a -> Behavior a
integrateES = scanES (\cur t v -> cur + v) 0

ballPos :: Behavior Vec2
ballPos = pos
where
pos = integrate vel
vel = (1,1) + integrateES imp + integrate accel
accel = (0,-0.5)  -- gravity
imp = (impx, impy)
impx = bounce (-10,10) 1 (fst pos) (fst vel) 0
impy = bounce (-10,10) 1 (snd pos) (snd vel) 0
```

And this is really where FRP is beautiful. This felt incredibly declarative to write: the position is just the integral of velocity, the velocity is just (1,1) + the integral of all impulses + the integral of acceleration, etc.

Sadly, this is not valid Haskell. I left out all the necessary lifting in both of these snippets. I’m hoping that the arrow notation will be able to alleviate some of the tireless lifting. For comparison, here’s a correct version of ballPos:

```  ballPos :: Behavior Vec2
ballPos = pos
where
pos = integrate vel
vel = liftW2 (\imp' accel' -> (1,1) + imp' + accel')
(integrateES imp) (integrate accel)
accel = lift0 (0,-0.5)
imp = liftW2 (,) impx impy
impx = bounce (-10,10) 1 (liftW fst pos) (liftW fst vel) 0
impy = bounce (-10,10) 1 (liftW snd pos) (liftW snd vel) 0
```

Which is quite a bit muckier. Still, the concepts are clean and elegant. And I didn’t pull very much at all out of thin air, everything I used was firmly grounded in the paper.

UPDATE: For those of you without programs that can grok `.ps.gz`, here is a PDF.