Program Flow
I begin this chapter by introducing you to a new concept that you probably already understand intuitively. It is the concept of program flow. Every program traces a path as it executes, carrying out first one command, and then another, and another, until it reaches the end of the program; then the computer stops executing the program. Program flow is similar to the concept of a storyline for a movie: first the heroine does this, and then that happens, and then somebody else does something, and then the heroine does something heroic, and they all live happily ever after. The story moves from one event to another as it follows the storyline. So too does the computer move from one command to another as it follows the program flow. Perhaps we could even make a movie out of a single program’s execution:
Our story starts with the variable price set equal to 4 ("Wow!"). Then, all of a sudden, the program subtracted 12 from cashOnHand! ("Oh, no!") But, quick as a flash, the program stored the result into bankBalance (“Whew, that was close!”). In the end, bankBalance turned out to be correct. ("Yay!").
Granted, this would not make a very exciting movie, but it does show the similarity between program flow and storyline.
The important concept here is that the program flow starts at the first command of the program, moves to the second command, then the third, the fourth, and so on until it reaches the end of the program. The program flow follows a straight path from the beginning of the program to the end, just like a movie does.
At least, that’s how simple programs work. But in this chapter I am going to introduce you to something you will never see in the movies: program flow that branches. The best way to appreciate branching program flow is to imagine a movie that you could change. For example, imagine a movie in which the beautiful young heroine’s car mysteriously breaks down on a dark and stormy night in front of an old, abandoned house. Blood-red eyes peer from dark windows. “I’ll just wait in the house until morning”, our innocent maiden chirps. “NO!” you cry out, “Don’t go into that creepy house!” But in she goes, the dummy. Well, what if the movie could change in response to your wishes? When you cry out, “Don’t go into that creepy house!” she pauses and says, “On second thought, I think I’ll just wait in the car.”
You’ll probably agree that movies like this would not be as interesting as regular movies; the heroes and heroines would always do the mature, reasonable thing, and they would as dull and boring as the rest of us. But in this case, what makes a bad movie makes a good program. So let’s talk about branching.
Decisions
The essence of branching lies in decision-making. The act of making decisions carefully is one of the central components of Western civilization. We take it for granted, not realizing the degree to which we worship at the altar of decision-making. Perhaps a little story will drive home how crucial this religious devotion of ours is.
In 1757 India was a semi-autonomous collection of principalities under the partial domination of European powers. France and England contended for primacy on the Indian subcontinent. After a series of complex diplomatic maneuvers, the British commander, Robert Clive, led a tiny army of 3,000 men and 8 cannons against an Indian force of 50,000 men and 53 cannons. The odds looked bad, to say the least. The night before the battle, the Indian commander, Suraj-ud-Dowlah, celebrated the victory he felt certain to achieve on the morrow. Clive, by contrast, spent the night meticulously going over every aspect of the coming battle, inspecting troops, positioning his meager forces with painstaking care, planning for every possible contingency. When the battle was fought, the British forces emerged triumphant. The battle of Plassey delivered India into the British Empire. It was won, not by heroism, or superior firepower, or technological superiority, but by careful, thorough, meticulous planning. India was won by sheer force of decision-making power.
Precisely what is a decision? How do we make decisions? At heart, a decision is a choice between options. Three steps are required in the decision-making process:
1. Identify the options available
2. Identify criteria for choosing between options
3. Evaluate the criteria and resolve the decision
An example might show this process in action. Suppose you are driving your car, about to enter an intersection. Suddenly an oncoming car makes a left turn directly in front of you. What do you do?
Let us begin by dispensing with all the nonsense options such as “Play a game of poker” or “Whistle Dixie”. Let us focus on the options that might avert an accident. Three simple possibilities come to mind: swerve to the right, swerve to the left, or hit the brakes and stop here. There might be more, but we don’t have time to debate; a collision is just a fraction of a second away!
Having identified our options, we must now identify our criteria for choosing between options. Our prime criterion is, of course, the avoidance of a collision. Given our uncertainties about the speed of the oncoming car, the condition of the road surface, and the intentions of the other driver, we cannot be certain as to the efficacy of any of the options, so we must think in terms of probabilities. Our decision criterion, then, is, “Which option has the greatest probability of avoiding a collision?” Again, we could get snazzy and throw in such considerations as the fact that an impact on the driver’s side of our car is more likely to injure us than an impact on the passenger side, but, again, let’s not dawdle on fine points when time is so short.
We gauge the relative positions and velocities of the two cars and assess the probabilities of avoiding collisions of each of the three options. From this assessment we conclude the following: if we attempt a straight-line brake to a stop, the probability of collision is very high; if we attempt to swerve to the right, the probability of collision is moderate; and if we attempt to swerve to the left, the probability of collision is low. Since our decision criterion is the lowest probability of collision, we choose the option “swerve to the left”. That is an example of decision-making.
This example also demonstrates the fact that most decision-making is bedevilled by ugly complications and confusing uncertainties. These are the little nasties that demoralize our efforts to decide things carefully. We throw our hands up and declare, “It’s too complicated to figure out. I’ll just choose arbitrarily.” It is sad to see people abandon their greatest human birthright, the ability to exercise free will by making decisions. There is another way to deal with complexity and uncertainty in our decision-making efforts. That way is to strip away the extenuating circumstances, to cut through the underbrush of complicating factors and get down to the heart of the matter. How can we reduce decision-making to its absolute essence?
The first step in this process is to reduce a complex decision to a series of binary choices. Instead of asking, should I take decision A, B, C, or D, we can use a process of elimination rather like that used in sports playoffs. To determine the best football team in the National League, we don’t throw all the football teams in the league into a single stadium and have them play one huge twelve-sided game. Instead, we play a series of binary games, each game determing one victor and one loser, always pitting victors against victors, until there is but one ultimate victor. Choosing between two things is always simpler and easier than choosing between many things.
Sometimes we can simplify even further. When we are considering taking an action, sometimes it is possible to reduce a decision to “Do I take the action or don’t I?” This yes-no type of decision is the simplest possible way to approach decisions about actions.
In the case of a binary decision like this, the criterion for choice between the two options becomes ridiculously simple. It can be a simple true-false or yes-no type of criterion. In the case of football, the football game is a decsion-making process that determines the winner. If team A has the higher score, then team A is the winner. If team B has the higher score, then team B is the winner.
We have now arrived at a surprisingly simple formula for making decisions. It takes the form:
IF (condition) THEN action
Condition is a variable that is either true or false. There is no uncertainty or equivocation with condition: it is one or the other. We call it a “Boolean variable”, because it holds either true or false instead of a number.
Action is what we do if condition is true, like so:
IF (team A has the higher score) THEN print (“team A is the winner”);
If you understand this simple concept of decision-making, then you are ready to use it in your programs, for this is exactly the way that decisions are made in JavaScript. The statement in JavaScript that makes decisions is called the IF-statement, and it looks like this:
IF condition THEN action
In this statement, the command-part is any regular JavaScript command, such as
price = 5;
or
print(price);
To see how this is done in JavaScript, check out this example. Then try your hand at it with this little challenge. After you’ve solved that little puzzle, here’s a bigger puzzle. There are three even better challenges here, here, and here.
Boolean Expressions
Until now we’ve spoken only of variables that are numbers, but now it’s time to introduce you to a different kind of variable: a boolean variable. These are named in honor of George Boole, a British mathematician who invented symbolic logic. Really, all he did was come up with an official way to write down equations about logical situations. You already intuitively understand the basic concepts; this is just a way to write it down in a neat, clean way. For example, suppose that, in order to be eligible to take an advanced programming course, you must have already passed the basic programming course and be a sophomore. Then we write these ideas down as follows:
passedBasicProgramming is a boolean variable that means “you passed the basic programming course”
isSophomore is a boolean variable that means “you are a sophomore student”
isEligibleForAdvancedCourse is a boolean variable that means “you are eligible to take the advanced course”
Then we write it down in boolean form like this:
isEligibleForAdvancedCourse = passedBasicProgramming AND isSophomore
If you passed the basic programming course, then passedBasicProgramming is TRUE; if you did not pass the basic programming course, then passedBasicProgramming is FALSE. Same thing goes with isSophomore. Therefore, if both boolean variables are TRUE, then the equation above says that the conclusion (eligibleForAdvancedCourse) is TRUE. If either of those boolean variables is FALSE, then the conclusion is FALSE.
This is all so simple that you’re probably confused, thinking that there must be some deep, powerful truth that you’re missing. You aren’t. This is really dumb, simple stuff. So why bother with it? Because you can build up these boolean expressions into really big, complicated things if you need to. That’s when this notation is a lifesaver.
I slipped in the boolean operator AND without saying much about it, because it’s pretty obvious what it means. Here is the complete set of boolean operators that computers use:
AND
NOT
OR
Exclusive-OR
You already know what AND means: the expression statement1 AND statement2 is TRUE only if both statement1 and statement2 are true. Easy-peasy.
NOT is also obvious: it makes something the opposite. For example, if isSophomore is TRUE, then NOT isSophomore is FALSE, and vice versa. It’s like the minus sign before a number: -5 is just the negative of 5.
OR and Exclusive-OR must be explained together. OR — we like to call it “inclusive OR” — is true if one or the other is TRUE, or both are TRUE. For example, suppose that we know that
isComputerBroken = computerWillNotStart OR isComputerOnFire
If either of the two cases is TRUE, then the conclusion is TRUE. If both cases are TRUE, then the conclusion is also TRUE.
The inclusive OR operator must be understood in contrast to the exclusive OR operator, which yields TRUE only when just one of the two statements is TRUE. If both of the two statements are TRUE, then the Exclusive OR operator is FALSE. Here’s an great example from Dave Richeson:
Waiter: “Would you like tea or coffee?” (exclusive or)
Patron: “Coffee, please.”
Waiter: “Would you like cream or sugar?” (inclusive or)
Patron: “I’d like both, thank you.”
In the first case (tea exclusive-or coffee), it is clear that the patron would not want both tea and coffee; he would want one or the other. In the second case, the patron might well want one or the other or both. That’s the difference between the two flavors of OR.
Compounding logical statements
So far, this all seems like a lot of academic froofaroo about ideas that are just common sense. Now, however, we’re going to show the value of the Boolean formalism. Oftimes in programs you need to combine a bunch of logical considerations. Here’s an example:
Suppose that you are looking over the menu of entrees at your favorite restaurant. You don’t want to eat something that you’ve previously had there; you want to try something new. You are watching your weight, so you want something with fewer calories. Your doctor has warned you to cut down on salt. Also, you’re feeling like having something spicy rather than bland. You would write this all down in Boolean form like so:
isGoodToOrder = NOT previouslyEaten AND isLowCalorie AND isLowSalt AND isSpicy
Let’s take this a little further. Suppose that there’s nothing on the menu that satisfies these rather stringent requirements, so you decide to loosen them up a bit: you’ll accept a salty dish if it’s low-calorie, or a high-calorie dish if it’s low-salt. Now your expression looks like this:
isGoodToOrder = NOT previouslyEaten AND (isLowCalorie OR isLowSalt) AND isSpicy
Using numbers in boolean form
OK, now let’s suppose that you STILL can’t find anything that meets your requirements, so you have to water them down even more. You decide that you’re willing to order something that you’ve previously ordered, if you had it more than 30 days ago. You can do this with a special kind of operator:
isGoodToOrder = (timeSinceLastOrdered > 30) AND (isLowCalorie OR isLowSalt) AND isSpicy
This new sign (>) means “greater than”. The new expression means “the time since I last ordered this dish is greater than 30 days”. This sign is one member of a family:
> means “greater than”
< means “less than”
= means “equal to”
≥ means “greater than or equal to”
≤ means “less than or equal to”
These operators allow you to include numbers in your boolean expressions.
Conclusions
This has been a long and involved chapter. What does it all mean? The important lesson here is that the computer really can make decisions. They are not the sort of soul-searching, agonizing decisions that we humans make; they are not expressions of free will. They are simple, mechanical decisions. Yet, we should not minimize the value of this kind of decision-making. We can differentiate between decisions involving incalculable factors and decisions that are merely complex. Moral and emotional decisions like, "Should we get married?" fall into the incalculable category, but many other decisions, such as "Which computer should I buy?" are at least theoretically calculable.
You might be surprised to know just how many decisions really can be submitted to calculation. The crucial element is our ability to express seemingly incalculable factors in quantitative form. Part of the problem is our own squeamishness with numbers, a reluctance on our part to reduce flesh-and-blood issues to numerical form. It seems dehumanizing to reduce issues to mere numbers.
But what is so “mere” about a number? Precisely what is wrong with expressing ideas in numerical form? Let’s consider a specific example. I once wrote a program (Balance of Power) that concerned geopolitical conflict. One of the variables I used in the program is called integrity. As you might guess, this variable keeps track of the integrity of the player in his dealings with other nations. Now, integrity is one of our most cherished human virtues, something we revere as special, magic, beyond the soulless world of numbers. But is it not a quantity that a person can possess more or less of? Are not some people distinguished by great integrity, while others are possessed of little integrity? Is it not a small jump from “great or little” integrity to “100 or 20” integrity? Does not the numerical form allow us greater precision?
I will press the argument even further. My program uses another quantity called should, which measures the degree to which the player should help another nation in time of need. The value of should is derived from treaty commitments made by the player. In other words, if I have made solemn treaty commitments to you, then should will have a high value, whereas if I have made only minor assurances, not guarantees, then should will have a low value. My program has a section dealing with the ramifications of a failure to honor one’s commitments. If you make a treaty commitment and then you break it, that means you don’t have much integrity. One command from that section looks something like this:
integrity = integrity - should
Talk about blasphemy; here is a formula for integrity! Before you cross yourself and reach for the garlic, though, consider this: this line of code does not present THE formula for integrity; it presents A formula for integrity. The idea expressed in that line is simple: if you fail to honor your commitments, then your integrity falls in proportion to the solemnity of the commitment. Is this not a reasonable concept? Does it not reflect the truth of the world?
Numbers and formulas are only a way to express ideas. They are another language. There is nothing intrinsically blasphemous about a language. Ideas can be blaspemous; had I written
integrity = murder + lies + theft
that would be blasphemy. The blasphemy does not arise from the quantification of the relationship, but rather from the relationship itself. Integrity does not arise from murder, lies and theft, no matter what language you use to say it.
If you can learn how to express thoughts in quantitative form, you will have made a large step into a new world. Decisions become much clearer when they can be expressed in calculable form. But beware of taking your new-found skills too seriously; ultimately, all such decisions should be checked against simple common sense. Only a fool would take my equation for integrity as final truth.