Out of the Tar Pit (2006) [pdf]

Oh right, I forgot the ORM with "distributed caching" needed between the database and GraphQL layers. More hidden state.

Bear with me, we're going on a bit of a walk.

An abstraction layer says: here are some operations you can do, operating on some models. Presumably those models are a useful or convenient perspective on some underlying data, and those operations are important or useful as well. At this level, we can define something like "order a pizza", "renew my driver's license", or "show me a book I might like to read". Note the abstraction is driven by the needs of the users/consumers/callers of the abstraction, not its implementations. This sounds obvious, but it's extremely often done the wrong way around -- "Foo : IFoo" shouldn't be muscle memory, and it should mean "I can't currently think of any other implementation of IFoo right now, although that might change", and NOT mean "this interface is the header of this class, which we have to do or we get yelled at".

The implementation of an abstraction layer breaks down an operation in one domain into operations in another (presumably "lower level") domain. It's possible that "renew my driver's license" can be reasonably written directly in a few SQL statements. Okay, that's no big deal. Most likely you have a few intermediate layers, or an ORM, or whatever. So the implementation of the "DMV API" (or whatever is defining that operation) is where you break it down into INSERT/UPDATE/SELECT or whatever other lower-level tools you have.

None of this changes when you start thinking about your higher-level operations algebraically. All that really means is that you consider the operations and their inputs/outputs, and you start asking questions like: are these idempotent? Associative? Commutative? Do they have identity? You can ask those questions at the abstraction level. They are part of the definition of the operation. It's up to the implementation to make sure those properties are respected.

Look for ways to change the operations you offer to be as "mathematical" as you can. The more mathematical they are, they more you'll serendipitously come up with new and interesting and useful ways to use them; the more reusable they'll be.

"Renew my driver's license" is idempotent; "order a pizza" is not. Prefer idempotency. Can we make "order a pizza" idempotent? Sure. The client generates (or requests) a unique ID for the order. We have "update an order", which may actually be a family of operations. We have "finalize an order" which places it. Finalizing the same order twice does nothing -- it's idempotent.

User story: a bunch of guys are sitting around and want to order from your pizza place, but it's always annoying to pass the phone around; everyone wants to look at the menu at once. We want "distributed ordering", so a party can all contribute what they want to the same order. They want to see what everyone else is doing in real-time. I want breadsticks, but there's only 5 of us. If anyone has ordered breadsticks, we're all good. If we have an "add breadsticks" operation and poor concurrency, we end up with 5 breadsticks in our cart; someone has to notice that and fix it. Not great.

So what's a better operation than "add breadsticks"? How about "make sure there are enough breadsticks"? If three people all say "make sure there are enough breadsticks!" that's basically the same as one person saying it. That's an important domain operation. If all you're doing is thinking "event sourcing", then "add breadsticks" looks more like a domain event than "make sure there are enough breadsticks", but the latter is actually easier to work with and leads to a better experience. You can't make the jump from "add breadsticks" to "make sure there are enough breadsticks" just by thinking about event sourcing -- you get there by thinking about math.

What happens when someone removes a pizza from the cart at the same time as someone else is adding pepperoni to it? This is the "Google Docs" problem. We need to think about associativity and commutativity to really solve these problems, not to mention random vs. sequential identity. Can you undo these operations? If I say "extra sauce", and someone else says "no, light sauce", we might have a conflict to resolve. But if I then undo my "set extra sauce" action -- what happens? It should clearly result in "light sauce". That's the obviously correct answer, so we can work back from that to figure out how the "set sauce amount" operation should work. "User A requests heavy sauce on pizza AF73" is idempotent and reversible. "User B requests light sauce on pizza AF73". "User A revokes their request for heavy sauce on pizza AF73". Okay, great, we're golden. "User C removes pizza AF73 from their order." "User D requests pepperoni on pizza AF73". "User C undoes their operation to remove pizza AF73 from their order." Great: pizza AF73 has pepperoni on it, despite the fact that it had been removed when pepperoni was added. No problem here.

How do you handle statements like "User A revokes their request for heavy sauce on pizza AF73?" Event sourcing would say that this is a distinct event that you have to INSERT in your append-only log. But why not just DELETE the initial request? That works just fine. In any case, the low-level steps are the easy part.

We're not too far from event sourcing here, but that emerged from analyzing the problem and trying to make it as "mathematically pure" as we could. We didn't start with event sourcing, and we saw another example (add breadsticks) where the "event sourced" version was worse. Event sourcing is a trick, but not the goal. The goal is "domain algebra".

On the back end, you'll be doing reporting on these numbers. You want a really flexible reporting system? There was a buzzword a few years ago, "data cube". It was a buzzword because nobody could define what it meant, but after thinking about it for a while, I decided it could have a useful definition: A data cube is a pairing of a set of categorical data (pizza sizes, customer types, order times, whatever) and value data (costs, amounts, prep times, ratings). Each "value data" must have a monoid defined over it, which means some binary "add" (or "combine") method with identity. Any time you have a monoid defined, you get a (distributed!) "aggregate" method for free. That's what "roll up" and "drill down" are, in report-speak: projecting your categorical data and aggregating all your value data using the defined monoid. The same kind of analysis applies here, even though event sourcing has nothing to do with any of this.

By the way: the identity of "combine" over rating and prep time are not simply 0! Think about it harder than that. How do you combine user ratings? Most likely your value type will need to be able to sensibly represent "0/0" -- that's a valid and useful value sometimes!

We didn't get particularly "mathy" operations with our pizza example, partly because it's a very "end user" domain and not a reusable mid-level domain like unit conversions or a physics engine. It's even more important for those domains. What's a Point minus another Point? Not a Point! Are "offset" and "rotate" associative? Commutative? Distributive? Think about these things if you want a reusable physics engine.

This is not scripting. This is not even programming. It's software engineering.

This paper was career changing for me.

Chapter 9 is effectively the original concept for our business rules engine today. We use SQLite and C# UDFs as the actual foundation.

Using a proper relational model and SQL queries for all the things means that domain experts can directly contribute. It also makes it feasible to turn your domain experts into internal customers of your developers. For B2B products, this can be make or break.

Building an actual business around this kind of thing is very hazardous in my experience. Unless you are completely certain that you have the schema figured out, this promising foundation converts to quicksand.

Using higher normal forms is one way to reduce the consequence of screwing up domain modeling, but you still really have to know the relational guts of the business one way or another.

One design-time trick is to get all stakeholders to compose their ideal schema in something like excel and have them fill in some sample data. Showing them an example of one of these for a different domain is a powerful lesson in my experience.

IMHO in the context of the Tar-Pit Paper (programming for services and applications rather than electronics) mutation merely is a mean to an end. The end being: some piece of memory holds the value I expect (e.g., to transmit, store, show information). Thus I disagree that mutable state is essential complexity. For the rest of the post I don't understand what you mean with "walking the line between avoiding/ignoring mutable state" and I wish you ad elaborated about what you mean by "play very well with Turing neighbors" because I cannot really connect with that.

Regarding, functional programming and mutation. In a typed "pure-FP" language like Haskell: - you need to explicitly declare what constitutes a valid value - which drives what valid values are observable between program steps - which informs how corrupted a data-structure can be in your program

For instance, using a tree-shaped structure like `Tree1 = Leaf Int32 | Node Int32 Tree1 Tree1` and you have some `MutableRef (Tree1)`. You know exactly that from the ref you can read a whole Tree1, you can change the content of the MutableRef but you need to give a whole new Tree1. In particular, you are sure to never read "an half-initialized tree" or "a tree that was changed while I was reading it" because these things just do not exist in the realm of valid Tree1s. Such simple guarantees are really important to many programs but are not guaranteed in most programming languages.

Of course, if for some reason (e.g., for performance) you need something more flexible and are willing to pay the extra complexity, you can do it. As an illustration, you can augment your Tree1 with some MutableRef as well. `Tree2 = Leaf Int32 | Node Int32 Tree2 Tree2 | Cell (MutableRef Tree1)`. Here Tree2 contains mutable references to a valid Tree1 so Tree2 is not fractally complicated but you could do that too. With Tree2, you can interleave reads, writes, and other operations while working on a Tree2. These extra effects could be required (for performance reasons for instance) at the expense of inviting surprising behaviors (bugs). In pure-FP it is clear that with Tree2 we lost the possibility to "read/write a whole tree in a single program step". Thus, if the control flow of the code is not linear (e.g., multi-threaded, callback-heavy) you may have fun things occurring, like printing a half of the tree at a given time and the second half of the tree after a mutation, resulting in printing a tree that never existed. Enforcing global properties like the heap-invariant becomes inconvenient because it is actually hard if we let mutation in. I'd go as far as saying that the Tree2 doesn't exist as a tree: given a Tree2 we are merely capable of enumerating chunks with tree-shapes piecewise.

This reply is long already, so I won't go into how Haskell has various flavors of mutable refs in IO, ST, STM and recently even got linear-types to allow some fine-grained composition-of-atomic-mutations/interleaving/prevention of effects. But overall I find pure-FP takes mutability much more seriously than other more mainstream languages. Here, pure-FP just keeps us honest about where non-determinism bites. The collective failure to realize is one of the key reason why we are in The Tar-Pit: violated in-memory-invariants can compound even outside programs by forcing outside/future users to deal with things like misleading information being shown to users, urgently upgrading your fleet of servers, days of one-off data-cleanup and so on and so forth.

For anyone who is not aware, 'accidental and essential complexity' were coined in Fred Brooks' 1986 paper No Silver Bullet.