BFOIT - Introduction to Computer Programming

Iteration and Animation

Introduction

We worked our way through defining commands, a.k.a. procedures, in the last lesson so that our programs could be built in small, understandable pieces.  The smaller your programs are, the less you type, and the better chance your program will do what you want it to do.  In this lesson, you are going to learn about another powerful mechanism for writing smaller programs: iteration.

As you write more Logo programs, you will notice that to do certain things, your code repeats similar patterns.  Programming involves recognizing these patterns.  There are a few ways to reduce the number of duplicate instructions your programs contain.  Iteration is one which we cover in this lesson.

We'll end this lesson with an introduction to animation.  Animation is everywhere in the digital world.  In Appendix F there is a reference to the SolveMaze jLogo program which draws a maze and then solves it.  It shows off the solution via animation.  In this lesson you will learn how to perform simple animation.

Drawing a Circle, Step by Step, Point by Point

You may think that drawing a circle requires understanding some advanced mathematics like algebra, geometry or trigonometry - subjects which you may not have had in school yet.  Don't worry if you have little to no experience with any of these subjects.  We are going to get the turtle to draw a circle in this lesson.  We'll figure out how to do it the same way we solve many puzzles - start by working with things we know how to do.

Here are a couple of definitions of a circle:

     A closed plane curve every point of which is equidistant
     from a fixed point within the curve.
     (Webster's New Collegiate Dictionary).
     
     A circle is the set of all points in a plane at a fixed
     distance from a fixed point in the plane.
     (www.math.psu.edu)
			

Over the past two lessons you have been exposed to two different ways in which you can approach writing a program.  One method is to first write pseudocode.  Let's look at some pseudocode that instructs the turtle to draw a bunch of points that are all the same distance from the center of the TurtleSpace.

  1. pick up the pen so it's not leaving a trace,
  2. move some number of steps forward, for example: 100,
  3. put the pen down so it will draw,
  4. move a few steps forward to make a little mark,
  5. pick up the pen so it's not leaving a trace,
  6. return to the original position,
  7. turn a bit to the right, and
  8. repeat steps 1 through 7 until the turtle is back to its original heading - until it has rotated 360 degrees.

The alternative is to extend Logo's set of primitive procedures, creating our own new pieces providing higher level utilities.  Each piece is implemented by defining a new procedure.  The name of the new procedure is an abbreviated form of pseudocode; it needs to be carefully chosen to reflect what the new procedure does. 

Taking this approach, let's define a new procedure named pointOut100. It should draw a point 100 turtle steps outward (forward on the current heading) from the turtle's current position.

Ok, use the pseudocode description above to write your own version of pointOut100. and use it.  Get something working...  Here's the TG applet.

alt="Your browser understands the <APPLET> tag but isn't running the applet, for some reason." Your browser is completely ignoring the <APPLET> tag! TG - TurtleGraphics Applet

Tip: The left mouse button can be used to change the heights of the TurtleSpace, the CommandCenter, and the Editor.  Hold the left mouse button down while on the name stripe between these subwindows and drag it up/down.

Tip: When you press the up-arrow key while you are working in the CommandCenter, it brings up the previous line of input.  Press it again and you will get the line before this.  This continues until some maximum number of saved lines is reached.  Once you've nailed down the code that draws a point and rotates the turtle, you can put all of these instructions on a single line and repeat it using the up-arrow.

I think what you will find is that either approach works, but it is going to take a lot of typing.  A LOT of typing.  Too much typing.  If you decided to to take the procedural abstraction approach you learned in the last lesson, you had to do a lot less typing.  Here's how I approached the exercise, showing what I mean.

   ; draw a solid box with sides that are 30 turtle steps long
   ; its center is 100 turtle steps out from the current location   
   to pointOut100
     setpensize 30
     penup forward 85
     pendown forward 30
     penup back 115
     end 

Then in the CommandCenter, I entered the line of instructions:

   pointOut100 right 20    

a bunch of times, 18 times to be exact (18 times 20 degrees = 360 degrees).

There is one command in this source code that you may not have used yet, setpensize.  It was mentioned in the Exploration - Additional Commands section of the Commanding a Turtle lesson.  setpensize takes an integer as an input and sets the width of the line drawn by the pen to be this number of turtle steps.  By setting the width of the pen to 30 steps and using it to draw a line 30 steps long, I get a big solid colored box - a BIG point!

Walking in a Circle


      Let us imagine, then, as I have seen a hundred times, a
      child who demands: How can I make the Turtle draw a circle?
      The instructor in a LOGO environment does not provide
      answers to such questions but rather introduces the child
      to a method for solving not only this problem but a large
      class of others as well.  This method is summed up in the
      phrase "play Turtle."  The child is encouraged to move his
      or her body as the Turtle on the screen must move in order
      to make the desired pattern.  For the child who wanted to
      make a circle, moving in a circle might lead to a descrip-
      tion such as: "When you walk in a circle you take a little
      step forward and you turn a little. And you keep doing it."
      From this description it is only a small step to a formal
      Turtle program.
			  (Seymour Papert, in "Mindstorms")

			

A principal idea behind the creation of Logo was to embed a student in an environment in which they can explore for solutions.  Seymour wanted students to learn mathematics by spending time in Mathland.  Rather than learning concepts by doing problems from some textbook, students would learn concepts by exploring them in a virtual world, a Mathland.  In the quoted paragraph above, students would discover how to make the turtle draw a circle by physically acting out the process themselves and then translating this into Logo instructions for the turtle.

You can think of the description of the process of walking in a circle, take a little step forward and turn a little, as pseudocode.  Use the TG application if you have it or go back up to the TG applet to convert this pseudocode into Logo instructions.  Experiment with different distances to move forward as well as different amounts of turning right or left.  Go play in Mathland.  Do not continue reading on until you have instructed the turtle to draw a few circles.

What may have appeared to be a game was actually some serious exploration of mathematics.  What I wanted you to discover, or verify if you already knew a bit about geometry, is that you can get the turtle to draw a circle by moving forward in increments as you also turn right or left in increments.  To complete the circle, the sum of all the amounts you turned the turtle must add up to 360 degrees.  Did you enter a symmetrical series of instructions something like the following?

   fd 30 rt 30   fd 30 rt 30   fd 30 rt 30   fd 30 rt 30   
   fd 30 rt 30   fd 30 rt 30   fd 30 rt 30   fd 30 rt 30
   fd 30 rt 30   fd 30 rt 30   fd 30 rt 30   fd 30 rt 30 

If you didn't, try them out now.  There are two crucial, distinctive elements to this list of instructions.

  1. All of the forward instructions had the same distance and all of the right instructions had rotations of the same amount.
  2. Since the amount rotated in each right instruction was 30 (degrees), the list of instructions consisted of exactly 12 pairs of forward and right instructions - 12 times 30 equals 360.

What is actually drawn is a regular dodecagon - a 12-sided regular polygon.  Regular polygons and circles have a very interesting history, dating back over 2,200 years!  Archimedes used the geometry of regular polygons to estimate π (Pi), the ratio of the circumference of a circle to its diameter.  Archimedes knew how to compute the perimeter of a regular polygon and noticed that the more sides a regular polygon had, the closer is was to being a circle.  To see this for yourself, click here to go to a webpage that covers regular polygons.

alt="Your browser understands the <APPLET> tag but isn't running the applet, for some reason." Your browser is completely ignoring the <APPLET> tag! Regular Polygons Applet

So let's take advantage of this convergence of many-sided regular polygons and a circle and define a new command that draws a 36-sided regular polygon.  Luckily, the Editor has copy & paste.

   to reg36gon
     fd 15 rt 10   fd 15 rt 10   fd 15 rt 10   fd 15 rt 10   
     fd 15 rt 10   fd 15 rt 10   fd 15 rt 10   fd 15 rt 10
     fd 15 rt 10   fd 15 rt 10   fd 15 rt 10   fd 15 rt 10
     fd 15 rt 10   fd 15 rt 10   fd 15 rt 10   fd 15 rt 10
     fd 15 rt 10   fd 15 rt 10   fd 15 rt 10   fd 15 rt 10
     fd 15 rt 10   fd 15 rt 10   fd 15 rt 10   fd 15 rt 10
     fd 15 rt 10   fd 15 rt 10   fd 15 rt 10   fd 15 rt 10
     fd 15 rt 10   fd 15 rt 10   fd 15 rt 10   fd 15 rt 10
     fd 15 rt 10   fd 15 rt 10   fd 15 rt 10   fd 15 rt 10
     end 

And... you have what looks like a reasonable circle.  And you've achieved this with what started out as an observation of how you would walk in a circle.  But with the Logo programming environment, you were able to explore this concept.  And in the process, either you learned a bit more about math (geometry), or at least visualized what you already knew.

Summary of Drawing a Circle

You should now know two ways to get the turtle to draw a circle in the Logo programming language.  A problem with both approaches is that they take a LOT of typing.  And what you are typing is a lot of the same stuff, over, and over.

The first way we approached the problem required drawing points some distance from the center of the circle.  If you think back about what we did in this approach, you will see that if we draw one point for each degree in a circle; it will take 2,161 instructions.  If you define the command pointOut100, you reduce your program to 2 times the number of points that are drawn.  So if we want a circle drawn as a thin line, we would probably need to draw at least 360 point, requiring 720 instructions.

Our second approach was much shorter, but still contained a lot of redundant instructions.  reg36gon contained 36 pairs of identical forward and right instructions.

There's got to be a better way...

And there is... it's called iteration.

Iteration, aka Repeating Something

In the Summary section of the "Commanding a Turtle" lesson, I emphasized that the sequence that the steps in our programs get done in is extremely important.  In the TG applet (or TG application), when you are working in the CommandCenter, instructions (the steps in your program) are executed left to right on each line after you press the [Enter] key.

Well, Logo has a way for you to tell the interpreter to execute of a list of instructions a number of times.  The syntax of the Logo repeat command is:

   repeat       <number>       <List-of-Instructions>   

  1. the command name: "repeat"
  2. a <number>, and
  3. a <List-of-Instructions>

And, the syntax of a <List-of-Instructions> is:

   [       <Instructions>       ]   

  1. an open square bracket,
  2. <Instructions>, and
  3. a close square bracket

For example, here are repeat instructions which draw regular polygons:

   repeat       3       [       forward 100   right 120       ]   
   repeat       4       [       forward 90   right 90       ]   
   repeat       5       [       forward 80   right 72       ]   
   repeat       6       [       forward 70   right 60       ]   
Table 5.1

The initial version of reg36gon is now down to

   to reg36gon
     repeat 36 [forward 15 right 10]   
     end 

Logo Animation - Watching Iteration

IterationAnimated Figure 5.1

Here is an applet that demonstrates the execution of a small program which draws a circle the way I first described. If you are having any trouble visualizing how the repeat command works, go watch it...

Animation - Moving an Object Around TurtleSpace

Writing a program that does some sort of animation is actually easy now that we have the repeat command.  Use the TG application if you have it or go back up to the TG applet and enter the following:

   home clean hideturtle setpensize 20 setpencolor 2
   repeat 25 [ fd 20 wait 500 setc 7 bk 20 fd 10 setc 2 ]    

So, moving a 20x20 turtle-step box up the screen is just iteration of drawing the box, erasing the box, moving.

But... notice the new command in the repeated list of instructions - WAIT.  It has an input, a number, the amount of time to wait before the next command is executed.

Take out the wait instruction and see what happens.  Put it back in and vary the size of its input number.  This number specifies the amount of time in milliseconds (1/1000s of a second) to wait. 

Simple animation consists of the steps:

  1. draw an object,
  2. pause for some amount of time,
  3. erase all or part of what was drawn (often by drawing it again in the same color as the background),
  4. move a bit, and
  5. go back to step 1.

Practice: Jumpin Jack or Jill

Ok.  Figure 5.2 shows three different positions of a stick figure performing a common exercise.

#1
#2
#3
Figure 5.2

Here is part of the source code including everything for drawing JumpinJack #1.

   ; draw two arms raised above the head
   ; turtle is expected to be at the center of the body
   to arms1
     setpensize 8
     forward 5
     right 45 forward 50 back 50
     left 90 forward 50 back 50
     right 45
     back 5
     end

   ; draw a stick figure body (80 turtlesteps in height)
   ; turtle should be at centerpoint of the body
   to body
     pendown
     setpensize 16
     forward 40 back 80 forward 40
     end

   ; draw a head at the top of the body
   ; turtle should be at centerpoint of the body
   to head
     forward 25
     setpensize 10
     repeat 12 [forward 16 back 16 left 30]
     back 25
     end

   ; draw legs of stick figure (legs spread wider than shoulders)
   ; turtle is expected to be at the center of the body
   to legs1
     setpensize 8
     back 35
     right 135 forward 60 back 60
     right 90 forward 60 back 60
     left 225
     forward 35
     end

   ; draw a stick figure with arms above head and legs spread out
   ; turtle should be at centerpoint
   to fig1
     body
     head
     arms1
     legs1
     end

   ; animate a stick figure as if it's doing jumping jacks exercise   
   to main
     hideturtle home clean setheading 0
     repeat 10 [ fig1 ]
     end

   main 

It's up to you to write commands: arms2, legs2, fig2, arms3, legs3, fig3 and then modify main such that it iterates through the three figures to animate Jack, or is it Jill???

Tip: If you decide to copy&paste arms1 as a prototype for arms2 and arms3, make sure to change everything that needs to be changed.  This means reading the code carefully...  This applies to the legs and fig commands as well.  If any of the commands are confusing to you, play with them out in the CommandCenter to see what they do.

Tip: When you have everything you need for figure #2, test out your fig2 command by typing its name in the CommandCenter.  The great thing about working in an interpreted language is that you can try all sorts of things out, without modifying your program to get the desired effects.  Figure 5.3 shows how I tested me program during its development.  Look carefully at what I entered in the CommandCenter and what the graphic results were.

Test JumpinJack Figure 5.3

Practice: Additional Projects

Back in the exercises at the end of lesson 2, you were asked to draw a pair of axes like shown in Figure 5.4.  Now that you know how to define new commands and use the repeat command, you should be able to write a much smaller version of this program. 

Axes Figure 5.4

Take a look at the circular arc in Figure 5.5a.  This particular arc is one quarter of a circle.  You've learned how to draw a circle in this lesson, so write a new command named drawArc which instructs the turtle to draw a circular arc that is a quarter of a circle in length.  Then, use your drawArc command to write another new command named petal which draws something that looks like Figure 5.5b.

Now take a close look at the plant with a flower in Figure 5.5c..  Use your new commands to draw the flower.  Then, expand your program to draw the stem and the leaf - completing a plant with a flower.

a. Arc
b. Dual Arcs
c. Plant With Flower
Figure 5.5

Write a bunch of new versions of drawArc (named drawRedArc, drawOrangeArc, etc...) that cover half of a circle, 180 degrees.  Each should be colored representing a band of a rainbow.  Then write a main procedure that puts a rainbow together.

Rainbow
Figure 5.6

Checkout the brick wall drawn in Figure 5.7.  Write two new commands, procedures which instruct the turtle to draw a brick and a half-brick.  Use these new commands to draw the brick wall. 

Warning: this is a bit tricky :)

Figure 5.7

Trickier still... how about drawing a house with a brick front!

Figure 5.8

Summary

Iteration - repeating something some number of times - is a powerful way to reduce the size of a computer program as well as making the purpose of the code more obvious.  The repetition may not be obvious when you start writing a program; the something that gets repeated can be a pattern you only recognize when you are typing in your program.  So, look closely for patterns in the code you write.  As you get more and more experience writing programs, you'll start to think about iteration as a basic building block of programming.

If you found the topic of regular polygons interesting and want to learn more about their relationship to circles and π and/or how Archimedes estimated the value of π, go to the library and checkout pages 23-32 of William Dunham's book The Mathematical Universe.

Logo Primitive Procedures
Introduced in This Lesson

Command Inputs Description Example
REPEAT count
instructionList
The instructionList input is performed the number of times specified by the count input. REPEAT 4 [ FD 100 RT 90 ]
WAIT number Execution of instructions is suspended for the number of milliseconds (1/1000s of a second). WAIT 1000
Table 5.2


Back to Adding Commands
Go to the Table of Contents
On to Hierarchical Structure

Public Domain Mark
This work (BFOIT: Introduction to Computer Programming, by Guy M. Haas),
identified by Berkeley Foundation for Opportunities in IT (BFOIT),
is free of known copyright restrictions.