Emergence and Composition
Emergence and Composition
Exploring the topic of emergence in computing, and notes on how it becomes relevant in various problems, including arena allocators.
There are only two hard things in Computer Science: cache invalidation and naming things.
—Phil Karlton
Naming is often called one of the most difficult problems in programming. Surely, at least once during a programming conference of your choice, and almost always by someone who has done a lot of programming.
This infamous saying is—especially for the first-time listener—mystifying. Computers seem complex, and when you begin your programming journey, almost everything seems like a difficult problem. And yet, the most experienced programmers in the room are usually saying that what you thought were the complex problems are all actually easy, at least relatively. If it was just that, then it might seem like they’re just bragging—cackling at the noobs, sitting in their conference panel chair, stroking their gray beards. But they follow this up by suggesting that the hardest problems are the ones you thought to have already squared away. So, the saying ends up ringing of humility and experience, rather than arrogance. To me, it feels similar to one of those old martial arts proverbs: poetic, wise, somewhat comical…
…but at the end of the day, you might not really know what to do with it.
Sure, we’ve all stared at a blinking cursor, fumbling around in our brains, trying to figure out what to call something that is precise in our minds computationally, but difficult to encode into a relatively short identifier. (Some of us may have even flipped through a thesaurus trying to find synonyms to already-occupied words.)
This is merely one of the many comical realities about textual programming systems—where relationships must be encoded by duplicate usage of textual identifiers—and around the Internet you’ll find numerous jokes on this exact concept. And, yes this situation can be frustrating, but one of the most difficult problems in programming? Really? What in the world is going on here?
Emergence: The Divorce of Effects and Computational Concepts
At some point in one’s programming journey, though, the saying begins to make sense. The exact moment might differ from person to person, but for me, it was when I made an explicit mental distinction between effects and computational concepts.
I’ll unpack that.
An effect is a perceived result of computation: a knight, running around on the screen according to a joystick, slashing a sword when you hit the B button, hitting a goblin, and a big magical poof when the goblin dies. It’s the product of imagination—it’s what seems to happen, according to your mind, when you interact with an imaginary program or device which has not yet been built. (Or, when you perceive actual interaction with a program or device which has been built.)
Computational concepts, on the other hand, are the tools and abstractions you directly codify in implementing a system which aids an imagination in producing effects.
It’s fairly common to teach beginner programmers to immediately merge these two ideas. In this model, a beginner should take their desired effects—which, as a beginner, will be high-level and perceptual, rather than related to computation—and codify them as computational concepts. A knight? A sword? A joystick? A goblin? A poof? Clearly, we need class Knight {…};, class Sword {…};, class Joystick {…};, class Goblin {…};, class Poof {…};. No naming difficulties here!
Don’t be fooled, though—this is the exactly wrong place to start.
The subsequent stage, for programmers who learn this way but choose to proceed forward in their journey, is to immediately unlearn this technique of merging effects and computational concepts, and to instead understand how perceived effects may arise from data transforms. Knights and Swords are irrelevant concepts to your machine—they’re purely ideas that the human mind interprets from light, vibrating air, and interactive behavior.
The idea that there is such a thing as a Knight in your machine is a lie—you need a way to get pixels on the screen in a certain way, to play sound in a certain way, to receive data from a joystick in a certain way, and to simulate physics in a certain way. So, instead of working with Knights and Swords, you begin working with rendering, audio mixing, input data, and physics simulation. Those are the true kernels of the problem. To begin by codifying the high-level effects you desire is to make zero progress.
And, importantly, this is inevitably how dynamic systems must be organized for flexibility, computational efficiency, and code deduplication—around computational requirements, not high-level perceived effects. Codifying high-level effects cements you to them—soon, you won’t want a Knight nor a Goblin, but other such effects which exhibit slightly mutated properties.
Too many programmers who have learned this lesson, however, take it too far, to the point of cringe-inducing nihilistic reductionism. The takeaway from all of this is not that the knight does not exist, just like the takeaway from the discovery of the cell is not that the human does not exist. Indeed, such reductionism taken to its logical conclusion is anti-beauty, anti-life, and anti-meaning.
The takeaway is that, instead, the effect of the knight arises through a composition of other effects. A knight is the final result of a beautiful symphony of cooperating systems, all clicking together in just the right way. A human player controlling a knight fighting a goblin on a screen is not a trivially-derived effect from a CPU executing any set of instructions, and so it cannot arise immediately (and who would want such a CPU anyways?). It must instead arise from a set of carefully-designed supporting systems, which themselves arise from others, and so on. The effect of the knight exists at a higher level of abstraction, and it somehow is more than the sum of its parts—as such, it can be said to be an emergent effect.
These supporting systems correspond with layers of some computing system—hardware or software. One layer has the task of taking the tools it has available and providing a useful set of computational or abstractive abilities for other layers, which depend on it. One layer is one “rung” in the “emergence ladder”.
When considering the problem of producing the effect of a knight on screen fighting a goblin, it becomes clear that the intended high-level perceived effect slices through a multitude of overlapping layers. There is no one spot that you may point to and call “the knight”—everything is simultaneously the “knight” (or, whatever highest level effect happens to be produced). Each layer peels away one sliver of the problem until—at last—a knight.
Thus, the answer to “why is naming so difficult?” becomes clear—for a multitude of overlapping layers, there are a multitude of design decisions and computational concepts to define, all of which must balance often-innumerable tradeoffs relating to efficiency, reusability, reliability, and so on. It’s not as easy as taking the name of the effect you want—the knight—and using it. It may seem this easy when programming strictly at the highest level, but soon the wool is peeled from your eyes, and things start getting confusing.
Emergence in Encoding and Decoding
The idea of a single high-level effect slicing through several layers of analysis becomes apparent when working with any sufficiently complex encoding or decoding problems.
Take the example of a file—let’s just say it stores some complex, uncontrolled JSON—and it must be parsed by a program which needs to interpret its contents.
What “are” the contents of the file?
Bits. First we might say that it’s a big stream of bits. And that is necessarily true, because all data on computers is encoded as a stream of bits. But that’s not very useful.
Bytes. It might be more useful to consider it as a stream of bytes, just by grouping each sequential eight bits and considering them as one unit in the stream. But that is still not enough information to interpret the data.
UTF-8 Codepoints. So then we might consider the stream of bytes as a stream of UTF-8 codepoints. Now our program can interpret variable-length streams of bytes as characters, allowing our codepaths to recognize letters and symbols. Nevertheless, we still have a ways to go before we can interpret the data in a useful fashion.
Tokens. So we might then begin tokenizing the stream of UTF-8 codepoints, producing a token stream. These tokens group multiple codepoints together and classify them, allowing us to consider things at a slightly higher granularity. Now, our stream’s granularity buckets important concepts for interpretation—names, numbers, symbols, and so on—directly. Nevertheless, we still can’t easily interpret only the tokens—the JSON may include hierarchical structures, for instance, which are embedded in the token stream.
Syntax Tree. So we might begin parsing the stream of tokens, producing a syntax tree. This encodes hierarchical and list-like constructs—as defined by JSON—directly, allowing us to consider concepts at that level of abstraction.
Schema. And finally, we might add yet another layer of interpretation to the syntax tree according to our program’s specific rules about what is encoded in this JSON (our particular “schema” of JSON).
So—let’s return to the original question—what are the contents of the file? Are they bits? Bytes? UTF-8 codepoints? Tokens? A syntax tree? Constructs in our custom JSON schema?
Now, I hope, you see—picking any one of these layers of abstraction would be overly reductive. The contents of the file are simultaneously something at all of these layers. Each stage in the pipeline emerges from the previous.
Naming, in this case, is not as difficult, because parsing a textual file format is a problem that is continuously revisited. But notice that in an unexplored problem space, useful terms at various layers—like “token”, “codepoint”, “syntax tree node”, and so on, in the parsing case—do not exist, and so they must be invented. That is why naming becomes particularly difficult.
The above set of concepts I walked through is, not coincidentally, the order in which a program which parses the file must execute. I may have started considering this problem by wanting the last step—to parse the file and use it as configuration data for my program, or something of the sort—but the solution for the problem began at the opposite end of the pipeline.
Emergence with Arena Allocators
Now that I’ve walked through some of the ideas behind emergence, I can provide more insight into a topic I’ve written and spoken about before: the arena memory allocator.
Note: There is an unfortunate confusion in the programming world about the term “arena”. Some individuals mean something different by “arena” than what I, for example, mean by the same name. My original post on arenas has even been referenced as a useful arenas resource by a conference talk that defined arenas differently! Needless to say, there is a remarkable amount of confusion on the subject. Nevertheless, I’ll remain consistent in what I mean by “arena”—a simple linear (or “bump”) allocator, possibly growing, particularly which is used as an API construct, and not merely an implementation detail.
I’d like to shed some light on the statements which I’ve seen surprise the most—those referring to an arena as a core building block for a diverse array of memory allocation problems, not merely a useful tool in a constrained set of scenarios (like short-lived temporary allocation). After all, I have claimed that arenas make systems programming in C feel nearly like writing in a garbage collected language, and emergence is crucial in making that point.
Many new programming languages introduce formal allocator constructs. Usually, they define an “allocator” as an abstract interface. In these languages, an allocator can be an arena, or a pool, or a heap, or something else. But in my original post on arenas, I introduced the idea of implementing a pool allocator by composing with an arena allocator, meaning the “allocator” in question was simultaneously an arena and a pool.
This is done by using a single free list together with an arena:
struct Foo
{
Foo *next;
int data;
};
struct State
{
Arena *arena;
Foo *first_free_foo;
};
Foo *FooAlloc(State *state)
{
Foo *foo = state->first_free_foo;
if(foo != 0)
{
state->first_free_foo = state->first_free_foo->next;
MemoryZeroStruct(foo);
}
else
{
foo = PushArrayZero(state->arena, Foo, 1);
}
return foo;
}
void FooRelease(State *state, Foo *foo)
{
foo->next = state->first_free_foo;
state->first_free_foo = foo;
}I’d like to relate the above allocator to the topic of this post.
The arena implements one part of a pool: the problem of obtaining new memory, and bundling a collection of allocations into a single overarching lifetime. The arena is the most basic layer. The additional logic relating to the free list—a layer which depends on the arena—implements another part: the problem of taking fixed-size blocks which have been allocated, marking them as released somehow, and being able to quickly re-obtain them upon a subsequent allocation.
This is another example of emergence—the pool allocator cannot be directly found within the above code, and yet the effect of a simple pool allocator emerges from the composition of a free list with an arena.
The same idea can be used for a number of other, more complex allocators. As I mentioned originally, I’ve implemented pools, heaps, and quad-tree allocators with arenas (although most problems fall into either the arena or pool category). They compose in identical fashion to the above pool allocator.
Closing Thoughts
Emergence is a powerful and beautiful concept—it can help explain the cooperation of many seemingly-unrelated models or systems. Look no further than the sciences: out of physics emerges chemistry, out of chemistry arises biology, out of biology arises psychology, and so on. It can explain the cooperation of a complex system at many levels of abstraction—as I write this post, I move my fingers to hit keys, yet I am also writing words, and yet also sentences, and paragraphs, and sections, and so on. It can help describe complex, non-centrally-organized economic systems—and how they might produce a pencil.
For me, the discovery that I, too, could leverage the power of emergence in computing was delightful—and immeasurably useful.
This post may seem abstract, but nevertheless it represents one attempt (of many) to communicate what I see as my own tactile knowledge in programming. For me, considering complex, seemingly-intractable systems as emergent systems has sometimes made them somehow tractable. It has been useful in building dynamic systems, where I am not slowed down—as if in molasses—even with rapidly changing designs and requirements. It has been useful in structuring concepts in my head around their computational requirements, which has immeasurable benefits in performance and code deduplication.
And, with this post, I hope I’ve helped you discover its utility also!
If you enjoyed this post, please consider subscribing. Thanks for reading.
-Ryan