Part of a series of posts explaining programming for the lay-person.
This is part of a series of posts; see the introduction to this series. This entry overviews various kinds of loops, which are control constructs.
Loops are one of the most important, simplest, and most often misunderstood of common control constructs. The phrase “one of the superlative” implies there are “more superlative” things out there without specifying how many. It thus has no denotative meaning, only connotative. Purely denotative and purely connotative phrases are worth collecting. They change a single action into a repeated action. I will look at just two examples in this post: “eat all the apples” and “deal 7 cards to each player.”
The first thing to note about my two examples is they don’t look, immediately, like loops. I didn’t say “repeat” or “as long as” or “while”. There are probably ways to eat all the apples without repeating anything. A technical interpretation of English would say that “eat all the apples” means there is no loop: we take the apples as a collective and eat that collective as an action. “Eat each apple” would be the implied loop. But the distinction between “each” and “all” seems to be pretty widely ignored, so we’ll skip that for now. But the implication in phrases like “eat all the apples” and “deal each player 7 cards” is that something is going to be repeated. And there are many ways to write that repetition.
Consider the following three ways to “eat all the apples”:
This first one is pretty simple. I look to see if there are apples; if there are, I eat one of them and then go back to look again. In most programming languages this is called a while loop: while something is true, do something. Note that it repeats not only eating, but also checking, which, for some tests (like “as long as p is not prime, increment p”) can be quite expensive.
This second example avoids checking for apples every time by counting them and then just repeating that many times. Of course, if someone adds or removes an apple while you are eating you might have a problem. For some reasonI know the reason, but it isn’t particularly interesting., this type of loop is usually called a for loop, but that term is not as fixed as is “while loop” and sometimes is used to mean the next example instead. I do occasionally hear these called “counter loops.”
This third example is usually called an iterator loop or a foreach loop. It is interesting because it doesn’t actually state how to go about looping through the apples, only that the apples should be considered one at a time. Under the hood it might be a while loop, or a for loop, or something else altogether.
More and more computer languages are moving toward this kind of “high-level” construct that describes the outcome instead of the process. Doing so means you, as a programmer, can write less code and they, as the language designers, can do whatever they want to get the work done: making use of multiple processors at once, going in a strange order, etc. The downside is that you can’t assume any particular behavior unless you dig into the details of how the language is implemented. Taking away an apple during the loop might break it, or it might not, and it might change from one run to another.
There are other types of loops. For example, a construct called the “do-while loop” was once quite popular, though it has fallen out of favor. “C-style for loops” are still fairly common, being a strange way to write a while loop that makes it easy to make them act like a counter loop. Other techniques only work for particular kinds of outputs, like “list comprehension”, “filter”, and “reduce”. In the end, though, the idea is always the same: repeat some statement a lot of times.
The phrase “deal 7 cards to each player” is interesting because it actually contains two loops, not just one. We need to loop over all the players, and we need to do something seven times. Also, one loop needs to be nested or happen one inside the other, so that for each time through one loop we do the entire other loop.
There are two basic ways to organize this, though the names of the two aren’t related to eachother.
It might be worth a little time thinking about these nested loops. The end result is the same: each player gets seven cards. The process is different: there is a point in the first one where some players have seven cards and others have none. If the deck of cards was completely shuffled, would it matter which one you used? What about if it was sorted in order before the dealing began?
One interesting note is that one ordering is sometimes faster than the other. This is because switching between players takes a lot more effort than switching from giving someone their third card to giving them their fourth card. Because of the way computer memory works, Computer memory is so complicated these days that the only reliable way to find out if a different loop structure is faster is to write that loop structure and try it out. Even that has a lot of variability depending on what else is running, and how exactly you computer is set up. it can sometimes be faster still to do something like the following rather convoluted-looking process:
These “optimized” loops can get a lot uglier, too….
As a parting exercise, think about ways to write loops that achieve the goal “deal each player 7 cards of each color”.
Looking for comments…