Sunday, March 18, 2012

The Evolution of the FOR loop

The most widely and commercially used languages today are largely based on the imperative and structured programming paradigms and many have a direct and strong roots in the C language of the early seventies.

Even though there seems to have been little fundamental change in main stream programming languages over the  last 40 years, there have been subtle shifts in usage patterns, even for things as simple and fundamentally low-level as doing some things repeatedly or in a loop.

As a perfectly and randomly useless example to illustrate the evolution of looping, we are creating a list of squared numbers from the positive members of an input list.

In C or any similar imperative language of its time, the most basic way to do something like this would be something like:

out_size = 0;
for (i = 0; i < in_size; i++) {
  if (a[i] > 0) {
    b[out_size++] = a[i] * a[i];
  }
}

Languages like C++ and Java, which includes a standard library of higher level collection data types, this basic pattern of an indexing counting loop is typically replaced by some sort of iteration support of the input collection.

for (std::vector<int>::iterator it = a.begin(); it != a.end(); ++it) {
  if (*it > 0) {
    b.push_back(*it * *it);
  }
}

Which is still basically the same counting loop disguised as type-safe pointer arithmetic. Java 5 offers a slightly more elegant syntax for iteration of types supporting the Iterable interface and the new for-each variant of the for loop:


for (Integer num : a) {
  if (num > 0) {
    b.add(num * num);
  }
}

In Python, this idiom would read like:

b = []
for num in a:
  if num > 0:
    b.append(num * num)

However for usage patterns like this, which are essentially transforming an input iterable into an output, some languages also support a more functionally inspired idiom. In Python originally using the map and filter functions:

b = map(lambda x: x * x, filter(lambda x: x > 0, a))

And since the introduction of generator expressions and list comprehensions as:

b = (num * num for num in a if num > 0)

The advantage of the functional model is that in its purest forms, it allows for deferred evaluation, has generally no side effects, describes more specifically the nature of the operation than would the use of general flow-control structures and thus could more easily be parallelized by a smart runtime.

A more functional style is also possible in Java using some 3rd party libraries as Iterables from the Guava library. However without support for some sort of compact lambda function definition in current Java, this would result in significantly more complex and probably less readable code than the currently most standard variant using the for-each iteration. Until then, even the authors of the Guava library recommend to not use a functional idiom for most cases...