Recently, the Rabbit r1 launched. It's a new handheld device that promises a new primary interaction model with compute: by talking to them in the context of the real world. In turn, they would help us perform actions to help us with unstructured, but menial tasks throughout our day.

The reaction was visceral. As evidenced by the entire thread of replies, otherwise reasonable people were overcome by unreasonable emotion against someone building something categorically new.

Of course, hot takes for internet points is nothing new, and it has no cost to take up a dissenting view. But there's this insidious underlying pessimism whenever we introduce something categorically new: why are we making tech where I can't see the need?

I had originally set out to write about the pessimistic reaction to the Rabbit r1 (having no affiliation with the company), but this expanded to an expression of my broader view: that technological optimism is required for seeing into the future for the health of both the individual and society.

Surprisingly, I find this cynical perspective common even among tech workers, the people supposedly building the future.[^0] Our collective memories are so short that we can't remember how obviously useful technology started as toys with non-obvious utility. As if the technologies one uses today weren't once radical heresies that transformed into an ambient miracle we take for granted. And as a technology optimist, I find it incredibly shortsighted to dismiss anything outright.

Here's where one might object: it's selective bias if we only look backward! Of course, that will make it seem all heretical new inventions will become commonplace. What about all the different technological innovations that failed?

I'm not suggesting that every new thing that comes on the market has an inevitable climb to being indispensable and commonplace. But I am saying for categorically new technology, we can't tell just by thinking about it.

For sustaining technologies that have an existing market of jobs-to-be-done, we can accurately tell whether we can make use of a new technology or not. When a new smartphone comes on the market today, it does mostly the same job that I've used other smartphones for before. Take pictures, chat with friends, navigate the world, check email, troll on social media, or hail a ride. I can accurately predict whether I'd find any of these useful because it's easier to imagine something I'm already doing, but better.

But for potentially disruptive and categorically new technology that addresses completely new and underserved markets, it's very hard to see or predict where the utility will be. By definition, technology that caters to new and underserved markets addresses our changing habits, boosts our capabilities, or expands our possibilities–something different from what we do now. Unless you happen to be smack middle of the underserved niche, it won't be obvious how a categorically new technology is useful. It takes work to move yourself into the niche to see a new technology's potential.

When the iPhone first came out, the biggest objection was its lack of a physical keyboard. But with additional predictive technology, a device with no keyboard was usable without fanfare. Initial objections loom so large in the pessimist's mind that they can't get beyond it to ask more forward-looking questions–to move themselves into the niche of a categorically new product. Doing so is to explore, to say to oneself, "What if this did work? Then what?"

An explorer would notice that a multitouch interface expands the set of mobile applications beyond email. Then the forward-looking question was, "What mobile applications does this enable?" An explorer would see the smartphone made computing intensely personal for the first time by being always on you in your pocket. Then the forward-looking question was, "How does this affect how people view each other or themselves?" It may not be clear what the answers are, but at least you're starting to ask targeted questions about the future. Because, unlike technology in existing markets, it's hard for us to imagine something we've never done before.

Hence, this is my own hot take: The Rabbit r1 isn't a device. It's an invitation to explore a new frontier.

All is not lost

Well, not everyone is pessimistic. Rabbit sold 10k devices invitations to explore on the first day, and sold out of 5 batches.

What I'm excited about the Rabbit r1 is that it brings real-world context into an LLM. My own experiences with LLMs conclude context is very important for LLMs to be useful. To that end, we currently pair a search over a database (Retrieval Augmented Generation, RAG) with an LLM. But we can pair it with more than just a database. Rabbit provides a multimodal context of the real world. It makes the real world a "database" that an LLM can query, and that opens up many categorically different use cases than we've had in the past year using LLMs in a chatroom context.

And lots of people on this thread have positive outlooks about its prospects too.

There are still explorers of frontiers out there, looking towards the future. I think it's important that we keep that sense of excitement for the future alive. Technology doesn't progress all on its own. It only happens when people who see a problem are motivated to find a solution, either by using one or by creating one.

Why is seeing the future important? How do you set yourself up to have the greatest chance of seeing the future?

If you want to hear more on this line of thought about optimism and seeing the future, subscribe or follow me on Twitter.

Thanks to Eric Dementhon for reading the drafts.

[^0] For non-tech workers, I find disruptive innovative tech doesn't even register in their heads. They don't even know what they're looking at when you show it to them.

We want a data structure that holds an ordered set of keys, as a way to build composite CRDTs. The keys must have a total order.

This data structure should be like a B+tree, Prolly Tree, and Merkle Tree. It should have the following properties:

• High-fanout on each node.
• The tree is balanced and low in height to keep query complexity around O(log n)
• Balancing the tree will change as little of the tree as possible upon insertion of keys.
• The tree is unicit, where the order of insertion doesn't alter the state of the tree. The same ordered set of keys will yield the same tree.

The construction of the tree is as follows:

• A leaf node contains entries that are an ordered subsequence of keys in the set.
• A branch node contains entries of the content hash and the range of keys of every child node.
• Regardless of type, the ideal node size is \(N\).
• It's a Merkle tree, so each node is identified with a hash of its contents. A leaf node is a hash of its keys. A branch node is a hash of the concatenations of the child node hashes and ranges.

Balance with history independence

As with any tree, we want ours to be balanced, where the number of entries in each node should be about the same. Balanced trees are desirable for efficient queries. At the same time, we want unicity, where the same set of ordered keys must result in the same tree, regardless of insertion order. Unicit trees are desirable for Merkle Trees for fast equality comparisons by simply comparing root hashes.

In B+trees. nodes are balanced on insert, but the structure of the tree is not history-independent. Two B+trees could be different, even if they contain the same set of keys.

In Merkle Search Trees and Prolly Trees, nodes are probabilistically balanced. While the expected value of nodes is \(N\), the variance of node sizes is large. There is a variant of Prolly Trees with a tighter variance of node sizes, but it is not history-independent.

It turns out unicity is in conflict with balancing nodes. Could we use some of the same math in CRDTs to get a unique balanced tree regardless of the insertion order of keys?

To do that, we'll need:

• An element type that describes how the ordered set of keys is divided between leaf nodes.
• A partially ordered set of elements defined with a binary relation that orders two elements, \(A \leq B\)
• A merge function that combines two elements into a third element that is closed over the element type.

The binary relation of a partially ordered set needs to have the following properties: Reflexive, Antisymmetric, and Transitive.

The merge function needs to have the following properties: Commutative, Associative, and Idempotent.

We'll define these properties later.

Multi-Split Description

How do we define the elements in the partially ordered set that can describe how keys are split between leaf nodes? We define Multi-split descriptions (MSD) that describe the splits.

• A multi-split description can be represented as a sequence of key groups: \(A = [K_0^A, K_1^A, \ldots, K_i^A]\), where each key group \(K_j^A\) is an ordered subset of keys.
• The key groups are ordered in the sense that if \(j<k\), then every key in \(K_j\)​ is less than every key in \(K_k\)​ according to the total order of keys.
• Each key group \(K_j\)​ represents a set of keys that would reside together in a node if the tree were split at this point.

Partially Ordered Set

To get a partially ordered set (poset) of MSDs, we'd have to define a binary relation \(\leq\) that orders two MSDs. Keep in mind that the keys in a key group of an MSD have a total order, but the MSDs themselves have a partial order.

The binary relation has two criteria: a primary criterion based on closeness/variance and a secondary criterion based on subsequences.

Primary Criterion: Closeness/Variance

Each MSD \(A = [K_0^A, K_1^A, \ldots, K_i^A]\) is evaluated based on how closely each key group \(K_i^A\)​ adheres to a target node size \(N\) and the variance in sizes across the key groups. The metric for closeness/variance is

$$M_A = \sum_{i=0}^{n} (\text{length}(K_i^A) - N)^2$$

where \(n\) is the total number of key groups in the multi-split description \(A\), \(K_i^A\) is the ith key group of MSD \(A\), and \(N\) is the target node size.

Secondary Criterion: Subsequences

There can be multiple MSDs with the same primary metric \(M\), so the secondary criterion serves as a tie-breaker and indication of partial order based on subsequences.  For two multi-split descriptions \(A\) and \(B\), \(A\) is considered less than or equal to \(B\) under this criterion if each key group in \(A\) (\(K_i^A\)), is a subsequence of the corresponding key group in \(B\), (\(K_i^B\)).

Binary Relation Definition

For two multi-split descriptions \(A\) and \(B\), we define \(A \leq B\) in the poset if:

1. Primary: The closeness/variance measure \(M_A​ \geq M_B\). Notice the direction of the inequality is reversed. The closer \(M\) is to zero, the better balanced it is.
2. Secondary: If two descriptions \(A\) and \(B\) have the same closeness/variance measure \(M_A = M_B\)​, then \(A \leq B\) if each key group \(K_i^A\) in \(A\) is a subsequence of the corresponding key group \(K_i^B\) in \(B\).

Required Properties of a Partially Ordered Set

• Reflexivity: \(A \leq A\)
  Every multi-split description \(A\) is reflexive with itself since \(M_A = M_A\)​ and each key group \(K_i^A\)​ is trivially a subsequence of itself. Therefore, \(A \leq A\).
  
• Antisymmetry: If \(A \leq B\) and \(B \leq A\), then \(A = B\).
  Assume \(A \leq B\) and \(B \leq A\). Hence, \(M_A \geq M_B\) and \(\text{for each } i, K_i^A \text{ is a subsequence of } K_i^B\). Also, \(M_B \geq M_A\) and \(\text{for each } i, K_i^B \text{ is a subsequence of } K_i^A\). From \(M_A \geq M_B\) and \(M_B \geq M_A\), we deduce that \(M_A = M_B\). And since each \(K_i^A\)​ is a subsequence of \(K_i^B\) and each \(K_i^B\) is a subsequence of \(K_i^A\), each pair of corresponding key groups must be identical. That is, for each \(i\), \(K_i^A = K_i^B\).
  
• Transitivity: If \(A \leq B\) and \(B \leq C\), then \(A = C\)
  If \(A \leq B\) (meaning \(M_A \geq M_B\)​ and subsequences align) and \(B \leq C\) (meaning \(M_B \geq M_C\)​ and subsequences align), then \(M_A \geq M_C\)​ and the subsequence condition from \(A\) to \(C\) will also hold, thus \(A \leq C\). Therefore, If \(A \leq B\) and \(B \leq C\), then \(A \leq C\).

Merge function

Now that we have a partially ordered set (poset) of MSDs, we need to define a merge function. The merge function combines two MSDs and returns a third MSD that represents the Least Upper Bound of the two MSDs in the join-semilattice.

$$A \sqcup B = C$$

where \(A\) and \(B\) are MSDs that combine into the merged MSD \(C\).

An outline of this merge function is as follows:

• For every key group \(K_i^A\) in \(A\), merge it with its corresponding key group \(K_i^B\) in \(B\). Recall each key group is a totally ordered set, and each key is unique, so they can be merged according to a set merge.
• For the key group \(K_c^{A \sqcup B}\) that changed at index \(c\), due to the insertion or deletion of a key, we rebalance the splits between the key group and its neighbouring siblings. This has to be a function that only relies upon the changed key group \(K_{c}^{A \sqcup B}\), and its previous sibling \(K_{c-1}^{A \sqcup B}\) and next sibling \(K_{c+1}^{A \sqcup B}\).
• After this rebalancing, we change the content hash references to the child node on the parent node recursively back up to the root node.

The rebalancing function must be a pure function of the three key groups under consideration. There is a list of possible "moves" to rebalance the three key groups:

• Do nothing (leave \(K_{c}^{A \sqcup B}\) as is)
• Move the leftmost key of \(K_{c}^{A \sqcup B}\) to \(K_{c-1}^{A \sqcup B}\)
• Move the rightmost key of \(K_{c}^{A \sqcup B}\) to \(K_{c+1}^{A \sqcup B}\)
• Borrow the rightmost key of \(K_{c-1}^{A \sqcup B}\) to \(K_{c}^{A \sqcup B}\)
• Borrow the leftmost key of \(K_{c+1}^{A \sqcup B}\) to \(K_{c}^{A \sqcup B}\)
• Split \(K_{c}^{A \sqcup B}\) into two nodes (at the middle index or median key value).

For each move, calculate the closeness metric.

$$M_{A \sqcup B} = \sum_{i=c-1}^{c+1} (\text{length}(K_i^{A \sqcup B}) - N)^2$$

where \(K_i^{A \sqcup B}\) denotes the original state of the key groups. Because the rest of the tree is unchanged, we don't need to take into account the contribution of the unchanged nodes to the closeness metric computation.

We also need to calculate the closeness metric of both A and B at the point of insertion before the merge.

$$M_{A} = \sum_{i=c-1}^{c+1} (\text{length}(K_i^{A}) - N)^2$$

$$M_{B} = \sum_{i=c-1}^{c+1} (\text{length}(K_i^{B}) - N)^2$$

Given the closeness metrics, \(M_{A}\), \(M_{B}\), and all moves of \(M_{A \sqcup B}\), we pick the move with the max metric that's less than the metric of both A and B. This should give us the least upper bound of the merge.

$$\max { m \in M_{A \sqcup B} \mid m < M_{A} \text{ and } m < M_{B} }$$

Remember, the smaller the metric, the greater the binary relation. So we want the maximum metric (least) with a metric less than (upper bound) both A and B.

In the case of a split, we have a special case. We need to rebalance the parent node and repeat this calculation, recursively up to the root node, or until we get to an ancestor branch node that doesn't need to rebalance.

In the case of a tie, we choose the move where every key group \(K_i^{A \sqcup B}\) is a supersequence of the key group \(K_j^{A \sqcup B}\) from the other move.

We want to pick the move that gives us an MSD that's greater than the MSD of the other move per the binary relation of the poset as described above.

Required Properties of a Merge Function

This merge function has to satisfy three algebraic properties: commutativity, associativity, and idempotence. Objects that satisfy all three properties are called semilattices.

• Commutativity: \(A \sqcup B = B \sqcup A\)
• Associativity: \((A \sqcup B) \sqcup C = A \sqcup (B \sqcup C)\)
• Idempotence: \((A \sqcup B) \sqcup B = A \sqcup B\)

For all of these, it relies on properties of sets and a property of pure functions.

1. Merging sets have all of the algebraic properties above.
2. Pure functions return the same output given the same inputs.

The keys have a total order and are unique. Each key group is an ordered set. Therefore, a merged key group \(K_{i}^{A \sqcup B}\) is the identical regardless of merge order \(K_{i}^{A \sqcup B} = K_{i}^{B \sqcup A}\). The rebalance function is pure.

Therefore, given the same set of input key groups, the resulting key groups are the same. Hence, it does not matter the order the merge function is applied for commutivity and associativity. Idempotence relies on the idempotence of the set merge function–it doesn't matter how many times an element is inserted, the merged set will be the same.

Join semi-lattice

With both a partially ordered set of multi-split descriptions and an algebraic merge function, we can combine the two into a join semi-lattice that can maintain the same splits regardless of the insertion order.

This should give us a unicit tree where the same data gives us the same tree, making it easy to compare hashes as a Merkle tree.

Addendum: monotonically increasing state

So far, the formulation for this only addresses insertions. However, it should also work for deletions, but we'd need a different representation of a key group to maintain a monotonically increasing state. It should be enough to add tombstones: two sets for every key group–a set for addendums, and a set for deletions.

CRDTs often have to keep this monotonically increasing state around to retroactively sync any replicas in the future. We don't have that requirement. For single-threaded use, I think we can collapse the state after every reversal from insertion to deletion or vice versa. For multi-threaded use, we can keep the state around while there are concurrent edits, but after all changes are committed, we can probably compress that state.

I designed this with the help of GPT. It probably warrants a blog post at some point. But in the meantime, you can see the transcripts here:

• Designing Lattice Merkle Trees Part 1
• Designing Lattice Merkle Trees Part 2
• GPT writing Isabelle code

And the resulting incomplete Isabelle code.

• The incomplete initial strategy of proving a full implementation.
• The incomplete simplified strategy of proving properties on node sizes.

Compared to 2021, I was much more focused this year. Compared to 2022, I have built more conviction. And starting in September, I started to have full days to work, rather than just the nights and weekends.

Unlike 2021, I wasn't trying a lot of different things. I was mainly trying to focus and build conviction in the direction I needed to go forward.

At the beginning of this year, I wasn't sure if building a database in the browser was the right move. Do I want to do this because I am attracted to the problem, or am I attracted to the solution? I've fallen down the rabbit hole of the latter before, and it results in a whole lot of wasted time, even if there were challenges and fun to be had along the way.

Hence, I surveyed the existing databases as a local-first solution and found most wanting. Some came close, like ElectricSQL, Evolu, and CR-SQLite, but I don't think they have the same long-term focus that I'm envisioning. And yet, that wasn't enough to build conviction. So I sought to try and build a to-do list app, both as a demonstration of needs, as well as a way to explore questions about why applications didn't use avatars.

It did take a while to work through a bunch of issues on the application side, and I did learn quite a bit about application-level issues one would run into when it came to migrations.

However, at some point, I just ran into a roadblock with off-the-shelf CRDT libraries. Almost all of them were focused on a document-orientated way of modelling data. I thought there was much value to a relational model that could sync.

So at the end of August, I ended back where I was in January: it's the right thing to build a database in the browser. After making the call, I made relatively quick progress. I have a model of how relational data can be synced, how to leverage existing databases, and the tactical details of how the whole thing would fit together.

At the end of this year, I find myself deep in the rabbit hole, eager to pop my way all the way up the stack to get something usable.

When it comes to syncing, I think I have all the pieces I need. However, when it comes to incrementality, that's a whole topic I have yet to dive into. But I think just like the CRDTs, I think just committing fully to diving in will get me up to speed pretty quickly. I've shown myself this fall that I could catch up pretty quickly, not only because I've been looking at this from the sidelines for a long time, but also because I can now enlist the help of GPTs to help me get up to speed quickly.

Aside from this main line of work, Sri and I recorded The Technium Podcast together. Our original impetus for starting it was just that we talked about this sort of stuff anyway over the pandemic, why not just record it and put it out there?

And while fun, it took a while to edit each episode. We tried to structure everything so we could do as little editing as possible, and yet it took us away from our other main thrust of work. With 300 subscribers, it was hard to justify the timesink. So after the third season, we decided to take a hiatus.

However, it seems like some people do enjoy our work after feeling our absence. With some time away, we've come to think of 300 as an auditorium of people, which is quite a lot! In addition, building an audience is an activity with superlinear returns if one can get the flywheel going. So it's probably worth putting in the effort despite the low absolute numbers. To get us through this period, we've changed our perspective to this being a beacon to interesting people. So we'll be talking about how we'll proceed in the coming year on a new season.

With the additional time, I started writing more again, committing to weekly updates. These are less polished, more to jot down progress and accountability, starting with Lab Note #021.

A friend of mine told me that I'm very good at consistently living in the future, but I'm not very good at selling the future. So to help fix that, I'll also write more complete and long-form thoughts in longer posts. They should take no longer than three weeks to write, just to keep some consistency going. This year, I managed to put out three. That should be an easy bar to clear. Check them out if you haven't already.

• The state management library front-ends are looking for is a database
• Trade-offs between Different CRDTs
• CRDTs Turned Inside Out

I think a lot lately about building conviction, and why it was so tough for me to find it this year. It's the classic mid-wit move of talking yourself out of everything when you know slightly too much. This year, I learned that you just don't know how things will turn out ahead of time, no matter how much you think about it or ask other people. Instead, you must light your conviction based on your initial hunch, and run as fast as you can to the end before the candle of conviction burns out.

What I hope for 2024 is that I will continue to accelerate the pace of learning, and keep building conviction for what I'm doing. But importantly, this year, I'm committing to systematically find a way to learn how to work faster. Hope you had a great year too, and commit to finding direction in your own work.

Last time, I discussed the trade-offs between more traditional CRDTs, such as the State-based CRDT, Op-based CRDT, and Delta-based CRDT.

There is another class of CRDTs: Merkle CRDTs.

Most ink spilled on CRDTs focuses on consistently merging data from different replicas. That's just half the story. Without a way of storing when concurrent edits happen, merges can't make consistent decisions about conflict resolution.

Normally, this is the job of version vectors in State-based CRDTs and the log of causal operations in Op-based CRDTs. But if you're familiar with blockchains or Git, we notice that Merkle Trees and DAGs (Directed Acyclical Graph) can also do the same job.

The following is how we construct this bookkeeping, exposed as an inherent structure of the concurrent state, rather than hidden away within a container. Let's look at the two variations:

• Merkle-DAG CRDTs
• Merkle Search Tree CRDTs

Merkle-DAG CRDT

The Merkle-DAG (Directed Acyclical Graph) models CRDTs as a growing DAG of Merkle nodes about concurrent updates as events occur. This is a Merklized version of Op-based CRDTs, where the internal bookkeeping grows with the number of state updates, rather than with the number of replicas.

Each node in the Merkle-DAG can carry a payload of operations, state snapshots, or even deltas. This node payload must be a CRDT for the Merkle-DAG to be a CRDT. However, these payload CRDTs can be much simpler in their implementation because the bookkeeping on concurrent edits is delegated up to the Merkle-DAG.

It's as if a state-based CRDT was turned inside-out. The common bookkeeping elements are now the container (the DAG), and the payload-specific bookkeeping is inside of the payload CRDT.

Beyond simpler bookkeeping for payload CRDTs, Merkle-DAG CRDTs have an advantage that non-Merklized CRDTs don't. They can determine equality by comparing root hashes, and they can determine diffs by walking down the DAG.

This reduces the bandwidth for syncing between replicas.

1. A remote replica broadcasts its root hash to our local replica.
2. The local replica compares its root hash with the remote hash to determine if something has changed.
3. If the root hashes are different, it then asks the remote replica to send every node hash as it walks down the DAG from the root.
4. When the remote replica sends a hash that the local replica already has, the path from the root to this node is the list of all nodes missing in the local replica.

This is quite a bit of chatter over the network, but the hashes don't have to be delivered in causal order any more. Merkle DAGs are by definition a causal chain of hashes. Hence, the nodes can be reordered at the receiver, regardless of how they were sent, as long as all of the nodes were received.

An upside of keeping the Merkle-DAG is that the data kept by a Merkle-DAG is immutable. It can be reconstructed and queried at any point in history. Immutability means diffs are easy, undos are easy, and provenance can be verified. But again, the downside here is a history of changes that grows with the number of events. However, Merkle Trees uses structural sharing as a form of compression to lower the space cost of storing such a data structure.

Merkle Search Tree CRDT

The second kind of Merkle CRDT is covered in the Merkle Search Tree paper.

A Merkle Search Tree (MST) is a tree that maintains an ordered set of keys. It does this by maintaining a few invariants.

1. All the keys in a node are ordered.
2. All child nodes between two keys in a node contain entries lexicographically between the two keys.
3. The leaf layer is layer zero. The layer above is layer one, with increasing layer numbers until the root. The layer a key belongs to is dictated by the number of leading zeros in the hash of the key.
4. A node has a content ID that's a hash of all its keys concatenated with the content IDs of all its children. A child node is referenced by its content id.

Keys live in all nodes of an MST tree, unlike a B-tree where keys are only at the leaves. This construction makes MSTs advantageous in two ways: it is self-balancing and it is unicit.

A MST is self-balancing through both invariants #2 and #3. When a key is inserted in the tree, the layer is determined by the key's hash and the node in the layer is determined by the key's value. When the key is inserted in a node between two keys, it necessarily splits the child node between the two keys into two nodes due to invariant #2. Given a hash is in base B and invariant #3, the average number of keys in layer L is B times the average number of keys in layer L + 1. Hence, the average node size is B. Due to the placement of a key being completely deterministic, the tree self-balances.

Unicity means, for a given set of keys, the MST is unique. It implies the MST's construction does not depend on the order of the keys that were inserted. This is extremely desireable, because we can tell if two MSTs are different simply by comparing their root hashes regardless of the insertion order. If the root hash is the same, then the two trees are the same.

To construct a CRDT out of an MST, we simply add a payload to each key that's also a CRDT. Since the MST is an ordered set, merging sets have well-defined semantics, and merging the payloads is delegated to the payload itself to resolve.

And just like the Merkle-DAG construction, the payload CRDT doesn't need to be as complicated. For example, to construct a Grow-Only CRDT, we select the set { ⏊, ⏉ } (called "bottom" and "top" respectively) as the payload CRDT. All the values of the payload start as "bottom" by default. Merging means taking the max of "top" vs "bottom" (top always wins in a max operation).

Unfortunately, the paper leaves out the construction of other CRDTs using MSTs, as it was left as an exercise for the reader. However, there are two other possible constructions I think will work.

Causal Length CRDTs for add-remove sets could be implemented in MSTs with ℤ (the set of integers) as the payload. If the number is even the key doesn't exist, and if it's odd, then it does. Merging would just be taking the max of the two replica's payloads.

Replicated Growable Arrays (RGA) could be implemented by using virtual pointers concatted with the replica ID as the key. Since the MST keeps the keys ordered, we can read back the string by traversing in key order. This would need a mechanism outside of the MST to insert and assign tombstones for deletions. [^3]

Beyond that, there is an undetailed edge case. What if the key you're adding has a lot more (or a lot less) leading zeros in its hash than the number of leading zeros in the current root layer? Do you just add nodes in between the root and the new node? What should go in those in-between nodes? If there are no keys in these in-between nodes and just child content IDs, there would be no way to discern which child to descend into on a query. My guess is to simply insert a ghost key that doesn't exist in the set but only serves as a range bookend for queries. There are implementations to check out for details. [^4]

As for downsides, it's also vulnerable to attackers constructing a key with a large number of zeros and trying to insert it. That would result in a tall tree, reducing queries from O(log n) to O(n). And while the node size is on average B, the variance is spread pretty wide, so it can be common to have nodes that are too small or too large.

The surprising connection

After this and the previous survey on CRDTs, I came away with some clarity on them.

CRDTs need two main ingredients to work, a merge/application operator that's commutative and associative, and some bookkeeping to keep track of concurrent or causal edits. This bookkeeping is like an uncollapsed superposition of state while the system isn't sure if there are any more concurrent edits. If we can be sure that all replicas are synced, we can either collapse the state or simply throw it away if we don't need to travel back in time.

For typical CRDTs, this bookkeeping is internal, and you're given an interface to set and query, so one can pretend this is a regular state that can be updated in place. Merkle CRDTs turn this inside out, exposing the inherent structure of concurrent edits and uncollapsed state for users to see and exploit.

This mirrors closely with how Git is structured. That surprised me at first. But as I dove into Git's history, I found this tidbit in passing.

The important part of a merge is not how it handles conflicts (which need to be verified by a human anyway if they are at all interesting), but that it should meld the history together right so that you have a new solid base for future merges.

In other words, the important part is the _trivial_ part: the naming of the parents, and keeping track of their relationship. Not the clashes.
Linus Travolus vs Bram Cohen

The values are the contents of the file, and the bookkeeping on concurrent edits happens outside of the value. What stops Git from being a CRDT is that its default 3-way merge isn't commutative and associative.

As history proved, it's the bookkeeping data structure that's important for merges, not the conflict resolution itself. But in the case of CRDTs, it's important to constrain the merge with algebraic properties [^2].

The search continues

Merkle Search Trees have lots of nice properties, such as unicity, self-balancing, and a CRDT that doesn't grow with the number of replicas or events. But I think we can do better. For one, the variance of the node sizes is large in MSTs, which makes for uneven trees.

In my search, I found Prolly Trees, and will take a look at them. If anyone has other suggestions for data structures to look at to implement composable CRDTs, let me know. In the meantime, subscribe or follow me on twitter.

[^1] If you aren't familiar with the internals of Git, I'd recommend looking into it.  Git is the only piece of software where learning its internal data structure made it easier to use.
- Git Internals: Plumbing and Porcelain
- A Visual Guide to Git

[^2] The algebraic properties we need to maintain for a merge are commutativity, associativity, and idempotency. This forces every replica to arrive at the same merged state without coordinating with each other.

[^3] Of course, actual RGA implementations are far more optimized than this outline.

[^4] There are two existing implementations of MSTs.

• https://github.com/domodwyer/merkle-search-tree
• https://github.com/jrhy/mast

What are the trade-offs between different kinds of CRDTs (Conflict-free Replicated Data Types)? Most introductory talks cover just state-based and operations-based CRDTs because that's what the original paper formulated. But since then, there have been other variations, and I haven't seen much written about them in blog posts, so I'll cover their trade-offs here.

• State-based CRDTs (convergent CRDTs)
• Operation-based CRDTs (commutative CRDTs)
• δ-state-based CRDTs
• Δ-state-based CRDTs

The basics of CRDTs are covered in a lot of other different places [^1], so I won't try to speed run it here. Let's just jump into the differences.

State-based CRDTs (Convergent CRDTs)

In State-based CRDTs, a replica's state can be updated by a merge operation with another replica's state. But if the network is unreliable and can deliver events out of order, how would all the replicas achieve convergence and agreement of all their states? The trick is simply to restrict ourselves to data structures and operations that are immune to net-splits and out-of-order delivery.

First, the internal data structure of the CRDT must be monotonically increasing. Second, the merge operation has to be commutative, associative, and idempotent with respect to the internal data structures.

These constraints make the CRDT immune to the unreliable network. As long as all replicas eventually see every state update event, they're guaranteed to converge to the same state. Due to the use of vector clocks, replicas coming in and out of the network are easily handled. The internal bookkeeping grows linearly with the number of replicas.

The rest of the design problem is how to build useful data structures out of only monotonically increasing elements. Luckily, there is already a menagerie of CRDTs that can model numbers, arrays, maps, strings, and other common data structures.

State-based CRDTs are theoretically sound, but in practice, it has a glaring downside: they require sending the entire state of a replica over the network to other replicas. This can be prohibitive for all but the smallest states like counters and registers. That's because a CRDT needs to maintain internal bookkeeping of "which replica said what" at some logical time in order to resolve conflicts for any new state changes. The end-user queries this internal bookkeeping for a current value, like a functional view calculated from the actual state, the internal bookkeeping. For anything beyond a counter or register, this internal bookkeeping can be too big for sets and maps. And as the number of replicas grows, it can grow too big too quickly.

Therefore, most current CRDT implementations are not state-based but op-based.

Operation-based CRDTs (Commutative CRDTs)

Current practical implementations of CRDTs opt for a way to ship smaller pieces of data over the wire while retaining the same properties as a state-based CRDT. We will give up a merge function and instead use a defined set of operations that can be used on the state. It's akin to defining a command in an effect system. Like before, the operations will need to be constrained to give us the property of uncoordinated syncing between replicas. The operations will need to be both commutative and associative, but unlike the merge function, they do not have to be idempotent.

Without idempotency, the syncing protocol now cannot just be an out-of-order delivery of updates like in state-based CRDTs. Instead, we require the operations to be delivered in causal order. When a replica syncs and catches up to the latest state, the operations are applied in causal order. Any concurrent operations will result in the same state, due to the commutative and associative properties of the operations. We're shifting part of the complexity of the merge function into the sync protocol.

Our internal bookkeeping to converge to the same state with concurrent operations doesn't use vector clocks. Instead, we can keep a log of the causal history of all the operations that occurred. Our internal bookkeeping no longer grows with the number of replicas, but instead with the number of events.

Op-based CRDTs can scale easily with the number of replicas and with an unknown number of replicas that come in and out of the network easily. However, like blockchains, it has an ever-growing internal bookkeeping if it wants to allow any replica to sync regardless of how long it has been offline.

There are two ways to address this ever-growing bookkeeping. One or the other may be feasible depending on the requirements of your application.

The first is to adopt what accountants do: close books at the end of every month and quarter. All replicas keep a rolling window of the latest N days of data and throw away data that's older than N days. And if a replica has been offline longer than a certain number of days, then they cannot be expected to sync and will need to reload from the latest.

The second is to keep all the history, but find ways to compress it. This is what the CRDT library Automerge does. This can sound like a bad idea, but we already have software that keeps its entire history around that developers use every day: Git. Of course, not all application requirements allow us to do this, but in my opinion, we don't do enough of it. Disks are comparatively cheap now, and the benefits of immutability far outweigh the downsides.

To query for the value of an op-based CRDT, we can apply all operations from the history log to an empty state to get the current state. Alternatively, we can keep a cache of the latest state in memory and update it on every operation.

Delta-state CRDTs

Delta-state CRDTs try to solve the data-over-the-wire problem differently. Instead of breaking the merge function into operations to send over the wire, we try to calculate the minimum amount of state to send to other replicas to sync.

There are two versions of delta-state CRDTs. In the first δ-state CRDT paper, we do something similar to op-based CRDTs: we create a set of operations, called delta-mutators) that are used to update the state. But instead of sending these operations over the wire, delta-mutators generate a diff between the states before the delta-mutator was applied and after it was applied. The diff is then stored in a buffer to be sent out to all other replicas.

But this buffer isn't a queue. The buffer holds the diff between the current state and the state when the buffer was last sent to other replicas. This is possible because the delta-mutator diffs are composable. This means if we have two diffs, d₁₂ (a diff between State X₁ and State X₂) and d₂₃ (a diff between State X₂ and State X₃), the composition of the two diffs would be D₁₃ (computed with d₁₂ ⨆ d₂₃). Hence, the application of d₁₂ and then d₂₃ is the same as the application of the composition D₁₃. The paper calls these compositions, delta-groups.

And because the diffs exist in the same join-semilattice as the states, you can use the same merge function to merge the diffs received from other replicas into your own local state.

The second Δ-state paper takes a slightly different approach. While the 𝛿-state CRDT has a replica send the same diff to all other replicas, in the Δ-state CRDT, we notice that the information about which replica has which part of the state is already encoded in the vector clock internal bookkeeping of the CRDTs. Hence, we can tailor the diff that we send to each replica. Therefore, we can toss the buffer and calculate the exact diff of the state that another replica needs. But by trading off the buffer, you now need to keep track of tombstones.

Delta-CRDTs retain the idempotency property of state-based CRDTs but do not require lots of bandwidth to sync replicas.

The Search Continues

While all of these CRDTs have strengths and weaknesses, I'm looking for something where I don't have to compromise. Next time, I'll cover my search into Merkle CRDTs. In the meantime, follow me on twitter.

[^1]: Here's some introductory material on CRDTs I found helpful
- An interactive intro to CRDTs
- An introduction to state-based CRDTs
- CRDTs for non-academics
- CRDT: The Hard Parts
- Readings in CRDTs
- crdt.tech

I was surprised to learn that different stacks of software all do some type of computational analysis to better do its job. The CPU does it to figure out how to pipeline instructions. Compilers do it to feed CPUs better set of instructions. Front-end frameworks do it to figure out how to incrementally update the DOM.

We separate our tech stack into layers to make it more understandable, but it does seem like a pity that the same work is done multiple times. It might be one of those problems that seem the same on the surface, but it really isn't, so if you tried to unify them somehow, you'd get a big specification mess. Still, it does seem regrettable.

This brings me to caching. Caching is hard because the cache subsystem often has the least information about what has changed in the system. If the computational dependency graph was available to a cache, it'd know exactly what outputs to invalidate based on the inputs that were changed. Taken to the extreme, if you have this computational dependency graph, you can carry it all the way to the GPU. This only solves instances where we need to update caches initiated by a change in the data store. This is the problem of cache invalidation.

In the instances where we want to cache based on the user's actions, it's harder to know what to cache. This is not a problem of cache invalidation, but what to cache in the first place. A cache miss requires us to fetch the data as it's requested, which means we need to wait for new data when we've discovered that we're about to step off the edge of the world.

There are predictive techniques we can use to try to figure out what the user will do next, so we can do pre-fetching. I think this can be simplified if we know ahead of time the possible actions, and hence the new sets of data the user could possibly request. Just like there are only two ordinal directions on a map, if we had such a map–a state dependency graph, then we can pre-fetch the "next possible steps" ordered by likelihood so that the user would never fall off the edge of the world if they didn't walk too fast.

We currently don't encode this state dependency graph in any way, other than in HATEOS, which isn't in wide accepted use. But I think if we can have the same idea on the client, then it'd be able to ask the server for more data without involvement from the developer manually asking for data when the client is fetching data.

In the last post, I detailed the various problems that could be solved by an immutable database on the front-end. In summary, the four state management problems, and how they are solved by an immutable database are as follows:

• 1️⃣ State is a cross-cutting concern: Now we can query both UI state and server state from anywhere.
• 2️⃣ Weak equivalence hinders re-rendering: No more useCallback, useMemo, or key annotations to help optimize rendering. The renderer can figure that all out on its own.
• 3️⃣ Distance between code and data breeds complexity: Developers can treat server state as local using database replication. The data will automatically get synced.
• 4️⃣ State transitions need linear traces: Application state is now observable by querying the transaction log of the immutable database.

As an exercise to see what the developer experience might look like, I outlined what it might look like for a React-like single-page app. The app that's outlined below is a variation on the TodoMVC.

The Todo MVC

The outline is of a TodoMVC with a slight variation. It will have a side panel that holds details of the focused task. There will be a main panel with a list of tasks and a side panel with the details of the task.

Most of the uninteresting components will be at the end as a reference to fill in details, such as the data model and pure functional components. Let's focus on the interactive components with state.

Main panel: a list of tasks

Here's the main panel with a list of tasks.

let MainPanel = () => {    
    let tasks = useQuery(
    	{ find: ["?t", "?isDone", "?title", "?assignedTo"] },
        { where: [
            ["?t", "task/assignedTo", "?u"],
            ["?a", "app/selectedUser", "?u"],

            ["?t", "task/isDone", "?showComplete"],
            ["?a", "app/taskCompleteFilter", "?showComplete"],

            ["?t", "task/isDone", "?isDone"],
            ["?t", "task/title", "?title"],
            ["?u", "user/name" "?assignedTo"],
        ] })
    
    return <div>
        <TaskFilterByCompletion />
        <ul>
            {tasks.map((task) => {
                <TaskLineItem task={task} />
            })
        </ul>
    </div>
}

The main panel does two things: query for the tasks and show the list of tasks. The list of tasks can be filtered for done or incomplete tasks with the TaskFilterByCompletion component.

The front-end has an immutable database that acts as the store. It holds both the application state and the remote server state. In this case, it holds the task filter criteria (selectedUser and taskCompleteFilter) and the list of tasks respectively. This means the list of tasks can be retrieved with a join in a single query.

Side Panel: Task details

let SidePanel = () => {
    let user = useQuery(
        { find: ["?u", "?name"] },
        { where: [
        	["?u", "user/name", "?name"],
            ["?a", "app/selectedUser", "?name"],
        ] }
    );
    
    let task = useQuery(
    	{ find: ["?t", "?title", "?description", "?labels"] },
        { where: [
            ["?t", "task/title", "?title"],
            ["?a", "app/selectedTask", "?t"],
            
            ["?t", "task/description", "?description"],
            ["?t", "task/labels" "?l"],
            ["?l", "label/name" "?labels"],
        ] }
    );
    
    return <div>
    	<UserSelector user={user} />
    	<TaskDetails task={task} />
    </div>
}

In the side panel, we query for the user that's currently being selected, and the details of a task.

Because the state is accessible anywhere in the component tree, we can query for the application state here, and pass what we need down to the pure functional components. There is no useState to pull up and down the component hierarchy. There is no prop drilling from the top-level store. There is no top-level Context component to nest and split up to optimize rendering.

Interactive Components

The interactive components are where the action's at, so let's take a look at the TaskLineItem

let TaskLineItem = (task: Task) => {
    let db = useDb();
    
    let changeTaskTitle = useTx(
        { in: ["?id, "?title"] },
        { update: [ ["?id", "task/title", "?title"] ] }
    );
        
    let handleToggleDone = (_) => {
        db.tx({ "db/id": task.id, "task/isDone": !task.isDone });
    }
    
    let handleChangeTaskName = (evt) => {
    	changeTaskTitle({ id: task.id, title: evt.value });
    }
    
    let handleFocus = () => {
    	db.selectTask({ selectedTask: task.id });
    }
    
    let handleBlur = () => {
    	db.selectTask({ selectedTask: null });
    }
    
    return <li onFocus={handleFocus} onBlur={handleBlur}>
    	<Checkbox isChecked={task.isDone} onToggle={handleToggleDone} />
        <TextField text={task.title} onChange={handleChangeTaskName} />
    </li>
}

There is no query here, because the component is passed the task, but the query could have existed as just well here. When a database is immutable and local, there is not an N+1 problem, and just querying for a task when you need it within a component is not a problem.

Outside of a query for data, it has handlers and transaction queries to change the state. In handleToggleDone, the transaction is written directly inside the handler. In changeTaskTitle, the transaction can be specified as a locally reusable hook. Lastly, a transaction can be centralized across an application in a single file, so that state transitions for a particular feature can be seen all in the same place. It's also possible to add guards to these transactions, because they're effectively state transitions in a state machine.

// specify direct queries, or as a higher level state machine

let db.selectTask = useTx(
    { in: ["?selectedTask"] },
    { where: [ ["?a", "app/selectedTask"] ] },
    { update: [ ["?a", "app/selectedTask", "?selectedTask"] ] },    
);

We can ask the database all the state transitions that lead to the current value shown in a UI. When a user hits an error, the transaction events can be sent over to the developers to reproduce the bug exactly. This can drastically help debugging.

Query language

The query is modeled after Datomic's variant of Datalog. One realization after doing this exercise, is that while Datalog is powerful and simple to join, it's quite verbose.

A major requirement of any query language to make this work are two-fold:

• The query has to be parameterizable. The where clauses are usually filter conditions for the query that needs input from the user. We typically do string interpolation for raw SQL queries which is a security issue. ORMs do this right by make queries parameterizable. GraphQL also does this, but it's a little verbose.
• The query has to be composable. SQL does have subqueries and common table expressions now. GraphQL has fragments. Both are great help, but I don't see a lot of tools or organizing principles to help developers organize these into a useful library of composable queries.

I'll have to have a closer look at LINQ, CTE, and Imp to see if there's something that works for this problem.

References to other parts of the Todo MVC that isn't particularly important to the discussion, but help fill out the mental model:

Data model

The data model is a little bit more involved with task details such as labeled and the assigned user, but nothing too complicated.

type Task = {
    isDone: boolean;
    title: string;
    assignedTo: Option<User>;
    labels: List<Label>;
}

type User = {
    name: string;
}

type Label = {
    name: string;
}

Top level page

let App = () => {
	return <div>
    	<MainPanel />
        <SidePanel />
    </div>
}

Pure Display Components

let TaskDetails = (task: Task) => {
    return <>
    	<h4>{task.title}</h4>
        <p>{task.description}</p>
        <Labels labels={task.labels} />
    </>
}

let Label = (label: Label) => {
	return <span>
    	{label.name}
    </span>
}

Most programmers manipulated state directly ever since we first learned to program. We think of state manipulation as being inherently tied to programming. It's not until we've experienced being completely overwhelmed by system complexity that we start to learn one major source of that complexity is having to maintain, manipulate, and keep track of state.

As outlined in Out of the Tar Pit, a large source of complexity is due to state management. The sentiment is also echoed in various pockets of different programming ecosystems trying to find a better way.

Recently, I went back and looked for blog post rants on React, and reactions they produced on HN and lobsters (listed at the end of this post), and the following summarizes some of the major sources of complexity due to state management.

State is a cross-cutting concern

A source of complexity is that application state is a cross-cutting concern in an interactive app of even the most modest complexity. It's not uncommon for multiple sub-trees of an app to require access to the same data model. While "views as a pure function of state" is a good architectural choice, it also implies the shape of the view is the same as the shape of the data model. This isn't commonly the case.

For example, in an app like Figma, the data model for a visual element is used across all sub-components, such as the hierarchy sidebar, the attribute sidebar, and the main canvas view. This means the data model of the visual component can't live in any one of the three as there wouldn't be a clean way for the state of the visual component to be communicated across sibling branches of the component tree.

The advice for such a situation is to pull the data model up to the common ancestor of all three sections, which in this case is the root component. When we do this, there are downsides.

The application state now needs to be propagated all the way down to the descendant component that displays it. That requires prop drilling, which introduces a lot of boilerplate and manual threading the deeper the descendant lives. While we can use Context to forgo prop drilling, this choice can un-intuitively affect rendering performance. For large apps, Context often needs to be split and ordered so that the outer-most Context is unlikely to change.

Weak equivalence hinders re-rendering

React simplifies developers' mental model by modeling rendering as blitting the entire component tree onto the screen on every frame. In reality, it incrementally updates the DOM by keeping track of which parts of the data model have changed, and hence which component to re-render. However, it's hard for React to know when data has changed in every case because Javascript was not built with immutability as a core tenet. It doesn't have a good definition of equivalence to enable the rendering engine to tell when two objects or two functions are the same. Hence, it has a hard time telling if attributes have changed from the last render.

To compensate, React requires developers to give it hints manually using keys in lists, useMemo, and useCallback. Unlike types in Haskell, these mechanisms aren't tools to help think through the architectural design. Rather they are just bookkeeping you need to do to satisfy a performance issue with the renderer.

In the ideal case, the whole system would be able to propagate an incremental change in the data model through to an incremental change in the DOM model without manual annotations from the developer. It can do that if the underlying runtime and language could tell when two objects or two functions were the same or not from frame to frame.

Distance between data and code breeds complexity

Beyond managing the local front-end state, a modern interactive app has to manage the remote state on the server. When data is in a different place than the code that needs to operate on it, complexity ensues. A lot of things can go wrong when we try to get data "over there" where it is stored to "over here" where the code is, and we fail most of the time and paper over the results.

Web apps are naturally distributed systems. We could mostly pretend that they weren't in multi-page apps (MPAs) because the business logic lived close enough to the data that we could pretend they were in the same place. Any transactional writes could be pushed down to the database and any views were stateless, so we could blow it away for a new application state on any action. [1] The UI state was simply the URL the user was currently visiting.

This simple architecture was easy to build and scale in a distributed manner, but it sorely lacked the responsiveness of desktop apps for end-users. In a desire to mimic this responsiveness without reloading the entire page in this distributed environment, developers moved the UI state and certain business logic [2] to the front-end under the banner of single-page apps (SPAs).

What we gained in responsiveness, we paid for in complexity. Now that business logic was on the front-end, the server data is now "over there". So we now need a way to query, fetch, store, and apply the data from "over there" to "over here" over an unreliable network. And we need to do it while retaining state on the front-end.

As is well-known in the Eight Fallacies in Distributed Systems, this is a recipe for a whole host of additional complexity. To name a few:

• Deduping multiple requests for the same data into a single request.
• Knowing when data is out-of-date or expired.
• Updating out-of-date data in the background.
• Updates that don't trample on other updates from other users.
• Retry policy on failures.

React Query and Hasura Subscriptions can help mitigate a lot of the problems here, but they don't go far enough. Either move UI state and business logic back to the server and give HTML a more expressive language to declare responsive interfaces [3], or move the working set of data to the front-end, so it can be treated as local data.

State transitions need linear traces

Redux is an implementation of the Flux-proposed architecture of one-way data binding and serialization of state transitions. This made it much easier to reason about the effect of changing state over its two-way binding predecessors.

Effectively, it's a state machine that serializes states between state transitions in a reliable way. It's certainly a simplifying way to think about state changes, and it's a pity that Javascript is such an impedance mismatch that it generates a generous amount of boilerplate.

Modeling state management as a state machine is only a step up if the developer was previously just thinking about state changes as a nested series of if-else statements. While state machines bring clarity by making impossible states impossible, a state machine expressed linearly in text (even as a DSL) is still quite verbose. Unless there is a better notation, it can't be used as a design and thinking tool without graphic visualizations. [4] So if a developer was already thinking about reducers as state machine transitions, most of the benefit is actually from the serialization of state transitions.

With a serialization (linear list) of state transitions, it's easier to trace a history of changes to the application state using messages as labels of user intent. More importantly, serialization also brings deterministic reproducibility to state changes and leaves the potential for conflict resolution when there are multiple concurrent sources of change to the front-end store.

Pointing to an Immutable Database

This isn't an exhaustive list of the troubles with state management in front-end interactive apps on the web. However, they all seem to point to the same place: an immutable database for building interactive apps on the web.

Why does the front-end need a database for state management? Many of the problems listed above are problems that databases have solved before for backend or distributed systems. To start, one advantage is that databases centralize the access points for data and are accessible anywhere from the app. This helps solve the problem that state is a cross-cutting concern for even the most modestly complex app.

Databases have two other features that help the state management problem: serialized transactional writes and replication.

Databases have long dealt with the hard problem of coordinating writes between multiple clients with transactions. Databases also keep a serialized log of these transactions to establish durability guarantees in case of catastrophic events like power loss. Querying this log would solve the original problem flux attempted to solve. It'd be a way of tracing the effect of a state change on the entire visual component tree over time.

Databases also feature replication between primary and secondary instances. This can be used to fetch new data from the server to the relevant working set for the front-end. Currently, developers manually fetch data from the server. But to do it well, developers need to account for timeouts with retries, cache invalidation for performance, deduping multiple requests and batching them, and pagination with lazy loading of data, all for efficiency. Most developers simply don't handle these common edge cases, and just leave users with infinite spinners, slow loads, or inconsistent views. It's even more challenging when data was changed on the server by another client, and we need to push the change to the browser to update its view without a manual refresh from the user. By leveraging database replication, between client and server, the front-end developer can treat data as completely local and not worry about network-induced state management from the server. [6]

But why an immutable database? An immutable database is like other databases except that once data is written, it's never changed. To "update" a piece of data, the new data is appended and versioned. For example, a table storing the current President of the United States wouldn't delete the previous president when a new president is elected. The new president would simply be appended to the series of presidents as a new version.

Keeping every version of data sounds like it would take too much space. In practice, this isn't a problem. Typically, only a small part of the data in any dataset is updated at a time. Therefore the data between versions have most of their data shared in common. Immutable databases leverage persistent data structures that rely on structural sharing that exploit the commonality between versions. [5]

It's this persistent data structure and structural sharing that makes it easier for the system to reason about equivalence. Two objects are the same if they point to the same part of the data structure storing the data. We can also tell exactly how two different versions are different due to the structural sharing in the persistent data structure. With that, we can tell a renderer exactly what has changed, and what it needs to re-render in turn.

In addition, immutability means there doesn't need to be coordination for reads, because once written, data will never change. That drastically reduces the complexity of multiple users in a system.

Lastly, an immutable database isn't enough. It needs to support incremental queries. Typical database queries assume that the data is stationary and it's the queries that need to be flexible. Incremental queries turn this around, where it's the query that's stationary, but data is streaming in over time. Incremental queries are more commonly found in real-time streaming databases and systems for big data, but they can be useful in interactive apps for the rendering pipeline.

When the application state held in the immutable database changes, an immutable query can update its result and propagate the difference all the way to the rendering engine, which in turn can efficiently tell what visual components in the tree need to change. This simplifies the state management for developers because they no longer need to give hints to the framework about which parts of the app to re-render.

To sum up:

• State is a cross-cutting concern: A database would allow a component from anywhere in the app query for application state.
• Weak equivalence hinders re-rendering: An immutable database leverage persistent data structures, which makes it easy to tell whether data has changed or not between renders.
• Distance between code and data breeds complexity: Developers can treat application state as local, rather than remote using database replication. In an immutable database data will never change out from under a read.
• State transitions need linear traces: The database can also serialize transactions and provide an immutable log for tracing, regardless of where in the application the write is coming from.

A step back

All this hullabaloo about a database on the front-end is only necessary if we decide that our web app definitely needs to move the UI state and business logic to the browser. This isn't the only architectural choice we can make. In fact, Rails Hotwire and Phoenix Liveview take a different tack. They keep most of the high-level UI state and business logic on the backend, close to the server database, and only ship small UI state and a (mostly) immutable view to the browser.

And given the amount of state management problems in the state-of-the-art front-end frameworks, you'd do well to consider hard whether you'd actually need it.

But given that you do, I'd argue that the state management library front-ends are looking for is a database.

[1] Besides the user session cookie.
[2] Business logic outside of access control.
[3] Interestingly, this is the direction Rails Hotwire and Pheonix Liveview take.
[4] State management libraries that focus on modeling the problem as a state machine are mistaken for this reason.
[5] This is how Git stores its data on disk. Blockchains also use this data storage pattern.
[6] That said, the developer may still need to fetch data through a 3rd party API whose database he doesn't control. In this instance, it seems like algebraic effects would be better suited.

Problems with State Management in React-likes

• React I Love You, but You're Bringing Me Down
• Get in Zoomer, We're saving React
• The new wave of React state management
• Why React Context is Not a "State Management" Tool (and Why It Doesn't Replace Redux)
• Past, Present, and Future of React State Management
• Why I'm not the biggest fan of Single Page Applications

This is a review of all the resources I found and learned about persistent data structures in the course of looking for a solution for maintaining state.

Complexity from maintaining state

One of the hard things about programming is how to maintain and manage state, especially at scale. In interactive programs, this manifests itself as all the bookkeeping required to fetch data from remote APIs, send and retrieve data from the database, and maintain the state of the view not dependent on the data (such as the state of a pull-down or current animation state of a UI component).

In my search for prior art on the topic, I came across Datomic, a functional immutable database. It's a database you can treat as a value in the functional sense, rather than a "place" where you can fetch and update data.

Why is this a problem? It turns out that much of the complexity in our modern web systems stems from the problem of maintaining state "over there". This phenomenon is outlined nicely in Juan Pedro Bolivar Puente's talk.

When data can change out from under you after you read it, there's a lot of work to compensate for it. Without that work, it's hard for humans to reason about, because we tend to think and reason in a sequence where only one thing happens at a time. So we just start adding the complexity, thinking that there isn't a way out.

Immutability is the star

Some people get hung up about types in functional programming when immutability is the star. Immutability guarantees that something won't change out from under you after you read or write it. This single thing simplifies the architecture of our systems drastically when we can swing it.

But what about databases? Could databases, explicitly used for maintaining state, be used as a value? Yes, if the database never ever deleted a record, and updates are actually just writing a new version. That's Rich Hickey's insight when he built Datomic.

What would it take to build your own functional immutable database? You need your own persistent data structure.

Persistent data structures

Persistent data structures are immutable. Once written they can never change. Once you read it, you're guaranteed that some other thread isn't going to come around and change it. Any updates to the persistent data structures actually amount to creating a new version with the update, so any older versions stay intact.

Now, there's no coordination required from reading data, which simplifies the problem of reading data. Writing data also doesn't require coordination if a single source of truth doesn't need to be maintained. But if you want everyone to agree on a single view of truth, then writes typically needs to be serialized.

One objection to this scheme may be that it would take up too much space. In practice, each version of the data uses structural sharing. That's where new versions of the data structure reuse data that didn't change from the previous version.

Chances are you use version control software like Git, and it uses a very similar idea. Every commit structurally shares the files that didn't change from the previous commit.

I initially started looking at surveys and talks on persistent data structures.

• Persistent data structure survey
• MIT 6.851 Advanced Data Structures Lecture 1 [lecture and note list]
• Okasaki's Purely Functional Data Structures

I found them to be rather broad, so I started looking at specific tree algorithms. A good place to start for any database retrieval algorithm is B+ Trees.

I thought it was a good starting place to implement a B+ Tree in Rust to get familiar with the language [1]. Turns out typical data structures such as a linked list are bad starting points for Rust. These data structures usually have two pointers pointing at the same piece of data, which violates the basic ownership enforcement required in Rust programs. This required me to unlearn many of the things I learned when I learned C. The following were good reads on this topic:

• Rust Collections Case Study: BTreeMap
• Idiomatic tree and graph-like structures in Rust

After reading about the weaknesses of B+ Trees, and looking through a bunch of others, I happened upon the Hash Array Map Tries (HAMTs) by Phil Bagwell. I saw an implementation of this in the im.rs library. The confluence of im.rs, Bagwell's work on Ideal Hash Trees, and Clojure's own implementation lead me to Relaxed Radix Balanced Tries (RRBTs), a variation on the Radix Trie.

Radix Tries structures itself after the key, leading to large fanouts, and keeping all data at the leaves of the trie. By keeping the trie balanced as an invariant, we can achieve O(log n) lookups.

Clojure uses some variant of this, which is well described by L'Orange in his blog post series, as well as Krukow's posts.

• Understanding Clojure's Persistent Vectors, pt. 1, pt. 2, pt. 3
• Understanding Clojure's Transients
• Persistent Vector Performance Summarised
• Understanding Clojure's PersistentHashMap (deftwice...)
• Assoc and Clojure's PersistentHashMap: part ii

But specifically, RRBTs I found three main sources in Bagwell, L'Orange, Stucki, and Bolìvar Puete.

• RRB-Trees: Efficient Immutable Vectors
• Improving RRB-Tree Performance through Transience
• RRB Vector: A Practical General Purpose Immutable Sequence
• Turning Relaxed Radix Balanced Vector from Theory into Practice for Scala Collections
• Persistence for the Masses: RRB-Vectors in a Systems Language
• CppCon 2017: Juan Pedro Bolivar Puente “Postmodern immutable data structures”
• 🐙🐱 Magnap/persistent-vector-rs
• 🐙🐱 hypirion/c-rrb

I found that I had to piece together information from all of these sources to figure out an implementation. But once it's in your head, it's actually pretty intuitive. The most complicated method to implement is concatenation, as it has to keep a relaxed version of its invariants to guarantee its properties. But with both `concatenation` and `split`/`slice` you can implement insertion.

In the process of doing the implementation, OpenAI released ChatGPT. I tried using it to help, as an experiment.

I asked it to explain and convert the pseudocode to Rust. It was a mild success. While I couldn't use the code it generated, the comments and code in Rust made it more clear what was going on.

Defaults matter

Javascript has a bunch of immutable libraries, but to my knowledge, it's not overwhelmingly popular. I think languages like Clojure that build it in as a default have a leg up on other languages.

Immutable data structures should be the default in a new modern programming language, and mutation of state should be an intentional act by the programmer. The advantage of immutability everywhere you can swing it, even in places you didn't think you could before should be able to create wins in reducing complexity in our software.

[1] I decided to go with Rust instead of Zig, since I was a new systems programmer. I figured having the guard rails would really help. Turns out Rust is a really complicated language.

The first programs were more like programmable calculators. Fire it up with some inputs and wait for the output. Then in 1963, Ivan Sutherland conceived of a program that facilitated a continuous dialog between computers and humans. You could type or move a pen, and the computer screen updated in real-time. It was the first interactive program.

Though commonplace today, it was non-obvious and took a leap of insight to see it and its potential. But despite approximately half a century of building interactive software, we're still figuring out how to do it well.

The typical interactive program of today generally has this structure. Starting at the bottom of the interactive loop, a component tree is rendered on-screen. A user clicks on an interactive element, like a button, and generates an event. The event is sent to the state manager to update the application state. Then, the component tree is rendered as a pure function of application state, thus completing the cycle.

In The Broken Half of Interactive Programs, we focused on the stateful interactive side of the main loop (yellow box). In this post, we'll examine the side of the loop where we render components as a pure function of state (green arrow) [0].

What could be simpler? If all complexities of dealing with state are pushed to the stateful side of the main loop, then the functional render side is just dependent on its inputs from the application state. However, there are times when this doesn't hold true. What if the changes to the input result in state changes or view renderings that can't be computed fast enough to keep the user interface snappy for an interactive program? Reactivity to the rescue. It's a way to drastically reduce the amount of computation required to compute an output given a change to the input.

In this post, we'll cover the following:

• Establish why we'd want reactive systems from a user-centric view.
• Attempt to distill and identify the core problem in reactive systems.
• Discuss the tradeoffs for design choices addressing this core problem.
• Speculate on using composable derivatives for reactivity.

What and why of reactivity?

Reactivity is where a program recomputes state changes when its inputs change, at an environmentally determined speed (such as the user's clicks), and not by the program itself. Additionally, reactive systems allow a design where developers specify what the dynamic result should be, without specifying the how thus simplifying the system mental model for programmers. [1]

Why is reactivity a desired property for interactive programs? Interactive programs facilitate a dialog between human users and computers to find solutions to problems the human user is trying to solve. Practically speaking, making computers wait for humans is preferred over making humans wait for computers. The creative flow for problem-solving breaks when humans have to wait. When a program is slow, the human user never knows if the computer is still processing or if it has gotten stuck. It's rarely apparent whether to retry or how much longer to wait. This distraction becomes top of mind, rather than the problem at hand.

In contrast, a responsive interactive program helps the human-computer dialog iterate towards a solution. This dialog becomes a core loop where the user immediately sees the results of making a change. Each result generates ideas of what to try and change next. The quicker the cycle, the faster a user can iterate through a problem space in search of a creative solution. [2]

Games call this loop a core game loop, but we can simply call it a core loop. The time budget available to return a computed result is defined by how fast a human can cycle through the core loop (remember, we want computers to wait on humans). The faster the cycle, the shorter the time budget.

And yet, not all interactive programs require the use of reactive techniques. Games are the best example of interactive programs that rarely use reactive techniques. Why is this? A game's goal is to be fun, and fun derives from allowing the player to make meaningful choices in the simulated world. An exact accurate simulation of the world is often secondary (and sometimes in opposition) to the fun. Hence, a game can oftentimes get away with approximate answers, so they opt to use the simplest and fastest computation, not the most accurate one. This gives them much leeway to be fast without reactive techniques. [3] That said, there is recent work on reactive 3D scene rendering for the web.

However, there are still good reasons to use reactive techniques for both interactive and non-interactive programs. One reason is in domains that require exactly the right answer without redoing all the work. For non-interactive programs, good examples would be build systems and borrow-checkers. For interactive programs, the poster child is the venerable spreadsheet.

Another good reason to leverage reactivity is when the size of the dataset is too large to conceivably return a computational result in milliseconds through brute force. Even with fast computers, there are computational jobs that are beyond the reach of brute force to return a result within milliseconds. For example, streaming systems for big data often need to process petabytes of data. These systems leverage reactivity to make processing practical and tractable.

Lastly, a good reason to use reactivity is when a required external subsystem is too slow. For example, Front-end web apps render using browser DOM elements, which are well-known to be heavyweight objects that are expensive to create and destroy.

But then, why not just write imperative code to just minimally update the DOM? This can work, if the scope of the state changes required by the application is small enough. For example, if there's just a single list of elements to update, such as in a todo list or pins on a map. But just as manual memory management is manageable by a human up to a certain point, so it is with manually updating the DOM. A more complex UI with inter-relate parts, such as a vector drawing app is likely to tax a developer on what state changes should update which part of the view and when. At least in front-end web apps and Rust GUI ecosystems, we've found declarative one-way data flow modeling of GUIs to be an easier mental model of the system for developers.

A declarative interface, by definition, removes control from the developer so they only have to specify the what, not the how–the exact series of steps. This responsibility of the how doesn't go away. It's merely shifted from the developer to the reactive library. But now, efficiency is also the responsibility of the library. Reactivity allows front-end web frameworks to support a declarative interface while ceding control to the library to maintain efficiency by minimizing changes to the slow DOM tree.

In short, reactivity is a complexity that system implementers are willing to deal with in order to make the core loop practical when brute-forcing an exact answer isn't. [4]

The core problem

The design space for reactive systems is large, and different people have covered different sets of considerations subject to different constraints. At the end of this post, there is an overview of various posts on the design space for various reactive systems.

To summarize the various attempts to parameterize the design space of reactive systems, we ask: What is the core problem when designing such a system?

The fastest program is a program that does nothing at all.
- Programming Koan

To make a fast program, just never make it slow.
- Paul Buchheit

Fast programs are largely about exploiting the inherent data structure of a problem domain to avoid doing work. This can involve not doing work that you've already done, or not doing work that doesn't affect the final output. Grep is famously fast because it does so little.

Reactive systems model computation carefully to answer the question: If the input changes by this small amount, what's the minimum re-computation to get the same answer as the full computation?

To answer this question, creators of reactive systems need fine-grained control over the execution of code to decide which computations to recompute. We achieve this with two techniques commonly used together.

First, we ask the developer to rewrite their code more explicitly as a computational graph of data dependencies. In Apache Spark, it's a program with only the functional operators it makes available. In React, it's the react hooks with data dependencies relating them to one another. In build systems like Make, it's explicit file dependencies between build steps.

Second, the reactive system implements a scheduler to decide which computation should be executed and when. This is often embedded in the reactive library. For languages that don't allow runtime modification, such as javascript, the scheduler is implemented in userland. In fact, React is actually a runtime on top of a browser. [5]

Now then, should the system propagate deltas or should it perform diffs between the subsequent computational graphs?

Propagating deltas means that each node computes how a change in input will change its output. This change in output, rather than the output value itself, is propagated through the computational graph.

On the other hand, performing diffs means that we build an entire new graph on every cycle through the core loop. And then we diff the current vs previous computational graph to see what has changed.

In An Opinionated Map of Incremental and Streaming Systems, the difference between the two approaches is called unstructured vs structured systems.

Structured systems typically propagate deltas through the computational graph, but the downside is that they restrict the operations available to the user. Unstructured systems allow for any type of user operation, so it typically executes diffs. The downside is the implementation complexity, and if the update semantics aren't internally consistent, it is frustrating to debug.

This is a base design decision that affects everything else since that is the core problem: it's the mechanism by which we determine whether or not to recompute. Let's compare the trade-offs between the two designs.

The limits of a structured system

Structured systems restrict the set of operators available to the user. But with this carefully picked set of functional operations, deltas can be propagated through the entire computational graph. Streaming frameworks seem to favor this design. For example, Differential Dataflow propagates deltas along with multi-dimensional counters to label intermediate computational results at different points in time and in loops, so it knows how to combine them correctly when all of the input data for an output data has been seen.

Because we know what has changed, rather than just that something has changed, we don't need to perform tree diffs or define equivalence. All the problems in unstructured systems mentioned above are answered by the delta.

Why not default to propagating deltas in all reactive systems?

It seems to be partially a cultural stumbling block. Structured systems would require mainstream developers to rewrite their algorithms in this limited set of functional operators. Given the limited (but growing!) popularity of functional programming, it's a tall ask. Big-data streaming systems have orders-of-magnitude bigger workloads than front-end web frameworks, so the choice of delta propagation over tree diffs is likely because of performance. If a limited operator set is the trade-off for performance and tractability of large problems, users of streaming systems are more than willing to make that trade.

That said, even if this trade-off was made willingly, it can be hard to use. MapReduce is famously hard to translate into queries by hand, and even functional systems like Apache Spark provide more operators than just map and reduce now for jobs that query. It now has a SQL variant on top of the functional language for this very use case.

The baggage with unstructured systems

In unstructured systems, we can allow arbitrary computation, but because unstructured systems don't propagate deltas, it has to take the diff between the previous application state/tree and the current application state/tree in the computational cycle. It has to have an answer to the equivalence question: "what does it mean when two things are the same?", so it can make decisions about whether or not to recompute and in what order.

Why would that be difficult? Equivalence is already a subject of debate amongst mathematicians, not to mention amongst programmers. Some software systems treat things with the same memory location as equivalent. Other systems treat pure functional computational nodes with the same inputs as equivalent.

These attempted one-size-fits-all answers are problematic. They're insensitive to the problem domain's inherent data structure that yields exploits for faster execution. One class of these exploits is to skip recompute when changes to input don't change the output in a meaningful way. For example, if the problem domain is compiling code, changing a comment shouldn't trigger a re-compilation. Hence, many of these unstructured systems have a default consistent and predictable (if dumb) recomputation heuristic but leave an escape hatch ajar for the user to override for their specific domain.

But leaving it up to the user to wire up case-by-case is a recipe for bugs and glitches, and it's easy for a user to get it wrong and end up with a hard-to-debug system. If a computational node decides to re-run more often than needed, then it is over-subscribed. (correct but not efficient) If a computational node decides to re-run less often than needed, then is it under-subscribed. (minimal computation–but at worst incorrect answers, at best just glitchy intermediate answers that are hard to debug) As The Incremental Machine and An In-depth Explanation of MobX both noted, this is a cache invalidation problem in disguise.

How come it's a hard problem to know when the data changes in unstructured systems? We know exactly when the data changes--it's when the dirty bit gets set. The reason we set a dirty bit is that triggering recomputes at this moment would result in updating all the children to intermediate values. This means that those children might be processed again as we traverse down the computation graph. Until all nodes have been marked, the process doesn't have enough information to ascertain the minimal set of computational nodes to run for the correct output. The decision of whether or not to invalidate cannot be done locally, one step at a time in a single pass.

Other complications

So far, we've mostly considered this problem of designing reactive systems as deciding whether or not to recompute specific nodes of a computational graph. The other knobs for tweaking the design of reactive systems have to do with how they would work with other commonly used language features.

Some of these systems don't allow for loops and functions. It is true you might not need a loop to iterate across datasets if you have a map operator, but what if you need loops to iterate across time and across a core loop cycle? Sometimes it would be needed to iterate a dataset to a fixed point. How would reactive systems model functions? Is it possible to reuse parts of the computation graph, or even pass it around to insert dynamically? Self-adjusting computations explicitly address this use case.

The problem of reactivity is complicated when a computational node in our graph has a data dependency that lives outside of our system across the network. How closely the application is expected to sync with remote data? Does the node wait forever for data? How often should it check? What happens on error, and should the user know? Most of these questions can't be answered by the reactive system and are left to the user to manually hook up. As a result, it's often error-prone and feels glitchy to the end-user without a concerted effort and attention paid by the developer. [6] This is a problem most acutely felt by front-end frameworks, since streaming systems typically have a reliable data store to draw from.

That's not all. A reactive system's design is further complicated if the system is expected to handle old data. Since some of these formulations of reactive systems keep internal state–such as when a fold is supported as an operator–complications arise when parallel or concurrent computation is introduced, such as data races. That's where front-end frameworks fall over, as they're not built to address these problems, and people reach for streaming systems built for big data with all their constraints.

These complications are mentioned for completeness, rather than as an attempt to address them. The decision of whether and how much to recompute is at the heart of the problem, and the two approaches between structured and unstructured are limited in their perspective ways. Is there a way we can have the best of both worlds?

Does Discrete Differentiation exist?

In this search through the current state of reactive systems, one question loomed in my mind. As opposed to the common numeric differentiation, does discrete differentiation exist? For example, how would we compute, represent, and compute the derivative of a functional operation such as string append? More importantly, is there a Chain Rule for almost any functional computation?

In numeric computations, if we want to compute

f(xt) where xt = xt-1 + Δ

(current input is the previous input with a little change), we can take one of two routes. We can either compute it directly or we can compute

f(xt-1) + f'(Δ)

In reactive systems, we'd prefer the latter if f(xt) is expensive to compute, but f'(Δ) (the derivative) isn't.

Just finding the derivative of a specific function isn't enough. To remove the constraint of limited operators, we want a Chain Rule to help us compose the derivatives. The Chain Rule would compute the compositional delta from end-to-end. That means we wouldn't need to calculate diffs between trees, mark dirty bits, or worry about equivalence problems when comparing two trees. It would also be internally consistent as inputs changed.

What are some open questions?

In addition, not all operators have a delta to propagate. Cryptographic functions like SHA256 are, by design, incrementation proof. The whole point of their design is to generate outputs that are statistically white-noise when their input changes a little bit. But even if most functional operators had a delta, it's not yet clear to me what it would look like for classic operators like append, concat, push, pop, etc.

And as often noted in introductions to auto-differentiation for deep learning, symbolic differentiation for numeric computations often becomes untenable because of the combinatorial explosion of terms as you take the nth derivative. The deeper the neural network, the higher the derivative. Worse, the terms from one function are often repeated and entangled in different parts of the entire expression–a result of a composition that doesn't compose cleanly.

What would a possible solution look like? The closest thing I've come across is Conal Elliott's Compiling to Categories. [7]

Compiling to Categories

The idea is to compile a program into a category theory representation, called Closed Cartesian Category (CCC), as an intermediate representation (IR) of code. We can then use a "template" to compile this IR into anything else. In our case, we want to compile into functions that propagate deltas but also still compose.

In Conal Elliott's demos, he compiles a short program into CCC. And then, using a "template", he can compile it into a graphical DAG representation.

Then, with the flick of a different template, he's able to compile the same code into Verilog, a language for programming FPGAs. With another, he's able to compile it into GLSL for a GPU.

But the real magic happens when we compile the IR into code with functions that are function-like but aren't traditional functions–they're embellished in some way.

One such example is functions that keep track of their deltas–differentiable functions. Differentiable functions are useful for constructing neural networks with auto-differentiation since manually writing derivatives for each layer is error-prone and hard to debug. With a template, he's able to compile a program to be auto-differentiable.

Auto-differentiation isn't a far stretch from incremental and reactive systems. And indeed, he has a section where he addresses incremental systems. [8] The purported advantage of this construction of a reactive system is that differentiable functions compose cleanly, and it doesn't hold state, hence making it easily parallelizable.

Discussion

While reactivity is deceptively simple when pure functions are involved, it's easily complicated by temporal locality, the choice of propagating differences, and how equivalence is determined. All of this complexity is absorbed by the implementor in hopes of providing a logical model for the end user that is functional (or declarative), and will run fast enough to produce a result in the short time allotted by the user's core loop cycle speed.

It's intriguing whether this construction of compiling to and from Closed Cartesian Categories can yield a process by which reactive systems are much simpler to build and maintain. Even better if it yields faster systems with more flexibility in operations.

Could reactive systems be more broadly used to build databases and query languages? The answer seems to be yes. Differential Datalog and SkipDB are two attempts in this direction. Could we build a runtime that is reactive by default? Could we provide a better developer experience with a reactive compiler? Or will it just collapse on itself with complexity and be hard to use/debug due to inconsistencies?

Through all this, it may not be worth doing any of it at all, depending on the domain. Today's computers are faster at doing math, than it is at loading data from memory. Memoization may be slower than just redoing the computation all over again. It'd really have to be an order of magnitude slower than loading from main memory for these techniques to be worth it.

That said, it's clear to me that the current technique of diffing states in unstructured systems has lots of problems, and that propagating deltas with composable constructions seems like a more promising way to go.

Many thanks to Eric Dementhon and Sri Thatipamala for reading drafts.

Supplemental overview of the design space for reactive systems

Towards a unified theory of reactive UI focuses on reactive systems for building GUIs in Rust. The primary mental model is simplifying GUI rendering as a pipeline of steps transforming application state through intermediate representations to become a set of draw calls to the GPU. The design decisions for such a system are:

• data structure vs a computational trace. The representations of various states after transformations can either be a tree data structure or an execution trace (a linear order of instructions).
• push vs pull interface. Is code recomputed through a function call (pull), or are changes notified to those subscribing to those changes (pull)?
• explicit deltas vs diffing. To implement a declarative UI and to provide incremental computation, we'd need to discern what has changed. Should we propagate deltas from cycle to cycle in the core loop? Or should we diff the current and previous trees representing state in the pipeline?
• identity by: object reference vs key path vs unique id. Lastly, given a changing state tree from cycle to cycle, how do we get a stable identity for nodes requiring change?

Build Systems a la Carte focuses more on build systems. While different on the surface, it's effectively the same problem that GUIs try to tackle. A build system must be a) correct and b) rebuild out-of-date keys at most once. By correct, it means when the build system completes, the target key and all its dependencies should be up-to-date. And build order of the out-of-date keys should respect their dependencies. Hence, it focuses on two key design parameters that are orthogonal:

• What order to build. This decision ensures the dependencies of a computational node are computed before the node itself is computed.
• Whether to build. This decision ensures nodes aren't computed more than needed.

An Opinionated Map of Incremental and Streaming Systems, on the other hand, breaks down the variety of reactive systems into a decision tree.

• Structured vs Unstructured. Structured systems restrict the operations available to the user, and they typically propagate deltas through the computational graph. Unstructured systems allow for any type of user operation, and typically execute diffs between the current and previous computational graph to determine which nodes require recomputation. (similar to explicit deltas vs diffing mentioned above)
• Low Temporal Locality vs High Temporal Locality. For streaming systems, data can arrive out of order. How do we incrementally update the result when old data arrives (low temporal locality)? Or do we have a tight window where we ignore old data (high temporal locality)?
• Internally Consistent vs Internally Inconsistent. When systems are incremental, the internal state will vacillate as values stream into the system. The systems that aren't internally consistent could be in a state that doesn't make sense when read. This can be a problem. In GUIs, this manifests itself as visual jank when a page is loading.
• Eager vs Lazy. An eager system actively computes new outputs whenever the inputs change. A lazy system waits until the output is requested. Lazy systems, however, can't be used for monitoring use cases.

Breaking down FRP focuses more on reactive systems for web apps. It identifies the variety of properties you'd want from a functional reactive system, but notes you can't have them all in the same system. They are trade-offs that you'd have to pick and choose. The following properties are

• History-sensitivity. How do we redo our computation incrementally when old data shows up in our front-end? (similar to temporal locality above)
• Efficiency. This refers to both space efficiency and computational efficiency. Minimize both the amount of past to remember, and minimize the amount of recomputation on an input change. However, it's hard to have both.
• Dynamism. This is the ability to reconfigure the computational graph over time, as a response to changing input. But a dynamically changing graph makes it harder to determine what it should do when old data shows up.
• Ease of Reasoning. Clean semantics that makes it easy to reason about the behavior of the system. (This is related to internally consistent vs internally inconsistent above)

[0] A survey of unidirectional front-end architectures shows us some variations.

When people say UI is a pure function of state, the state they're referring to is application data, not the state of various widgets. While you can consider widget states as part of the application state, it's too fine-grained. The end user rarely cares about the state of a widget.

[1] Some choice quotes on a definition of a reactive system.

The essence of functional reactive programming is to specify the dynamic behavior of a value completely at the time of declaration
https://svelte.dev/blog/svelte-3-rethinking-reactivity

Reactive programs maintain a continuous interaction with their environment, at a speed which is determined by the environment, not by the program itself.
Gérard Berry (RR-1065, INRIA. 189)

[2] In Inventing on Principle, Bret Victor puts it in a different way.

...here's something I've come to believe: Creators need an immediate connection to what they're creating.

And what I mean by that, is when you're making something, if you make a change or you make a decision, you need to see the effects of that immediately. There can't be a delay, and there can't be anything hidden.

In fact, most consumer-facing applications are of this nature: playing games, writing emails, constructing 3D models, and more.

[3] There are other reasons games are fast, such as using languages that allow for SIMD. That said, the data pipe to the GPU is slow, so games tend to batch up all the triangles it wants to draw and push them out to the GPU all at once.  

[4] I'm referring to the complexity we're willing to deal with as implementers, not as client-user developers.

[5] It seems both Haskell and Julia allow a programmer to change the runtime. Wouldn't be surprised if both Lisp and Smalltalk allow this as well.

React is a runtime because it actually has a scheduler that decides when and how much to run the hooks and rendering. It will yield to the browser when its time is up, and resume where it left off when it regains control from the browser.

Not all front-end frameworks are runtimes. Svelte, takes a different approach. It compiles reactive code into imperative code. It is the imperative code that is run in the browser.

[6] Immutability and passing of values help here. If interested, Hyperfiddle and Datomic offer a refreshing look at the problem here.

[7] Conal Elliott is the originator of Functional Reactive Programming, which influenced Elm, which in turn influenced Redux. But since then, he's moved on to this idea of compiling to categories.

[8] Incremental Computation is discussed in section 7.6

We still don't know how to structure interactive programs.

In the last couple of years, web front-ends evolved quickly to converge to a design with two subsystems that depend on each other. The first subsystem renders components in a view as a pure function of application state. The second subsystem leverages a state manager and some way to deal with side effects to provide interactivity.

This interactivity not only responds to user input, but also to network messages. While most front-ends today have largely agreed on the design of the rendering subsystem, we seem to be grappling with design of the interactive subsystem. We devise different ways to deal with side effects without clear tradeoffs. We can't decide where state should live, and how to manage state changes in a flexible way.

What should the the interactive subsystem of the program look like to keep the render side of the loop functional?

If you have any insight into this, email me or tweet @iamwil.

The evolution of front-ends

Front-end architecture for the web has evolved quickly in the last couple of years. Early on, front-ends weren't much of a program. It was a hodge-podge of event handlers, and as the front-end grew in size, the corresponding complexity grew even faster. It became a rat's nest of dependencies of a component's state with incoming changes from both the user and the server.

This complexity only worsened with the desire to give users a low latency experience. To that end, we now build Single Page Apps, which manage their state in addition to handling user events and server updates. It became hard to keep views consistent both internally and with the state on the server.

We needed a way to organize the front-end programs.

To that end, circa 2010, we've had a slew of front-end frameworks such as Backbone, Knockout, Ember, and AngularJS, all with differing opinions on the topic. ^[1] Around 2013, React introduced a simplification of front-end programs using functional concepts and the virtual DOM to bring immediate-mode rendering to web developers. And in 2015, Redux introduced a reducer as a sequential message processor to manage state changes.

While we've had other libraries since then to challenge React and Redux, we seemed to have stabilized on this architecture that pairs functional rendering with one-way data flow with a managed state/effects. These two halves of the architecture are tied end to end to form a core loop of our application that makes it easier to reason about.

The Core Loop

The core loop of most front-end architectures looks something like this:

1. One-way data flow from the state at the top of the application down to the rendered components. ^[2] Components are a pure function of state.
2. User actions are handled in the component rendering the UI. The handler emits messages to the state manager. The state manager changes the state based on the message.
3. State changes trigger a re-calculation and re-rendering of the components.

Hence, the core loop of the application is easy to understand. On one side, application views are rendered as a pure function of the state. We can call this the render side. On the other side, user interactions invoke state changes that trigger re-renders. We can call this the interaction side.

It's worth noting at this point this design has analogs in other ecosystems. In enterprise back-ends, there's a design pattern called Hexagonal Architecture (or more aptly named: "Ports and Adaptors"). It makes the general recommendation: write applications with a functional core, and an imperative shell.

"Functional core, imperative shell" encourages programmers to build the core of a program with pure functions until the point where the program needs to interact with the outside world. This happens at the boundaries of the program, such as user interactions, databases, and the network. At that boundary, use an imperative shell to manage these side effects.

We see web front-end applications converging on the same design. Let's look at each side in turn, though we'll spend more time on one than the other.

The Render Side

On the render side, we can see it has an analog in games. Before React, front-end programmers had to maintain both the application state and the DOM state in sync. Syncing these two states can be hard to do consistently and is error-prone. It contributes to the complexity and can introduce view consistency bugs. React introduced immediate-mode rendering to web developers without calling it that.

In games, a frame is rendered entirely from the game state. No rendering results from previous frames are used to render the current frame. In other words, rendering is a pure function of state. While this can make a rendering API more low-level, it frees the programmer from syncing the application state with the renderer's state.

The advantage of this architecture is that the core is much easier to reason about and test. Pure functions are only affected by their inputs. And one doesn't need to mock up a graph of objects just to test a pure function.

… Because the problem with object-oriented languages is they’ve got all
this implicit environment that they carry around with them. You wanted a banana but what you got was a gorilla holding the banana and the entire jungle.
- Joe Armstrong, creator of Erlang Programming Language

The front-end library and ecosystem in Javascript seemed to have converged on a functional design on the render side. I won't expand on the benefits of functional programming here, as that is covered elsewhere. The current design issues rest on the other side of the core loop: the interaction side.

The Interaction Side

On the interaction side, the story is a little bit more complicated. On this side, a programmer has to contend with both user input and network comms with the server, both commonly regarded as side effects.

While pure functions are easier to reason about and test, it's impossible to build useful programs with just pure functions. Many useful programs are interactive programs that need to respond to user input or the outside world through the network. That's why we have an interaction side of the loop.

But by their nature, handling user interactions and network responses are not pure functions; the output of the side effects depends on inputs that are outside of the program, and hence outside of its control. To keep the useful design of a pure functional core with interactive elements, we're forced to push all side effects to the boundaries of the program. Then the question remains, how to best handle the impure interactive elements? This is where front-end programs and the larger functional programming communities differ.

Effects with Monads

In contrast to enterprise back-ends that use the hexagonal architecture, pure functional languages like Elm and Haskell, a program cannot explicitly execute side effects. When the pure functional core runs up against the boundary of the program, it uses monads and monad transformers to compose these side effects together. The composed side effects are queued up for the underlying runtime to execute. In Elm, they're called commands, and in Haskell, they're called I/O monads. One can think of it as using commands and I/O monads to tell the effects manager in the runtime what side effects to run.

On one hand, effect managers have the advantage of keeping the rest of the program purely functional and decoupling the event handler from the state manager. However, control flow is now harder to follow and no longer explicit. Typical stack traces are useless here, and we'd have to use other tools to trace a message across the effect manager to its corresponding state update. To complicate tracing, a single event can emit one or more messages for state updates.

Effects with Algebraic Effects

Monads and effect managers aren't the only solution to dealing with side effects at the boundaries of a program in a pure functional language. Experimental languages such as Eff and Koka both feature algebraic effects as a way to manage side effects.

An algebraic effect is like a resumable exception. Instead of using the underlying runtime to execute side effects, the programmer implements the side effect in what looks like a "catch block". The side effect can then be invoked anywhere in the "try block", even if it's invoked deep in the call stack. An invoked algebraic effect will jump back up to the "catch block" to execute the effect, and then resume back where it was invoked after the effect has been completed.

The only design I know of that remotely leverages algebraic effects on the interaction side are React Hooks. Unlike Redux and The Elm Architecture (TEA) which keep all application states at the root of the component tree, hooks allow us to choose at which level state can live in the component tree. This can be useful for scoping view state, such as which dropdown was selected, to its local component tree. If the view state needs to be seen across sibling components, we have the option of pulling it up to the lowest common ancestor. Hooks also keep the view and relevant state together, which is easier than tracing messages across the effects manager to discern how a message would change the application state.

Effects with Linear Types

Lastly, a less well-known method is using linear types to manage side effects.^[4] Linear types are a type system that restricts a program to only a single reference to a variable. Side effects, such as network fetches, rely on the state of the world for their output. Since we can't rewind and rerun the world, it's impossible to do a network fetch twice and guarantee the same output as a pure function. Hence linear types are a way to constrain the programmer to make sure a side effect is never run more than once.

I don't know of any front-end interaction side design that leverages linear types. Perhaps there are Rust GUI libraries that would count. If you know of any with an interesting design, let me know.

Much of the effort from functional programming has been on how to deal with side effects at the boundaries. But for the design of the interaction side, there are other things to consider. Let's explore a couple below.

Where should state live?

As mentioned earlier, Redux and TEA keep a single global state at the root component, with a single reducer to manage state changes. Global state is possible because writes are sequenced linearly by the underlying runtime, and we're not subject to unpredictable data races.

On the upside, we can see all our state changes and updates in one place, the reducer. The reducer is usually implemented as one big case statement, but it should be seen as a finite state machine (FSM). With it, we get the advantages of an FSM: we can enumerate all good states and their transitions and make impossible states impossible.

Another upside of keeping all application states global is that it becomes trivial to implement infinite undo and time-traveling features. However, I've rarely seen web apps leverage this. This is probably because outside of database-less web apps, this requirement would cascade supporting undo all the way into the database, which is no easy thing, as most databases mutate in-place.

The downside is that it's hard to get the granularity of the state updates correct. If it's too fine, the event handler may need to generate many messages for a single user action, which makes it harder to trace and debug. If it's too coarse, the programmer may find duplication between the different state changes in reaction to messages. In addition, with actions that fetch data over the network, there often needs to be intermediate states that represent the state of data while in transition and error to account for network failures. And while Redux has the concept of sub-reducers that compose, in practice, I found it cumbersome to move state changes in reducers up and down to keep the code organized and in lock step with my current understanding of the domain problem.

Additionally, an application may need to keep two different types of state, a domain-model state (i.e. list of todos that have been done) and a view state (i.e. the selected dropdown in a list of todos). In an application with global state, reusing the same component in another part of the app requires adding a new global view state. This is extra bookkeeping a programmer would need to keep track of. Hooks are better in this regard by bundling the view state of a component entirely within the component. Reusing a component involves just using the component, and not about coordinating the global view state with the component it references.

How should state be referenced?

A fundamental assumption of React is that the structure of the state tree largely matches the structure of the component tree. But this isn't always the case. In an illustration app (like Figma), the state of a shape (such as its x, y coordinates) has a single source of truth. However, that state is being referenced in the following sibling components: in the main canvas to draw the shape, in the right sidebar to show its relation to other components, and in the left sidebar to display its properties.

In a case like this, the recommendation is often to pull the shape's state up to the first common ancestor between all the siblings. However, in React at least, this has the issue of forcing unnecessary re-renders in sibling components that don't use the shape state.

Recoil is another state management library from Facebook that tries to solve this problem by introducing querying of the state, which decouples the shape of the data from the shape of the component tree. Solid.js claims to only render all components once, but rerun all its hooks, so it may not have this problem.

What if we make time explicit?

What if we make time explicit? If we treat user interactions not as a lone event in time, but as a signal of user interactions over all time? That way, we can treat it as an immutable value that we can plug into pure functions.

Well-read readers would recognize this is what functional reactive programming (FRP) poses as a solution to structuring the interaction side of the core loop. ^[3]

On paper, it doesn't sound like a bad idea. However, we've done that experiment once. Elm started as a language embracing FRP, but decided to say farewell to it. It turns out TEA killed off FRP in the name of ease of learning and understandability. That may either be an indictment of the method or that most programmers weren't conceptually ready for it back then.

But perhaps it just needs to be introduced in a different guise. Solid.js uses a hooks-like API for its state, but instead of calling it createState, it's called createSignal.

How should state be updated?

What if state was versioned instead of updated? States would be considered immutable and append-only. We could treat the entire future and history of the state as a value, where previous versions are immutable and future versions are also immutable, but just not yet revealed to us.

At first thought, immutable state should make renders faster, because it'd be easier to compare equality to decide whether a component depending on a state needs to re-render or not. The immutable values could also be shipped around and make it easier to communicate with remote resources like the server's database. However, it also means that state would need to be garbage collected when old states are no longer being used or referenced, and this might impact performance.

However, as I describe this, it sounds suspiciously like FRP, so I might have to make a separate post to figure out the implications.

What about in games?

As a passing thought, what do games do? They're the most interactive of all programs, to the point they're considered a medium.

But as far as I can tell, they don't do much hand-wringing. They just mutate state and be done with it. While the rendering system is a pure function of state, that's largely handled by the game engine. Most game code deals with the state imperatively, and I don't know of any games that are written in a functional language. However, the best game programmers understand the value of a functional style in their programs, so at least there's some agreement on the "functional core" part.

How do games manage updating game state in a manageable way? I do know that finite state machines are commonly in use. And state can get complex with open world systemic games, where the desired property of the game is a combinatorial explosion of behaviors from a combination of game mechanics, such as cats vomiting in taverns in Dwarf Fortress.

But overall, I'm less familiar with what developers typically do here, the problems they run up against. Let me know if you know.

Discussion

In summary, it seems like the properties we'd want in the interaction side are the following:

1. View state and its transitions should be bundled by default with a component to make it easier to reuse the component. The view state and its transitions can be separated from its default component if necessary to make variations, such as dropdowns with or without search.
2. Domain-model state should be accessible to any component but scoped if necessary to avoid re-rendering.
3. State managers are finite state machines. It should be easy to group states and transitions for reuse and composability. It should be just as easy to break a grouped state into its component states and transitions to refactor.
4. State management should include pre-built states and transitions to handle network fetches, waits, and failures.
5. User actions and server pushes should be traceable from the event emittance, through the application state changes, all the way to the re-rendering of the components.

Taken together, I wonder if an in-memory database with some type of restricted update semantics would be what I'm looking for.

Do these problems and properties resonate with you? Are these systemic problems that you see in front-end libraries and architectures? If you have thoughts or insights, let me know.

Thanks to Sri Thatipamala for reading drafts.

Photo by Vanessa Loring

Today’s web developers are distributed systems engineers, they just don’t know it yet. And unfortunately for them, most languages and tools fail programmers exactly when they need them most: in a world full of network boundaries.

Programming languages help with complexity stemming from shared mutable state inside a program, but not across network boundaries between programs. This is especially true of web apps, commonly with two network boundaries. ^[1] We could initially ignore it, circa 2007 by pushing shared state down into the database and treating browser pages as a pure function of state. But today with single-page apps keeping state, serverless cloud functions, and microservices backends, this is no longer the case.

I think much of the complexity can be tamped down if we had practical abstractions across these network boundaries. What should they look like? Or are network failures an inescapable complexity that we can't abstract over?

If you have any insight into this, email me or tweet @iamwil.

The network boundary

Let's pick on pure functional programming for a second. It deals with shared mutable state by banishing mutable state within a program altogether and pushing it to the edge of the program. Then I/O monads and algebraic effects populate the edges to keep out the mutable world.

However, pure functional programming has nothing to say about composing programs across this network boundary. ^[2] And it's not just pure functional programming. Most languages and paradigms address complexity stemming from shared mutable state within a program by constraining the context in which state is used.

For example, Rust's smart pointers and ownership rules make it explicit who can update a variable at any one time. Clojure's atom/ref/var/agent reference types achieve a similar end along different dimensions. The Hexagonal Architecture preaches a pure functional core with an imperative shell. ^[3] None of these address the composition across the network boundary.

While Java (along with its JVM ilk, Scala and Clojure) are often used to build distributed systems and web apps, these languages and their ecosystem of libraries also make it apparent when you're reaching across the network to another program. As for Javascript, the most popular language for web apps, it has little to no support across the network boundary either, needless to say. ^[4]

The only languages that directly address this are ones that were designed to build distributed systems from the get-go. Erlang/Elixir leverages the actor model and message passing over the network. Pony uses a type system to check that code is dead-lock and data-race free. Unison sends functions across the wire instead of data, because Unison code is immutable and content-addressable. However, these languages are currently not particularly popular for building web applications. ^[5]

What is it about web applications that makes them susceptible to this network boundary problem? Simply put, web application workloads are dominated by I/O, disk, and network, rather than the CPU. For any particular CRUD app, most of the work is mapping data from structure to structure, and waiting on the network. We used to be able to ignore the problem of shared mutable states across network boundaries by making prudent architectural design decisions.

Around 2007, web developers could ignore the problem of shared mutable state in the system with server-side rendered web architecture. On the back-end, you could scale by making the application servers as stateless as possible, and pushing that state down into the database. As a result, we delegated all the hard parts of concurrent programming to the database, which they already specialized in. On the front-end, the view for an endpoint was a pure function of the state of the database. There were no inconsistencies in the page because like immediate-mode rendering, we throw away the entire page and request a new one when the user navigates away from the page.

But today, web developers can no longer ignore the shared mutable state across network boundaries. On the back-end, we have microservices architecture that complicates it into a distributed system. On the front-end, we've started constructing thick clients on the browser that manage state of their own, under the banner of more responsive/low latency apps. No longer a pure function of state, front-ends are rife with inconsistent views and introduce complexities like hydration. ^[6]

The composable properties offered by powerful abstractions in modern languages, such as ownership, immutability, monads, algebraic effects, linear types, etc. help manage the complexity of shared mutable state within a program. And yet, this composability all get destroyed at the boundaries of the program. We still haven't figured this out, even though our software systems are full of network boundaries.

The Two Boundaries

Most web apps have two major boundaries: the browser/server boundary and the server/database boundary. Let's go over the current design problems with these two boundaries.

The Browser/Server Boundary

On this network boundary, the latency is higher and less reliable. The question is: how to send code and state over the network to deliver a fast-loading application and keep a consistent view with new user input and events, even in a loss of connectivity?

For client-side rendered apps (single page apps), most of the current activity in the space is centered around state management in the browser. However, these libraries are largely unopinionated about how you fetch and sync the server state with the client state. ^[7] Some sort of async effect handler is provided, and it's up to you to manually fetch data from a server endpoint and the method to update the application state from the data received from the server. ^[8]

There are a few libraries that specifically focus on this problem, such as React Query and Hasura Subscriptions. Both provide functions to tie the fetching of data, displaying of data, and mutation of data together, so that there's deep integration between all three stages to keep them in sync. However, the API is more like the engine type of reuse, where it's the library that's in control, and you're just filling in the blanks. This can be problematic if you ever need to do something the engine doesn't provide. They don't provide compositional properties over the network boundary.

From Casey Muratori's Designing and Evaluating Reusable Components

On the other side of this same boundary, server-side rendering advocates have long considered client-side rendered apps as complex and slow-to-first-render. Instead of sending data from the server to the client for it to render, the server renders a partial view of the data and sends it over to the client. The client wouldn't do a full page reload, but take the partial view and insert it into the current page. ^[9] The initial load is quick, because it's a thinner client. And the user still experiences an app that doesn't refresh on every action, but now every action is subject to a round-trip latency.

The Server/Database Boundary

No matter how well you constrain mutable state in your programming language in a web app, you'll need to deal with the database: it's the ultimate global shared mutable state.

On this network boundary, the data is often "over there" with the database and the business logic is on the application server "over here". The question is: do you bring the code to the data or the data to the code? Current designs often choose the latter, which means how the data is structured, represented, and accessed will affect systems on both sides of the boundary. This wouldn't be an issue if both sides agree, but oftentimes, they don't. How do we resolve this tension?

Traditionally, databases weren't designed to run arbitrary business logic–we don't move the application code to the data. Instead, we move a subset of the data to the application server, by sending the database a query, effectively short declarative programs to get a subset of the entire data set.

Databases are also typically designed with in-place updates of data, which Rich Hickey calls Place-orientated programming (PLOP). ^[10] PLOP means that you're if you're reading data, some other participant might have updated it since you last read it. Therefore, reading values for consistent views and incrementing counts require coordination between participants, which complicates the client.

As a consequence of these design choices, we're wary of making too many small requests due to the overhead of making round trips. It's up to the client to now batch up queries, which also complicates the client. For example, when implementing a GraphQL server, a front-end request can traverse any number of tables and microservices. It's up to the server to batch up those requests to keep the overhead for a request low.

Because we typically bring the data to the application code, the way it's represented and structured couples software systems on each side of the boundary. Databases often choose a set and relational representation of data, because that aligns with their goals of data storage and access. On the other hand, application servers tend to process data as objects and dictionaries, as mainstream languages tend to be structured around object-orientated programming. This tension results in friction and complication at this network boundary called the object-relational impedance mismatch. ^[11]

A short summary of the mismatch is summarized in the table below.

Lifted from The Impedance Mismatch is Our Fault by Stuart Halloway

We've tried to solve this with object-relational mapping (ORM) libraries, but often to no avail. ^[12]

Does it need to be that way? What if we moved the code closer to the data instead? It's typically big data systems that move the code to data, but there do seem to be some applications that make the choice of putting business logic in the database as stored procedures. However, this architectural choice currently also has friction as it often doesn't work with other developer tools and workflow, like version control. In addition, scaling out via replicas introduces consistency issues.

Does the data need to be updated in-place? What if data is immutable and append-only? Then, reads can be done without coordination with other participants. Favoring immutable data has seen success in a variety of software, such as React, immediate-mode rendering, Clojure, Kafka, and others. It stands to reason, that immutable data would find a chance for success here too.

At this point, I'm not advocating for any particular solution. In the design space of cutting a boundary between systems, we seem to be making the decision manually for each application. The place where we make the cut has significant design implications for the rest of the system, and perhaps we can rethink where that boundary is cut, and whether we need to do it manually at all.

Composition across the network boundary

How do we compose over the network boundary? Are the eight fallacies of distributed computing impossible to abstract over because of its inherent complexity? Or is it akin to memory management, where we insisted on doing it by hand until the abstraction became so good that we couldn't justify it any longer for large swaths of programming domains?

Like all beginner optimists, I suspect we should be able to. TCP/IP abstracted the network, so data looks like it came in order. HTTP request/response abstracted over TCP/IP, so it looks like servers are engaged in a conversation. When it comes to distributed computing, however, we've taken abstractions that work on a single-threaded computational model and tried to shoehorn them into an environment whose reality invalidates fundamental assumptions of the model, such as calling a function would execute it once and only once. The harder we've worked to maintain it, the more complex our systems have become. ^[13]

What would an abstraction across the network boundary look like? A promising place to start would be to assume an environment that can fail as a network does. It seems to me it should have a couple of properties.

1. The fundamental assumptions of the abstraction we use shouldn't be invalidated by the eight fallacies, such as functions called means only-once execution.
2. The abstraction should allow the programmer to focus on two tasks: initiating the next computation and getting the data ready for the next computation to consume.
3. Whatever abstraction works over the network environment should also work in a single-threaded, single-computer environment without needless over-complication.
4. Failures need to be taken into account as part of the abstraction. There should be a way for network failures to manifest themselves in the abstraction, so users can handle different cases of failure at a higher level.

Discussion

Web developers are distributed systems engineers in diguise. The myriad of libraries at both the browser/server boundary and the server/database boundary are all searching for the right place to make a boundary in the design space. None of them feel quite right, resulting in both a frustrating user and developer experience.

Is there a unifying pattern or abstraction we can take from distributed systems to simplify the complexity that accrues and accumulates at these boundaries for web applications? What are people trying today to ease the complexities at these boundaries? Do you have insights into what's already been tried, and what might be pitfalls in such an abstraction?

Thanks to Sri Thatipamala, Eric Dementhon, and *David Tran for reading drafts.

Photo by Sirli Jung from Pexels

The New Year is as good of a time to reboot something as any. To encourage more writing, I'll change this around. I'll talk more about the incomplete thoughts I have and what I'm up to. Those are easier to write.

Seeing that it's the New Year, I was reflecting on the things I worked on this year.

Things I built this past year:

At the beginning of 2021, I didn't know what I was going to do next. I spent this past year trying different things. Looking back, I seemed to have tried a bunch of things, more than I'd remembered.

Payment workflow builder

The first few weeks of 2021 was spent building a payment workflow builder. At Pulley, implementing employee option purchasing with ACH payments without holding the funds was a pain. Inspired by page builders, I tried a payment flow builder to direct the flow of money. While it did seem promising, when asking devs on reddit, most of them seem to have relatively simple flows for money. I never launched it.

Automation Cookbook

A longstanding problem I want solved are chainable background jobs–really an ETL pipeline for web apps, rather than for data science. I seem to keep running into this problem at most every job over the years. Workflow automation tools have an issue where people don't exactly know what to do with it. Hence, I wanted to collect user stories and use cases, so I started a newsletter called automationcookbook.io. I even interviewed someone on their process, but I ended boring myself to tears doing this. None of the use cases seemed particularly compelling. It felt like swimming in the long tail.

Gather Town Clone

I didn't really have a name for this project, but it's like Gather Town–like a Zoom meets Pokemon.

I originally came at this from a remote work meets visual programming perspective. You and your coworkers would walk around an environment (doesn't have to be an office) to talk to each other over video chat when close in proximity. But also you'd collaboratively build business workflow processes (that can actually get executed) together by connecting buildings (that fetch or transform data) with packages (containing data) that travel to and from the buildings.

I deployed this at a domain I already had handy: tetracasa.com. You can walk around, and if someone else is also there, you can video chat with them. However, there's no visual programming implemented, because I ran into conceptual issues. I recognized I had no strong opinion on who the user was, what they'd use it for, and the issue at hand. I just had an intution that there was something useful and intereseting here, but I couldn't articulate it.

The more I looked into other attempts at visual programming, the more I wasn't convinced connecting buildings together with traveling data packages would be manageable. In the game Factorio, it also has a similar model–factories connected by conveyor belts. The near un-manageability in Factorio is half the fun, but it seems like a weakness in a collaborative programming environment.

The other problem I wrestled with was the issue of embodiment. In a game-like 2D environment for programming, how do you represent abstract data structures and functions? I had little mainstream prior art I could really build upon, so it felt more like a research problem. At the time, I wanted to avoid doing research if I didn't have to.

I got lost in the weeds. and didn't have an angle of attack for some of these problems, so I decided to take a break and swing back to this later. But I took a long detour.

React Hooks for Data Pipelines

I fell into a rabbit hole learning about React Hooks and was surprised to learn it was inspired by Algebraic Effects. This post on Headless React showed it was possible to use the React Hooks API for 3D scene rendering.

Going back to the chainable background jobs, I never thought the API for most workflow automation/ETL software like Airflow of connecting nodes with edges was that robust. But a React Hooks offered a way to declaratively state a pipeline.

As a sample workflow, I used it to pull down the interest rates of all markets on Compound, and recording it over time. It is for the most part pretty easy to use, and I think promising. However, it's easy to let an uninitialized state variable slip by and having that cause an error.

The full project is called Refract, for the lack of a better name. Of everything I worked on, this was the most satisfying because it came the closest to scratching my own long-standing itch. But more importantly, I started to see React in a different way–it's dragging mainstream developers halfway towards accepting effect managers as a norm. I'm starting to be able to articulate an opinion.

I have other features I'd want to add to this, one of which was data provenance. You should be able to rewind and look at any piece of data that you processed. I was stuck thinking about it and stepped away for a bit, and got sucked into the next three things.

NFT with crafting mechanics

Inspired by Loot Project, This was a side project meant to be 2 weeks, but it took the better part of a quarter. I had meant to jump back into crypto somehow, so this seemed like a good small project. Turns out it was lots of deadends and redesign to fit around the limits of Solidity and the Ethereum VM.

It's basically Cards Against Humanities mechanics, of combining blank cards with answer cards, but with shit that cryptonerds say.

And then crafting the black and white cards together will get you a rainbow card with the blank filled in. People can heart it with eth.

Was it worth it? I'd almost say no. The interesting parts of what might make this a compelling project to buyers had been stripped away to keep scope. Text manipulation is Solidity is a pain, and the limitations of a Solidity contract is annoying to work around. Given the amount of time this took, I should have ejected quickly like I did with the Payment Flow and the Automation Cookbook. I think I just wanted to finish something.

If I were to retro-justify it with anything, is that I learned how painful it was (again) to write smart contracts. Maybe this is something I should pay attention to, and do something about.

I haven't deployed this yet, but will in the coming weeks. It's hard to justify, because it'll cost me about $2500 to deploy this thing onto mainnet.

The Technium Podcast

I started a podcast with Sri in the last couple of months. As a result of some of the things I've talked about in the newsletter and our pandemic conversations, he suggested we just record our conversations.

It's a podcast about the (usually software) technologies Sri and I see on the horizon. It usually follows the arc of:

• What is it?
• What are people using it for today?
• What would the world look like if it was pervasive?

We covered topics from The Metaverse and Datalog to CLIP/DALL-E and Zero Knowledge Proofs. We've already finished the first season, and we're starting up our second season with better production values–new mics!

Overall, this has been good. First, it's been reflective. We don't often see ourselves on screen or hear our selves talk. But being forced to do it while editing in post, it's like looking in the mirror. I noticed my verbal ticks are putting "right?" at the end of sentences, with the occasional "like" thrown in. And sometimes, I start a sentence in the middle, only to abort to restart somewhere else. I can see it's because I had never had to articulate that particular thought before, and I'm putting together the sentence as I'm going.

Second, it's been an outlet. I've been excited about this kind of stuff for a long time and didn't really find someone to nerd out with out it until now. Even in Silicon Valley, people find it easy to be cynics or skeptics, so it's hard to see a potential future.

We'll continue to keep recording episodes as long as we amuse each other. Not sure where this will lead, but so far so good.

Impromptu Spices

Over the summer, I started selling a Beef Noodle Soup spice blend. I thought it was a dumb idea. But early ambition and ideas are fragile, and I've talked myself out of too many things. This time I figured I'd just do it and see what happens. A couple of you bought a bottle when it was announced on this newsletter (thanks!), but I needed validation from strangers if y'all were just being nice. Jess suggested I tell a Taiwanese Cooking facebook group about it.

The demand surprised me, and I ended up selling out twice, and scrambled to make more. I was featured on TaiwaneseAmerican.org in an interview about it in December. Last quarter, I sold over 300 bottles as well as a couple refill bags of the stuff.

This is the first time that I made something people want, however small. It definitely felt different, like people were pulling it out of me. I had just tripped over a latent demand. That said, I'm waiting to see how many return customers there are to see if this really is a thing.

I think there's a couple reasons for the latent demand. One, the product is pretty tasty. So that's a base line. But two, it has a compelling narrative for a specific group of people. I think Taiwanese Americans are so hungry for representative products that they're willing to pay shipping for it.

To me, this is new, since I've always got a sense for what can be possible, but I've always found it hard to craft a compelling narrative for others before I'm able to show them. It'll be something that I'll focus on more for other things I work on going forward.

In Review

At the beginning of 2021, I didn't know what I should be doing, but I did let go of the idea that I should be doing this or that. This past year was just exploring and trying things without talking myself out of it. That's lead to, of all things, a spice blend.

I had gotten better at ejecting out of unpromising projects or dead-ends, but it's still a skill that can be honed better. That has to be balanced with just doing things to see what happens, because there are always surprises when you do something.

While this year's exploration was helpful in getting unstuck, I feel like I haven't really accrued deep expertise in any one particular vertical. For 2022, I'm going to be more focused on something. Looking back, for the past couple of years, I find myself reading and learning about programming languages, Tools for Thinking previously hard-to-think-about thoughts, and human-computer augmentation with any chance I get–regardless of what I'm actually working on. And in my work, I've always thought a lot about the affordance of my code for other developers, to the point of being derided as too clean.

And yet, I've been denying myself from going deep into this topic because it didn't fit the narrative I wanted for myself. It wasn't something my peers seemed to value. I've killed projects working on these things because, I didn't think it'd have a market. I've not joined things because I was so focused on something else. I really just didn't know how to make this something sustainable. So this year, I'm also letting that go, but this means it points me in a direction that I don't really have a name for.

Will I be any good at this? Do I actually have an original line of thought, an angle of attack, to contribute to the state of programming and thinking tools? I can see that behind the Gather Town clone and Refract is a viewpoint on programming, but it was vague and not well articulated. In retrospect, that has to come from writing to clarify my thoughts to more clearly communicate the currently scattered and faceted intuition I have on the topic.

So the near-term plan is to do two things. One, write to articulate the problems in the space. Two, learn how to write interpreters.

Hope you have a plan for your 2022, and that you have lots to look forward to!

Ever since my realization that React's hook API was useful in other contexts, I've been excited about its application to a workflow software like Apache Airflow. Riding on that momentum, I built a bare-bones React for data pipelines, which for now, I'll call by its codename Refract.

So beyond just getting it to work, I wanted to address the backfilling problem I had building ETL pipeline in the past. When fetching incoming data and running it through a transformation, something inevitably can go wrong, resulting in downtime.

Hence, when bringing the service back up, you might have missed event data and will need to backfill it. This is often extra work that I may not have had time for to get it up and running. But when something breaks, I spend more time manually backfilling data.

Using Refract, I built an example app that fetches interest rates from the Compound smart contract for all their markets directly from an Ethereum node.

I implemented a backfill mechanism with the basic hooks, so when the pipeline is brought back up after some downtime, it'll not only do its job of ingesting new blocks for interest rates, but it will also see how many of the last 128 blocks it missed and ingest those. [1]

Most visual programming where nodes are connected via wires makes reuse hard to do because they don't distinguish between a component and its instance. But because Refract uses components and hooks much like React does, the main pipeline as well as the missing block hook are both reusable.

export const ApyIngestor = props => {
  let { providerUri, tokenListPath, mainnetPath, mainnetAbiPath } = props;

  // ...various hooks...

  return [
    elem(MainLine, {
      key: "0",
      knex,
      tokens: filteredTokens,
      contractGenerator,
      blockHeader
    }),

    elem(Backfill, {
      key: "1",
      web3,
      knex,
      tokens: filteredTokens,
      contractGenerator,
      latestBlockHeader: blockHeader
    })
  ];
};


export const Backfill = props => {
  let { web3, knex, tokens, contractGenerator, latestBlockHeader, children } =
    props;

  const { missingKeys, numRemainingKeys, setNumRemainingKeys } = useMissingKeys(
    knex,
    "annual_percentage_yields",
    "blocknumber",
    latestBlockHeader?.number
  );

  let [pastBlockHeader, setPastBlockHeader] = Refract.useState(
    "past blockheader",
    null
  );

  Refract.useEffect(
    "get past block",
    () => {
      if (!web3 || !missingKeys || !numRemainingKeys) return;

      (async () => {
        missingKeys.forEach(async blocknumber => {
          const bh = await web3.eth.getBlock(blocknumber);
          setPastBlockHeader(bh);
          setNumRemainingKeys(numRemainingKeys - 1);
        });
      })();
    },
    [missingKeys, numRemainingKeys]
  );

  return [
    elem(MainLine, {
      key: "0",
      knex,
      tokens,
      contractGenerator,
      blockHeader: pastBlockHeader
    })
  ];
};

Backfill is something specific to the domain, so I decided to leave it as something the programmer constructs, but with reusable hooks to help make it easier.

For example, we backfill in ascending order, processing the oldest first. Otherwise, the Ethereum node might flush the old block before we get a chance to get around to it. Also, we try to generate a new missing keys list on every new block, but only if we haven't finished processing the last generated backfill list yet. That's what the numRemainingKeys count is for. We return it and its complement setNumRemainingKeys from the hook, so the client can update it.

So far, I've liked the experience of writing Backfill with this API. When I refactor and move either components or hooks around, I don't really have to change much; I can just cut and paste. And I can reuse components because each place I use them is a different instanciation.

Another advantage is that I don't really have to worry about cache invalidation any longer. In the initial non-Refract implementation, I did notice I reloaded the ABI files from disk on every new block. It's wasteful, but I didn't change it because it didn't seem to affect run time. But in Refract, it just worked. The caveat is that I have to get the dependency array correct in useEffect hooks, which sometimes I can miss. Also, forgetting that some variables might be undefined in the beginning, so I have to use option chaining.

So far so good.

[1] Unless you're talking to a full archive node, Infura only keeps the last 128 blocks.

By now, most of you have heard of cryptocurrencies, such as Bitcoin or Ethereum. Even in Silicon Valley, it's been a polarizing technology. Some think of it as seismic as the internet, whereas others think of it as a giant scam. As John Oliver puts it, "Cryptocurrencies: It's all the things you don't understand about computers mashed with all the things you don't understand about money."

The most prominent aspect of cryptocurrencies is the price and volatility, but that's hardly the interesting bit. In the last couple of years, people have been building a global, open alternative to every financial products you use today, accessible to anyone in the world with a smartphone and internet connection.

These financial services are grouped under the umbrella term, Decentralized Finance (DeFi). It's one of the fastest growing sectors in cryptocurrencies, with $26 billion of cryptocurrencies deposited, and growing exponentially as of this writing.

DeFi products are different from their traditional counterparts, in a number of different ways, but to me, the most interesting aspect is that these financial services are interoperable and composable without coordination or permission.

Compound is an automated money market–a lending and borrowing platform for cryptocurrencies. As a borrower, you can borrow crypto with an over-collateralized loan, usually with other crypto as collateral. As a lender, you can lend your crypto to earn continuously compounding interest. When you lend on Compound, you receive cTokens representing your contribution in the lending pool. These cTokens can be bought, traded, and sold on exchanges because cTokens themselves are also cryptocurrencies.

PoolTogether is no-loss prize game. Multiple users trade their cryptocurrency for tickets to pool their crypto together. PoolTogether then uses the pooled crypto to lend in Compound. The interest earned is then used as prize money that gets distributed randomly to ticket holders like a lottery. These tickets can be bought, traded, and sold on exchanges because the tickets themselves are also cryptocurrencies.

PoolTogether didn't have to coordinate with Compound to implement no-loss prize games. And if a new DeFi product wanted to use cTokens and tickets, they can do so without coordinating with either party. This permission-less innovation mirrors the growth of web integrations to provide value to users that each individual service couldn't do alone.

There are many other DeFi products out there, and each successful DeFi product is yet another building block for future DeFi products in a positive feedback loop. By the looks of it, the pace of innovation in this space will only accelerate. [1]

That said, I think it will still be a long while before the DeFi ecosystem will substantially affect the day to day real world workings of the economy. For me, the tipping point will be when businesses can seriously consider using crypto to help integrate financial services into their products for a seamless customer experience. Before, I was more bullish, but now I have reservations.

For one, the regulatory environment is uncertain in this space, as the SEC hasn't made definitive rulings on certain aspects of crypto. If there's draconian regulation, it could easily cool business adoption in this space. However, this won't kill crypto, because the decentralization ethos of crypto has made it more resistant to state-level actors.

Second, cryptocurrencies have some serious user experience problems. There's a definite learning curve, and unless you have sufficiently motivated users, most people aren't going to want to learn all new ways of transacting online. While there is some work on a great user experience, most of the attention and work in the crypto space is about infrastructure, inventing new financial services, and memes.

Third, fintech companies are the default go-to for tech companies that want to deeply integrate a financial service into their product for a more seamless customer experience. They've coined this movement as Embedded Finance. Examples are Uber Insurance for drivers or Shopify Capital to give loans to small businesses. The fintech companies powering financial services aren't your mother's Bank of America, but rather, companies like Stripe and Mercury. They are fierce competitors and are entirely focused on customer experience.

Cryptocurrencies will likely remain as a secondary alternative financial system for speculative assets if it can't find an in-road to being the go-to default for businesses that wants to integrate financial services into their product for a better customer experience. There's only two other paths I can see at the moment. They could provide financial services for companies in spaces that are turning from illegal to legal, like weed delivery companies, since traditional banks won't service them. Or they'd have to provide services that can't exist in traditional finance, such as non-fungible tokens (NFTs).

The other valuable contribution these DeFi products create is the governance model with their community of users. Some DeFi products issue governance tokens as a part of its ecosystem or as natural by-product of using it. These governance tokens can then be used to vote on provisions that dictate the policy the DeFi product should adopt.

For example, MakerDAO is a DeFi product that locks up Ethereum as collateral, and issues a loan for less than the USD value of the locked Ethereum. [2] This loan has a variable interest rate, which is controlled and voted on by holders of the Maker governance token. It's deliberately designed with a system of incentives to give users of MakerDAO a voice to dictate policy, even if they don't work at the company.

While social media companies can sometimes have an internal committee that decides policy, it has no actual system of government to allow users to voice their desires from outside the company. That result in the quagmire we see today with the debates over the censoring power of Big Tech. I think DeFi products have communities that are much better suited to address this class of problems.

It's hard to see the value in cryptocurrencies. There's definitely a lot of hype, meme-ing, and religious fervor that get in the way. In addition, many of the problems crypto projects solve are only applicable if you're already using cryptocurrencies. The early internet was similar. Google, Del.icio.us, Flickr, Yahoo Mail, and Paypal were only useful if you were already using the internet. [3] It wasn't until later we had web services that affected the real world and other industries like Uber, Netflix, and Airbnb. Will crypto be able to jump the gap? For now, I'm cautiously optimistic about DeFi's prospects.

For those of you that are curious:

• A beginner's guide to DeFi by Linda Xie
• Coinbase's beginner's guide to DeFi
• Nakamoto's beginner's guide to DeFi
• DeFi indexes: DefiPulse and DappRadar

I haven't worked in crypto in the last year and a half, but I wanted to catch up with developments since. For those of you working in crypto, what should I look at besides flash loans, social tokens, and yield farming?

Photo by Jason Boyd from Pexels