Not sure how, last week I stumbled onto my Shadow DOM diaries from 2014 and realized how few of my learnings I captured there. Designing the beast as complex as adding a whole new type of composition to the Web platform was chock-full of them. So I thought, maybe I could share some of them. Think of it as “What Dimitri learned, then forgot to write down, felt guilty, and decided to share much, much later.” If you’re currently investing time into designing a composition system, I hope these will come in handy.
One particular learning that came to mind was the discovery of a distinct tension between graph and tree structures that I felt when exploring that problem space. If I were a law-formulating type of person, I would probably describe it as something like: “every graph wants to become a tree, but also secretly wants to remain a graph.”
There’s something around human intuition that views composition-as-containment as more legible than the chaos of graphs. This desire for legibility imposes a resolute force on pretty much any composition system we design, eventually converting it into a tree-like structure — or becoming enveloped by another composition that is tree-like. From files and folders to markup to house layouts, it seems that we try to put everything into boxes that contain boxes that contain boxes. We just can’t help it. Should we accidentally design graph-like structures, we immediately try to build additional structures that represent them as trees, kind of like the vast graph of the Web being reduced to a search page that — you guessed it! — contains links.
If a designer of a composition system ignores this force, they are likely to see a few things happening: either their composition system doesn’t make any sense to the intended audience, or it becomes the infrastructure of a tree. To the aspiring architects of web3, here’s a bit of advice that comes from the heart. Though graphs have the appealing property of being decentralized, they are still subject to the centralizing force of boxes-within-boxes-within-boxes. There’s always going to be that human desire to understand a graph of relationships in terms of containment, and thus, every graph-like structure will either eventually get simplified into a tree or grow an external “understander of the graph” that represents it as a hierarchy – with one thing most definitely being at its top. Designing a composition system that only offers a graph means designing an incomplete composition system – that will be completed, whether by future you or someone else.
Yet… when it is all said and done, and the primacy of tree structure is unequivocally established within a composition system, the secret desire to keep (or re-establish) some graph-like properties remains. Sometimes it manifests as wanting to reduce computational redundancy (like with shared stylesheets). Sometimes it pops up as the need to convey semantics that are obvious visually, but impossible to infer without eyesight (like with labels). Regardless of the specific requirement, real-life compositions will feel quite limited within a tree and continue to want to sprout non-hierarchical appendages. Often, these appendages come across as gnarly hacks. For a well-trained hierarchist, they are easy to dismiss or sigh about with disdain. A more productive way to look at these is probably this: they are an expression of the deficiency of a composition system design that assumes that, since the hierarchy is so strongly wanted by humans, it is the only way to represent things.
So, in addition to accepting the “want of the hierarchy” as the law, the composition system designer needs to recognize the “need for the graph” as the countervailing force in tension. My intuition is that a robust composition system design will be a layered affair: the graph composition abstraction as the infrastructure, with the tree composition as the human-friendly interface. This way, the tension between the two forces is embodied by the composition system itself, rather than leaving it to the consumers to figure out.
Of course, this means that most designers of Web frameworks wanting to follow this recipe are, as kids say, SOL: the Document Object Model is your bedrock, and it is unabashedly tree-first. My sincere apologies, y’all.
I don’t think the human impulse is to build trees. That’s just a result of object orientation being taught to a lot of impressionable young programmers.
The notion you generally actually want is the partial ordering that comes with a tree, and which lets you give the graph a DAG structure. There is absolutely no reason why a node should have just one parent (or just one child).
Now, you can add more structure that a tree may have, such as being a directed set, a semi lattice, a lattice, a matroid or antimatroid etc etc. But there are many models other than trees that are viable, with the ECS model probably being the most famous one.
Personally I am a big fan of antimatroids to represent hierarchies in terms of their path poset as a way to unify OO inheritance, ECS composition, and grouping into subgroups, but there are other models.