Type-checking is compile-time evaluation

I've been thinking a bit about type-checking the last days -- especially how type-checking corresponds to compile-time evaluation (CTE). In C++ templates are often used to implement CTE -- it's a messy way of achieving it but it works.

The idea is a language L where the type-checking is implemented purely by CTE. When a compiler for such language compiles a function f it generates (in addition to compiling the function into executable code) a function fs that type-checks each call to f.

The fact the that type-checking is a function make it possible to do all kinds of fun things, like verifying that an argument is an even integer. All that is needed to do this is to create a function (like fs) that checks whatever one wish to check. For instance, such function can be implemented in L itself (or a subset thereof).

Of course, to be able to type-check this way a lot of type-information needs to be available for the type-checking functions (like fs). For providing that kind of information, the compiler needs to (in addition to compiling) know how various kinds of type-information propagate through the program. For instance, if a is an even integer and b is an odd integer, is a * b even?

It is more less straight-forward to figure out how such type-information propagates through arithmetic functions, like a * b. What complicates things are conditionals, but those can be solved too. The real problem is loops.

And that's were I'm stuck right now -- with loops. Not that I've implemented a full compiler, but I've played around with a instruction set for a stack-based VM and how type-information propagates through those instructions. So far the only compiler is my head, though, but I'm using very mechanical steps to compile.

Anyway, as I said, the problem is loops. Generally, as soon as there is a loop in a program very little type-information can be propagated. However, it is my hope that most practical uses of loops can be expressed in a way such that a reasonable amount of type-information can be propagated through functions containing loops. This might imply that there is a need for other kinds of loops that is traditionally used: for, while, and do-while. Or, that only a certain form of for loops are allowed.

This is where I currently spend my thinking.

Andersson's Law

Proebsting's law states compiler advances double computing power every 18 year --- a pretty depressing fact.

Another depressing fact is that the most used language appeared to the public in 1973 -- almost 40 years ago.

The second most used language is essentially a combination of language features developed in the 70th and 80th -- 30 to 40 years ago. This language appeared in 1995 -- 16 years ago.

The third most used language is 30 years old and is based on a 40 years old language with some added features developed 40 years ago.

And the list goes on... Here is a compilation of the ages of the top 10 most used programming languages:

1. 38 (C)
2. 16 (Java)
3. 28 (C++)
4. 16 (PHP)
5. 16 (JavaScript)
6. 20 (Python)
7. 10 (C#)
8. 24 (Perl)
9. 37 (SQL)
10. 16 (Ruby)

Of course, just because a language is old doesn't mean it bad. Not at all. On the contrary, an old language is proven to be good (in some regard).

What bothers me though, is the "new" languages, e.g., Java, C#, or Ruby, which don't really add any kind of innovation except new syntax and more libraries to learn. Come on, there are tonnes of more interesting problems to solve... There is still no way of automatically parallelize a sequential program for instance.

There seems to be a new law lurking in programming language development... I call it Andersson's Law: Modulo syntax, innovation in new programming languages approaches zero.

And here's the "proof":
Every year there are new programming languages, however, a wast majority of those are merely reiterations of features found in previous languages (except syntax). Thus, the number of unique features per new language approaches zero for each year, that is, innovation approaches zero.

I wish for a green compiler

I like programming languages and I like compilers. I especially like how the less-is-more rule applies to programming languages in the sense that what is not available to the programming, the compiler and the run-time environment can do what ever it want with. For example, a language with pointer arithmetic can not (easily) have a compacting garbage collector, while a language without pointer arithmetic can. This can also be said for what optimizations the compiler can perform.

In a language where the memory layout is implementation defined, the compiler can optimize the memory layout of data structures such that they are ideal for the application. For instance, using run-time profiling information, the compiler can opt for a tree-base map instead of a hash-based map; or select an array of bools instead of a array of ints addressed bit-wise.

However, this requires us programmers to let go of some of our control -- if we want to have the memory layout optimized by the compiler, then the programmer can't have control over it. In theory, the resulting application should be slower, since the programmer usually know more about the application than the compiler. However, in practice I believe the application will perform better, because the programmer rarely take advantage of his/her knowledge for improving performance (it takes to much time and effort).

So, if we accept the fact that programmers are lazy (and compilers aren't), and designed a language with this in mind we would see applications with higher performance. Especially considering that programmers should make it work, make it right, make it fast (in that order) applications rarely reach the make it fast phase.

If you would ask me a few years ago, I wouldn't think that performance is such a big issue -- there is enough computation power in an average computer anyway. But considering that everything is turning into a computer application (I can book laundry slots using my remote control for my TV), it is nothing other that waste to not use that computing power properly.

I use the word waste here in an environmental way. For instance, assume an application that runs on several million computers over 5 year had 25% better cache performance -- how much less energy would that consume? Also, assume that those computers are mostly servers located in huge server rooms -- how much less cooling would be needed? Maybe it would be possible to have fewer computers running in the server room, such that the building containing the computers could be smaller...

Seeing how more and more is driven by software, we should look more into how we use the available computing power. We don't want to waste such incredible resource.

Dumbing it down, intelligently

There are problems that seems to be solvable only by throwing more and more code at it -- we call it the brute force method. It works in most situations, but it rarely produces elegant code that survives bit rotting. The brute force method is actually surprisingly common -- how many times haven't developers solved bugs by adding yet another if-statement?

Luckily, there is another way of solving such problems that result in simple and (potentially) elegant code -- here, I call it the dumb-it-down method. The dumb-it-down method achieves simplicity by solving a similar, more general, problem.

While the brute force method result in masses of code that covers every possible corner case of a very specific problem, the dumb-it-down method results in much less, more general, and simpler code. Let's take an example to clarify what I mean.

Let's assume there is a function has_python() that checks if python is installed on a machine. This function is used for making sure that a certain Python script can be executed. How is such function implemented? It needs to check permissions, check paths, check the python version, etc. There is a lot of intelligence needed to be implemented to make sure that the script can be executed, right? This is the brute force method.

Ok, now let's rewrite the problem slightly. Remember that has_python()'s purpose in life is to make sure that a certain python script can be executed. So, we can just as well write a function that executes the python script and return whether or not it succeeded, right? As it turns out, that function is called exec and is built into the standard C library. No need to write a single line of code!

In the above example we rewrote the problem slightly but kept the intention: execute the script only if it can be executed. This is the pattern; this is the idea behind the dumb-it-down method -- look at what the code tries to do on a more general level and find the a simple (or 'dumb' if you want) way of implementing that.

I think the dump-it-down method is an umbrella term covering many design strategies which aim are to produce simple long-living code. I've previously discussed this here.

It seems like software is in a never-ending spiral of complexity: software needs to grow more complex to manage other complex software. Why is an IDE larger than the operating systems from last decade? Are today's IDEs solving more complex problems than the operating systems did? How can the plug-in APIs of said editor be more complex than the C standard library? Aren't the APIs supposed to make it easy to implement plugins?

I've mentioned it before in this blog, but it needs to be repeated. We software developers, need to start looking at our work (and the result of out work) differently. Our skills are not measured by the complexity of the programs we write, but the simplicity of them (assuming equal functionality).

Forgotten treasures I: Look-up tables

Think fast: how would you convert a bool to a string, "TRUE" or "FALSE", in C? Most of us probably answers "with an if-statement", and when asked to show some code doing it end up with something like:

const char* theString;
if (theBool)theString = "TRUE";
elsetheString = "FALSE";

or some similar code using the conditional operator as follows:

const char* theString = (theBool ? "TRUE" : "FALSE");

But there is at least one more way of doing it, which in some cases gives more readable code. I'm speaking of look-up tables. The code above can be expressed by look-up tables like this:

static const char* options[] = { "FALSE", "TRUE" };
const char* theString = options[theBool];

which is much less code compare to the above if-then-else version. It's slightly more code, though, compared to the conditional operator-version. However, I personally find code using the conditional operator hard to read. I know perfectly well how the conditional operator works, but I still need a few more brain cycles to read such code.

On the other hand, I have no problems at all reading code using look-up tables since code like options[theBool] looks very similar to a normal function call. Of course, there are down-sides to using look-up tables; the most important one is that the result is undefined if you index outside the range of the table.

Another way of using arrays like this is when you need to decode a tree structure. Let's say we have three ints which represents a path in a tree.
   Node root = { "Root", layer1Nodes[node1], 0 };
   Node layer1Nodes[] = { { "L1A", layer1ANodes[node1]  } };

During the last year I've gone from primarily developing Java to write C++, C, and assembler. I have to admit, there are a few idioms that I have rediscovered in this transition to C and assemble. Look-up tables are on such treasure.

Of course, there is now real reason why look-up tables can't be used in, e.g., Java, but it seems like the coding traditions in Java discourage such code. Other languages encourage such  code; for instance lists and dicts are very common in Python as a tool for simplifying expressions. It's a bit funny what different communities value in their code.

The problem with code coverage and why static is good

How can  you automatically determine how well a test-case tests some piece of code? What metric should you use? What instrument should you use to measure it? As I'm sure you know, these questions are not easy to answer. Measuring the quality of testing is not a simple thing to do.

Normal code coverage tools are basically worthless for measuring the quality of the test-cases. All they measure is if a line of code has been executed or not; not if the test case verified the result produced by that line. Tools like Jumble are much better, but much harder to use.

However, code coverage is actually a much better  measurement of test-case quality if you language is very static, declarative, and the code hard to extend. Language like that may sound not sound very useful, but they are. They really are. There are circumstances when you really need their static, declarative and precise semantics. When you design hardware, or software for running on resource limited hardware, then you really need precise semantics with regards to the combinatoric depth, stack usage, the position of code in memory, etc. Higher level language, by their very definition, do not make you worry about those "petty details", which is good unless the "petty details" are what makes you application actually function as it should.

High level languages come with a cost, though. The more dynamic a language gets, the less you know what actually will happen when you run the program. Thus, a test-case exercising the code is further from how the code actually will be run. In fact the more dynamic a language gets, the less you can tell what any piece of code written in that language does; it all depends on how it is run. For example, what does this python function do?

def magic(string, filter):
   return [c.swapcase() for c in string if c in filter]

You cannot say for sure, because it all depends on the types of 'string' and 'filter'. Furthermore, when you see the following code:

print magic("Hello, world", "aeiou")

You cannot say for sure what it means either (even though you know the types of the arguments), because 'magic' might have been redefined to do something entirely different.

Consequently, the value of the test-case is much smaller in dynamic languages; thus, more test-cases are needed. This is nothing new, but it is worth considering before saying "I'm so much more productive in Language X than in Language Y". You didn't forget testing did you?

Separating responsibilities using channels

Imagine the following situation. Three developers that are responsible for three separate (but connected and interacting) subsystem discuss which subsystem that should be responsible for a certain feature.

Developer A: I don't care if Subsystem B or C is responsible for producing Information Y; but Subsystem A needs Information Y to support Feature X.

Developer B: Well, Subsystem B shouldn't be responsible for Information Y because Subsystem B's responsibility is Z and only Z!

Developer C: Subsystem C shouldn't provide Subsystem A with information Y, because Subsystem C should never communicate subsystem A directly!

Feels familiar? It sure does for me.

Basically the problem is that the architecture (which say what subsystems that should interact with each other directly) and the responsibilities (of those subsystem), does not allow the some information (needed by one of those subsystem) to flow as needed.

What is the solution here then? Should poor Developer B be forced to make Subsystem B take on responsibilities beyond Z? Or should Subsystem A and Subsystem C be allowed to communicate directly? Non of these two alternatives are ideal, is there another option?

Of course there are! And I'm sure that you have already figured it out: simply let Subsystem B provide a channel that let's other subsystems provide Subsystem A with information. Subsystem B never knows what information is sent over the channel and Subsystem A never know that the information's source actually is some other subsystem than Subsystem B. In other words, no architectural rule should be broken by introducing a channel.

If you have looked into layered systems, such as communication stacks, this is nothing new. The insight (if there is any for you to get here) should be that any  kind of system can provide a channel without that conflicting with it's other responsibilities. For instance, a system that decompresses files can have a channel that allows other systems to attach meta-data of the decompressed file.

Of course, the channel doesn't have to be a channel in the sense of sending messages back and forth. For instance, a channel can be implemented simply by a std::map<std::string, boost::any>.

A problem that might appear is that the channel is misused and unspecified, informal protocols/contracts starts to grow. But that's a problem that isn't connected to channels, but rather any kind of communication (be it messages, method calls, or file formats).