Test the source code, not the assembly

Unit tests are great. Integration tests are great. Regression tests are great. User tests are great. The problem with these kinds of test is that they test the compiled source code -- the assembly -- not the source code itself.

Why is this a problem, you ask? The problem is that the source code, which (should) communicates intention to other programmers is not tested. This aspect of the source code is not tested. It is very hard to test this aspect, though. The only way I know of is Checkstyle (and similar lint tools), and code reviews. The former has the advantage of being possible to automate, the latter has the advantage of being correct (which the former is not :)).

I use correct here in the sense that it actually reflect the opinions of by the target audience -- the programmer. The primary user of source code is the programmer, not the computer. The primary user of the compiled code is the computer (which doesn't have strongs opinions on how structure of the code should by, by the way).

The idea I'm trying to express here is that source code can be functionally perfect in the sense that millions and millions of testcases verify every tiny aspect of the code. Yet the source code will fail miserably on a core review. Testing is not enough if the source code is supposed to live for long.

Is code review the only tool for making sure that source code does not degenerate into a huge ball of spaghetti/mud mixture? Refactoring is often mentioned in discussions like this. However, in my mind this is is a tool for un-mudding the ball into something nicer. It is not a tool for identifying what to refactor.

It kind of sucks, because core review are boring like hell, but what other solution is there to this problem? I would be happy to know of any other than code reviews.

RIP C and LISP

Two very influential profiles in the computer science community and in software engineering has passed away.

On the 12th of October the father of C, Dennis Ritchie passed away; and on the 24th the father of LISP, John McCarthy, passed away. I encourage you to read up on their achievements during their life-time.

Imagine a world without C -- the worlds first really portable language.

Imagine a would without LISP -- the Maxwell's equations of computer science.

std::fstream -- please leave!

During the last half year, there has been several bugs related to C++ file streams, e.g., std::ifstream. Most bugs have been resolved by adding calls to ios::clear to clear the error state of the stream, or similar fixes. Other bugs were fixed by using C FILE instead.

Why, why, why, is file I/O so hard to implement in a reliable way in C++? I haven't done much work with files in C, but the things I've done work well. Same thing with python. Java's file I/O is just a joke (why do I need three classes to read a file?), but at is more reliable than C++.

Think twice before I use std::fstream again. You code might be fine on implementation of the C++ standard library, but will fail on another. Sad.

Dynamic scoping in C++

I've had ideas for dynamic scoping before. There are pros and cons with dynamic scoping, as is explained at the emacs wiki.

Last time I implemented it in Java, this time I'm trying to get something more primitive (compared to the Java implementation) working in C++ (it should be straight-forward to port to C).

The use-case I had in mind when implementing this was how to distribute loggers or hierarchical configurations to every part of an application. In such code is is usually required to pass a Logger or a Configuration around to basically every function. However, with the approach described here, there is no need to pass stuff around like that, instead one uses stack-searching technique.

This little demo demonstrates the idea:

int func1() {
  TaggedInt i1(1);
  printf("i1 = %d\n", findClosestTaggedInt());
}

int func0() {
  printf("i0 = %d\n", findClosestTaggedInt());
  func1();
}

int main() {
  TaggedInt i0(0);
  func0();
}

When run, the following is printed:
i0 = 0
i1 = 1
Ok, what happens here? It's pretty simple. The class TaggedInt is a class that holds two values. A tag and an int. The function findClosestTaggedInt searches backwards through the stack until it finds the tag of a TaggedInt object and returns the corresponding int of that object.

In a real application the int would probably be replaced by something else, like a pointer to a LogConfig object or something similar. Further more, the findClosestTaggedInt would be replaced by findClosestTaggedLogConfig and probably not be used explicitly like in this demo, but rather implicitly in a constructor of some other object such as Logger. For instance:

void func() {

  Logger logger; // findClosestTaggedLogConfig is called by the ctor.

  logger.warning("Something is happening!");

}

int main() {

  LogConfig config(std::cerr); // This is a tagged object.

  func();

}

Now, there is a problem with this approach. Searching through the stack is an expensive operation, and not something you should do often. That implies that findClosetsTaggedXYZ should only be rarely called, or when the program is not in a time-critical phase. However, since findClosestTaggedXYZ is only used when distributing an object throughout the application (not when the object is used) this can usually be done once at application start-up and never again.

To sum up, here's a the rest of the code for running the demo above:
#include <string.h>
#include <assert.h>
#include <inttypes.h>
#include <stdio.h>

static const unsigned TAG_SIZE = 16;
static const char TAG[TAG_SIZE] = "my magic string";

// A tagged int is an magic tag followed by an int. The tag
// *must* be at zero  offset relative to the 'this' pointer.
class TaggedInt {
  char tag[TAG_SIZE + sizeof(void*)];
public:
  int variable;
  TaggedInt(int variable) : variable(variable) {
    // Setup the tag.
    memcpy(tag, TAG, TAG_SIZE);
    TaggedInt* self = this;
    memcpy(&tag[TAG_SIZE], &self, sizeof(self));
  }
};

// Find which direction the stack grows.
int stackDirection() {
  int first;
  int second;
  int diff = intptr_t(&second) - intptr_t(&first);
  return diff > 0 ? 1 : -1;
}

// The maximum number of bytes to search backwards through
// the stack for the  tagged int before giving up.
static const unsigned STACK_SIZE = 1024 * 1024;

// Search backwards through the stack for the first tag.
// Note: this might be possible to optimize by a large factor
// by knowing the  alignment of stack allocated variables.
int findClosestTaggedInt() {
  static const unsigned ALIGMENT = 1;
  int direction = stackDirection();
  char start;
  for (char* ptr = &start; ptr != &start - STACK_SIZE;
       ptr -= direction * ALIGMENT) {
    if (0 == strcmp(TAG, ptr)) {
      TaggedInt* tagged;
      memcpy(&tagged, &ptr[TAG_SIZE], sizeof(tagged));
      return tagged->variable;
    }
  }
  assert(false);
}
With this code you should have a fairly good start for implementing something more useful, such as a distributor of Loggers or Configurations.

One last thing, I would be really interested in hearing from any anyone that figures out how to compute the ALIGMENT constant in findClosestTaggedInt to increase performance while still making sure no tag is missed.

Types are smart, inheritance is plain old code-resue

I've been programming object-oriented languages for at least ten years, yet the paper Inheritance is not subtyping didn't make any sense to me at all the first time I read it. (If you haven't read, I recommend you to do so.) When I started to think about type-checking in my own terms and concepts, and implemented a type-system using those concepts, then I think I got it. I think...

I guess the cause for me not understanding it was that my understanding of types in programming languages was (and still are, but to a lesser degree) very ad-hoc. For instance, in C++ is int a subtype of std::complex<int>. Why isn't it? After all, the set of of non-complex integers is a subset of the set of complex integers, isn't it?

And that's just what type or a variable is -- the set of possible values of that variable. So, why isn't int a subtype of std::complex<int> in C++ then? Well, it's simple: because the type-system doesn't allow it. And why doesn't the type-system allow it? Because subtyping in (most? all?) statically typed OO languages is tied to inheritance. This is the error that crippled the ability to reason about types of so many programmers brains.

The more I read and the more I program, the more I realize that inheritance is just another tool for code-reuse; not so much different from how functions are a tool for code-reuse. It should have been decoupled from the type-system when it was designed though. Instead there should be a separate construct for defining subtype relationship.

But let me get back to what the type of a variable is. If your brain, like mine, has been crippled by C++'s or Java's types-systems, then the phrase "the type of a variable is the set of possible values for that variable" isn't as eye opening as it should be. Consider the following C program:

1  int func(int a) {

2     if (a % 2 == 0) {

3        return a - 2;

4     return a - 1;

5  }

What can we say about the type of a here? The brain-crippled programmer would say something like "it's an int, which it either 16, 32, or 64 bits signed integer, depending on for which the architecture it's compiled." But let's dig deeper...

Let us take the role of a type-system and let's write down as much as we can possible know about a at every line of this program.

1  int func(int a) { // Don't know anything yet.

2     if (a % 2 == 0) { // If true, then a is even.

3        return a - 2; // a is even; a - 2 is even

4     return a - 1; // a is odd; a - 1 is even.

5  }

There are type-system that does precisely this; the type of a variable may change each time the variable is used. The reason for this is that every time a variable is used, there is (potentially) more information about the value of the variable. Thus, following the definition the type of a variable is the set of possible values for that variable, the type of a variable changes as the type-system derives different set of possible values at different parts of the program. For example, at line 1 the type of a is int, and at line 3 the type of a is even int.

Why did I just discuss that? Because I wanted to illustrate how distant the concept subtype and inheritance is. It is unfortunate that these two concepts are blended together in mainstream languages.

What makes the problem even worse is that inheritance is not a guarantee for proper subtyping, as the circle vs. ellipse problem illustrates.

(Please note that I'm not a type-system guy; I have no formal training in this area. This is just my take at the inheritance vs. subtyping problem.)

What OOP's jargons and complexities?

I was introduced to functional programming in an introductory programming course at the university. I had experience with imperative languages and a bit of OO from before. My immediate impression of the functional programming style was simply "this is really peculiar".

However, after a few labs in Scheme, I was stuck. The ideas was clean yet powerful. Everything made sense.

The reason I write about is because I just read Programing: What are OOP's Jargons and Complexities and I recalled those introductory lectures into functional programming. It's a great read if you are interested in how languages and programming styles relate to each other.

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.