A poll: hot events or applicatives? Choose two!

A few weeks ago, I wrote two articles making two separate points about FRP.

1. Cold events, meaning that events that trigger side effects on subscription and unsubscription, are evil.
2. The type Behavior a can essentially be Effect a, as it answers the question "what is a program doing now?"

In the second article, I argued that Phil Freeman's definition of Behavior cast its net too wide given what we understand a behavior to be semantically.

newtype ABehavior event a = ABehavior (forall b. event (a -> b) -> event b)

In this article, I'd like to revisit Freeman's type and explore the question "Does this type have a useful semantic meaning?" Spoiler: the answer is yes. And not only yes, but it will allow us to overcome one of the biggest shortcomings of the hot event: the fact that, by its construction, it lacks an Applicative instance. This, in turn, will allow us to get back pure while staying in the predictable and safe world of hot events.

A few reminders

Before delving into Freeman's Behavior type, let's review why hot events lack an Applicative instance so that you don't have to slog through the first article linked above.

My definition of a hot event is:

newtype Event a = Event ((a -> Effect Unit) -> ST Global (ST Global Unit))

What this is saying is: "If you give me an effectful emitter, I'll give you a small program that you can turn on to listen for events and off to stop the event stream."

Crucially, the on and off bit, aka ST Global (ST Global Unit), can't trigger side effects. This is what makes Applicative impossible. Let's try (and fail):

instance Applicative Event where
  pure a = Event \k ->
    -- d'oh! illegal
    -- `k` is in `Effect` and we need `ST Global`
    k a
    pure unit

This is a good thing. Hot events promise never to emit anything by themselves. They should never "make news", they should just report it.

What we've lost

So we're happy that there's no Applicative instance, but at the same time, we sort of miss it because it does mean something useful. For cold events, pure means "serve up this value at the moment of subscription." That's kinda nice, for example, if we're building a FRP-based framework. Maybe we wanna do a bunch of setup when a subscription occurs, like creating DOM elements or an initial render for a video game. pure could help us here, aa it is synonymous with "setup", which is a pretty basic need for most projects.

To show the mechanics of how purity interacts with subscriptions in cold events, let's bring back the old definition of Event that allows for cold events, to wit:

newtype Event a = Event ((a -> Effect Unit) -> Effect (Effect Unit)

instance Applicative Event where
  pure a = Event \k ->
    -- completely legal
    k a
    pure unit

When will that k a happen? When this happens:

-- remembering the definition of subscribe
subscribe (Event e) k = e k
-- sometime later
u <- subscribe (pure "hello") log
-- rewriting this using the definition of subscribe
u <- pure "hello" $ log
-- rewriting this using the definition of `pure`
u <- do
  log "hello"
  pure (pure unit)

That is, at the instant of subscribe, k will emit a (in this case "hello") and the subscriber, log, will dutifully log it to your logging apparatus of choice.

So purity in cold events is always related to the moment of subscribe.

Is there a way to get pure back?

No. Sorry, not with hot Events there isn't. It would really be nice, though, if we could. For example, purescript-deku creates a big DOM tree on the moment of subscription. purescript-ocarina creates a bunch of nice sound on the moment of subscription. All this is done with the erstwhile Applicative instance for Event.

So do we shrug and resign ourselves to cold events because it would be too unergonomic to lose pure? Of course not!

In fantasy land, we want to outlaw the random side effects of cold events but get pure back.

-- welcome to fantasy land!

-- this is outlawed
makeEvent \k -> do
  make1000APICalls
  k "hello"
  pure (pure unit)

-- this is ok
makeEvent \k -> do
  k "hello"
  pure (pure unit)

Let's start from this goal. Can we construct a type that does everything that Event does: filtering, fixed points, sampling, alternatives, but also has pure?

To do so, I'd like to go back to Freeman's Behavior type:

newtype ABehavior event a = ABehavior (forall b. event (a -> b) -> event b)

While this does not really define a behavior in that it is not a continuous function of time (as I argue in the article that I mentioned in the introduction), it does define the exact semantics of the problem we discuss above. As we saw above, the old Applicative instance of Event just responded to subscription. We can consider subscription itself an event, and if we do, we see that the definition of Behavior is just a more generic version of "respond to some event with another event."

The Applicative instance of Behavior formalizes exactly this: it pins a pure value a to some other event, namely the incoming one.

instance Apply event => Applicative (ABehavior event) where
  pure a = ABehavior \e -> e <#> (_ $ a)

So we've got pure back 🎉 But we've now traded our Applicative problem for two new ones:

1. ABehavior is not an event.
2. ABehavior, as I argued in my other article, is not even a behavior.

Let's fix those, first by figuring out what this type is and then arguing that it can be used interchangeably with events.

The Poll

If I gave Freeman's Behavior type to a storyteller and asked her to spin a tale, she may recount:

A surveymonger named event arrives with a survey called a -> b. Some entities a need to take the survey (could be a survey for cows, chairs, humans, whatever) and produce responses b. event tasks you with administering the survey. As your job is just that, you don't care what the results are, in fact, you have no idea what they mean. But you do know how to run a survey. So you consult the cows, or chairs, or humans, aka a, gather a bunch of responses, aka b, and report them back, aka event b.

Nice story, huh? Has rising action, a climax, a denouement. This story has nothing to do with behaviors, though. It is a story about polling. And that is what Freeman's type is. It's a poll! Or more accurately, it's a pollster, but we'll run with Poll as it sort of mirrors the abuse of language for Event, which also isn't an event but rather a series of them. Let the renaming commence!

newtype APoll event a = APoll (forall b. event (a -> b) -> event b)

So we've solved problem one of rehabilitating Freeman's type with a compelling semantic reading that boasts an applicative instance to boot. But is it a solution to our problem with events? Can we just drop events and use polls? Read on!

Yes we can just drop events and use polls

Ok, you didn't have to read much to get that the answer is yes. But keep reading!

At first blush, APoll is certainly not an Event. It is an event constructor, so saying it can be used interchangeably with events is like saying functions can be used interchangeably with values.

Of course, functions can be used interchangeably with values up to a point. For example, if I have Identity Int (a value) and String -> Int (a function), I can write the same program for both and then just change up the last step.

program = do
  a <- pure 1
  b <- pure 2
  pure (a + b)

-- for identity
programA = unIdentity program
-- for function
programB = program "foo"

So, in this trivial sense, one can drop in polls for events if all the program is doing is mapping, applying, and various other instances that both APoll and Event have. So what we're really asking is not if they can be used interchangeably, but rather if the stuff that makes an event an event can be done with APoll. And what is this "stuff" even?

This leads us to an oft overlooked but critical typeclass IsEvent. The IsEvent typeclass, also created by Freeman, describes the contract that events need to respect to be events. It contains the following functions:

class (Plus event, Alt event, Filterable event) <= IsEvent event where
  keepLatest :: forall a. event (event a) -> event a
  once :: event ~> event
  sampleOnRight :: forall a b. event a -> event (a -> b) -> event b
  sampleOnLeft :: forall a b. event a -> event (a -> b) -> event b
  fix :: forall i. (event i -> event i) -> event i

The first function, keepLatest, is unrelated to the other ones, but it is a guarantee that we can avoid time leaks where events create zombie subscriptions. Instead, if an event creates a bunch of events, it is required to clean up the old one before minting a new one. For any FRP framework to be useful in the wild, this is needed.

The next four functions are all related and have to do with state. The first, once, can be thought of an initial condition or initial state: it limits an event to a single emission. The sampleOnX can be thought of induction, meaning that they provide a way for event n + 1 to be derived from event n by emitting when one side of an expression emits. The last one, fix, can be used to execute this induction from an initial state, which is what allows for events to contain arbitrary state machines. Again, this stems from practice: anyone using an FRP framework in anger needs some sort of state management.

So, to use APoll interchangeably with event, we'd like to at least have these bases covered. One good strategy is to make sure that the events produced by APoll have the properties dictated by the IsEvent contract. For example, if we are implementing once = poll \a -> ?? (as we'll do below), we want to make sure that ?? also implements IsEvent and also has once applied to it.

once

In Event-land, once means that for a given Event a named A, we should produce a B that stops firing after its first emission. The analogue in APoll-land would be a poll that, for every incoming event a -> b, produces an event b that only fires once.

-- here, EClass is the namespace for the `IsEvent` class,
-- and `sample` merely unwraps a poll and performs function application.
once :: forall event a. IsEvent event => APoll event a -> APoll event a
once a = poll \e -> EClass.once (sample a e)

sampling

sampleOnRight and sampleOnLeft follow a similar arc. They sample each side by the incoming e and then call the event's instance of sampleOnRIght or sampleOnLeft.

sampleOnRight
  :: forall event a b
   . Pollable event event
  => IsEvent event
  => APoll event a
  -> APoll event (a -> b)
  -> APoll event b
sampleOnRight a b = poll \e -> EClass.sampleOnRight (sample_ a e) (sampleBy composeFlipped b e)

fix

Coming up with plausible semantics for the fixed point of a poll is harder. We want to produce an event with a fixed point, so at least we can commit that to writing.

fix fPoll = poll \e -> EClass.fix someSortOfLoop

While that's a start, it doesn't clarify the semantics of the input argument fPoll with type APoll event a -> APoll event a. In Event-land, something of type Event a -> Event a is easier to grok: it is a stream that feeds into itself, like a highway with a looping overpass or a microphone held up to a loudspeaker.

So if we have good intuition about the semantics of loops of type Event a -> Event a (highways, audio, etc), can this transfer over to a loop over polls to help us understand what that loop "means." To do this, we have to take our function APoll event a -> APoll event a and somehow turn it into Event a -> Event a. Then, by understand what transformation we underwent, we can form a logical relation to the easier-to-understand feedback loop.

We've seen already that we can turn a poll into an event by sampling it on some event e. To go the other way and turn an event into a poll, we don't have many options. Basically all we can do is let the poll emit the event (so an event emitting events) and then flatten it with keepLatest.

sham :: forall event. IsEvent event => event ~> APoll event
sham i = poll \e -> EClass.keepLatest (map (\f -> f <$> i) e)

I call this sham because it's a rigged poll: the set and order of respondents is pre-ordained irrespective of the incoming input, and if you used identity as the incoming function, you just get the original input back.

Armed with this, let's add a bit more pseudo-code

fix
  :: forall event a
   . IsEvent event
  => (APoll event a -> APoll event a)
  -> APoll event a
fix f = poll \e -> EClass.fix \ev -> sample (f (sham ev)) e

This is still wrong (we'll get to why in a minute), but at least we have a transformation into and out of APoll that will allow us to run a fixed point over events. But does this shed any light on the semantics of Poll a -> Poll a? Does it mean something as clear as Event a -> Event a, where the output stream is plugged back in as the input similar to wires in a mixing board?

It turns out that the two are interchangeable modulo the transformation f. To see this, let's take the inner term of fix and, whenever we get to a point where we can plug in an arbitrary function of type a -> a (like for f) or for type a -> b where we choose the b (like g), plug in identity.

-- the term
\ev -> sample (f (sham ev)) e
-- remembering that sample is just function application
\ev -> f (sham ev) e
-- substituting in the definition of `sham`
\ev -> f (\ee -> keepLatest (map (\g -> g <$> ev) ee)) e
-- substituting in `identity` for `f`
\ev -> (\ee -> keepLatest (map (\g -> g <$> ev) ee)) e
-- performing the function application, thus eliminating `ee`
\ev -> keepLatest (map (\g -> g <$> ev) e)
-- plugging in `identity` for `g`
\ev -> keepLatest (e *> ev)
-- remembering that `ev` _is_ the incoming event,
-- it will emit at the same rate as `keepLatest (e *> ev)`.
-- that's the definition of a fixed point!
\ev -> ev
-- which is just...
identity

It means that setting the input to the output for a poll, aka identity, is tantamount to setting the input to the output for an event, which means it is hermetic: no signal will flow. But it shows that, modulo some functions f and g, the event terms can be eliminated.

This isn't as rigorous as a formal proof, but hopefully it builds intuition that in the case of identity, a fixed point over polls is the same as a fixed point over events. More generally, it shows how the incoming event to the poll "cancels out" because it winds up being composed with the temporally-equivalent incoming event of the fixed point at the keepLatest step. Or, otherwise stated, it leverages the property of keepLatest that keepLatest (a $> a) === a.

As mentioned before, though, this is still in the land of pseudo-code, the types aren't quite right yet. Let's revisit the pseudo-definition:

fix
  :: forall event a
   . IsEvent event
  => (APoll event a -> APoll event a)
  -> APoll event a
fix f = poll \e -> EClass.fix \ev -> sample (f (sham ev)) e

The output of poll needs to be of type event b, which means that ev would need to be of type event b and sham ev of type APoll event b. However, f operates on APoll event a. So it can't be applied to a term of type APoll event b.

How can we fix this? One way is to use the idea from category theory that the function type a -> b can be represented as a morphism between Tuple (a -> b) a and b. By representing the function as Tuple (a -> b) a (which is also called the Store comonad), we have access to a and can thus apply a function of type APoll event a -> APoll event a.

To construct our tuple, we use sampleBy:

sampleBy :: forall event a b c. Functor event => (a -> b -> c) -> APoll event a -> event b -> event c
sampleBy f b e = sample (map f b) (map applyFlipped e)

fix f = poll \e -> (\(Tuple a ff) -> ff a) <$> EClass.fix \ee -> sampleBy Tuple (f (sham (fst <$> ee))) e

Then, as the last step, we do the function application to produce a b. Et voilà! We have fixed points over polls that work exactly the same as their event homologues. When an event of type a -> b comes down the pipe, it constructs a fixed point over an event of type b, and reconstructs the fixed point for every new emission of an a -> b.

keepLatest

Last but not least, we need a keepLatest. This is going to be a heavier lift than fix both conceptually and definitionally. With fix, the idea of a fixed point over polls doesn't make sense, but we can show that it is equivalent to a fixed point over events modulo some arbitrary transformation, so we can ground our intuition in fixed points over events.

With keepLatest, what does it mean to keep the most recent poll and cancel the previous one? Polls don't emit anything: they are a promise to emit 0 or more "answers" of type b after they receive a "survey/question" of type a -> b. So what are we keeping if we "keep the most recent poll" if nothing is even emitting yet?

Let's sum up intuition we've built so far to see if there's anything that will help us:

Function	Event-land	Poll-land
once	Emit an event once	For every incoming event, emit the output event once
sampleOnX	Like apply, but only emits when one of the two sides emits	For every incoming event, sample the left and right poll using that event, and then do sampleOnX on the events.
fix	Event a -> Event a represents a signal that feeds into itself like feedback	APoll event a -> APoll event a can be shown to work like Event a -> Event a, so we can ground our reasoning about behaviors based on events
keepLatest	Unsubscribe the previous inner event and subscribe to the new one	???

keepLatest is clearly the outlier: it is the only one that is talking about the mechanics of turning on and off event streams, and because we can't turn polls on and off, it makes the previous analogies difficult to apply here.

Without a clear semantic road-map, it's easy to write a definition of keepLatest that is nonsense. For example:

keepLatest a = poll \e -> EClass.keepLatest (sample_ (map (flip sample e) a) e)

This will compile, but it will behave completely differently than Event's keepLatest. It will sample the outer poll, which means that it will start emitting after both e and the output of a emit. And then, it will sample the inner poll on e as well, but at this point, if e is no longer emitting, nothing will happen.

To illustrate this more vividly, imagine the above explanation as a story:

A poll e comes down the pipe. We administer it, and the respondents send in their responses a few days later. All of the responses are... another poll! Well, we better administer this one as well, so we'll just wait until a second e comes down the pipe. But if e only ever happens once, then we'll never administer the second poll.

So it's very easy to create nonsense definitions of keepLatest that aren't in spirit with what we need out of it: namely, to cancel something old when something new happens.

For keepLatest to make sense, it has to somehow "preserve" the original impetus of the poll and reapply it to the inner poll. This would also give us a plausible semantic: unlike fix, where the incoming event to the poll "canceled out" through the fixed point, here the event needs to "echo" until the inner poll arrives so that we can sample it. Can we create an echo using FRP? We sure can!

An echo in signal processing is a form of feedback! Think about when you hear feedback in a microphone/loudspeaker setup: before it gets to that annoying high whine, you hear something echoing. The whine is just the loud frequencies of the echo tending towards infinity and the quiet ones tending towards zero.

We know how to create feedback, aka fixed points, because we just slogged through a whole section on exactly that. So let's have at it!

data KeepLatestOrder event a b
  = KeepLatestStart (APoll event a) (a -> b)
  | KeepLatestLast b

keepLatest
  :: forall event a
   . Filterable.Filterable event
  => EClass.IsEvent event
  => APoll event (APoll event a)
  -> APoll event a
keepLatest a = APoll \e ->
  Filterable.filterMap
    ( case _ of
        KeepLatestLast b -> Just b
        _ -> Nothing
    ) $ EClass.fix \ie -> oneOf
    [ sampleBy KeepLatestStart a e
    , EClass.keepLatest $ flip Filterable.filterMap ie case _ of
        KeepLatestStart b ff -> Just (sampleBy (\bb _ -> KeepLatestLast (ff bb)) b (EClass.once ie))
        _ -> empty
    ]

Here, we sample the outer event via sampleBy KeepLatestStart a e and use this as the first input to our echo machine. Then, we can sample the inner event - the sampleBy (\bb _ -> KeepLatestLast (ff bb)) b (EClass.once ie). Crucially, the EClass.once ie is guaranteed to fire in time for the sampleBy because it is the echo (fixed point) of the sampleBy KeepLatestStart a e!

So, to summarize, to give APoll event a valid instance of IsEvent, we always employed the strategy of "for each input, do the equivalent function from IsEvent on the output event." This was straightforward for once and sampleOnRight/Left. For fix, this was more circuitous but wound up being possible because we saw how a fixed point over polls can be algebraically reduced to a fixed point over events. And for keepLatest, we saw how this was possible by creating an "echo" over time to preserve the impetus of an incoming event.

Back to our frameworks

So now that we have the APoll type that can be used more or less interchangeably with Event and has an Applicative instance, where can we take it for a spin?

Look no further than purescript-deku and purescript-ocarina. Both frameworks, as mentioned above, rely extensively on events and need an Applicative instance so that they can have some sort of initial state, be it in the DOM or in the audio domain. Without APoll, it would be impossible for them to work in a hot-event-only world. But with APoll, not only do they work, but programs written using these frameworks need minimal if any adjustment because APoll has all the same instances as Event.

So, the next time you would like to transition to using only hot events in a framework you are maintaining but you can't forego an applicative instance (I'm assuming this happens to you multiple times a week), reach for APoll!