diff options
| author | elioat <elioat@tilde.institute> | 2023-08-23 07:52:19 -0400 |
|---|---|---|
| committer | elioat <elioat@tilde.institute> | 2023-08-23 07:52:19 -0400 |
| commit | 562a9a52d599d9a05f871404050968a5fd282640 (patch) | |
| tree | 7d3305c1252c043bfe246ccc7deff0056aa6b5ab /js/games/nluqo.github.io/~bh/v1ch10/v1ch10.html | |
| parent | 5d012c6c011a9dedf7d0a098e456206244eb5a0f (diff) | |
| download | tour-562a9a52d599d9a05f871404050968a5fd282640.tar.gz | |
*
Diffstat (limited to 'js/games/nluqo.github.io/~bh/v1ch10/v1ch10.html')
| -rw-r--r-- | js/games/nluqo.github.io/~bh/v1ch10/v1ch10.html | 790 |
1 files changed, 790 insertions, 0 deletions
diff --git a/js/games/nluqo.github.io/~bh/v1ch10/v1ch10.html b/js/games/nluqo.github.io/~bh/v1ch10/v1ch10.html new file mode 100644 index 0000000..6759b7f --- /dev/null +++ b/js/games/nluqo.github.io/~bh/v1ch10/v1ch10.html @@ -0,0 +1,790 @@ +<HTML> +<HEAD> +<TITLE>Computer Science Logo Style vol 1 ch 10: Turtle Geometry</TITLE> +</HEAD> +<BODY> +<CITE>Computer Science Logo Style</CITE> volume 1: +<CITE>Symbolic Computing</CITE> 2/e Copyright (C) 1997 MIT +<H1>Turtle Geometry</H1> + +<TABLE width="100%"><TR><TD> +<IMG SRC="../csls1.jpg" ALT="cover photo"> +<TD><TABLE> +<TR><TD align="right"><CITE><A HREF="http://www.cs.berkeley.edu/~bh/">Brian +Harvey</A><BR>University of California, Berkeley</CITE> +<TR><TD align="right"><BR> +<TR><TD align="right"><A HREF="../pdf/v1ch10.pdf">Download PDF version</A> +<TR><TD align="right"><A HREF="../v1-toc2.html">Back to Table of Contents</A> +<TR><TD align="right"><A HREF="../v1ch9/v1ch9.html"><STRONG>BACK</STRONG></A> +chapter thread <A HREF="../v1ch11/v1ch11.html"><STRONG>NEXT</STRONG></A> +<TR><TD align="right"><A HREF="https://mitpress.mit.edu/books/computer-science-logo-style-second-edition-volume-1">MIT +Press web page for Computer Science Logo Style</A> +</TABLE></TABLE> + +<HR> + +<P> +Logo is best known as the language that introduced the <EM>turtle</EM> +as a tool for computer graphics. In fact, to many people, Logo and +turtle graphics are synonymous. Some computer companies have +gotten away with +selling products called "Logo" that provided nothing <EM>but</EM> +turtle graphics, but if you bought a "Logo" that provided only the +list processing primitives we've used so far, you'd probably feel +cheated. + +<P>Historically, this idea that Logo is mainly turtle graphics is a +mistake. As I mentioned at the beginning of Chapter 1, Logo's name +comes from the Greek word for <EM>word,</EM> because Logo was first +designed as a language in which to manipulate language: words and +sentences. Still, turtle graphics has turned out to be a very +powerful addition to Logo. One reason is that any form of computer +graphics is an attention-grabber. But other programming languages had +allowed graphics programming before Logo. In this chapter we'll look +at some of the reasons why <EM>turtle</EM> graphics, specifically, was +such a major advance in programming technology. + +<P>This chapter can't be long enough to treat the possibilities of +computer graphics fully. My goal is merely to show you that the same +ideas we've been using with words and lists are also +fruitful in a very different problem domain. Ideas like locality, +modularity, and recursion appear here, too, although sometimes in +different guises. + +<P><H2>A Review, or a Brief Introduction</H2> + +<P>I've been assuming that you've already been introduced to Logo turtle +graphics, either in a school or by reading Logo +tutorial books. If not, perhaps +you should read one of those books now. But just in case, here is a +very brief overview of the primitive procedures for turtle graphics. +Although some versions of Logo allow more than one turtle, or allow +<EM>dynamic</EM> turtles with programmable shapes and speeds, for now +I'll only consider the traditional, single, static turtle. + +<P>Type the command <CODE>cs</CODE> (short for <CODE>clearscreen</CODE>), with no +inputs. The effect of this command is to initiate Logo's graphics +capability. A turtle will appear in the center of a graphics window. +(Depending on which version of Logo you have, the turtle may look like an +actual animal with a head and four legs or--as in Berkeley Logo--it may be +represented as a triangle.) The turtle will be facing toward the top of the +screen. Any previous graphic drawing will be erased from the screen and +from the computer's memory. + +<P>The crucial thing about the turtle, which distinguishes it from other +metaphors for computer graphics, is that the turtle is pointing in a +particular direction and can only move in that direction. (It can +move forward or back, like a car with reverse gear, but not sideways.) +In order to draw in any other direction, the turtle must <EM>first</EM> +turn so that it is facing in the new direction. (In this respect it +is unlike a car, which must turn and move at the same time.) + +<P>The primary means for moving the turtle is the <CODE>forward</CODE> command, +abbreviated <CODE>fd</CODE>. <CODE>Forward</CODE> takes one input, which must be a +number. The effect of <CODE>forward</CODE> is to move the turtle in the +direction it's facing, through a distance specified by the input. The +unit of distance is the "turtle step," a small distance that depends +on the resolution of your computer's screen. (Generally, one turtle +step is the smallest line your computer can draw. This is +slightly oversimplified, though, because that smallest distance may be +different in different directions. But the size of a turtle step does +<EM>not</EM> depend on the direction; it's always the same distance for +any given computer.) Try typing the command + +<P><TABLE><TR><TD> +<PRE> +forward 80 +</PRE><TD valign="center"><IMG SRC="fd80.gif" ALT="turtle figure"></TABLE> + +<P>Since the turtle was facing toward the top of the screen, +that's the way it moved. The turtle should now be higher on the +screen, and there should be a line behind it indicating the path +that it followed. + +<P>The first turtles were actual robots that rolled along the floor. +They got the name "turtle" because of the +hard shells surrounding their delicate electronic innards. A robot +turtle has a pen in its belly, which it can push down to the floor, or +pull up inside itself. When the pen is down, the turtle draws a trace +of its motion along the floor. + +<P> +<P>When talking about the screen turtle, it's customary to think of the +screen as a kind of map, representing a horizontal floor. Therefore, +instead of referring to the screen directions as "up," "down," +"left," and "right," we talk about the compass headings North, +South, West, and East. Your turtle is now facing North. Besides +fitting better with the turtle metaphor, this terminology avoids a +possible confusion: the word "left" could mean either the <EM> +turtle's</EM> left or the <EM>screen's</EM> left. (They're the same +direction right now, but they won't be the same after we turn the +turtle.) To avoid this problem, we use "West" for the left edge of +the screen, and reserve the word "left" for the direction to the +left of whichever way the turtle is facing. + +<P>Logo provides primitive commands to raise and lower the turtle's pen. +The command <CODE>penup</CODE> (abbreviated <CODE>pu</CODE>) takes no inputs; its +effect is to raise the pen. In other words, after you use this +command, any further turtle motion won't draw lines. Try it now: + +<P><TABLE><TR><TD> +<PRE>penup +forward 30 +</PRE><TD valign="center"><IMG SRC="https://people.eecs.berkeley.edu/~bh/v1ch10/pufd30.gif" ALT="turtle figure"></TABLE> + +<P>Similarly, the command <CODE>pendown</CODE> (<CODE>pd</CODE>) takes no +inputs, and lowers the pen. Here's a procedure you can try: + +<P><TABLE><TR><TD> +<PRE>to dash :count +repeat :count [penup forward 4 pendown forward 4] +end + +? <U>clearscreen dash 14</U> +</PRE> +<TD valign="center"><IMG SRC="dash14.gif" ALT="turtle figure"></TABLE> + +<P>The command <CODE>back</CODE> (or <CODE>bk</CODE>) takes one input, which must be a +number. The effect of <CODE>back</CODE> is to move the turtle backward by +the distance used as its input. (What do you think <CODE>fd</CODE> and <CODE> +bk</CODE> will do if you give them noninteger inputs? Zero inputs? +Negative inputs? Try these possibilities. Then look up the commands +in the reference manual for your version of Logo and see if the +manual describes the commands fully.) + +<P>To turn the turtle, two other commands are provided. <CODE>Left</CODE> +(abbreviated <CODE>lt</CODE>) takes one input, which must be a number. Its +effect is to turn the turtle toward the <EM>turtle's</EM> own left. +The angle through which the turtle turns is the input; angles are +measured in degrees, so +<CODE>left 360</CODE> +will turn the turtle all the way around. (In other words, that +instruction has no real effect!) Another way of saying that the turtle +turns toward its own left is that it turns <EM>counterclockwise.</EM> +The command <CODE>right</CODE> (or <CODE>rt</CODE>) is just like <CODE>left</CODE>, except +that it turns the turtle clockwise, toward its own right. + +<P>»Clear the screen and try this, the classic beginning point of Logo +turtle graphics: + +<P><PRE>repeat 4 [forward 100 right 90] +</PRE> + +<P>This instruction tells Logo to draw four lines, each 100 +turtle steps long, and to turn 90 degrees between lines. In other +words, it draws a square. + +<P>There are many more turtle procedures provided in Logo, but these are +the fundamental ones; with them you can go quite far in generating +interesting computer graphics. If you haven't had much experience +with turtle graphics before, you might enjoy spending some time +exploring the possibilities. There are many introductory Logo +turtle graphics books to help you. Because that part of Logo +programming is so thoroughly covered elsewhere, I'm not going to +suggest graphics projects here. Instead I want to go on to consider +some of the deeper issues in computer programming that are +illuminated by the turtle metaphor. + +<P><H2>Local vs. Global Descriptions</H2> + +<P>Earlier we considered the difference between <EM>local</EM> variables, +which are available only within a particular procedure, and <EM> +global</EM> variables, which are used throughout an entire project. +I've tried to convince you that the use of local variables is a much +more powerful programming style than one that relies on global +variables for everything. For one thing, local variables are +essential to make recursion possible; in order for a single procedure +to solve a large problem and a smaller subproblem simultaneously, each +invocation of the procedure must have its own, independent variables. +But even when recursion is not an issue, a complex program is much +easier to read and understand if each procedure can be understood +without thinking about the context in which it's used. + +<P>The turtle approach to computer graphics embodies the same principle of +locality, in a different way. The fact that the turtle motion +commands (<CODE>forward</CODE> and <CODE>back</CODE>) and the turtle turning commands (<CODE> +left</CODE> and <CODE>right</CODE>) are all <EM>turtle-relative</EM> means that a +graphics procedure need not think about the larger picture. + +<P>To understand what that means, you should compare the turtle metaphor +with the other metaphor that is commonly used in computer +graphics: <EM>Cartesian coordinates.</EM> This metaphor +comes from analytic geometry, +invented by Rene Descartes +(1596-1650). The word "Cartesian" is derived from his +name. Descartes' goal was to use the techniques of algebra in solving +geometry problems by using <EM>numbers</EM> to describe <EM>points.</EM> +In a two-dimensional plane, like your computer screen, you need two +numbers to identify a point. These numbers work like longitude and +latitude in geography: One tells how far the point is to the left +or right and the other tells how high up it is. + +<P><CENTER><IMG SRC="cartesian.gif" ALT="figure: cartesian"></CENTER> + +<P> +This diagram shows a computer screen with a grid of horizontal and +vertical lines drawn on it. The point where the two heavy lines meet +is called the <EM>origin;</EM> it is represented by the numbers +<CODE>[0 0]</CODE>. For other points the first number (the <EM> +x-coordinate</EM>) is the horizontal distance from the origin to the +point, and the second number (the <EM>y-coordinate</EM>) is the +vertical distance from the origin to the point. A positive +x-coordinate means that the point is to the right of the origin; a +negative x-coordinate means that the point is to the left of the +origin. Similarly, a positive y-coordinate means that the point is +above the origin; a negative y-coordinate puts it below the origin. +Logo does allow you to refer to points by their Cartesian coordinates, +using a list of two numbers. The origin is the point where the turtle +starts when you clear the screen. + +<P>The primary tool for Cartesian-style graphics in Logo is the command +<CODE>setpos</CODE> (for <CODE>set</CODE> <CODE>pos</CODE>ition). <CODE>Setpos</CODE> +requires one input, which must be a list of two numbers. Its effect +is to move the turtle to the point on the screen at those +coordinates. If the pen is down, the turtle draws a line as it moves, +just as it does for <CODE>forward</CODE> and <CODE>back</CODE>. Here is how you +might draw a square using Cartesian graphics instead of turtle +graphics: + +<P><PRE>clearscreen +setpos [0 100] +setpos [100 100] +setpos [100 0] +setpos [0 0] +</PRE> + +<P>Do you see why I said that the Cartesian metaphor is global, like the +use of global variables? Each instruction in this square takes into +account the turtle's position within the screen as a whole. The +"point of view" from which we draw the picture is that of an +observer standing above the plane looking down on all of it. This +observer sees not only the turtle but also the edges and center of +the screen as part of what is relevant to drawing each line. By +contrast, the turtle geometry metaphor adopts the point of view of the +turtle itself; each line is drawn without regard to where the turtle +is in global terms. + +<P>Using the turtle metaphor, we can draw our square (or any other figure +we can program) anywhere on the screen at any orientation. First +I'll write a <CODE>square</CODE> command: + +<P><PRE>to square :size +repeat 4 [forward :size right 90] +end +</PRE> + +<P>Now here's an example of how <CODE>square</CODE> can be used in +different positions and orientations: + +<P><TABLE><TR><TD> +<PRE>to face +pendown square 100 +penup forward 20 +right 90 +forward 25 +pendown forward 50 +penup back 75 +left 90 +forward 65 +right 90 +forward 20 +pendown square 15 +penup forward 45 +pendown square 15 +penup back 15 +right 90 +forward 20 +left 45 +pendown square 20 +end +</PRE><TD><IMG SRC="https://people.eecs.berkeley.edu/~bh/v1ch10/face.gif" ALT="turtle figure"></TABLE> + +<P>The head and the eyes are upright squares; the nose is a +square at an angle (a diamond). To write this program using Cartesian +graphics, you'd have to know the absolute coordinates of the corners +of each of the squares. To draw a square at an unusual angle, you'd +need trigonometry to calculate the coordinates. + +<P> + +<P>»Here is another demonstration of the same point. Clear the screen and +type this instruction: + +<P><PRE>repeat 20 [pendown square 12 penup forward 20 right 18] +</PRE> + +<P>You'll see squares drawn in several different orientations. +This would not be a one-line program if you tried to do it using the +Cartesian metaphor! + +<P> + +<P> +<H2>The Turtle's State</H2> + +<P>From a turtle's-eye point of view, drawing an upright square is the +same as drawing a diamond. It's only from the global point of view, +taking the borders of the screen into account, that there is a +difference. + +<P>From the global point of view how can we think about that +difference? How do we describe what makes the same procedure +sometimes draw one thing (an upright square) and sometimes another (a +diamond)? The answer, in the most general terms, is that the result +of the <CODE>square</CODE> command depends on the past <EM>history</EM> of the +turtle--its twists and turns before it got to wherever it may be +now. That is, the turtle has a sort of memory of past events. + +<P>But what matters is not actually the turtle's entire past history. +All that counts is the turtle's current <EM>position</EM> and its +current <EM>heading,</EM> no matter how it got there. Those two things, +the position and the heading, are called the turtle's <EM>state.</EM> +It's a little like trying to solve a Rubik's Cube; you may have turned +part of the cube 100 times already, but all that counts now is the +current pattern of colors, not how you got there. + +<P>I've mentioned the <CODE>setpos</CODE> command, which sets the turtle's +position. There is also a command <CODE>setheading</CODE> (abbreviated +<CODE>seth</CODE>) to set the +heading. <CODE>Setheading</CODE> takes one input, a number. The effect is to turn +the turtle so that it faces toward the compass heading specified by +the number. Zero represents North; the heading is measured in degrees +clockwise from North. (For example, East is 90; West is 270.) The +compass heading is different from the system of angle measurement used +in analytic geometry, in which angles are measured counterclockwise +from East instead of clockwise from North. + +<P>In addition to commands that set the turtle's state, Logo provides +operations to find out the state. pos<CODE>Pos</CODE> is an operation +with no inputs. Its output is a list of two numbers, representing the +turtle's current position. heading<CODE>Heading</CODE> is also an +operation with no inputs. Its output is a number, representing the turtle's +current heading. + +<P>Remember that when you use these state commands and operations, you're +thinking in the global (Cartesian) style, not the local (turtle) +style. Global state is sometimes important, just as global variables +are sometimes useful. If you want to draw a picture containing three +widgets, you might use <CODE>setpos</CODE> to get the turtle into position +for each widget. But the <CODE>widget</CODE> procedure, which draws each +widget, probably shouldn't use <CODE>setpos</CODE>. (You might also use +<CODE>setpos</CODE> extensively in a situation in which the Cartesian +metaphor is generally more appropriate than the turtle metaphor, like +graphing a mathematical function.) As in the case of global +variables, you'll be most likely to overuse global graphics style if +you're accustomed to BASIC computer graphics. A good rule of +thumb, if you're doing something turtleish and not graphing a function, is +that you shouldn't use <CODE>setpos</CODE> with the pen down. + +<P>»Do you see why? + +<P> +<H2>Symmetry</H2> + +<P>Very young children often begin playing with Logo simply by moving the +turtle around at random. The resulting pictures usually don't look +very interesting. You can recapture the days of your youth by +alternating <CODE>forward</CODE> and <CODE>right</CODE> commands with arbitrary inputs. +Here is a sample, which I've embodied in a procedure: + +<P><TABLE><TR><TD> +<PRE>to squiggle +forward 100 +right 135 +forward 40 +right 120 +forward 60 +right 15 +end +</PRE><TD valign="center"><IMG SRC="squiggle.gif" ALT="turtle figure"> +</TABLE> + +<P>This isn't a very beautiful picture. But +something interesting happens when you keep squiggling repeatedly: + +<P><TABLE><TR><TD> +<PRE>repeat 20 [squiggle] +</PRE><TD valign="center"><IMG SRC="https://people.eecs.berkeley.edu/~bh/v1ch10/squiggle4.gif" ALT="turtle figure"></TABLE> + +<P>Instead of filling up the screen with hash, the turtle draws +a symmetrical shape and repeats the same path over and over! Let's +try another example: + +<P><TABLE><TR><TD> +<PRE>to squaggle +forward 50 +right 150 +forward 60 +right 100 +forward 30 +right 90 +end +</PRE><TD valign="center"><IMG SRC="squaggle.gif" ALT="turtle figure"> +</TABLE> + +<P><CODE>Squiggle</CODE> turns into a sort of fancy square when you repeat it; +<CODE>squaggle</CODE> turns into an 18-pointed pinwheel. Does every possible +squiggle produce a repeating pattern this way? Yes. Sometimes you +have to <CODE>repeat</CODE> the procedure many times, but essentially any +combination of <CODE>forward</CODE> and <CODE>right</CODE> commands will eventually retrace +its steps. (There's one exception, which we'll talk about shortly.) + +<P>To see why repetition brings order out of chaos, we have to think +about a simpler Logo graphics procedure that is probably very +familiar to you: + +<P><PRE>to poly :size :angle +forward :size +right :angle +poly :size :angle +end +</PRE> + +<P>Since this is a recursive procedure without a stop rule, +it'll keep running forever. You'll have to stop it by pressing the +BREAK key, or command-period, or whatever your particular computer +requires. The procedure draws regular polygons; here are some +examples to try: + +<P><PRE>poly 100 90 +poly 80 60 +poly 100 144 +</PRE> + +<P>A little thought (or some experimentation) will show you that +the <CODE>size</CODE> input makes the +picture larger or smaller but doesn't change its shape. The shape is +entirely controlled by the <CODE>angle</CODE> input. + +<P>»What angle would you pick to draw a triangle? A pentagon? How do you +know? + +<P>The trick is to think about the turtle's state. When you finish +drawing a polygon, the turtle must return to its original position +<EM>and its original heading</EM> in order to be ready to retrace the +same path. To return to its original heading, the turtle must turn +through a complete circle, 360 degrees. To draw a square, for +example, the turtle must turn through 360 degrees in four turns, so +each turn must be 360/4 or 90 degrees. To draw a triangle, each turn +must be 360/3 or 120 degrees. + +<P>»Now explain why an <CODE>angle</CODE> input of 144 draws a star! + +<P>Okay, back to our squiggles. Earlier, I said that the only thing we +have to remember from the turtle's past history is the change in its +state. It doesn't matter how that change came about. When you draw a +<CODE>squiggle</CODE>, the turtle moves through a certain distance and turns +through a certain angle. The fact that it took a +roundabout path doesn't matter. As it happens, <CODE>squiggle</CODE> turns +right through 135+120+15 degrees, for a total of 270. This is +equivalent to turning left by 90 degrees. That's why repeating <CODE> +squiggle</CODE> draws something shaped like a square. + +<P><CENTER><IMG SRC="turtlestate.gif" ALT="figure: turtlestate"></CENTER> + +<P>»What about <CODE>squaggle</CODE>? If repeating it draws a figure with +18-fold symmetry, then its total turning should be 360/18 or 20 degrees. Is +it? + +<P>»Here's another bizarre shape. See if you can predict what kind of +symmetry it will show <EM>before</EM> you actually repeat it on the +computer. + +<P><TABLE><TR><TD> +<PRE>to squoggle +forward 50 +right 70 +forward 10 +right 160 +forward 35 +right 58 +end +</PRE><TD valign="center"><IMG SRC="https://people.eecs.berkeley.edu/~bh/v1ch10/squoggle.gif" ALT="turtle figure"> +</TABLE> + +<P>Suppose you like the shape of <CODE>squiggle</CODE>, but you want to draw a +completed picture that looks triangular (3-fold symmetry) instead of +square (4-fold). Can you do this? Of course; you can simply change +the last instruction of the <CODE>squiggle</CODE> procedure so that the total +turning is 120 degrees instead of 90. (Go ahead, try it. Be careful +about left and right.) + +<P>But it's rather an ugly process to have to edit <CODE>squiggle</CODE> in +order to change not what a squiggle looks like but how the squiggles +fit into a larger picture. For one thing, it violates the idea of +modularity. <CODE>Squiggle</CODE>'s job should just be drawing a squiggle, +and there should be another procedure, something like <CODE>poly</CODE>, +that combines squiggles into a symmetrical pattern. For another, +people shouldn't have to do arithmetic; computers should do the +arithmetic! + +<P>To clean up our act, I'm going to start by writing a procedure that +can draw an arbitrary squiggle but without changing the turtle's +heading. It's called <CODE>protect.heading</CODE> because it protects the +heading against change by the squiggle procedure. + +<P><PRE>to protect.heading :squig +local "oldheading +make "oldheading heading +run :squig +setheading :oldheading +end +</PRE> + +<P>This procedure demonstrates the use of <CODE>heading</CODE> +and <CODE>setheading</CODE>. We remember the turtle's initial heading +in the local variable <CODE>oldheading</CODE>. Then we carry out whatever squiggle +procedure you specify as the input to <CODE>protect.heading</CODE>. (The +<CODE>run</CODE> command takes a Logo instruction list as input and evaluates +it.) Here is how you can use it: + +<P><PRE>protect.heading [squiggle] +protect.heading [squaggle] +</PRE> + +<P>Notice that what is drawn on the screen is the same as it +would be if you invoked <CODE>squiggle</CODE> or <CODE>squaggle</CODE> directly; the +difference is that the turtle's final heading is the same as its +initial heading. + +<P><CENTER><IMG SRC="protect.gif" ALT="figure: protect"></CENTER> + +<P> + +<P>Now we can use <CODE>protect.heading</CODE> to write the decorated-<CODE>poly</CODE> +procedure that will let us specify the kind of symmetry we want: + +<P><PRE>to spin :turns :command +repeat :turns [protect.heading :command right 360/:turns] +end +</PRE> + +<P>»Try out <CODE>spin</CODE> with instructions like these: + +<P><TABLE><TR><TD> +<PRE>spin 3 [squiggle] +spin 5 [squiggle] +spin 4 [squaggle] +spin 6 [squoggle] +spin 6 [fd 40 squoggle] +spin 5 [pu fd 50 pd squaggle] +</PRE><TD valign="center"><IMG SRC="https://people.eecs.berkeley.edu/~bh/v1ch10/spin.gif" ALT="turtle figure"> +</TABLE> + +<P>Isn't that better? + +<P>I mentioned that there is an exception to the rule that every squiggle +will eventually retrace its steps if you repeat it. Here it is: + +<P><TABLE><TR><TD> +<PRE>to squirrel +forward 40 +right 90 +forward 10 +right 90 +forward 15 +right 90 +forward 20 +right 90 +end +</PRE><TD valign="center"><IMG SRC="squirrel.gif" ALT="turtle figure"> +</TABLE> + +<P>»Try repeating <CODE>squirrel</CODE> 20 times. You'll find that +instead of turning around to its original position and heading, the +turtle goes straight off into the distance. Why? (<CODE>Squiggle</CODE> had +four-fold symmetry because its total turning was 90 degrees. What is +the total turning of <CODE>squirrel</CODE>?) Of course, if you use <CODE> +squirrel</CODE> in the second input to <CODE>spin</CODE>, it will perform like the +others, because <CODE>spin</CODE> controls the turtle's heading in that case. + +<P>I've been using random squiggles with silly names to make +the point that by paying attention to symmetry, Logo <EM>can</EM> make +a silk purse from a sow's ear. But of course there is no reason not +to apply <CODE>spin</CODE> to more carefully designed pieces. Here's one I +like: + +<P><TABLE><TR><TD> +<PRE>to fingers :size +penup forward 10 pendown +right 5 +repeat 5 [forward :size right 170 forward :size left 170] +left 5 +penup back 10 pendown +end + +spin 4 [fingers 50] +spin 10 [fingers 30] +</PRE><TD valign="center"><IMG SRC="fingers.gif" ALT="turtle figure"> +</TABLE> + +<P> +<H2>Fractals</H2> + +<P>I'd like to write a procedure to draw this picture of a tree: + +<P><CENTER><IMG SRC="https://people.eecs.berkeley.edu/~bh/v1ch10/tree.gif" ALT="figure: tree"></CENTER> + +<P>The trick is to identify this as a recursive problem. Do +you see the smaller-but-similar subproblems? The tree consists of a +trunk with two smaller trees attached. + +<P><CENTER><IMG SRC="splittree.gif" ALT="figure: splittree"></CENTER> + +<P>So a first approximation to the solution might look like this: + +<P><PRE>to tree :size +forward :size +left 20 +tree :size/2 +right 40 +tree :size/2 +end +</PRE> + +<P>If you try running this procedure, you'll see that we still +have some work to do. But let me remind you that an unfinished +procedure like this isn't a <EM>mistake;</EM> you shouldn't feel that +you have to have every detail worked out before you first touch the +keyboard. The first obvious problem is that there is no stop rule, so +the procedure keeps trying to draw smaller and smaller subtrees. What +should the limiting condition be? In this case there is no obvious +end, like the <CODE>butfirst</CODE> of a word becoming empty. + +<P>There are two approaches we could take to limiting the number of +branches of the tree. One approach would be to choose explicitly how +deep we want to get in recursive invocations. We could do this by +adding another input, called <CODE>depth</CODE>, that will be the number of +levels of recursion to allow: + +<P><PRE>to tree :depth :size +if :depth=0 [stop] +forward :size +left 20 +tree (:depth-1) :size/2 +right 40 +tree (:depth-1) :size/2 +end +</PRE> + +<P>The other approach would be to keep letting the branches get +smaller until they go below a reasonable minimum: + +<P><PRE>to tree :size +if :size<4 [stop] +forward :size +left 20 +tree :size/2 +right 40 +tree :size/2 +end +</PRE> + +<P>Either approach is reasonable. I'll choose the second one +just because it seems a little simpler. The cost of that choice is +somewhat less control over the final picture; I'm not sure if it'll +have exactly the number of branches I originally planned. + +<P>The modified procedure does come to a halt now, but it still doesn't +draw the tree I had in mind. The problem is that this version of <CODE> +tree</CODE> is not <EM>state-invariant:</EM> it doesn't leave the turtle with +the same position and heading that it had originally. That's +important because when <CODE>tree</CODE> says + +<P><PRE>tree :size/2 +right 40 +tree :size/2 +</PRE> + +<P>the assumption is that at the end of the first smaller tree +the turtle will be back at the top of the main trunk, in position to +draw the second subtree. We can fix the problem by making the turtle +climb back down the trunk (of each subtree): + +<P><PRE>to tree :size +if :size<4 [stop] +forward :size +left 20 +tree :size/2 +right 40 +tree :size/2 +left 20 +back :size +end +</PRE> + +<P>Voila! If you try <CODE>tree 50</CODE> you'll see something like the +picture I had in mind. + +<P>You're probably thinking that this "tree" doesn't look very tree-like. +There are several things wrong with it: It's too symmetrical; it doesn't +have enough branches; the branches should grow partway up the trunk as well +as at the top. But all of these problems can be solved by adding a few more +steps to the procedure: + +<P><TABLE><TR><TD> +<PRE>to tree :size +if :size < 5 [forward :size back :size stop] +forward :size/3 +left 30 tree :size*2/3 right 30 +forward :size/6 +right 25 tree :size/2 left 25 +forward :size/3 +right 25 tree :size/2 left 25 +forward :size/6 +back :size +end +</PRE><TD valign="center"><IMG SRC="https://people.eecs.berkeley.edu/~bh/v1ch10/realtree.gif" ALT="turtle figure"> +</TABLE> + +<P>We can embellish the tree as much as we want. The only +requirement is that the procedure be state-invariant: The turtle's final +position and heading must be the same as its beginning position and heading. + +<P> + +<P>Because I chose to use a minimum length as the stopping condition, the +shape of the tree depends on the size of its trunk. That's slightly +unusual in turtle graphics programs, which usually draw the same shape +regardless of the size. + +<P>A recursively-defined shape (one that contains smaller versions of itself) +is called a <EM>fractal.</EM> Until the 1970s, hardly anybody explored +fractals except for kids learning Logo and a few recreational mathematicians. +Today, however, fractals have become important becase movie producers are +using computer graphics as an alternative to expensive sets and models for +fancy special effects. It turns out that programs like <CODE>tree</CODE> are the +secret of drawing realistic clouds, mountains, and other natural +backgrounds with a computer. + +<P>»If you want another challenging fractal project, try writing a program +to produce these fractal snowflakes: + +<P><CENTER><IMG SRC="flake.gif" ALT="figure: flake"></CENTER> + +<P><H2>Further Reading</H2> + +<P>If you're interested in an intellectually rigorous exploration of +turtle geometry, continuing along the lines I've started here, +read +<A HREF="http://mitpress.mit.edu/catalog/item/default.asp?sid=21C60546-CCA2-45E0-AA55-8E6BAC3EB07F&ttype=2&tid=7287"><EM>Turtle Geometry</EM></A>, +Abelson and diSessa (MIT Press, +1981). I learned many of the things in this chapter from them. It's +a hard book but worth the effort. + +<P>The standard reference book on fractals is <EM>The Fractal Geometry +of Nature,</EM> by Benoit Mandelbrot (W. H. Freeman, 1982). +Dr. Mandelbrot gave fractals their name and was the first to see +serious uses for them. + +<P><A HREF="../v1-toc2.html">(back to Table of Contents)</A> +<P><A HREF="../v1ch9/v1ch9.html"><STRONG>BACK</STRONG></A> +chapter thread <A HREF="../v1ch11/v1ch11.html"><STRONG>NEXT</STRONG></A> + +<P> +<ADDRESS> +<A HREF="../index.html">Brian Harvey</A>, +<CODE>bh@cs.berkeley.edu</CODE> +</ADDRESS> +</BODY> +</HTML> |