Monthly Archives: November 2007

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
      -- 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
    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
    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.

More posts about FRP coming soon!


Here’s a sketch of a short screenplay I’d like to write.

Depict a stereotypical “successful businessman” finishing a day’s work (closing a deal or something), driving home in his nice car, sitting in front of his top-notch TV set and beginning to play a video game. Repeat a few times, with some, but not too much, variety. Playing somewhat, again not too much so, digital-sounding music.

Pan out to find that this depiction is in fact on a top-notch home theater, a video game being played by an identical stereotype, but a different actor. He expresses boredom or frustration somehow, that he wants his character in the game to do something different. Frustrated, he turns off the console and walks outside.

Depict him climbing trees, hopping across a river on stones, other fun things in organic environments. Playing fluid, organic music. Close with him jumping on a goomba.
image of goomba


I’m Back

A few months ago I thought I had lost my laptop’s audio interface, and there was a gig in 4 days. So I hastily ordered a new one and had it fedexed. It arrived the day of the gig (whew). About a day later, I found my old one hiding (essentially in plain sight).

I have not sold either. So I am out $350 or so. But the side effect is that I can keep my old one set up in my room by the piano, so I can just plop my laptop on top of the piano, plug in the card, and start recording. Therefore, I’ll be resuming my daily improvs. Excellent.

I notice that whenever I try a jazzy improv, it comes out clumsy, loud, soulless. So I’ll be doing two improvs per day: one in a jazz style and one in a classical style, in order to improve my jazz skillz.

Without further ado, here are the two for today.

Alien Nation

I’m giving a guest lecture on Haskell to the Principles of Programming Languages class at CU tomorrow. That’s pretty exciting.

This is a personal entry, by the way. I found myself censoring my posts for a while to just technical issues in order to build a base of readers. But then this blog completely lost its therapeutic properties, so I’m going to censor my censorship a bit.

My roommates Jude and Namaste were sitting in Namaste’s room checking out gametap, and I was sitting there watching them play some games for a while. I wasn’t really interested in playing those games—I’ve found myself less interested in games lately—I just wanted to sit there and be around people.

That proving pretty uninteresting because there isn’t that much idle socialization in games, I decided to go for a walk. I bundled up and began walking through the dark to a nearby park. Halfway there, I just stopped on the sidewalk and stood there, noticing myself feeling incredibly lonely. Loneliness… is not an intense emotion. It’s subtle, and you just feel kind of empty and tired. It doesn’t make you cry, it just sits there, omnipresent, reducing your enjoyment of life.

I started walking again and started talking to myself, which is one of the strongest ways I have of working through issues. Except this isn’t an issue which was very well suited to my self-talking therapy. All my life I’ve learned to speak using the meta model, precisely, mathematically, nailing down in a sentence exactly what I’m talking about. And emotions aren’t like that. They’re vague constructions, floating around in various forms, not necessarily caused by any particular phenomenon, not really solvable with a simple proof.

“I’m lonely.” That was productive.

I reached the park and found the exact middle. I knelt down right there and curled up into a little ball. I tried to concentrate the emotion, but it didn’t really work. I feigned a few meditative tactics, obviously to no avail (you can’t feign meditation and have it work!). And by work I mean have the way I’m feeling change at all, better or worse. Like I said, loneliness just sits there in the corner of the room with its notebook, quietly judging you as you become more and more desperate. If it interacted with you any more then that, it would serve to make you less lonely, which would defeat its purpose.

Who are my friends? Previously I just wanted a girl, but that might have just been the gut response to my relationships with my friends weakening. I have two groups of friends, gamers and musicians. I’m having trouble connecting with my gamer friends because I’m gradually losing interest in games, for whatever reason. I’ve never really built friendships with the musicians I know, because we get together and play music and go home, essentially. There’s a musical connection there, which is strong and interesting, but it lacks some of the more human elements. One exception is Nolan, who I have a pretty good friendship with. But I don’t see him much.

Nolan was really really good at bringing his band together as a family. I could learn a few things from him.

Everyone else just brushes me off when my life isn’t going smoothly. I probably would do the same to them. It’s hard to get out of my own head; if I’m working on a programming project or a composition, I don’t want to be bothered with the details of somebody else’s life. You need a really good connection with somebody to be able to talk openly about your problems. It’s been a few years since I’ve cared about someone enough to stop anything I’m doing in order to really listen to what they had to say. That’s pretty sad.

Just as I was arriving home, I started to feel something like a very energized anger. I ran as fast as I could for the fast 50 yards home or so, walked in the house, and with energy pounding at my hands and through my body, found I had nothing to do with it. If nobody was home I would scream at the top of my lungs… but I’m too self-conscious for that.

Much as I want to be unrestricted and act on my impulses, when I know that the worst consequences possible are a little embarrassment, I can’t bring myself to do that. Each time I suppress my impulses, the next time the impulse will be stronger and so will the impulse to suppress it. It’s like going insane by holding on too tightly to my sanity.

I’m just lost. I don’t know where to go next.