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 FROGGER set equal to 4 ("Wow!"). Then, all
of a sudden, he added 12 to FROGGER! ("Oh, no!") But, quick as a
flash, he stored the answer into BIRDIE ("Whew, that was close!"). In
the end, he printed both FROGGER and BIRDIE, and they were both
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."
If you think about it, you'll probably agree that movies like this
would not be as powerful or as interesting as regular movies; the
heros 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 better
discipline, 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 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 bridge" 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; that car is coming fast!
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 monstrous,
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, 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 something that is either true or false. There is
no uncertainty or equivocation with "condition": it is one or the
other. "Action" is the option that is selected. If this all sounds
strange, just try the example: "condition" is "team A has the higher
score". There's nothing abstruse about that, is there? It's either
true or false; either team A has the higher score, or it doesn't. And
"action" is simply, "team A is the winner". Thus, the statement
becomes:
IF (team A has the higher score) THEN (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 BASIC. The statement in BASIC that makes
decisions is called the IF-statement, and it looks like this:
IF condition THEN command
In this statement, the command-part is any regular BASIC command,
such as FROGGER=5 or PRINT BIRDIE. The condition-part is a little
trickier. It is a logical expression. A logical expression is not a
command. It is a statement, a declaration that may or may not be
true. Sometimes a logical expression can look just like a command,
but that doesn't make it the same. Here's an example of what I mean:
10 FROGGY=5
20 IF FROGGY=6 THEN PRINT "YOU GOOFED!"
Line 10 is a command; it tells the computer, "Computer, I command
you to put a 5 into FROGGY!" But in line 20, the reference to FROGGY
is a logical expression. It asks the computer if FROGGY really is 6.
The computer will, of course, evaluate the statement as false,
because FROGGY is actually 5, and so it will not print "YOU GOOFED!"
Logical expressions can take many forms. They can evaluate
equality with the equals sign (=), as in the above example. You can
get much more complex than that example if you want:
30 IF (FROGGY+2)*5=(BIRDIE-7)/3 THEN PRINT "FROGGY'S the one"
For that matter, you can also determine if two numbers are
unequal. The symbol to use for this is <>, a "less than" sign
followed by a "greater than" sign. Together, they mean "is not equal
to". So we could have the following code:
40 IF FROGGY=BIRDIE THEN PRINT"They are equal!"
50 IF FROGGY<>BIRDIE THEN PRINT"They are not equal!"
A particularly useful aspect of logical expressions is their
ability to evaluate inequalities &emdash; whether one number is
bigger or smaller than another. The symbols for these are ">"
(greater than) and "<" (less than). I always get them straight by
thinking that the big guy is on the big side of the sideways V. Their
use is illustrated with these commands:
60 IF FROGGY>BIRDIE THEN PRINT "FROGGY is bigger than BIRDIE"
70 IF FROGGY<BIRDIE THEN PRINT "FROGGY is less than BIRDIE"
Just as with the equality symbol, you can get very messy with the
logical expression:
80 IF ((FROGGY-7)*12)+3 > ((BIRDIE+4)/4)-8 THEN PRINT "What a
mess!"
Now let's lean back for a moment and consider broader issues. You
may remember that I began this discussion by emphasizing the need to
strip away petty details and get down to the heart of the matter. Now
that we have reduced decision-making to its simplest form, we
must now return to the question of making real-world decisions. All
of this simplistic, yes-no decision-making may look great in a
program, but what good does it do in the real world? It turns out
that we can now use these simple decisions like building blocks to
address a much more complex range of decisions. Mind you, we won't
be able to solve all the world's problems, but you'll be surprised at
how much you can do with this simple IF-THEN statement. There are
three ways to add richness to the decision-making that we can do with
the IF-THEN statement: compound conditions, compound commands, and
multiple options.
COMPOUND CONDITIONS
Sometimes you may want to consider several factors before taking
an action. For example, suppose that your program is considering the
age of the various people it is working with, but only wants to
consider teenagers whose age is between 13 and 16? The program must
consider two conditions: whether AGE is greater than 13, and whether
age is less than 16. How do you put the two factors together?
In most BASICs you can solve this problem with Boolean operators. These
are simple words, "AND" and "OR", but they are used much more
precisely in BASIC than in English. You use these operators to
couple two logical expressions, thereby creating a third, compound
logical expression. The general rule is pretty much common sense:
AND: If you AND two logical expressions together, then the result
is true only if both expressions are true (e.g., if expression A AND
expression B are both true).
OR: If you OR two logical expressions together, then the result
is true if either expression is true (e.g., if either expression A OR
expression B is true.). If both expressions are false, then the
result is false.
Suppose, for example, that AGE has a value of 14. Here are some
examples of true and false statements:
StatementValue
AGE > 13 TRUE
AGE < 16 TRUE
AGE > 99 FALSE
(AGE > 13) AND (AGE < 16) TRUE
(AGE > 13) AND (AGE > 99) FALSE
(AGE < 16) OR (AGE > 99) TRUE
(AGE > 16) OR (AGE > 99) FALSE
((AGE > 13) AND (AGE < 16)) OR (AGE > 99) TRUE
This last example demonstrates the use of parentheses with logical
expressions. If it generates confusion, just think of the
parentheses the same way that you think about parentheses when you
calculate numbers: figure out the innermost parentheses first and
work outward. In fact, it's quite practical to think of logical
expressions in much the same way that you think of arithmetic, only
instead of working with numbers, you are working with just plain old
true-false answers. Let's try it with the last expression in the
list. First, look at each inequality and determine whether it is
true or false; substitute that result into the expression. That
gives:
((TRUE) AND (TRUE)) OR (FALSE)
Now discard unneeded parentheses that mark off single expressions:
(TRUE AND TRUE) OR FALSE
Now let's collapse that TRUE AND TRUE phrase into a single result. You
will recall that the rule for AND is that when both expressions
are true, then the result is true. And indeed, both are true. So now
we have:
(TRUE) OR FALSE
Discard the unneeded parentheses:
TRUE OR FALSE
And now remember the rule for OR: if either one or the other
expression is true, then the result is true. Therefore, our
expression works out to be:
TRUE
The value of compound expressions is that they make it possible to
evaluate very complex situations. For example, consider this bit of
code that one might see in a football program:
70 IF (DOWN = 4) AND ((YARDS > 2) OR ((THEIRSCORE-OURSCORE)
< 20)
THEN PRINT"PUNT!"
Can you figure out what it means?
COMPOUND ACTIONS
What happens if you want to execute more than one command if the
condition of an IF-THEN statement is satisfied? Suppose, for
example, that you have a program that asks the user to input the age
of a certain person, and you want to check to make sure that the
number that the user types in is reasonable. If the inputted number
is unreasonable, you want to print a message telling the user that
and ask for him to input the value again, then thank the user for
being patient. Your program might look like this:
50 INPUT AGE
60 IF (AGE < 1) OR (AGE > 99) THEN PRINT "That age is odd;
please repeat."
70 INPUT AGE
80 PRINT "Thank you for your patience."
90 (this is the rest of the program)
This code would not do what you want. Even if the age were
correct, it would ask for the age a second time, without explaining,
and thank the user. In other words, lines 70 and 80 are executed
regardless of the results of the IF-THEN statement. So there is the
problem: how do you put multiple lines inside the "THEN" part of an
IF-THEN statement?
The answer relies on a new command that is very simple in
operation. The command is called GOTO and to use it, you simply type
"GOTO n", where n is the line number of the line you want the
computer to go to. The GOTO command breaks the normal program flow. As
you remember, the program flow starts with the first command in
the program and continues to the next largest line, then the next,
the next, and so on until the computer reaches the end of the
program. But the GOTO statement commands the computer to jump to
whatever line number is specified. If you tell the computer to GOTO
60, it will immediately jump there and continue computing from line
60.
This is a very powerful command. It allows you to create whole
groups of commands and execute them all just by telling the computer
to GOTO the first command in the group. At the end of the group, you
can tell the computer to GOTO the line from which it had earlier
come. For example, a correct way to solve the problem of the bad age
input would look like this:
50 INPUT AGE
60 IF (AGE < 1) OR (AGE > 99) THEN GOTO 1000
70 (this is the rest of the program)
1000 PRINT "That age is odd; please repeat."
1010 INPUT AGE
1020 PRINT "Thank you for your patience."
1030 GOTO 70
This code will execute properly; if the age is wrong then the
program will jump to the corrective code in lines 1000-1030, then
when it is done it will jump back to line 70 to resume the normal
program. If the age is OK, it will do nothing in line 60 and go
straight on to line 70.
There is one minor problem with it, a technical detail. What
happens when the computer reaches the end of the program? It will
eventually work its way through all the line numbers higher than 70
and come to lines 1000-1030. Then it will execute those lines, even
though there was no error. Oops! The solution to this is a minor
command that I never bothered to mention before. It is called "END"
and it means just that. When the computer reaches the END statement,
it stops executing the program. So, you should always put an END
statement after your regular program but before all the little chunks
of code like the example. In our example, the END statement might
look like this:
200 END
As it happens, there is a neater way to solve the problem of the
bad age input, but it requires a backwards approach. The code for it
looks like this:
50 INPUT AGE
60 IF NOT ((AGE < 1) OR (AGE > 99)) THEN GOTO 70
62 PRINT "That age is odd; please repeat."
64 INPUT AGE
66 PRINT "Thank you for your patience."
70 (this is the rest of the program)
This code reverses the logic of the IF-THEN statement by using the
NOT-operator. This operator just takes the opposite of a logical
expression. If an expression is true, then NOT-expression is false. If
the expression is false, then NOT-expression is true. It's a
simple idea, but it can be confusing to figure out. The same thing
is true in English: no statement that isn't written with no negatives
is not knotty to figure out, no? Nevertheless, if you dig through it
diligently, you can figure it out. Line 60 now says, in effect, "if
the opposite of the old condition is true, then skip over lines 62-66
to line 70." The advantage of this approach over the earlier version
is that lines 62-66 automatically feed into line 70 when they are
done without requiring another GOTO statement. This approach cuts
down on the amount of "spaghetti code" that you create. Spaghetti
code is code that is full of GOTO statements, jumping all over the
program. Programs like this are very confusing to read, and so they
are difficult to work with. Since this latter approach is cleaner
than the former approach, it is considered superior. However, please
remember that both approaches work just as well. The difference is
one of style, not function.
MULTIPLE OPTIONS
Now we tackle the toughest problem: how do you put together all of
these binary IF-THEN statements to handle complicated sets of
options? For example, how would a BASIC program handle the traffic
collision problem that I used at the beginning of this chapter? Let
us assume that the computer is driving the car (Lord help us!) and is
capable of calculating the probabilities of collision for each of the
three options available. How could it choose among three options
with its IF-THEN statement?
The answer requires the use of several IF-THEN statements in a
sequence. Let's say that it has stored the probability of avoiding a
collision by swerving to the left into the variable LEFTSAFE.
Similarly, it has stored the probability of avoiding a collision by
swerving to the right into the variable RIGHTSAFE, and simililarly
for STRAIGHTSAFE. It must decide which probability is highest and
indicate the proper course of action. It does this by examining each
in turn. Here's how it's done:
50 IF LEFTSAFE > RIGHTSAFE THEN GOTO 110
60 IF RIGHTSAFE > STRAIGHTSAFE THEN GOTO 90
70 PRINT "GO STRAIGHT"
80 GOTO 200
90 PRINT "SWERVE RIGHT"
100 GOTO 200
110 IF LEFTSAFE < STRAIGHTSAFE THEN GOTO 70
120 PRINT "SWERVE LEFT"
200 END
If you trace the program flow for each of the three possible
cases, you will find that the program correctly deduces the correct
course of action in each case. There is an ambiguity when two of the
three values are equal; in this case, the program will prefer
straight over right and right over left; that is an arbitrary aspect
of the order in which the statements are executed.
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 arguement 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. One command from that section looks something like
this:
2240 INTEGRITY=INTEGRITY - SHOULD
Talk about blasphemy; here is a formula for integrity! Before you
cross yourself and reach for the garlic, though, consider this: line
2240 does not present the formula for integrity; it presents a
formula for integrity. The idea expressed in line 2240 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
2240 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
&emdash; no matter how you 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 the equation in line 2240 as final truth.