CPSC 120: Principles of Computer Science
Fall 2002
Lab 6: Thinking About Programs
THIS LAB CONTINUES THE STUDY of programming, which was begun in the previous lab. The emphasis here is on how a complex program can be developed to perform a specified task. An organized approach to programming is necessary for all but the most simple programs. Complex tasks can be broken down into simpler tasks, and complex programs can be built up out of simple components. The problem is how to determine what components are needed and how to piece them together.
Before beginning this lab, it would be useful to be familiar with the material in Chapter 6 of The Most Complex Machine, especially Section 6.3. In particular, this lab uses the ideas of preconditions and postconditions. This lab also uses the "nested squares" example from Section 6.3. You'll also find an introduction to subroutines in this lab. Subroutines are officially covered in Chapter 7 of the text.
The exercises for this lab ask you to save some files in the "homework" directory in your Linux account. Under Windows, make sure that your math account is mounted as a network drive. Goto the Lab5 folder in the cpsc120 folder and double-click the icon named "Run xTurtle Lab6". Assuming that your math account has been mounted, you will be able to directly save files into your homework directory. Please be sure to give your files obvious names, or make a sub-folder for them inside the homework folder.
You can also run xTurtle off the web by clicking the following button. However, if you do this , you will not be able to save your work:
Preconditions
The xTurtle applet that you have launched should have loaded a sample program called "NestedSquares". Select this program using the pop-up menu at the top of the applet. Read the program and the comments, and run the program by clicking on the "Run Program" button. For this example, and for much of the lab, I suggest that you use the speed pop-up menu to reduce the speed at which programs are executed, so that you will better understand what is going on.
As explained in the text, the key to getting this program correct was making sure that the preconditions for drawing each square were set up properly. A precondition is something that must be true at a certain point in a program, if the program to continue correctly from that point.
The following picture, taken directly from Figure 6.9 in the text, shows the correctly drawn squares and the results of five incorrect attempts to draw them. For each of the incorrect versions, the error can be traced to the fact that one or more preconditions was not met in the program that produced that picture:
In the "NestedSquares" program, there are several statements near the end of the loop that are responsible for making sure that the required preconditions are met. You should try to understand why each of these statements is required. You will work with this example in Exercise 1 at the end of the lab.
Postconditions
Preconditions are things that must be true at a given point in a program for that program to continue correctly. A postcondition is something that is actually true at a given point in the program, because of what has been done by the program so far. A common way for programmers to think about programs is to ask, "At this point in the program, do the postconditions from what comes before match up with the preconditions for what is done next." In addition, the effect of a program as a whole can be thought of as a set of one or more postcondition for the entire program. The postconditions of a program are things that are true after the program has been executed. That is, they are things that are accomplished by the program. For an xTurtle program, the postconditions of the program include the picture that has been drawn on the screen.
The following picture shows a simple "staircase" with 5 steps and another staircase, with 4 steps, leaning at a 30 degree angle:
Suppose that you want a program to draw such staircases. Let's say that the number of steps in the staircase will be input by the user. You will have to use a loop to draw the steps, since when you are writing the program, you don't know how many steps there will be. Each execution of the loop will draw one of the staircase's steps. Before drawing each step, the turtle must be facing in the right direction; this is a precondition. After drawing the step, the turtle has changed direction; this is a postcondition. You have to include commands that will provide "splicing" from the actual postcondition to the desired precondition. After the loop, you will still have to draw the two long sides of the staircase. To get them into the correct positions and orientations, you will have to think about the postconditions that hold after the loop has been executed and how they match up with the preconditions for drawing the lines. Exercise 5 at the end of the lab asks you to write this program.
Subroutines
A subroutine is -- more or less -- a small program made into a black box and given a name. Some subroutines, such as forward and PenUp are predefined; others are written by a programmer as part of a larger program. Subroutines are an essential tool for organizing complex tasks.
Most subroutines have parameters such as the 9 in forward(9) or the 30 in turn(30). Parameters allow subroutines to receive information from the rest of the program or to send information back. Suppose that we want to turn the staircase program described above into a subroutine. Then it would no longer make sense to get the input from the user, since that would greatly limit the generality of the subroutine. Instead, the number of steps would probably be provided as a parameter. From the "point of view of the subroutine," the parameter is like input coming from "somewhere outside," just as input from the user comes from outside the program.
A subroutine definition begins with the word SUB and ends with the word END SUB. Just after the word SUB comes the name of the subroutine and (optionally) a list of one or more parameter names. The subroutine name and the parameters form the interface of the subroutine; everything from there up until the END SUB is the implementation.
The sample program "SpiralsSubroutine" defines a subroutine named spiral. Select this program from the pop-up menu at the top of the xTurtle applet, and read the program and comments. When you click the "Run Program" button to run this program, it will look like nothing has happened! But in fact, the effect of the program is to define the subroutine. Ordinarily, the computer has no idea what the word "spiral" means, but once the computer compiles the subroutine definition, it will then understand commands like spiral(61) and spiral(89). Such commands can be added to the program after the subroutine definition, or they can be entered into the text-input box below the drawing area in the xTurtle applet. Try it. Some of the pictures you can make are rather pretty! Parameter values close to 90, 120, 144, and 180 tend to make nuice pictures. Try spiral(143.5).
Exercises
These exercises are due next Friday, October 25. For Exercises 2, 3, and 4, you should save a program in your homework directory. In the lab report that you turn in, you should tell me the file names for your programs, and if you are working with someone, you should tell me whose directory to look in to find the program. You should turn in your answers to Exercises 1 and 5 on paper. You do not need to turn in programs for Exercise 1!
Exercise 1: Consider each of the pictures b), c), d), and e) in the nested squares illustration, shown above. For each of these incorrect versions (b through d), determine what small change in the program "NestedSquares" would produce that picture. In each case, it's a question of removing one or more statements from the end of the LOOP in the correct program, so that one or more of the required preconditions are not met. Determine which statement to remove in each case and what preconditions are unmet in the resulting programs. Report your answers.
Exercise 2: Write a program that can draw staircases, like those shown in the picture above. The program you write must meet the following requirements:
- The user will be asked to specify the number of steps.
- Each step is one unit high and one unit wide.
- The orientation of the staircase will depend on the starting orientation of the turtle, as shown in the second example in the picture. This means that you should draw the staircase using only forward, back, and turn commands. Do not use face or moveTo.
- After the staircase is drawn, the position and heading of the turtle will be the same as they were when the drawing begins. This is a postcondition for the program as a whole.
Start your program with the following three lines:
DECLARE NumberOfSteps
AskUser("How many steps?", NumberOfSteps)
DECLARE count
The variable named count should be used as a counting variable in a loop to count the number of steps that have been drawn. You should think about preconditions and postconditions as you write the program. Include comments in your program that discuss specific preconditions and postconditions for various parts of the program. It is a bit easier to write the program if you start drawing the steps at the top of the staircase.
Exercise 3: Convert the program you wrote for Exercise 2 into a subroutine. Start by removing the first two lines of the program, which were given to you in Exercise 2. Replace them with:
SUB stairs(NumberOfSteps)
Add the line
END SUB
at the end of your program. These two steps turn your staircase-drawing program into a staircase-drawing subroutine. After running the modified program, you will be able to use commands like stairs(5) to draw a staircase with five steps and turn(30) stairs(4) to draw a tilted staircase with four steps. To make a more interesting picture, add the following lines at the end of your modified program, after the definition of the subroutine, and then run the program:
LOOP
stairs(3)
stairs(5)
stairs(7)
turn(30)
EXIT IF heading = 0
END LOOP
What picture is drawn by one execution of the loop in this program? Why? (You will only get the correct picture if your solution to Exercise 2 meets the fourth requirement imposed on the program in that exercise.) What picture is drawn by the program as a whole? Why?
Exercise 4: Write a program to draw the following picture. There are ten lines. The lengths of the lines from top to bottom are 2, 4, 6, 8, 10, 12, 14, 16, 18, and 20, and the lines are two units apart. In order for the whole picture to be visible on the screen, the top line should be at y-coordinate 9.
Exercise 5: Explain carefully why running the sample program "SpiralsSubroutine" does not produce any output or have any visible effect. What exactly does the program do when it is executed? What is the point of it, if it doesn't do anything?