Ha! I can’t even get Events right

No wonder FRP has been so difficult. In going back to basics, forgetting about behaviors and just doing Events, I realize that my belief that Events are “the easy part” has been flawed. Neither of the semantics I’ve had in mind are both implementable and appropriate. Or rather, they both are, but neither of them can do as much as I thought they could.

I will leave my previously preferred semantics of Event a = Waiter a = Time -> (Time,a), for annoying practical reasons (it also violates intuition about what an event is).

The reactive semantics of Event, Event a = [(Time,a)], is no good because there is always a least occurrence. This violates relativity and intuition (relativity being an intuitive concept I’ve developed regarding the lack of a “global start time”).

So I’m left with Event a = Set (Time, a), or Set (Time, Set a) to handle multiple occurrences at the same time. I am actually inclined to resort to the former, and require a Monoid instance on a to merge. Anyway: what’s the problem with this one? No temporal operations are allowed on it, because it must be observant. Consider mouseClick :: Event Point, the event of mouse clicks. There may be many mouse clicks before the program started, before we were listening for them. If we then sequence mouseClick with some other event, then we have to know about those earlier mouse clicks to detect it. Also consider everySecond :: Time -> Event (), which occurs every second before and after the given time. There are infinitely many occurrences of this event, and so there are infinitely many simultaneous occurrences of everySecond t >> everySecond t. We can not possibly handle all of them.

I know I didn’t motivate that very well, but hopefully you get the idea. If an Event is a set of occurrences, then we must be able to see all of them, including ones that depend on events that happened when we weren’t watching.

I conclude that Event is not a Monad or even Applicative, and all we have is the following interface:

    data Event a
    instance Functor Event
    instance (Monoid a) => Monoid (Event a)
    filter :: (a -> Bool) -> Event a -> Event a
    withTime :: Event a -> Event (Time,a)

Actually, as far as primitives go, I prefer this to filter:

    partition :: Event (Either a b) -> (Event a, Event b)

But they are definable in terms of each other, so it really doesn’t matter except for efficiency concerns. Look how partition is dual to zip. Isn’t that cool?

But in exchange for meaning and implementability, we have given up much of Event’s usefulness. Note that we can no longer even construct the event of double clicks. That makes sense to me, though, because what if the first of the two occurred before we were watching?

I can think of a bunch of ways to get back bits and pieces of the usefulness — EventParsers and the like — and I’m still experimenting with which will be the most effective.

About these ads

3 thoughts on “Ha! I can’t even get Events right

  1. Consider mouseClick :: Event Point

    I think you’re in trouble already here, unless you have a pretty complex (and therefore poorly compositional) semantics for Event. It’s a bit like saying that argc :: Integer. The semantics of Integer includes integers and bottom, and the meaning of argc is neither. Instead the meaning of argc is a function of some other information (perhaps rolled up in the semantically inscrutable wad we call “IO”). Similarly, a particular mouseClick event you have in mind is also a function of other information. That other information is what distinguishes your mouse from mine and yesterday’s Luke from today’s Luke.

    Reactive, like Fran before it, keeps event semantics simple & composable by using signatures like mouseClick :: User -> Event Point, for suitable User types. When you make the source of user input explicit in this way, I think the problem you worried about above vanishes. You can see all of the mouse clicks from the particular user you’re given, because that user by construction contains only recent, present & future info.

    If you tried rolling a particular notion of user information into the the Event type, the result would lose simplicity, generality, and composability.

  2. My semantics for Event a is strictly a set of Time × a (a bit stricter: if there is some occurrence in [x,∞), there must be a least occurrence). I’m very careful with it, I don’t even allow multiple occurrences at the same time. When I said mouseClick :: Event Point, I was speaking in some particular scope, not global scope. E.g. we have:

    someProg :: Event Point -> Behavior Drawing
    someProg mouseClick = …

    In fact, the locality here is very strong, and I’m thinking of strengthening it more with region types (meaning a particular “reference frame” to some extent) to provide yet more guarantees. For example, the only functions of type forall r. Behavior r Bool -> Behavior r Bool are of the form fmap f for some f.

    I’m picturing events such as “updates of the page foo.com/bar?baz”, events which must know they are being watched. This will allow efficient handling of event-rich systems such as gtk, or, say, device files. The only practical place to “snip” such an event is the instant we start watching it. In some sense, at any given time, an event can only give you occurrences later. That is the observance property.

    And as long as we’re snipping events to some point like the program start or something else, how much does join mean? Why can we not talk about events which have occurrences back to the beginning of time, such as clock ticks every second?

    Observance is a constraining property, and I am beginning to see this as a virtue. It makes sense as a practical limitation, and even makes sense philosophically in some sense (“if a tree falls in the forest …”). And it provides us with very strong theorems with which to reason, such as the above lifting theorem.

    With enough cleverness, and this is the speculative part, I don’t think it is any less powerful. We might just have to do a little more software engineering with the observant basis.

  3. Generalization of the lifting theorem:

    type BF a b = forall r. Behavior r a -> Behavior r b

    Every value of type BF a b is of the form fmap f, for some f :: a -> b.

    The trick is the scope of the r: eg. Behavior r (Behavior r b) is not allowed. Behaviors returning behaviors is where temporal information starts coming into play, because eg. integral :: (VectorSpace v) => Behavior r v -> Behavior r (Behavior r v).

    I wonder what kind of machinery I need to prove this.

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