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/v1ch5 | |
| parent | 5d012c6c011a9dedf7d0a098e456206244eb5a0f (diff) | |
| download | tour-562a9a52d599d9a05f871404050968a5fd282640.tar.gz | |
*
Diffstat (limited to 'js/games/nluqo.github.io/~bh/v1ch5')
| -rw-r--r-- | js/games/nluqo.github.io/~bh/v1ch5/filter.gif | bin | 0 -> 1376 bytes | |||
| -rw-r--r-- | js/games/nluqo.github.io/~bh/v1ch5/hof.html | 1431 | ||||
| -rw-r--r-- | js/games/nluqo.github.io/~bh/v1ch5/initials.gif | bin | 0 -> 2149 bytes | |||
| -rw-r--r-- | js/games/nluqo.github.io/~bh/v1ch5/maperror.gif | bin | 0 -> 1288 bytes | |||
| -rw-r--r-- | js/games/nluqo.github.io/~bh/v1ch5/mapoper.gif | bin | 0 -> 998 bytes | |||
| -rw-r--r-- | js/games/nluqo.github.io/~bh/v1ch5/v1ch5.html | 1431 |
6 files changed, 2862 insertions, 0 deletions
diff --git a/js/games/nluqo.github.io/~bh/v1ch5/filter.gif b/js/games/nluqo.github.io/~bh/v1ch5/filter.gif new file mode 100644 index 0000000..9e040e6 --- /dev/null +++ b/js/games/nluqo.github.io/~bh/v1ch5/filter.gif Binary files differdiff --git a/js/games/nluqo.github.io/~bh/v1ch5/hof.html b/js/games/nluqo.github.io/~bh/v1ch5/hof.html new file mode 100644 index 0000000..7bbd997 --- /dev/null +++ b/js/games/nluqo.github.io/~bh/v1ch5/hof.html @@ -0,0 +1,1431 @@ +<HTML> +<HEAD> +<TITLE>Computer Science Logo Style vol 1 ch 5: Functions of Functions</TITLE> +</HEAD> +<BODY> +<CITE>Computer Science Logo Style</CITE> volume 1: +<CITE>Symbolic Computing</CITE> 2/e Copyright (C) 1997 MIT +<H1>Functions of Functions</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/v1ch05.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="../v1ch4/v1ch4.html"><STRONG>BACK</STRONG></A> +chapter thread <A HREF="../v1ch6/v1ch6.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> +We now have many of the tools we need to write computer programs. We have +the primitive operations for arithmetic computation, the primitive +operations to manipulate words and sentences, and a way to choose between +alternative computations. One thing that we still lack is a way to deal +systematically with data <EM>aggregates</EM>--collections of data. We want +to be able to say "carry out this computation for each member of that +aggregate." Processing large amounts of data uniformly is one of the +abilities that distinguish computers from mere pocket calculators. + +<H2>The Problem: <CODE>Initials</CODE></H2> + +<P> +To make this concrete, we'll look at a very simple example. I'd like to +write a procedure that can figure out a person's initials, like this: + +<PRE> +? <U>show initials [George Harrison]</U> +[G H] +</PRE> + +<P> +One obvious approach is to find the initials of the first name and the +last name: + +<PRE> +to initials :name +output sentence (first first :name) (first last :name) +end +</PRE> + +<P> +The trouble is that this approach doesn't work for people with middle +names. We'd like our <CODE>initials</CODE> procedure to be able to handle +any length name. But it doesn't: + +<PRE> +? <U>show initials [John Alec Entwistle]</U> +[J E] +? <U>show initials [Peter Blair Denis Bernard Noone]</U> +[P N] +</PRE> + +<P> +What we want is this: + +<PRE> +? <U>show initials.in.our.dreams [John Alec Entwistle]</U> +[J A E] +? <U>show initials.in.our.dreams [Peter Blair Denis Bernard Noone]</U> +[P B D B N] +</PRE> + +<P> +If we knew that the input would have exactly five names, we +could extract the first letter of each of them explicitly. But you never +know when some smart alec will ask you to + +<PRE> +show initials [Princess Angelina Contessa Louisa Francesca ~ + Banana Fana Bo Besca the Third] +</PRE> + +<H2>One Solution: Numeric Iteration</H2> + +<P> +If you've programmed before in other languages, then one solution will +immediately occur to you. You create a variable <CODE>n</CODE> whose value +is the number of words in the input, then you have a variable <CODE>i</CODE> +that takes on all possible values from 1 to <CODE>n</CODE>, and you select +the <CODE>i</CODE>th word from the input and pull out its first letter. +Most languages have a special notation for this sort of computation: + +<PRE> +for i = 1 to n : ... : next i <I>(BASIC)</I> +for 1 := 1 to n do begin ... end <I>(Pascal)</I> +for (i=1; i<=n; i++) { ... } <I>(C)</I> +</PRE> + +<P> +All of these have the same meaning: Carry out some instructions +(the part shown as <CODE>...</CODE> above) repeatedly, first with the variable +named <CODE>i</CODE> having the value <CODE>1</CODE>, then with <CODE>i</CODE> equal to <CODE>2</CODE>, +and so on, up to <CODE>i</CODE> equal to <CODE>n</CODE>. This technique is called +<EM>numeric iteration.</EM> "Iteration" means repetition, and it's +"numeric" iteration because the repetition is controlled by a variable +that takes on a sequence of numeric values. + +<P> +We can do the same thing in Logo, although, as we'll soon learn, it's not +the usual approach that Logo programmers take to this problem. + +<PRE> +to initials :name +local "result +make "result [] +for [i 1 [count :name]] ~ + [make "result sentence :result first (item :i :name)] +output :result +end +</PRE> + +<P> +(The reason I declare <CODE>result</CODE> as local, but not <CODE>i</CODE>, +is that Logo's <CODE>for</CODE> automatically makes its index variable local +to the <CODE>for</CODE> itself. There is no variable <CODE>i</CODE> outside +of the <CODE>for</CODE> instruction.) + +<P> +The command <CODE>for</CODE> takes two inputs. The second input is an +instruction list that will be carried out repeatedly. The first input +controls the repetition; it is a list of either three or four members: a +variable name, a starting value, a limit value, and an optional increment. +(The variable named by the first member of the list is called the <EM>index +variable.</EM> For example: + +<PRE> +? <U>for [number 4 7] [print :number]</U> +4 +5 +6 +7 +? <U>for [value 4 11 3] [print :value]</U> +4 +7 +10 +</PRE> + +<P> +In the first example, <CODE>number</CODE> takes on all integer values +between 4 and 7. In the second, <CODE>value</CODE>'s starting value is 4, +and on each repetition its new value is 3 more than last time. +<CODE>Value</CODE> never actually has its limiting value of 11; the next +value after 10 would have been 13, but that's bigger than the limit. + +<P> +<CODE>For</CODE> can count downward instead of upward: + +<PRE> +? <U>for [i 7 5] [print :i]</U> +7 +6 +5 +? <U>for [n 15 2 -6] [print :n]</U> +15 +9 +3 +? <U>for [x 15 2 6] [print :x]</U> +? +</PRE> + +<P> The last example has no effect. Why? The increment of 6 implies that +this invocation of <CODE>for</CODE> should count upward, which means that the +<CODE>for</CODE> continues until the value of <CODE>x</CODE> is greater than +the limit, 2. But the starting value, 15, is <EM>already</EM> greater than +2. + +<P> If no increment is given in the first input to <CODE>for</CODE>, then +<CODE>for</CODE> will use either <CODE>1</CODE> or <CODE>-1</CODE> as the +increment, whichever is compatible with the starting and limit values. + +<P> +Although I've been using constant numbers as the starting value, limit +value, and increment in these examples, <CODE>for</CODE> can handle any Logo +expression, represented as a list, for each of these: + +<PRE> +to spread :ends +for [digit [first :ends] [last :ends]] [type :digit] +print [] +end + +? <U>spread 19</U> +123456789 +? <U>spread 83</U> +876543 +</PRE> + +<P> +More formally, the effect of <CODE>for</CODE> is as follows. First it creates the +local index variable and assigns it the starting value. Then <CODE>for</CODE> +carries out three steps repeatedly: testing, action, and incrementing. The +testing step is to compare the current value of the index variable with the +limit value. If the index variable has passed the limit, then the <CODE>for</CODE> +is finished. ("Passed" means that the index variable is greater than the +limit, if the increment is positive, or that the index variable is less than +the limit, if the increment is negative.) The action step is to evaluate +the instructions in the second input to <CODE>for</CODE>. The incrementing step is +to assign a new value to the index variable by adding the increment to the +old value. Then comes another round of testing, action, and incrementing. + +<P> +So, for example, if we give Logo the instruction + +<PRE> +show initials [Raymond Douglas Davies] +</PRE> + +<P> +then the <CODE>for</CODE> instruction within <CODE>initials</CODE> is equivalent +to this sequence of instructions: + +<PRE> +local "i ; initialize index variable +make "i 1 + +if (:i > 3) [stop] ; testing +make "result (se :result first "Raymond) ; action (result is [R]) +make "i :i+1 ; incrementing (i is 2) + +if (:i > 3) [stop] ; testing +make "result (se :result first "Douglas) ; action (result is [R D]) +make "i :i+1 ; incrementing (i is 3) + +if (:i > 3) [stop] ; testing +make "result (se :result first "Davies) ; action (result is [R D D]) +make "i :i+1 ; incrementing (i is 4) + +if (:i > 3) [stop] ; testing +</PRE> + +<P> +except that the <CODE>stop</CODE> instruction in the testing step stops +only the <CODE>for</CODE> instruction, not the <CODE>initials</CODE> procedure. + +<H2>Critique of Numeric Iteration</H2> + +<P> +Computers were originally built to deal with numbers. Numeric iteration +matches closely the behind-the-scenes sequence of steps by which computers +actually work. That's why just about every programming language supports +this style of programming. + +<P> +Nevertheless, a <CODE>for</CODE> instruction isn't anything like the way +you, a human being, would solve the <CODE>initials</CODE> problem without a +computer. First of all, you wouldn't begin by counting the number of words +in the name; you really don't have to know that. You'd just say, for +example, "First of Raymond is R; first of Douglas is D; first of Davies is +D." When you ran out of names, you'd stop. + +<P> +The manipulation of the <CODE>result</CODE> variable to collect the results also +seems unnatural. You wouldn't think, "I'm going to start with an empty +result; then, whatever value <CODE>result</CODE> has, I'll throw in an R; then, +whatever value <CODE>result</CODE> now has, I'll throw in a D" and so on. + +<P> +In fact, if you had to explain to someone else how to solve this problem, +you probably wouldn't talk about a sequence of steps at all. Rather, you'd +draw a picture like this one: + +<P><CENTER><IMG SRC="initials.gif" ALT="<P>figure: initials"></CENTER> + +<P> +To explain the picture, you'd say something like "Just take the +<CODE>first</CODE> of each word." You wouldn't even mention the need to put the +results together into a sentence; you'd take that for granted. + +<P> +In Logo we can write an <CODE>initials</CODE> procedure using the same way of +thinking that you'd use in English: + +<PRE> +to initials :name +output map "first :name +end +</PRE> + +<P> +The <CODE>map</CODE> procedure means "collect the results of +doing <EM>this</EM> for each of <EM>those.</EM>" + +<P> +As this example illustrates, <CODE>map</CODE> is easy to use. But it's a +little hard to talk about, because it's a function of a function. So first +we'll take a detour to talk more precisely about functions in general. + +<H2>What's a Function?</H2> + +<P> +A <EM>function</EM> is a rule for turning one value (called the +<EM>argument</EM>) into another. If +you've studied algebra you'll remember numeric function rules such as + +<P><CENTER><I>f</I>(<I>x</I>) = 3<I>x</I>-6</CENTER> + +<P> +but not all functions are numeric, and not all rules need be expressed as +algebraic formulas. For example, here is the Instrument function, which +takes a Beatle as its argument and returns his instrument: + +<P><CENTER><TABLE> +<TR align="left"> +<TH><U>argument</U>       </TH> +<TH><U>result</U></TH> +<TR> +<TD>John</TD> +<TD>rhythm guitar</TD> +<TR> +<TD>Paul</TD> +<TD>bass guitar</TD> +<TR> +<TD>George</TD> +<TD>lead guitar</TD> +<TR> +<TD>Ringo</TD> +<TD>drums</TD> +</TABLE></CENTER> + +<P> +This particular function has only four possible arguments. Other +functions, like <I>f</I>(<I>x</I>) above, may have infinitely many possible arguments. +The set of possible arguments is called the <EM>domain</EM> of the +function. Similarly, the set of possible result values is called the +<EM>range</EM> of the function.* + +<SMALL><BLOCKQUOTE><SMALL><SUP>*</SUP>It's a little awkward to talk about +the domain of a function that takes two arguments. That is, it's easy to +say that the domain of the function represented by the <CODE>first</CODE> operation +is words or lists, but how do we describe <CODE>item</CODE>? We could loosely say +"its domain is numbers and words or lists," but that sounds as if either +argument could be any of those. The most precise way to say it is this: +"The domain of <CODE>item</CODE> is pairs of values, in which the first member of +the pair is a positive integer and the second member is a word or list of +length greater than or equal to the first member of the pair." But for +ordinary purposes we just rephrase the sentence to avoid the word "domain" +altogether: "<CODE>Item</CODE> takes two inputs; the first must be a positive +integer and the second must be a word or list..."</SMALL></BLOCKQUOTE></SMALL> + +<P> +Functions can be represented in many ways. (We've seen two in this +section: formulas and tables.) One way to represent a function is with a +Logo operation. Here are Logo representations of the two functions we've +discussed: + +<PRE> +to f :x +output 3*:x - 6 +end + +to instrument :beatle +if :beatle = "John [output [rhythm guitar]] +if :beatle = "Paul [output [bass guitar]] +if :beatle = "George [output [lead guitar]] +if :beatle = "Ringo [output [drums]] +end +</PRE> + +<P> +(What if we give <CODE>instrument</CODE> an input that's not in the +domain of the function? In that case, it won't output any value, and a Logo +error message will result. Some people would argue that the procedure +should provide its own, more specific error message.) + +<P> +I've been careful to say that the Logo operation <EM>represents</EM> the +function, not that it <EM>is</EM> the function. In particular, two Logo +procedures can compute the same function--the same relationship between +input and output values--by different methods. For example, +consider these Logo operations: + +<PRE> +to f :x to g :x +output 3*:x - 6 output 3 * (:x-2) +end end +</PRE> + +<P> +The Logo operations <CODE>f</CODE> and <CODE>g</CODE> carry out two different +computations, but they represent the same function. For example, to compute +<CODE>f 10</CODE> we say 3×10=30, 30-6=24; to compute +<CODE>g 10</CODE> we say 10-2=8, 3×8=24. Different computations, +but the same answer. Functional programming means, in part, focusing our +attention on the inputs and outputs of programs rather than on the sequence +of computational steps. + +<P> +Just as a Logo operation represents a function, the procedure's inputs +similarly <EM>represent</EM> the arguments to the corresponding function. +For example, that instrument function I presented earlier has Beatles (that +is to say, people) as its domain and has musical instruments as its range. +But Logo doesn't have people or instruments as data types, and so the +procedure <CODE>instrument</CODE> takes as its input <EM>the name of</EM> a +Beatle (that is, a word) and returns as its output <EM>the name of</EM> an +instrument (a sentence). Instrument is a function from Beatles to +instruments, but <CODE>instrument</CODE> is an operation from words to +sentences. + +<P> +We're about to see a similar situation when we explore <CODE>map</CODE>. +The map function--that is, the function that <CODE>map</CODE> +represents--is a <EM>function of functions.</EM> One of the arguments to +the map function is itself a function. The corresponding input to Logo's +<CODE>map</CODE> procedure should be a procedure. But it turns out that +Logo doesn't quite allow a procedure to be an input to another procedure; +instead, we must use the <EM>name</EM> of the procedure as the input, just as +we use the name of a Beatle as the input to <CODE>instrument</CODE>. + +<P> +I know this sounds like lawyer talk, and we haven't written any programs for +a while. But here's why this is important: In order to understand the +<EM>purpose</EM> of <CODE>map</CODE>, you have to think about the map +function, whose domain is functions (and other stuff, as we'll see in a +moment). But in order to understand the <EM>notation</EM> that you use with +<CODE>map</CODE> in Logo, you have to think in terms of the Logo operation, +whose input is words (names of procedures). You have to be clear about this +representation business in order to be able to shift mentally between these +viewpoints. + +<H2>Functions of Functions: <CODE>Map</CODE></H2> + +<P> +<CODE>Map</CODE> takes two inputs. The first is a word, which must be the name +of a one-input Logo operation. The second can be any datum. The output +from <CODE>map</CODE> is either a word or a list, whichever is the type of the +second input. The members of the output are the results of applying the +named operation to the members of the second input. + +<PRE> +? <U>show map "first [Rod Argent]</U> +[R A] +</PRE> + +<P> +In this example, the output is a list of two members, just as the second +input is a list of two members. Each member of the output is the result of +applying <CODE>first</CODE> to one of the members of <CODE>map</CODE>'s +second input. + +<P> +Many people, when they first meet <CODE>map</CODE>, are confused by the +quoting of its first input. After all, I made a fuss back in Chapter +2 about the difference between these two examples: + +<PRE> +? <U>print Hello</U> +I don't know how to Hello +? <U>print "Hello</U> +Hello +</PRE> + +<P> +You learned that a quoted word means the word itself, while an unquoted word +asks Logo to invoke a procedure. But now, when I want to use the +<CODE>first</CODE> procedure as input to <CODE>map</CODE>, I'm quoting its +name. Why? + +<P> +All that effort about the domains of functions should help you understand +the notation used here. Start by ignoring the Logo notation and think about +the domain of the map function. We want the map function to have +<EM>another function,</EM> the function "first" in this case, as one of its +arguments: + +<P><CENTER><IMG SRC="https://people.eecs.berkeley.edu/~bh/v1ch5/mapfun.gif" ALT="<P>figure: mapfun"></CENTER> + +<P> +It's tempting to say that in Logo, a function is represented by a procedure, +so <CODE>map</CODE> represents map, and <CODE>first</CODE> represents first. +If this were algebra notation, I'd say <I>map</I>(<I>first</I>, <I>Rod Argent</I>), +so in Logo I'll say + +<PRE> +show map first [Rod Argent] ;; wrong! +</PRE> + +<P> +But when a Logo instruction has two unquoted procedure names in a row, that +doesn't mean that the second function is used as argument to the first! +Instead, it means that <EM>the output from invoking</EM> the second function +is used as the argument to the first. In this case, we'd be +<EM>composing</EM> <CODE>map</CODE> and <CODE>first</CODE>: + +<P><CENTER><IMG SRC="maperror.gif" ALT="<P>figure: maperror"></CENTER> + +<P> +As the plumbing diagram shows, the list that we intended as the second input +to <CODE>map</CODE> actually ends up as the input to <CODE>first</CODE>, and +Logo will complain because <CODE>map</CODE> isn't given enough inputs. + +<P> +Instead, as I said earlier, we must use <EM>the name of</EM> the +<CODE>first</CODE> procedure to represent it. That gives this diagram: + +<P><CENTER><IMG SRC="mapoper.gif" ALT="<P>figure: mapoper"></CENTER> + +<P> +Here's another simple example. Logo has a primitive operation +<CODE>uppercase</CODE> that takes a word as input, and outputs the same word +but in all capital letters: + +<PRE> +? <U>print uppercase "young</U> +YOUNG +</PRE> + +<P> +What if we want to translate an entire sentence to capital letters? The +<CODE>uppercase</CODE> primitive doesn't accept a sentence as its input: + +<PRE> +? <U>show uppercase [neil young]</U> +uppercase doesn't like [neil young] as input. +</PRE> + +<P> +But we can use <CODE>map</CODE> to translate each word separately and +combine the results: + +<PRE> +? <U>show map "uppercase [neil young]</U> +[NEIL YOUNG] +</PRE> + +<P> +Ordinarily <CODE>map</CODE> works with one-argument functions. But we can +give <CODE>map</CODE> extra arguments (by enclosing the invocation of +<CODE>map</CODE> in parentheses, as usual) so that it can work with +functions of more than one argument. + +<PRE> +? <U>show (map "item [2 1 2 3] [john paul george ringo])</U> +[o p e n] +? <U>show (map "sum [1 2 3] [40 50 60] [700 800 900])</U> +[741 852 963] +</PRE> + +<P> +Each input after the first provides values for one input to the mapped +function. For example, <CODE>[2 1 2 3]</CODE> provides four values for the +first input to <CODE>item</CODE>. The input lists must all have the same +length (two lists of length four in the <CODE>item</CODE> example, three +lists of length three in the <CODE>sum</CODE> example). + +<P> +In the examples so far, the input data have been lists. Here's an example +in which we use <CODE>map</CODE> with words. Let's say we're writing a +program to play Hangman, the word game in which one player guesses letters +in a secret word chosen by the other player. At first the guesser sees only +a row of dashes indicating the number of letters in the word; for each +guess, more letters are revealed. We aren't going to write the entire +program yet, but we're ready to write the operation that takes the secret +word, and a list of the letters that have been guessed so far, and outputs a +row of letters and dashes as appropriate. + +<PRE> +to hangword :secret :guessed +output map "hangletter :secret +end + +to hangletter :letter +output ifelse memberp :letter :guessed [:letter] ["_] +end + +? <U>print hangword "potsticker [e t a o i n]</U> +_ot_ti__er +? <U>print hangword "gelato [e t a o i n]</U> +_e_ato +</PRE> + +<P> +Notice that <CODE>hangletter</CODE> depends on Logo's dynamic scope to have +access to <CODE>hangword</CODE>'s local variable named <CODE>guessed</CODE>. + +<P> +» Write an operation <CODE>exaggerate</CODE> that takes a sentence as +input and outputs an exaggerated version: + +<PRE> +? <U>print exaggerate [I ate 3 potstickers]</U> +I ate 6 potstickers +? <U>print exaggerate [The chow fun is good here]</U> +The chow fun is great here +</PRE> + +<P> +It should double all the numbers in the sentence, and replace +"good" with "great," "bad" with "terrible," and so on. + +<P> +A function whose domain or range includes functions is called a +<EM>higher order function.</EM> The function represented by +<CODE>map</CODE> is a higher order function. (We may speak loosely and say +that <CODE>map</CODE> is a higher order function, as long as you remember +that Logo procedures aren't really functions!) It's tempting to say that the +<CODE>map</CODE> procedure itself is a "higher order procedure," but in +Logo that isn't true. Procedures aren't data in Logo; the only data types +are words and lists. That's why the input to <CODE>map</CODE> is a word, +the name of a procedure, and not the procedure itself. Some languages do +treat procedures themselves as data. In particular, the language Scheme is +a close relative of Logo that can handle procedures as data. If this way of +thinking appeals to you, consider learning Scheme next! + +<H2>Higher Order Selection: <CODE>Filter</CODE></H2> + +<P> +The purpose of <CODE>map</CODE> is to <EM>transform</EM> each member of an +aggregate (a list or a word) by applying some function to it. Another +higher order function, <CODE>filter</CODE>, is used to <EM>select</EM> some +members of an aggregate, but not others, based on a criterion expressed as a +predicate function. For example: + +<PRE> +? <U>show filter "numberp [76 trombones, 4 calling birds, and 8 days]</U> +[76 4 8] + +to vowelp :letter +output memberp :letter "aeiou +end + +? <U>show filter "vowelp "spaghetti</U> +aei + +to beatlep :person +output memberp :person [John Paul George Ringo] +end + +? <U>show filter "beatlep [Bob George Jeff Roy Tom]</U> +[George] +</PRE> + +<P> +What happens if we use the <CODE>initials</CODE> procedure that we wrote with +people's names in mind for other kinds of names, such as organizations or +book titles? Some of them work well: + +<PRE> +? <U>show initials [Computer Science Logo Style]</U> +[C S L S] +? <U>show initials [American Civil Liberties Union]</U> +[A C L U] +</PRE> + +<P> +but others don't give quite the results we'd like: + +<PRE> +? <U>show initials [Association for Computing Machinery]</U> +[A f C M] +? <U>show initials [People's Republic of China]</U> +[P R o C] +</PRE> + +<P> +We'd like to eliminate words like "for" and "of" before taking the first +letters of the remaining words. This is a job for <CODE>filter</CODE>: + +<PRE> +to importantp :word +output not memberp :word [the an a of for by with in to and or] +end + +to initials :name +output map "first (filter "importantp :name) +end + +? <U>show initials [Association for Computing Machinery]</U> +[A C M] +? <U>show initials [People's Republic of China]</U> +[P R C] +</PRE> + +<H2>Many to One: <CODE>Reduce</CODE></H2> + +<P> +Of course, what we'd <EM>really</EM> like is to have those initials in the +form of a single word: ACLU, CSLS, ACM, and so on. For this purpose we +need yet another higher order function, one that invokes a combining +function to join the members of an aggregate. + +<PRE> +? <U>show reduce "word [C S L S]</U> +CSLS +? <U>show reduce "sum [3 4 5 6]</U> +18 +? <U>show reduce "sentence "UNICEF</U> +[U N I C E F] +</PRE> + +<P> +<CODE>Reduce</CODE> takes two inputs. The first must be the name of a +two-input operation; the second can be any <EM>nonempty</EM> word or list. + +<PRE> +to acronym :name +output reduce "word initials :name +end +</PRE> + +<P> +In practice, the first input to <CODE>reduce</CODE> won't be any old +operation; it'll be a <EM>constructor.</EM> It'll be something that doesn't +care about the grouping of operands; for example, <CODE>sum</CODE> is a good +choice but <CODE>difference</CODE> is problematic because we don't know +whether + +<PRE> +reduce "difference [5 6 7] +</PRE> + +<P> +means 5-(6-7) or (5-6)-7, and the grouping affects the answer. Almost +all the time, the constructor will be <CODE>word</CODE>, +<CODE>sentence</CODE>, <CODE>sum</CODE>, or <CODE>product</CODE>. But +here's an example of another one: + +<PRE> +to bigger :a :b +output ifelse :a > :b [:a] [:b] +end + +to biggest :nums +output reduce "bigger :nums +end + +? <U>show biggest [5 7 781 42 8]</U> +781 +</PRE> + +<H2>Choosing the Right Tool</H2> + +<P> +So far you've seen three higher order functions: <CODE>map</CODE>, +<CODE>filter</CODE>, and <CODE>reduce</CODE>. How do you decide which one to +use for a particular problem? + +<P> +<CODE>Map</CODE> transforms each member of a word or list individually. The +result contains as many members as the input. + +<P><CENTER><IMG SRC="https://people.eecs.berkeley.edu/~bh/v1ch5/map.gif" ALT="<P>figure: map"></CENTER> + +<P> +<CODE>Filter</CODE> selects certain members of a word or list and discards the +others. The members of the result are members of the input, without +transformation, but the result may be smaller than the original. + +<P><CENTER><IMG SRC="filter.gif" ALT="<P>figure: filter"></CENTER> + +<P> +<CODE>Reduce</CODE> transforms the entire word or list into a single result +by combining all of the members in some way. + +<P><CENTER><IMG SRC="https://people.eecs.berkeley.edu/~bh/v1ch5/reduce.gif" ALT="<P>figure: reduce"></CENTER> + +<H2>Anonymous Functions</H2> + +<P> +In several of the examples in this chapter, I've had to write "helper" +procedures such as <CODE>hangletter</CODE>, <CODE>importantp</CODE>, and +<CODE>bigger</CODE> that will never be used independently, but are needed +only to provide the function argument to a higher order function. It would +be simpler if we could avoid writing these as separate procedures. + +<P> +Does that sound confusing? This is one of those ideas for which an example +is worth 1000 words: + +<PRE> +to hangword :secret :guessed +output map [ifelse memberp ? :guessed [?] ["_]] :secret +end +</PRE> + +<P> +Until now, the first input to <CODE>map</CODE> has always been a word, +used to represent the function with that word as its name. In this example +we see how a nameless function can be represented: as a list containing a +Logo expression, but with question marks where the function's argument +belongs. Such a list is called a <EM>template.</EM> + +<PRE> +? <U>show filter [memberp ? [John Paul George Ringo]] ~</U> + <U>[Bob George Jeff Roy Tom]</U> +[George] +</PRE> + +<P> +Anonymous functions of more than one argument are a little uglier. Instead +of <CODE>?</CODE> for the argument, you must use <CODE>?1</CODE> for the +first, <CODE>?2</CODE> for the second, and so on. + +<PRE> +to biggest :nums +output reduce [ifelse ?1 > ?2 [?1] [?2]] :nums +end +</PRE> + +<P> +Notice that the templates don't say <CODE>output</CODE>, as the named +procedures did. That's because procedures are made of +<EM>instructions,</EM> whereas these are <EM>expression</EM> templates. +When input values are "plugged in" for the question marks, the template +becomes a Logo expression, which means that when evaluated it has a value. +If the template said <CODE>output</CODE>, it would be saying to use that +value as the output <EM>from the procedure containing it!</EM> (I'm just +repeating the point made earlier that <CODE>output</CODE> immediately stops +the procedure it's in, even if there are more instructions below it.) + +<H2>Higher Order Miscellany</H2> + +<P> +<CODE>Map</CODE> combines the partial results into a list, if the second +argument is a list, or into a word, if it's a word. Sometimes this behavior +isn't quite what you want. An alternative is <CODE>map.se</CODE> (map to +sentence), which makes a sentence of the results. Here are some examples. + +<PRE> +? <U>make "numbers [zero one two three four five six seven eight nine]</U> +? <U>show map [item ?+1 :numbers] 5789</U> +fiveseveneightnine +? <U>show map.se [item ?+1 :numbers] 5789</U> +[five seven eight nine] + +? <U>show map [sentence (word "With ?) "You] [in out]</U> +[[Within You] [Without You]] +? <U>show map.se [sentence (word "With ?) "You] [in out]</U> +[Within You Without You] + +? <U>show map.se [sentence ? "Warner] [Yakko Wakko Dot]</U> +[Yakko Warner Wakko Warner Dot Warner] +? <U>show map [sentence ? "Warner] [Yakko Wakko Dot]</U> +[[Yakko Warner] [Wakko Warner] [Dot Warner]] +</PRE> + +<P> +As these examples show, sometimes <CODE>map</CODE> does what you want, but +sometimes <CODE>map.se</CODE> does, depending on the "shape" you want your +result to have. Do you want a word, a sentence, or a structured list? + +<P> +Suppose we have two sets of things, and we want all the pairings of one of +these with one of those. An example will make clear what's desired: + +<PRE> +? <U>show crossproduct [red blue green] [shirt pants]</U> +[[red shirt] [blue shirt] [green shirt] [red pants] [blue pants] + [green pants]] +</PRE> + +<P> +This is a tricky example because there are two different mistakes +we could make. We don't want to "flatten" the result into a sentence: + +<PRE> +[red shirt blue shirt green shirt red pants blue pants green pants] +</PRE> + +<P> +but we also don't want all the shirts in one list and all the +pants in another: + +<PRE> +[[[red shirt] [blue shirt] [green shirt]] + [[red pants] [blue pants] [green pants]]] +</PRE> + +<P> +Here's the solution: + +<PRE> +to crossproduct :these :those +output map.se [prepend.each :these ?] :those +end + +to prepend.each :these :that +output map [sentence ? :that] :these +end +</PRE> + +<P>» Notice that this solution uses both <CODE>map</CODE> and +<CODE>map.se</CODE>. Try to predict what would happen if you used +<CODE>map</CODE> both times, or <CODE>map.se</CODE> both times, or +interchanged the two. Then try it on the computer and be sure you +understand what happens and why! + + +<P> +By the way, this is a case in which we still need a named helper function +despite the use of templates, because otherwise we'd have one template +inside the other, and Logo couldn't figure out which <CODE>?</CODE> to +replace with what: + +<PRE> +to crossproduct :these :those +output map.se [map [sentence ? ?] :these] :those ; (wrong!) +end +</PRE> + +<P> +Just as <CODE>map.se</CODE> is a variant of <CODE>map</CODE>, +<CODE>find</CODE> is a variant of <CODE>filter</CODE>, for the situations in +which you only want to find <EM>one</EM> member that meets the criterion, +rather than all the members. (Perhaps you know in advance that there will +only be one, or perhaps if there are more than one, you don't care which you +get.) + +<PRE> +to spellout :card +output (sentence (butlast :card) "of + (find [equalp last :card first ?] + [hearts spades diamonds clubs])) +end + +? <U>print spellout "5d</U> +5 of diamonds +? <U>print spellout "10h</U> +10 of hearts +</PRE> + +<P> +Sometimes what you want isn't a function at all. You want to take some +<EM>action</EM> for each member of an aggregate. The most common one is to +print each member on a separate line, in situations where you've computed a +long list of things. You can use <CODE>foreach</CODE> with an +<EM>instruction</EM> template, rather than an expression template as used +with the others. The template is the last argument, rather than the first, +to follow the way in which the phrase "for each" is used in English: For +each of these things, do that. + +<PRE> +? <U>foreach (crossproduct [[ultra chocolate] pumpkin [root beer swirl]</U> + <U>ginger] [cone cup]) "print</U> +ultra chocolate cone +pumpkin cone +root beer swirl cone +ginger cone +ultra chocolate cup +pumpkin cup +root beer swirl cup +ginger cup +</PRE> + +<P> +If you look closely at the letters on your computer screen you'll see that +they are made up of little dots. One simple pattern represents each letter +in a rectangle of dots five wide and seven high, like this: + +<PRE> + * ***** ***** **** ***** + * * * * * * * * +* * * * * * * * +***** **** * * * *** +* * * * * * * * +* * * * * * * * +* * ***** ***** **** ***** +</PRE> + +<P> +The following program allows you to spell words on the screen in big letters +like these. Each letter's shape is kept as the value of a global variable +with the letter as its name. (I haven't actually listed all 26 letters.) +The value is a list of seven words, each of which contains five characters, +some combination of spaces and asterisks. + +<PRE> +<A name="say">to say :word</A> +for [row 1 7] [foreach :word [sayrow :row ?] print []] +print [] +end + +to sayrow :row :letter +type item :row thing :letter +type "| | +end + +make "b [|*****| |* *| |* *| |**** | |* *| |* *| |*****|] +make "r [|*****| |* *| |* *| |*****| |* * | |* * | |* *|] +make "i [|*****| | * | | * | | * | | * | | * | |*****|] +make "a [| * | | * * | |* *| |*****| |* *| |* *| |* *|] +make "n [|* *| |** *| |** *| |* * *| |* **| |* **| |* *|] + +? <U>say "brian</U> +***** ***** ***** * * * +* * * * * * * ** * +* * * * * * * ** * +**** ***** * ***** * * * +* * * * * * * * ** +* * * * * * * * ** +***** * * ***** * * * * +</PRE> + +<P>» Modify the program so that <CODE>say</CODE> takes another input, a +number representing the size in which you want to print the letters. If the +number is 1, then the program should work as before. If the number is 2, +each dot should be printed as a two-by-two square of spaces or asterisks; if +the number is 3, a three-by-three square, and so on. +</LI> + +<H2>Repeated Invocation: <CODE>Cascade</CODE></H2> + +<P> +Finally, sometimes you want to compose a function with itself several times: + +<PRE> +? <U>print first bf bf bf bf [The Continuing Story of Bungalow Bill]</U> +Bungalow +? <U>print first (cascade 4 "bf [The Continuing Story of Bungalow Bill])</U> +Bungalow +</PRE> + +<P> +<CODE>Cascade</CODE> takes three inputs. The first is a number, +indicating how many times to invoke the function represented by the second +argument. The third argument is the starting value. + +<PRE> +to power :base :exponent +output cascade :exponent [? * :base] 1 +end + +? <U>print power 2 8</U> +256 + +to range :from :to +output cascade :to-:from [sentence ? (1+last ?)] (sentence :from) +end + +? <U>show range 3 8</U> +[3 4 5 6 7 8] +</PRE> + +<P> +Like <CODE>map</CODE>, <CODE>cascade</CODE> can be used with extra inputs to +deal with more than one thing at a time. One example in which multi-input +<CODE>cascade</CODE> is useful is the Fibonacci sequence. Each number in +the sequence is the sum of the two previous numbers; the first two numbers +are 1. So the sequence starts + +<P><CENTER>1,1,2,3,5,8,13,...</CENTER> + +<P>A formal definition +of the sequence looks like this: + +<P><CENTER><TABLE> +<TR><TD><I>F</I><SMALL><SUB>0</SUB></SMALL> = 1</TD> +<TR><TD><I>F</I><SMALL><SUB>1</SUB></SMALL> = 1</TD> +<TR><TD><I>F</I><SMALL><SUB>n</SUB></SMALL> = <I>F</I><SMALL><SUB>n-1</SUB></SMALL> + +<I>F</I><SMALL><SUB>n-2</SUB></SMALL>,       n>1</TD> +</TABLE></CENTER> + +<P>In order to compute, say, <I>F</I><SMALL><SUB>23</SUB></SMALL>, +we must know both <I>F</I><SMALL><SUB>22</SUB></SMALL> and +<I>F</I><SMALL><SUB>21</SUB></SMALL>. +As we work our way up, we must +always remember the two most recent values, like this: + +<P><CENTER><TABLE> +<TR> +<TH> </TH> +<TH>Most recent value      </TH> +<TH>Next most recent value</TH> +<TR> +<TD>start</TD> +<TD>1</TD> +<TD>0</TD> +<TR> +<TD>step 1</TD> +<TD>1</TD> +<TD>1</TD> +<TR> +<TD>step 2</TD> +<TD>2</TD> +<TD>1</TD> +<TR> +<TD>step 3</TD> +<TD>3</TD> +<TD>2</TD> +<TR> +<TD>step 4</TD> +<TD>5</TD> +<TD>3</TD> +<TR> +<TD>...</TD> +<TD>...</TD> +<TD>...</TD> +<TR> +<TD>step 22      </TD> +<TD><I>F</I><SMALL><SUB>22</SUB></SMALL></TD> +<TD><I>F</I><SMALL><SUB>21</SUB></SMALL></TD> +<TR> +<TD>step 23</TD> +<TD><I>F</I><SMALL><SUB>22</SUB></SMALL>+<I>F</I><SMALL><SUB>21</SUB></SMALL></TD> +<TD><I>F</I><SMALL><SUB>22</SUB></SMALL></TD> +</TABLE></CENTER> + +<P> +To express this using <CODE>cascade</CODE>, we can use <CODE>?1</CODE> to +mean the most recent value and <CODE>?2</CODE> to mean the next most +recent. Then at each step, we need a function to compute the new +<CODE>?1</CODE> by adding the two known values, and a function to copy the +old <CODE>?1</CODE> as the new <CODE>?2</CODE>: + +<PRE> +to fib :n +output (cascade :n [?1+?2] 1 [?1] 0) +end + +? <U>print fib 5</U> +8 +? <U>print fib 23</U> +46368 +</PRE> + +<P> +Another situation in which multi-input <CODE>cascade</CODE> can be useful is +to process every member of a list, using <CODE>?1</CODE> to remember the +already-processed ones and <CODE>?2</CODE> to remember the still-waiting +ones. The simplest example is reversing the words in a sentence: + +<PRE> +to reverse :sent +output (cascade (count :sent) + [sentence (first ?2) ?1] [] + [butfirst ?2] :sent) +end + +? <U>print reverse [how now brown cow]</U> +cow brown now how +</PRE> + +<P><CENTER><TABLE> +<TR align="left"> +<TH> </TH> +<TH><CODE>?1</CODE></TH> +<TH><CODE>?2</CODE></TH> +<TR> +<TD>start</TD> +<TD><CODE>[]</CODE></TD> +<TD><CODE>[how now brown cow]</CODE></TD> +<TR> +<TD>step 1    </TD> +<TD><CODE>[how]</CODE></TD> +<TD><CODE>[now brown cow]</CODE></TD> +<TR> +<TD>step 2</TD> +<TD><CODE>[now how]</CODE></TD> +<TD><CODE>[brown cow]</CODE></TD> +<TR> +<TD>step 3</TD> +<TD><CODE>[brown now how]</CODE></TD> +<TD><CODE>[cow]</CODE></TD> +<TR> +<TD>step 4</TD> +<TD><CODE>[cow brown now how]</CODE>   </TD> +<TD><CODE>[]</CODE></TD> +</TABLE></CENTER> + +<P> +Here is the general notation for multi-input <CODE>cascade</CODE>: + +<PRE> +(cascade <U>howmany</U> <U>function1</U> <U>start1</U> <U>function2</U> <U>start2</U> ...) +</PRE> + +<P> +There must be as many <TT><U>function</U></TT> inputs as +<TT><U>start</U></TT> inputs. Suppose there are <I>n</I> pairs of inputs; +then each of the <TT><U>function</U></TT>s must accept <I>n</I> inputs. The +<TT><U>start</U></TT>s provide the initial values for <CODE>?1</CODE>, +<CODE>?2</CODE>, and so on; each function provides the next value for one of +those. <CODE>Cascade</CODE> returns the final value of <CODE>?1</CODE>. + +<H2>A Mini-project: Mastermind</H2> + +<P> +It's time to put these programming tools to work in a more substantial +project. You're ready to write a computer program that plays a family of +games like Mastermind<SMALL><SUP>TM</SUP></SMALL>. The +computer picks a secret list of colors; +the human player makes guesses. (The number of possible colors can be +changed to tune the difficulty of the game.) At each turn, the program +should tell the player how many colors in the guess are in the correct +positions in the secret list and also how many are in the list, but not at +the same positions. For example, suppose the program's secret colors are + +<PRE> +red green blue violet +</PRE> + +and the player guesses + +<PRE> +red orange yellow green +</PRE> + +<P> +There is one correct-position match (red, because it's the first color in +both lists) and one incorrect-position match (green, because it's second in +the computer's list but fourth in the player's list). + +<P> +In the program, to reduce the amount of typing needed to play the game, +represent each color as a single letter and each list of colors as a word. +In the example above, the computer's secret list is represented as +<CODE>rgbv</CODE> and the player's guess as <CODE>royg</CODE>. + +<P> +There are two possible variations in the rules, depending on whether or not +color lists with duplications (such as <CODE>rgrb</CODE>, in which red +appears twice) are allowed. The program will accept a true-or-false input +to determine whether or not duplicates are allowed. + +<P> +Here's an example of what an interaction with the program +should look like: + +<PRE> +? <U>master "roygbiv 4 "false</U> + +What's your guess? +<U>royg</U> +You have 1 correct-position matches +and 2 incorrect-position matches. + +What's your guess? +<U>rogy</U> +You have 1 correct-position matches +and 2 incorrect-position matches. + +What's your guess? +<U>orygbv</U> +You must guess exactly 4 colors. + +What's your guess? +<U>oryx</U> +The available colors are: roygbiv + +What's your guess? +<U>oryr</U> +No fair guessing the same color twice! + +What's your guess? +<U>oryg</U> +You have 0 correct-position matches +and 3 incorrect-position matches. + +What's your guess? +<U>rbyg</U> +You have 1 correct-position matches +and 2 incorrect-position matches. + +What's your guess? +<U>boyg</U> +You have 0 correct-position matches +and 3 incorrect-position matches. + +What's your guess? +<U>roby</U> +You have 1 correct-position matches +and 3 incorrect-position matches. + +What's your guess? +<U>rybo</U> +You have 2 correct-position matches +and 2 incorrect-position matches. + +What's your guess? +<U>ryob</U> +You win in 8 guesses! +? +</PRE> + +<P> +If you prefer, just jump in and start writing the program. But I have a +particular design in mind, and you may find it easier to follow my plan. +The core of my program is written sequentially, in the form of a +<CODE>for</CODE> instruction that carries out a sequence of steps once for +each guess the user makes. But most of the "smarts" of the program are in +a collection of subprocedures that use functional programming style. That +is, these procedures are operations, not commands; they merely compute and +output a value without taking any actions. Pay attention to how these two +styles fit together. In writing the operations, don't use <CODE>make</CODE> +or <CODE>print</CODE>; each operation will consist of a single +<CODE>output</CODE> instruction. + +<P>» The first task is for the computer to make a random selection from the +available colors. Write two versions: <CODE>choose.dup</CODE> that allows +the same color to be chosen more than once, and <CODE>choose.nodup</CODE> +that does not allow duplication. Each of these operations should take two +inputs: a number, indicating how many colors to choose, and a word of all +the available colors. For example, to choose four colors from the rainbow +without duplication, you'd say + + +<PRE> +? <U>print choose.nodup 4 "roygbiv</U> +briy +</PRE> + +<P> +You'll find the Logo primitive <CODE>pick</CODE> helpful. It takes a +word or list as its input, and returns a randomly chosen member: + +<PRE> +? <U>print pick [Pete John Roger Keith]</U> +John +? <U>print pick [Pete John Roger Keith]</U> +Keith +? <U>print pick "roygbiv</U> +b +</PRE> + +<P> +Writing <CODE>choose.dup</CODE> is a straightforward combination of +<CODE>pick</CODE> and <CODE>cascade</CODE>. + +<P> +<CODE>Choose.nodup</CODE> is a little harder. Since we want to eliminate +any color we choose from further consideration, it's plausible to use a +multi-input <CODE>cascade</CODE> sort of like this: + +<PRE> +(cascade :number-wanted + [<U>add one color</U>] " + [<U>remove that color</U>] :colors) +</PRE> + +<P> +If we always wanted to choose the first available color, this would be just +like the <CODE>reverse</CODE> example earlier. But we want to choose a +color randomly each time. One solution is to <EM>rotate</EM> the available +colors by some random amount, then choose what is now the first color. To +use that idea you'll need a <CODE>rotate</CODE> operation that rotates a +word some random number of times, like this: + +<PRE> +? <U>rotate "roygbiv</U> +ygbivro +? <U>rotate "roygbiv</U> +vroygbi +? <U>rotate "roygbiv</U> +bivroyg +</PRE> + +<P> +You can write <CODE>rotate</CODE> using <CODE>cascade</CODE> along with the +Logo primitive operation <CODE>random</CODE>. <CODE>Random</CODE> takes a +positive integer as its input, and outputs a nonnegative integer less than +its input. For example, <CODE>random 3</CODE> will output <CODE>0</CODE>, +<CODE>1</CODE>, or <CODE>2</CODE>. + +<P>» The second task is to evaluate the player's guess. You'll need an +operation called <CODE>exact</CODE> that takes two words as inputs (you may +assume they are the same length) and outputs the number of correct-position +matches, and another operation called <CODE>inexact</CODE> that computes the +number of wrong-position matches. (You may find it easier to write a helper +procedure <CODE>anymatch</CODE> that takes two words as inputs, but outputs +the total number of matches, regardless of position.) Be sure to write +these so that they work even with the duplicates-allowed rule in effect. +For example, if the secret word is <CODE>rgrb</CODE> and the user guesses +<CODE>yrrr</CODE>, then you must report one exact and one inexact match, not +one exact and two inexact. + + +<PRE> +? <U>print exact "rgrb "yrrr</U> +1 +? <U>print inexact "rgrb "yrrr</U> +1 +? <U>print inexact "royg "rgbo</U> +2 +</PRE> + +<P> +<CODE>Exact</CODE> is a straightforward application of multi-input +<CODE>map</CODE>, since you want to look at each letter of the secret word +along with the same-position letter of the user's guess. My solution to +<CODE>anymatch</CODE> was to use <CODE>map</CODE> to consider each of the +available colors. For each color, the number of matches is the smaller of +the number of times it appears in the secret word and the number of times it +appears in the guess. (You'll need a helper procedure <CODE>howmany</CODE> +that takes two inputs, a letter and a word, and outputs the number of times +that letter occurs in that word.) + +<P>» Up to this point, we've assumed that the player is making legitimate +guesses. A valid guess has the right number of colors, chosen from the set +of available colors, and (perhaps, depending on the chosen rules) with no +color duplicated. Write a predicate <CODE>valid.guessp</CODE> that takes a +guess as its input and returns <CODE>true</CODE> if the guess is valid, +<CODE>false</CODE> otherwise. In this procedure, for the first time in this +project, it's a good idea to violate functional programming style by +printing an appropriate error message when the output will be +<CODE>false</CODE>. + + +<P>» We now have all the tools needed to write the top-level game procedure +<CODE>master</CODE>. This procedure will take three inputs: a word of the +available colors, the number of colors in the secret word, and a +<CODE>true</CODE> or <CODE>false</CODE> to indicate whether or not duplicate +colors are allowed. After using either <CODE>choose.dup</CODE> or +<CODE>choose.nodup</CODE> to pick the secret word, I used a <CODE>for</CODE> +loop to carry out the necessary instructions for each guess. + +<P><A HREF="../v1-toc2.html">(back to Table of Contents)</A> +<P><A HREF="../v1ch4/v1ch4.html"><STRONG>BACK</STRONG></A> +chapter thread <A HREF="../v1ch6/v1ch6.html"><STRONG>NEXT</STRONG></A> + +<P> +<ADDRESS> +<A HREF="../index.html">Brian Harvey</A>, +<CODE>bh@cs.berkeley.edu</CODE> +</ADDRESS> +</BODY> +</HTML> diff --git a/js/games/nluqo.github.io/~bh/v1ch5/initials.gif b/js/games/nluqo.github.io/~bh/v1ch5/initials.gif new file mode 100644 index 0000000..f1eedd4 --- /dev/null +++ b/js/games/nluqo.github.io/~bh/v1ch5/initials.gif Binary files differdiff --git a/js/games/nluqo.github.io/~bh/v1ch5/maperror.gif b/js/games/nluqo.github.io/~bh/v1ch5/maperror.gif new file mode 100644 index 0000000..60ab9eb --- /dev/null +++ b/js/games/nluqo.github.io/~bh/v1ch5/maperror.gif Binary files differdiff --git a/js/games/nluqo.github.io/~bh/v1ch5/mapoper.gif b/js/games/nluqo.github.io/~bh/v1ch5/mapoper.gif new file mode 100644 index 0000000..e516c3b --- /dev/null +++ b/js/games/nluqo.github.io/~bh/v1ch5/mapoper.gif Binary files differdiff --git a/js/games/nluqo.github.io/~bh/v1ch5/v1ch5.html b/js/games/nluqo.github.io/~bh/v1ch5/v1ch5.html new file mode 100644 index 0000000..7bbd997 --- /dev/null +++ b/js/games/nluqo.github.io/~bh/v1ch5/v1ch5.html @@ -0,0 +1,1431 @@ +<HTML> +<HEAD> +<TITLE>Computer Science Logo Style vol 1 ch 5: Functions of Functions</TITLE> +</HEAD> +<BODY> +<CITE>Computer Science Logo Style</CITE> volume 1: +<CITE>Symbolic Computing</CITE> 2/e Copyright (C) 1997 MIT +<H1>Functions of Functions</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/v1ch05.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="../v1ch4/v1ch4.html"><STRONG>BACK</STRONG></A> +chapter thread <A HREF="../v1ch6/v1ch6.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> +We now have many of the tools we need to write computer programs. We have +the primitive operations for arithmetic computation, the primitive +operations to manipulate words and sentences, and a way to choose between +alternative computations. One thing that we still lack is a way to deal +systematically with data <EM>aggregates</EM>--collections of data. We want +to be able to say "carry out this computation for each member of that +aggregate." Processing large amounts of data uniformly is one of the +abilities that distinguish computers from mere pocket calculators. + +<H2>The Problem: <CODE>Initials</CODE></H2> + +<P> +To make this concrete, we'll look at a very simple example. I'd like to +write a procedure that can figure out a person's initials, like this: + +<PRE> +? <U>show initials [George Harrison]</U> +[G H] +</PRE> + +<P> +One obvious approach is to find the initials of the first name and the +last name: + +<PRE> +to initials :name +output sentence (first first :name) (first last :name) +end +</PRE> + +<P> +The trouble is that this approach doesn't work for people with middle +names. We'd like our <CODE>initials</CODE> procedure to be able to handle +any length name. But it doesn't: + +<PRE> +? <U>show initials [John Alec Entwistle]</U> +[J E] +? <U>show initials [Peter Blair Denis Bernard Noone]</U> +[P N] +</PRE> + +<P> +What we want is this: + +<PRE> +? <U>show initials.in.our.dreams [John Alec Entwistle]</U> +[J A E] +? <U>show initials.in.our.dreams [Peter Blair Denis Bernard Noone]</U> +[P B D B N] +</PRE> + +<P> +If we knew that the input would have exactly five names, we +could extract the first letter of each of them explicitly. But you never +know when some smart alec will ask you to + +<PRE> +show initials [Princess Angelina Contessa Louisa Francesca ~ + Banana Fana Bo Besca the Third] +</PRE> + +<H2>One Solution: Numeric Iteration</H2> + +<P> +If you've programmed before in other languages, then one solution will +immediately occur to you. You create a variable <CODE>n</CODE> whose value +is the number of words in the input, then you have a variable <CODE>i</CODE> +that takes on all possible values from 1 to <CODE>n</CODE>, and you select +the <CODE>i</CODE>th word from the input and pull out its first letter. +Most languages have a special notation for this sort of computation: + +<PRE> +for i = 1 to n : ... : next i <I>(BASIC)</I> +for 1 := 1 to n do begin ... end <I>(Pascal)</I> +for (i=1; i<=n; i++) { ... } <I>(C)</I> +</PRE> + +<P> +All of these have the same meaning: Carry out some instructions +(the part shown as <CODE>...</CODE> above) repeatedly, first with the variable +named <CODE>i</CODE> having the value <CODE>1</CODE>, then with <CODE>i</CODE> equal to <CODE>2</CODE>, +and so on, up to <CODE>i</CODE> equal to <CODE>n</CODE>. This technique is called +<EM>numeric iteration.</EM> "Iteration" means repetition, and it's +"numeric" iteration because the repetition is controlled by a variable +that takes on a sequence of numeric values. + +<P> +We can do the same thing in Logo, although, as we'll soon learn, it's not +the usual approach that Logo programmers take to this problem. + +<PRE> +to initials :name +local "result +make "result [] +for [i 1 [count :name]] ~ + [make "result sentence :result first (item :i :name)] +output :result +end +</PRE> + +<P> +(The reason I declare <CODE>result</CODE> as local, but not <CODE>i</CODE>, +is that Logo's <CODE>for</CODE> automatically makes its index variable local +to the <CODE>for</CODE> itself. There is no variable <CODE>i</CODE> outside +of the <CODE>for</CODE> instruction.) + +<P> +The command <CODE>for</CODE> takes two inputs. The second input is an +instruction list that will be carried out repeatedly. The first input +controls the repetition; it is a list of either three or four members: a +variable name, a starting value, a limit value, and an optional increment. +(The variable named by the first member of the list is called the <EM>index +variable.</EM> For example: + +<PRE> +? <U>for [number 4 7] [print :number]</U> +4 +5 +6 +7 +? <U>for [value 4 11 3] [print :value]</U> +4 +7 +10 +</PRE> + +<P> +In the first example, <CODE>number</CODE> takes on all integer values +between 4 and 7. In the second, <CODE>value</CODE>'s starting value is 4, +and on each repetition its new value is 3 more than last time. +<CODE>Value</CODE> never actually has its limiting value of 11; the next +value after 10 would have been 13, but that's bigger than the limit. + +<P> +<CODE>For</CODE> can count downward instead of upward: + +<PRE> +? <U>for [i 7 5] [print :i]</U> +7 +6 +5 +? <U>for [n 15 2 -6] [print :n]</U> +15 +9 +3 +? <U>for [x 15 2 6] [print :x]</U> +? +</PRE> + +<P> The last example has no effect. Why? The increment of 6 implies that +this invocation of <CODE>for</CODE> should count upward, which means that the +<CODE>for</CODE> continues until the value of <CODE>x</CODE> is greater than +the limit, 2. But the starting value, 15, is <EM>already</EM> greater than +2. + +<P> If no increment is given in the first input to <CODE>for</CODE>, then +<CODE>for</CODE> will use either <CODE>1</CODE> or <CODE>-1</CODE> as the +increment, whichever is compatible with the starting and limit values. + +<P> +Although I've been using constant numbers as the starting value, limit +value, and increment in these examples, <CODE>for</CODE> can handle any Logo +expression, represented as a list, for each of these: + +<PRE> +to spread :ends +for [digit [first :ends] [last :ends]] [type :digit] +print [] +end + +? <U>spread 19</U> +123456789 +? <U>spread 83</U> +876543 +</PRE> + +<P> +More formally, the effect of <CODE>for</CODE> is as follows. First it creates the +local index variable and assigns it the starting value. Then <CODE>for</CODE> +carries out three steps repeatedly: testing, action, and incrementing. The +testing step is to compare the current value of the index variable with the +limit value. If the index variable has passed the limit, then the <CODE>for</CODE> +is finished. ("Passed" means that the index variable is greater than the +limit, if the increment is positive, or that the index variable is less than +the limit, if the increment is negative.) The action step is to evaluate +the instructions in the second input to <CODE>for</CODE>. The incrementing step is +to assign a new value to the index variable by adding the increment to the +old value. Then comes another round of testing, action, and incrementing. + +<P> +So, for example, if we give Logo the instruction + +<PRE> +show initials [Raymond Douglas Davies] +</PRE> + +<P> +then the <CODE>for</CODE> instruction within <CODE>initials</CODE> is equivalent +to this sequence of instructions: + +<PRE> +local "i ; initialize index variable +make "i 1 + +if (:i > 3) [stop] ; testing +make "result (se :result first "Raymond) ; action (result is [R]) +make "i :i+1 ; incrementing (i is 2) + +if (:i > 3) [stop] ; testing +make "result (se :result first "Douglas) ; action (result is [R D]) +make "i :i+1 ; incrementing (i is 3) + +if (:i > 3) [stop] ; testing +make "result (se :result first "Davies) ; action (result is [R D D]) +make "i :i+1 ; incrementing (i is 4) + +if (:i > 3) [stop] ; testing +</PRE> + +<P> +except that the <CODE>stop</CODE> instruction in the testing step stops +only the <CODE>for</CODE> instruction, not the <CODE>initials</CODE> procedure. + +<H2>Critique of Numeric Iteration</H2> + +<P> +Computers were originally built to deal with numbers. Numeric iteration +matches closely the behind-the-scenes sequence of steps by which computers +actually work. That's why just about every programming language supports +this style of programming. + +<P> +Nevertheless, a <CODE>for</CODE> instruction isn't anything like the way +you, a human being, would solve the <CODE>initials</CODE> problem without a +computer. First of all, you wouldn't begin by counting the number of words +in the name; you really don't have to know that. You'd just say, for +example, "First of Raymond is R; first of Douglas is D; first of Davies is +D." When you ran out of names, you'd stop. + +<P> +The manipulation of the <CODE>result</CODE> variable to collect the results also +seems unnatural. You wouldn't think, "I'm going to start with an empty +result; then, whatever value <CODE>result</CODE> has, I'll throw in an R; then, +whatever value <CODE>result</CODE> now has, I'll throw in a D" and so on. + +<P> +In fact, if you had to explain to someone else how to solve this problem, +you probably wouldn't talk about a sequence of steps at all. Rather, you'd +draw a picture like this one: + +<P><CENTER><IMG SRC="initials.gif" ALT="<P>figure: initials"></CENTER> + +<P> +To explain the picture, you'd say something like "Just take the +<CODE>first</CODE> of each word." You wouldn't even mention the need to put the +results together into a sentence; you'd take that for granted. + +<P> +In Logo we can write an <CODE>initials</CODE> procedure using the same way of +thinking that you'd use in English: + +<PRE> +to initials :name +output map "first :name +end +</PRE> + +<P> +The <CODE>map</CODE> procedure means "collect the results of +doing <EM>this</EM> for each of <EM>those.</EM>" + +<P> +As this example illustrates, <CODE>map</CODE> is easy to use. But it's a +little hard to talk about, because it's a function of a function. So first +we'll take a detour to talk more precisely about functions in general. + +<H2>What's a Function?</H2> + +<P> +A <EM>function</EM> is a rule for turning one value (called the +<EM>argument</EM>) into another. If +you've studied algebra you'll remember numeric function rules such as + +<P><CENTER><I>f</I>(<I>x</I>) = 3<I>x</I>-6</CENTER> + +<P> +but not all functions are numeric, and not all rules need be expressed as +algebraic formulas. For example, here is the Instrument function, which +takes a Beatle as its argument and returns his instrument: + +<P><CENTER><TABLE> +<TR align="left"> +<TH><U>argument</U>       </TH> +<TH><U>result</U></TH> +<TR> +<TD>John</TD> +<TD>rhythm guitar</TD> +<TR> +<TD>Paul</TD> +<TD>bass guitar</TD> +<TR> +<TD>George</TD> +<TD>lead guitar</TD> +<TR> +<TD>Ringo</TD> +<TD>drums</TD> +</TABLE></CENTER> + +<P> +This particular function has only four possible arguments. Other +functions, like <I>f</I>(<I>x</I>) above, may have infinitely many possible arguments. +The set of possible arguments is called the <EM>domain</EM> of the +function. Similarly, the set of possible result values is called the +<EM>range</EM> of the function.* + +<SMALL><BLOCKQUOTE><SMALL><SUP>*</SUP>It's a little awkward to talk about +the domain of a function that takes two arguments. That is, it's easy to +say that the domain of the function represented by the <CODE>first</CODE> operation +is words or lists, but how do we describe <CODE>item</CODE>? We could loosely say +"its domain is numbers and words or lists," but that sounds as if either +argument could be any of those. The most precise way to say it is this: +"The domain of <CODE>item</CODE> is pairs of values, in which the first member of +the pair is a positive integer and the second member is a word or list of +length greater than or equal to the first member of the pair." But for +ordinary purposes we just rephrase the sentence to avoid the word "domain" +altogether: "<CODE>Item</CODE> takes two inputs; the first must be a positive +integer and the second must be a word or list..."</SMALL></BLOCKQUOTE></SMALL> + +<P> +Functions can be represented in many ways. (We've seen two in this +section: formulas and tables.) One way to represent a function is with a +Logo operation. Here are Logo representations of the two functions we've +discussed: + +<PRE> +to f :x +output 3*:x - 6 +end + +to instrument :beatle +if :beatle = "John [output [rhythm guitar]] +if :beatle = "Paul [output [bass guitar]] +if :beatle = "George [output [lead guitar]] +if :beatle = "Ringo [output [drums]] +end +</PRE> + +<P> +(What if we give <CODE>instrument</CODE> an input that's not in the +domain of the function? In that case, it won't output any value, and a Logo +error message will result. Some people would argue that the procedure +should provide its own, more specific error message.) + +<P> +I've been careful to say that the Logo operation <EM>represents</EM> the +function, not that it <EM>is</EM> the function. In particular, two Logo +procedures can compute the same function--the same relationship between +input and output values--by different methods. For example, +consider these Logo operations: + +<PRE> +to f :x to g :x +output 3*:x - 6 output 3 * (:x-2) +end end +</PRE> + +<P> +The Logo operations <CODE>f</CODE> and <CODE>g</CODE> carry out two different +computations, but they represent the same function. For example, to compute +<CODE>f 10</CODE> we say 3×10=30, 30-6=24; to compute +<CODE>g 10</CODE> we say 10-2=8, 3×8=24. Different computations, +but the same answer. Functional programming means, in part, focusing our +attention on the inputs and outputs of programs rather than on the sequence +of computational steps. + +<P> +Just as a Logo operation represents a function, the procedure's inputs +similarly <EM>represent</EM> the arguments to the corresponding function. +For example, that instrument function I presented earlier has Beatles (that +is to say, people) as its domain and has musical instruments as its range. +But Logo doesn't have people or instruments as data types, and so the +procedure <CODE>instrument</CODE> takes as its input <EM>the name of</EM> a +Beatle (that is, a word) and returns as its output <EM>the name of</EM> an +instrument (a sentence). Instrument is a function from Beatles to +instruments, but <CODE>instrument</CODE> is an operation from words to +sentences. + +<P> +We're about to see a similar situation when we explore <CODE>map</CODE>. +The map function--that is, the function that <CODE>map</CODE> +represents--is a <EM>function of functions.</EM> One of the arguments to +the map function is itself a function. The corresponding input to Logo's +<CODE>map</CODE> procedure should be a procedure. But it turns out that +Logo doesn't quite allow a procedure to be an input to another procedure; +instead, we must use the <EM>name</EM> of the procedure as the input, just as +we use the name of a Beatle as the input to <CODE>instrument</CODE>. + +<P> +I know this sounds like lawyer talk, and we haven't written any programs for +a while. But here's why this is important: In order to understand the +<EM>purpose</EM> of <CODE>map</CODE>, you have to think about the map +function, whose domain is functions (and other stuff, as we'll see in a +moment). But in order to understand the <EM>notation</EM> that you use with +<CODE>map</CODE> in Logo, you have to think in terms of the Logo operation, +whose input is words (names of procedures). You have to be clear about this +representation business in order to be able to shift mentally between these +viewpoints. + +<H2>Functions of Functions: <CODE>Map</CODE></H2> + +<P> +<CODE>Map</CODE> takes two inputs. The first is a word, which must be the name +of a one-input Logo operation. The second can be any datum. The output +from <CODE>map</CODE> is either a word or a list, whichever is the type of the +second input. The members of the output are the results of applying the +named operation to the members of the second input. + +<PRE> +? <U>show map "first [Rod Argent]</U> +[R A] +</PRE> + +<P> +In this example, the output is a list of two members, just as the second +input is a list of two members. Each member of the output is the result of +applying <CODE>first</CODE> to one of the members of <CODE>map</CODE>'s +second input. + +<P> +Many people, when they first meet <CODE>map</CODE>, are confused by the +quoting of its first input. After all, I made a fuss back in Chapter +2 about the difference between these two examples: + +<PRE> +? <U>print Hello</U> +I don't know how to Hello +? <U>print "Hello</U> +Hello +</PRE> + +<P> +You learned that a quoted word means the word itself, while an unquoted word +asks Logo to invoke a procedure. But now, when I want to use the +<CODE>first</CODE> procedure as input to <CODE>map</CODE>, I'm quoting its +name. Why? + +<P> +All that effort about the domains of functions should help you understand +the notation used here. Start by ignoring the Logo notation and think about +the domain of the map function. We want the map function to have +<EM>another function,</EM> the function "first" in this case, as one of its +arguments: + +<P><CENTER><IMG SRC="https://people.eecs.berkeley.edu/~bh/v1ch5/mapfun.gif" ALT="<P>figure: mapfun"></CENTER> + +<P> +It's tempting to say that in Logo, a function is represented by a procedure, +so <CODE>map</CODE> represents map, and <CODE>first</CODE> represents first. +If this were algebra notation, I'd say <I>map</I>(<I>first</I>, <I>Rod Argent</I>), +so in Logo I'll say + +<PRE> +show map first [Rod Argent] ;; wrong! +</PRE> + +<P> +But when a Logo instruction has two unquoted procedure names in a row, that +doesn't mean that the second function is used as argument to the first! +Instead, it means that <EM>the output from invoking</EM> the second function +is used as the argument to the first. In this case, we'd be +<EM>composing</EM> <CODE>map</CODE> and <CODE>first</CODE>: + +<P><CENTER><IMG SRC="maperror.gif" ALT="<P>figure: maperror"></CENTER> + +<P> +As the plumbing diagram shows, the list that we intended as the second input +to <CODE>map</CODE> actually ends up as the input to <CODE>first</CODE>, and +Logo will complain because <CODE>map</CODE> isn't given enough inputs. + +<P> +Instead, as I said earlier, we must use <EM>the name of</EM> the +<CODE>first</CODE> procedure to represent it. That gives this diagram: + +<P><CENTER><IMG SRC="mapoper.gif" ALT="<P>figure: mapoper"></CENTER> + +<P> +Here's another simple example. Logo has a primitive operation +<CODE>uppercase</CODE> that takes a word as input, and outputs the same word +but in all capital letters: + +<PRE> +? <U>print uppercase "young</U> +YOUNG +</PRE> + +<P> +What if we want to translate an entire sentence to capital letters? The +<CODE>uppercase</CODE> primitive doesn't accept a sentence as its input: + +<PRE> +? <U>show uppercase [neil young]</U> +uppercase doesn't like [neil young] as input. +</PRE> + +<P> +But we can use <CODE>map</CODE> to translate each word separately and +combine the results: + +<PRE> +? <U>show map "uppercase [neil young]</U> +[NEIL YOUNG] +</PRE> + +<P> +Ordinarily <CODE>map</CODE> works with one-argument functions. But we can +give <CODE>map</CODE> extra arguments (by enclosing the invocation of +<CODE>map</CODE> in parentheses, as usual) so that it can work with +functions of more than one argument. + +<PRE> +? <U>show (map "item [2 1 2 3] [john paul george ringo])</U> +[o p e n] +? <U>show (map "sum [1 2 3] [40 50 60] [700 800 900])</U> +[741 852 963] +</PRE> + +<P> +Each input after the first provides values for one input to the mapped +function. For example, <CODE>[2 1 2 3]</CODE> provides four values for the +first input to <CODE>item</CODE>. The input lists must all have the same +length (two lists of length four in the <CODE>item</CODE> example, three +lists of length three in the <CODE>sum</CODE> example). + +<P> +In the examples so far, the input data have been lists. Here's an example +in which we use <CODE>map</CODE> with words. Let's say we're writing a +program to play Hangman, the word game in which one player guesses letters +in a secret word chosen by the other player. At first the guesser sees only +a row of dashes indicating the number of letters in the word; for each +guess, more letters are revealed. We aren't going to write the entire +program yet, but we're ready to write the operation that takes the secret +word, and a list of the letters that have been guessed so far, and outputs a +row of letters and dashes as appropriate. + +<PRE> +to hangword :secret :guessed +output map "hangletter :secret +end + +to hangletter :letter +output ifelse memberp :letter :guessed [:letter] ["_] +end + +? <U>print hangword "potsticker [e t a o i n]</U> +_ot_ti__er +? <U>print hangword "gelato [e t a o i n]</U> +_e_ato +</PRE> + +<P> +Notice that <CODE>hangletter</CODE> depends on Logo's dynamic scope to have +access to <CODE>hangword</CODE>'s local variable named <CODE>guessed</CODE>. + +<P> +» Write an operation <CODE>exaggerate</CODE> that takes a sentence as +input and outputs an exaggerated version: + +<PRE> +? <U>print exaggerate [I ate 3 potstickers]</U> +I ate 6 potstickers +? <U>print exaggerate [The chow fun is good here]</U> +The chow fun is great here +</PRE> + +<P> +It should double all the numbers in the sentence, and replace +"good" with "great," "bad" with "terrible," and so on. + +<P> +A function whose domain or range includes functions is called a +<EM>higher order function.</EM> The function represented by +<CODE>map</CODE> is a higher order function. (We may speak loosely and say +that <CODE>map</CODE> is a higher order function, as long as you remember +that Logo procedures aren't really functions!) It's tempting to say that the +<CODE>map</CODE> procedure itself is a "higher order procedure," but in +Logo that isn't true. Procedures aren't data in Logo; the only data types +are words and lists. That's why the input to <CODE>map</CODE> is a word, +the name of a procedure, and not the procedure itself. Some languages do +treat procedures themselves as data. In particular, the language Scheme is +a close relative of Logo that can handle procedures as data. If this way of +thinking appeals to you, consider learning Scheme next! + +<H2>Higher Order Selection: <CODE>Filter</CODE></H2> + +<P> +The purpose of <CODE>map</CODE> is to <EM>transform</EM> each member of an +aggregate (a list or a word) by applying some function to it. Another +higher order function, <CODE>filter</CODE>, is used to <EM>select</EM> some +members of an aggregate, but not others, based on a criterion expressed as a +predicate function. For example: + +<PRE> +? <U>show filter "numberp [76 trombones, 4 calling birds, and 8 days]</U> +[76 4 8] + +to vowelp :letter +output memberp :letter "aeiou +end + +? <U>show filter "vowelp "spaghetti</U> +aei + +to beatlep :person +output memberp :person [John Paul George Ringo] +end + +? <U>show filter "beatlep [Bob George Jeff Roy Tom]</U> +[George] +</PRE> + +<P> +What happens if we use the <CODE>initials</CODE> procedure that we wrote with +people's names in mind for other kinds of names, such as organizations or +book titles? Some of them work well: + +<PRE> +? <U>show initials [Computer Science Logo Style]</U> +[C S L S] +? <U>show initials [American Civil Liberties Union]</U> +[A C L U] +</PRE> + +<P> +but others don't give quite the results we'd like: + +<PRE> +? <U>show initials [Association for Computing Machinery]</U> +[A f C M] +? <U>show initials [People's Republic of China]</U> +[P R o C] +</PRE> + +<P> +We'd like to eliminate words like "for" and "of" before taking the first +letters of the remaining words. This is a job for <CODE>filter</CODE>: + +<PRE> +to importantp :word +output not memberp :word [the an a of for by with in to and or] +end + +to initials :name +output map "first (filter "importantp :name) +end + +? <U>show initials [Association for Computing Machinery]</U> +[A C M] +? <U>show initials [People's Republic of China]</U> +[P R C] +</PRE> + +<H2>Many to One: <CODE>Reduce</CODE></H2> + +<P> +Of course, what we'd <EM>really</EM> like is to have those initials in the +form of a single word: ACLU, CSLS, ACM, and so on. For this purpose we +need yet another higher order function, one that invokes a combining +function to join the members of an aggregate. + +<PRE> +? <U>show reduce "word [C S L S]</U> +CSLS +? <U>show reduce "sum [3 4 5 6]</U> +18 +? <U>show reduce "sentence "UNICEF</U> +[U N I C E F] +</PRE> + +<P> +<CODE>Reduce</CODE> takes two inputs. The first must be the name of a +two-input operation; the second can be any <EM>nonempty</EM> word or list. + +<PRE> +to acronym :name +output reduce "word initials :name +end +</PRE> + +<P> +In practice, the first input to <CODE>reduce</CODE> won't be any old +operation; it'll be a <EM>constructor.</EM> It'll be something that doesn't +care about the grouping of operands; for example, <CODE>sum</CODE> is a good +choice but <CODE>difference</CODE> is problematic because we don't know +whether + +<PRE> +reduce "difference [5 6 7] +</PRE> + +<P> +means 5-(6-7) or (5-6)-7, and the grouping affects the answer. Almost +all the time, the constructor will be <CODE>word</CODE>, +<CODE>sentence</CODE>, <CODE>sum</CODE>, or <CODE>product</CODE>. But +here's an example of another one: + +<PRE> +to bigger :a :b +output ifelse :a > :b [:a] [:b] +end + +to biggest :nums +output reduce "bigger :nums +end + +? <U>show biggest [5 7 781 42 8]</U> +781 +</PRE> + +<H2>Choosing the Right Tool</H2> + +<P> +So far you've seen three higher order functions: <CODE>map</CODE>, +<CODE>filter</CODE>, and <CODE>reduce</CODE>. How do you decide which one to +use for a particular problem? + +<P> +<CODE>Map</CODE> transforms each member of a word or list individually. The +result contains as many members as the input. + +<P><CENTER><IMG SRC="https://people.eecs.berkeley.edu/~bh/v1ch5/map.gif" ALT="<P>figure: map"></CENTER> + +<P> +<CODE>Filter</CODE> selects certain members of a word or list and discards the +others. The members of the result are members of the input, without +transformation, but the result may be smaller than the original. + +<P><CENTER><IMG SRC="filter.gif" ALT="<P>figure: filter"></CENTER> + +<P> +<CODE>Reduce</CODE> transforms the entire word or list into a single result +by combining all of the members in some way. + +<P><CENTER><IMG SRC="https://people.eecs.berkeley.edu/~bh/v1ch5/reduce.gif" ALT="<P>figure: reduce"></CENTER> + +<H2>Anonymous Functions</H2> + +<P> +In several of the examples in this chapter, I've had to write "helper" +procedures such as <CODE>hangletter</CODE>, <CODE>importantp</CODE>, and +<CODE>bigger</CODE> that will never be used independently, but are needed +only to provide the function argument to a higher order function. It would +be simpler if we could avoid writing these as separate procedures. + +<P> +Does that sound confusing? This is one of those ideas for which an example +is worth 1000 words: + +<PRE> +to hangword :secret :guessed +output map [ifelse memberp ? :guessed [?] ["_]] :secret +end +</PRE> + +<P> +Until now, the first input to <CODE>map</CODE> has always been a word, +used to represent the function with that word as its name. In this example +we see how a nameless function can be represented: as a list containing a +Logo expression, but with question marks where the function's argument +belongs. Such a list is called a <EM>template.</EM> + +<PRE> +? <U>show filter [memberp ? [John Paul George Ringo]] ~</U> + <U>[Bob George Jeff Roy Tom]</U> +[George] +</PRE> + +<P> +Anonymous functions of more than one argument are a little uglier. Instead +of <CODE>?</CODE> for the argument, you must use <CODE>?1</CODE> for the +first, <CODE>?2</CODE> for the second, and so on. + +<PRE> +to biggest :nums +output reduce [ifelse ?1 > ?2 [?1] [?2]] :nums +end +</PRE> + +<P> +Notice that the templates don't say <CODE>output</CODE>, as the named +procedures did. That's because procedures are made of +<EM>instructions,</EM> whereas these are <EM>expression</EM> templates. +When input values are "plugged in" for the question marks, the template +becomes a Logo expression, which means that when evaluated it has a value. +If the template said <CODE>output</CODE>, it would be saying to use that +value as the output <EM>from the procedure containing it!</EM> (I'm just +repeating the point made earlier that <CODE>output</CODE> immediately stops +the procedure it's in, even if there are more instructions below it.) + +<H2>Higher Order Miscellany</H2> + +<P> +<CODE>Map</CODE> combines the partial results into a list, if the second +argument is a list, or into a word, if it's a word. Sometimes this behavior +isn't quite what you want. An alternative is <CODE>map.se</CODE> (map to +sentence), which makes a sentence of the results. Here are some examples. + +<PRE> +? <U>make "numbers [zero one two three four five six seven eight nine]</U> +? <U>show map [item ?+1 :numbers] 5789</U> +fiveseveneightnine +? <U>show map.se [item ?+1 :numbers] 5789</U> +[five seven eight nine] + +? <U>show map [sentence (word "With ?) "You] [in out]</U> +[[Within You] [Without You]] +? <U>show map.se [sentence (word "With ?) "You] [in out]</U> +[Within You Without You] + +? <U>show map.se [sentence ? "Warner] [Yakko Wakko Dot]</U> +[Yakko Warner Wakko Warner Dot Warner] +? <U>show map [sentence ? "Warner] [Yakko Wakko Dot]</U> +[[Yakko Warner] [Wakko Warner] [Dot Warner]] +</PRE> + +<P> +As these examples show, sometimes <CODE>map</CODE> does what you want, but +sometimes <CODE>map.se</CODE> does, depending on the "shape" you want your +result to have. Do you want a word, a sentence, or a structured list? + +<P> +Suppose we have two sets of things, and we want all the pairings of one of +these with one of those. An example will make clear what's desired: + +<PRE> +? <U>show crossproduct [red blue green] [shirt pants]</U> +[[red shirt] [blue shirt] [green shirt] [red pants] [blue pants] + [green pants]] +</PRE> + +<P> +This is a tricky example because there are two different mistakes +we could make. We don't want to "flatten" the result into a sentence: + +<PRE> +[red shirt blue shirt green shirt red pants blue pants green pants] +</PRE> + +<P> +but we also don't want all the shirts in one list and all the +pants in another: + +<PRE> +[[[red shirt] [blue shirt] [green shirt]] + [[red pants] [blue pants] [green pants]]] +</PRE> + +<P> +Here's the solution: + +<PRE> +to crossproduct :these :those +output map.se [prepend.each :these ?] :those +end + +to prepend.each :these :that +output map [sentence ? :that] :these +end +</PRE> + +<P>» Notice that this solution uses both <CODE>map</CODE> and +<CODE>map.se</CODE>. Try to predict what would happen if you used +<CODE>map</CODE> both times, or <CODE>map.se</CODE> both times, or +interchanged the two. Then try it on the computer and be sure you +understand what happens and why! + + +<P> +By the way, this is a case in which we still need a named helper function +despite the use of templates, because otherwise we'd have one template +inside the other, and Logo couldn't figure out which <CODE>?</CODE> to +replace with what: + +<PRE> +to crossproduct :these :those +output map.se [map [sentence ? ?] :these] :those ; (wrong!) +end +</PRE> + +<P> +Just as <CODE>map.se</CODE> is a variant of <CODE>map</CODE>, +<CODE>find</CODE> is a variant of <CODE>filter</CODE>, for the situations in +which you only want to find <EM>one</EM> member that meets the criterion, +rather than all the members. (Perhaps you know in advance that there will +only be one, or perhaps if there are more than one, you don't care which you +get.) + +<PRE> +to spellout :card +output (sentence (butlast :card) "of + (find [equalp last :card first ?] + [hearts spades diamonds clubs])) +end + +? <U>print spellout "5d</U> +5 of diamonds +? <U>print spellout "10h</U> +10 of hearts +</PRE> + +<P> +Sometimes what you want isn't a function at all. You want to take some +<EM>action</EM> for each member of an aggregate. The most common one is to +print each member on a separate line, in situations where you've computed a +long list of things. You can use <CODE>foreach</CODE> with an +<EM>instruction</EM> template, rather than an expression template as used +with the others. The template is the last argument, rather than the first, +to follow the way in which the phrase "for each" is used in English: For +each of these things, do that. + +<PRE> +? <U>foreach (crossproduct [[ultra chocolate] pumpkin [root beer swirl]</U> + <U>ginger] [cone cup]) "print</U> +ultra chocolate cone +pumpkin cone +root beer swirl cone +ginger cone +ultra chocolate cup +pumpkin cup +root beer swirl cup +ginger cup +</PRE> + +<P> +If you look closely at the letters on your computer screen you'll see that +they are made up of little dots. One simple pattern represents each letter +in a rectangle of dots five wide and seven high, like this: + +<PRE> + * ***** ***** **** ***** + * * * * * * * * +* * * * * * * * +***** **** * * * *** +* * * * * * * * +* * * * * * * * +* * ***** ***** **** ***** +</PRE> + +<P> +The following program allows you to spell words on the screen in big letters +like these. Each letter's shape is kept as the value of a global variable +with the letter as its name. (I haven't actually listed all 26 letters.) +The value is a list of seven words, each of which contains five characters, +some combination of spaces and asterisks. + +<PRE> +<A name="say">to say :word</A> +for [row 1 7] [foreach :word [sayrow :row ?] print []] +print [] +end + +to sayrow :row :letter +type item :row thing :letter +type "| | +end + +make "b [|*****| |* *| |* *| |**** | |* *| |* *| |*****|] +make "r [|*****| |* *| |* *| |*****| |* * | |* * | |* *|] +make "i [|*****| | * | | * | | * | | * | | * | |*****|] +make "a [| * | | * * | |* *| |*****| |* *| |* *| |* *|] +make "n [|* *| |** *| |** *| |* * *| |* **| |* **| |* *|] + +? <U>say "brian</U> +***** ***** ***** * * * +* * * * * * * ** * +* * * * * * * ** * +**** ***** * ***** * * * +* * * * * * * * ** +* * * * * * * * ** +***** * * ***** * * * * +</PRE> + +<P>» Modify the program so that <CODE>say</CODE> takes another input, a +number representing the size in which you want to print the letters. If the +number is 1, then the program should work as before. If the number is 2, +each dot should be printed as a two-by-two square of spaces or asterisks; if +the number is 3, a three-by-three square, and so on. +</LI> + +<H2>Repeated Invocation: <CODE>Cascade</CODE></H2> + +<P> +Finally, sometimes you want to compose a function with itself several times: + +<PRE> +? <U>print first bf bf bf bf [The Continuing Story of Bungalow Bill]</U> +Bungalow +? <U>print first (cascade 4 "bf [The Continuing Story of Bungalow Bill])</U> +Bungalow +</PRE> + +<P> +<CODE>Cascade</CODE> takes three inputs. The first is a number, +indicating how many times to invoke the function represented by the second +argument. The third argument is the starting value. + +<PRE> +to power :base :exponent +output cascade :exponent [? * :base] 1 +end + +? <U>print power 2 8</U> +256 + +to range :from :to +output cascade :to-:from [sentence ? (1+last ?)] (sentence :from) +end + +? <U>show range 3 8</U> +[3 4 5 6 7 8] +</PRE> + +<P> +Like <CODE>map</CODE>, <CODE>cascade</CODE> can be used with extra inputs to +deal with more than one thing at a time. One example in which multi-input +<CODE>cascade</CODE> is useful is the Fibonacci sequence. Each number in +the sequence is the sum of the two previous numbers; the first two numbers +are 1. So the sequence starts + +<P><CENTER>1,1,2,3,5,8,13,...</CENTER> + +<P>A formal definition +of the sequence looks like this: + +<P><CENTER><TABLE> +<TR><TD><I>F</I><SMALL><SUB>0</SUB></SMALL> = 1</TD> +<TR><TD><I>F</I><SMALL><SUB>1</SUB></SMALL> = 1</TD> +<TR><TD><I>F</I><SMALL><SUB>n</SUB></SMALL> = <I>F</I><SMALL><SUB>n-1</SUB></SMALL> + +<I>F</I><SMALL><SUB>n-2</SUB></SMALL>,       n>1</TD> +</TABLE></CENTER> + +<P>In order to compute, say, <I>F</I><SMALL><SUB>23</SUB></SMALL>, +we must know both <I>F</I><SMALL><SUB>22</SUB></SMALL> and +<I>F</I><SMALL><SUB>21</SUB></SMALL>. +As we work our way up, we must +always remember the two most recent values, like this: + +<P><CENTER><TABLE> +<TR> +<TH> </TH> +<TH>Most recent value      </TH> +<TH>Next most recent value</TH> +<TR> +<TD>start</TD> +<TD>1</TD> +<TD>0</TD> +<TR> +<TD>step 1</TD> +<TD>1</TD> +<TD>1</TD> +<TR> +<TD>step 2</TD> +<TD>2</TD> +<TD>1</TD> +<TR> +<TD>step 3</TD> +<TD>3</TD> +<TD>2</TD> +<TR> +<TD>step 4</TD> +<TD>5</TD> +<TD>3</TD> +<TR> +<TD>...</TD> +<TD>...</TD> +<TD>...</TD> +<TR> +<TD>step 22      </TD> +<TD><I>F</I><SMALL><SUB>22</SUB></SMALL></TD> +<TD><I>F</I><SMALL><SUB>21</SUB></SMALL></TD> +<TR> +<TD>step 23</TD> +<TD><I>F</I><SMALL><SUB>22</SUB></SMALL>+<I>F</I><SMALL><SUB>21</SUB></SMALL></TD> +<TD><I>F</I><SMALL><SUB>22</SUB></SMALL></TD> +</TABLE></CENTER> + +<P> +To express this using <CODE>cascade</CODE>, we can use <CODE>?1</CODE> to +mean the most recent value and <CODE>?2</CODE> to mean the next most +recent. Then at each step, we need a function to compute the new +<CODE>?1</CODE> by adding the two known values, and a function to copy the +old <CODE>?1</CODE> as the new <CODE>?2</CODE>: + +<PRE> +to fib :n +output (cascade :n [?1+?2] 1 [?1] 0) +end + +? <U>print fib 5</U> +8 +? <U>print fib 23</U> +46368 +</PRE> + +<P> +Another situation in which multi-input <CODE>cascade</CODE> can be useful is +to process every member of a list, using <CODE>?1</CODE> to remember the +already-processed ones and <CODE>?2</CODE> to remember the still-waiting +ones. The simplest example is reversing the words in a sentence: + +<PRE> +to reverse :sent +output (cascade (count :sent) + [sentence (first ?2) ?1] [] + [butfirst ?2] :sent) +end + +? <U>print reverse [how now brown cow]</U> +cow brown now how +</PRE> + +<P><CENTER><TABLE> +<TR align="left"> +<TH> </TH> +<TH><CODE>?1</CODE></TH> +<TH><CODE>?2</CODE></TH> +<TR> +<TD>start</TD> +<TD><CODE>[]</CODE></TD> +<TD><CODE>[how now brown cow]</CODE></TD> +<TR> +<TD>step 1    </TD> +<TD><CODE>[how]</CODE></TD> +<TD><CODE>[now brown cow]</CODE></TD> +<TR> +<TD>step 2</TD> +<TD><CODE>[now how]</CODE></TD> +<TD><CODE>[brown cow]</CODE></TD> +<TR> +<TD>step 3</TD> +<TD><CODE>[brown now how]</CODE></TD> +<TD><CODE>[cow]</CODE></TD> +<TR> +<TD>step 4</TD> +<TD><CODE>[cow brown now how]</CODE>   </TD> +<TD><CODE>[]</CODE></TD> +</TABLE></CENTER> + +<P> +Here is the general notation for multi-input <CODE>cascade</CODE>: + +<PRE> +(cascade <U>howmany</U> <U>function1</U> <U>start1</U> <U>function2</U> <U>start2</U> ...) +</PRE> + +<P> +There must be as many <TT><U>function</U></TT> inputs as +<TT><U>start</U></TT> inputs. Suppose there are <I>n</I> pairs of inputs; +then each of the <TT><U>function</U></TT>s must accept <I>n</I> inputs. The +<TT><U>start</U></TT>s provide the initial values for <CODE>?1</CODE>, +<CODE>?2</CODE>, and so on; each function provides the next value for one of +those. <CODE>Cascade</CODE> returns the final value of <CODE>?1</CODE>. + +<H2>A Mini-project: Mastermind</H2> + +<P> +It's time to put these programming tools to work in a more substantial +project. You're ready to write a computer program that plays a family of +games like Mastermind<SMALL><SUP>TM</SUP></SMALL>. The +computer picks a secret list of colors; +the human player makes guesses. (The number of possible colors can be +changed to tune the difficulty of the game.) At each turn, the program +should tell the player how many colors in the guess are in the correct +positions in the secret list and also how many are in the list, but not at +the same positions. For example, suppose the program's secret colors are + +<PRE> +red green blue violet +</PRE> + +and the player guesses + +<PRE> +red orange yellow green +</PRE> + +<P> +There is one correct-position match (red, because it's the first color in +both lists) and one incorrect-position match (green, because it's second in +the computer's list but fourth in the player's list). + +<P> +In the program, to reduce the amount of typing needed to play the game, +represent each color as a single letter and each list of colors as a word. +In the example above, the computer's secret list is represented as +<CODE>rgbv</CODE> and the player's guess as <CODE>royg</CODE>. + +<P> +There are two possible variations in the rules, depending on whether or not +color lists with duplications (such as <CODE>rgrb</CODE>, in which red +appears twice) are allowed. The program will accept a true-or-false input +to determine whether or not duplicates are allowed. + +<P> +Here's an example of what an interaction with the program +should look like: + +<PRE> +? <U>master "roygbiv 4 "false</U> + +What's your guess? +<U>royg</U> +You have 1 correct-position matches +and 2 incorrect-position matches. + +What's your guess? +<U>rogy</U> +You have 1 correct-position matches +and 2 incorrect-position matches. + +What's your guess? +<U>orygbv</U> +You must guess exactly 4 colors. + +What's your guess? +<U>oryx</U> +The available colors are: roygbiv + +What's your guess? +<U>oryr</U> +No fair guessing the same color twice! + +What's your guess? +<U>oryg</U> +You have 0 correct-position matches +and 3 incorrect-position matches. + +What's your guess? +<U>rbyg</U> +You have 1 correct-position matches +and 2 incorrect-position matches. + +What's your guess? +<U>boyg</U> +You have 0 correct-position matches +and 3 incorrect-position matches. + +What's your guess? +<U>roby</U> +You have 1 correct-position matches +and 3 incorrect-position matches. + +What's your guess? +<U>rybo</U> +You have 2 correct-position matches +and 2 incorrect-position matches. + +What's your guess? +<U>ryob</U> +You win in 8 guesses! +? +</PRE> + +<P> +If you prefer, just jump in and start writing the program. But I have a +particular design in mind, and you may find it easier to follow my plan. +The core of my program is written sequentially, in the form of a +<CODE>for</CODE> instruction that carries out a sequence of steps once for +each guess the user makes. But most of the "smarts" of the program are in +a collection of subprocedures that use functional programming style. That +is, these procedures are operations, not commands; they merely compute and +output a value without taking any actions. Pay attention to how these two +styles fit together. In writing the operations, don't use <CODE>make</CODE> +or <CODE>print</CODE>; each operation will consist of a single +<CODE>output</CODE> instruction. + +<P>» The first task is for the computer to make a random selection from the +available colors. Write two versions: <CODE>choose.dup</CODE> that allows +the same color to be chosen more than once, and <CODE>choose.nodup</CODE> +that does not allow duplication. Each of these operations should take two +inputs: a number, indicating how many colors to choose, and a word of all +the available colors. For example, to choose four colors from the rainbow +without duplication, you'd say + + +<PRE> +? <U>print choose.nodup 4 "roygbiv</U> +briy +</PRE> + +<P> +You'll find the Logo primitive <CODE>pick</CODE> helpful. It takes a +word or list as its input, and returns a randomly chosen member: + +<PRE> +? <U>print pick [Pete John Roger Keith]</U> +John +? <U>print pick [Pete John Roger Keith]</U> +Keith +? <U>print pick "roygbiv</U> +b +</PRE> + +<P> +Writing <CODE>choose.dup</CODE> is a straightforward combination of +<CODE>pick</CODE> and <CODE>cascade</CODE>. + +<P> +<CODE>Choose.nodup</CODE> is a little harder. Since we want to eliminate +any color we choose from further consideration, it's plausible to use a +multi-input <CODE>cascade</CODE> sort of like this: + +<PRE> +(cascade :number-wanted + [<U>add one color</U>] " + [<U>remove that color</U>] :colors) +</PRE> + +<P> +If we always wanted to choose the first available color, this would be just +like the <CODE>reverse</CODE> example earlier. But we want to choose a +color randomly each time. One solution is to <EM>rotate</EM> the available +colors by some random amount, then choose what is now the first color. To +use that idea you'll need a <CODE>rotate</CODE> operation that rotates a +word some random number of times, like this: + +<PRE> +? <U>rotate "roygbiv</U> +ygbivro +? <U>rotate "roygbiv</U> +vroygbi +? <U>rotate "roygbiv</U> +bivroyg +</PRE> + +<P> +You can write <CODE>rotate</CODE> using <CODE>cascade</CODE> along with the +Logo primitive operation <CODE>random</CODE>. <CODE>Random</CODE> takes a +positive integer as its input, and outputs a nonnegative integer less than +its input. For example, <CODE>random 3</CODE> will output <CODE>0</CODE>, +<CODE>1</CODE>, or <CODE>2</CODE>. + +<P>» The second task is to evaluate the player's guess. You'll need an +operation called <CODE>exact</CODE> that takes two words as inputs (you may +assume they are the same length) and outputs the number of correct-position +matches, and another operation called <CODE>inexact</CODE> that computes the +number of wrong-position matches. (You may find it easier to write a helper +procedure <CODE>anymatch</CODE> that takes two words as inputs, but outputs +the total number of matches, regardless of position.) Be sure to write +these so that they work even with the duplicates-allowed rule in effect. +For example, if the secret word is <CODE>rgrb</CODE> and the user guesses +<CODE>yrrr</CODE>, then you must report one exact and one inexact match, not +one exact and two inexact. + + +<PRE> +? <U>print exact "rgrb "yrrr</U> +1 +? <U>print inexact "rgrb "yrrr</U> +1 +? <U>print inexact "royg "rgbo</U> +2 +</PRE> + +<P> +<CODE>Exact</CODE> is a straightforward application of multi-input +<CODE>map</CODE>, since you want to look at each letter of the secret word +along with the same-position letter of the user's guess. My solution to +<CODE>anymatch</CODE> was to use <CODE>map</CODE> to consider each of the +available colors. For each color, the number of matches is the smaller of +the number of times it appears in the secret word and the number of times it +appears in the guess. (You'll need a helper procedure <CODE>howmany</CODE> +that takes two inputs, a letter and a word, and outputs the number of times +that letter occurs in that word.) + +<P>» Up to this point, we've assumed that the player is making legitimate +guesses. A valid guess has the right number of colors, chosen from the set +of available colors, and (perhaps, depending on the chosen rules) with no +color duplicated. Write a predicate <CODE>valid.guessp</CODE> that takes a +guess as its input and returns <CODE>true</CODE> if the guess is valid, +<CODE>false</CODE> otherwise. In this procedure, for the first time in this +project, it's a good idea to violate functional programming style by +printing an appropriate error message when the output will be +<CODE>false</CODE>. + + +<P>» We now have all the tools needed to write the top-level game procedure +<CODE>master</CODE>. This procedure will take three inputs: a word of the +available colors, the number of colors in the secret word, and a +<CODE>true</CODE> or <CODE>false</CODE> to indicate whether or not duplicate +colors are allowed. After using either <CODE>choose.dup</CODE> or +<CODE>choose.nodup</CODE> to pick the secret word, I used a <CODE>for</CODE> +loop to carry out the necessary instructions for each guess. + +<P><A HREF="../v1-toc2.html">(back to Table of Contents)</A> +<P><A HREF="../v1ch4/v1ch4.html"><STRONG>BACK</STRONG></A> +chapter thread <A HREF="../v1ch6/v1ch6.html"><STRONG>NEXT</STRONG></A> + +<P> +<ADDRESS> +<A HREF="../index.html">Brian Harvey</A>, +<CODE>bh@cs.berkeley.edu</CODE> +</ADDRESS> +</BODY> +</HTML> |
