Some notes on for loops

Experts can learn a lot by looking at the basics.

New Blogpost

Don't let Alloy facts make your specs a fiction, about formal methods practices (and a lot of Alloy). Patreon link here.

Some notes on for loops

I sometimes like to sharpen the axe by looking at a basic programming concept and seeing what I can pull out. In this case, for loops.

There are two basic forms of for loops:

for(i = 0; i < 10; i++)

for val in ["a", "b", "c"]:

The second is usually called a foreach loop, and I'll call the former "forstep", after the ALGOL-60 construct. Almost all languages have one of the two, some have both. While forstep loops show up early, foreach loops only appear in PLs ~20 years later.

Looking at this, here's some things I see:

Construct reduction

Given a foreach loop, I can syntactically translate it into a forstep loop:

for val in arr:
    # ...

-->

for(i = 0; i < arr.len; i++) {
    val = arr[i];
    // ...
}

There's a lot of terms we use to express this property. We can say that foreach is homomorphic or reducible to forstep, or that foreach can be constructed out of forstep, or others I can't think of rn.

If we could also construct forstep from foreach, we could say the two are equivalent or isomorphic. In theory we can do this if we had a range operator:

for(i = 0; i < 10; i += 2) 

--> 

for i in range(0, 10, step=2);

Most forstep implementations, though, can do things like modify the iterator in the middle of the loop:

for(i = 0; i < 10; i++) {
    // stuff
    if(cond) i = 0;
    // stuff
}

You can't convert this to a foreach loop: it's an "irreducible" feature.

Most people consider modifying the index bad practice, though. 99% of the use cases of forstep loops are constructible with foreach loops, so the two are morally equivalent. I'll treat them as roughly interchangeable going forward.

Primitives and Expressivity

For loops are reducible to while loops:

for(i = 0; i < 10; i += 1) 

-->

i = 0;
while i < 10 {
  // ...
  i++;
}

But while loops are not reducible to for loops:

while(user_cmd != "quit")

-->

???

Again, lots of terms to cover this: while loops are more "primitive", more "powerful", more "low-level", more "expressive", etc. If you have while loops, you don't need for loops, and if you have goto, you don't need either.

But you shouldn't use a goto when a while loop works or a while loop where a for loop works. This is a generalization of the rule of least power (RLP): given a problem, use the tool that is most specific to the problem. If you can iterate through a list with a foreach loop, don't use a while instead!

There's two reasons for this. One is that it's more communicative to other programmers. If they see a foreach loop, they know it's going to be used for some kind of iteration, while that's not clear with the while loop. Two is the capability/tractability tradeoff: the more limited a construct is, the easier it is to understand and work with. A foreach loop can do less than a while loop, but it's much easier to guarantee that it processes each item only once.

Programming languages evolve to replace the all-powerful "low-level" constructs with more limited constructs that reduce to the low-level ones. It's why you get things like interfaces over inheritance.

The corollary of this is that if you use a powerful construct, it should be because the limited one can't do what you want. Don't force an infinite for-loop!

Extensions to for loops

For loops reduce to while loops, while loops reduce to goto, everything reduces to goto. So there are some kinds of looping goto can do that for and while cannot.

They get a little closer to feature-parity by adding flow-control inside the loop: continue for advancing the loop early, break for terminating it. I didn't look into when or how these were added, but I'd guess they come from looking at what goto can do that loops could not, and adding features as needed.

"Imperative programming" is just for loops

I think one of the most basic functions of a programming language is to iterate through an array. So much so that you can distinguish different programming paradigms by how they iterate.

• Imperative programming: for loops
• OOP: a foreach method on iterable objects[^python]
• Functional programming: recursion, reduce (we'll talk about this later)
• Logic programming: I'm less familiar with this, but I think it's recursion + pattern matching (which ML and Haskell adopted)
• Array programming: all operations take arrays by default.

I think this explains why arrays are universal while dictionaries are relatively new: there's no obvious basic operation that covers what you do with dicts to the degree that for covers what arrays do.

(Question: do list comprehensions lead to a new paradigm? How do you describe "iteration" in spreadsheet languages?)

Functional replacements

When people talk about replacements for foreach loops in FP, they usually bring up map and filter. But these are not equivalent. Rather map and filter are "preferred" to loops because they are more limited. It's another instance of RLP.

As far as I can tell, reduce is equivalent to foreach. Morally, anyway. This is interesting because reduce is considered part of the "big three" (along with map and filter), but it's also the one that's the "odd one out". It's the hardest for people to understand, and Haskell even has three versions of it. Is it confusing because it's so powerful?

Map and filter are composable in a way that foreach loops are not, but they're also weirdly less "composable" in one very specific way? Consider something of the form

map f (filter p arr))

-->

out = []
for x in arr:
  if p(x):
    out.append(f(x))

The map/filter iterates over the list twice, while the foreach loop iterates only once. I know Haskell can fuse maps together as an optimization but I don't think you safely fuse arbitrary map/filters? I dunno.

You can fuse map and filter with a reduce:

reduce ((out, x) => 
        if p(x) 
        then out ++ f(x)
        else out
       ), [], arr

This gets really awkward though.

I wonder if "reduce is equivalent to for loops" plus "reduce is awkward for fusion" somehow inspired clojure transducers.

I'll be writing this forever

Things I could have looked at in more detail but ran out of time and energy:

• "Iterators" as a general concept.
• Loop invariants and variants. This is really relevant to formal methods in particular.
• Specific implementations of for loops in languages. ALGOL's loop expression-lists, Python's for else, Raku's phasers, javascript's for in/for of distinction, Ada and Chapel loop parallelization constructs... If I keep going I'll get something as long as this.

Following any of those leads would get us to different insights, as opposed to main thing that ended up catching my interest with these notes, which is how the rule of least power applies to language constructs. I should probably write a blog post about it!

Anyway I think this kind of exercise, looking at something everybody takes for granted and try to learn things from it, is really valuable for understanding software better. I don't know how interesting it is to read about, though. Lemme know if you think you'd like to see this for other stuff, or just share the essays that are downstream of the practice (like writing about RLP).

Podcast appearance: are we engineers?

I was on a podcast, talking about the crossover project and what software engineers can learn from traditional engineering. Check it out here!

If you're reading this on the web, you can subscribe here. Updates are once a week. My main website is here.

My new book, Logic for Programmers, is now in early access! Get it here.