Max Hallinan

Critique of a code meme

The examples here are written in Elm, the original language of the RemoteData pattern. Like the pattern itself, the thinking can be generalized to other languages.

I. What is a code meme?

I’m not certain that code memes exist. I have a hard time defining the idea and unlike Justice Stewart, I am uncomfortable asserting the reality of something that escapes definition.1 “Code meme” is a label I give to some bits of programming I encounter on Twitter. The technical content of the code meme is a readymade response to a common experience, a macro of thought, rigidly copied from one context to the next. Like any meme, a code meme suddenly seems to be everywhere at once until suddenly it is nowhere at all.

Not every use of a programming pattern is mimetic. Programmers often adapt a pattern to a problem. Then the pattern informs but does not dictate the result. Code memes defy adaptation. Perhaps the most well-known code meme is the Hello World program. Hello World is a readymade solution to the problem of what program to write when beginning to learn a new language. The thought expressed by the code is unmodified. Only details like language or implementation change.

II. RemoteData is a code meme

The code meme Slaying a UI Antipattern in… refers to the RemoteData pattern. 2, 3, 4, 5, 6 To invoke the meme as “Slaying a UI Antipattern in Elm” means to show an Elm implementation of RemoteData. Like the Hello World program, the implementation is used to sample the flavor of the language, specifically the flavor of that language’s union types.

The RemoteData pattern and the UI Antipattern are both approaches to modeling the state of data generated by a REST request. User interfaces generally present remote data in states like not loaded, loading, error, and success. The UI Antipattern represents these states implicitly. The current state is derived from a model with roughly this shape:

type alias Model = 
  { xs : List X
  , isLoading : Bool
  , error : Error
  }

RemoteData improves on this approach by using a union type to make these states explicit. The state of the data is encoded into the data’s type:

type RemoteData a b
    = NotAsked
    | Loading
    | Failure a
    | Success b


type alias Model =
    { xs : RemoteData Error (List X)
    }

Making the state explicit has two benefits. First, the state is universally consistent and clear. There is no risk that consumers of the data will incorrectly derive an implicit state. Second, consumers of the data are required to handle every state:

view : Model -> Html a
view model =
    case model.xs of
        NotAsked ->
            emptyView

        Loading ->
            loadingView

        Failure error ->
            errorView error

        Success data ->
            successView data

This code will not compile unless the patterns of the case statement cover every possible state. The result is a robust system.

III. RemoteData does not model all possible states

RemoteData models a stateful cache of data in terms of a stateless transfer of data, REST. The current state of a RemoteData value preserves none of its prior state. For example, the transformation of Success b to Loading means that the information in b is lost. To carry that information from Success b to Loading requires us to update the Loading constructor to Loading b or Loading (Maybe b).

Here we must recall the old adage: user interfaces are state machines. Many common features demand a continuity of context. For example, infinite scroll is a combination of Success a and Loading. By breaking this continuity, RemoteData makes it impossible to model many legitimate states. These states include:

We can attempt to salvage the RemoteData pattern by adding nullable error and data parameters to the Loading and Failure states.

type RemoteData a b
    = NotAsked
    | Loading (Maybe a) (Maybe b)
    | Failure a (Maybe b)
    | Success (Maybe a) b

This enables us to model states that are a mix of loading, error, and data. For example, the “data cached, general error, and request pending” state would look like this:

Loading (Just error) (Just xs)

The “empty, general error, and request pending” state would look like this:

Loading (Just error) Nothing

We can use a similar approach to associate the loading and error states with a subset of the data. Here we assume a collection of items where each item is uniquely identified by a string. The relationship between the state and an item in the collection is made by adding a nullable string parameter to the Loading and Failure states.

type RemoteData a b
    = NotAsked
    | Loading (Maybe String) (Maybe a) (Maybe b)
    | Failure (Maybe String) a (Maybe b)
    | Success (Maybe a) b

But this approach only enables us to associate the error state or the loading state with one item at a time. The approach does not enable us to relate a mix of states with multiple items in the collection. Nor can we relate multiple states to the same item at the same time. Loading (Maybe String) (Maybe a) (Maybe b) must become Loading (Maybe String) (Maybe String, Maybe a) (Maybe b) to associate both the error and the loading state with an item in the collection.

We could continue to cram more information into the RemoteData type but I don’t recommend it. This path leads directly back to implicit states. Any code that consumes a value of the RemoteData type will explode with the nested case statements required to derive the current state.

IV. Inefficient-meme hypothesis

The efficient-market hypothesis states that prices always reflect all available information. I propose an inefficient-meme hypothesis: a meme never reflects all available information. As an utterance becomes more and more memetic, it is a map corresponding less and less to the territory.7

Edsger Dijkstra famously defined programming as “the art of organizing complexity, of mastering multitude”.8 In organizing complexity, we cannot make our programs less complex than they need to be. As programmers, we should be wary of code memes. The inefficient-meme hypothesis suggests that the code meme masters multitudes by leaving some of those multitudes out.

V. An alternative

It is tempting to sign off here, at the conclusion of my critique. But the critique does not solve the problem of modeling the states of a remote data cache. I work a lot on user interfaces. Whether or not I use the remote data pattern, I still want to solve that problem. So here is an alternative approach to modeling these states. This is an experimental approach. I’m not sure that it is a sane approach. I am always suspicious that there is a simpler way and glad to hear when there is.

The core of this problem is an insufficient number of states. Even a relatively simple user interface requires many more than the four states of RemoteData. There are two kinds of missing state. The first kind of missing state is compound state. Even a relatively simple user interface displays states that are a mix of “empty”, “loading”, “error”, and “success”. Let’s start by defining those states.

type Cache a b
    = Empty
    | EmptyInvalid a
    | EmptySyncing
    | EmptyInvalidSyncing a
    | Filled b
    | FilledSyncing b
    | FilledInvalid a b
    | FilledInvalidSyncing a b

The second kind of missing state is specific state. The state of a collection and the state of an item in that collection are not always the same. For example, an application might load a list of data first and then later make a request for details about one item in that list. Then only the item, not the collection, should be in the FilledSyncing state.

General and specific states are achieved by creating a cache of caches. Imagine that we are fetching data from a Person API. For every Person, we’ll create a PersonCache. Then we’ll store each PersonCache in a Dict keyed by Person id. Finally, we’ll create a Cache for this PersonCollection. General states are managed by the outer cache. Specific states are managed by the inner caches.

type alias Person =
    { name : String
    }


type alias PersonCache =
    Cache Http.Error Person


type alias PersonCollection =
    Dict String PersonCache


type alias Model =
    { persons : Cache Http.Error PersonCollection
    }

All possible states are represented. But when will the cache change its current state? The cache will change its state in response to a CacheEvent. Our cache will respond to three events: the start of a request to the remote data source and resolutions of that request to an error or data.

type CacheEvent a b
    = Sync
    | Error a
    | Update b

VI. A remote data cache is a state machine

Every combination of cache state and cache event results in a new cache state. All states and all events are known, and all state changes are knowable too. For example, a cache in the Empty state should change to EmptyInvalid a when an Error a event occurs. Here is a table that shows how each state should change in response to each event.

State                    | Sync                     | Error             | Update
-----------------------------------------------------------------------------------
Empty                    | EmptySyncing             | EmptyInvalid a    | Filled b
EmptyInvalid a           | EmptyInvalidSyncing a    | EmptyInvalid a    | Filled b
EmptySyncing             | EmptySyncing             | EmptyInvalid a    | Filled b
EmptyInvalidSyncing a    | EmptyInvalidSyncing a    | EmptyInvalid a    | Filled b
Filled b                 | FilledSyncing b          | FilledInvalid a b | Filled b
FilledSyncing b          | FilledSyncing b          | FilledInvalid a b | Filled b
FilledInvalid a b        | FilledInvalidSyncing a b | FilledInvalid a b | Filled b
FilledInvalidSyncing a b | FilledInvalidSyncing a b | FilledInvalid a b | Filled b

We know what the states are, when the states change, and how the states change. We know what we want to happen. Now we need a system that will make it happen. In fact, there is already a name for such a system. By describing the remote data cache, we have specified a finite state machine.

A finite state machine has three components: states, events, and transitions. An event prompts the finite state machine to transition from its current state to a new state. The finite state machine makes the correct transition by testing conditions at the time of the event. In our case, these conditions are all the combinations of states and events found in our state change table.

A simplified Elm update function closely resembles a simple state machine:

type Msg
    = Increment
    | Decrement
    | Reset


type alias Model =
    Int


update : Msg -> Model -> Model
update msg model =
    case msg of
        Increment ->
            model + 1

        Decrement ->
            model - 1

        Reset ->
            0

The Msg is like an event, the Model is like a state, and each branch of the case expression is a transition from the current state to the next state. A major difference between this update function and a finite state machine is that update produces an infinite number of states. Without upper and lower bounds, update can return any member of the infinitely large set of integers.

We can write a similar update function that changes the state of the remote data cache. This is the heart of the state machine. updateCache takes a CacheEvent event and a current Cache state, and returns a new Cache state. The state will change according to the rules defined in the state change table above.

updateCache : CacheEvent a c -> Cache a b -> Cache a b
updateCache event current =
    case current of
        Empty ->
            case event of
                Sync ->
                    EmptySyncing

                Error nextError ->
                    EmptyInvalid nextError

                Update nextData ->
                    Filled nextData

        EmptyInvalid currentError ->
            case event of
                Sync ->
                    EmptyInvalidSyncing currentError


        -- etc.

There is no prescribed implementation of a remote data cache as a finite state machine. States, events, and transitions should reflect the needs of the application. And state machines themselves come in several varieties. My principal aim is to make the conceptual connection. Nonetheless, it is not enough to say “just use a finite state machine”. Implementing a state machine for this purpose is not trivial, so I want to touch on a few of the details.

VII. Polymorphic transitions without polymorphism

Before implementing updateCache, we must remember that this cache system should be compatible with different types of data. There is one problem here. When the state of the cache changes, it’s sometimes necessary to change the data itself. For example, the Update b event might require us to merge new data with existing data if the state of the cache is Filled b. How the data changes is probably specific to the type of data. So the cache must do some type-specific transformations while remaining uncoupled to the type.

The solution is to pass transitions into the state machine. These transitions are hooks for moments in the process of changing the state. The state machine knows how and when to call these hooks but does not know what they do. This keeps type-specific logic out of the cache while enabling type-specific transformations.

For the moment, let’s provide two of these transitions. This first is updateEmpty, a transition that is called when an empty cache changes to a filled cache. updateEmpty is called with data from the Update a cache event. The second is updateFilled, a transition that is called when a filled cache changes to a filled cache. updateFilled is called with data from the Update a cache event and data that is already in the cache.

type alias Transitions a b =
    { updateEmpty : a -> b
    , updateFilled : a -> b -> b
    }


updateCache : Transitions c b -> CacheEvent a c -> Cache a b -> Cache a b
updateCache transitions event current =
    case current of
        Empty ->
            case event of
                Sync ->
                    EmptySyncing

                Error nextError ->
                    EmptyInvalid nextError

                Update nextData ->
                    Filled <| transitions.updateEmpty nextData


        -- etc.

VIII. General and specific state changes

Recall that our Person cache example is structured as a cache of caches. As we move forward with the implementation, we realize that there is no way to update the inner caches. Updating the inner cache should begin as an update to the outer cache. But how can the outer cache know that the event and the resulting state change are specific to one of the inner caches? In our system, it cannot.

Again, the cache should not know the structure of the cached data. This means that the cache should not even know about the inner caches. Any cache just needs to know the difference between a change to all of the cached data and a change to a piece of the cached data. Events are the medium of communication with the state machine. If the Update b event signals a change to all of the cached data, we need to add a new event that signals a change to a subset of the data. We’ll call this event Patch c.

type CacheEvent a b c
    = Sync
    | Error a
    | Update b
    | Patch c

Changing the data in response to Update b is different from changing the data in response to Patch c. For example, merging two lists of data in response to Update b is one transformation. Merging two copies of one item in that list in response to Patch c is a second transformation. To account for this difference, we’ll add a patchFilled transition. This transition is called with data from the Patch c event and all of the cached data. patchFilled, not the state machine, is responsible for selecting the subset of data to transform.

type alias Transitions a b c =
    { updateEmpty : a -> b
    , updateFilled : a -> b -> b
    , patchFilled : c -> b -> b
    }

updateCache : Transitions c b d -> CacheEvent a c d -> Cache a b -> Cache a b
updateCache transitions event current =
    case current of
        -- etc.


        Filled currentData ->
            case event of
                Sync ->
                    FilledSyncing currentData

                Error nextError ->
                    FilledInvalid nextError currentData

                Update nextData ->
                    Filled <| transitions.updateFilled nextData currentData

                Patch patch ->
                    Filled <| transitions.patchFilled patch currentData


        -- etc.

To update the state of an inner cache, we’ll send an event through the outer cache to the inner cache. Patch CacheEvent is used to carry the inner cache event through the outer state machine. patchFilled receives that event and coordinates the update.

type alias PersonCollection =
    Dict String PersonCache


type alias PersonCache =
    Cache Http.Error Person


patchFilled : String -> CacheEvent Http.Error Person a -> PersonCollection -> PersonCollection
patchFilled key cacheEvent personCollection =
    -- select the inner cache
    Dict.get key personCollection
        -- update the state of the inner cache
        |> Maybe.map
            (updateCache
                { updateEmpty = updatePersonEmpty
                , updateFilled = updatePersonFilled
                , patchFilled = patchPersonFilled
                }
                cacheEvent
            )
        -- reinsert the updated inner cache into the collection of caches
        |> Maybe.map (\update -> Dict.insert key update personCollection)
        |> Maybe.withDefault personCollection

This is the part of the approach that I am the least comfortable with. The concept is undoubtedly hard to understand here and it was tricky to implement for the proof of concept.

IX. Mediating state explosion

All consumers of the remote data cache are required to handle every cache state. Depending on the pattern matching capabilities of the language, explicit states result in verbose code. The code becomes especially noisy when many states are handled in the same way.

View functions are prone to suffer from this noisiness. Many of these view functions have a binary relationship to the state of the cache. A loading icon is displayed when the cache is in a loading state. Otherwise, no loading icon is displayed. An error message is displayed when the cache is in an error state. Otherwise, no error message is displayed. View functions responsible for these features do not need to know all varieties of cache state. It is advisable to reduce the many states of the cache to a set of fewer states for the view.

type Visibility a
    = Show a
    | Hide

Then each kind of view defines its own reduction of Cache to Visibility. For example, an error view might reduce all cache error states to Show Error and all other cache states to Hide.

errorVisibility : Cache Error a -> Visibility Error
errorVisibility cache =
    case cache of
        Empty ->
            Hide

        EmptyInvalid error ->
            Show error

        EmptyInvalidSyncing error ->
            Show error

        EmptySyncing ->
            Hide

        Filled _ ->
            Hide

        FilledInvalid error _ ->
            Show error

        FilledInvalidSyncing error _ ->
            Show error

        FilledSyncing _ ->
            Hide

This approach is enhanced by a higher-order function that handles the Hide case.

visibilityToHtml : (a -> Html b) -> Visibility a -> Html b
visibilityToHtml toHtml visibility =
    case visibility of
        Show x ->
            toHtml x

        Hide ->
            text ""

The view itself is a composition of these functions. This keeps large case statements out of the function that produces the html.

errorView : Cache Http.Error a -> Html Msg
errorView =
    errorVisibility >> visibilityToHtml errorHtml

X. Unfinished maps

There is a lot of information here and I’m not convinced that any of it is good. This is, emphatically, an experiment. While the RemoteData pattern was too simple, this approach is in danger of becoming too complicated. We are accustomed to doubt the correctness of a messy abstraction because it is messy. I am inclined to also doubt tidy abstractions because they are tidy. The lesson of the code meme is that messiness and tidiness of abstraction can be the same kind of incorrectness. Our world is both messy and tidy. Our abstractions crystallize our understanding of that world. So we can expect our abstractions to be messy and tidy too. Pronounced messiness and pronounced tidiness might both be signs of incomplete understanding. We began with a tidy abstraction and now end with a messy abstraction. Please let me know when you find the middle path.

Notes

  1. ^ Supreme Court Justice Potter Stewart doubted that he could ever "intelligibly" define obscenity. Instead, his famous test was "I know it when I see it."

  2. ^ How Elm Slays a UI Antipattern by Kris Jenkins, the first to describe this pattern.

  3. ^ Slaying a UI Antipattern in Fantasyland

  4. ^ Slaying a UI Antipattern in React

  5. ^ Slaying a UI Antipattern in Flow

  6. ^ Slaying a UI Antipattern in ReasonML

  7. ^ The usefulness of the code meme, like any code, depends on how accurately it represents the problem:

    A map is not the territory it represents, but, if correct, it has a similar structure to the territory, which accounts for its usefulness.
    Alfred Korzybski

  8. ^ Edsger Dijkstra (1970) "Notes On Structured Programming" via Wikiquote:

    The art of programming is the art of organizing complexity, of mastering multitude and avoiding its bastard chaos as effectively as possible.