Kick Your Manual Iteration Habit

When John Backus asked in 1977 in his ACM Turing Award Lecture “Can Programming Be Liberated from the von Neumann Style?” he surely had higher hopes than you still writing for(i = 0; i < n; i++) 40 years later.

Von Neumann programming languages use variables to imitate the computer's storage cells; control statements elaborate its jump and test instructions; and assignment statements imitate its fetching, storing, and arithmetic. The assignment statement is the von Neumann bottle-neck of programming languages and keeps us thinking in word-at-a-time terms in much the same way the computer’s bottleneck does.

By the year 2017, major programming languages have already assimilated the most pragmatic ideas from functional programming. I’m here to persuade you that using higher order functions for processing collections of data, can often make your intent much clearer than manual iteration.

We’re long overdue to move on from describing how to perform the computation as a side effect of incrementing a counter in a loop, or by indexing into dictionary from the set of keys. This imperative style requires the human reader of your code to simulate the computer’s execution in their mind. That is a bad thing! Instead move up one rung on the ladder of abstraction and describe what is your computation doing in terms of functional composition: filtering, transforming and reducing the input stream.

In most cases that I have encountered, the fact that data is stored in an array or list is an accident of convenience. Data stored in there are not truly ordered. Array is usually just the collection that is easiest to type because of syntax sugar built into all languages. It is better to think of collections generally as containers that hold some elements. When you are processing them, start thinking in sets of elements matching a given criteria — that’s filter application. Need to compute some derived values for each element? That transformation is called mapping. Need some aggregate value from the whole set? That is reduction or folding. Learn these concepts and use them to more clearly express your intent.

When you do your computation as a side-effect of incrementing indexes, understanding it requires you to perform all commands in your head, step-by-step. When you declaratively express your intent with functional composition, there is less space for bugs to hide.

Let’s take a look at example from test driver in Swift Benchmark suite:

What is going on there? You can simulate the execution in your head…

But there is some tricky and probably unintended interaction between onlyPrecommit and filters hiding in there. The onlyPrecommit is true by default, but when the test driver gets invoked with --run-all option it is set to false. The default setting conveniently skips over performance tests that are not run before merging commits from PRs into master branch. Filters are populated from test driver’s positional command line arguments and are used when you want to manually invoke just the specified benchmarks.

The catch is that you can not manually invoke tests that are not part of the pre-commit group — unless you specify the --run-all option. Hardly an intended design choice…

If we refactored the method in functional style, we could arrive at this nicely declarative code:

We convert the dictionaries into 3 arrays of tuples, sort them by name and join them into single array. Then we create a set of tests to run based on the provided options. Finally we create an array of Tests by assigning them ordinal number. To figure out the value for run parameter we check the test name and ordinal against the set of tests to run.

Notice how the logic that sets the run parameter is expressed without being negative (in contrast to the original code), making it easier to understand.

You can use same style in all languages that support higher level functions. To move our craft of programming forward, we need to shed old habits that hold us back and learn from different programming cultures. Functional programming is truly beautiful if you maintain open mind and pragmatically pick up the parts that make sense to use in your language without getting dogmatic about mathematical purity.

I apologize for the click-bait title, “Curb Your Manual Iteration Impulse” would probably be more like it. There is still place where for loop and arrays are the right tools for the job. Just don’t grab them automatically — let it be a conscious choice.

My thanks to Andyy Hope, Rob Napier and Chris Eidhof, for their help with my first article!

🖖

…and now watch the excellent Bret Victor: The Future of Programming