Make your own free website on Tripod.com

Discussion #8 - Iterative and Conditional Control Structures


A control structure is a way of altering the normal flow of a program. You know that the Interpreter normally translates the instructions in a procedure one after the other in sequential order from first to last. Control structures provide the means by which the Interpreter may alters this flow pattern under particular circumstances. Control structures enable a program to repeat certain instructions, to skip certain instructions, or to choose between alternate instructions. Each of these options is enabled by one of Logo's four control structures:

The iterative structure tells the Interpreter to repeat certain instructions before continuing with the rest of the program. There are two kinds of iterative structures - loops and tail recursive procedures.

The conditional structure, implemented by the primitive command if, tells the Interpreter to skip a particular list of instructions under certain circumstances.

The branch structure, implemented by the primitive command ifelse tells the Interpreter to execute either one list of instructions or another list of instructions, depending on the circumstances.

The recursive structure, like the iterative structure, tells the Interpreter to repeat certain instructions. But unlike iteration, recursion requires the Interpreter to store and re-use the results of each repetition.

In this unit you will learn how to use iterative and conditional structures. Unit #9 explains branch structures and Unit #10 explains recursive structures.

You are already familiar with one kind of iterative structure, the loop. A loop is implemented by the primitive repeat. Here are two examples of loops that you have already used:

repeat 4 [fd 30 rt 90]

repeat :times [pr "Hello!]

The effect produced by repeat is to execute the quoted instruction list over and over, as many times as required by the first input. Each time the instruction list is executed, we say that the program makes a pass through the loop. In the first example above, each pass draws one side and one angle of a square. In the second example, each pass prints 'Hello!' The value of the variable :TIMES determines how many Hello!'s will be displayed.

Loops are useful in solving problems that have these two characteristics: You know how often the list of instructions must be repeated to produce the desired effect. You know that each pass through the loop will produce exactly the same effect. In the first example, the effect of each pass was to draw a line and make a turn. In the second example, the effect of each pass was to print the word "HELLO!"

A loop structure has the form of a single repeat instruction within a defined procedure. The other kind of iterative structure, tail recursion, has the form of an entire defined procedure. Tail recursive procedures are useful in solving problems when the instructions you need to repeat are not quite the same for every pass. For this reason, I think of tail recursion as being as almost looping. Here is a tail recursive procedure that draws larger and larger squares. It is obviously repetitive in nature, like a loop, but the instructions that are repeated are not quite the same every time, Each new square is a little larger than the one before.

TO GROWBOX :SIZE
  repeat 4 [fd :size rt 90]
  growbox :size + 5
END
At first glance, this looks like an example of a superprocedure calling a subprocedure, because one of the instruction lines contains the name of a defined procedure. But growbox has two important characteristics that force the Interpreter to deal with it quite differently from a usual superprocedure-subprocedure situation: (1) The procedure being called has the same name as the procedure making the call. (2) The instruction that contains the call is the last instruction line of the procedure.  If the procedure had been a reporter, instead of a command like growbox, there would have been a third essential characteristic. We will deal with this in Unit #12: (3) If the procedure is a reporter, the expression containing the procedure call must provide an input directly to the op command.

These characteristics are what make this a tail recursive structure instead of the usual situation of a superprocedure calling a subprocedure. When the Interpreter reaches the last line of growbox, instead of looking around for a different procedure to run, the interpreter simply runs the the same procedure again, using the new input values. Because of the way the Interpreter responds, we refer to the last line of growbox as an iterative call. To run the iterative procedure above, you could type growbox 10 in the command center. The turtle will draw a set of boxes with sides of 10, 15, 20, 25, 30, and so on indefinitely. On the first pass through the iteration, the Interpreter executes the growbox procedure with an input of 10, provided by the variable :SIZE that was created when you typed 10 into the command center. After drawing a box measuring 10 turtlesteps on each side, the Interpreter reaches the iterative call instruction that tells it to repeat the same procedure with an input calculated by adding 5 to the original :SIZE. The new :SIZE variable has a value of 10 + 5, or 15. The interpreter now executes growbox 15, drawing a larger box measuring 15 turtlesteps on each side. When it reaches the last instruction, it does the same thing again: it repeats growbox with a new :SIZE calculated by adding 5 to 15. This process continues indefinitely; each execution of growbox draws a larger box.

Here is another example of a tail recursive procedure that draws a spiral:

TO SPIRAL :SIZE
  fd :size
  rt 120
  spiral :size + 3
END
You can see that the Interpreter will follow the same pattern in executing this procedure as it did for growbox. Each time it reaches the iterative call, the Interpreter calculates a new input value and executes spiral again. With each repetition, the spiral expands a little bit. The obvious problem with growbox and spiral is that they keep growing and spiralling indefinitely! You could stop the iterations from the keyboard by pressing <COMMAND/.> (holding down the COMMAND key while pressing the PERIOD key) or clicking on the command center's "S" box, but it would be much better to include a "stop rule" in the procedure itself.

That is where the conditional structure comes in. A conditional is a control structure that tells the Interpreter to execute an instruction list only if a particular test turns out to be true. The command if implements a conditional structure. if requires two inputs, an expression that outputs either the word 'true' or the word 'false', and a quoted list of instructions. The instruction list is executed only if the first input is the word 'true' If the first expression outputs 'false', the instruction list is ignored, and the Interpreter moves on to the next line of the procedure. Here is an example of a stop rule:

if :size > 100 [stop]
> is a reporter that outputs either the word 'true' or the word 'false', depending upon how the value of :SIZE compares to 100. As long as :SIZE is less than or equal to 100, the Interpreter ignores the stop command because the value of the expression :SIZE > 100 is the word 'false'. But as soon as :SIZE becomes larger than 100, the Interpreter passes the word 'true' to if, and if tells the Interpreter to execute the command stop. The effect of the command stop is to terminate execution of the procedure by telling the Interpreter to jump directly to the End line, skipping all the instructions in between.

Conditional structures may use any reporter that outputs the word 'true' or the word 'false', and may include any list of instructions to be executed. Reporters that output 'true' or 'false' are called test reporters. There are fourteen primitive test reporters in LogoWriter and, of course, you may define others if you need them. The conditional structure used in tail recursive procedures is called a stop rule because its function is to stop the procedure as soon as the controlling variable reaches a certain size. The stop rule is included as early as possible in the procedure, often as the first instruction. Stop rules are usually controlled by the test reporter greater than (>,) less than (<,) or equal to (=.) Like the other arithmetic reporters, these are infix procedures that require two numerical inputs, one preceding and one following the reporter.

Here are the two sample procedures, rewritten to include stop rules:

TO GROWBOX :SIZE
  if :size > 100 [stop]
  repeat 4 [fd :size rt 90]
  wait 10
  growbox :size + 5
END

TO SPIRAL :SIZE
  if or xcor > 240 ycor > 100 [stop]
  fd :size
  rt 120
  spiral :size + 5
END
 

The stop rule for the growbox procedure clicks in when the side of a square becomes greater than 100 turtlesteps. The wait instruction slows down the action to allow you to see what is happening. The stop rule for the spiral procedure is designed to keep the turtle from running off the screen. Since I did not know whether she would reach the top or the side first, I had to include both possibilities. or is a reporter that requires inputs from two test reporters. If either of the two test reporters outputs the word 'true', or passes 'true' back to if. However, if both test reporters output the word 'false', or passes 'false' back to if. LogoWriter has another primitive test reporter, and, which is similar in function to or. Like or, and requires inputs from two test reporters. and outputs the word 'true' if both test reporters output 'true'; otherwise, and outputs 'false'. The reporters xcor and ycor output the x-coordinate and the y-coordinate of the turtle, respectively. Here is another version of growbox that combines the stop rule and the recursive call in the same instruction line, and thereby eliminates the need for a stop command:
TO GROWBOX1 :SIZE
  if or :size < 100 :size = 100 [growbox :size + 5]
END
As long as the value of :SIZE is less than 100 or equal to 100, the Interpreter repeats growbox with larger and larger inputs. When :SIZE becomes larger than 100, the Interpreter ignores the quoted instruction list and moves on to the last line of the procedure. Tail recursive procedures may have more than one input, of course. They are frequently used as subprocedures, called by a superprocedure that supplies them with the starting values of their inputs.

Here is a more elaborate version of the spiral procedure that exemplifies this. When experimenting with this version, you should begin by altering only the side, keeping the angle constant by entering "0" in response to the fourth question. Later, you might want to experiment with changing angles only by entering "0" in response to the second question and a small number of degrees in response to the fourth question. When you experiment with spirals whose angle changes with each iteration, (:ANGLE.INC is not zero), it is helpful for the turtle to be visible so you can trace her path. Use the slowturtle command to help you trace her moves.

TO SPIRAL1
  cg
  ct
  ht
  pr [What starting length of side shall I use?]
  name rw "distance
  pr [How fast do you want the side to increase?]
  name rw "distance.inc
  pr [What starting angle shall I use?]
  name rw "angle
  pr [How fast do you want the angle to increase?]
  name rw "angle.inc
  if not :angle.inc = 0 [st]
  ct
  do.spiral1 :distance :angle
END

TO DO.SPIRAL1 :DISTANCE :ANGLE
  if :angle.inc = 0 [ if or xcor > 240 ycor > 100 [stop] ]
  fd :distance
  rt :angle
  do.spiral1 :distance + :distance.inc :angle + :angle.inc
END

Notice that the values of two of the global variables created by spiral1, :DISTANCE and :ANGLE, are used as the starting values for local variables when do.spiral1 is called. :DISTANCE and :ANGLE are included in the Title line of do.spiral1 to alert the Interpreter that it must create local variables before executing each version of do.spiral1. The initial values for these local variables are provided by spiral1 when it calls do.spiral1, and the values for the new variables created each time the subprocedure is repeated are provided by the iterative call instruction (the last instruction in the procedure.) The new values for :DISTANCE and :ANGLE are calculated by adding the amounts of increase to the present values of the variables.

Since the variables :DISTANCE.INC and :ANGLE.INC do not change, they remain global variables and so are not in-cluded in do.spiral1's Title line. The stop rule in do.spiral1 has been modified so that it only works when :ANGLE.INC is zero; otherwise, the stop rule is disabled and you will have to stop the procedure by hand. You will see the reason for this when you experiment with the procedure.

growbox and do.spiral illustrate tail recursive procedures that were "almost loops." Each box was a little bigger than its predecessor, and each segment of the spiral was a little longer than, or had a slightly different turning angle from, its predecessor. Tail recursive procedures are also used in cases where the repetitions are exactly the same, but where the number of repetitions is not known beforehand. Here is an example of this use of tail recursion. Before running the procedure, you could use setsh to give the turtle a costume from the shapes page.

TO DUPLICATE
  seth 90
  pd
  stamp
  pr [Another copy?]
  if rw = "no [stop]
  pu
  fd 20
  pd
  duplicate
END
In this example, the user's reply to the question 'Another copy?' determines the number of passes through the iterative procedure. As long as the output of the defined reporter rw is anything except the word 'no', the turtle continues to duplicate her shape on the page. The test reporter = compares its two inputs, and outputs 'true' if they are the same. = is able to compare two numbers, two words, or two lists. It does not look for differences in the use of upper and lower case letters.

These examples of tail recursive procedures have all been commands. In Unit #12 you will see that defined reporters may also be tail recursive.
 

Exploration #8

New Special Words

true The output of a test reporter when the test condition is true.

false The output of a test reporter when the test condition is false.
 

New Commands


if true.or.false.expression instruction.list Used to introduce a conditional control structure. If the test reporter outputs the word 'true' the Interpreter executes the list of instructions. If the test reporter outputs the word 'false', the Interpreter executes the next instruction in the procedure.

stop Directs the Interpreter to jump directly to the End line of the procedure, skipping all the instructions in between.
 

New Reporters

first number > second number Outputs 'true' if the first number is greater than the second; otherwise outputs 'false'.

first number < second number Outputs 'true' if the first number is less than the second; otherwise outputs 'false'.

first number, word, or list = second number, word, or list Outputs 'true' if the inputs have the same value; otherwise outputs 'false'.

or first true.or.false expression second true.or.false expression Outputs 'true if either test reporter outputs 'true'; otherwise outputs 'false'.

and first true.or.false expression second true.or.false expression Outputs 'true' if both test reporters output 'true'; otherwise outputs 'false'.

xcor Outputs the x-coordinate of the turtle's position.

ycor Outputs the y-coordinate of the turtle's position.
 

1. Experiment with the growbox procedure using different expressions to provide inputs for the iterative call.

2. Write a new shrinkbox procedure that draws smaller and smaller boxes, rather than larger and larger ones. How will the stop rule be different from that of growbox? How will the iterative call line be different?

3. Write procedures like growbox and shrinkbox that draw figures other than growing or shrinking squares. For example, how about growtri that draws triangles or shrinkhex that draws hexagons?

4. Write a procedure growstar based on one of the star designs you wrote in Exploration #4.

5. You can obtain interesting patterns by adding an instruction that turns the turtle a little to the left or right just before the iterative call line. Try this with different shapes of polygons and with different amounts of turn. You might even want to add a second variable to the Title line which permits you to input the turning angle for the turtle to use between each iteration. Try programming a slinky by using iterative circles!

6. Experiment with a procedure that draws larger and larger boxes which are concentric, that is, which have a common center point rather than a common corner. It might be easier to start drawing each box at the middle of one side rather than at a corner, so you could move the turtle a little to the left or right between drawing each box. Here is an instruction that draws a box starting in the middle of its left side:

repeat 4 [fd :side / 2 rt 90 fd :side / 2]
7. Write a procedure that draws a target, using concentric circles.

9. Try adding a new variable name, :COLOR, to the Title line of do.spiral and a starting value for this variable, 1, to the last instruction in spiral. Change the color of each iteration by adding :color + 1 to the recursive call instruction in do.spiral.