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/v2ch10/iter.html | |
| parent | 5d012c6c011a9dedf7d0a098e456206244eb5a0f (diff) | |
| download | tour-562a9a52d599d9a05f871404050968a5fd282640.tar.gz | |
*
Diffstat (limited to 'js/games/nluqo.github.io/~bh/v2ch10/iter.html')
| -rw-r--r-- | js/games/nluqo.github.io/~bh/v2ch10/iter.html | 1404 |
1 files changed, 1404 insertions, 0 deletions
diff --git a/js/games/nluqo.github.io/~bh/v2ch10/iter.html b/js/games/nluqo.github.io/~bh/v2ch10/iter.html new file mode 100644 index 0000000..dcb816e --- /dev/null +++ b/js/games/nluqo.github.io/~bh/v2ch10/iter.html @@ -0,0 +1,1404 @@ +<HTML> +<HEAD> +<TITLE>Computer Science Logo Style vol 2 ch 10: Iteration, Control Structures, Extensibility</TITLE> +</HEAD> +<BODY> +<CITE>Computer Science Logo Style</CITE> volume 2: +<CITE>Advanced Techniques</CITE> 2/e Copyright (C) 1997 MIT +<H1>Iteration, Control Structures, Extensibility</H1> + +<TABLE width="100%"><TR><TD> +<IMG SRC="../csls2.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/v2ch10.pdf">Download PDF version</A> +<TR><TD align="right"><A HREF="../v2-toc2.html">Back to Table of Contents</A> +<TR><TD align="right"><A HREF="https://people.eecs.berkeley.edu/~bh/v2ch9/v2ch9.html"><STRONG>BACK</STRONG></A> +chapter thread <A HREF="../v2ch11/v2ch11.html"><STRONG>NEXT</STRONG></A> +<TR><TD align="right"><A HREF="https://mitpress.mit.edu/books/computer-science-logo-style-second-edition-volume-2">MIT +Press web page for <CITE>Computer Science Logo Style</CITE></A> +</TABLE></TABLE> + +<HR> + +<P> +In this chapter we're taking a tour "behind the scenes" of Berkeley Logo. +Many of the built-in Logo procedures that we've been using all along are +not, strictly speaking, primitive; they're written in Logo itself. When you +invoke a procedure, if the Logo interpreter does not already know a procedure +by that name, it automatically looks in a <EM>library</EM> of predefined +procedures. For example, in Chapter 6 I used an operation called +<CODE>gensym</CODE> that outputs a new, unique word each time it's invoked. If +you start up a fresh copy of Logo you can try these experiments: + +<PRE> +? <U>po "gensym</U> +I don't know how to gensym +? <U>show gensym</U> +g1 +? <U>po "gensym</U> +to gensym +if not namep "gensym.number [make "gensym.number 0] +make "gensym.number :gensym.number + 1 +output word "g :gensym.number +end +</PRE> + +<P> +The first interaction shows that <CODE>gensym</CODE> is not really a Logo +primitive; the error message indicates that there is no such procedure. Then +I invoked <CODE>gensym</CODE>, which made Berkeley Logo read its definition +automatically from the library. Finally, once Logo has read the definition, +I can print it out. + +<P> +In particular, most of the tools we've used to carry out a computation +repeatedly are not true Logo primitives: <CODE>for</CODE> for numeric +iteration, <CODE>foreach</CODE> for list iteration, and <CODE>while</CODE> +for predicate-based iteration are all library procedures. (The word +<EM>iteration</EM> just means "repetition.") The only iteration mechanisms +that are truly primitive in Logo are <CODE>repeat</CODE> and recursion. + +<P> +Computers are good at doing things over and over again. They don't +get bored or tired. That's why, in the real world, people use +computers for things like sending out payroll checks and telephone +bills. The first Logo instruction I showed you, in the first volume, was + +<PRE> +repeat 50 [setcursor list random 75 random 20 type "Hi] +</PRE> + +<P> +When you were first introduced to turtle graphics, you +probably used an instruction like + +<PRE> +repeat 360 [forward 1 right 1] +</PRE> + +<P> +to draw a circle. + +<H2>Recursion as Iteration</H2> + +<P> +The trouble with <CODE>repeat</CODE> is that it always does <EM>exactly</EM> +the same thing repeatedly. In a real application, like those payroll +checks, you want the computer to do <EM>almost</EM> the same thing each +time but with a different person's name on each check. The usual way +to program an almost-<CODE>repeat</CODE> in Logo is to use a recursive +procedure, like this: + +<PRE> +to polyspi :side :angle :number +if :number=0 [stop] +forward :side +right :angle +polyspi :side+1 :angle :number-1 +end +</PRE> + +<P> +This is a well-known procedure to draw a spiral. What makes +it different from + +<PRE> +repeat :number [forward :side right :angle] +</PRE> + +<P> +is that the first input in the recursive invocation is <CODE>:side+1</CODE> +instead of just <CODE>:side</CODE>. We've used a similar technique for +almost-repetition in procedures like this one: + +<PRE> +to multiply :letters :number +if equalp :number 0 [stop] +print :letters +multiply (word :letters first :letters) :number-1 +end +</PRE> + +<P> +Since recursion can express any repetitive computation, why bother +inventing other iteration tools? The answer is that they can make +programs easier to read. Recursion is such a versatile mechanism +that the intention of any particular use of recursion may be hard to +see. Which of the following is easier to read? + +<PRE> +to fivesay.with.repeat :text +repeat 5 [print :text] +end +</PRE> + +<P> +or + +<PRE> +to fivesay.with.recursion :text +fivesay1 5 :text +end + +to fivesay1 :times :text +if :times=0 [stop] +print :text +fivesay1 :times-1 :text +end +</PRE> + +<P> +The version using <CODE>repeat</CODE> makes it obvious at a glance +what the program wants to do; the version using recursion takes some +thought. It can be useful to invent mechanisms that are intermediate +in flexibility between <CODE>repeat</CODE> and recursion. + +<P> +As a simple example, suppose that Logo did not include <CODE>repeat</CODE> as +a primitive command. Here's how we could implement it using recursion: + +<PRE> +to rep :count :instr +if :count=0 [stop] +run :instr +rep :count-1 :instr +end +</PRE> + +<P> +(I've used the name <CODE>rep</CODE> instead of <CODE>repeat</CODE> to avoid +conflict with the primitive version.) The use of <CODE>run</CODE> to carry out +the given instructions is at the core of the techniques we'll use +throughout this chapter. + +<H2>Numeric Iteration</H2> + +<P> +<CODE>Polyspi</CODE> is an example of an iteration in which the value of a +numeric variable changes in a uniform way. The instruction + +<PRE> +polyspi 50 60 4 +</PRE> + +<P> +is equivalent to the series of instructions + +<PRE> +forward 50 right 60 +forward 51 right 60 +forward 52 right 60 +forward 53 right 60 +</PRE> + +<P> +As you know, we can represent the same instructions this way: + +<PRE> +for [side 50 53] [forward :side right 60] +</PRE> + +<P> +The <CODE>for</CODE> command takes two inputs, very much like +<CODE>repeat</CODE>. The second input, like <CODE>repeat</CODE>'s second +input, is a list of Logo instructions. The first input to <CODE>for</CODE> +is different, though. It is a list whose first member is the name of a +variable; the second member of the list must be a number (or a Logo +expression whose value is a number), which will be the <EM>initial</EM> +value of that variable; and the third member must be another number (or +numeric expression), which will be the <EM>final</EM> value of the +variable. In the example above, the variable name is <CODE>side</CODE>, the +initial value is <CODE>50</CODE>, and the final value is <CODE>53</CODE>. +If there is a fourth member in the list, it's the amount to add to the named +variable on each iteration; if there is no fourth member, as in the example +above, then the <EM>step</EM> amount is either 1 or -1, depending on +whether the final value is greater than or less than the initial value. + +<P> +As an example in which expressions are used instead of constant numeric +values, here's the <CODE>polyspi</CODE> procedure using <CODE>for</CODE>: + +<PRE> +to polyspi :start :angle :number +for [side :start [:start+:number-1]] [forward :side right :angle] +end +</PRE> + +<P> +Most of the work in writing <CODE>for</CODE> is in evaluating the expressions +that make up the first input list. Here is the program: + +<PRE> +<A name="impfor">to for :values :instr</A> +localmake "var first :values +local :var +localmake "initial run first butfirst :values +localmake "final run item 3 :values +localmake "step forstep +localmake "tester ~ + ifelse :step < 0 [[:value < :final]] [[:value > :final]] +forloop :initial +end + +to forstep +if (count :values)=4 [output run last :values] +if :initial > :final [output -1] +output 1 +end + +to forloop :value +make :var :value +if run :tester [stop] +run :instr +forloop :value+:step +end +</PRE> + +<P> +One slightly tricky part of this program is the instruction + +<PRE> +local :var +</PRE> + +<P> +near the beginning of <CODE>for</CODE>. The effect of this instruction is +to make whatever variable is named by the first member of the first input +local to <CODE>for</CODE>. As it turns out, this variable isn't given a +value in <CODE>for</CODE> itself but only in its subprocedure +<CODE>forloop</CODE>. (A <EM>loop,</EM> by the way, is a part of a program +that is invoked repeatedly.) But I'm thinking of these three procedures as a +unit and making the variable local to that whole unit. The virtue of this +<CODE>local</CODE> instruction is that a program that uses <CODE>for</CODE> +can invent variable names for <CODE>for</CODE> freely, without having to +declare them local and without cluttering up the workspace with global +variables. Also, it means that a procedure can invoke another procedure in +the instruction list of a <CODE>for</CODE> without worrying about whether +<EM>that</EM> procedure uses <CODE>for</CODE> itself. Here's the case I'm +thinking of: + +<PRE> +to a +for [i 1 5] [b] +end + +to b +for [i 1 3] [print "foo] +end +</PRE> + +<P> +Invoking <CODE>A</CODE> should print the word <CODE>foo</CODE> fifteen +times: three times for each of the five invocations of <CODE>B</CODE>. If +<CODE>for</CODE> didn't make <CODE>I</CODE> a local variable, the invocation +of <CODE>for</CODE> within <CODE>B</CODE> would mess up the value of +<CODE>I</CODE> in the outer <CODE>for</CODE> invoked by +<CODE>A</CODE>. Got that? + +<P> +Notice that the <CODE>make</CODE> instruction in <CODE>forloop</CODE> has +<CODE>:var</CODE> as its first input, not <CODE>"var</CODE>. This +instruction does not assign a new value to the variable <CODE>var</CODE>! +Instead, it assigns a new value to the variable whose name is the value of +<CODE>var</CODE>. + +<P> +The version of <CODE>for</CODE> actually used in the Berkeley Logo library is +a little more complicated than this one. The one shown here works fine as +long as the instruction list input doesn't include <CODE>stop</CODE> or +<CODE>output</CODE>, but it won't work for an example like the following. +To check whether or not a number is prime, we must see if it is divisible by +anything greater than 1 and smaller than the number itself: + +<PRE> +to primep :num +for [trial 2 [:num-1]] [if divisiblep :num :trial [output "false]] +output "true +end + +to divisiblep :big :small +output equalp remainder :big :small 0 +end +</PRE> + +<P> +This example will work in the Berkeley Logo <CODE>for</CODE>, but not +in the version I've written in this chapter. The trouble is that the +instruction + +<PRE> +run :instr +</PRE> + +<P> +in <CODE>forloop</CODE> will make <CODE>forloop</CODE> output +<CODE>false</CODE> if a divisor is found, whereas we really want +<CODE>primep</CODE> to output <CODE>false</CODE>! We'll see in Chapter 12 +how to solve this problem. + +<H2>Logo: an Extensible Language</H2> + +<P> +There are two ways to look at a program like <CODE>for</CODE>. You can take +it apart, as I've been doing in these last few paragraphs, to see how it +works inside. Or you can just think of it as an extension to Logo, an +iteration command that you can use as you'd use <CODE>repeat</CODE>, without +thinking about how it works. I think both of these perspectives will be +valuable to you. As a programming project, <CODE>for</CODE> demonstrates +some rather advanced Logo techniques. But you don't have to think about +those techniques each time you use <CODE>for</CODE>. Instead you can think +of it as a primitive, as we've been doing prior to this chapter. + +<P> +The fact that you can extend Logo's vocabulary this way, adding a new way to +control iteration that looks just like the primitive <CODE>repeat</CODE>, is +an important way in which Logo is more powerful than toy programming +languages like C++ or Pascal. C++ has several iteration commands built in, +including one like <CODE>for</CODE>, but if you think of a new one, there's +no way you can add it to the language. In Logo this kind of language +extension is easy. For example, here is a preview of a programming project +I'm going to develop later in this chapter. Suppose you're playing with +spirals, and you'd like to see what happens if you change the line length +<EM>and</EM> the turning angle at the same time. That is, you'd like to be +able to say + +<PRE> +multifor [[size 50 100 5] [angle 50 100 10]] [forward :size right :angle] +</PRE> + +<P> +and have that be equivalent to the series of instructions + +<PRE> +forward 50 right 50 +forward 55 right 60 +forward 60 right 70 +forward 65 right 80 +forward 70 right 90 +forward 75 right 100 +</PRE> + +<P> +<CODE>Multifor</CODE> should step each of its variables each time +around, stopping whenever any of them hits the final value. This tool +strikes me as too specialized and complicated to provide in the Logo +library, but it seems very appropriate for certain kinds of project. +It's nice to have a language in which I can write it if I need it. + +<H2>No Perfect Control Structures</H2> + +<P> +Among enthusiasts of the Fortran family of programming languages (that is, +all the languages in which you have to say ahead of time whether or not the +value of some numeric variable will be an exact integer), there are fierce +debates about the "best" control structure. (A <EM>control structure</EM> +is a way of grouping instructions together, just as a <EM>data +structure</EM> is a way of grouping data together. A list is a data +structure. A procedure is a control structure. Things like +<CODE>if</CODE>, <CODE>repeat</CODE>, and <CODE>for</CODE> are special +control structures that group instructions in particular ways, so that a +group of instructions can be evaluated conditionally or repeatedly.) + +<P> +For example, all of the Fortran-derived languages have a control +structure for numeric iteration, like my <CODE>for</CODE> procedure. But +they differ in details. In some languages the iteration variable +must be stepped by 1. In others the step value can be either 1 or +-1. Still others allow any step value, as <CODE>for</CODE> does. Each of +these choices has its defenders as the "best." + +<P> +Sometimes the arguments are even sillier. When Fortran was first +invented, its designers failed to make explicit what should happen +if the initial value of an iteration variable is greater than the +final value. That is, they left open the interpretation of a Fortran +<CODE>do</CODE> statement (that's what its numeric iteration structure is +called) equivalent to this <CODE>for</CODE> instruction: + +<PRE> +for [var 10 5 1] [print :var] +</PRE> + +<P> +In this instruction I've specified a positive step (the +only kind allowed in the Fortran <CODE>do</CODE> statement), but the initial +value is greater than the final value. (What will <CODE>for</CODE> do in +this situation?) Well, the first Fortran compiler, the program that +translates a Fortran program into the "native" language of a +particular computer, implemented <CODE>do</CODE> so that the statements +controlled by the <CODE>do</CODE> were carried out once before the computer +noticed that the variable's value was already too large. Years later +a bunch of computer scientists decided that that behavior is +"wrong"; if the initial value is greater than the final value, the +statements shouldn't be carried out at all. This proposal for a +"zero trip <CODE>do</CODE> loop" was fiercely resisted by old-timers who +had by then written hundreds of programs that relied on the original +behavior of <CODE>do</CODE>. Dozens of journal articles and letters to the +editor carried on the battle. + +<P> +The real moral of this story is that there is no right answer. +The right control structure for <EM>you</EM> to use is the one that +best solves <EM>your</EM> immediate problem. But only an extensible +language like Logo allows you the luxury of accepting this moral. +The Fortran people had to fight out their battle because they're +stuck with whatever the standardization committee decides. + +<P> +In the remainder of this chapter I'll present various kinds of +control structures, each reflecting a different way of looking at the +general idea of iteration. + +<H2>Iteration Over a List</H2> + +<P> +Numeric iteration is useful if the problem you want to solve is about +numbers, as in the <CODE>primep</CODE> example, or if some arbitrary number is +part of the rules of a game, like the seven stacks of cards in solitaire. +But in most Logo projects, it's more common to want to carry out a +computation for each member of a list, and for that purpose we have +the <CODE>foreach</CODE> control structure: + +<PRE> +? <U>foreach [chocolate [rum raisin] pumpkin] [print sentence [I like] ?]</U> +I like chocolate +I like rum raisin +I like pumpkin +</PRE> + +<P> +In comparing <CODE>foreach</CODE> with <CODE>for</CODE>, one thing you might +notice is the use of the question mark to represent the varying datum in +<CODE>foreach</CODE>, while <CODE>for</CODE> requires a user-specified +variable name for that purpose. There's no vital reason why I used these +different mechanisms. In fact, we can easily implement a version of +<CODE>foreach</CODE> that takes a variable name as an additional input. Its +structure will then look similar to that of <CODE>for</CODE>: + +<PRE> +to named.foreach :var :data :instr +local :var +if emptyp :data [stop] +make :var first :data +run :instr +named.foreach :var (butfirst :data) :instr +end + +? <U>named.foreach "flavor [lychee [root beer swirl]] ~</U> + <U>[print sentence [I like] :flavor]</U> +I like lychee +I like root beer swirl +</PRE> + +<P> Just as in <A HREF="iter.html#impfor">the implementation of <CODE>for</CODE></A>, +there is a recursive invocation for each member of the data input. We +assign that member as the value of the variable named in the first input, +and then we <CODE>run</CODE> the instructions in the third input. + +<P> +In order to implement the version of <CODE>foreach</CODE> that uses question +marks instead of named variables, we need a more advanced version of +<CODE>run</CODE> that says "run these instructions, but using this value +wherever you see a question mark." Berkeley Logo has this capability as a +primitive procedure called <CODE>apply</CODE>. It takes two inputs, a +<EM>template</EM> (an instruction list with question marks) and a list of +values. The reason that the second input is a list of values, rather than a +single value, is that <CODE>apply</CODE> can handle templates with more than +one slot for values. + +<PRE> +? <U>apply [print ?+3] [5]</U> +8 +? <U>apply [print word first ?1 first ?2] [Peter Dickinson]</U> +PD +</PRE> + +<P> +It's possible to write <CODE>apply</CODE> in terms of <CODE>run</CODE>, and +I'll do that shortly. But first, let's just take advantage of Berkeley +Logo's built-in <CODE>apply</CODE> to write a simple version of +<CODE>foreach</CODE>: + +<PRE> +to foreach :list :template +if emptyp :list [stop] +apply :template (list first :list) +foreach (butfirst :list) :template +end +</PRE> + +<P> +<CODE>Apply</CODE>, like <CODE>run</CODE>, can be either a command or an +operation depending on whether its template contains complete Logo +instructions or a Logo expression. In this case, we are using +<CODE>apply</CODE> as a command. + +<P> +The version of <CODE>foreach</CODE> in the Berkeley Logo library can take +more than one data input along with a multi-input template, like this: + +<PRE> +? <U>(foreach [John Paul George Ringo] [rhythm bass lead drums]</U> + <U>[print (sentence ?1 "played ?2)]</U> +John played rhythm +Paul played bass +George played lead +Ringo played drums +</PRE> + +<P> +We can implement this feature, using a special notation in the title line of +<CODE>foreach</CODE> to notify Logo that it accepts a variable number of +inputs: + +<PRE> +to foreach [:inputs] 2 +foreach.loop (butlast :inputs) (last :inputs) +end + +to foreach.loop :lists :template +if emptyp first :lists [stop] +apply :template firsts :lists +foreach.loop (butfirsts :lists) :template +end +</PRE> + +<P> +First look at the title line of <CODE>foreach</CODE>. It tells Logo +that the word <CODE>inputs</CODE> is a formal parameter--the name of an input. +Because <CODE>:inputs</CODE> is inside square brackets, however, it represents +not just one input, but any number of inputs in the invocation of +<CODE>foreach</CODE>. The values of all those inputs are collected as a list, +and that list is the value of <CODE>inputs</CODE>. Here's a trivial example: + +<PRE> +to demo [:stuff] +print sentence [The first input is] first :stuff +print sentence [The others are] butfirst :stuff +end + +? <U>(demo "alpha "beta "gamma)</U> +The first input is alpha +The others are beta gamma +</PRE> + +<P> +As you know, the Logo procedures that accept a variable number of inputs +have a <EM>default</EM> number that they accept without using parentheses; +if you want to use more or fewer than that number, you must enclose the +procedure name and its inputs in parentheses, as I've done here with the +<CODE>demo</CODE> procedure. Most Logo primitives that accept a variable +number of inputs have two inputs as their default number (for example, +<CODE>sentence</CODE>, <CODE>sum</CODE>, <CODE>word</CODE>) but there are +exceptions, such as <CODE>local</CODE>, which takes one input if parentheses +are not used. When you write your own procedure with a single input name in +brackets, its default number of inputs is zero unless you specify another +number. <CODE>Demo</CODE>, for example, has zero as its default number. If +you look again at the title line of <CODE>foreach</CODE>, you'll see that it +ends with the number <CODE>2</CODE>; that tells Logo that +<CODE>foreach</CODE> expects two inputs by default. + +<P> +<CODE>Foreach</CODE> uses all but its last input as data lists; the last +input is the template to be applied to the members of the data lists. That's +why <CODE>foreach</CODE> invokes <CODE>foreach.loop</CODE> as it does, +separating the two kinds of inputs into two variables. + +<P> +Be careful when reading the definition of <CODE>foreach.loop</CODE>; it +invokes procedures named <CODE>firsts</CODE> and <CODE>butfirsts</CODE>. +These are not the same as <CODE>first</CODE> and <CODE>butfirst</CODE>! +Each of them takes a <EM>list of lists</EM> as its input, and outputs a list +containing the first members of each sublist, or all but the first members, +respectively: + +<PRE> +? <U>show firsts [[a b c] [1 2 3] [y w d]]</U> +[a 1 y] +? <U>show butfirsts [[a b c] [1 2 3] [y w d]]</U> +[[b c] [2 3] [w d]] +</PRE> + +<P> +It would be easy to write <CODE>firsts</CODE> and <CODE>butfirsts</CODE> in +Logo: + +<PRE> +to firsts :list.of.lists +output map "first :list.of.lists +end + +to butfirsts :list.of.lists +output map "butfirst :list.of.lists +end +</PRE> + +<P> +but in fact Berkeley Logo provides these operations as primitives, because +implementing them as primitives makes the iteration tools such as +<CODE>foreach</CODE> and <CODE>map</CODE> (which, as we'll see, also uses +them) much faster. + +<P> +Except for the use of <CODE>firsts</CODE> and <CODE>butfirsts</CODE> to +handle the multiple data inputs, the structure of <CODE>foreach.loop</CODE> +is exactly like that of the previous version of <CODE>foreach</CODE> that +only accepts one data list. + +<P> +Like <CODE>for</CODE>, the version of <CODE>foreach</CODE> presented here +can't handle instruction lists that include <CODE>stop</CODE> or +<CODE>output</CODE> correctly. + +<H2>Implementing <CODE>Apply</CODE></H2> + +<P> +Berkeley Logo includes <CODE>apply</CODE> as a primitive, for efficiency, but +we could implement it in Logo if necessary. In this section, so as not +to conflict with the primitive version, I'll use the name <CODE>app</CODE> for +my non-primitive version of <CODE>apply</CODE>, and I'll use the percent sign +(<CODE>%</CODE>) as the placeholder in templates instead of question mark. + +<P> +Here is a simple version of <CODE>app</CODE> that allows only one input to the +template: + +<PRE> +to app :template :input.value +run :template +end + +to % +output :input.value +end +</PRE> + +<P> +This is so simple that it probably seems like magic. <CODE>App</CODE> seems +to do nothing but <CODE>run</CODE> its template as though it were an ordinary +instruction list. The trick is that a template <EM>is</EM> an instruction +list. The only unusual thing about a template is that it includes special +symbols (<CODE>?</CODE> in the real <CODE>apply</CODE>, <CODE>%</CODE> in +<CODE>app</CODE>) that represent the given value. We see now that those +special symbols are really just ordinary names of procedures. The question +mark (<CODE>?</CODE>) procedure is a Berkeley Logo primitive; I've defined +the analogous <CODE>%</CODE> procedure here for use by <CODE>app</CODE>. + +<P> +The <CODE>%</CODE> procedure outputs the value of a variable, +<CODE>input.value</CODE>, that is local to <CODE>app</CODE>. If you invoke +<CODE>%</CODE> in some context other than an <CODE>app</CODE> template, +you'll get an error message because that variable won't exist. Logo's +dynamic scope makes it possible for <CODE>%</CODE> to use <CODE>app</CODE>'s +variable. + +<P> +The real <CODE>apply</CODE> accepts a procedure name as argument instead of a +template: + +<PRE> +? <U>show apply "first [Logo]</U> +L +</PRE> + +<P> +We can extend <CODE>app</CODE> to accept named procedures, but the +definition is somewhat messier: + +<PRE> +to app :template.or.name :input.value +ifelse wordp :template.or.name ~ + [run list :template.or.name "%] ~ + [run :template.or.name] +end +</PRE> + +<P> +If the first input is a word, we construct a template by combining that +procedure name with a percent sign for its input. However, in the rest of +this section I'll simplify the discussion by assuming that <CODE>app</CODE> +accepts only templates, not procedure names. + +<P> +So far, <CODE>app</CODE> takes only one value as input; the real +<CODE>apply</CODE> takes a list of values. I'll extend <CODE>app</CODE> to +match: + +<PRE> +to app :template :input.values +run :template +end + +to % [:index 1] +output item :index :input.values +end +</PRE> + +<P> +No change is needed to <CODE>app</CODE>, but <CODE>%</CODE> has been changed +to use another new notation in its title line. <CODE>Index</CODE> is the +name of an <EM>optional input.</EM> Although this notation also uses square +brackets, it's different from the notation used in <CODE>foreach</CODE> +because the brackets include a <EM>default value</EM> as well as the name +for the input. This version of <CODE>%</CODE> accepts either no inputs or +one input. If <CODE>%</CODE> is invoked with one input, then the value of +that input will be associated with the name <CODE>index</CODE>, just as for +ordinary inputs. If <CODE>%</CODE> is invoked with no inputs, then +<CODE>index</CODE> will be given the value 1 (its default value). + +<PRE> +? <U>app [print word first (% 1) first (% 2)] [Paul Goodman]</U> +PG +</PRE> + +<P> +A percent sign with a number as input selects an input value +by its position within the list of values. A percent sign by itself +is equivalent to <CODE>(% 1)</CODE>. + +<P> +The notation <CODE>(% 1)</CODE> isn't as elegant as the <CODE>?1</CODE> used +in the real <CODE>apply</CODE>. You can solve that problem by defining +several extra procedures: + +<PRE> +to %1 to %2 to %3 +output (% 1) output (% 2) output (% 3) +end end end +</PRE> + +<P> +Berkeley Logo recognizes the notation <CODE>?2</CODE> and automatically +translates it to <CODE>(? 2)</CODE>, as you can see by this experiment: + +<PRE> +? <U>show runparse [print word first ?1 first ?2]</U> +[print word first ( ? 1 ) first ( ? 2 )] +</PRE> + +<P> +(The primitive operation <CODE>runparse</CODE> takes a list as input +and outputs the list as it would be modified by Logo when it is about +to be run. That's a handwavy description, but the internal workings +of the Logo interpreter are too arcane to explore here.) + +<P> +Unlike the primitive <CODE>apply</CODE>, this version of <CODE>app</CODE> +works only as a command, not as an operation. It's easy to write a separate +version for use as an operation: + +<PRE> +to app.oper :template :input.values +output run :template +end +</PRE> + +<P> +It's not so easy in non-Berkeley versions of Logo to write a +single procedure that can serve both as a command and as an operation. +Here's one solution that works in versions with <CODE>catch</CODE>: + +<PRE> +to app :template :input.values +catch "error [output run :template] +ignore error +end +</PRE> + +<P> +This isn't an ideal solution, though, because it doesn't report errors other +than "<CODE>run</CODE> didn't output to <CODE>output</CODE>." It could be +improved by testing the error message more carefully instead of just +ignoring it. + +<P> +Berkeley Logo includes a mechanism that solves the problem more +directly, but it's not very pretty: + +<PRE> +to app :template :input.values +.maybeoutput run :template +end +</PRE> + +<P> +The primitive command <CODE>.maybeoutput</CODE> is followed by a Logo +expression that may or may not produce a value. If so, that value is +output, just as it would be by the ordinary <CODE>output</CODE> command; the +difference is that it's not considered an error if no value is produced. + +<P> +From now on I'll use the primitive <CODE>apply</CODE>. I showed you +<CODE>app</CODE> for two reasons. First, I think you'll understand +<CODE>apply</CODE> better by seeing how it can be implemented. Second, this +implementation may be useful if you ever work in a non-Berkeley Logo. + +<H2>Mapping</H2> + +<P> +So far the iteration tools we've created apply only to commands. +As you know, we also have the operation <CODE>map</CODE>, which is similar +to <CODE>foreach</CODE> except that its template is an expression (producing +a value) rather than an instruction, and it accumulates the values +produced for each member of the input. + +<PRE> +? <U>show map [?*?] [1 2 3 4]</U> +[1 4 9 16] +? <U>show map [first ?] [every good boy does fine]</U> +[e g b d f] +? +</PRE> + +<P> +When implementing an iteration tool, one way to figure out how to write +the program is to start with a specific example and generalize it. For +example, here's how I'd write the example about squaring the numbers in +a list without using <CODE>map</CODE>: + +<PRE> +to squares :numbers +if emptyp :numbers [output []] +output fput ((first :numbers) * (first :numbers)) ~ + (squares butfirst :numbers) +end +</PRE> + +<P> +<CODE>Map</CODE> is very similar, except that it applies a template to +each datum instead of squaring it: + +<PRE> +to map :template :values +if emptyp :values [output []] +output fput (apply :template (list first :values)) ~ + (map :template butfirst :values) +end +</PRE> + +<P> +You may be wondering why I used <CODE>fput</CODE> rather than +<CODE>sentence</CODE> in these procedures. Either would be just as good in +the example about squares of numbers, because each datum is a single word (a +number) and each result value is also a single word. But it's important to +use <CODE>fput</CODE> in an example such as this one: + +<PRE> +to swap :pair +output list last :pair first :pair +end + +? <U>show map [swap ?] [[Sherlock Holmes] [James Pibble] [Nero Wolfe]]</U> +[[Holmes Sherlock] [Pibble James] [Wolfe Nero]] + +? <U>show map.se [swap ?] [[Sherlock Holmes] [James Pibble] [Nero Wolfe]]</U> +[Holmes Sherlock Pibble James Wolfe Nero] +</PRE> + +<P> +Berkeley Logo does provide an operation <CODE>map.se</CODE> in which +<CODE>sentence</CODE> is used as the combiner; sometimes that's what you +want, but not, as you can see, in this example. (A third possibility that +might occur to you is to use <CODE>list</CODE> as the combiner, but that +never turns out to be the right thing; try writing a <CODE>map.list</CODE> +and see what results it gives!) + +<P> +As in the case of <CODE>foreach</CODE>, the program gets a little more +complicated when we extend it to handle multiple data inputs. Another +complication that wasn't relevant to <CODE>foreach</CODE> is that when we +use a word, rather than a list, as the data input to <CODE>map</CODE>, we +must use <CODE>word</CODE> as the combiner instead of <CODE>fput</CODE>. +Here's the complete version: + +<PRE> +to map :map.template [:template.lists] 2 +op map1 :template.lists 1 +end + +to map1 :template.lists :template.number +if emptyp first :template.lists [output first :template.lists] +output combine (apply :map.template firsts :template.lists) ~ + (map1 bfs :template.lists :template.number+1) +end + +to combine :this :those +if wordp :those [output word :this :those] +output fput :this :those +end +</PRE> + +<P> +This is the actual program in the Berkeley Logo library. One feature I +haven't discussed until now is the variable <CODE>template.number</CODE> +used as an input to <CODE>map1</CODE>. Its purpose is to allow the use of +the number sign character <CODE>#</CODE> in a template to represent the +position of each datum within its list: + +<PRE> +? <U>show map [list ? #] [a b c]</U> +[[a 1] [b 2] [c 3]] +</PRE> + +<P> +The implementation is similar to that of <CODE>?</CODE> in templates: + +<PRE> +to # +output :template.number +end +</PRE> + +<P> +It's also worth noting the base case in <CODE>map1</CODE>. When the data input +is empty, we must output either the empty word or the empty list, and +the easiest way to choose correctly is to return the empty input itself. + +<H2>Mapping as a Metaphor</H2> + +<P> +In this chapter, +we got to the idea of mapping by this route: iteration, numeric +iteration, other kinds of iteration, iteration on a list, iterative +commands, iterative operations, mapping. In other words, we started +thinking about the mapping tool as a particular kind of repetition in +a computer program. + +<P> +But when I first introduced <CODE>map</CODE> as a primitive operation, +I thought about it in a different way. Never mind the fact +that it's <EM>implemented</EM> through repetition. Instead think of +it as extending the power of the idea of a list. When we started +thinking about lists, we thought of the list as one complete entity. +For example, consider this simple interaction with Logo: + +<PRE> +? <U>print count [how now brown cow]</U> +4 +</PRE> + +<P> +<CODE>Count</CODE> is a primitive operation. It takes a list as +input, and it outputs a number that is a property of the entire list, +namely the number of members in the list. There is no need to think +of <CODE>count</CODE> as embodying any sort of repetitive control structure. +Instead it's one kind of handle on the <EM>data</EM> structure called +a list. + +<P> +There are other operations that manipulate lists, like <CODE>equalp</CODE> +and <CODE>memberp</CODE>. You're probably in the habit of thinking of these +operations as "happening all at once," not as examples of +iteration. And that's a good way to think of them, even though it's +also possible to think of them as iterative. For example, how does +Logo know the <CODE>count</CODE> of a list? How would <EM>you</EM> find out +the number of members of a list? One way would be to count them on +your fingers. That's an iteration. Logo actually does the same +thing, counting off the list members one at a time, as it would if +we implemented <CODE>count</CODE> recursively: + +<PRE> +to cnt :list +if emptyp :list [output 0] +output 1+cnt butfirst :list +end +</PRE> + +<P> +I'm showing you that the "all at once" Logo primitives can be +considered as iterative because, in the case of <CODE>map</CODE>, I want to +shift your point of view in the opposite direction. We started +thinking of <CODE>map</CODE> as iterative; now I'd like you to think of it +as happening all at once. + +<P> +Wouldn't it be nice if we could say + +<PRE> +? <U>show 1+[5 10 15]</U> +[6 11 16] +</PRE> + +<P> +That is, I'd like to be able to "add 1 to a list." I want +to think about it that way, not as "add 1 to each member of a list." +The metaphor is that we're doing something to the entire list at once. +Well, we can't quite do it that way, but we can say + +<PRE> +? <U>show map [1+?] [5 10 15]</U> +[6 11 16] +</PRE> + +<P> +Instead of thinking "Well, first we add 1 to 5, which gives +us 6; then we add..." you should think "we started with a list of +three numbers, and we've transformed it into another list of three +numbers using the operation add-one." + +<H2>Other Higher Order Functions</H2> + +<P> +Along with <CODE>map</CODE>, you learned about the higher order functions +<CODE>reduce</CODE>, which combines all of the members of a list into a single +result, and <CODE>filter</CODE>, which selects some of the members of a list. +They, too, are implemented by combining recursion with <CODE>apply</CODE>. +Here's the Berkeley Logo library version of <CODE>reduce</CODE>: + +<PRE> +to reduce :reduce.function :reduce.list +if emptyp butfirst :reduce.list [output first :reduce.list] +output apply :reduce.function (list (first :reduce.list) + (reduce :reduce.function + butfirst :reduce.list)) +end +</PRE> + +<P> +If there is only one member, output it. Otherwise, +recursively reduce the butfirst of the data, and apply the template +to two values, the first datum and the result from the recursive call. + +<P> +The Berkeley Logo implementation of <CODE>filter</CODE> is a little more +complicated, for some of the same reasons as that of <CODE>map</CODE>: the +ability to accept either a word or a list, and the <CODE>#</CODE> feature +in templates. So I'll start with a simpler one: + +<PRE> +to filter :template :data +if emptyp :data [output []] +if apply :template (list first :data) ~ + [output fput (first :data) + (filter :template butfirst :data)] +output filter :template butfirst :data +end +</PRE> + +<P> +If you understand that, you should be able to see the +fundamentally similar structure of the library version despite +its extra details: + +<PRE> +to filter :filter.template :template.list [:template.number 1] +localmake "template.lists (list :template.list) +if emptyp :template.list [output :template.list] +if apply :filter.template (list first :template.list) ~ + [output combine (first :template.list) + (filter :filter.template (butfirst :template.list) + :template.number+1)] +output (filter :filter.template (butfirst :template.list) + :template.number+1) +end +</PRE> + +<P> +Where <CODE>map</CODE> used a helper procedure <CODE>map1</CODE> to handle +the extra input <CODE>template.number</CODE>, <CODE>filter</CODE> uses an +alternate technique, in which <CODE>template.number</CODE> is declared as an +optional input to <CODE>filter</CODE> itself. When you invoke +<CODE>filter</CODE> you always give it the default two inputs, but it +invokes itself recursively with three. + +<P> +Why does <CODE>filter</CODE> need a local variable named +<CODE>template.lists</CODE>? There was a variable with that name in +<CODE>map</CODE> because it accepts more than one data input, but +<CODE>filter</CODE> doesn't, and in fact there is no reference to the value +of <CODE>template.lists</CODE> within <CODE>filter</CODE>. It's there +because of another feature of templates that I haven't mentioned: you can +use the word <CODE>?rest</CODE> in a template to represent the portion of +the data input to the right of the member represented by <CODE>?</CODE> in +this iteration: + +<PRE> +to remove.duplicates :list +output filter [not memberp ? ?rest] :list +end + +? <U>show remove.duplicates [ob la di ob la da]</U> +[di ob la da] +</PRE> + +<P> +Since <CODE>?rest</CODE> is allowed in <CODE>map</CODE> templates as well as +in <CODE>filter</CODE> templates, its implementation must be the same for both: + +<PRE> +to ?rest [:which 1] +output butfirst item :which :template.lists +end +</PRE> + +<H2>Mapping Over Trees</H2> + +<P> +It's time to move beyond the iteration tools in the Logo library and +invent our own new ones. + +<P> +So far, in writing operations on lists, we've ignored any sublist structure +within the list. We do something for each top-level member of the +input list. It's also possible to take advantage of the complex +structures that lists make possible. For example, a list can be used +to represent a <EM>tree,</EM> a data structure in which each branch can +lead to further branches. Consider this list: + +<PRE> +[[the [quick brown] fox] [[jumped] [over [the [lazy] dog]]]] +</PRE> + +<P> +My goal here is to represent a sentence in terms of the +phrases within it, somewhat like the sentence diagrams you may have +been taught in elementary school. This is a list with two members; +the first member represents the subject of the sentence and the +second represents the predicate. The predicate is further divided +into a verb and a prepositional phrase. And so on. (A representation +something like this, but more detailed, is used in any computer +program that tries to understand "natural language" interaction.) + +<P> +Suppose we want to convert each word of this sentence to capital letters, +using Berkeley Logo's <CODE>uppercase</CODE> primitive that takes a word as +input. We can't just say + +<PRE> +map [uppercase ?] ~ + [[the [quick brown] fox] [[jumped] [over [the [lazy] dog]]]] +</PRE> + +<P> +because the members of the sentence-list aren't words. What +I want is a procedure <CODE>map.tree</CODE> that applies a template to +each <EM>word</EM> within the input list but maintains the shape of the +list: + +<PRE> +? <U>show map.tree [uppercase ?]~</U> + <U>[[the [quick brown] fox] [[jumped] [over [the [lazy] dog]]]]</U> +[[THE [QUICK BROWN] FOX] [[JUMPED] [OVER [THE [LAZY] DOG]]]] +</PRE> + +<P> +After our previous adventures in mapping, this one is relatively easy: + +<PRE> +to map.tree :template :tree +if wordp :tree [output apply :template (list :tree)] +if emptyp :tree [output []] +output fput (map.tree :template first :tree) ~ + (map.tree :template butfirst :tree) +end +</PRE> + +<P> +This is rather a special-purpose procedure; it's only good for trees +whose "leaves" are words. That's sometimes the case but not +always. But if you're dealing with sentence trees like the one in my +example, you might well find several uses for a tool like this. For +now, I've introduced it mainly to make the point that the general idea +of iteration can take many different forms, depending on the +particular project you're working on. (Technically, this is <EM>not</EM> +an iteration, because it doesn't have a two-part structure in which the +first part is to perform one step of a computation and the second part +is to perform all the rest of the steps. <CODE>Map.tree</CODE> does have a +two-part structure, but <EM>both</EM> parts are recursive calls that might +carry out several steps. But <CODE>map.tree</CODE> does generalize the broad +idea of dividing a large computation into similar individual pieces. +We'll go into the nature of iteration more carefully in a moment.) + +<H2>Iteration and Tail Recursion</H2> + +<P> +If you look back at the introduction to recursion in the first volume, +you'll find that some recursive commands seem to be carrying out an +iteration, like <CODE>down</CODE>, <CODE>countdown</CODE>, or +<CODE>one.per.line</CODE>. (In this chapter we've seen how to implement +<CODE>countdown</CODE> using <CODE>for</CODE>, and you should easily be able +to implement <CODE>one.per.line</CODE> using <CODE>foreach</CODE>. +<CODE>Down</CODE> isn't exactly covered by either of those tools; can you see +why I call it an iterative problem anyway?) Other recursive commands don't +seem to be repeating or almost-repeating something, like <CODE>downup</CODE> +or <CODE>hanoi</CODE>. The difference is that these commands don't do +something completely, then forget about it and go on to the next +repetition. Instead, the first invocation of <CODE>downup</CODE>, for +example, still has work of its own to do after all the lower-level +invocations are finished. + +<P> +It turns out that a command that is <EM>tail</EM> recursive is one +that can be thought of as carrying out an iteration. A command that +invokes itself somewhere before the last instruction is not +iterative. But the phrase "tail recursive" doesn't <EM>mean</EM> +"equivalent to an iteration." It just happens to work out, for +commands, that the two concepts are equivalent. What "tail +recursive" means, really, is "invokes itself just before stopping." + +<P> +I've said before that this isn't a very important thing to worry about. The +reason I'm coming back to it now is to try to clear up a confusion that has +been part of the Logo literature. Logo implementors talk about tail +recursion because there is a tricky way to implement tail recursion that +takes less memory than the more general kind of recursion. Logo +<EM>teachers,</EM> on the other hand, tend to say "tail recursive" when +they really mean "iterative." For example, teachers will ask, "Should we +teach tail recursion first and then the general case?" What's behind this +question is the idea that iteration is easier to understand than recursion. +(By the way, this is a hot issue. Most Logo teachers would say yes; they +begin by showing their students an iterative command like <CODE>poly</CODE> +or <CODE>polyspi</CODE>. I generally say no; you may recall that the first +recursive procedure I showed you is <CODE>downup</CODE>. One reason is that +I expect some of my readers have programmed in Pascal or C, and I want to +make it as hard as possible for such readers to convince themselves that +recursion is just a peculiar way to express the idea of iteration.) + +<P> +There are two reasons people should stop making a fuss about tail +recursion. One is that they're confusing an idea about control +structures (iteration) with a Logo implementation strategy (tail +recursion). The second is that this way of thinking directs your +attention to commands rather than operations. (When people think +of iterative procedures as "easier," it's always commands that +they have in mind. Tail recursive operations are, if anything, +less straightforward than versions that are non-tail +recursive.) Operations are more important; they're what gives Logo much of +its flexibility. And the best way to think about recursive operations +isn't in implementation terms but in terms of data transformation +abstractions like mapping, reduction, and filters. + +<H2>Multiple Inputs to <CODE>For</CODE></H2> + +<P> +Earlier I promised you <CODE>multifor</CODE>, a version of <CODE>for</CODE> +that controls more than one numeric variable at a time. Its structure is +very similar to that of the original <CODE>for</CODE>, except that we use +<CODE>map</CODE> or <CODE>foreach</CODE> (or <CODE>firsts</CODE> or +<CODE>butfirsts</CODE>, which are implicit uses of <CODE>map</CODE>) in +almost every instruction to carry out <CODE>for</CODE>'s algorithm for each +of <CODE>multifor</CODE>'s numeric variables. + +<PRE> +to multifor :values.list :instr +localmake "vars firsts :values.list +local :vars +localmake "initials map "run firsts butfirsts :values.list +localmake "finals map [run item 3 ?] :values.list +localmake "steps (map "multiforstep :values.list :initials :finals) +localmake "testers map [ifelse ? < 0 [[?1 < ?2]] [[?1 > ?2]]] :steps +multiforloop :initials +end + +to multiforstep :values :initial :final +if (count :values)=4 [output run last :values] +if :initial > :final [output -1] +output 1 +end + +to multiforloop :values +(foreach :vars :values [make ?1 ?2]) +(foreach :values :finals :testers [if run ?3 [stop]]) +run :instr +multiforloop (map [?1+?2] :values :steps) +end +</PRE> + +<P> +This is a very dense program; I wouldn't expect anyone to read and understand +it from a cold start. But if you compare it to the implementation of +<CODE>for</CODE>, you should be able to make sense of how each line +is transformed in this version. + +<P> +Here is an example you can try: + +<PRE> +? <U>multifor [[a 10 100 5] [b 100 10 -10]] ~</U> + <U>[print (sentence :a "+ :b "= (:a + :b))]</U> +10 + 100 = 110 +15 + 90 = 105 +20 + 80 = 100 +25 + 70 = 95 +30 + 60 = 90 +35 + 50 = 85 +40 + 40 = 80 +45 + 30 = 75 +50 + 20 = 70 +55 + 10 = 65 +? +</PRE> + +<H2>The Evaluation Environment Bug</H2> + +<P> +There's a problem with all of these control structure tools that I haven't +talked about. The problem is that each of these tools uses <CODE>run</CODE> +or <CODE>apply</CODE> to evaluate an expression that's provided by the +calling procedure, but the expression is evaluated with the tool's local +variables active, in addition to those of the calling procedure. This can +lead to unexpected results if the name of a variable used in the expression +is the same as the name of one of the local variables in the tool. For +example, <CODE>forloop</CODE> has an input named <CODE>final</CODE>. What +happens if you try + +<PRE> +to grade :final +for [midterm 10 100 10] [print (sum :midterm :final) / 2] +end + +? <U>grade 50</U> +</PRE> + +<P> +Try this example with the implementation of <CODE>for</CODE> in this +chapter, not with the Logo library version. You might expect each iteration +to add 10 and 50, then 20 and 50, then 30 and 50, and so on. That is, you +wanted to add the iteration variable <CODE>midterm</CODE> to the input to +<CODE>grade</CODE>. In fact, though, the variable that contributes to the +sum is <CODE>forloop</CODE>'s <CODE>final</CODE>, not <CODE>grade</CODE>'s +<CODE>final</CODE>. + +<P> +The way to avoid this problem is to make sure you don't use variables +in superprocedures of these tools with the same names as the ones +inside the tools. One way to ensure that is to rewrite all the tool +procedures so that their local variables have bizarre names: + +<PRE> +to map :template :inputs +</PRE> + +<P> +becomes + +<PRE> +to map :map.qqzzqxx.template :map.qqzzqxx.inputs +</PRE> + +<P> +Of course, you also have to change the names wherever they +appear inside the definition, not just on the title line. You can see +why I preferred not to present the procedures to you in that form! + +<P> +It would be a better solution to have a smarter version of <CODE>run</CODE>, +which would allow explicit control of the +<EM>evaluation environment</EM>--the variable names and values +that should be in effect while evaluating <CODE>run</CODE>'s input. Some +versions of Lisp do have such a capability. + +<P><A HREF="../v2-toc2.html">(back to Table of Contents)</A> +<P><A HREF="https://people.eecs.berkeley.edu/~bh/v2ch9/v2ch9.html"><STRONG>BACK</STRONG></A> +chapter thread <A HREF="../v2ch11/v2ch11.html"><STRONG>NEXT</STRONG></A> + +<P> +<ADDRESS> +<A HREF="../index.html">Brian Harvey</A>, +<CODE>bh@cs.berkeley.edu</CODE> +</ADDRESS> +</BODY> +</HTML> |