Copy
View this email in your browser
Arch-Engineer
Code better

The Benefits of Free Objects

Domain modeling, turning the world into nice clean data structures, is fun. But it's not fun when the real world hands you a counterexample that messes up your clean ontology. But doing that to other people is fun. I recently warned someone designing a gesture-recognition API against assuming that all people have 5 fingers.

Towards that end, I have a design exercise called "Full Names: Evil Edition." In this exercise, the student begins by writing a trivial function: given a first name ("Jimmy") and surname ("Koppel") return the full name ("Jimmy Koppel"). But in the ensuing rounds, the student must extend their code to deal with the many variations of names found across languages and cultures, along with individuals who stubbornly refuse to conform to any of them. 

A 1-on-1 student recently did this exercise, and quickly found himself scrapping the string representation of names for more structured data. In our session today, he asked me: how does he know when his data structure is "structured enough" and won't need to track more stuff to handle later feature requests I may throw at him?

In spite of my previous recommendations against studying it, I quickly realized the answer comes from category theory: design it to be a free object.

It goes like this: Imagine your space of initial inputs. Call it X. You have some type of data structure containing those inputs. Call this type of data structure A. You build up a value of type A by feeding in inputs from X and doing all kinds of operations that add and merge and modify stuff. For a concrete example, for a Reddit-style comment feed, X might be the type of user/comment pairs, and A will be the type of threads built out of these comments along with the sequence of upvotes/downvotes performed on them.

Now, imagine later you want to build a different data structure out of X, called B. Maybe you do this by taking A and making it larger, by adding more inputs and operations. Or maybe you decide A is too complex and some components can be shrunken down. For the Reddit example, the type of comment threads could be made larger by adding moderation features, and could be made simpler by replacing the sequence of upvotes/downvotes with just the count.

The defining feature that makes the type A a free object is if, for any possible altered type B which supports the same operations, it is possible to transmute a value of type A into the exact same value of type B we would have gotten had we started with the same inputs and performed the same operations. This is an incredibly strong property, but it's quite attainable. If you've ever built an interpreter that adds 5 and 7 together into Plus(Int(5), Int(7)) instead of into 12, then you've done this. The Reddit comment example also gives some intuition for the extensibility: it is very easy to replace a design that tracks who did the upvoting/downvoting and in what order with one that only tracks the count, but impossible to go in the opposite direction.

This gets us to our software-engineer's working definition of a free object: A free object is something that tracks all inputs and all operations that have been performed.

You can then ask what exactly "the operations" are. This corresponds to the question "which category are we talking about," which gets into the heaps of technicalities that led me to caution software engineers against studying category theory. Still, the previous paragraphs should provide enough intuition for these purposes.

Saying "It should be possible to recover the inputs" is not exactly shocking advice for anticipating future changes. The rest of this section will be about common ways to accidentally make something not be a free object, each of which comes with countering directives. You will quickly realize that you probably don't want to follow all of these directives most of the time, at least not to their full extent. But you'll still get a lot of future flexibility by only applying them partway.

Dropping Inputs

This is the simplest one. If someone does an operation and you don't record the timestamp, you're never getting it back. Even if you don't care about these timestamps now, if you ever decide you do want a timestamp field, you'll have to grumble and make the field optional (or backfill with false timestamps). This needs no further explanation.

Making your data structures be free objects means keeping around all this data and logging all actions, which leads to a form of input "hoarding." This can lead to giant useless piles of stuff, just like hoarding in real life. Unlike hoarding in real life, I am generally in favor of input hoarding. The tradeoff is different: digital space is much cheaper.

Creating Summaries

Anytime you replace some data with something computed from that data, you lose information. This can take the form of just tracking the number of upvotes instead of who upvoted and when, and it can take the form of saving a boolean as the only result of some complex decision, which burned another software-engineering writer with harder debugging. If you want to be able to upgrade the system later and have the same state as if it was built that way all along, you need a structured log of everything. Like with input hoarding, this can be a no-brainer in some cases, and will have you Googling hard-drive prices in others.

But there are also subtler ways by which you may have replaced some basic data with something derived. Consider in the domain of names: Surnames are gendered in Slavic languages, so that Alfred Tarski's wife was named Maria Tarska. It would lose information to store her name as "Tarska," rather than its derivation of "Tarski" + "a." Perhaps you can't think of any reason why one would need to recover "Tarski" from "Tarska" (I came up with some, but they're a little dubious), but that's exactly the point: if you can't confidently say you aren't going to need this information, making a free object and keeping it is a safer bet.

Losing Structure/Relations

The third and most surprising way to lose freedom is to drop the relations and structure of the inputs. This often means order, such as storing the upvoters/downvoters as a set instead of as a list. It can also come from dropping distinctions, such as using the same "suffix" field for both honorary suffixes like "Ph. D." and "Esq" and for generational suffixes like "Jr." Another common form of this problem, similar to the Maria Tarska example, is to jam multiple pieces of data into a single string in a way that's not easily recoverable, such as presenting a string date like "5/4/21" (is that May the 4th or April 5th?) or to send a chain of commands as a string.

Conclusion

Making data structures be free objects comes with many costs. Some of the labor costs will disappear with practice; some of them won't; and the physical (storage) costs will sometimes be prohibitive. But if you do, you get something very powerful in return: the ability to losslessly apply retroactive design changes that you never anticipated. And with it, you inch closer to the peace of a life without regret.

 

This is Dr. Koppel speaking


This newsletter has been on a long hiatus. And that's because I've been working on something important: I finished my thesis and graduated!

I haven't entirely left MIT. Officially, I'm a Visiting Scientist, and still have a few papers to write. But for the most part, helping software developers improve is now my only job.

For you in the short term, this means more newsletters, more blog posts, and more frequent runs of the Advanced Software Design web course. Longer-term, it means more content for you in forms not yet dreamed of.

But I still face the limits of how many I can train. The few of you who keep careful watch on my website will realize that I started and completed a run of the course without even mentioning it here, because I had enough of a backlog of interest that I never needed to. I'll be running them more often now, but it's clear I'll have to do something extra if I want to grow beyond just training 50-100 engineers a year.

(Also, if you really want to get into the course, best way is to express interest early; you will be prioritized.)

I'm a very strong believer in the power of personalized feedback, and that it is requisite to rapidly level people up, but it's very laborious. I think frequently about how to make personalized feedback scale. On top of our process improvements, towards that end, I spent a lot of time last year studying Intelligent Tutoring Systems. It turns out that a small corner of academia has delivered stupendous results without the rest of the world noticing, and that simple techniques can be quite pedagogically effective. I'll have a lot more to share about that once we have our own results.

Planning is well underway for the new training software. I recently finished interviewing a few dozen former students, and will soon be reaching out to a small handful of readers of this newsletter who have never worked with me before. If you're actively interested in being interviewed to help design the future of developer training, please reach out by replying to this E-mail.
Copyright © 2021 James Koppel Coaching, All rights reserved.