FRP in Yampa: Part 1

I’ve been writing some Haskell lately, for the first time in a year, and it’s a total blast! In particular, school is out for the holidays, so I had some spare time, and thought I’d waste it by making a video game. In Haskell.

It’s always more fun to make video games with other people, but the few people I pitched it to all had the same response—“I don’t know how to do that.” So it seemed like a good opportunity to dust off the old blog and write about how to make a video game in Haskell, using arrowized FRP.

What the hell does that mean? Get ready to FIND OUT!

FRP?🔗

FRP is short for functional reactive programming, originally invented by Conal Elliott. The library we’ll be using today is called Yampa, which is certainly inspired by Elliott’s work, but my guess is it’s insufficiently true to the core idea for him to be excited about it.

Nevertheless, even an imperfect implementation of the idea is still orders of magnitude for making real-time applications than doing everything by hand. And to this extent, Yampa is an excellent library.

So what exactly is FRP? The core idea is that we want to talk about functions that are continuous in time, which give rise to extremely useful combinators-over-time. Real-time programs written as FRP are much easier to reason about, and significantly more expressive than you’d manage otherwise.

A Point of Contrast🔗

It’s informative to compare what writing a video game looks like under an imperative style. The idea is that you have your game loop (a fancy name for “infinite loop”) running:

void main() {
  setup();

  while (true) {
    float delta_time = waitForNextFrame();
    updateGame(delta_time);
    renderFrame();
  }
}

and this is kind of fine and manages to get the job done. But it’s inelegant for a few reasons. The biggest problem is that we are not actually modeling time here; we’re just running the game discretely, and time happens as a side effect of things changing. There’s this delta_time variable which counts how long it’s been since you last updated the game, which is to say it corresponds to “how much work you need to do this frame.”

What goes wrong is when updateGame or renderFrame takes too long to run; in that case, you might get spikes in how long it’s been since you last updated. Procedurally-written games compensate by interpolating everything a little further on the next frame, which gives the player the perception that they’re actually experiencing time.

But things can break down. If your last frame took too long, you need to simulate physics a little more this frame. In practice this usually means that you integrate your velocity a little more than usual—which really means your positions will teleport a little further than usual. This is a common bug in games, where it’s often easy to clip through obstacles when the frame-rate is too low.

The other problem with modeling your time only incidentally is that it makes it really annoying to actually do anything. For example, when you read from the controller you will only get whether the buttons are down or up, but you won’t get whether the button was just pressed this frame. If you want to know that you’ll have to compute it yourself:

bool last_a_button = false;

void updateGame(float delta_time) {
  controller ctrls = getControllerState();

  if (ctrls.a_button && !last_a_button) {
    // handle a press
  }

  last_a_button = ctrls.a_button;
}

It’s tedious, but it gets the job done. Another common pain point is when you want to do something five seconds in the future:

float timer;

void updateGame(float delta_time) {
  timer -= delta_time;

  if (getWantsToStartTimer()) {
    timer = 5.0;
  }

  // ...

  if (timer <= 0) {
    // handle timer finishing
  }
}

Again, nothing you can’t tackle, but in aggregate, this all becomes very weighty. Not being able to model time explicitly is a real pain, and everywhere you go you need to simulate it by diddling state changes.

Signal Functions🔗

If you’ve ever written a video game, it probably looked a lot like the examples from the previous section. That’s the sort of thing we’d like to abstract over, and work at a much higher level of detail than.

Here comes FRP to the rescue.

The core building block in Yampa is the “signal function”, written as SF i o. You can think of this as a transformer of signals of i into signals of o, where a signal is a function Time -> a. Unwrapping all of this, an SF i o is a function (Time -> i) -> (Time -> o).

That’s everything you need to know about what SFs are. I don’t know how they’re implemented, and I don’t need to, because the abstraction doesn’t leak. Being a haskell programmer, you’re probably looking at SF i o and thinking “that thing is clearly a Functor/Applicative/Monad.” Two out of three—it’s a functor and an applicative, but not a monad. We’ll come back to this momentarily.

The trick to working in FRP is to think of continuous streams of values over time. Thus, we can think about the player’s controller as an SF:

controller :: SF () Controller

which is to say, a continuous stream of Controller values. By marking the input side of the SF as a unit, it means we don’t need to provide anything in order to get this value, which makes sense since the controller state is obviously at the very periphery of our program.

Since SF is a functor, we can get the state of the A button by fmapping it:

aState :: SF () Bool
aState = fmap a_button controller

which isn’t very surprising. But what’s more interesting are the SF-operating primitives that Yampa gives us. For example, there’s delay:

delay :: Time -> a -> SF a a

which delays a signal by the given time, using the a parameter as the value for the initial value of the stream. Thus, we can get the value of the A button two seconds ago via:

aStateTwoSecondsAgo :: SF () Bool
aStateTwoSecondsAgo = aState >>> delay 2 False

where (>>>) :: SF a b -> SF b c -> SF a c is composition of SFs, analogous to function composition.

Already we can see the benefit of this approach. While it’s not clear exactly why we might want to look at the state of the controller two seconds ago, it’s also non-obvious how you’d go about implementing such a thing procedurally with a game loop.

One last signal function we might be interested for the time being is integral, which allows us to compute the integral of a stream:

integral :: Fractional a => SF a a

Events🔗

SFs are transformers of continuous signals, but often we want to talk about discrete moments in time. For this, we’ve got the Event type, which is isomorphic to Maybe:

data Event a
  = Event a
  | NoEvent

The interpretation you should have for an Event is that it’s a discrete piece of data arriving at a specific moment in time. In our earlier discussion of things you want to do in games, we’ve already seen two examples of events: when a timer expires, and when the player presses the A button. Under Yampa, the first is particularly easy to code up, by way of the after combinator:

after :: Time -> b -> SF a (Event b)

If we want to trigger a timer after 5 seconds, it’s just after 5 () :: SF a (Event ()), and we can listen to the output of this stream for an Event () value in order to know when the timer has elapsed.

Similarly, when we’re interested in the player pressing a button, what we’re really interested is in the edges of their button signal. We can get this functionality by way of the edge signal function:

edge :: SF Bool (Event ())

which generates an event whenever the input boolean goes from false to true.

Of course, just being able to generate events isn’t very useful if we don’t have any means of subsequently eliminating them. A simple means of eliminating events is via hold:

hold :: a -> SF (Event a) a

The hold function takes a stream of events, and holds onto the most recent value it received.

Making a Game of Snake🔗

We’ve already seen enough of FRP in order to make most of the old classic, Snake. In Snake, you are a snake who slithers around in a square, with a constant velocity, continuing in the direction you’re going until the player asks you to turn.

Begin with a Controller, and an SF to read it:

data Controller = Controller
  { ctrl_up    :: Bool
  , ctrl_down  :: Bool
  , ctrl_left  :: Bool
  , ctrl_right :: Bool
  }

controller :: SF () Controller
controller = ...

We can then write a little helper function to determine when a button has been pressed—tagging it with a particular value of our choice:

onPress :: (Controller -> Bool) -> a -> SF () (Event a)
onPress field a = fmap (fmap (const a)) $ fmap field controller >>> edge

Next, we can sum up an onPress for each direction on the controller, mapping them into direction vectors:

arrowEvents :: Num a => SF () (Event (V2 a))
arrowEvents =
  (\u d l r -> asum [u, d, l r])
    <$> onPress ctrl_up    (V2 0 (-1))
    <*> onPress ctrl_down  (V2 0 1)
    <*> onPress ctrl_left  (V2 (-1) 0)
    <*> onPress ctrl_right (V2 1    0)

Above, the use of asum allows us to combine these four events into one, meaning that if the player presses two directions at exactly the same moment, we will prefer up over down, and down over left, etc.

By holding onto the most recent arrow event, we can get the current direction our snake is facing:

snakeDirection :: SF () (V2 Float)
snakeDirection = arrowEvents >>> hold (V2 0 1)

which we can then integrate in order to have the snake move around:

snakePosition :: SF () (V2 Float)
snakePosition = snakeDirection >>> integral

Not too shabby at all! This particular snake will move at a rate of 1 unit per second, but we could make him faster by scaling up snakeDirection before taking its integral.

Wrapping Up🔗

Hopefully I’ve given you a taste of how FRP can radically simplify the implementation of real-time applications. Tomorrow we’ll look into arrowized FRP, and get a sense of how to build bigger, more interesting programs.