Category: Uncategorized

Everything you don’t say

Everything you don’t say

Recently I was reading an old blog post I came across about productivity variations among software developers, where he says that “researchers have found 10-fold differences in productivity and quality between different programmers with the same levels of experience and also between different teams working within the same industries“. My immediate instinct as I was reading it was that it makes perfect sense, and it’s supported by my own experience, and from what I hear from others in the software industry.

But at the end of the post, he talks about a study which compares productivity of the teams for Excel and Lotus, and makes between their productivity in lines of code:

 Excel’s team produced about 13,000 lines of code per staff year. Lotus’s team produced 1,500 lines of code per staff year. 

It’s interesting the huge difference in lines of code per staff-year, but is that really a measure of productivity? It’s not clear from the post whether a high LOC-per-year is considered high or low productivity, but it seems to mean high productivity in this context. If this is so, then I am probably the least productive person in my team. I make an effort to write as few lines of code as possible.

In fact for the last few months my average LOC per day is probably negative, if you count deletion of lines as negative lines produced1. That sounds terrible, but it’s because I not only try to write as few lines as possible, but I also simplify other people’s verbose code as I go through it. It’s not uncommon for me to rewrite existing code using 5 or 10 times fewer lines (typically simpler lines).

Let me clarify though. Writing fewer lines of code is not my goal, it’s a side effect. What I try to do is write simpler code. Code that’s easier to reason about. Code that’s more pleasant to maintain. Code that has fewer bugs just because it’s simpler. What generally results from this is fewer lines of code. I do consider fewer lines of code to be a goal, but only in service of readability.

Leverage

Another reason why fewer lines of code can be a good sign, is when you consider how much leverage each line of code has. I don’t know if leverage is the right word here, so let me explain. What I mean is simply a small piece of code that has a big effect, because of some amplification mechanism. For example, a bad coder might repeat almost the same line of code 20 times, while a good coder will instead write a for-loop which amplifies his single line of code to cover 20 cases2. A good programmer will use abstractions like this (and polymorphism, generics, frameworks, code generators, DSLs, etc) to amplify small pieces of code to great effects. A good programmer is not one who can write 1000 lines of code, but one who knows how to write 1 line of code in just the right way that it can be reused 1000 times. If he continues to write another 999 lines of this kind of code, he will have produced 1000 times more than the man who wrote the 1000 lines which had only one use34.

This sort of leverage is not linear, because good software engineers can leverage the leverage. They can abstract the abstractions. Any time you find yourself repeating something, you write code to do it for you. The more abstractly you can recognize these patterns, the more generally the solutions will apply and the less code you’ll need to write to get things done (although you have to be careful to not make code more complicated in all the abstraction).

Conclusion

I do understand that getting a quantitative measurement of programming productivity can be incredibly difficult. If it was easy, I could just give potential employers my objective productivity “score” in various areas of expertise, and they could simply hire me according to how this fits their objectives. It would also make it easier to pay software engineers what they’re individually worth. But I think “number of lines of code” is terrible variable to proxy for productivity. Especially when you look at the extremes of the spectrum, where people are really productive or where people get very little done.

This doesn’t change the fact that, at least for me, a better solution is one with fewer lines of code. Every line of code you don’t write is valuable, and often this value outweighs the cost of planning how to not write that line.


  1. If you didn’t count deletion as negative, then the best way to be productive is simply to delete and rewrite the same function every day for the rest of your life 

  2. You might think this is a bad example because nobody would write the non-for-loop code, but it’s exactly the situation I found just the other day 

  3. It’s difficult to qualify the word “use”, since this doesn’t need to refer to the programmer himself reusing the code, but could also just refer to the number of times it’s executed, like in the example of the for-loop 

  4. You might think 1000-times reusability is ridiculous, but there are number of places where I’ve achieved this level of “amplification”. They seem to normally manifest themselves as frameworks 

Thoughts about Random Access

Thoughts about Random Access

Recently I’ve been thinking about what it means for a data structure to support random access (aka “direct access”). This may seem so obvious that it’s not worth thinking about: an array supports “random access” because you can access any element with O(1) complexity by just calculating the elements position and going straight there. A linked list doesn’t have this property because the only way to get to an element is through other elements that it’s linked to. But let’s explorer this idea further.

Here’s one way Wikipedia explains random access quite well:

As a rule the assumption is that each element can be accessed roughly as easily and efficiently as any other, no matter how many elements may be in the set, nor how many coordinates may be available for addressing the data

Let me add another note to this which is perhaps obvious but not normally specified: we’re talking about runtime complexity. If we had a linked list completely defined at compile-time then I would still classify it as a “random access”, even though linked lists are normally not considered to be random access1.

So what is it about an array gives us random access? Let’s take a guess: it’s because the elements of the array are stored contiguously in memory.

ContiguousElements

This seems like a reasonable first guess. Because “element 2” is known to be after “element 1” which is after “element 0”, we can calculate where “element 2” is. To get the position of element 2, we multiply the size of an element by 2, and move to that binary position in the array.2

But what if the elements aren’t all the same size?3

ContiguousVariableElements

If element 1 in the array might be larger than another then we can’t multiply anymore so we need to somehow sequentially access the elements, right? Well, no. If the size of element 1 is known at compile time then we can simply offset this amount when calculating the positions of any element that comes after it.

Perhaps I deceived you when I said all the elements aren’t the same size in this example: I didn’t say whether or not there was static information about the sizes of elements. Lets say that we have an array, which we’ll define such that every second element is 4 bytes big, and every other element is 8 bytes big. To calculate the binary position of an even element in the array we just use `index / 2 * 12 + (start of array)` and to calculate the position of an odd element in the array we just say `index / 2 * 12 + (start of array + 4)` (assuming some implicit integer truncation). These are both constant time operations.

So to sum up, it’s not about whether the array elements are the same size, or how they are laid out in memory. It’s about what we know at compile time vs what calculations needs to be delayed until runtime, and how complicated those runtime calculations need to be. If we go back to our original definitions then this isn’t anything new – it’s just a restatement of our definition of random access. But it does make me think a bit differently about it. 


  1. This would be quite difficult to do in most languages. You could do it in C++ with template meta programming 

  2. Actually it’s not the size of the element that counts, but the pitch of the array – there might be padding bytes between elements to help properly align them. But let’s just imagine the “size” includes the padding between the elements 

  3. I don’t know any compiler that will generate arrays of elements that don’t all have the same inline value size, but we’re not so much talking about what compilers do as about what could be done 

Rethinking goto, Part 2

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 `goto`s.

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:

Example-stream

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:

ReadFieldFlowchart

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 `goto`s.

void readField()
{
    switch (readFieldType()) {
        case SHORT_STRING:
            // ...
            goto validate_chars;
        case LONG_STRING: 
            // ...
            goto validate_chars;
        case INT: 
            // ...
            goto assign_to_field;
    }

validate_chars:
    //...
    if (isValid)
        goto skip_n_bytes;

skip_n_bytes:
    // ...
    goto next_field;

assign_to_field:
    // ...
    goto next_field;

next_field:
    // ...
}

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:

void readField() {
    switch (readFieldType()) {
        case SHORT_STRING:
            // ...
            validate_chars();
        case LONG_STRING: 
            // ...
            validate_chars();
        case INT: 
            // ...
            assign_to_field();
    }
}

void validate_chars() {
    // ...
    if (isValid)
        skip_n_bytes();
}
void skip_n_bytes() {
    // ...
    next_field();
}
void assign_to_field() {
    // ...
    next_field();
}
void next_field() {
    // ...
}

It satisfies our requirement of not using `goto`s. 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 `goto`s, 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 `goto`s are now function calls, but the code otherwise looks the same.

Bad code using `goto`s can trivially be represented as equally bad code without `goto`s – 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 `goto`s, 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#:

protected virtual void OnThresholdReached(EventArgs e)
{
    EventHandler handler = ThresholdReached;
    if (handler != null)
    {
        handler(this, e);
    }
}

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. 

Unifying Layers

Unifying Layers

Software architecture theses days is all about separating things. For example, MVC patterns separates the view from the model it represents and code that governs its behavior. Or applications that have a data access layer, a business logic layer, and a presentation layer, to separate different aspects of the application. All these approaches come down separation: for instance you should hypothetically be able to change the way you data is displayed (the presentation or view) without needing to change the model or how the data is accessed.

But how do these approaches actually work in reality? My experience has almost always been the opposite: the more separation there is, the longer it takes to develop. I’ll give you a few examples…

MVVM

A few years ago was doing a project in WPF. If you don’t know, WPF is a Microsoft technology for developing GUIs (or rather, a framework on which GUIs can be developed). It could be said to be the successor of WinForms, and when I was researching it, it certainly looked very attractive.  The underlying architecture it encourages is called MVVM – Model View View-Model, which is similar to MVC. In essence, the “model” is the data in your application, the “view-model” is the data represented in a form that you want presented to the user, and then the view is the actual graphical presentation of this data.

This is great in principle. It means the graphic design team can work on the view and how to present the information to the user in the most flashy way possible, while other teams work on the view-model and model. If there’s some business reason to change the presentation, you can do it without changing anything else. But here’s the catch: all these teams were just… me. It wasn’t such a big project that we needed more than one person working on it, so it was just me. Suddenly all the layers are just things that get in the way. When I need to add piece of data to the model… Now I need to add it to the view-model and view as well, and add all the wiring that connects them. And now we have the same domain object smeared across multiple files.. the xaml file for the view, a view-model C# file, and a model C# file. If the domain changes a little, you need to update all 3 files.

Web Layers

Another example that comes to mind is a website I’m working on. This one is not a one-man project. We have a team of 5 or 10 developers (depending which roles you consider to be part of the actual site development), and the site has hundreds of pages. The architecture chosen for website, when it was started a few years back, is to have separate layers for data access, business logic, business objects, and presentation. In addition to these, there are “layers” underneath the data access layer for stored-procedures and then for tables in the database.

This seems like the perfect situation for a layered architecture. We can have database professionals working on the SQL side of things, and user experience professionals working on the presentation side of things, professional software engineers working on the business logic, and some kind of entity framework or something similar for the data access.

But that’s not what we have. The reality is this: the customer requests a new feature; the feature gets handed off to one of the developers, who implements the tables or fields to store the data, the stored procedures to read the data, the data access layer to call the stored procedures from the web server, the business object layer to represent the objects fetched from the stored procedure, the business logic layer (which is normally almost empty, but gets implemented anyway), and finally the presentation layer so the user can actually see the new data that was added. The end result is about 5 or 10 new or changed files across a few different platforms and whole lot of layers. All for one logical change, like “a customer now needs an address field”.

Is the problem the way work is distributed among developers? Would it be more efficient to have 5 people working on the one logical problem, so each can work on a different layer? No, I don’t think so. Sure, the database would be more efficient, and the presentation layer more presentable. But even with 5 people, the same total work would need to be done, except now you have the extra overhead of coordinating between multiple people on the same logical change – a change that probably evaluates 20 lines of real, business-valued code (smeared across a number of different places). If you can afford the extra inefficiencies, the result might be better, but at an extraordinary price which I would say is only suitable in particularly large corporations.

A successful model

In my mind, the two above examples show how layered development can get in the way of real productivity. The feeling separation “good style” it provides is a lie. But what’s the alternative?

Well, it so happens that I do have a successful alternative. I recently finished re-architecting another project to avoid exactly this problem. To give you some background, the application is a server which mediates between a remote embedded system and a database server (among other things). The original architecture was like the layered one described above: a communications layer, logic layer, and data access layer – each in its neatly separated. If you needed to add some new domain concept you would need to add it to all three layers: the communication layer to be able to transfer it from the embedded system, the logic layer to specify how it should be transferred, and the data layer to interface to the database. Not to mention the extra man-hours spent debugging the connectivity and marshaling between the layers themselves.

So, what was solution? For starters, you should put all your related code together – related by business concept not by activity. You don’t keep “communication” code together – you keep foobar’s communication code in the same place as foobar’s logic and database code. If it was a web application, I would be saying that you shouldn’t universally keep all your JavaScript files together, and all your CSS files together1. A rule of thumb I would apply is this: If you were to no longer need a particular domain concept (or feature), could you just delete the one file or folder and have it just disappear with no residual or side effects? If so, then the reverse is also true: it’s easy to add a new domain concept without spattering new code across the whole code base (or multiple code bases).2

The second part of the solution is to remove repetition. Since the data “layer” is now really just a hundred mini data layers – one for each separate domain concept – but we don’t want to repeat the same data-accessing code in every file. There are many solutions to this. The one I happened to choose in this case was to write a .NET IL emitter, which at runtime would automatically do a one-step transformation of a C# interface definition into the communications code or database code required. The code behind each “mini-layer” can’t get any smaller – it’s just a single interface, with no explicit implementation.

Unified Layers

The result is amazingly maintainable code. All the code related to a single domain feature is consolidated within a single file or handful of related files in a folder, so the process of responding to requests for feature changes or additions generally involved changes to a very isolated part of the code base.

Taking it further

This architecture has proven itself highly successful. The types of maintenance done most often take the least amount of effort, and only ever change or add code in a single isolated subset of the codebase. Also, as much as 90% of new code is actually business logic, rather than boilerplate and wiring code.

It really makes me want to take it to the next level. I mentioned that this project is a mediator between an embedded system and a database. So in effect, the whole application is a “layer” in a larger system. In fact, the web system I was talking about is also a layer – between the database and the end-user. When there is a new domain concept to be added to the system as a whole, they need to be added to all of these super-layers. Why not unify all layers? The embedded C code that relates to a particular domain concept should be physically right next to the SQL that stores it, and the HTML that displays it. If the feature is simple, they could even be all in one file. Static type checking can verify that everything’s compatible.

Each “unit” of code would span multiple platforms and mediums, but hold only a single business concept. Sure, there will be dependencies.. but you can manage these dependencies in the same way that you would have managed dependencies between business concepts in a single layer back when the architecture was layered.

Conclusion

I won’t lie, it would be a difficult goal to achieve to have a fully heterogeneous business units that spans multiple environments and languages. But the problem is not that it’s a bad idea. The problem is just that it goes against the existing way of doing things, and the existing way has a lot of support and tools. Another reason is that the existing system is very good for large teams of highly specialized individuals who can each work on a separate layer, while the “unified layer” system is best for small teams and individuals who have skills in all the different environments that a feature spans. In other words, the big money is behind the layered systems, at the expense of generalists like me who would develop much more efficiently in unified systems.


  1. This only applies to files that are tied to a particular domain concept. Of course the styles and scripts that apply globally across the site should be in a common place, such as a “css” and “javascript” directory 

  2. In the real world there will always be dependencies between domain concepts, but this is largely an orthogonal problem. 

Mutating Types

Mutating Types

This is an idea I have for a feature for a statically typed language which would make the type system more expressive. I call it "mutating types", and in a nutshell the idea is that the act of mutating a variable can also change its type.

I’d like to preface this article by saying that I’ve come up with this idea completely on my own, meaning that if it appears that I’m copying some other academic work it is completely unintentional, and please let me know if I’m doing it. Likewise, please don’t use this idea without acknowledging that it’s mine, and please contact me if you do intend to use it, even if you modify it somewhat.

I apologize in advance for how long this "post" is. I felt it was important to start with the problem description to put the idea into context, and to end with some explanations of how this might be used in practical situations.

The Problem

Let me illustrate the scenario with an example. I’m going to add the feature to C++ in this example. Consider the following types:

struct Int{
    int value;
};

struct Null {
};

struct NullableInt {
    bool isNull;

    union
    {
        Int intValue;
        Null nullValue;
    } value;

    void set(Int i) { value.intValue = i; isNull = false; }
    void reset() { value.nullValue = Null(); isNull = true; }
};

So, a NullableInt is a tagged union which can either hold an integer with a value, or null. I’ve been unnecessarily explicit about the types for Int and Null, because conceptually they are subtypes of NullableInt. Now lets say we have the following code which defines a new Int with a null value, and then calls a function to give it a new value, and then prints out the value that it has.

int main() {
    NullableInt myInt;
    myInt.reset(); // Initialize myInt to null value

    // Call a function to set the value to 42
    setValue(myInt, 42); // function defined below

    // Print out what the value is
    if (!myInt.isNull)
        std::cout << "myInt is " << myInt.value.intValue.value << std::endl;
    else
        std::cout << "myInt is Null" << std::endl;
}

void setValue(NullableInt& i, int newValue) {
    Int newInt;
    newInt.value = newValue;
    i.set(newInt);
}

The function setValue mutates a NullableInt. The particular mutation is just to assign it to a new value, but in general imagine that the mutation might be more complicated.

What I want to point out is on line 9: we have to check whether the value is null or not, even though we know the value isn't null because of the behavior of setValue. Well, obviously we don't need to check the value, and probably most people wouldn't, but there is nothing about the type signature of setValue that says it won't set it to null. In other words if you just assume that it's not null, you're relying on the maintainers of the setValue function to keep that behavior consistent, and not the compiler. This is a reasonable assumption in this case, but perhaps a bad thing to rely on in general.

How would we guarantee, through the type system, that setValue always "outputs" an Int and not a Null?

Option 1: Avoid Mutation

Well, the functional-programming bias in me might suggest the following:

Int setValue(NullableInt& i, int newValue) {
    Int newInt;
    newInt.value = newValue;
    return newInt;
}

In other words, we avoid mutation altogether, and simply calculate a new value based on the old and return it (in this case the new value is not dependent on the old, but in general it could be, which is why I added i as a parameter). The returned value is of the more-specific type Int and not NullableInt, echoing the intention of the function not outputting a nullable value.

This is elegant, but it's not the same thing. For one thing, there are life-time issues. The original value is not destroyed until after the function returns (presumably by the caller), and it's impossible to specify otherwise. In a language with deterministic destruction this is just simply not the same thing, and it has consequences in performance. Quite often, mutations are small changes to a big thing: a state machine changing state, a list acquiring a new item, etc. Creating a whole new "big thing" is just a waste of time1.

Option 2: Mutating Types

So far I've explained the problem, and also how an immutable style doesn't fix the problem. Now for a real solution, the crux of this post: lets define a mutating type.

I don't know what syntax is best for this, but for the sake of being explicit I'm going to define a mutating parameter type as (T1->T2), where T1 is the type passed into the function, and T2 being the type passed out. It is implied that a mutating parameter type must be pass-by-reference. For example:

void setValue2;
    foo(x);
    foo(x); // err... problem!
}

Here, the fact that foo takes an auto_ptr as a parameter means that it implicitly takes ownership of the pointer. However, the ownership semantics are only a runtime construct in this case, because the compiler doesn't even warn when bar tries to use the value that it just gave away3. But we could rewrite this using mutating types:

void foo((int* -> void) x) {
    cout << *x << endl;
    delete x; 
}

void bar() {
    int* x = new int(42);
    foo(x);
    foo(x); // compiler error: foo expects type `int*` but instead got type `void`.
}

What this example is showing is that the act of passing ownership actually changes the type, so that the type can indicate ownership. Since x is deleted in this case, the new type is void to indicate that the type has no possible values. This not only removes a whole class of possible bugs, but also could potentially improve performance by avoiding unnecessary value-checks.

2. Mutating conditionals

I won't go into too much detail, but imagine that we could eliminate type-casting by instead using mutating conditional statements. That is, if-statements which actually alter the type of their operands.

struct Animal { };

struct Cat : Animal {
    void meow();
}

struct Dog : Animal {
    void bark();
}

void foo(Animal& animal) {
    if (animal is Cat)
        animal.meow(); // the conditional altered the type to `Cat`,
    else if (animal is Dog)
        animal.bark(); // so no type-casting necessary
}

There are some open questions here. For example, what does the is operator look like in this hypothetical language? But you can see possibilities!

3. Once-off subscription/continuation

Here is another situation I run into quite often. In an environment with limited resources you can't always afford to have multiple subscribers to an event. It creates a nice inversion of control to have an event in the first place, instead of a direct function call, but for the sake of performance you aren't going to maintain a dynamic structure to handle the possibility of multiple subscribers because you know there's only one.

typedef void (*Action)(); // Function basic pointer type

struct Event {
    virtual void invoke() = 0;
};

struct UnsubscribedEvent {
    virtual void invoke() { }
};

struct SubscribedEvent : public Event {
    Action _func;

    // Constructor
    SubscribedEvent(Action func) : _func(func) { }

    // Override invoke
    virtual void invoke() { _func(); }
};

void subscribe((UnsubscribedEvent -> SubscribedEvent) event, Action func) {
    delete event;
    event = new SubscribedEvent(func);
}

struct ModuleXStuff
{
    UnsubscribedEvent someEvent;
}    

void initialize()
{
    ModuleXStuff moduleX = initModuleX();
    initModuleY(moduleX.someEvent);
}

void initModuleY((UnsubscribedEvent -> SubscribedEvent) event) {
    subscribe(event, &moduleYsomeEvent);
}

void moduleYsomeEvent() {
    cout << "Some event fired" << end;
}

I won't explain this example too much, since if you've read this far you probably already understand it. The idea is that module Y, whatever that is, needs to subscribe to an event from module X. This is achieved by module X exposing an UnsubscribedEvent, which module Y can mutate into a SubscribedEvent by subscribing to it. Subscribe should actually be a member function of UnsubscribedEvent, but this-mutating member functions is beyond the scope of this post.

The same logic can be applied to continuation functions:

void someLongProcess((UncalledContinuation -> CalledContinuation) onDone) {
    // ...
    // result = ...;
    call(onDone, result); // call the continuation

    call(onDone, result); // Type error, cannot call "CalledContinuation"
}

This is useful if the continuation has some cleanup work to do. If someLongProcess forgets to call the continuation then there will be a type error. And if someLongProcess double-calls the continuation then there will be a type error.

Conclusion

I haven't fully described it here, but mutating types could have a whole host of other uses, and I can't even begin to go into all of them. Most are related to resource and state management, which are particularly important in low level, imperative languages such as C. They are not restricted to "function parameters", although the description of a more general system gets a little complicated to put in a blog. I've only touched the surface, but perhaps I will go deeper in a future post.

Mutating-types embrace the stateful, mutable world that is low-level embedded- or systems-programing. They open up an avenue not just for creating more readable software, but also for making it safer and more performant. I think it would be a great addition to many languages.


  1. Of course, I'm all for the idea of writing simple code and having the optimizer recognize where it can reuse memory and so on, but an ideology of C is that we can have more predictable guarantees about performance, and mutation is one way of achieving that 

  2. NullableInt->Int) i, int newValue) { Int newInt; newInt.value = newValue; i = newInt; } int main() { NullableInt myInt; myInt.reset(); // Initialize myInt to null value // Call a function to set the value to 42 setValue(myInt, 42); // Now, myInt is actually of type Int, and not NullableInt // Print out what the value is std::cout << "myInt is " << myInt.value << std::endl; }

    If you try to interpret the example as straight C++ it may be a little confusing, since Int is not actually a subtype of NullableInt, but this is a different issue. The point is that the function setValue mutates one of it's arguments, and puts restrictions on this mutation by specifying the mutating type.

    Usefulness

    The previous example is pretty contrived. Is this really a useful feature? I'll give you a few examples from real-life where this would be useful.

    1. Resource ownership

    In C++ you can specify pointer ownership using smart pointers. But there's something I've found missing from smart pointers: the ability to specify at compile-time that something acquires or loses ownership.

    void foo(auto_ptr x) {
        cout << *x << endl;
    }
    
    void bar() {
        auto_ptr x(new int(42 

  3. Note that C++11 move semantics don't really address the problem 

Navigation by Compile Error

Navigation by Compile Error

Where is the mistake in this code:

void myPrint(int x) {
    printf("%s", x);
}

The problem is that `x` is declared as an integer, but used as if it were a string. But my question was, where is the mistake? Is the mistake that `x` is declared as an integer, or is it a mistake that `x` is used as a string? A compiler would probably chose to highlight line 2 as the problem (possibly as a warning in this case).

Compile errors are usually conflicts between two different assertions in the code. “Undefined field”? – it’s a conflict between using a field and not declaring it. You can either solve it by adding the field, if you intended it to be there, or by not using it, perhaps if you intended to use a different field.

The problem is that compilers almost always only error on one side of the conflict. This is sensible in some ways, but inconvenient in other ways.

I have a habit of using compile errors as a means of searching through code. If I need an extra parameter in the function I’m working on, I simply add it. The compiler will automatically “find” all the places where the function is called with one less value than it should be, and takes me to those places to modify the code. In other words, I’m relying on the compiler to tell me where I need to change the code.

And there’s the problem with only getting an error on one side of a conflict: it only takes you to where you want to go half the time. If I want to add an argument to a function I’m calling, the error will be on the code I’ve just written rather than on the function declaration I need to add the parameter to. Likewise if I use an undefined field or function of an object, it would be nice if the error took me to the class declaration so I can change the class.

Yes, there are ambiguities in deciding where exactly the other side of the conflict is. Is it the base class? Which overload of the function do we go to? Where would the variable be declared? But I think a simple approach would be for the compiler to present a few of the top candidates and list them along side the error. The programmer could click to go to the code location, and perhaps the IDE would even perform the obvious action at the same time, like adding in the parameter or field at that location.

Would you find this useful?

Rethinking goto

Rethinking goto

Most programming languages have support for an if-statement1:

Untitled1

The if-statement is a branch which splits two directions: one direction for `true` and the other direction for `false`2. The code after the if-statement is executed regardless of which branch was taken, so in effect the two branches come together after the if-statement3.

Most of the languages I’ve encountered also define some variant of a switch-statement, which is the concept of an if-statement except generalized to any number of branches:

Untitled2

Just like the if-statement, control returns to a single path after the switch-statement.

But what about this example:

Untitled3

So far as I know, there is no language construct which can directly represent this idea, except that of `goto`.

Here is another, slightly more complicated, example:

Untitled4

It’s difficult to come up with a simple program that follows this flow without repeating condition checks or other some other unnecessary overhead. Again, the answer may be to use a `goto` in this case.

But practically, when would you ever run into a complicated branching construct that doesn’t fit so well into `if` or `switch`? Well, lets look at this often-required-but-difficult-to-implement flow:

ErrorBranch

I’ll call this the “error-branch statement”, because I don’t know of a better term for it. A sequence of operations needs to be performed, and each may fail to common error branch. If we say that a switch-statement generalizes an if-statement to have multiple alternative branches with one condition, the error-branch statement generalizes an if-statement to have multiple conditions with a single alternative “else” branch.

A try-catch-statement could be used to model this behavior, but there are many situations where exceptions are more trouble than they’re worth. This is particularly true in code embedded on a microcontroller that needs to run indefinitely, which is the type of code I deal with quite often. And an error-branch-statement would probably be a more idiomatic fit into a language like C than exception handling would.

Here’s another type of error handling branch I would find handy in low-level language like C:

ErrorBranch2

I broke convention here and changed physical orientation of the error handling flow path because it fits better. This is the same case as the error-branch statement before, except each operation requires different cleanup code if it fails. For example, if operation 1 is to open a file, cleanup 1 might be to close the file again, etc.

In C# this type of branching is achieved by a `using` statement and exceptions. In C++ this type of behavior is achieved using RAII and exceptions. In C there is no direct way of representing this, despite the fact that I’ve seen this pattern more often in C than any other language. In C you have to settle: either goto, nested ifs, function calls, error state variables, etc. None of them is quite the right fit, and the code reads as if it were more complicated than it really is.

What about the other flowcharts I presented earlier? Why can’t we represent those using structured-programming constructs? Well, you can’t define a new branching statement for every possible flowchart, so instead we need a generic mechanism to handle arbitrary cases. In C this is the `goto` statement: it allows us to define any arbitrary control paths for anything we want to.

Next time I’m going to dig deeper by discussing an alternative to `goto` which I’ve seen used quite often, for better or worse.


  1. I’m using a basic flowchart representation 

  2. Obviously the else/false branch may be empty if it hasn’t been specified 

  3. I’m ignoring exceptions and returns and other such things in this basic flow 

Dynamic scoping is better

Dynamic scoping is better

When I first discovered that there was a thing called “dynamic scope”, I was amazed that there was actually another way of doing “scope” other than lexical scope. Part of the amazement was the thought, “why would anyone want to do it that way, it seems so error prone!”. Apparently others agreed, because you don’t see dynamic scope much in modern languages anymore.

For those who don’t know what dynamic scoping is, let me give a quick demonstration in a fictitious language:

void foo()
{
    string x = "Hello World!";
    bar();
}

void bar()
{
    print(x); // Prints "Hello World!" if called from foo
}

In the above example, x is in scope in bar not because bar knows about foo but because bar is called by foo at runtime.

At first glance dynamic scoping seems terrible. It reminds me of programming in assembly, where a called routine may refer to the “variable” EAX, whose value is dynamically determined by the most recent time EAX was set – be it the caller code or anywhere else. Surely this is a bad thing?

Wikipedia points out that,

Dynamic scoping also voids all the benefits of referential transparency. As such, dynamic scoping can be dangerous and few modern languages use it

In other words, we can’t really tell what a function will evaluate to because it might use variables we didn’t pass to it, whose values depend on where the function is currently being called from.

As a side note, I think Wikipedia is wrong in this case [1]. The reason is simple: we could just as easily pass the dynamic environment into each function as an argument. Arguments are the bridge between lexical and dynamic scope: the parameter value is determined dynamically based on the context of the function’s execution rather than its lexical context, but its identifier is determined lexically by the parameter name. So functions accessing dynamically scoped variables can still be referentially transparent if the dynamic context is considered to be syntactic sugar for an additional parameter that holds the dynamic environment.

That technicality aside though, dynamically scoped variables are still quite different to lexical scoping in practice. For example a function can access a variable that is multiple frames down in the stack, and it could be quite difficult to predict what value a particular variable might have just by looking at the program.

The flip side

I think dynamically scoped variables can actually be a good thing.

Here’s the reason: global variables.

Global variables are bad [2]. At least that’s what we’ve been taught, and I partially agree.

But what happens when we literally need a single instance of something?

One example is a program. We only need one program in our program [3], and the solution is that we normally need a globally defined main function. How would you write a program in C# or Java if they didn’t have a way to say public static main?

Maybe main is a stupid example of a global variable. What about std::cout in C++? In this case a program has a console interface, and cout is a global variable that represents that interface. One console = one cout. What a pain it would be if cout wasn’t global. We would have void main(ostream& cout...).

In other words, there are places where a global variable just makes sense. These are cases where there really is just one instance of something (or any fixed number of something). All the non-member functions in the C and C++ standard libraries are examples of this. We have one heap, so we have one global malloc function. We have one operating system, so we have one global fopen function.

I can easily extend these principles to functions and classes I’ve written myself. I have a program that accesses one database, reads from one config file, interacts with one GUI. I think all of these qualify just as easily as correct places to use global variables.

Except…

What happens when there are two?

What happens when a piece of program code normally writes to the console, and now I want it to write to a log file? What happens if it uses a native GUI, and now I want to use a web interface, or have multiple client GUIs? What happens if it connects to a database, but now in my unit tests I want it to connect to a mock data source? In these cases, hard-coding access to cout or to myDatabase seems like a bad design decision.

Enter: Dynamic scoping

I think dynamic scoping is a perfect fit here, and I probably don’t even need to explain my reasons because I’m sure you can see exactly where I’m going with this. You can have whole chunks of your program just “assume” that there’s a thing called a “database” without caring where it comes from.

Using dynamic scoping has a decoupling effect. Functions right at the top of the stack can access environments near the bottom of the stack without coupling to anything in between. Nothing is coupled directly to global variables or functions. If you want to override the heap and define your own malloc functions for a particular branch of the program, it’s as simple as pie.

It could reduce code. For an entire module that’s intended for for data manipulation it makes no sense to manually “thread” the database variable as a parameter through the call tree – it’s just work for nothing. The developers implicitly know there is a database accessible from any function in the module, so why can’t the language support that?

It’s an ideal replacement for global variables. In any situation where a global variable might have been a good choice, a dynamically scoped variable will be a better one, and probably better than dependency injection with lexical scoping in these cases. In fact why not just define the whole program as having a “root dynamic scope” which contains all the “global variables” – then any function can override global variables at any time.

Final Note

I have a few final things to say. One is that dynamic scoping doesn’t mean dynamic typing. I think it’s entirely reasonable to have a static type checker enforce the type bindings of a dynamic scope environment. A function has certain environment requirements, and it implicitly adopts the requirements of the functions it calls. The environment requirements become implicitly part of the published type signature of the function.

Finally, let me say that I don’t intend a language to only support dynamic scoping. That would be crazy – lexical scoping is much more sensible 99% of the time. Dynamic scoping is better than global variables, and it’s better than lexical scoping in some situations.

I really think dynamic scoping has promise, and we shouldn’t throw the baby out with the bath water. Yes it’s dangerous, but don’t take the chainsaw away from the lumberjack.

Have you ever worked in a language with dynamic scoping? I’d be interested to hear what your experience is and if you agree with what I’m saying.

[1] I won’t change Wikipedia because I don’t have any evidence of this, it’s just my opinion.

[2] And by extension, static fields are also bad. And since we can use functions as variables (eg function pointers or delegates), static member functions are also bad, and non-member functions are equally bad since they’re just globally scoped function values.

[3] Oh, I didn’t know that

Practical Dependent Types

Practical Dependent Types

This morning I found another practical need for dependent types. The details are confidential, but the situation is a common one so I’m not giving anything away by explaining the general situation.

It’s quite simple: we have an embedded device with a flat fixed “file system”. There are no file names, just 10 fixed-size “slots” where a file can go. Each slot is reserved for a particular module of the program to store its persistent data, and has a binary format that is only useful to that module. For example, slot 3 might hold a configuration for calibrating power module. [1]

So how does the power module read its configuration from the file system? A simple implementation is something like this:

enum FileId
{
    ...
    POWER_SYSTEM_FILE = 3,
    ...
};

void* get_file_data(FileId id); // implemented somewhere else

// The structure of the file the power system uses
struct PowerSystemFile { ... }; 

void power_system_init()
{
    PowerSystemFile* file = 
        (PowerSystemFile*)get_file_data(POWER_SYSTEM_FILE);
    // Use the file to apply the power configuration
}

 

The suspect piece of code is the cast from void* to PowerSystemFile*. I think its generally a code smell to have to cast like this. What may be a clue to the validity of this smell is that if the language were completely type-safe then this cast would be either completely disallowed or it would result in a runtime check (and possibly a runtime failure). And in a language like C/C++, a static cast like this is a potential entry point for catastrophic failure with some very strange symptoms. So the question is, how could this be implemented to not require a cast, so that the compiler can verify that we’re doing the right thing?

This to me is an ideal situation for dependent typing. I’m going to make up a fictitious language that might express the things needed to make this example work the way I want it to.

struct FileSlot; // FileId is the same as previously declared
{
    switch (id)
    {
        ...
        case POWER_SYSTEM_FILE: PowerSystemFile file;
        ...
    }
};

FileSlot* get_file_data(FileId id); // Implemented elsewhere

void power_system_init()
{
    FileSlot;* slot = get_file_data(POWER_SYSTEM_FILE);
    PowerSystemFile* file = &slot->file;
    // Use the file to apply the power configuration
}

 

Let me briefly explain the syntax of the above imaginary language in case it’s not completely self-evident. The struct FileSlot<> take an integer argument. For those who know C# or Java, the syntax should look familiar, except that in this case FileSlot doesn’t take a type parameter but an “enum” parameter. The switch statement effectively creates a tagged union.. depending on the value of id (the tag), a different member of the union will be accessible. In this case though, the tag is not part of the union structure, rather it is passed in as a type parameter.

The especially interesting piece of code is the declaration of get_file_data, which returns a FileSlot<id> which is a type dependent on the parameter value id. This is really the dependent type, since it’s the first time we’re saying that the parameter of FileSlot can be a variable.

For the sake of comparison, I’m going to implement this in C++ as well:

template <FileID id>
struct FileSlot;

template <>
struct FileSlot<POWER_SYSTEM_FILE> // Template specialization
{
    PowerSystemFile file;
};

template <FileID id>
FileSlot<id>* get_file_data(); // Implemented elsewhere

void power_system_init()
{
    FileSlot<POWER_SYSTEM_FILE>* slot = get_file_data<POWER_SYSTEM_FILE>();
    PowerSystemFile* file = &slot->file;
    // Use the file to apply the power configuration
}

 

The first thing I’d like to point out is that you can actually do this in C++. But there are some important differences. The most practical difference in my mind is that the C++ version is purely a compile-time concept. The id is not a parameter of get_file_data, it’s a template parameter that is used to instantiate an instance of get_file_data for each id that it’s used with. If you only knew the id at runtime then this function wouldn’t work at all (for example if you needed a function that loops through all the files to do file synchronization).

In my hypothetical language the FileID id parameter (of both the type and the function) is a real runtime variable. In the case where the id is constant, the compiler could choose to do a constant propagation optimization to emit exactly the same binary as the C++ version, so I don’t see this as a compromise on performance. On the other hand the compiler could keep the runtime version if it was actually more efficient – which in this case it probably is since our model has a flat file structure where get_file_data probably just fetches data from the id location in the file medium.

As a final note, I don’t actually like any of these solutions completely. The reason is code cohesion. This example requires that we define all possible values of FileID in one place (the enum declaration), and correspondingly all possible types (or template specializations) of FileSlot need to be defined in one place (although they may be physically separated by using #include, the coupling is still there). This has some benefits (if you need to know all the file types then you know where to look), but it smells to me because of its lack of modularity. This isn’t a downfall of dependent types, it’s just a downfall of this particular design.

Anyway, I hope that by giving you a practical example of where a dependent type may be useful that I’ve set off a spark in your mind. And I hope I’ve made you feel a little bit more uncomfortable in your most used language, like I am every day. Enjoy the bitter taste now that you can taste it, because without it you wouldn’t know to move to fresher pastures. [2]


[1] This whole example is completely inaccurate relative to the real situation, but it works well as a simplified model that explains the essence of what the requirement is.

[2] If you can’t taste it, don’t worry. Just wait 10 or 20 years and you’ll be jostled along with the rest of the herd.

Programming with no rules

Programming with no rules

A type system in a programming language provides rules and restrictions. They tell you all sorts of things that you can’t do. Ever find yourself jumping through hoops just to satisfy the compiler’s stupid rules? It’s even worse with functional programming, where you can never change the value of a variable after “setting” it. What’s the point of rules except to get in the way?

They give you a path:

When driving to work, you don’t complain that you’re restricted to drive only on the roads. Driving down the road makes easier to navigate. If you were to drive arbitrarily through gardens and parks and shopping malls, apart from wrecking your car you would also find it much harder to navigate. Normally you only have to consider which way to turn when you get to a junction, but now everywhere is a junction! Everywhere is a new choice.

They make it easy:

If society were to abandon roads because they restrict your driving too much, then where would we put the tar to make driving more pleasant? In other words, the more restricted we are about what we’re allowed to do, the better we can work on and improve those few things that we allow.

There are two points to this. The one is that if you have tons of options at each decision in making a program, then to describe one of those options is more difficult. This is simple information theory: the more “expected” something is, the easier it is to represent. The less information you need to convey, the easier it is to say it.

The other point is simply related to the work involved in giving you all the options. It’s easier to make road-cars and roads than to either make all cars capable of driving over anything, or to simply tar everywhere. In other words it takes time and money to implement language features, and time and effort to learn to use them. Although it’s theoretically possible to just tar everything, the resources involved would better be spent on making the existing roads more pleasant and safe to drive on.

They come with some guarantees

The rule that people must drive on the road comes with some great advantages that we all know and love. For example, I don’t need to do my gardening with the expectation that people might drive through it [1]. I don’t need to wear a helmet in the mall. If I better know what to expect from the behavior of a car, then it makes it easier to plan my own behavior and easier to do things in general.

In other words, even though rules can restrict one entity, they really help when it comes to cooperation between multiple entities. And cooperation is the key to making big programs. I’m not talking about cooperation between programmers, I’m talking about cooperation between parts of a program. The more well defined the rules of the game (language and interface specifications), the more the players can play instead of worrying about what others do or don’t do.

If I had to program with no rules, it would only be easy for the very first piece of code. The second piece I would now have my first unruly piece of unpredictable code to interact with, and so I’d have to put on a helmet and tons of error checking.


But what if we just have the best of both worlds? What if we say there are just “guidelines” – you get all the benefits of the rules, except you can bypass them in the case where you have good reason to do so?

Just guidelines

Sounds like a good idea [2]. Now you can drive on the road most of the time, because it’ll give you all the benefits of the rules, but you can turn into a park if you need to get to the other side and it’s too far to go around. We advise you not to cast an int to a std::string, but the referee won’t blow the whistle if you decide that’s what you want [3] [4].

But wait, what about me? Do I need to wear a helmet when I’m potting my pretty petunias or not? I’d better call up every single person who lives in the area to see if they plan on driving today.

In short, guidelines are stupid when it comes to cultivating cooperation [5]. There should be a well-defined set of rules, which the compiler/referee/traffic officer will enforce, that tell you exactly what behavior you can expect from another part of the program. If a function has a return type of a string, you should be damn sure it’s not returning an integer, otherwise there’s no point in playing anymore and I give up!

Public Safety

The metaphors intersect when it comes to security and safety critical applications. The traffic lights are running software, the ATM is running software, paypal is running software, the x-ray machine is running software. In a C/C++ world, where there are only guidelines, and where you can make a call to a string instead of a function, and free a banana instead of a pointer, there is no such thing as guaranteed security. C programs can’t even guarantee that they won’t do something terrible when there isn’t malicious intent. Keeping your password as a “private” unused field doesn’t mean it can’t accidentally be sent to mars, and keeping it “const” doesn’t mean it can’t accidentally be changed. Not assigning to the x-ray-strength variable doesn’t mean it won’t change “on its own” because of some crazy pointer mistake in an unrelated part of the system. No piece of C/C++ code comes with any guarantees when it’s integrated with other code. Instead of commenting functions with what they do, they should all be commented with “this function really does anything, but what I hope it does most of the time is this…”

Conclusion

I do exaggerate a little [6]. But the point is clear: rules offer more advantages than guidelines when it comes to making and interacting with predictable software. Because of its roots in math, software is one of the few (perhaps the only) engineering disciplines where it’s actually possible to completely and perfectly guarantee behavior. And it’s even easier to guarantee the lack of certain unwanted behaviors (eg using strings as integers, or accessing memory you don’t permission to). This is not a “guarantee” in the legal sense, where you get your money back if it’s wrong. This is a guarantee in the mathematical sense, where there is no such thing as wrong. I think we need to use this to our advantage. Seriously.

To anyone who feels comfortable in C or C++ I say, you need to set your standards higher! There is another world on the other side where there is no such thing as segfault or a heap corruption! There is a place where you can tell what a function doesn’t do just by looking at it’s signature! Come and join me!

[1] I don’t actually have a garden. What a shame

[2] Sure, I’ll play along

[3] string s = (string&)x

[4] It’s ok, because I’ll remember to only call it with an int that’s actually a string so I won’t kill any puppies

[5] Guidelines are still good for communication between cooperating individuals, but they can’t be trusted like rules can

[6] Just a little