Computer science is not physics

I've read Existential Type for a while and gotten to the post Languages and Machines, which discusses models of computation. It all makes a lot of sense: there are different ways of modelling computation and they are good for different things, the only catch is that all but one models a machine. A machine with computational units, storage, and what not.

A programming language is not used for manipulating registers and mutating memory cells, it's used for expressing thoughts and ideas. Thoughts and ideas does not live in the physical world (a least that's what I've heard) so why should we rely on a language (read: C/C++/Java/etc) that inherently is bound to a (more or less) physical machine?

No one questions that the field of maths is unrelated to the physical world we live in, right? Maths would exists with or without humans discovering mathematical truths and proofs. That's because maths uses some axiomatic system (that just happens to be very useful in the real world). However, I'd hope that no one in their right mind would argue that maths is about the physical realisations of the axioms, e.g., that 1 apple + 2 apples is 3 apples. Maths is not about apples -- apples just happen to fit in the axiomatic system.

Dijkstra famously said:

Computer science is no more about computers than astronomy is about telescopes.

I guess an equivalent statement about maths would be maths is no more about numbers than astronomy is about telescopes... Let me now rephrase the previous paragraph to emphasis my point.

No one questions that the field of computer science is unrelated to the physical world we live in, right? Computer science would exists with or without humans discovering computational truths and proofs. That's because computer science uses some computational model (that just happens to be very useful in the real world). However, I'd hope that no one in their right mind would argue that computer science is about the physical realisations of the models, e.g., the NAND gate. Computer science is not about NAND gates -- NAND gates just happen to fit in the computational model.

So why not call it computation science, or automated maths? No one would question the above paragraph if  I'd written automated maths instead of computer science.

Rob Pike: Less is exponentially more

I just read Rob Pike on the history of Go. I find it interesting that Go fails to attract C++ programmers, but instead attract Ruby and Python programmers. What does it take to make a C++ programmer switch to a new language? Maybe some clues can be found at the Socio-PLT.

Level up your automatic test suit

Having an automatic test suit has been mainstream for quite some time by know -- we know why and why we should do it. I personally had the luck of doing it at every workplace I ever been at. But I avent been fortunate to discover the correct way of runnin them until just a few days ago.

The command watch is a standard Linux command that repeatingly executes a command and prints the result in full screen in the terminal. I've used this lately to avoid "edit, alt-tab, up-arrow, enter, alt-tab, edit" cycles when devloping a python application, that is, to avoid having to switch to the consol I'm using to test the code and run run it.

It sounds like a small thing, but I recomend you try it. It suprisingly useful to see the result of the current code automatically when I save it.

 This is similar to Mim,  the build system I created some time ago. Mim could actually be extended such that it could run a script everytime the contents of a set of files (e.g., the depdendencies) changed. But since Mim isn't installed on every Linux machine, but watch is, watch has to do. :)

Java initialization chaos

I've recently started using Java again after going from C++ to Java to C++ and now Java again. What bums me out the most with Java is how it pretty surface hides a lot of chaos. Don't get me wrong, it's good that you don't have to see the chaos (too often), but it's terrible that the chaos is there at all. Java's static initialization is particular "interesting" topic.

What is a and b in the following code:

class A { public static int a = B.b; }

class B { public static int b = A.a; }

I know its a contrived example, but non-obvious variants of this code pops up every now and then and brings havok to the dependency graph.

So, what do happen to a and b in the code above? How does the JVM resolve the cyclic dependency? It does it by initializing a and b to zero. In fact, all (static) fields are first initialized to zero (or null if the fields holds a reference type) when the JVM first sees the field during class loading. Then when the entire class is loaded, it's class initializer is called where the fields are initialized to the values written in the source code, e.g., 10 in the code below:

class C { public static int c = 10; }

In other words, the code for C is equivalent to:

class C {

  public static int c = 0;

  static { c = 10; }

}

Which you can easily see by running javap on the C's .class-file.

Now, what I've been asking my self is why it's done like this? Why is the fields initialized to zero (or null) and later assigned to their proper value (10 in the case of C.c). It would be extremely helpful to have the fields being tagged as uninitialized before a  proper value is assigned to them. That would not require tonnes of extra logic in the JVM, and would capture circular dependencies upon startup of the application.

The JVM is nice and all, but it's not perfect. But then again, no one is arguing it is, right?

Happy four years

Amazing, four years have passed since the first post. Since them I've been writing about all crazy things: getting lisp-y things into Java, reflection-based code generation, abstracting protocols, smarter compilers, optimization detection, dwelving into macros safety, telling stories from my past, complaining on enterprise solutions, creating a new build system, fueling the inheritance-vs-subtyping fire, and arguing that you must know what you are doing to do it right.

It's fun to go back trough the archive of post. For me personally it's a diary of my development as a writer of posts as well as software. The posts are also an indicator of where my interests happen to be at that time -- as they tend to move over time. :)

Move constructor without C++11 and overhead

A few days ago I saw Bjarne Stroustrup's keynote from the GoingNative conference earlier this month. In his talk he mentioned move constructors and that they open the possibilities for improved performance. What hit me though is that he mentioned that he had implemented move constructors for a decade before they appeared in C++11 and that he did it by "setting a bit" in the object to be moved before it was moved. I interpret him as being required to do:

MyVector foo() {

  MyVector m(1024, 1204);

  // Use vector.

  m.move(); // Set bit. Next copy will actual be a move.

  return m;

}

Now, I haven't seen his code so I might be wrong, but as I understand it it involves unnecessary run-time state and CPU cycles (the latter will be optimized away though, but not the former).

As I see it it should be possible to do this using the type system instead of run-time state. The idea is to let MyVector::move return a special type that can be converted to a MyVector object, but doing so using move semantics -- not copy semantics. It is used as follows:

MyVector::Move foo() {

  MyVector m(1024, 1204);

  // Use vector.

  return m.move();

}

Here, the result of m.move() is a MyVector::Move object which just holds the state of m needed to reconstruct a MyVector object. Also, MyVector has a constructor that takes MyVector::Move as argument -- this constructor is the move constructor. Here is a complete program showing how it's done. In this program I renamed the move function to operator Move such that the conversion to MyVector::Move is implicit and there is thus no need to call move.

class MyVector {
  int* values;
  MyVector(MyVector const&); // Don't allow copy. 
public:
  // Constructor allocates data on heap.
  MyVector(int numValues) : values(new int[numValues]) { }
 
  // Destructor deletes.
  ~MyVector() { delete[] values; }
  
  // Everything is public here for simplicity.
  struct Move {
    int* values;
    Move(int* values) : values(values) { }
    operator MyVector() {
      return MyVector(*values);
    }
  };
  
  // Move constructor.
  MyVector(Move const& rhs) : values(rhs.values) {
  }

  // This function was called 'move' in the earlier example.
  operator Move() {
    Move m(this->values);
    this->values = 0;
    return m;
  }

  // Access the contents of the vector.
  int& operator[](int idx) {
    return values[idx];
  }
};
 
MyVector::Move get() {
  MyVector h(1024);
  h[10] = 20;
  return h;
}

int main() {
  MyVector h(get());
  return h[10];
}
I must say that I'm surprised that this pattern hasn't popped up earlier for me. Granted, it has it's share of noise, but it does what it promises: moves without the unnecessary new and delete[].

Bridging templates and runtime parameters

I often write template classes in C++ for run-time efficiency. By providing the parameters of a class through template, the compiler can do a better job since it can do constant propagation. However, a problem with using templates like this is that is not obvious to reuse the template code when the parameters is only known at run-time. In this post I'll explain one way of writing template code such that it can be used with run-time parameters as well as compile-time parameters.

The idea is pretty simple: create a template class where the declaration of the (compile-time or run-time) parameters are extracted into a separate class.

The following two classes will be used to illustrate how to it.

template<int I0, int I1> struct CT {

  int func() { return I0 + I1; }

};

struct RT {

   int i0, i1;

   RT(int i0, int i1) : i0(i0), i1(i1) { }

   int func() { return i0 + i1; }

};

First, let's extract the parameters into a separate class to isolate the state of the class from the behaviour.

template<int P0, int P1> struct CTParams {

  static const int i0 = P0;

  static const int i1 = P1;

};

template<typename PARAMS> struct CT {

  int func() { return PARAMS::i0 + PARAMS::i1; }

};

struct RTParams {

   int i0, i1;

   RTParams(int i0, int i1) : i0(i0), i1(i1) { }

};

struct RT {

   RTParams params;

   RT(RTParams const& params) : params(params) { }

   int func() { return params.i0 + params.i1; }

};


Second, to make  the body of CT::func and RT::func look the same we rewrite the code of CT into:

template<typename PARAMS>

struct CT {

  PARAMS params; 

  int func() { return params.i0 + params.i1; }

};

Ok, we're getting closer. Now, the only difference between CT and RT is essentially that RT has a constructor and that CT is a template. We can create a new class CTRT which has both these features and thus replaces CT and RT:

template<typename PARAMS>

struct CTRT {

  PARAMS params;

  CTRT(PARAMS const& params = PARAMS()) : params(params) { }

  int func() { return params.i0 + params.i1; }

};

And we're done! The class CTRT can be used in two ways -- with run-time parameters or compile-time parameters, as follows:

void f() {

  // Look here! Compile-time parameters!

  CTRT<CTParams<10, 20> > ct;

  ct.func();

  // Look here! Run-time parameters! Omg!

  CTRT<RTParams> rt(RTParams(10, 20));

  rt.func();

}

Pretty straight-forward, right? There are a few downsides to this solution. The first is that there is a small overhead in memory usage of CTRT<CTParams<...>> compared to the original CT class. Luckily, this can easily be solved by using private inheritance (and the empty base class optimization).

Second, the implementation of CTRT<...> is much more complicated than the original RT class. However, this is a small price to pay compared to having multiple implementations.

Third, and most important, since CTRT is a template it must (usually) be implemented entirely in the header file, thus, increasing compilation times and potentially cause code bloat.