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.

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.