Conal Elliott's seminal paper on type class morphisms has an enigmatic chiasmus in its abstract and conclusion:

The instance’s meaning follows the meaning’s instance.

It's taken me a while to wrap my head around this, but doing so led me to a PR for purescript-deku that implements server-side rendering.

This article, in addition to showing off Deku's new SSR features, also explores work by Conal Elliott and Phil Freeman on denotational semantics and how they relate to reactive programming.

Denotational semantics and meaning

Conal's paper starts from the insight that type classes serve two functions:

• They represent laws, and it's up to a library's maintainer to make sure these laws are enforced. For example, map (f <<< g) = map f <<< map g is a law of functors.
• They have semantic meaning. In the case of Monoid, Additive Int and Multiplicative Int are lawful but also have different meanings with respect to Int. Additive 2 <> Additive 3 = 5 whereas Multiplicative 2 <> Multiplicative 3 = 6.

The rest of the article focuses on the oft-ignored second purpose of type classes: their denotational semantics, or in plainer terms, what they mean.

Conal elaborates:

...the meaning of each method application is given by application of the same method to the meanings of the arguments. In more technical terms, the semantic function is to be a type class morphism, i.e., it preserves class structure.

Type-class morphism sounds pretty scary, but because we're programmers, we can write this out in pseudocode and it becomes clearer. Take, for example, Functor. Elliott's advice translates to:

-- the meaning of each method application
meaning (map f b) =
  -- is given by the application of the same method to the meanings of the arguments
  map f (meaning b)

For those of you that have worked with newtype-s, meaning looks a lot like wrap and it is conceptually similar. A newtype only ever exists in a program because we need to add a layer of meaning that did not exist before.

We use the word "morphism" here because, in programming, there is no function that will get us from meaning ... (instance ...) to instance ... (meaning ...) in all cases. In some cases, we can use coerce to get from one to the other, but in general, we have to move meaning around by ourselves in our implementations. So instead, Conal appeals to the notion of "morphism" from category theory that represents a path from object A to object B. Or in other words, "meaning" is an arrow that can transport us from one type-class instance to another one.

Where is meaning and how do we access it?

In the examples above, meaning was ascribed to individual elements before the application of a typeclass (map f (meaning b)) or to the result of the type-class application (meaning f (map b)). But how can we encode this meaning as a type, and how can we get at this type to do something useful with it?

To answer this, I'll start from a type class IsEvent. IsEvent is the type class we'll wind up using when we discuss SSR, so it's good to get acquainted with it early! All of the examples from here on out will be in PureScript, and Conal's original paper was written with examples in Haskell, but the ideas this article are valid for any language where you can inject a dictionary of type classes, which is more or less any language.

Here's the definition of IsEvent from purescript-event:

-- | Functions which an `Event` type should implement:
-- |
-- | - `fold`: combines incoming values using the specified function,
-- | starting with the specific initial value.
-- | - `keepLatest` flattens a nested event, reporting values only from the
-- | most recent inner event.
-- | - `sampleOn`: samples an event at the times when a second event fires.
-- | - `fix`: compute a fixed point, by feeding output events back in as
-- | inputs.
-- | - `bang`: A one-shot event that happens NOW.
class (Plus event, Filterable event) <= IsEvent event where
  fold :: forall a b. (a -> b -> b) -> event a -> b -> event b
  keepLatest :: forall a. event (event a) -> event a
  sampleOn :: forall a b. event a -> event (a -> b) -> event b
  fix :: forall i. (event i -> event i) -> event i
  bang :: forall a. a -> event a

And some LAWS!

-- fold must respect monoidal identity
fold append event mempty = event
-- folding on emptiness yields emptiness
fold f empty b = empty
-- fixing on emptiness yields emptiness
fix empty = empty
-- keeping the latest of a single event is the same as the event
keepLatest (bang a) = a
-- sampling an event on itself yields a value with the same temporality as the event
let x = bang (a /\ fab) in
  sampleOn (fst a) (snd a) = bang b

IsEvent is by no means complete or exhaustive. Like many type-classes, it doesn't correspond to a category-theoretical ideal. Rather, its laws are common-sense truisms by which we need to abide for a reactive system to work. For example, we can't invent an event out of thin air through folding. Nor do we want sampling to warp time.

So while IsEvent has some laws, it's also a great demonstration of how impoverished the "law" viewpoint of type classes is without a semantic viewpoint. Events exist in time, and without some semantic domain for time, we can only define our laws in a way that appeals to the temporality of one of the events in the law itself. For example, keepLatest (bang a) = a is a law that is defined in terms of the temporality of bang. But what is bang? What is the "latest" in keepLatest? What does it mean for the second event in sampleOn to be fired at a "time"?

My questions may sound insincere, and a totally valid response would be "We're not reading Proust here, and you're not Marty McFly. Just measure time in some sensible unit, preferably seconds, and be done with it."

That's certainly one way to do it. In that case, we have a pretty open-and-shut argument for what the type of event should be:

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

An event takes a pusher that pushes values and returns two side effects: subscribing to it and unsubscribing from it. The pusher can be invoked at any time that a subscription is live.

Going back to the title of this section "Where is meaning and how do we access it?", meaning is "time" and "time" is encapsulated in the Effect monad. Furthermore, we can access Effect using the following function:

messWithMeaning f (Event e) =
  Event $ dimap (map f) (f <<< map f)

which will apply a natural transformation of type Effect ~> Effect all over our event.

Let's see if our use of meaning holds. We'll create a small function delay10 that delays an Effect Unit by 10 seconds.

delay10 e = launchAff_ (delay (Milliseconds 10_000.0) *> e)

In the Event domain, this can become:

delay10E (Event e) = Event $ lcmap (map delay10) e

And now, let's convince ourselves that:

delay10E (sampleOn a b) = sampleOn (delay10E a) (delay10E b)

We've shifted the entire time domain back by 10 seconds. The instance's meaning (what it means to delay by 10 seconds) follows the meaning's instance (the instance of IsEvent using Effect).

SSR and time

My little web framework purescript-deku runs on an event-based architecture, so I'm thinking about IsEvent quite a lot these days.

In deku, everything is an event at some level. Some events occur immediately at subscription (the initial render) whereas others occur later (like a mouse click or a timer).

But what if we want to do SSR and beam down HTML from the server instead of JavaScript? If we have a bunch of events that could happen anytime, we're out of luck: there's no way we can skim off the events from an initial render. But what if we can modulate the meaning of time 😵‍💫. This is what SSR is, after all. It's a morphism from dynamic time to static time. If we could do this, then we could take our entire application and run it through two different semantics of time depending on if we wanted static HTML or dynamic JavaScript. And we can do this, otherwise I wouldn't be writing this article :) Here's how!

Dissecting the Event type

In order to introduce a semantic domain into a law-abiding type-class instance, we need to modulate a variable in a type constructor that represents meaning. Recalling from the last section, Effect was what represented time. So that seems like a good candidate to modulate. In the definition of AnEvent below, we replace Effect by a polymorphic m.

newtype AnEvent m a = ((a -> m a) -> m (m a))

Now, when we're defining instances, our instances will look like:

instance IsEvent (AnEvent Effect)
instance IsEvent (AnEvent Foo)
instance IsEvent (AnEvent Bar)

If we want to control how AnEvent is used, we can also define it in terms of a constraint:

instance MyTypeClass m => IsEvent (AnEvent m)

where MyTypeClass has its own laws that need to be abided by.

I should take a moment to say that, like most things in PureScript, I learned this from Phil Freeman. He has a Semantic type that works slightly differently but is based on the same general ideas.

For server-side rendering, then, we want some monad m that doesn't let you do any of the nasty stuff - network calls, writing to disk, playing music (ew) - and also doesn't have any notion of time. It will dutifully collect all of the events that happen when the system fires up, use them to figure out what HTML a webpage needs, and ignore anything that happens "later" because "later" does not exist in this temporality: there is only now.

At the same time, our monad needs to be stateful. For example, when we use sampleOn, if we are sampling on two events that happen at an application's start up, realistically one will happen before the other on the CPU. So we do need to retain state for these important edge cases.

A great candidate for a stateful monad that has no notion of time or any other objectionable side effects is ST r. ST r is a monad with a single side effect: allowing you to freely write and read memory from a region r. That's exactly what we need, so we'll run with it!

Armed with our SSR monad, we have two event types with two different meanings:

-- Event for our application, can do all sorts of time-based logic and side effects
type Event = AnEvent Effect
-- Event for SSR, can only collect events that happen on an initial render
type STEvent r = AnEvent (ST r)

We've already confirmed that the "meaning" of Event held with sampleOn, so let's do the same thing for STEvent r. This will be easier: as we can't really do anything interesting in ST r aside from store and retrieve stuff in memory, we'll use a trivial function that just does some superfluous memory shenanigans.

trivial :: forall r. AnEvent (ST r) ~> AnEvent (ST r)
trivial (AnEvent i) = AnEvent \k -> do
  r <- new 0
  void $ write 3 r
  i k

And now, let's convince ourselves that:

trivial (sampleOn a b) = sampleOn (trivial a) (trivial b)

That's all well and good, but what about all those events that fire later, like click listeners? What is their "meaning" in STEvent. The sad truth for them is that they have no meaning (sorry!) because they will not exist in SSR. However, the non-existence of future events in SSR is complicated by the type of AnEvent, which we'll revisit now:

newtype AnEvent m a = AnEvent ((a -> m Unit) -> m (m Unit))

We can only ever subscribe to AnEvent if we give it a pusher of type a -> m Unit. For anything that requires external input like click listeners, we often use the following pattern to dislocate pushers from their events, freeing us up to dispatch the pusher wherever it's needed:

create
  :: forall m1 m2 s a
   . MonadST s m1
  => MonadST s m2
  => m1 { event :: AnEvent m2 a
  , push :: a -> m2 Unit
  }
create = do
  subscribers <- liftST $ Ref.new []
  pure
    { event:
        AnEvent \k -> do
          _ <- liftST $ Ref.modify (_ <> [ k ]) subscribers
          pure do
            _ <- liftST $ Ref.modify (deleteBy unsafeRefEq k) subscribers
            pure unit
    , push:
        \a -> do
          (liftST $ (Ref.read subscribers)) >>= traverse_ \k -> k a
    }

So create will externalize our pusher as a function push that we can use in listeners all over our application. The problem here is that all of our listeners, like click listeners and network calls, will expect this type to be a -> Effect Unit. In other words, even though our event has open-ended temporal semantics through the polymorphic type m, our application expects a single temporality of Effect. So can we coax our a -> m Unit to a -> Effect Unit? Or in other words, can one "meaning" of time (m) pretend to be another one (Effect).

A naïve solution would be to put pusher $> mempty all over our code, which will get us an a -> Effect Unit for any function of type a -> m Unit. But this is overzealous, as it will also annihilate the pusher in our JavaScript, which we don't want. The solution, then, comes from the type class Always. Always a takes an arbitrary monoid a and provides a function always :: b -> a that is guaranteed to be identity if a === b. So to get our pusher to Effect Unit, we write always <$> pusher. This means that, when "time" is represented by Effect, we will retain the original pusher via identity, whereas when "time" is represented by any other m, our pusher will push to mempty, which is sort of like the /dev/null of Effect.

If we step back a second, what we are saying here is that, when we do SSR, we want to provide effectful listeners like clicks and keyboard-presses with valid pusher functions of type a -> Effect Unit without making our AnEvent monomorphic over Event. But as we are generating HTML, our pushers will never get called anyway because there are no mice or keyboards in HTML. The click listeners are only ever attached during hydration. So always will only ever be called during the dynamic runtime as an Effect, meaning that its non-effectful vicissitude exists just to please the compiler.

From a semantic perspective then, we have one version of time a -> m Unit masquerading as another version of time a -> Effect Unit in a context where it will never be used. It is the equivalent of storefronts in a Western. You can have all sorts of flimsy crap representing buildings and it will totally fly provided that the actors never touch or shoot them. And this, in turn, leads to one of the most important generalizations about denotational semantics in life and code: It doesn't matter what things are, but only what we think they are.

SSR in Deku

Moving from the theoretical to the practical, purescript-deku now has SSR! The implementation follows the contours of that in this article. The Deku documentation uses SSR (otherwise it wouldn't be that honest, would it? use view-source:https://mikesol.github.io/purescript-deku to see for yourself!) and there is a tab in the documentation showing how to add SSR to your sites. In short, if you have an application of type type App = Domable m payload where m has the meaning of temporality, then you can use runSSR app to get raw HTML and hydrate app to hydrate it after a first render. Both runSSR and hydrate specialize m to two different meanings to get two different notions of time.

I'm pretty sure there are only two people in the world using Deku now, which is one short of a crowd! I hope you get a chance to try it out soon, but even if you don't, I hope that you'll check out Conal's paper and incorporate some of his ideas in your own work.