Welcome back! This week in our exploration of sequences we’re going to do something a little different. Up until now we’ve been looking at a single running example of a function that interacts with sequences, and progressively developing its interface and considering the consequences of each choice. But this week I’d like to delve a little deeper into the meaning of these strange concepts of push and pull, as they apply to sequences.

What is push and pull?

Wikipedia doesn’t talk directly about “push” and “pull” as coding patterns, but does talk about the related concept of a push technology, which it says is a

…style of Internet-based communication where the request for a given transaction is initiated by the publisher or central server.

There is also a corresponding Wikipedia entry for pull technology, where requests are initiated by the client.

So here it seems that these terms are, in a sense, used to say which side of communication interface has control, or initiates an action. If the server has control, and is the one to initiate or “cause” the transaction, then the server is pushing to the client.

We can apply the same principles to software design at a smaller scale. When your code calls a function, it could be said to be a client of that function. When your code uses an object, it could be said to be a client of that object. So our server-client relationship applies in these cases as well.

Pull

Consider the following simple piece of C code which might be used to print a sequence of values to the console:

initProducer();
for (int i = 0; i < numValues; i++) { 
    int value = produceValue();
    printf("Value %i: %i\n", i, value);
}

This code uses the values from the sequence, so it’s a client of the sequence. It accesses items from the sequence by calling produceValue, which pulls the next item from the sequence. The pulled value is available to be used on the very next line of code, where in turn it’s pushed to the console output. Whatever is producing the sequences responds to the pull by providing the pulled values as they’re requested. This is the same iterator pattern that we’ve been looking at in past posts¹.

Push

What happens if the producer of the sequence needs to provide these values by pushing them to the consumer?  Now our consumer code might look like this:

int i;

void initConsumer() {
    i = 0;
}

void consumeValue(int value) {
    printf("Value %i: %i\n", i, value);
    i++;
}

All the same elements of the code are here: the declaration of int i, the initialization of i to 0, printing the values to console by printf, and incrementing i after every value is consumed. The producer just has to call initConsumer before it starts producing values, and it has to call consumeValue every time it produces a new value. So here the producer is in control, and decides when new values are available.

Strangely enough, by writing the consumer in such a way that it doesn’t pull values, the producer code might look much like our original consumer code:

initConsumer();
for (int i = 0; i < numValues; i++) { 
    consumeValue(i * 10); // produces values 0, 10, 20, 30, ...
}

It’s clearly much easier to write producer code that pushes, and consumer code that pulls. But these two things seem to be at odds with each other – either the producer or the consumer is “in charge”, and the other one loses out. Many sequence-manipulating functions both produce and consume sequences, since they have an input and an output. It’s much easier to write these kinds of functions if they can pull from a data source, and push to a data sink.

C++ seems to deal with this by dividing “sequence processors” broadly into 2 categories: on the one hand we have containers (and their corresponding iterators) which are happy to be both pushed-to and pulled-from. On the other hand we have algorithms and application-specific functions, which both push and pull from containers in order to get their job done. These application-specific functions can be written more simply because now they don’t have to worry about being pushed-to or pulled-from.

It’s as if the containers act as peace-makers, mediating between all these functions that all want to be in charge, that push and pull the data whenever they find it most convenient. But as I’ve mentioned before, containers almost always come at a cost, and it would be better if they weren’t the default solution to the problem of manipulating sequences.

Harmony between Push and Pull

But consider what happens if we take our first example, and replace getValue with the getchar from the stdio library:

for (int i = 0; i < numValues; i++) {
    int value = getchar();
    printf("%i\n", value);
}

This code instead reads the values from the console². This is still a pull, since the code appears to be actively causing the value to be acquired, and just like before, the value is available to be used on the very next line of code.

But yet we also know where these values ultimately come from: they come when the user pushes keys on the keyboard (this is a “push” in two senses of the word). How can it be that both sides of the interface think that they initiated the transaction?

In many ways I think it’s equally true that both sides did really initiate the transfer. This example shows that it’s possible for the parties on both sides of the interface to feel like they’re both in complete control, calling the shots and deciding when the next value should appear. In this particular case what’s happening is that the thread is suspended or blocked until the value becomes available.

Let’s step out of reality for a moment, and imagine a strange world with different laws of physics and time. Imagine that I decide I want to talk to my friend, and after dialing his number on my phone, the phone freezes me in time, without forwarding the call to my friend. There I am, suspended in time in my room for days, not knowing that the world is continuing around me. A few weeks later, of his own accord, my friend also spontaneously decides it would be a good time to give me a call. After dialing my number, time unfreezes for me, and I hear his voice as if no time had passed at all for me. To me, I feel like I called him, but to him, he feels like he called me. In fact both are true: we both initiated the call.

This is very convenient for both my friend and myself, since we both waited till the perfect moment to call each other. Neither of us were interrupted by “receiving” the other person’s call (possibly while we were in an inconvenient state, such as in the shower or on another call).

The same is true in the world of code. Code which pushes and pulls is much easier to write than code which is pulled-from or pushed-to. State management is much easier, because code that is pushed-to has to be prepared to be interrupted (hear: race-conditions and re-entrancy problems).

Just like freezing time is difficult in the real world, multithreading in the software is not easy either (although it’s obviously much easier to suspend thread-time than to suspend physical time!). But lets take a look at another example, this time in C#:

static void Main()
{
    foreach (int value in Values())
    {
        Console.WriteLine(value);
    }
}

static IEnumerable<int> Values()
{
    for (int i = 42; i < 52; i++)
        yield return i;
}

The example is simple. In our main function we have a loop that pulls values from a sequence of values returned from the Values function. The Values function which produces the data also has a loop, and pushes values the consumer (Main). Don’t let the keyword “return” deceive you into thinking that that the Values function is not pushing, since the act of returning is initiated by the called function, and the function progresses to the next line of code when the consumer comes back for the next value. The code would look pretty much the same if yield return i was instead produceValue(). Or to put it another way, the code would look horribly different if Values was actually just responding to pulls and not structured in such a way that it’s pushing.

Neither the Main function nor the Values function is more in control than the other – they are like a pair of coroutines, cooperatively yielding control to each other. Both are written as if they’re in control, which makes the code much simpler to write. And best of all, it does this without using any extra threads! This is the power of the generator – to be able to write functions  which produce values by pushing them, while their consumers are able to pull them. The best of both worlds.

1. Except that the producer state is statically allocated, which may not be a good thing in general but it makes for a simpler example ↩

2. Or other standard input ↩

The other day I had to write a function in C which decodes Unicode characters from a sequence of bytes in UTF-8.

UTF-8 is a variable length encoding, meaning that one character (known as a “code point”) can be represented by any number of bytes – usually one or two bytes. The exact format of UTF-8 is irrelevant for this series, but you can find more information on Wikipedia if you’re interested.

So what we want is something that takes a sequence of bytes, and produces a sequence of Unicode characters.

sequence of bytes -> sequence of Unicode code points

But in this series I don’t want to talk specifically about UTF-8 sequences. The concepts I want to investigate with this example aren’t unique to UTF-8 decoding. Many of the problems we solve in software development involve writing code that transforms a sequence of one thing into a sequence of another. Whether its parsing objects from a file, querying objects from a database, or presenting data to the user. In fact most programs don’t do anything except process sequences: they accept a sequence of user input, and produce a sequence of reactions to those inputs.

So, sequences are important, and figuring out how to represent and manipulate them is also important. In this series I hope look at a few different ways of representing sequences, and consider the pros and cons of each. I’m not going to be looking at any one particular programming language, so the insights I uncover should help understand sequences in any language at a deeper level. I’m going to start by looking at C, because of its simplicity and lack of abstraction. Then I’ll consider other common languages such as C++ and C#. And I’ll finish off by pointing out the common flaws across all of these languages, and consider a new hypothetical language to address these problems.

Attempt 1

Let’s start with what is perhaps the most obvious implementation in C. The function must accept a sequence of bytes, and return a sequence of characters. In C, as in many languages, a common way of representing a sequence of something is with the use of an array. So let’s have a function that accepts an array as input, and produces an array as an output:

wchar_t* decodeUtf8_attempt1(const uint8_t* data);

Since this is a language-agnostic investigation, let me explain that uint8_t is, unsurprisingly, the type representing a byte. And wchar_t is one of the types that can be used to represent a character (in this case a Unicode code point). The const modifier is good practice, and in this case means that the data passed to the function is strictly input data, and that the function promises not to modify it.

The implementation for this function is too boring to show here, but would do something like this:

1. Run through the input data, counting the number of Unicode characters
2. Allocate the memory for the output array of characters, probably by calling the traditional C malloc function
3. Run through the input data again, this time storing each output character in the output array
4. Return the output array

Problems

We can see immediately that there are problems with this implementation. Perhaps the most striking is that we’re making two passes over the input data. In terms of performance, this might not be serious: it might might make an O(n) operation into an O(2n) operation, which is still an O(n) operation, and not much slower. On the other hand if the input data is large enough then the beginning of the input might not still be in the CPU cache by the time we make the second pass, and it could land up a lot slower.

A more important problem with making two passes over the input data is that we’re breaking the DRY principle. The second pass is very likely to repeat a lot of the code used in the first pass. It wouldn’t be difficult to accidentally predict a slightly different size on the first pass than you use on the second pass, and land up with some ugly memory bugs.

But actually, we can’t do much better an implementation of the function given this particular function interface (aka function “prototype”). We could perhaps have avoided the double pass over the input data if we’d chosen to provide a conservative over-estimate of the output array size by using the fact that there will never be more Unicode characters than bytes. But this would be a clever trick that wouldn’t apply to sequences in general, so it’s not relevant to our investigation. Or we could perhaps have avoided the double-pass if we were willing to incur extra overhead of resizing the output array as we encountered more characters while parsing the input. And indeed this might have been a preferable way to go since it avoids some duplicate code, although it’s debatable whether it would be more efficient.

Heap, Memory and Ownership

Another issue with this implementation/interface is that we’re allocating memory at all. The heap is slow by most definitions. If you’re in a multithreaded environment the heap is generally also a shared resource, causing thread locking, CPU multi-core cache invalidation, and a variety of other effects that would put the breaks on our program.

Once the heap space is allocated, somebody needs to free it. There are the usual problems with this: added risk forgetting to free memory results in a leak, or freeing it twice or prematurely and having difficult-to-track-down bugs in the program. But there’s also a more subtle issue: since the function abnegates ownership of the result-array to the caller, the caller is coupled to the implementation of the decoder function. That is to say, the decoder function chose to implement the output as a heap-allocated array, but now the caller also has to be aware of this implementation detail because it needs to also access the heap to free the array. This coupling would make it difficult to change the implementation down the line to use some other dynamic storage, such as a memory pool.

Availability

But there’s another memory-related problem that’s also pertinent to our investigation that’s hiding in our function interface: both the input and the output sequences are completely “populated” before they’re passed across the interface boundary. Or to put it another way: the entire input sequence is passed to the decoder function at once, and it returns the entire output sequence back to the caller at once.

It would be a terrible thing if all sequences were manifested like this. Imagine if, in your favorite desktop application, it were necessary for you to perform all the clicks and key presses before you ran the program (so that the whole sequence of input events is “populated” before the program is invoked), and then execute the program on those clicks and presses, and it in turn skips through all the GUI sequences that correspond to those clicks and presses. Some things clearly work better if you can provide input in a streaming fashion, rather than a batched fashion. We’ll talk more about streaming implementations later in the series.

The Good Parts

So there are lots of problems with this naïve implementation. But there are also some good things, which may not be obvious amongst all the flaws I’ve highlighted.

For one it’s a very simple interface and implementation, and simplicity is often severely underestimated. It’s very easy to understand how to use it and what it’s doing. Whoever is maintaining it doesn’t need to understand any complicated patterns or language features.

Another benefit that may not be immediately apparent is that the implementation decides exactly when and where it wants to read from the input (I call this “pull“, since the function actively pulls elements out of the input array), and exactly when and where it wants to write to the output array (I call this “push“, since the function actively pushes into the output array). This makes for a simpler and more maintainable implementation.

Next time I’m going to look at another alternative function interface – one which accepts a “push” input rather than a pull one – and we’ll compare this with our first solution.

In software design, we’re often obsessed with perfecting the qualities software has right now, or the qualities of how the software should be under ideal conditions in the future. We don’t often focus on designing changes to software – we mostly focus on the start and end points.

Imagine different components of a software system dancing together – each step of the dance is a change to the component. In an ideal situation, when software development is complete the dance stops and players remain perfectly still in their final state of interlock. No change is required, because the software is “finished”.

But no software is like this. When a software project first commences the dance floor is empty. Gradually new players/dancers are introduced to the dance floor. Dancer’s positions and poses are change to accommodate each other. Bug fixes and refactorings change the position or pose of dancers that needed fixing.

But by today’s software design practices this dance is nothing but a crowd of players, each one rigid in his/her shape. We go to great lengths to fix solid the interface between the players (components) – their interlocking posture – and then we hope never to change it again. Instead of a dance, this is like a weird game of twister. Players have to hold their position as steadily as possible. It’s considered a design flaw if changes to one player cause changes to another player – this is software coupling.

Let me emphasize this point: todays design practices emphasize immobility and decoupling between components of the system. This is very valid way of dealing with the dancing problem: limit the movement of the dancers so that they don’t run into each other. Give them each enough space so that when they do need to move a little they won’t influence others around them.

But we know all this comes at enormous cost. The interfaces have to be clearly defined and agreed upon – never to be changed – so they better be correct right at the beginning. We have to use complicated interfacing patterns – facades, indirection, visitors, injection. No longer can we just call function foo. We now have to add foo to the interface, and inject the concrete object through the construct, saving it until we need to call it, and then call it through an adapter because it didn’t quite have the right structure¹.

So these principles solve half the problem: slow down the game so that it’s easier to keep everyone separate. But there’s another solution which also deserves attention: formalize methods of change. That is, formalize the dance moves.

For example, here’s a situation I’ve encountered. Let’s say a program X calls a web service Y. So X and Y hold a single dance position with each other. Now lets say we need to add a new parameter to the service. What moves can we make?

• We can simply change X and Y, and deploy them at the same time.
• We can change Y first to accept the new parameter, but not require the new parameter, and deploy Y. Then we can change X to provide the new argument, and deploy it
• We can change X first to provide the new argument, and deploy X. Then we can change Y to use the argument, and deploy Y.
• We can create a new service Z which supports the new parameter, and then update X to use Z.

The order of footwork is important: we can’t change X to require that Y have the parameter if it doesn’t yet. We can’t change Y to require the new argument, if X isn’t supplying it yet. We can’t deploy X to require the new service Z, if the new service hasn’t been implemented yet. There are a number of steps in this part of the dance, and the order is important.

The above example is simple, and could just be solved by reasoning it out, but you can see it could get complicated quite quickly. If some data had to be passed back from the service as well, then the moves become more intricate.

Do any of these dance moves have a name? Not that I know of (but correct me if I’m wrong). We don’t have names for them, and we also don’t really have a standard notation to describe the moves. And what about tools, and what about static analysis? What if the development tools could give a compilation error if we make an illegal dance move?²

This doesn’t just apply to distributed systems. It applies equally to self contained programs, or within modules and components themselves. For one thing, things don’t get developed atomically. A developer can only write one line of code at a time, and each new line of code is a small dance move. If the move is illegal, you might get a compilation error or perhaps your unit tests fail. It’s much better to be able to develop in small increments, rather than having to go a week with failing tests. I’ve certainly had times like that: where I started a “small” refactoring but it was weeks before the code even compiled again. Instead of engineering a sequence of small legal moves, I made one multi-week leap – flying dangerously through the air. This is the same thing that I’ve seen happen with producing new major versions of software: it takes months or years to develop the new major version from scratch, and only then can it be introduced to the dance floor with the customers. It would be better to engineer a sequence of small changes to get from the old version to the new one, even if the new one has a completely different architecture.

This is also important for collaboration, since software teams don’t make changes atomically either. There are dependencies between different people’s development, and order is often important. Every time you commit code to the common repository you’re making a dance move with your team mates, and you don’t want to tread on their feet. A formal discipline of change engineering would make it easier to coordinate this dance without having to resort to tons of scaffolding or indirection code.

Coupling can be good

I’d like to make one last point and say that coupling can be a good thing. The reason is perhaps obvious: the more connected two pieces of code are, the easier it is to directly access information between them. All the rules we have for decoupling generally add layers of indirection, which in turn makes it harder to see what’s really going on (the runtime structure looks less and less like the code structure), and harder to add new functionality because you have to weave new pieces of data through all the decoupling layers and interfaces. The “god-class” anti-pattern is, practically speaking, a great pattern to use if you have a program that’s only a few hundred lines of code.

The apparent problem with coupling is that solidifies the program. You can’t change one thing because it requires a change to something else. Each coupling link is an iron beam that connects the two pieces: when one moves, so does the other. Enough iron beans and the whole system becomes completely rigid. You don’t want to change anything because you would risk breaking everything else.

Although decoupling addresses this issue, so does dancing. That is, if we can define formal rules for changing components that are coupled together, we are expanding the number of coupled pieces that we can handle in the system. We’re replacing the iron beams with hinges, and allowing the dancers to interact directly with each other without being rigid.

Conclusion

In software engineering and design, there is perhaps too much emphasis on the fixed state of code. You generally design software with a single endpoint in mind, rather than the sequence of atomic changes required to get there without breaking the system at each checkpoint. These are almost independent of each other, and there should be a new discipline for change engineering, so that we can build more robust systems, minimize risk, and reduce code. For large systems there should perhaps even be dedicated engineers focusing on the problem of change design, formally engineering the sequences needed to move the software towards long-term goals of the company, rather than letting the dancers to wonder undirected into a dead-end of rotted software before starting again on a new version.

1. Don’t think to hard about this example. The point is that it’s normally a long process to do something that should be simple ↩

2. Don’t underestimate the power of this possibility ↩