Fregl: an introduction to FRP

I’ve been mentioning quite a bit about my latest FRP implementation. First things first: You can find it here. The implementation is called “Fregl”, for “Functional Reactive Game Library”, roughly. But I thought I would take a moment to describe it and some of the directions I plan on taking it. The first section introduces FRP at a high level, and my intent is to write it so that someone unfamiliar with Haskell can at least get an idea of what it is about. The second section is much more technical, and goes into some of the implementation details. (Hmm, don’t have time right now to write the second section. It’s a post for another day.)

The Surface: Signals and Events

There are two major types of objects that make up the core of Fregl: Signals and Events. People familiar with FRP will feel right at home with these. A Signal is a value that varies over time, like any ordinary variable in a typical imperative language (they are defined and used very differently, though). An Event is just something that happens at some time, and then returns a value when it does happen. Both Signal and Event are type constructors, kind of like templates in C++; they carry with them an additional type. For example: Signal Int is a value of type Int that varies over time; Event Vec2 is an event that, when it happens, returns a 2D vector.

There are some core events, for example: waitClickPos, the position of the next mouse click; waitTimestep, occurs when a simulation timestep happens and returns the amount of time since the last one. There are a handful of others, but for simplicity we’ll only use mouseClick which we’ll define like this:

  mouseClick :: Event Vec2                        -- type signature (optional)
  mouseClick = waitClickPos ButtonLeft MouseDown  -- implementation

I should stress that Events are first-class objects just like any other (unlike events in C#!). There is nothing stopping a function from taking some arguments and returning an Event. In fact, waitClickPos does exactly that! It takes a button and a state and returns an Event representing when that mouse button enters that state.

It turns out that most of the logic in an FRP program comes in the form of custom events. Events are composable: you make big, complex events out of smaller ones. Here are a few examples. Non-Haskell programmers, I encourage you to try to understand this code too, it is pretty easy (and I’ve intentionally written it in a more imperative style).

  -- wait for two mouse clicks and return the position of the second one
  secondClick = mouseClick >> mouseClick

  -- wait for two mouse clicks and return the vector from the first to the second
  clickVector = do {
      pos1 <- mouseClick;
      pos2 <- mouseClick;
      return (pos2 ^-^ pos1);  -- ^-^ is vector subtraction
  }

  -- wait for a given amount of time
  waitTime time = do {
    if time <= 0 then
        return ()
    else do {
        dt <- waitTimestep;
        waitTime (time - dt);
    }
  }

  -- if there's a mouse click in the next 10 seconds, return its position,
  -- otherwise return (0,0)    (oh, how unhaskellish)
  clickInTenSeconds = eitherEvent waitTenSeconds mouseClick
      where
      waitTenSeconds = waitTime 10 >> return (0,0)

I hope by the last example you can start to see the power of such composability.

So far we have seen how to define your own Events, but Events don’t do anything. They just define what it means for something to happen, not what to do when they actually do happen. So we have to introduce an “event handler”, right?

Wrong. We need only two primitives, neither of which I would consider an event handler:

  -- return an event which happens instantly, returning the current value in the signal
  readSig :: Signal a -> Event a

  -- The returned signal takes on the value of the first signal until the event happens
  -- (and returns a signal), and takes on the value of the second signal from that point
  -- on.
  untilEvent :: Signal a -> Event (Signal a) -> Event (Signal a)

Examples of using these are coming soon. First, and this the essential difference from classical game programming, note that there is no “signal assignment”. To determine what the value of a signal at a certain time should be, you look at the signal’s definition, and that tells you everything. The only things which can affect its value are the things it depends on, not the things that depend on it. This is one of the sorts of “referential transparency” that Fregl obeys. There will be another–read on.

Okay, so how do you actually use these things? Here is one example to get the feel for it. Again, non-Haskellers should be able to understand this code given a little thought. Oh, I should mention the backquote syntax: If I write foo `baz` bar, that just turns the function baz into an infix operator; i.e. it is equivalent to calling baz with the two arguments: baz foo bar.

  -- Takes an 'initial value' and returns an event which occurs instantly, returning
  -- a signal which counts the amount of time since the event occurred plus the
  -- initial value.
  time :: Double -> Event (Signal Double)
  time init = pure init `untilEvent` do {  -- "pure" constructs a constant signal
      dt <- waitTimestep;
      time (init + dt);
  }

Let’s take a moment to study that code. It says that the returned signal takes on the constant value ‘init’ [“pure init”] until [“untilEvent”] the next timestep [“waitTimestep”], at which point it behaves like time (init + dt). It is a recursive definition. (Nit for the leet: the last line should be time $! init + dt lest we should make a huge addition thunk.)

It returns the signal inside an Event which occurs instantly. This is very common of signals. You can think of Events not just as things that happen, but things that have a perception of time. That is, our time function here needs to know what the “current time” is for its definition, which is why it must be returned inside an Event. Don’t worry if this part doesn’t make sense yet.

Now we get to step way outside the realm of conventional programming and define some really powerful stuff. It turns out that it is possible to define the following function:

  -- Returns an event which happens instantly, and returns a signal which represents
  -- the integral of the given signal over time, starting from the time the event
  -- was fired.
  integral :: Signal Vec2 -> Event (Signal Vec2)

(The actual implementation works on more general types than just Vec2)

Using this, we can define the following program (very similar to examples/follow):

  -- we use the following predefined signal:
  mousePos :: Signal Vec2

  -- defines the position of a ball that follows the mouse around
  follower = mdo {
      let acceleration = mousePos ^-^ position ;
      velocity <- integral acceleration ;
      position <- integral velocity ;
      return position ;
  }

If nothing in the article has given you chills yet, this should. In the definition of follower, first we define the acceleration to be the target position (the mouse) minus the current position. What do you mean the current position, where is that defined? Look two lines down, there it is, defined as the integral of velocity! This is a circular definition of position, essentially asking the library to solve the equation position = ∫∫ (mousePos – position).

Then, using this definition, we can easily turn this into a program which draws a ball at that position using the (very limited so far) drawing primitives:

  main = runGameSDL $ do {
    ballPos <- follower
    return (Draw.translate <$> ballPos <*> pure Draw.circle)
  }

And there’s the whole program.

This is just the beginning, the bare bones of FRP. It’s all embedded inside idiomatic Haskell, so we can use Haskell’s top-notch abstraction abilities to write out programs. To give you a flavor, here’s the signature of a neat function:

  -- Takes an event as an argument.  When this event fires, it should return a
  -- a signal (representing perhaps the state of an actor) and another event
  -- (representing the death condition for this actor).  So the returned signal
  -- will be in the output list between the time the "creation event" fires
  -- and the time the "destruction event" fires.
  actorList :: Event (Signal a, Event ()) -> Event (Signal [a])

This function implements the idea of a list of active actors, something I’ve written over and over in C++, whose implementation is always spread out across my program (iterate through it once in the draw() routine, once in the step() routine, once in the events() routine). A less general variation of it appears in examples/shmup, and it only takes about 9 lines to implement, once and for all.

That’s it for the layman’s introduction. One of my major programming-evangelistic goals is to convince people that OO is not the best way to solve every problem. I hope that this introduction has shown you that there are some non-OO techniques which can be immensely powerful that the game community has not even begun to explore.

Here’s a teaser for next time. It turns out, not by any conscious plan of my own, just by coincidence, that Fregl’s implementation of these semantics admits a very nice parallel implementation. In theory, it scales linearly with the number of processors automatically (i.e. the game programmer need not put in any extra work), which is a big deal if I do say so myself. I’ll be performing a practical test on one of CU’s 8-processor machines in a few days.

About these ads

5 thoughts on “Fregl: an introduction to FRP

  1. Just a brief query only tangentially related to your post. Are you using GHC 6.8.*? If so, then where are you getting your SDL binding from? The one on Hackage doesn’t work with GHC 6.8.* (see “build failure” comment on the Hackage page for libSDL).

  2. I am using 6.8.1. If I’m not mistaken, I’m using the SDL binding in the Haskell portage overlay in gentoo. It looks like it’s getting its tarball from hackage, version 0.4.0. Hope this helps.

  3. Awesome! I’m reading this over and going through your code at the same time. It’s taking some time for it all to sink in. Hope to provide more useful feedback then — thanks for sharing!

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