Rethinking goto, Part 2

A while back I discussed some ideas for new branching constructs to compliment the if-statement and switch-statement in a low-level language. Today I’m going to tell you about another pattern which I’ve seen commonly used to represent complicated control flows without gotos.

First, lets come up with some example of a control flow that doesn’t fit well into the standard branching constructs of switch, if, while and for. The example I’ve devised is deserializing fields from a binary stream. Let me explain the hypothetical situation before I go into the solution. In the stream we have a byte that represents the field type: perhaps a 0x01 represents a “short string” type, a 0x02 represents a “long string” type, and a 0x03 represents a 32bit integer type. If the field type is a short string, then we’ll say the next byte in the stream is a length of the string field, and the bytes after that are the characters in the string field. If the field type is a long string, then the next 4 bytes are a 32bit length followed by that number of characters. If the field type is an integer, then the next 4 bytes are simply the integer value. Here’s an example stream that has a short string “AB”, followed by a long string “C”, followed by the integer 421:

If the field is a string, then after we know how long it is we need to check that all the characters are valid string characters (by some specification we don’t care much about right now), and if the string passes validation then we copy it into wherever it is going. Here is a reasonable flowchart illustrating these steps as directly as possible:

First, lets represent this as directly as we can in C code. The first branch is clearly a switch statement, but  the most direct way to represent the remaining control flow is using gotos.

I would argue that this is actually the most readable way of representing it, particularly if people maintaining the code can refer back to the flow diagram. It’s easy to reason about, since each block starts with a label and ends in a goto. I’ve chosen to order it in a similar way to the flow chart, so that control only  flows downward. This code is no more “spaghetti-like” than the diagram is. In fact, it reads very much like a document or book would: each label is a heading marking the section as a stand-alone unit.

But goto’s are bad, right? Well this is an endless debate, but let’s assume that they are and that we need an alternative. How about this:

It satisfies our requirement of not using gotos. Of course now we need to elevate some of our local variables to global variables, but nobody complains about global variables as much as they do about gotos, so this is an improvement, right?

Well, no. From a readability perspective nothing much has changed. The “headings” are now function names rather than labels, and the gotos are now function calls, but the code otherwise looks the same.

Bad code using gotos can trivially be represented as equally bad code without gotos – or possibly worse code because it’s now more spread out and pollutes the global namespace with extra functions and persistent variables. I’m not saying this is bad code – it may or may not be, but that’s beside the point. The point is that it’s not just possible, but trivially easy to write “spaghetti code” without gotos, since I believe any goto-based code can be similarly converted to function calls2.

Goto-Call

This brings me to another, more subtle point. The above example is an abuse of the idea of a “function call”. This may be subjective, but I think that the idea of a call (at least in an imperative language) is to perform a sub-task and then come back to the calling task to complete whatever operation it was on. There is an implicit hierarchy here: the called function is a “sub-function” in terms of its contribution of the caller. This is physically manifested in the call stack, where you can see that the calling function still has an activation record on the stack while the called function is executing, in anticipation of re-acquiring its temporarily delegated control.

This is not the way I’m using the “function call” feature in the above example. I’m instead intending it as a “fire-and-forget kinda call”. The caller isn’t saying “I need your help, can you please do this for me and get back to me later”, it’s saying “I’m done, you’re next, I grant you control from now on”. The latter idea sounds familiar – permanently passing control one way from one part of the program to another. It’s called a goto. And I’ll use the term “goto-call” to mean a call to a function in such a way.

An example that comes to mind of where I’ve seen this intention in a function call is in raising events in C#. I’ll take an example from the MSDN guidelines for raising an event in C#:

What does the call handler(this, e) on line 6 mean? Does it mean “I need your help, get back to me when you’ve got an answer”, or does it mean “goto the place I’ve called handler and I don’t care if you come back to me”3? It means the latter. It’s a “goto” in disguise.4

In a high level language this doesn’t matter. Using the feature of “calling a function” for “going to another part of the program” is fine. We waste a little stack space keeping the caller state when we don’t need it, incur some minor overhead preserving registers and allocating the new frame, and make it harder to read the call stack when we’re debugging, but the language is less complicated than it would be if we had to distinguish a “goto call” from a “normal call”.5

In an embedded microcontroller environment, and in a very imperative, stateful environment, I don’t think this is the case any more. I really think that low level languages like C should support a “goto-call” feature which is like a call (control moves to another function and you can pass arguments) but is intended never to return the caller, or is intended to return to the caller’s caller.

From the programmer’s perspective the “goto-call” would be a mechanism of communicating the intent of the code to other programmers. It tells other people reading the code that this is not a call “stack” operation, but a call “queue” operation – it’s one thing happening after another rather than one thing happening during another. It also tells the compiler “I don’t intend control to come back here”, so the compiler can helpfully produce an error if the “goto call” is not a valid tail call.6

Conclusion

I’ve shown that the problems with using goto are not unique to the goto feature, since there is a relatively trivial translation from goto-style programming to a form that uses function calls instead. I’ve used this as another argument as to why goto’s are not intrinsically bad, since you can write code that is at least as bad using function calls, and we do not consider function calls to be intrinsically bad.

I’ve also suggested that since calls can be used in this way, that sometimes we conflate the idea of a “call” with the idea of a “goto-call”, and suggested that if some imperative languages distinguished between the two by supporting a new “goto-call” feature then it would not only make the intent of code clearer to its readers, but also enable additional static checking and performance optimizations. I’ve given two concrete examples of where this would be useful: the example of reading a hand-crafted format from a binary stream in C using functions, and the example of event dispatching in C#.

1. Assuming little-endian integers and ASCII character encoding

2. I’ve glossed over some other differences between the two ways of doing it. If you use function calls you don’t have control “falling through” to another function by default if you forget to call the next function. Also, it’s much more difficult to combine traditional control structures such as while loops with this “function call” form. I think neither of these factors decrease the “spaghetti-ness” of the function-based code. However functions have some additional flexibility: we can call functions indirectly through pointers, we can put them physically wherever we want, and we have more access to the individual states from “outside”. Whether or not these are good things depends on the situation.

3. Of course it does need to come back to somewhere, but it could come back to the caller of OnThesholdReached, like a tail-optimized call

4. Another example that comes to mind is in continuation-passing style calls, where you typically execute a continuation as “I’m done, you’re next” and not “do this and get back to me”. Keeping the caller of the continuation on the stack is the moral equivalent of keeping the “returner” of a non-CPS function on the stack

5. For those who’ve worked with C# async, wouldn’t it be wonderful if the continuation of an “awaiting” function didn’t have a gazillion frames in the call stack, especially with recursive algorithms like “await the previous item in a long list”

6. Perhaps ironically, in attempting to justify a more imperative style of programming using goto’s, we’re actually encouraging a more functional style of programming using mutual tail recursion to “loop” through a stream.

2 thoughts on “Rethinking goto, Part 2”

1. One of the ways I have tackled this kind of problem in the past is to set up a series of functions that operate on the data stream and update the position of the data stream. I have used C++ style uint8_t*& for this purpose, but it can easily be adapted to other languages. All this code is very rough and hasn’t been compiled or tested.

The top level function prototype looks like this:

It starts at position pData, reads a field, sends that field data wherever it is supposed to go (which was unspecified in your original example so I feel safe leaving it unspecified here) and updates pData so that it points to the next piece of data after that field.

Internally it will look something like this:

{
switch ( readFieldType( pData ) ) {
case SHORT_STRING:
break;
case LONG_STRING:
break;
case INT:
break;
}
}

and the readFieldType function will look like this:

{
return *pData++;
}

Again, there is a pattern here of getting some information *and* updating pData.

The only difference between reading a short string and reading a long string is the way the length is obtained, so readShortString and readLongString get hold of the length in the appropriate manner then pass things on to another function:

{
int length = *pData++;
}

{
int length = getStringLength( pData );
}

readString is the function that has to cope with a possible error – the characters in the string might not be valid, however regardless of whether there’s an error or not it needs to update the data pointer to skip over the number of characters in the string. This means that readString can look something like this:

void readString( uint8_t*& pData, int length )
{
// We know where the string is and how long it is. Do whatever we need to
// here, including checking for errors. If the string is valid pass it on to
// whatever it is that cares about it, if the string isn’t valid, signal an error
// in an appropriate way.

// …..

// Regardless of whether the string is valid, update the data pointer past
// the end of the string.

pData += length;
}

I think your original flowchart makes things more complicated than they need to be by making “skip n bytes” dependent on the error (or lack of) in the string.

1. elec.mike@gmail.com says:

Thanks for the critical feedback. I think you’re correct, and I would probably have developed a similar solution myself if I was faced with this problem in the wild. In fact I might have moved the validation out of the parsing completely, but that is a different story.

Regarding your proposed solution, your readString function still has to deal with one of 2 possibilities:

1. The validation may fail, in which case the number of characters must be skipped
2. Or the validation passes, in which case the number of characters must be copied and the cursor must also be moved

As you say, in both cases the cursor must be moved, so you could chose to have the “copying-of-the-characters” not move the cursor, and instead move the cursor as a separate step which is common to both paths. But I think the control flow graph will look quite similar. The main difference, from what I can see, is more about which branches of the graph you’ve grouped into the lifetime of same function vs which are split into separate consecutive functions. (How many “returns” occur before a particular call, and therefore at which stack depth does the control move to the next logical step in the sequence).

But to step back a moment, what I was trying to do was not find an optimal solution to a particular problem, but rather to find a problem that best illustrates something that would most directly be representable in this sort-of “braided” control graph. It seems conceivable that there are domain problems which fit this classification, although perhaps my example is flawed.

Or perhaps it isn’t flawed, but instead you’ve subtly re-characterized the problem in a way that makes it easier to represent in structured C. For example, in the implementation that uses gotos (or an equivalent non-existent goto-call), all the steps in parsing are on the same level. That is, none of the blocks are considered to be sub-parts of any others. This matches the way I described the problem: I didn’t say that in a stream a string is represented by a subparts defining length and actual char data, but rather as simply the sequence that they follow. The former is a hierarchical structure, while the latter is a flat structure (even though the bytes are the same in each case).

If the format never changes, then perhaps you can reinterpret the implicit structure however you like. You could equally say that the fields are *preceded* by the their type, or say that they’re *prefixed* by their type (ie that the type is logically internal to the field data rather than external). But if the format (ie domain) may change, then the model you use to describe this hierarchy may become inconsistent with the way the domain changes within its “master model”.

I don’t know how this might happen in the case of the stream example. Maybe, lets say that version 2 of the stream format introduces an “encoding” byte for strings to distinguish between UTF-8 and UTF-16. For short strings the encoding byte is *before* the length, and for long strings the encoding byte is *after* the length. Why? Because it’s part of the “out there” domain and is out of our control. The guy who designed the format doesn’t see any reason to be consistent about it, because neither order breaks his mental-model of “the stream is flat, not hierarchical”. The original code he wrote to output the stream correspondingly used a flat structure, so his seeming inconsistent view fits perfectly with the code and is trivial to upgrade to version 2. On our side though, the change contradicts a pattern we thought we saw in the format, which turned out to be a coincidence. (Or what if the domain actually considered the field type to be suffixed to the previous element in the stream, even though we assumed it to be prefixed to the current element – what havoc could ensue when the format starts accumulating properties of a field *after* the data-type-byte for the following field!).

I may be stretching the analogy a bit ;-) And it’s actually not that difficult to implement the corresponding change in the hierarchical code. The point is that the most direct way to implement the solution based on the problem statement may still be goto-based code. Using more “structured” techniques may imply structure that is not a true representation of the domain, or may even be contradictory to the domain. Even if it isn’t true in *this* case, I think that may just be a flaw in my example, and I propose that it isn’t false in the general case.