FRP: What’s the big deal?

I really have to get to bed, but I just did a little test and am so excited I need to say something:

AFRP sucks. The incredible amount of trouble I had to go through just to implement extremely simple physics with a dynamic number of balls within FRP (none of that cheating by factoring the physics elsewhere; while that may be a good thing to do, it’s a point for the power of FRP if you can do it directly in FRP) indicates that AFRP is absolutely not suitable for games. The short reason is that is chokes when faced with dynamic behavior.

On the other hand, classical comonadic FRP is great; it supports such dynamism without a sweat. That is, if it weren’t for the spacetime leak that results when you have value recursion like:

  e = integral 1 e

Which is horrible because that is the form of every differential simulation (read: games).

Because of that leak, I tried three different approaches with arrows, with varying flexibility trade-offs, but they were all bad for making games. I wanted to go back to comonadic FRP so badly, but the spacetime leak loomed in the darkness, condemning my programs to progressively slow down (and eat up more and more memory) as they ran.

As refresher, the data structure for comonadic FRP is:

  type DTime = Double
  data Signal a = Signal a (DTime -> Signal a)

And today something hit me, something so simple that it made me reconsider my sanity:

  -- 'runSignal step sig' produces the infinite list of
  -- values every 'step' seconds from 'sig'
  runSignal :: Double -> Signal a -> [a]
  runSignal = ...

  -- listSignal is the inverse of runSignal, constructing
  -- a signal from a list
  listSignal :: Double -> [a] -> Signal a
  listSignal = ...

  buffer :: Double -> Signal a -> Signal a
  buffer step = listSignal step . runSignal step

The buffer function just samples a signal at regular intervals, caching the results internally in a list. The implementation of these three functions combined is 13 simple lines; the concepts are easy too. Again, foreheadslap! Why? This is why:

  e = buffer 0.05 $ integral 1 e

No more spacetime leak! The nth timestep of e is found in linear time and constant space. To generalize the technique, just put a buffer between any value recursion to fix the leak. No, it’s not a perfect solution, but it’s a good compromise. You still get perfect granularity in your event handling (to me, an essential property), and you get to use comonadic FRP.

I’m so excited!

About these ads

4 thoughts on “FRP: What’s the big deal?

  1. Awesome! I know of at least one other independent intuition that comonadic FRP is the way to go, as opposed to the arrowized alternative. Please keep blogging on this, I’m sure I’m not the only one who finds this fascinating. (Btw, what happened to your planet haskell feed?)

  2. fixCF looks like it is just loop from AFRP. One thing I briefly considered was to expose both the SF arrows and first-class Signals, which moves the burden of avoiding space leaks onto the user of the library. Not great, but better than being forced to have a leak :-). That idea died along with most of the other pure implementations once I realized (and due to Conal’s recent work on DataDriven and Reactive, it seems he has come to the same realization) that signals really need to depend on absolute time, not just time since binding. That is, if you really want signals to be first class, they should keep varying even when they’re not being used (sitting inside a list somewhere). That’s the informal explanation. A more detailed blog entry coming soon.

    I had a planet haskell feed?

  3. You mention that AFRP sucks when it comes to dynamism. Did the arrow notation not help at all?

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s