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/v1ch9/v1ch9.html | |
| parent | 5d012c6c011a9dedf7d0a098e456206244eb5a0f (diff) | |
| download | tour-562a9a52d599d9a05f871404050968a5fd282640.tar.gz | |
*
Diffstat (limited to 'js/games/nluqo.github.io/~bh/v1ch9/v1ch9.html')
| -rw-r--r-- | js/games/nluqo.github.io/~bh/v1ch9/v1ch9.html | 570 |
1 files changed, 570 insertions, 0 deletions
diff --git a/js/games/nluqo.github.io/~bh/v1ch9/v1ch9.html b/js/games/nluqo.github.io/~bh/v1ch9/v1ch9.html new file mode 100644 index 0000000..e68bebe --- /dev/null +++ b/js/games/nluqo.github.io/~bh/v1ch9/v1ch9.html @@ -0,0 +1,570 @@ +<HTML> +<HEAD> +<TITLE>Computer Science Logo Style vol 1 ch 9: How Recursion Works</TITLE> +</HEAD> +<BODY> +<CITE>Computer Science Logo Style</CITE> volume 1: +<CITE>Symbolic Computing</CITE> 2/e Copyright (C) 1997 MIT +<H1>How Recursion Works</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/v1ch09.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="../v1ch8/v1ch8.html"><STRONG>BACK</STRONG></A> +chapter thread <A HREF="../v1ch10/v1ch10.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>The last two chapters were about how to write recursive procedures. This +chapter is about how to <EM>believe in</EM> recursive procedures, and about +understanding the process by which Logo carries them out. + +<P> +<H2>Little People and Recursion</H2> + +<P> +In Chapter 3, I introduced you to the metaphor of a computer full of +little elves. Each elf is an expert on a particular procedure. I +promised that this metaphor would be helpful later, when we'd have to +think about two little people carrying out the same procedure at the +same time. Well, "later" is now. + +<P>I want to use the elf metaphor to think about the <CODE>downup</CODE> example +of the previous chapter: +<PRE>to downup :word +print :word +if equalp count :word 1 [stop] +downup butlast :word +print :word +end +</PRE> + +<P>Recall that we are imagining the computer to be full of +elves, each of whom is a specialist in carrying out some procedure. +There are <CODE>print</CODE> elves, <CODE>count</CODE> elves, <CODE>stop</CODE> elves, and +so on. Each elf has some number of pockets, used to hold the inputs +for a particular invocation of a procedure. So a <CODE> +print</CODE> elf will have one pocket, while an <CODE>equalp</CODE> elf needs two +pockets. + +<P> + +<P>We're going to be most interested in the <CODE>downup</CODE> elves and the +contents of their pockets. To help you keep straight which elf is +which, I'm going to name the <CODE>downup</CODE> elves alphabetically: the +first one will be Ann, then Bill, then Cathy, then David, and so on. +Since we aren't so interested in the other elves, I won't bother +naming them. + +<P>»If you're reading this with a group of other people, you may find it +helpful for each of you to take on the role of one of the <CODE>downup</CODE> +elves and actually stick words in your pockets. If you have enough +people, some of you should also serve as elves for the primitive +procedures used, like <CODE>print</CODE> and <CODE>if</CODE>. + +<P>What happens when you type the instruction +<PRE>downup "hello +</PRE> +to Logo? The Chief Elf reads this instruction and sees that +it calls for the use of the procedure named <CODE>downup</CODE>. She +therefore recruits Ann, an elf who specializes in that procedure. +Since <CODE>downup</CODE> has one input, the Chief Elf has to give Ann +something to put in her one pocket. Fortunately, the input you +provided is a quoted word, which evaluates to itself. No other elves +are needed to compute the input. Ann gets the word <CODE>hello</CODE> in her +pocket. + +<P>Ann's task is to carry out the instructions that make up the +definition of <CODE>downup</CODE>. The first instruction is +<PRE>print :word +</PRE> +This, you'll remember, is an abbreviation for +<PRE>print thing "word +</PRE> +Ann must hire two more elves, a <CODE>print</CODE> specialist and a +<CODE>thing</CODE> specialist. The <CODE>print</CODE> elf can't begin his work +until he's given something to put in his pocket. Ann asks the <CODE> +thing</CODE> elf to figure out what that input should be. The <CODE>thing</CODE> +elf also gets an input, namely the word <CODE>word</CODE>. As we saw in +Chapter 3, <CODE>word</CODE> is what's written on the name tag in Ann's +pocket, since <CODE>word</CODE> is the name of <CODE>downup</CODE>'s input. So the +<CODE>thing</CODE> elf looks in that pocket, where it finds the word +<CODE>hello</CODE>. That word is then given to the <CODE>print</CODE> elf, who +prints it on your computer screen. + +<P>Ann is now ready to evaluate the second instruction: +<PRE>if equalp count :word 1 [stop] +</PRE> + +<P>Ann must hire several other elves to help her: an <CODE>if</CODE> +elf, a <CODE>count</CODE> elf, and a <CODE>thing</CODE> elf. I won't go through all +the steps in computing the inputs to <CODE>if</CODE>; since the <CODE>count</CODE> +of the word <CODE>hello</CODE> is not 1, the first input to <CODE>if</CODE> turns +out to be the word <CODE>false</CODE>. The second input to <CODE>if</CODE> is, of +course, the list <CODE>[stop]</CODE>. (Notice that Ann does <EM>not</EM> hire +a <CODE>stop</CODE> specialist. A list inside square brackets evaluates to +itself, just like a quoted word, without invoking any procedures. If +the first input to <CODE>if</CODE> had turned out to be <CODE>true</CODE>, it would +have been the <CODE>if</CODE> elf who would have hired a <CODE>stop</CODE> elf to +carry out the instruction inside the list.) Since its first input is +<CODE>false</CODE>, the <CODE>if</CODE> elf ends up doing nothing. + +<P>Ann's third instruction is +<PRE>downup butlast :word +</PRE> + +<P>Here's where things start to get interesting. Ann must +hire <EM>another</EM> <CODE>downup</CODE> specialist, named Bill. (Ann can't +carry out this new <CODE>downup</CODE> instruction herself because she's +already in the middle of a job of her own.) Ann must give Bill an +input to put in his pocket; to compute this input, she hires a <CODE> +butlast</CODE> elf and a <CODE>thing</CODE> elf. They eventually come up with the +word <CODE>hell</CODE> (the <CODE>butlast</CODE> of <CODE>hello</CODE>), and that's what +Ann puts in Bill's pocket. + +<P>We now have two active <CODE>downup</CODE> elves, Ann and Bill. Each has a +pocket. Both pockets are named <CODE>word</CODE>, but they have different +contents: Ann's <CODE>word</CODE> pocket contains <CODE>hello</CODE>, while Bill's +<CODE>word</CODE> pocket contains <CODE>hell</CODE>. + +<P> +<CENTER><IMG SRC="https://people.eecs.berkeley.edu/~bh/v1ch9/elf2.gif" ALT="figure: elf2"></CENTER> + +<P>Here is what this metaphor represents, in more technical +language: Although there is only one <EM>procedure</EM> named <CODE> +downup</CODE>, there can be more than one <EM>invocation</EM> of that +procedure in progress at a particular moment. (An invocation of a +procedure is also sometimes called an <EM>instantiation</EM> of the +procedure.) Each invocation has its own local variables; at this +moment there are <EM>two</EM> variables named <CODE>word</CODE>. It is +perfectly possible for two variables to have the same name as long as +they are associated with (local to) different procedure invocations. + +<P>If you had trouble figuring out how <CODE>downup</CODE> works in Chapter 7, +it's almost certainly because of a misunderstanding about this +business of local variables. That's what makes the elf metaphor so +helpful. For example, if you're accustomed to programming in BASIC, +then you're familiar with <EM>global</EM> variables as the only +possibility in the language. If all variables were global in Logo, +then there could only be one variable in the entire computer named +<CODE>word</CODE>. Instead of representing variables as pockets in the +elves' clothes, we'd have to represent them as safe deposit boxes kept +in some central bank and shared by all the elves. + +<P>But even if you're familiar with Logo's use of local variables, you +may have been thinking of the variables as being local to a <EM> +procedure,</EM> instead of understanding that they are local to an <EM> +invocation</EM> of a procedure. In that case you may have felt +perfectly comfortable with the procedures named <CODE>downup1</CODE>, <CODE> +downup2</CODE>, and so on, each of them using a separate variable named <CODE> +word</CODE>. But you may still have gotten confused when the <EM>same</EM> +variable <CODE>word</CODE>, the one belonging to the single procedure <CODE> +downup</CODE>, seemed to have several values at once. + +<P>If you were confused in that way, here's how to use the elf metaphor +to help yourself get unconfused: Suppose the procedure definitions are +written on scrolls, which are kept in a library. There is only one +copy of each scroll. (That is, there is only one definition for a +given procedure.) All the elves who specialize in a particular +procedure, like <CODE>downup</CODE>, have to share the same scroll. Well, if +variables were local to a procedure, they'd be pockets in the <EM> +scroll,</EM> rather than pockets in the <EM>elves' jackets.</EM> By +directing your attention to the elves (the invocations) instead of the +scrolls (the procedure definitions), you can see that there can be two +variables with the same name (<CODE>word</CODE>), associated with the same +procedure (<CODE>downup</CODE>), but belonging to different invocations +(represented by the elves Ann and Bill). + +<P>We still have several more elves to meet, so I'm going to pass over +some of the details more quickly now. We've just reached the point +where Bill is ready to set to work. For his first instruction he +hires a <CODE>print</CODE> elf, who prints the word <CODE>hell</CODE> on your +screen. Why <CODE>hell</CODE> and not <CODE>hello</CODE>? The answer is that when +Bill hires a <CODE>thing</CODE> expert to evaluate the expression <CODE> +:word</CODE>, the <CODE>thing</CODE> rules say that that expert must look <EM> +first</EM> in Bill's pockets, <EM>then</EM> (if Bill didn't have a pocket +named <CODE>word</CODE>) in Ann's pockets. + +<P>Bill then carries out the <CODE>if</CODE> instruction, which again has no +effect. Then Bill is ready for the <CODE>downup</CODE> instruction. He +hires a third <CODE>downup</CODE> elf, named Cathy. Bill puts the word <CODE> +hel</CODE> in Cathy's pocket. There are now three elves, all with pockets +named <CODE>word</CODE>, each with a different word. + +<P>Cathy is now ready to get to work. Don't forget, though, that Ann and +Bill haven't finished their jobs. Bill is still working on his third +instruction, waiting for Cathy to report the completion of her task. +Similarly, Ann is waiting for Bill to finish. + +<P>Cathy evaluates her first instruction, printing <CODE>hel</CODE> on the +screen. She evaluates the <CODE>if</CODE> instruction, with no effect. Then +she's ready for the <CODE>downup</CODE> instruction, the third one in the +procedure definition. To carry out this instruction, she hires David, +a fourth <CODE>downup</CODE> expert. She puts the word <CODE>he</CODE> in his +pocket. + +<P>David's career is like that of the other <CODE>downup</CODE> elves we've met +so far. He starts by printing his input, the word <CODE>he</CODE>. He +evaluates the <CODE>if</CODE> instruction, with no effect. (The <CODE>count</CODE> +of the word <CODE>he</CODE> is still not equal to 1.) He then gets to the +recursive invocation of <CODE>downup</CODE>, for which he hires a fifth +expert, named Ellen. He puts the word <CODE>h</CODE> in Ellen's pocket. + +<P>Ellen's career is <EM>not</EM> quite like that of the other elves. It +starts similarly: she prints her input, the word <CODE>h</CODE>, on your +screen. Then she prepares to evaluate the <CODE>if</CODE> instruction. This +time, though, the first input to <CODE>if</CODE> turns out to be the word +<CODE>true</CODE>, since the <CODE>count</CODE> of <CODE>h</CODE> is, indeed, 1. +Therefore, the <CODE>if</CODE> elf evaluates the instruction contained in its +second input, the list <CODE>[stop]</CODE>. It hires a <CODE>stop</CODE> elf, whose +job is to tell Ellen to stop working. (Why Ellen? Why not one of the +other active elves? There are <EM>seven</EM> elves active at the +moment: Ann, Bill, Cathy, David, Ellen, the <CODE>if</CODE> elf, and the <CODE> +stop</CODE> elf. The rule is that a <CODE>stop</CODE> elf stops the <EM> +lowest-level invocation of a user-defined procedure.</EM> <CODE>If</CODE> and +<CODE>stop</CODE> are primitives, so they don't satisfy the <CODE>stop</CODE> elf. +The remaining five elves are experts in <CODE>downup</CODE>, a user-defined +procedure; of the five, Ellen is the lowest-level invocation.) + +<P>(By the way, the insistence of <CODE>stop</CODE> on a user-defined procedure +to stop is one of the few ways in which Logo treats such procedures +differently from primitive procedures. If you think about it, you'll +see that it would be useless for <CODE>stop</CODE> to stop just the +invocation of <CODE>if</CODE>. That would mean that the <CODE>if</CODE> instruction +would never do anything of interest and there would be no way to stop +a procedure of your own conditionally. But you can imagine other +situations in which it would be nice to be able to <CODE>stop</CODE> a +primitive. Here's one: +<PRE>repeat 100 [print "hello if equalp random 5 0 [stop]] +</PRE> + +<P>If it worked, this instruction would print the word <CODE> +hello</CODE> some number of times, up to 100, but with a 20 percent chance +of stopping after each time. In fact, though, you can't use <CODE> +stop</CODE> to stop a <CODE>repeat</CODE> invocation.) + +<P>Let's review what's been printed so far: +<PRE>hello printed by Ann +hell printed by Bill +hel printed by Cathy +he printed by David +h printed by Ellen +</PRE> + +<P>Ellen has just stopped. She reports back to David, the elf who hired +her. He's been waiting for her; now he can continue with his own +work. David is up to the fourth and final instruction in the +definition of <CODE>downup</CODE>: +<PRE>print :word +</PRE> + +<P>What word will David print? For David, <CODE>:word</CODE> refers +to the contents of <EM>his own</EM> pocket named <CODE>word</CODE>. That is, +when David hires a <CODE>thing</CODE> expert, that expert looks first in +David's pockets, before trying Cathy's, Bill's, and Ann's. The word +in David's <CODE>word</CODE> pocket is <CODE>he</CODE>. So that's what David +prints. + +<P>Okay, now David has reached the end of his instructions. He reports +back to his employer, Cathy. She's been waiting for him, so that she +can continue her own work. She, too, has one more <CODE>print</CODE> +instruction to evaluate. She has the word <CODE>hel</CODE> in her <CODE>word</CODE> +pocket, so that's what she prints. + +<P>Cathy now reports back to Bill. He prints his own word, <CODE>hell</CODE>. +He reports back to Ann. She prints her word, <CODE>hello</CODE>. + +<P>When Ann finishes, she reports back to the Chief Elf, who prints a +question mark on the screen and waits for you to type another +instruction. + +<P>Here is the complete effect of this <CODE>downup</CODE> instruction: +<PRE>hello printed by Ann +hell printed by Bill +hel printed by Cathy +he printed by David +h printed by Ellen +he printed by David +hel printed by Cathy +hell printed by Bill +hello printed by Ann +</PRE> + +<P>»You might want to see if the little person metaphor can help you +understand the working of the <CODE>inout</CODE> procedure from Chapter 7. +Remember that each elf carrying out the recursive procedure needs two +pockets, one for each input. + +<P><H2>Tracing</H2> + +<P>Many people find the idea of multiple, simultaneous invocations of a +single procedure confusing. To keep track of what's going on, you +have to think about several "levels" of evaluation at once. "Where +is <CODE>downup</CODE> up to right now?" -- "Well, it depends what you +mean. The lowest-level <CODE>downup</CODE> invocation has just evaluated its +first <CODE>print</CODE> instruction. But there are three other invocations +of <CODE>downup</CODE> that are in the middle of evaluating their recursive +<CODE>downup</CODE> instructions." This can be especially confusing if +you've always been taught that the computer can only do one thing at a +time. People often emphasize the <EM>sequential</EM> nature of the +computer; what we've been saying about recursion seems to violate that +nature. + +<P>If this kind of confusion is a problem for you, it may help to think +about a procedure like <CODE>downup</CODE> by <EM>tracing</EM> its progress. +That is, we can tell the procedure to print out extra +information each time it's invoked, to help you see the sequence +of events. + +<P>Just for reference, here's <CODE>downup</CODE> again: + +<P><PRE>to downup :word +print :word +if equalp count :word 1 [stop] +downup butlast :word +print :word +end +</PRE> + +<P>The trace command takes a procedure name (or a list of +procedure names, to trace more than one) as its input. It tells Logo to +notify you whenever that procedure is invoked: + +<P><PRE>? <U>trace "downup</U> +? <U>downup "logo</U> +<SMALL><CODE>( downup "logo ) +</CODE></SMALL>logo +<SMALL><CODE> ( downup "log ) +</CODE></SMALL>log +<SMALL><CODE> ( downup "lo ) +</CODE></SMALL>lo +<SMALL><CODE> ( downup "l ) +</CODE></SMALL>l +<SMALL><CODE> downup stops +</CODE></SMALL>lo +<SMALL><CODE> downup stops +</CODE></SMALL>log +<SMALL><CODE> downup stops +</CODE></SMALL>logo +<SMALL><CODE>downup stops +</CODE></SMALL></PRE> + +<P>To make this result a little easier to read, I've printed the +lines that are generated by the tracing in smaller letters than the lines +generated by <CODE>downup</CODE> itself. Of course the actual computer output all +looks the same. + +<P>Each line of tracing information is indented by a number of spaces equal to +the number of traced procedure invocations already active--the <EM> +level</EM> of procedure invocation. By looking only +at the lines between one <CODE>downup</CODE> invocation and the equally-indented +stopping line, you can see how much is accomplished by each recursive call. +For example, the innermost invocation (at level 4) prints only the letter <CODE>l</CODE>. + +<P><H2>Level and Sequence</H2> + +<P> +The result of tracing <CODE>downup</CODE> is most helpful +if you think about it two-dimensionally. If +you read it <EM>vertically,</EM> it represents the <EM>sequence</EM> of +instructions that fits the traditional model of computer programming. +That is, the order of the printed lines represents the order of events +in time. First the computer enters <CODE>downup</CODE> at level 1. Then it +prints the word <CODE>logo</CODE>. Then it enters <CODE>downup</CODE> at level 2. +Then it prints <CODE>log</CODE>. And so on. Each printed line, including +the "official" lines as well as the tracing lines, represents a +particular instruction, carried out at a particular moment. Reading +the trace vertically will help you fit <CODE>downup</CODE>'s recursive method +into your sequential habits of thought. + +<P> + +On the other hand, if you read the trace <EM>horizontally,</EM> it shows +you the hierarchy of <EM>levels</EM> of <CODE>downup</CODE>'s invocations. +To see this, think of the trace as divided into two overlapping +columns. The left column consists of the official pattern of words +printed by the original <CODE>downup</CODE>. In the right column, the +pattern of entering and exiting from each level is shown. The lines +corresponding to a particular level are indented by a number of spaces +that corresponds to the level number. For example, find the line +<PRE><SMALL><CODE> ( downup "log ) +</CODE></SMALL></PRE> + +<P>and the matching +<PRE><SMALL><CODE> downup stops +</CODE></SMALL></PRE> + +<P>Between these two lines you'll see this: +<PRE>log +<SMALL><CODE> ( downup "lo ) +</CODE></SMALL>lo +<SMALL><CODE> ( downup "l ) +</CODE></SMALL>l +<SMALL><CODE> downup stops +</CODE></SMALL>lo +<SMALL><CODE> downup stops +</CODE></SMALL>log +</PRE> + +<P>What this shows is that levels 3 and 4 are <EM>part of</EM> +level 2. You can see that the traced invocation and stopping lines +for levels 3 and 4 begin further to the right than the ones for level +2. Similarly, the lines for level 4 are further indented than the +ones for level 3. This variation in indentation is a graphic display +of the superprocedure/subprocedure relationships among the various +invocations. + +<P>There are two ways of thinking about the lines that aren't indented. +One way is to look at all such lines within, say, level 2: +<PRE>log +lo +l +lo +log +</PRE> + +<P>This tells you that those five lines are printed somehow +within the activity of level 2. (In terms of the little people +metaphor, those lines are printed by Bill, either directly or through +some subordinate elf.) Another way to look at it is this: +<PRE><SMALL><CODE> ( downup "log ) +</CODE></SMALL>log +<SMALL><CODE> ( downup "lo ) +</CODE></SMALL> ... +<SMALL><CODE> downup stops +</CODE></SMALL>log +<SMALL><CODE> downup stops +</CODE></SMALL></PRE> + +<P>What this picture is trying to convey is that only the two +<CODE>log</CODE> lines are <EM>directly</EM> within the control of level 2. +The three shorter lines (<CODE>lo</CODE>, <CODE>l</CODE>, <CODE>lo</CODE>) are delegated to +level 3. + +<P>We've seen three different points of view from which to read the +trace, one vertical and two horizontal. The vertical point of view +shows the sequence of events in time. The horizontal point of view +can show either the <EM>total</EM> responsibility of a given level or +the <EM>direct</EM> responsibility of the level. To develop a full +understanding of recursion, the trick is to be able to see all of +these aspects of the program at the same time. + +<P>»Try invoking the traced <CODE>downup</CODE> with a single-letter input. +Make a point of reading the resulting trace from all of these +viewpoints. Then try a two-letter input. + +<P> +<H2>Instruction Stepping</H2> + +<P>Perhaps you are comfortable with the idea of levels of invocation, but +confused about the particular order of instructions within <CODE> +downup</CODE>. Why should the <CODE>if</CODE> instruction be where it is, instead +of before the first <CODE>print</CODE>, for example? Logo's <CODE>step</CODE> command +will allow you to examine each instruction line within <CODE>downup</CODE> as it +is carried out: + +<P><PRE>? <U>step "downup</U> +? <U>downup "ant</U> +<SMALL><CODE>[print :word] >>> +</CODE></SMALL>ant +<SMALL><CODE>[if equalp count :word 1 [stop]] >>> +[downup butlast :word] >>> +[print :word] >>> +</CODE></SMALL>an +<SMALL><CODE>[if equalp count :word 1 [stop]] >>> +[downup butlast :word] >>> +[print :word] >>> +</CODE></SMALL>a +<SMALL><CODE>[if equalp count :word 1 [stop]] >>> +[print :word] >>> +</CODE></SMALL>an +<SMALL><CODE>[print :word] >>> +</CODE></SMALL>ant +</PRE> + +<P>After each of the lines ending with <CODE>>>></CODE>, Logo waits for you +to press the RETURN or ENTER key. + +<P>You can combine <CODE>trace</CODE> and <CODE>step</CODE>: + +<P><PRE>? <U>step "downup</U> +? <U>trace "downup</U> +? <U>downup "ant</U> +<SMALL><CODE>( downup "ant ) +[print :word] >>> +</CODE></SMALL>ant +<SMALL><CODE>[if equalp count :word 1 [stop]] >>> +[downup butlast :word] >>> + ( downup "an ) + [print :word] >>> +</CODE></SMALL>an +<SMALL><CODE> [if equalp count :word 1 [stop]] >>> + [downup butlast :word] >>> + ( downup "a ) + [print :word] >>> +</CODE></SMALL>a +<SMALL><CODE> [if equalp count :word 1 [stop]] >>> + downup stops + [print :word] >>> +</CODE></SMALL>an +<SMALL><CODE> downup stops +[print :word] >>> +</CODE></SMALL>ant +<SMALL><CODE>downup stops +</CODE></SMALL></PRE> + +<P>In this case, the <CODE>step</CODE> lines are indented to match +the <CODE>trace</CODE> lines. + +<P>Once a procedure is <CODE>trace</CODE>d or <CODE>step</CODE>ped, it remains so until +you use the <CODE>untrace</CODE> or <CODE>unstep</CODE> command to counteract the tracing +or stepping. + +<P>»Try drawing a vertical line extending between the line +<PRE> ( downup "an ) +</PRE> + +<P>and the equally indented +<PRE> downup stops +</PRE> + +<P>Draw the line just to the left of the printing, after the +indentation. The line you drew should also touch exactly four +instruction lines. These four lines make up the entire definition of the +<CODE>downup</CODE> procedure. If we restrict our attention to +one particular invocation of <CODE>downup</CODE>, like the one you've marked, +you can see that each of <CODE>downup</CODE>'s instructions is, indeed, +evaluated in the proper sequence. Below each of these instruction +lines, you can see the effect of the corresponding instruction. The +two <CODE>print</CODE> instructions each print one line in the left +(unindented) column. (In this case, they both +print the word <CODE>an</CODE>.) The <CODE>if</CODE> instruction has +no visible effect. But the recursive invocation of <CODE>downup</CODE> has +quite a large effect; it brings into play the further invocation of +<CODE>downup</CODE> with the word <CODE>a</CODE> as input. + +<P>One way to use the stepping information is to "play computer." Pretend +you are the Logo interpreter, carrying out a <CODE>downup</CODE> instruction. +Exactly what would you do, step by step? As you work through the +instructions making up the procedure definition, you can check +yourself by comparing your activities to what's shown on the screen. + +<P><A HREF="../v1-toc2.html">(back to Table of Contents)</A> +<P><A HREF="../v1ch8/v1ch8.html"><STRONG>BACK</STRONG></A> +chapter thread <A HREF="../v1ch10/v1ch10.html"><STRONG>NEXT</STRONG></A> + +<P> +<ADDRESS> +<A HREF="../index.html">Brian Harvey</A>, +<CODE>bh@cs.berkeley.edu</CODE> +</ADDRESS> +</BODY> +</HTML> |