getting back to the fun in computer programming

First, a few quotes:

A computational process is indeed much like a sorcerer’s idea of a spirit. It cannot be seen or touched. It is not composed of matter at all. However, it is very real. It can perform intellectual work. It can answer questions. It can affect the world by disbursing money at a bank or by controlling a robot arm in a factory. The programs we use to conjure processes are like a sorcerer’s spells. They are carefully composed from symbolic expressions in arcane and esoteric programming languages that prescribe the tasks we want our processes to perform.

Fortunately, learning to program is considerably less dangerous than learning sorcery, because the spirits we deal with are conveniently contained in a secure way. Real-world programming, however, requires care, expertise, and wisdom. A small bug in a computer-aided design program, for example, can lead to the catastrophic collapse of an airplane or a dam or the self-destruction of an industrial robot.

If Lisp is not a mainstream language, why are we using it as the framework for our discussion of programming? Because the language possesses unique features that make it an excellent medium for studying important programming constructs and data structures and for relating them to the linguistic features that support them. The most significant of these features is the fact that Lisp descriptions of processes, called procedures, can themselves be represented and manipulated as Lisp data. The importance of this is that there are powerful program-design techniques that rely on the ability to blur the traditional distinction between “passive” data and “active” processes. As we shall discover, Lisp’s flexibility in handling procedures as data makes it one of the most convenient languages in existence for exploring these techniques.

Above and beyond these considerations, programming in Lisp is great fun.

Those of us who already know what I am talking about, wish me luck! Those of us who don’t, here’s a four-letter word for you: SICP.

on the use of pre- and post- increment iterators, and erasing elements from an STL map

After spending a tense 2-3 hours trying to track down a segmentation fault, here’s what I found. The explanation is subtle and obscure enough to be documented in every text book that ever claims to teach “proper” C/C++ programming practices! Maybe they already do that, and I didn’t happen to read the right books. I do admit to learning most of my programming skills on the fly from existing good code.

Consider the following function calls:

  1. f(++i);
  2. f(i++);

Common understanding of these calls translates them to the following:

  1. i += 1; f(i);
  2. f(i); i += 1;

But that is not so! The post-increment operator used in the second call behaves in a more complicated way! What it really does, is to increment i after the arguments to f() are created, but before the function is called. Thus the correct translation of the second function call is:

temp = i; i += 1; f(temp);

This doesn’t look too different, but the subtlety involved would have saved me those couple of hours wasted in debugging. It happened when I was iterating over an STL map and wanted to delete some members, as follows, in pseudo-code:


for (map::iterator i = map.begin(); i != map.end(); ++i) {
  if (test(i))
    erase(i);
}

The problem is that map.erase() invalidates the iterator passed to it. So the ++i at the start of the next iteration no longer points to a valid iterator. The correct way to do this is:


for (map::iterator i = map.begin(); i != map.end();) {
  if (test(i))
    erase(i++);
  else
    ++i;
}

Note the use of the pre-increment operator in the else part, since that saves the unnecesary creation of a temp variable. It is definitely a good practice to always use the pre-increment operator unless you are sure you need post-increment.

The story doesn’t end here. What if f() expected a reference as its argument? It does receive a temporary copy and any changes the function makes will be lost. But the fact is that it can’t make those changes. It is important to note that the “translation” involving the variable temp is just a vague interpretation. That pseudo-variable temp is actually an rvalue and cannot be assigned this way … it’s just a way of showing something that the compiler does internally. The post-increment operator returns an rvalue and that can only be passed as a const reference to the function. The function being called has to be declared accordingly!

These facts were learnt from an old discussion that I chanced upon while searching.