Thoughts on recursive structures in design
A powerful approach that simplifies code and reduces complexity is to define recursive structures in a design. Recursion in general is a simple and hard concept for most people, so it’s no surprise that extending it to design is a rare occurrence. In practice, most problems that benefit from a recursive solution can also be solved in other ways, which further contributes to this approach not being considered.
On simplifying code and reducing complexity
Recursion is usually found in problems that border or are in the area of theory. In some cases, it’s the only approach that can be used to model a solution. For example, “how do we represent a sequence of things that can be infinitely large?” is solved by using a recursive list (I’m using the term recursive list to mean the theoretical linked list ). This is hardly the case in practice, where a sequence of things can’t really be infinite, which means the solution space is larger, and can be explored through questions like “how large will the sequence of things get?”. Outside of theory, solutions such as creating a space large enough to hold a sequence of things are perfectly acceptable (note: this space could be called a list, but in a different sense from the linked list, since you can model it without any recursion).
Infinitely large is a key term that distinguishes a problem in the area of theory to a practical problem, and is usually what gives away that you might not need recursion to solve it. A non-recursive solution, however, is likely to cost some additional complexity.
Let’s explore how this can happen by imagining the following system: a bunch of users manage resources, either individually or as a group, through an ownership model where each resource has an owner in charge of that resource; this ownership can be transferred to either a user or a group, but ultimately the ownership chain should always be traced to a single user to ensure strong accountability.
A straightforward model from this description is to define a user, a resource, a group, make the resource’s owner be either a user or a group, and make groups also have owners (for the strong accountability). Because of this model, we have two classes of objects, users and groups, that will require different treatment in code when working with ownership: the code must always check if it’s dealing with a user or a group, and in case of a group, check who is the group’s owner, and in case it’s another group, continue walking through the chain… This distinction between a user and a group is additional complexity: all the checks and edge cases incur cognitive load when thinking about the system, especially when figuring out the owner of a resource is a frequent action. There is an illusion of recursion here (groups being owned by groups), but it’s broken by the presence of the user, forcing us to also deal with the problem non-recursively.
Consider instead a model where ownership is always assigned to a group, and a resource having a single owner means that there is only one user in the group that owns that resource. This would simplify most of the checks when determining the user who is accountable for a resource — stop whenever we find a group that has a single user, otherwise keep going through the ownership chain. Naturally, the single-user group would have itself as the owner, which makes it hard to think about the solution (e.g. “what happens when we want to add another owner to the resource?”), but it’s still simple: only one edge case to think about, but makes the code much easier to read. This is hopefully enough to illustrate how recursive design can simplify code and reduce code complexity.
Applying the concept at a higher level
This concept of recursive design can be expanded to projects, or things in development: using the project/thing to solve the project/thing. It’s a common milestone for compilers, for example, to reach self-hosting status, but the concept is more broadly applicable as dogfooding .
Projects that are solving a particular problem have to deal with the risk of whether they will actually solve the problem. In software, people have dedicated entire careers to developing systems and methodologies to derisk projects, and this includes trying to ensure the project will solve the problem it should be solving. Dogfooding is potentially the most powerful way to avoid this particular risk. By definition, if you’re dogfooding your project, it means that it solves the problem, or at least part of it. Avoiding one risk by design means that people can focus on eliminating other risks. Things become just a bit easier, creating an advantage that contributes to the project’s success.
If I could, I’d really only work on projects that can be self-hosted. In my opinion, this advantage is underrated.
Finding recursive design
The key to finding recursive design is to change the perspective on the pieces that you’re working with: rather than seeing them for what they are, consider what they do or how they behave. Looking at the previous example of the system with users, groups, and resources, we see that users and groups have the same purpose when it comes to the ownership model — being one step in an evaluation chain — even though they’re different things in the system. They are users or groups, but they act as an evaluation step when determining ownership.
By changing how the pieces of the system are seen, sometimes you’ll reach these views that let you group multiple things that were different from another perspective. Almost any sufficiently big problem will allow multiple ways to do this, and it’s likely that one perspective will simplify some part of the solution, while introducing complexity in another, but another perspective will have the opposite effect. Explore ways to compose these perspectives in the solution. It might be possible to introduce both perspectives in the code in a simple way.
Original title: Thoughts on recursive structures
I find recursive structures to be very powerful. The idea that you can abstract parts of a structure using the structure itself allows you to build interesting tools to work with it. If you expand this to projects, you get projects that can be self-hosted . If I could, I’d only work on projects with this property.
You can describe any of a tree’s nodes as another tree, as the example below shows:
And this is very powerful, because it allows me to build a set of tools that work on top of trees, and then I can apply this to any level of the tree that I want. This means I can create as many layers of abstraction as I want, but as long as I can represent all of those abstractions using trees, the set of tools I created can still work at any level.
It’s not a surprise that a lot of computer things are built on top of structures like this. Also not a surprise that so many companies want you to know about these structures when interviewing you (although they usually do that through flawed processes).
This becomes very interesting when you start looking at more complex systems using this same idea. Compilers are usually known for this — at some point during the creation of a language, you might be able to write a compiler using the same language you’re creating, and then you have a compiler for language X written in language X!
One of the consequences of this is that you effectively create a dogfooding cycle, and it is my opinion (backed by what little experience I have) that this is the best way of ensuring your project will be as good as you want it to be.
Another recent example that came to my mind of a self-hosting project is Sourcehut (the source of this blog post is hosted there). I am a relatively early user of it (when you consider that as of this post’s date they’re still in alpha), but I have no concerns about its (current and future) quality: I know that as long as work is being put into the project, Sourcehut will be at least good enough for Drew’s use case (he’s the creator of Sourcehut, and maintainer of lots of open source projects), and my use case has less requirements than his.
(thinking about it, self-hostable projects seem like a relatively safe investment to make, as long as you’re happy with the creators’ sense of quality)
All of this is to say that we should pay more attention to opportunities in designing things that can be recursive. The most common mistake that I see is to treat an individual thing and a group of individual things as two different concepts.
Consider an authorization scheme that defines users, groups, and resources. A user is linked to a person using the system, a group is a list of users, and resources are the things you want to manage with your authorization scheme. This is a very common concept that many systems have. Generally, the design allows resources to be created/owned/read/modified/deleted by users or groups.
However, the design usually goes on so that resources can have a single user as a owner, and then extra care must be taken when a user is deleted (which leads to more code!), you need to support users transferring ownership of resources… All while still maintaining code that does almost the same thing, but for groups. One part of the code applies to a single thing (user), while the other part of the code applies to a list of things (group). It gets even worse if the design treats groups and resources as different things, and allows groups to have a single user as an owner, and now you have the same authorization code all over, but this time it applies only to groups.
This may sound “dumb”, and you may believe a design like this would never exist, but I assure you there are systems like that out there — especially internal systems at companies. I particularly remember a system which defined an owner and a secondary owner of a group (but not of a resource). The only difference between the secondary owner and the owner was that the secondary owner could not change the owner in the group. ¯\(ツ)/¯
Why not join all of that? In a recursive design, everything could just be a list of users. A resource “owned” by a single person will only have a single user in the list. If the resource needs to be shared, just add another user to the list.
If you require more granular read/write/other restrictions, you just introduce additional lists with different permissions. As you work on this, you realize that you want to reference a specific list of users more than once, and you want any updates to this list to apply everywhere the list was being used. Rather than create a group and start writing code for groups, resist the urge and treat a list of users as another resource instead. Then, your code to authorize lists of users to read/modify/delete/whatever a resource will automatically apply to lists of users themselves.
It’s a bit hard to wrap your head around this concept, but when you do, you’ll realize you need to write a lot less code (because your tools apply everywhere, doesn’t matter the level of abstraction), and thus you can focus on making existing code much better.
Another example of this mistake is in certain (most?) workflow systems that I’ve seen out there. They all define a workflow as a set of activities, or steps, but then fail to join both concepts into one. The systems will then allow you to define sets of activities inside a workflow, but workflows themselves will have different properties that don’t easily allow recursion.
To enable recursion in the design, you treat everything as a list of activities. What was previously a “single activity” becomes a list with a single activity in it. Thus, a “workflow” becomes an activity too. With this, you’re able to easily embed workflows within other workflows, and it becomes easier to break an activity that was too coarse into a workflow (because it’s just a list of activities).
This allows all your code to deal with a list of activities in your workflow system to be applied to new scenarios (such as a workflow embedded into a workflow). You also only need to write the code once, which allows you to focus on making it good.
Hopefully by now I was able to better explain this concept: recursive structures/designs are powerful, and they allow you to apply the same code at different levels of abstraction.
I think a powerful thing can be built by approaching distributed systems this way, specifically in a microservice architecture. I may have some ideas and possibly an interesting design, but I don’t really have anything concrete yet. Maybe you have an insight into this? I’d be curious to know.