Indiana University Multi-campus Modular Computing Curriculum

Course C Programming Concepts

Module # 1: The Mechanics of Program Writing

Goals

• Students will use their problem solving skills to navigate a specific programming environment.

• Students will interact with the Shakey the Robot applet^{1}, and understand the relationship between the program^{2} and its behavior.

• Students will understand the concept of a program as a sequence of statements in a particular language.

• Students will understand what it means to run or execute a program.

• Students will practice writing programs to direct Shakey through specific tasks.

• Students will understand the difference between syntax^{3} and semantics^{4} .

• Students will understand how and why to use program comments^{5} .

1

A Java program, which is linked into an HTML document, then retrieved and executed using a Web browser.

2A series of instructions executed by the computer, one after another.

3

The syntax of a computer language specifies how words and symbols can be combined into valid programs. Another word for syntax is grammar.

4

The semantics of a properly formed program statement describes the meaning of the statement in plain English and how it will be interpreted by the computer when it is executed.

5

Most programming languages provide a mechanism that allows a programmer to embed documentation directly into a program. Comments provide additional information and explain special processing. All text within a comment is for the benefit of the human audience, and is ignored by the computer.

1-1

Module # 1: The Mechanics of Program Writing

• Students will understand the debugging^{6} process.

Prerequisite Skills

• Students must understand the STAIR problem solving process.

• Students must have a basic understanding of computer hardware^{7} and software^{8} .

• Students should be familiar with a graphical web browser, such as Netscape or Explorer.

Programs: Easy as Pie...

You are a complex computing machine. You carry out pre-programmed instructions all the time. For example, consider the process of baking a cherry pie. This is a well-known task that humans have been doing for centuries. Even if you don’t know how to bake a cherry pie, you do know that recipes for such a task exist.

1-2

6 Debugging is the removal errors, or bugs, from a computer program. It may take several attempts before all bugs are found and eradicated, and its even possible to introduce new bugs while trying to fix the old ones!

7The tangible components of a computer system, such as the keyboard, monitor, and circuit boards.

8Programs and data.

Module # 1: The Mechanics of Program Writing

Such [^{9} consists of an ordered sequence of steps. It’s crucial to perform the steps in the prescribed

9

Cherry Pie] a recipe

Ingredients:

• 1 cup milk

• 2 Tablespoons softened butter

• \frac{1}{4} teaspoon almond extract

• 2 eggs

• \frac{1}{2} cup Bisquick

• \frac{1}{4} cup sugar

• 1 can cherry pie filling (dark)

• \frac{1}{2} cup Bisquick

• \frac{1}{2} cup brown sugar

• \frac{1}{2} teaspoon cinnamon

• 2 Tablespoons cold butter Directions:

1. Heat oven to 400F.

2. Grease a 10” pie plate.

3. Beat first 6 ingredients until smooth (about 15 seconds in blender or 1 minute with hand blender).

4. Pour into pie plate. Spoon pie filling evenly over top.

5. Bake for 25 minutes.

6. Prepare streusel: cut butter into bisquick, brown sugar, and cinnamon until crumbly.

7. At end of 25 minutes baking time, top pie with streusel.

8. Bake until streusel is brown, about 10 minutes longer.

9. Cool before serving; refrigerate any remaining pie.

1-3 order. It would not make sense to “bake for 25 minutes” before you’ve performed the “heat oven to 400F” step. But, if you follow the instructions carefully, you should be able to produce a cherry pie at the end. Note that there is a clear beginning and end to this entire process. Furthermore, note that you are probably following a recipe that someone else invented and wrote down. In computer science, we would say that you are executing a program for baking a cherry pie.

Similarly, planning a task is a familiar process. You want to bake a cherry pie. First, you search for a recipe. Then you go shopping for the ingredients. Then you follow the recipe, wait for the pie to cool, and, at long last, eat a big slice! You came up with this process on your own. You didn’t find it in a book. You devised your own program, and then executed it. One step in your program involved doing the actual baking, which meant following the instructions in the recipe. But, once that was accomplished, you pick up with the “wait” step of your program and continue.

So, planning a task is akin to writing a program and following a recipe is akin to executing or running a program. A program is nothing more than a sequence of instructions, written by you or by someone else.

Bugs and Miracles

Suppose you located your recipe for cherry pie in a cookbook written by Julia Child. She, Julia Child, is the programmer. She may have tried several variations of her cherry pie program before she got it just right. Each time she had a new idea, she couldn’t just imagine what the results would be. She actually had to bake a real pie using her new idea. That is, she had to execute her modified program. Then she had to test the result by tasting the pie. Maybe it was a good idea, and maybe it wasn’t... maybe it had a bug in it! This process of refining a solution until it’s correct is called debugging.

Rather than planning tasks for people to perform, in this course you will plan tasks for the computer to perform. Furthermore, whereas it’s easy for us to make a mistake when following a recipe (inadvertently skipping a step, or substituting salt for sugar), we can safely assume that the computer will make no such errors. If the end product is not what we expect, then the mistake is with our program, not with the computer itself.

Finding errors in programs and correcting them is much of what programming is all about. In order to make your programming experience as rewarding and painless as possible, and so you can have the benefit of our experience, you will use a friendly environment for developing your programs in this course. Initially you will use an environment for manipulating a simple robot. Later, you will use a more sophisticated environment, called Miracle, for creating JavaScript programs. These environments will, hopefully, guide you through the process in a controlled way, so that you avoid many of the most common pitfalls for beginning programmers.

1-4

Communicating with Language

Julia Child wrote her cookbook in English, and that is why we can understand and follow her directions. If the cookbook had been in French, at least some of us would have a hard time understanding what to do.

To program a computer we must first agree on a language that both we, as programmers, and the computer understand. A computer is not sophisticated enough to understand a natural language like English or French, so we must settle on one of many possible computer languages.

A computer is also not intelligent enough to make inferences about what we mean if we don’t use the proper grammer. A native English speaker can easily understand the meaning of this sentence “I ain’t gonna go nowhere, nohow, not never.” However, when we communicate with the computer in the computer’s language, we must use the proper grammar at all times. If we speak improperly, the computer will simply inform us of our error and give up.

Syntax = Grammar

To learn any new language, one must not only learn the words and their meanings, but also the rules describing how words can be combined to form valid sentences. The syntax of a language is a set of rules governing the formation of grammatically correct sentences. In a natural language like German, one must understand the rules regarding adjective endings and verb placement. In a computer language, one must understand the structure of each instruction and the proper use of punctuation.

The sentences in a computer language are frequently called program statements, and errors in the formation of statements, i.e. grammatical errors, are called syntax errors. A program that contains one or more syntax errors will not execute.

For example, a simple declarative English sentence has the following form:

article noun verb article noun .

If we agree that the word the is a particular instance of article, cat and milk are instances of noun, and drinks is an instance of verb, then the sentence

                            The cat drinks the milk.

is syntactically correct. So is

1-5

                            The milk drinks the cat.

It’s certainly true that the computer which is our brain would be quite confused if we heard the above sentence. Our brain does not reject the sentence based on improper syntax, but rather on what we know about the meanings of the individual words in the sentence.

Q. 1 Which of the following sentences contain one or more syntax errors based on the grammatical rule above?

  1. The cat drinks the milk
  2. The drinks milk cat the.
  3. The cat drinks milk.

Answer: They all contain syntax errors!

 The cat drinks the milk Missing period.
 The drinks milk cat the.  drinks is not a noun.
 The cat drinks milk.      Milk is not an article.

(Answer on page 1-??.)

Punctuation is an important part of the syntax of a computer language, and it must be used properly. Common punctuation symbols are {, }, (, ), ", and ;.

0.1 Semantics = Meaning

A statement can be properly formed, yet produce an improper meaning, as with the sentence The milk drinks the cat. The meanings assigned to the words in a language compise its semantics. Errors in the meaning of statements are called, not surprisingly, semantic errors. A program that contains one or more semantic errors will not produce the desired results. The program will execute, but it may stop unexpectedly at some point or it may run to completion but yield an incorrect result.

Going back to our cherry pie example, if we accidently use salt instead of sugar, then we eventually get a pie at the end. It looks good, but when we taste it, we realize that something went wrong during the execution of the recipe program. On the other hand, if Julia Child neglected to mention that we needed cinnamon in the list of ingredients, then when we get to the step that tells us to add the cinnamon, we would have to stop immediately and proceed no further because we don’t have any cinnamon in the house. In this case, we don’t get a pie at the end.

Semantic errors are only detected during or after the program execution, and so are also called run-time errors.

1-6

Robots, Real and Imagined

The most famous real-life robot in recent memory is probably \underline{the Sojourner rover}^{10}, part of the \underline{Mars Pathfinder Mission}^{11}, built by NASA and sent to Mars to travel its uncharted, pathless surface in Summer 1997. In 1992, Indiana University’s own \underline{Professor Jonathan Mills}^{12} invented \underline{Stiquito}^{13}: a simple, inexpensive, six-legged walking robot. Professor Mills envisions one day possibly sending off a group of 1000 or more of these small, insect-like robots into outer space. For more current information about the world of robotics, check out the links on \underline{the cool robots page}^{14}.

We start our journey into programming by writing programs to direct an imaginary robot, named Shakey, through some simple tasks. Shakey lives on a fixed size grid, surrounded on all sides by a high fence. Besides Shakey himself, there are two other types of objects that can occupy his world. The first type of object is a wall. Walls are used to represent obstacles that Shakey must maneuver around, such as hurdles, mountains, enclosed rooms, and mazes. The fence along the perimeter is also composed of walls.

The second type of object in Shakey’s world is an item. Shakey is equipped with a mechanical arm that he can use to pick up and put down items. Some of Shakey’s tasks involve picking up or putting down patterns made from items, or finding and transporting items.

Whenever we want Shakey to carry out a task in his world, we must supply him with a program, that is, a detailed set of instructions that describes how to perform the task. Shakey can receive, memorize, and execute such a program, assuming that it is written in a language he can understand.

The program can be saved in a file, to be later recalled and executed again and again. This is very similar to the redial feature found on most telephones – a number is recorded and then played back later (as many times as is desired) at the touch of a button.

0.1.1 Acknowledgement

Much of this material on Shakey was inspired by Karel the Robot. The definitive source for information about Karel is the book Karel the Robot, a gentle introduction to the art of programming, by Richard E. Pattis, second edition with revisions by Jim Roberts and Mark Stehlik, published by John Wiley and Sons, 1995.

There is also an object-oriented version called \underline{Karel++}^{15}.

1-7 Shakey’s Language

10http://mpfwww.jpl.nasa.gov/rover/sojourner.html

11http://mpfwww.jpl.nasa.gov

12http://www.cs.indiana.edu/hyplan/jwmills.html

13http://www.computer.org/cspress/catalog/bp07408.htm

14http://ranier.hq.nasa.gov/telerobotics_page/coolrobots.html

15http://csis.pace.edu/~bergin/karel.html

Shakey understands the following six commands:

1. step: When Shakey executes a step instruction, he moves forward one square on his grid, continuing to face in the same direction as before. Shakey’s program will terminate with a run-time error if he is ever directed to step into a wall. He may occupy the same square as an item.

2. left: Shakey executes a left instruction by pivoting 90 degrees to the left, remaining on the same square.

3. right: Shakey executes a right instruction by pivoting 90 degrees to the right, remaining on the same square.

4. pickup: Shakey picks up an item from the square he is standing on. If he executes a pickup instruction and the square he is standing on does not contain an item, then his program terminates with a run-time error.

5. drop: Shakey places one item on the currently occupied square. If he is not carrying any items, or if the current square already contains an item, then his program terminates with a run-time error.

6. home: Shakey moves directly to his home position. He does not pass go... he does not collect 200 dollars. (Ordinarily, Shakey’s home position is in the upper left hand corner of his grid, facing north.)

There is no limit to the number of items that Shakey can carry at one time.

These six commands constitute the core of Shakey’s language. Later, you will see how to extend the language by using these six commands as building blocks. Because they form the foundation of the language, they are sometimes called primitives.

Syntax of a Shakey Program

A Shakey program contains a sequence of Shakey commands. When a Shakey program is run, he performs each command, one after the other, in the order given.

When you use the programming environment to construct your program, the text window will display the program that you are creating. You do not have to actually type each program statement yourself. Thus, you do not have to be overly concerned about the precise syntax of Shakey’s language. However, you will see the text of your program and you should be able to recognize the different statements and know what they do.

Here is the syntax of each Shakey command:

     command-name();

1-8 The trailing punctuation after the command name is required, just as the period must appear at the end of an English sentence.

For example, the following sequence of instructions could be part of a Shakey program.

     step();
     left();
     drop();

All of the statements that comprise the program are surrounded by curly braces, { and }, and there is a header to the program of the form:

     function main()

Here is an example of a complete Shakey program that will cause him to turn right, take two steps, drop an item, and then return to his original position:

     function main()
       right();
       step();
       step();
       drop();
       right();
       right();
       step();
       step();
       left();

0.2 Formatting Details

For readability, we will put only one command on a single line, and each command will be indented slightly. Lines can be left entirely blank, and we will do so frequently in our examples to show which parts of the program hang together logically.

You must use all lower case letters in the command names. The command is step, not Step or

STEP.

Comments = Documentation

Although Shakey will be carrying out the instructions in your program, humans may also read the code you write. Naturally, this includes your instructor, but it also includes you yourself. Consequently, the language allows us to insert annotations within the code. These annotations are called comments^{16} , and they are completely overlooked by Shakey. Comments serve to explain

1-9 the intended logic of the program to the human audience.

16

Most programming languages provide a mechanism that allows a programmer to embed docu-

mentation directly into a program. Comments provide additional information and explain special

processing. All text within a comment is for the benefit of the human audience, and is ignored by

the computer.

In Shakey’s language, any text following the symbols // on a line designates a comment. For example:

// Take two steps and turn left.
step();  // first step
step();  // second step
left();  // turn

The use of blank lines and comments makes your program easier for you as the programmer to develop.

Q. 2 In English, explain exactly what the following program fragment does.

left();
left();
step();
left();
left();

Answer: When the program fragment is executed, it causes Shakey to step backwards one square. We could comment the program like this:

// Take one step backwards.
// 1. First turn around.
left();
left();
// 2. Now take the step.
step();
// 3. Finally, turn around again, so Shakey is
//    facing in the original direction.
left();
left();

If we remove all the code from the above example, then we are just left with the comments, which gives us a pseudocode^{17} variant of the program solution:

1-10

17 Pseudocode is an informal language that helps programmers develop algorithms for solving problems. The steps in a pseudocode program are expressed in everyday English. Such programs are not actually executed on computers. Each step in a pseudocode program must be translated into one or more steps in a computer language before the program can be executed.

     // Take one step backwards.
     // 1. First turn around.
     // 2. Now take the step.
     // 3. Finally, turn around again, so Shakey is
     //    facing in the original direction.

Your initial design of a program solution in pseudocode will typically end up corresponding to comments in the actual code.

(Answer on page 1-??.)

Debugging Shakey Programs

There are two type of errors, or bugs, that can creep into your program. A syntactic error occurs when Shakey sees a word in his program that is not part of his vocabulary. If you inadvertently enter loft instead of left, then the computer will not even attempt to execute your program. Instead you are presented with an error message giving the nature and location of the bug.

Happily, the programming environment you will use insulates you from such tedious syntactic bugs, since you do not actually type your program yourself. The program construction is carried out automatically. All you need to do is select the appropriate program elements in the appropriate order. Thus, you need not worry about typos or forgetting punctuation. You can concentrate on the more important task of program design^{18} and correctness.

Assuming your program does not contain any syntactic errors (and it won’t if you construct it inside the programming environment), then the computer will execute the program. Semantic errors are mistakes in the logic of the program, and emerge when the program is run. For example, it is a semantic error if you direct Shakey to step into a wall at some point.

Just because Shakey successfully completes his program without any error messages, does not mean that the program is error free. Perhaps he does not successfully complete his task. Only you can judge whether or not the result of running the program is correct. For example, suppose you want Shakey to jump three hurdles, but when your program runs, he only jumps over two hurdles. In that case, you must go back and re-examine your logic, make corrections, and run the program again. This is analogous to tasting your cherry pie to see if it turned out well. If it didn’t, you must analyze your recipe to determine what caused the failure.

Rarely is a program bug free on the first draft. Debugging is the main activity of even expert programmers.

1-11

18The plan for implementing a program, sometimes expressed using pseudocode.

Laboratory Assignment

Exploring the Shakey Environment

Exercise. 1 Shakey will do whatever you tell him to do, within his limited abilities.

Launch the Shakey applet and this is what you’ll see.

Click on the command buttons and see how Shakey reacts. You should see the corresponding instructions, along with descriptive comments, appear in the text window.

Some actions will produce errors. Try stepping Shakey into a wall, or picking up an item from an empty square.

Q. 3 What happens in the text window when Shakey encounters an error? Is the offending instruction included in the program? Answer: No! If Shakey executes an instruction that results in an error, then this instruction is not included in the program under construction. In the case of a bad step, only a comment appears in the program.

(Answer on page 1-??.)

Running a Shakey Program

You have seen how to direct Shakey one instruction at a time. If the task to perform is long or complicated, it can be quite tedious to repeatedly devise the correct instructions in this interactive fashion.

It would be nice if we could develop the program just once, and then execute it over and over again.

Exercise. 2 Clear the window by selecting “Load” and then “Clear”. Select “New Program”. Go through the sequence of commands to cause Shakey to take two steps, drop an item, turn right, and step. If you make a mistake, simply start over. When you are satisfied that the program that

1-12

Module # 1: The Mechanics of Program Writing

appears in the text window is the correct solution for this problem, clear the window and then select “Run” to execute the program. You may run the Shakey program as many times as you wish, but be sure to clear the window first.

Q. 4 What happens if you forget to clear the window before running the program? Answer: You get a run-time, or semantic, error! Only one item may appear in a single grid location. There is already an item at the precise point where Shakey tries to execute the drop instruction. Notice that the program does not run to completion. It stops early, as soon as the error is detected. (Answer on page 1-??.)

That was a very short program. Now construct a longer program of twenty or so instructions. It doesn’t matter what Shakey does... he can just turn in circles... You can change the speed at which a program executes by adjusting the “Speed” slider bar.

Q. 5 Is it possible to change Shakey’s speed during program execution? Answer: Yes! (Answer on page 1-??.)

Try experimenting with the “Suspend” and “Resume” features of “Run”.

Running Hurdles

Exercise. 3 “Load” allows you to initialize Shakey’s grid to various predefined patterns. Load the “Hurdles” world now.

The walls represent vertical hurdles that Shakey, the track and field star, is about to run. At the top of each hurdle is a flag. Try moving Shakey about this world.

Q. 6 What happens if you try to step into a hurdle? Answer: Error! Those hurdles are walls! (Answer on page 1-??.)

1-13 Q. 7 Construct a program that will maneuver Shakey over the hurdles, one at a time, and have him collect all the flags. Shakey must land on the ground after jumping over each hurdle... he is not strong enough to jump over more than one hurdle at a time.

Answer: Here’s one possible solution. It is commented differently than the automatically generated comments that you see in the text window, but these comments should clarify the logical structure of the program.

1-14

function main()
// Hurdles world loaded.
home();
//-----------------------
// JUMP THE FIRST HURDLE.
//-----------------------
// Take off...
right();
step();
left();
// Go up the left side...
step();
step();
step();
// Round the top and pickup the flag...
right();
step();
pickup();
step();
right();
// Go down the right side...
step();
step();
step();
// Get set for the next jump...
left();
step();
left();
//------------------------
// JUMP THE SECOND HURDLE.
//------------------------
// Take off...
right();
step();
left();
// Go up the left side...
step();
step();
step();
// Round the top and pickup the flag...
right();
step();
pickup();
step();
right();
// Go down the right side...
step();
step();
step();
// Get set for the next jump...
left();
step();
left();
//-----------------------
// JUMP THE THIRD HURDLE.
//-----------------------
// Take off...
right();
step();
left();
// Go up the left side...
step();
step();
step();
// Round the top and pickup the flag...
right();
step();
pickup();
step();
right();
// Go down the right side...
step();
step();
step();
// Get set for the next jump...
left();
step();
left();
//----------------------------------
// JUMP THE FORTH (AND LAST) HURDLE.
//----------------------------------
// Take off...
right();
step();
left();
// Go up the left side...
step();
step();
step();
// Round the top and pickup the flag...
right();
step();
pickup();
step();
right();
// Go down the right side...
step();
step();
step();
// Get set for the next jump...
left();
step();
left();

1-15 One thing to notice is that the code fragment for jumping the first hurdle is exactly the same as the code fragment for jumping the second (and third, and forth) hurdle.

If we remove all the distracting commands, then we are left with only the comments, which gives us a nice pseudo-code version of the program.

// Hurdles world loaded.
//-----------------------
// JUMP THE FIRST HURDLE.
//-----------------------
// Take off...
// Go up the left side...
// Round the top and pickup the flag...
// Go down the right side...
// Get set for the next jump...
//------------------------
// JUMP THE SECOND HURDLE.
//------------------------
// Take off...
// Go up the left side...
// Round the top and pickup the flag...
// Go down the right side...
// Get set for the next jump...
//-----------------------
// JUMP THE THIRD HURDLE.
//-----------------------
// Take off...
// Go up the left side...
// Round the top and pickup the flag...
// Go down the right side...
// Get set for the next jump...
//----------------------------------
// JUMP THE FORTH (AND LAST) HURDLE.
//----------------------------------
// Take off...
// Go up the left side...
// Round the top and pickup the flag...
// Go down the right side...
// Get set for the next jump...

One advantage of this particular solution is that it generalizes nicely. It’s fairly easy to see how to extend this program to make Shakey jump five or six hurdles.

(Answer on page 1-??.)

Now you are ready to begin writing some programs on your own.

1-16 Getting the Newspaper

Exercise. 4 Every morning Shakey is awakened in bed when his newspaper is thrown onto the front porch of his house. Program Shakey to retrieve his paper and bring it back to bed with him.

The Newspaper world depicts an arial view of Shakey in the morning.

To get you started, here is a pseudocode solution.

       // Newspaper world loaded.
       // Leave the bedroom...
       // Go to the door...
       // Get the paper...
       // Return to bed...

Shakey Goes Shopping

Exercise. 5 On the way home from the supermarket, Shakey’s shopping bag ripped at the bottom, leaking a few important items. The initial situation, when Shakey discovered the leak, is represented in the Shopping world.

Program Shakey to pick up all the dropped items and then line them up inside his house, as shown below:

1-17 Bowling for Dollars

Exercise. 6 In his spare time, Shakey works as a pin-setter in the local bowling alley. If you load the Bowling world, then Shakey is positioned in the middle of the window, holding ten bowling pins.

Write a program that directs Shakey to place the pins in a triangle shape, where the first row contains one pin, the second row contains two pins, the third row contains three pins, and the forth row contains four pins. The pins on each row are separated by a blank spot.

Design your solution so that is can be easily extended. That is, it should be fairly easy to modify your program if, instead of ten pins, Shakey started with fifteen pins and placed a fifth row of five pins in the triangle.

1-18