Once Upon an Algorithm Page 20

  Staff notation is more visual than a typical textual language, yet a sentence (that is, music piece) is still a linear sequence of note symbols that can be adapted by changing their position and appearance. This principle forms the basis for many notations that are not traditional textual languages. For example, in the universal graphical language Bliss, a sentence consists of sequences of words, which are symbols that can be composed out of simpler symbols. This is similar to part of Egyptian hieroglyphs, in which symbols can be combined in different ways, depending on their size and the intent of what is being expressed. Bliss and hieroglyphs are general languages, intended to express arbitrary thoughts. In contrast, the staff notation is targeted at a narrow domain and is thus much simpler. An example of a special-purpose notation is chemical formulas that describe the composition of molecules out of atoms (for example, the formula H2O, for water, says that each water molecule consists of one oxygen and two hydrogen atoms).

  The previous examples are still mostly linear notations, that is, a sentence in these languages is a sequence of symbols. Visual languages can be more expressive if they employ a two-dimensional layout. For example, chemical formulas only represent the proportions of atoms that constitute a molecule and ignore the spatial arrangement of the atoms. In contrast, structural formulas provide a description of the geometric arrangement of atoms. Similarly, Feynman diagrams are a two-dimensional language, used in physics to describe the behavior of subatomic particles.

  All of these languages employ a static one- or two-dimensional representation, which means one can take a picture of a sentence and send it to somebody else, who can then interpret it. Other languages transcend this snapshot limitation and employ a temporal dimension as well. For example, gestures are a form of language. Movements of body parts cannot be captured well by a single picture. To define a language of body movements one typically needs videos or sequences of pictures. In user interfaces for computers, tablets, and cell phones, hand movements such as swiping or pinching are interpreted as actions to be performed. In addition to gestures, there are also notations for describing dance, for example, Labanotation. A sentence in that language is an algorithm to be executed by a dancer, which produces a dance as a computation. Origami instructions are a similar kind of language for describing algorithms to fold paper objects. Language is not even restricted to humans. For example, in the series of books about the adventures of Doctor Dolittle, animals communicate by movements of noses, ears, and tails. But even outside of fiction we find, for example, the waggle dance of bees to communicate the location of food sources.

  The meaning of language is defined by rules that translate the abstract syntax of a sentence into values of a semantic domain. Communication can be successful only if the communicating partners agree on those rules. Lewis Carroll’s books Alice’s Adventures in Wonderland and Through the Looking-Glass illustrate what happens if the rules are violated or interpreted differently by the communicating partners.

  Control Structures and Loops

  Groundhog Day

  Force of Habit

  Back at the office, your first task is to send out several letters. Without thinking about it, you fold each letter twice horizontally to reduce its height to about one-third and then put it into an envelope. This works perfectly every time, since the paper and the envelope you are using have a fixed size, and you figured out long ago that this particular folding scheme makes the letter fit into the envelope.

  The folding process is a computation described by an algorithm—a basic example of origami. Despite its simplicity, the paper-folding algorithm illustrates a number of points about languages.

  The first is that the algorithm can be described in two slightly different ways. If fold means to fold a piece of paper a specific distance from the top (for example, one-third of the total paper length), then we could say either “fold and fold” or “fold twice.” It may not seem like a big difference, but these are two fundamentally different descriptions of a repeated action. The first lists an action to be repeated explicitly as many times as needed, whereas the second merely says how often an action is to be repeated. The difference becomes clearer when you have to send a larger sheet of paper that needs additional folding steps. For example, for folding three times, the two approaches would read “fold and fold and fold” and “fold three times,” respectively. Next, envision the case for 500 or more repetitions, and you can see which approach remains practical.

  The first description is a sequential composition of individual steps, whereas the second is a loop. Both are examples of control structures, which are components of an algorithm that don’t do any actual algorithmic work but rather organize the work of other steps. This is similar to workers and managers in a factory. Managers don’t manufacture anything directly but coordinate the actions of the workers who do. Control structures are essential components of any language for describing algorithms, and loops (or recursion) in particular are employed in most nontrivial algorithms.

  There is actually a third algorithm for folding a piece of paper, which simply says “fold until paper fits.” This algorithm also employs a loop control structure, but this loop is different from the previous one in an important way. It does not explicitly say how many times an action should be repeated, but instead defines a condition that must be fulfilled for the repetition to end. This algorithm is actually more general than the previous two, since it works for paper of arbitrary size, and thus it solves a more general problem. It would be impossible to express this algorithm without a loop (or recursion). In contrast, a loop with a fixed number of repetitions can always be rewritten as a sequence of that many steps.

  Assume you have to send not only a single letter but a whole bunch of documents. Whenever you have more than five sheets of paper, instead of folding them all and stuffing them into a small envelope, you use a larger envelop into which you can place the stack of papers directly without folding. Making this decision, to fold or not to fold, is an example of another control structure, the conditional, which executes one of two possible actions depending on a condition. In this case the condition is that the number of pages is five or less, in which case you fold the paper and use the small envelope. Otherwise, you don’t fold the paper and use the large envelope.

  A condition is also needed for determining when to end the repetition of a loop. The condition to end the loop “fold three times” is expressed with a counter having reached a particular value, namely, 3. In contrast, the condition of the loop “fold until paper fits” tests a property of the paper that is transformed by the actions in the loop. The latter kind of condition is more powerful, as evidenced by the fact that it expresses a more general algorithm. But with this increased expressiveness also comes a cost. While the counter-based loop can easily be shown to terminate (since the counter does not depend on what the actions in the loop do), this is not so obvious for the more general kind of loop, and we cannot be certain whether an algorithm using this kind of loop will ever stop (see chapter 11).

  Much of what we do is repetitive and can often be described by loops. Sometimes whole days seem repetitive. This view is taken to the extreme in the movie Groundhog Day, which guides the exploration of loops and other control structures in chapters 10 and 11.

  10

  Weather, Rinse, Repeat

  Any algorithm is given in some language, whose semantics determine the computation represented by the algorithm. We have seen that different languages can have different semantics and can be targeted for different computers. For example, an algorithm expressed in a programming language is executed on an electronic computer and typically denotes the computation of data. On the other hand, an algorithm in the language of music notation is executed by a musician and denotes sounds. Despite these differences, most nontrivial languages share an intriguing property, namely, that they consist of two kinds of instructions: (1) operations that have a direct effect, and (2) control structures for organizing the order, application, a
nd repetition of operations.

  Control structures not only play a crucial role in formulating algorithms, but also determine the expressiveness of languages. This means that the definition of control structures and the decision as to which control structures to include in a language determine which algorithms can be expressed in a language and thus which problems can be solved using it.

  One such control structure is the so-called loop, which allows the description of repetitions. We have seen many examples of loops already, as in Hansel and Gretel’s way-finding algorithm that instructs them to repeatedly find the next unvisited pebble, or in selection sort, which works by repeatedly finding the smallest element in a list. Even music notation contains control structures for expressing loops. Though I have employed loops extensively already, I haven’t discussed them in detail yet. This is done in this chapter. Following the weather reporter Phil Connors, who relives Groundhog Day over and over again, I explain how loops and other control structures work. I show different ways of describing loops and the differences in the computations they can express.

  Forever and a Day

  You may have heard about Groundhog Day, the tradition according to which a groundhog can foreshadow—literally—six more weeks of winter or an early spring. This works as follows. Each year, on the second day of February, a groundhog comes out of its burrow. If on a sunny day it sees its own shadow, it retreats into the burrow, indicating that winter will last for six more weeks. If on a cloudy day it can’t see its own shadow, this means an early arrival of spring.

  Growing up outside of the United States, I learned about this tradition through the 1993 movie Groundhog Day, in which Phil Connors, an initially arrogant and cynical weather reporter from Pittsburgh, reports about the Groundhog Day festivities in the small town of Punxsutawney. The intriguing feature about the movie is that Phil Connors has to relive the same day over and over again. Each morning he wakes up at 6:00 a.m. to the same song on the radio and has to experience the same series of situations. The plot of the story unfolds as he reacts differently to these situations over the course of the movie.

  Repetition plays an important part in all of our lives. Learning a skill makes sense only if we can expect that it will be applicable in the future. More generally, any use of past experience works only in circumstances that are similar to the one in which the experience was gained. Every day we repeat many things: getting up, getting dressed, having breakfast, commuting to work, and so on. An action (or a group of actions) that is repeated immediately several times is called a loop. The action that is repeated is called the body of the loop, and each execution of a loop’s body is called an iteration of the loop. Talking to someone at a bar, Phil Connors reflects on his situation:

  Phil: What would you do if you were stuck in one place and every day was exactly the same and nothing that you did mattered?

  Ralph: That about sums it up for me.

  This exchange can be summarized in the following characterization of one’s life by a loop:

  repeat daily routine until you die

  What makes Phil Connors’s daily routine so maddening to him—and so funny to the viewer of the movie—is that everything happens in exactly the same way as the day before, that is, everything that is not a direct response to his actions during the day. Otherwise, the movie would quickly become boring, like a monotonously repeating refrain at the end of a song.

  Our days are typically less frustrating than the ever-repeating Groundhog Day because our actions yesterday have an effect on today. Therefore, each day, no matter how repetitive it may seem, happens in a different context, and the knowledge that what we and others do makes a difference provides us with a sense of continuous change and progress. These observations suggest a distinction between two kinds of loops, namely, loops that produce on each iteration the same outcome and loops that yield different outcomes. An example of the first kind is a loop that prints the name of the city you were born in, say, New York. Barring any renaming of the city, this loop will produce a steady stream of the same outputs, such as “New York” “New York” “New York” …. In contrast, a loop to report whether it is raining will produce a stream that contains a mix of yes and no values—unless you live in Cherrapunji,1 where it’s likely to produce a constant stream of yes values.

  Note that even in a loop that produces varying outcomes, the loop body is the same for each iteration. The variation is achieved by variables. A variable is a name that points to part of the world. Through the variable name the algorithm can observe and manipulate the world. For example, the variable weather points to the current weather condition, say, sunny, and an algorithm that checks the current weather by accessing this variable would obtain the corresponding value. The variable weather cannot be changed by an algorithm, but the variable pebble that refers to the next pebble Hansel and Gretel walk toward changes with each pebble visited. Similarly, in the instruction to find the smallest element in a list that is part of selection sort, the variable smallest element changes in each iteration unless the list contains duplicates.

  Since the term loop is sometimes used for both the description of the loop (the algorithm) and the computation it generates, this is a good time to recall the difference between the description of a computation and its execution. A loop for the daily weather report looks as follows:

  repeat report weather until forever

  The result of executing this loop is a sequence of values, which is a very different thing from the loop description itself. For example, the execution of the algorithm could lead to the following sequence:

  rainy cloudy sunny sunny thunderstorm sunny …

  This weather-reporting loop describes the kind of loop that Phil Connors finds himself in: each morning he has to prepare a report on the forecast of his colleague, the groundhog Punxsutawney Phil. (Interestingly, despite all the dramatic variations he creates for the day—at one time he even tries to kill Punxsutawney Phil—he never seems to miss his report about the groundhog’s forecast.) Of course, Phil Connors hopes that the loop he is in does not repeat forever. In fact, he assumes the loop is of the following form:

  repeat report weather until ‘some hidden condition’

  His initial attempts to escape this loop are essentially efforts to discover the hidden condition, which is a critical component of any loop, called its termination condition. Toward the end of the story we learn that the termination condition is his becoming a good person, somebody who cares about and helps other people. His reincarnation every day provides an opportunity to perfect his karma, which is the key to his leaving the purgatory-like Groundhog Day.

  The Groundhog Day loop is an instance of the following general loop schema:2

  repeat step until condition

  The termination condition appears at the end and is evaluated after the body of the loop has been executed. If the condition is true, the loop stops. Otherwise, the body will be executed again, after which the condition is also checked again to determine whether to continue or end the loop, and so on.

  It is clear that a termination condition that is false at one time can become true later only if it contains a variable that can be changed by the actions of the loop body. For example, efforts to start a car that has run out of gas will not succeed until gas is refilled. Thus, if the repeated actions include only turning the ignition key or maybe kicking the tires or the incantation of a magic spell, they won’t help. The termination condition thus lets us distinguish between terminating loops whose termination condition eventually becomes true, and nonterminating loops whose termination condition always remains false.

  It has been said that insanity is doing the same thing over and over again and expecting different results.3 We might be tempted therefore to brand nonterminating loops as insane, but there are examples of perfectly valid loops that do not terminate. For example, a web service is a loop that takes a request, processes it, and then continues to take the next request, ad infinitum. However, when a
loop is part of an algorithm—in particular, when it is followed by other steps—we expect it to end eventually because otherwise steps that follow the loop could never be executed, and the algorithm would not terminate either.

  Termination is one of the most important properties of a loop. The termination condition determines whether a loop ends, but it is the effect the loop body has on the world that is critical for the loop’s termination, specifically the effect on those parts of the world on which the termination condition depends. Reporting the weather does not change the world very much and seems unlikely to have an effect on the unknown termination condition in Phil Connors’s Groundhog Day loop. In frustration, he tries out more and more extreme actions, including different forms of suicide and killing Punxsutawney Phil, desperately hoping to affect the world so that the termination condition finally becomes true.