Simple Function Design

Program Complexity and Design

Many software developers today notice that average code quality is less than desirable, and although the problem is well studied, it is not yet solved in a widespread manner. In light of this, and having spent a lot of time refactoring lately, I'd like to sketch out a basic theory of program complexity based on functions and see if provides insight into better design.

The Purpose, the Algorithm, and the Function

When designing a new function, there are three main forms which should be considered in order:

1. The purpose: the important relationships between a function's input and output
2. The algorithm: a high-level (English or pseudo-code) description of how the purpose is fulfilled
3. The function: the particular implementation in language X that runs best on machine Y

The purpose of the function is not its entire effect, only the part of it that we care about. A function that adds a list of integers has the same purpose no matter what order it adds them in. The purpose serves as the entire description of a function's interface. Ideally, a few lines of commenting should be able to describe a function's purpose.

Once a purpose is described, someone steps up and designs a decent algorithm to get it done. With any luck, there is already a published paper on the subject and the algorithm can simply be looked up. The algorithm is arguably the most crucial component. My requirement for an algorithm will be that it must provably fulfill the desired purpose, and preferably that proof is simple.

The code for the function itself should look as much like the algorithm as possible. This makes it easy for programmers to prove that their code is fulfilling its purpose, by reusing the proof from the algorithm. The function's interface should look like the purpose description. In fact, it must be usable knowing only the purpose description. Anytime you need to know the internals of a function to use it, that implies that the purpose description is insufficient and should be changed.

The following diagram illustrates these three components, with arrows indicating how one dictates another.

Next we can consider the complexity of a program composed of such functions. Complexity here means the effort required to understand the program. Note that this is not the actual structural complexity of the program but rather the the difficulty of discovering the structure of the program by reading it. Compare this to checking a list of integers for sorted order. No matter how well sorted they are to begin with, every integer must be checked to prove that the whole list is sorted. Similarly, given a program, one must assume the worst-case structural complexity and then check all the possible interactions to discover which are actually relevant. In this model, the only assumption is that functions are properly abstracted by interfaces.

Complexity over Function Length

Every line of code is one of three things (in this basic model):

1. A primitive: addition, bit shift, etc.
2. A conditional: just counting the 'if (condition)', not the lines to execute
3. A function call: interface, purpose

To simplify this model, loops can be seen as tail recursion with conditionals, like in Lisp. When conditions are about as simple as a primitive statement and function interfaces are also that simple, then we can say that a line of code is a constant unit of complexity.

Now, look at the holistic complexity of a function that is L lines long. In the worst case, every statement depends on every statement before it:

function f(a):

b = f2(a)

c = f3(a,b)

return f4(a,b,c)

In which case the complexity of the function is order L^2, since there are (L*(L+1))/2 interactions to understand. In the best case, statements are just a pipeline:

function f(a):

b = f2(a)

c = f3(b)

return f4(c)

In which case the complexity of the function is order L. From this we see that L is the lower bound and L^2 is the upper bound.

Program Complexity

Now lets look at a very simple model of a program: the whole code is N lines long, and all the functions are L lines long. By definition, there are N/L functions. In order to understand the whole program, one can start at the main function and perform a depth-first search of the call graph, understanding each function in that order. Such a search still traverses each function only once, so the complexity of the program is just (N/L)*(L^2), which turns out to be N*L. This simple expression can be interpreted this way: for every line of code you look at, you will have to examine its relation to at most L lines above it.

This simplified model concludes that we should minimize N*L: minimize the length of functions, but also remember not to lengthen the codebase when shortening functions.

User vs Programmer Understanding

There are two important levels of understanding any system, whether it is a car, a television, or a program: the understanding needed to use the system versus the understanding needed to make or change the system. I commonly see the misconception that once a system is mature or stable, focus shifts heavily to user-level understanding and little care is taken to preserve a deeper understanding.

The need for a deeper understanding of a program arises whenever it has to be changed. The implementation has to changed when it doesn't fulfill the purpose. Maybe it was written wrong to begin with, or maybe the purpose has recently been changed.

A bug is an implementation that doesn't fulfill its purpose right. Porting a program to a new OS/arch is an altered purpose. Making a function faster is an augmented purpose (and possibly a new algorithm). Making a function thread-safe is a refined purpose. Note that each of these changes is often undertaken by one person and could require understanding the whole program.

Conclusion

The ultimate reason to minimize complexity is to maximize productivity, i.e. the speed of carrying out the changes listed above (and others). Investing in simplicity speeds up future development and reduces future bugs. If a program is designed using purpose-only function interfaces, then the N*L complexity measure should hold roughly and provides a good rule of thumb for making programs readable and maintainable.