With these remarks on the structure of simple Modula-2 programs, it is time to return to the theme of problem solving. This was discussed at the start of chapter one; here that general discussion will be applied specifically to the kinds of problem for which a computer-assisted solution is anticipated. During the course of the following discussion, a simple problem will be posed and a complete solution provided. This will culminate in a program that embodies the solution in a coded form.
Most problems appear insurmountable at first--that seems to be their very nature. Many students (and some teachers), on being presented with one, will scan it over lightly in an attempt to get the whole picture in their mind at once and then, after a few minutes, throw up their hands in despair and shout "I don't know where to start!" Worse still, they may make dozens of trips to the professor or teaching assistants, each time with the same poignant question: "What's the next step?"
Note, however, that the way problem solving was defined in section 1.1 presupposes that a problem is something that has a solution. That which has no solution is not a problem in the sense used in this text. Thus, the person faced with a problem is here assumed to be one who can solve it, given a suitable strategy or technique. The task is to find such a technique, then to employ the computer to implement it. That is, a computer programmer is a problem solver who uses a particular tool (the computer) as part of the solution process.
In section 1.3, eight goals for a problem solver were detailed. It is time to turn those goals into a specific strategy. Thus, though the step-by-step problem solving system that follows still has enough generality to be modified for other types of problem, it has been formulated here with the assumption that computer assistance will be employed in the final process.
Write Everything Down.
1. Have a clear grasp of the existing state of affairs.
2. Have a clear conception of the goal.
3. Formulate the problem clearly.
This forces the would-be problem solver to slow down an overheated mind long enough to read the problem carefully instead of trying to absorb it as a whole by staring at entire paragraphs at once. If necessary, copy the whole thing word for word or highlight it in the book, or tap a pencil on each word while reading it. Before beginning to consider what the solution might be, one must know what the problem means--and that presupposes knowing what the words say.
Write a program that can raise a whole number (say 4) to a positive whole number power (say 6.)
There is no sense using a sledgehammer to crack a peanut or a chain saw to cut a toothpick. Likewise, there is no point in using a computer for simple additions or multiplications. They can be done mentally, or with a calculator, but it is a waste of both human and machine resources to write a computer program for such tasks. True, some of the examples in this book are trivial, but this is necessary to make teaching points simply. Students ought to remember that they have to walk before they can run. It will take a while to begin to realize the true power of the machine, and to write substantial programs to take advantage of that power.
The sample problem posed above is well within the reach of a simple calculator, and is therefore of marginal suitability for computer solution. However, the solution does illustrate how a number of the programming ideas discussed in chapter one are actually implemented in Modula-2.
Still, some problems may be too general, or too easy to be appropriate for computer solution. On the other hand, they may be out of a machine's reach for other reasons, such as the requirement for some thinking process that is outside the domain of machines. Here are examples of the kind of problem that might not at this time be appropriate for computer solution.
1. How do we solve Canada's economic problems?
2. What is the aesthetic value of that painting?
3. Who will win the Stampeders vs. Lions game?
4. Who is right--the Evolutionists or the Creationists?
Partial answers might be obtainable for the first problem by computer analysis of available data (provided that the meaning of the words "economic" and "problem" can be agreed upon). Reference to some base of information also may give an answer to the second question, but only as a dollar value, and even then only if the painting had a previous sales history. The third question can be responded to in terms of probabilities based on an analysis of the past (perhaps computer-assisted) but cannot be answered as stated here. The fourth question is not answerable in any final sense that would be satisfying to all concerned, either via data analysis or the scientific method, since there is no evidence compelling enough to convince either side that its religious or philosophical beliefs are wrong. Each will continue to "keep the faith" regardless of the other's interpretation of the data, and neither is likely to experience a conversion to the other view as a result of any computerized analysis.
There is a third category of problem that may be inappropriate to tackle with the particular resources at hand. These are the questions that could be analyzed by a machine, but not, say by a personal computer, for it may be too slow, or lack a suitable notation, peripherals, or storage space. For instance, one cannot run Canada's income tax collection system or design aircraft frames on a personal computer. One may also find that certain computing notations lack some facilities needed to solve a particular problem efficiently. In this case, the programmer must learn how to work within a different programming environment in order to get the desired answers.
Lack of knowledge about what the computer can do to solve a problem constitutes a fourth difficulty in this category. Even this many years into the computer revolution, many people have a knowledge of computing limited to what they read in the gushy reviews typical of many trade magazines. They often believe in such ephemeral enthusiasms and rush out to buy the latest brand-name computer solution for their accounting, inventory, or information flow troubles. However, computerizing a badly organized business will not solve any of its existing problems; it will only ensure that they occur more rapidly, in greater numbers, and with more potential for harm. An already efficient operation can be improved with carefully chosen machines and software, but an inefficient one will only become worse with the addition of a computer.
Caveat computorae! To err is human. To really foul things up requires a computer.
Murphy's Law: It only takes a millisecond for everything to go wrong using a computer.
At this third stage, one is aiming for an understanding of what is being asked. This is the stage where one begins to go from the general to specifics. If one's conception of what is known and what is required for the solution are vague, there is no point in carrying on. Use headings and point form, and concentrate on the given information and the desired result. Try to be precise. Write out any formulas that are stated or implied--in the latter case, it may be necessary to look something up.
Given: Two whole numbers, one the base and the other the exponent
To Do: Compute baseexponent
Desired Result: print the result
Formula: none. Use a repeated multiplication
Goals: 1. Consider related tasks.
2. Break the main task into sub-tasks.
If you have written any previous programs in Modula-2, there will likely be parts that one can copy into the new solution in order to avoid typing them again. These should be noted now. If this is a first program in Modula-2, one might think that there is nothing to be re-used. However, that is far from the case. Every implementation of Modula-2 comes with a substantial library of routines designed to solve certain problems commonly encountered in writing programs. As noted in the discussion of the simple example earlier in this chapter, those library routines include code for input and output. There are also pre-programmed mathematical functions, utilities for using other parts of the system (such as the computer's clock), and many others. Almost all Modula-2 programs import from these libraries, so a note should be made at any stage of the planning process when it is observed that the library can be used.
This problem has output requirements. It will, therefore make use of the standard STextIO and SWholeIO Modula-2 libraries. No other libraries are required.
This is done first into larger tasks, then into smaller ones. Simple programs may not have this distinction, but most do. Ultimately, individual detailed program statements must be fed to the computer's editor one statement at a time for later compilation. The place to decide how to do this is not at the terminal, as the programmer sits down to start typing. Rather, the steps to solve the problem must be written out ahead of time in enough detail to allow a more or less direct translation into computer code.
The amount of detail necessary varies with experience and familiarity with the question at hand, but most problems worth solving by computer require several refinements first into broad detail, then into finer steps. If several restatements and refinements are necessary, they must be documented. The time spent at this stage saves many hours later. Sloppily designed and poorly thought out programs simply do not work.
1. Input Section obtain base obtain exponent (these will be stored in the program) 2. Computation calculate baseexponent 3. Output print out final result
1. Set up values of base and exponent Assign the value of the base to a cardinal variable Assign the value of the exponent to another cardinal variable 2. Computation set the result initially to the base set a counter to one while the counter is less than the exponent multiply the result by the base and increase the counter 3. Print out the final answer
Goals: Write everything down.
Before actually beginning to code, write down the names of all variables that will be used and the names of all library items required. This section serves as a quick reference when writing the code, so that a name is not inadvertently used for the wrong thing.
Variables: base, exponent, counter, result--all cardinals Imports from STextIO: WriteString, WriteLn from SWholeIO: WriteCard
Here, the exact form of everything that will appear on the computer screen is specified. The final program is correct if it matches the specifications that were written for it in advance. Note that this section does not contain a sample of the actual output produced after the program is run; it specifies what the output for a given input will be before the program is ever written.
Set the base to 5 and the exponent to 6 in the code.
5 raised to the power 6 equals 15625
Goals: Refine the sub-tasks into individual steps.
Writing the solution in pseudocode is just another refinement, this time into a shorter and less wordy form. Pseudocode resembles the final program, but there is no need to pay attention to the exact syntax of the computing notation that will be used.
Write "This program will raise a given base to a given exponent" Assign the base Assign the exponent result <-- base counter <-- 1 while counter <-- exponent result <-- result * base counter <-- counter + 1 write base write "raised to the power" write exponent write "equals" write result
Do not waste scarce computer resources by doing initial rough copies of code at the keyboard. Ideally, what the programmer does type is so well thought out and so carefully written out (by hand) that it compiles and runs error free the first time. Actually, the world may not always turn in this fashion, but it is nice to try. In the case at hand, the final code looks like this:
MODULE Powers; FROM STextIO IMPORT WriteString, WriteLn; FROM SWholeIO IMPORT WriteCard; VAR base, exponent, counter, result: CARDINAL; BEGIN WriteString ("This program raises a base to a power"); WriteLn; base := 4; exponent := 6; result := base; counter := 1; WHILE counter < exponent DO result := result * base; counter := counter + 1 END; WriteCard (base, 0); WriteString ( " raised to the power "); WriteCard (exponent, 0); WriteString (" equals "); WriteCard (result, 0); WriteLn; END Powers.
NOTES: 1. Observe the specific syntax for the listing of variables and giving their type at the start of the program, for assignment and for the Modula-2 version of the WHILE loop. The assignment operator := is a reserved symbol; WHILE and DO are reserved words, and the name CARDINAL is a built-in identifier (see section 2.5.2.)
2. The purpose of the number 0 in the WriteCard statements will be given later.
3. Observe the use of spaces in the WriteString statements in order to separate the words from the numbers.
4. If using non standard-conforming Modula-2, WriteCard may be imported from InOut. Only one FROM..IMPORT line is needed instead of two.
There you have it--the top-down design of a small program in all its gory detail. As mentioned earlier, the amount of detail may vary, as may the number of times one must refine the problem into steps, but the kind of planning outlined here is not optional.
Goals: 1. Execute the completed process.
2. Re-develop the solution until the desired goal is reached.
The task is not complete until the program has been run and the output checked against the specifications. Output from a few sample runs should be recorded and made a part of the documentation for the project.
First run: (using the code above)
This program raises a base to a power 4 raised to the power 6 equals 4096
Second run: (with the base set to 3 and the exponent to 4)
This program raises a base to a power 3 raised to the power 4 equals 81
Only the final code was given above. The first time it was compiled there were several punctuation errors, including some missing semicolons and a missing colon in an assignment operator. The sample program could also use a little more work (not done here) in order to catch erroneous inputs such as incorrectly typed numbers. It also produces an incorrect result if the exponent is zero (try it.) That possibility was not allowed for in the original problem statement, so the solution is correct. However, one could add additional code, either to give a correct result for this case, or to exclude it by printing an error message whenever zero is input for the exponent.