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/v2ch5 | |
| parent | 5d012c6c011a9dedf7d0a098e456206244eb5a0f (diff) | |
| download | tour-562a9a52d599d9a05f871404050968a5fd282640.tar.gz | |
*
Diffstat (limited to 'js/games/nluqo.github.io/~bh/v2ch5')
| -rw-r--r-- | js/games/nluqo.github.io/~bh/v2ch5/prgdat.html | 499 | ||||
| -rw-r--r-- | js/games/nluqo.github.io/~bh/v2ch5/v2ch5.html | 499 |
2 files changed, 998 insertions, 0 deletions
diff --git a/js/games/nluqo.github.io/~bh/v2ch5/prgdat.html b/js/games/nluqo.github.io/~bh/v2ch5/prgdat.html new file mode 100644 index 0000000..4023574 --- /dev/null +++ b/js/games/nluqo.github.io/~bh/v2ch5/prgdat.html @@ -0,0 +1,499 @@ +<HTML> +<HEAD> +<TITLE>Computer Science Logo Style vol 2 ch 5: Program as Data</TITLE> +</HEAD> +<BODY> +<CITE>Computer Science Logo Style</CITE> volume 2: +<CITE>Advanced Techniques</CITE> 2/e Copyright (C) 1997 MIT +<H1>Program as Data</H1> + +<TABLE width="100%"><TR><TD> +<IMG SRC="../csls2.jpg" ALT="cover photo"> +<TD><TABLE> +<TR><TD align="right"><CITE><A HREF="http://www.cs.berkeley.edu/~bh/">Brian +Harvey</A><BR>University of California, Berkeley</CITE> +<TR><TD align="right"><BR> +<TR><TD align="right"><A HREF="../pdf/v2ch05.pdf">Download PDF version</A> +<TR><TD align="right"><A HREF="../v2-toc2.html">Back to Table of Contents</A> +<TR><TD align="right"><A HREF="../v2ch4/v2ch4.html"><STRONG>BACK</STRONG></A> +chapter thread <A HREF="../v2ch6/v2ch6.html"><STRONG>NEXT</STRONG></A> +<TR><TD align="right"><A HREF="https://mitpress.mit.edu/books/computer-science-logo-style-second-edition-volume-2">MIT +Press web page for <CITE>Computer Science Logo Style</CITE></A> +</TABLE></TABLE> + +<HR> + +<P> +In most programming languages there is a sharp distinction between +<EM>program</EM> and <EM>data.</EM> Data are the things you can +manipulate in your program, things like numbers and letters. These +things live in variables, which can be given new values by your +program. But the program itself is not subject to manipulation; it's +something you write ahead of time, and then it remains fixed. + +<P> +In Logo the distinction is not so sharp. We've made extensive use of one +mechanism by which a program can manipulate itself: the instruction lists +that are used as inputs to <CODE>run</CODE>, <CODE>if</CODE>, and so on are +data that can be computed by a program. For example, the solitaire program +in Chapter 4 constructs a list of Logo instruction lists, each of +which would move a card to some other legal position, and then says + +<PRE> +run first :onto +</PRE> + +<P> +to move the card to the first such position. + +<H2><CODE>Text</CODE> and <CODE>Define</CODE></H2> + +<P> +In this chapter we'll use a pair of more advanced tools that allow a +program to create more program. <CODE>Run</CODE> deals with a single +<EM>instruction;</EM> now we'll be able to examine and create +<EM>procedures.</EM> + +<P> +<CODE>Text</CODE> is an operation that takes one input, a word. That word +must be the name of a user-defined procedure. The output from +<CODE>text</CODE> is a list. The first member of that list is a list +containing the names of the inputs to the chosen procedure. (If the +procedure has no inputs, the list will be empty.)* The remaining +members of the output list are instruction lists, one for each line in the +definition of the procedure. + +<P> +<SMALL><BLOCKQUOTE><SMALL><SUP>*</SUP>Berkeley Logo allows user-defined +procedures with <EM>optional</EM> inputs. For such a procedure, this first +sublist may contain lists, representing optional inputs, as well as words, +representing required inputs.</SMALL></BLOCKQUOTE></SMALL> + +<P> +Here is an example. Suppose we've defined the procedure + +<PRE> +to opinion :yes :no +print sentence [I like] :yes +print sentence [I hate] :no +end +</PRE> + +<P> +Here's what the text of that procedure looks like: + +<PRE> +? <U>show text "opinion</U> +[[yes no] [print sentence [I like] :yes] [print sentence [I hate] :no]] +</PRE> + +<P> +In this example the output from <CODE>text</CODE> is a list with three +members. The first member is a list containing the words <CODE>yes</CODE> +and <CODE>no</CODE>, the names of <CODE>opinion</CODE>'s inputs. (Note that +the colons that are used to indicate inputs in a title line are <EM>not</EM> +used here.) The second and third members of the output list are instruction +lists, one for each line in the definition. (Note that there is no +<CODE>end</CODE> line in the definition; as I've remarked before, that line +isn't an instruction in the procedure because <CODE>end</CODE> isn't a +command.) + +<P> +The opposite of <CODE>text</CODE> is the command <CODE>define</CODE>. This +command takes two inputs. The first must be a word and the second a list. +The effect of <CODE>define</CODE> is to define a procedure whose name is the +first input and whose text is the second input. You can use +<CODE>define</CODE> to define a new procedure or to change the definition of +an old one. For example, I might redefine <CODE>opinion</CODE>: + +<PRE> +? <U>define "opinion [[yes no] [print sentence :yes [is yummy.]]</U> + <U>[print sentence :no [is yucky.]]]</U> +? <U>opinion [Ice cream] "Cheese</U> +Ice cream is yummy. +Cheese is yucky. +? <U>po "opinion</U> +to opinion :yes :no +print sentence :yes [is yummy.] +print sentence :no [is yucky.] +end +</PRE> + +<P> +Instead of replacing an old definition with an entirely new one, we +can use <CODE>define</CODE> and <CODE>text</CODE> together to change a procedure's +definition: + +<PRE> +? <U>define "opinion lput [print sentence :no "stinks!] ~</U> + <U>butlast text "opinion</U> +? <U>opinion "Logo "Basic</U> +Logo is yummy. +Basic stinks! +</PRE> + +<P> +(Of course, I didn't have to redefine the same procedure +name. I could have said + +<PRE> +? <U>define "strong.opinion ~</U> + <U>lput [print sentence :no "stinks!] butlast text "opinion</U> +</PRE> + +<P> +and then I would have had two procedures, the unchanged +<CODE>opinion</CODE> and the new version named <CODE>strong.opinion</CODE>.) + +<P> +It may be instructive to consider the analogy between <EM>variables,</EM> +which hold data, and <EM>procedures,</EM> which hold instructions. +Variables are given values with the <CODE>make</CODE> command and examined +with the operation <CODE>thing</CODE>. Procedures are given definitions with +the <CODE>define</CODE> command and examined with the operation +<CODE>text</CODE>. (There is no abbreviation for <CODE>text</CODE>-quote, +however, like the dots abbreviation for <CODE>thing</CODE>-quote.) + +<P> +To illustrate <CODE>define</CODE> and <CODE>text</CODE>, I've used them in +instructions typed in at top level. In practice, you wouldn't use +them that way; it's easier to examine a procedure with <CODE>po</CODE> and to +change its definition with <CODE>edit</CODE>. <CODE>Text</CODE> and <CODE>define</CODE> +are meant to be used not at top level but inside a program. + +<H2>Automated Definition</H2> + +<P> +Early in the first volume I defined the operation <CODE>second</CODE> this way: + +<PRE> +to second :thing +output first butfirst :thing +end +</PRE> + +<P> +Suppose I want more operations following this model, to be +called <CODE>third</CODE>, <CODE>fourth</CODE>, and so on. I could define them all +by hand or I could write a program to do it for me: + +<PRE> +to ordinals +ord1 [second third fourth fifth sixth seventh] [output first butfirst] +end + +to ord1 :names :instr +if emptyp :names [stop] +define first :names list [thing] (lput ":thing :instr) +ord1 (butfirst :names) (lput "butfirst :instr) +end + +? <U>ordinals</U> +? <U>po "fifth</U> +to fifth :thing +output first butfirst butfirst butfirst butfirst :thing +end +</PRE> + +<P> +(The name <CODE>ordinals</CODE> comes from the phrase <EM>ordinal +numbers,</EM> which is what things like "third" are called. Regular +numbers like "three" are called <EM>cardinal numbers.</EM>) This procedure +automatically defined new procedures named <CODE>second</CODE> through +<CODE>seventh</CODE>, each with one more <CODE>butfirst</CODE> in its +instruction line. + +<H2>A Single-Keystroke Program Generator</H2> + +<P> +A fairly common thing to do in Logo is to write a little program that +lets you type a single character on the keyboard to carry out some +instruction. For example, teachers of very young children sometimes +use a program that accepts <CODE>F</CODE> to move the turtle forward some +distance, <CODE>B</CODE> for back, and <CODE>L</CODE> and <CODE>R</CODE> for left and +right. What I want to write is a <EM>program-writing program</EM> that +will accept a name and a list of keystrokes and instructions as +inputs and define a procedure with that name that understands those +instructions. + +<PRE> +to onekey :name :list +local "text +make "text [[] [local "char] [print [Type ? for help]] + [make "char readchar]] +foreach :list [make "text lput (sentence [if equalp :char] + (word "" first ?) + butfirst ?) + :text] +make "text lput (lput (list "foreach :list ""print) + [if equalp :char "?]) ~ + :text +make "text lput (list :name) :text +define :name :text +end +</PRE> + +<P> +If we use this program with the instruction + +<PRE> +onekey "instant [[F [forward 20]] [B [back 20]] + [L [left 15]] [R [right 15]]] +</PRE> + +<P> +then it creates the following procedure: + +<PRE> +to instant +local "char +print [type ? for help] +make "char readchar +if equalp :char "F [forward 20] +if equalp :char "B [back 20] +if equalp :char "L [left 15] +if equalp :char "R [right 15] +if equalp :char "? [foreach [[F [forward 20]] [B [back 20]] + [L [left 15]] [R [right 15]]] + "print] +instant +end +</PRE> + +<P> +In addition to illustrating the use of <CODE>define</CODE>, this program +demonstrates how <CODE>sentence</CODE>, <CODE>list</CODE>, and <CODE>lput</CODE> can +all be useful in constructing lists, when you have to combine some +constant members with some variable members. + +<P> +Of course, if we only want to make one <CODE>instant</CODE> program, it's +easier just to type it in. An automatic procedure like <CODE>onekey</CODE> +is useful when you want to create several different procedures like +<CODE>instant</CODE>, each with a different "menu" of characters. For +example, consider these instructions: + +<PRE> +onekey "instant [[F [forward 20]] [B [back 20]] + [L [left 15]] [R [right 15]] [P [pens]]] +onekey "pens [[U [penup stop]] [D [pendown stop]] [E [penerase stop]]] +</PRE> + +<P> +With these definitions, typing <CODE>P</CODE> to <CODE>instant</CODE> +prepares to accept a pen command from the second list. In effect, +<CODE>instant</CODE> recognizes two-letter commands <CODE>PU</CODE> for <CODE>penup</CODE> +and so on, except that the sequence <CODE>P?</CODE> will display the help +information for just the pen commands. Here's another example: + +<PRE> +onekey "tinyturns [[F [forward 20]] [B [back 20]] + [L [left 5]] [R [right 5]] [H [hugeturns]]] +onekey "hugeturns [[F [forward 20]] [B [back 20]] + [L [left 45]] [R [right 45]] [T [tinyturns]]] +</PRE> + +<H2>Procedure Cross-Reference Listings</H2> + +<P> +When you're working on a very large project, it's easy to lose track +of which procedure invokes which other one. We can use the computer +to help solve this problem by +creating a <EM>cross-reference listing</EM> for all +the procedures in a project. For every procedure +in the project, a cross-reference listing tells which other procedures +invoke that one. If you write long procedures, it can also be helpful +to list which instruction line in procedure <CODE>A</CODE> invokes procedure +<CODE>B</CODE>. + +<P> +The general strategy will be to look through the <CODE>text</CODE> of every +procedure, looking for the name of the procedure we're interested in. +Suppose we're finding all the references to procedure <CODE>X</CODE> and +we're looking through procedures <CODE>A</CODE>, <CODE>B</CODE>, and +<CODE>C</CODE>. For each line of each procedure, we want to know whether +the word <CODE>X</CODE> appears in that line. (Of course you would not +really name a procedure <CODE>A</CODE> or <CODE>X</CODE>. You'd use +meaningful names. This is just an example.) We can't, however, just test + +<PRE> +memberp "x :instr +</PRE> + +<P> +(I'm imagining that the variable <CODE>instr</CODE> contains an +instruction line.) The reason is that a procedure invocation can be +part of a <EM>sublist</EM> of the instruction list if <CODE>X</CODE> is +invoked by way of something like <CODE>if</CODE>. For example, the word +<CODE>X</CODE> is not a member of the list + +<PRE> +[if emptyp :list [x :foo stop]] +</PRE> + +<P> +But it's a member of a member. (Earlier I made a big fuss about the fact +that if that instruction were part of procedure <CODE>A</CODE>, it's +actually <CODE>if</CODE> that invokes <CODE>X</CODE>, not <CODE>A</CODE>. +That's the true story, for the Logo interpreter. But for purposes of a +cross-reference listing, it does us no good to know that <CODE>if</CODE> +invokes <CODE>X</CODE>; what we want to know is which procedure definition to +look at if we want to find the instruction that uses <CODE>X</CODE>.) + +<P> +So the first thing we need is a procedure <CODE>submemberp</CODE> that takes +inputs like those of <CODE>memberp</CODE> but outputs <CODE>true</CODE> if the +first input is a member of the second, or a member of a member, and so +on. + +<PRE> +to submemberp :thing :list +if emptyp :list [output "false] +if equalp :thing first :list [output "true] +if listp first :list ~ + [if submemberp :thing first :list [output "true]] +output submemberp :thing butfirst :list +end +</PRE> + +<P> +Now we want a procedure that will take two words as input, both of +which are the names of procedures, and will print a list of all the +references to the first procedure in the text of the second. + +<PRE> +to reference :target :examinee +ref1 :target :examinee butfirst text :examinee 1 +end + +to ref1 :target :examinee :instrs :linenum +if emptyp :instrs [stop] +if submemberp :target first :instrs ~ + [print sentence "| | (word :examinee "\( :linenum "\) )] +ref1 :target :examinee butfirst :instrs :linenum+1 +end +</PRE> + +<P> +<CODE>Reference</CODE> uses <CODE>butfirst text :examinee</CODE> as the third +input to <CODE>ref1</CODE> to avoid the list of inputs to the procedure we're +examining. That's because one of those inputs might have the same name as +the <CODE>target</CODE> procedure, and we'd get a false indication of +success. (In the body of the definition of <CODE>:examinee</CODE>, any +reference to a variable named <CODE>X</CODE> will not use the word +<CODE>X</CODE> but rather the word <CODE>"X</CODE> or the word +<CODE>:X</CODE>. You may find that statement confusing. When you type an +<EM>instruction</EM> like + +<PRE> +print "foo +</PRE> + +<P> +the Logo evaluator interprets <CODE>"foo</CODE> as a request for the word +<CODE>foo</CODE>, quoted (as opposed to evaluated). So <CODE>print</CODE> +won't print a quotation mark. But if we look at the <EM>list</EM> + +<PRE> +[print "foo] +</PRE> + +<P> +then we are not, right now, evaluating it as a Logo +instruction. The second member of that list is the word <CODE>"foo</CODE>, +quote mark and all.) + +<P> +We can still get "false hits," finding the word <CODE>X</CODE> +(or whatever procedure name we're looking for) in an instruction list, +but not being used as a procedure name: + +<PRE> +print [w x y z] +</PRE> + +<P> +But cases like that will be relatively rare compared to the +cases of variables and procedures with the same name. + +<P> +The reason I'm printing spaces before the information is that I'm +working toward a listing that will look like this: + +<PRE> +target1 + proca(3) + procb(1) + procc(4) +target2 + procb(3) + procb(4) +</PRE> + +<P> +This means that the procedure named <CODE>target1</CODE> is invoked +in each of the procedures <CODE>proca</CODE>, <CODE>procb</CODE>, and <CODE>procc</CODE>; +procedure <CODE>target2</CODE> is invoked by <CODE>procb</CODE> on two different +instruction lines. + +<P> +Okay, now we can find references to one specific procedure within the +text of another specific procedure. Now we want to look for +references to one procedure within <EM>all</EM> the procedures making up +a project. + +<PRE> +to xref :target :list +print :target +foreach :list [reference :target ?] +end +</PRE> + +<P> +We're almost done. Now we want to apply <CODE>xref</CODE> to every +procedure in the project. This involves another run through the list +of projects: + +<PRE> +to xrefall :list +foreach :list [xref ? :list] +end +</PRE> + +<P> +To use this program to make a cross-reference listing of +itself, you'd say + +<PRE> +xrefall [xrefall xref reference ref1 submemberp] +</PRE> + +<P> +To cross-reference all of the procedures in your workspace, +you'd say + +<PRE> +xrefall procedures +</PRE> + +<P> +If you try this program on a project with a large number of procedures, +you should expect it to take a <EM>long</EM> time. If there +are five procedures, we have to examine each of them for +references to each of them, so we invoke <CODE>reference</CODE> 25 times. If +there are 10 procedures, we invoke <CODE>reference</CODE> 100 times! In +general, the number of invocations is the square of the number of +procedures. The fancy way to say this is that the program "takes +quadratic time" or that it "behaves quadratically." + +<P><A HREF="../v2-toc2.html">(back to Table of Contents)</A> +<P><A HREF="../v2ch4/v2ch4.html"><STRONG>BACK</STRONG></A> +chapter thread <A HREF="../v2ch6/v2ch6.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/v2ch5/v2ch5.html b/js/games/nluqo.github.io/~bh/v2ch5/v2ch5.html new file mode 100644 index 0000000..4023574 --- /dev/null +++ b/js/games/nluqo.github.io/~bh/v2ch5/v2ch5.html @@ -0,0 +1,499 @@ +<HTML> +<HEAD> +<TITLE>Computer Science Logo Style vol 2 ch 5: Program as Data</TITLE> +</HEAD> +<BODY> +<CITE>Computer Science Logo Style</CITE> volume 2: +<CITE>Advanced Techniques</CITE> 2/e Copyright (C) 1997 MIT +<H1>Program as Data</H1> + +<TABLE width="100%"><TR><TD> +<IMG SRC="../csls2.jpg" ALT="cover photo"> +<TD><TABLE> +<TR><TD align="right"><CITE><A HREF="http://www.cs.berkeley.edu/~bh/">Brian +Harvey</A><BR>University of California, Berkeley</CITE> +<TR><TD align="right"><BR> +<TR><TD align="right"><A HREF="../pdf/v2ch05.pdf">Download PDF version</A> +<TR><TD align="right"><A HREF="../v2-toc2.html">Back to Table of Contents</A> +<TR><TD align="right"><A HREF="../v2ch4/v2ch4.html"><STRONG>BACK</STRONG></A> +chapter thread <A HREF="../v2ch6/v2ch6.html"><STRONG>NEXT</STRONG></A> +<TR><TD align="right"><A HREF="https://mitpress.mit.edu/books/computer-science-logo-style-second-edition-volume-2">MIT +Press web page for <CITE>Computer Science Logo Style</CITE></A> +</TABLE></TABLE> + +<HR> + +<P> +In most programming languages there is a sharp distinction between +<EM>program</EM> and <EM>data.</EM> Data are the things you can +manipulate in your program, things like numbers and letters. These +things live in variables, which can be given new values by your +program. But the program itself is not subject to manipulation; it's +something you write ahead of time, and then it remains fixed. + +<P> +In Logo the distinction is not so sharp. We've made extensive use of one +mechanism by which a program can manipulate itself: the instruction lists +that are used as inputs to <CODE>run</CODE>, <CODE>if</CODE>, and so on are +data that can be computed by a program. For example, the solitaire program +in Chapter 4 constructs a list of Logo instruction lists, each of +which would move a card to some other legal position, and then says + +<PRE> +run first :onto +</PRE> + +<P> +to move the card to the first such position. + +<H2><CODE>Text</CODE> and <CODE>Define</CODE></H2> + +<P> +In this chapter we'll use a pair of more advanced tools that allow a +program to create more program. <CODE>Run</CODE> deals with a single +<EM>instruction;</EM> now we'll be able to examine and create +<EM>procedures.</EM> + +<P> +<CODE>Text</CODE> is an operation that takes one input, a word. That word +must be the name of a user-defined procedure. The output from +<CODE>text</CODE> is a list. The first member of that list is a list +containing the names of the inputs to the chosen procedure. (If the +procedure has no inputs, the list will be empty.)* The remaining +members of the output list are instruction lists, one for each line in the +definition of the procedure. + +<P> +<SMALL><BLOCKQUOTE><SMALL><SUP>*</SUP>Berkeley Logo allows user-defined +procedures with <EM>optional</EM> inputs. For such a procedure, this first +sublist may contain lists, representing optional inputs, as well as words, +representing required inputs.</SMALL></BLOCKQUOTE></SMALL> + +<P> +Here is an example. Suppose we've defined the procedure + +<PRE> +to opinion :yes :no +print sentence [I like] :yes +print sentence [I hate] :no +end +</PRE> + +<P> +Here's what the text of that procedure looks like: + +<PRE> +? <U>show text "opinion</U> +[[yes no] [print sentence [I like] :yes] [print sentence [I hate] :no]] +</PRE> + +<P> +In this example the output from <CODE>text</CODE> is a list with three +members. The first member is a list containing the words <CODE>yes</CODE> +and <CODE>no</CODE>, the names of <CODE>opinion</CODE>'s inputs. (Note that +the colons that are used to indicate inputs in a title line are <EM>not</EM> +used here.) The second and third members of the output list are instruction +lists, one for each line in the definition. (Note that there is no +<CODE>end</CODE> line in the definition; as I've remarked before, that line +isn't an instruction in the procedure because <CODE>end</CODE> isn't a +command.) + +<P> +The opposite of <CODE>text</CODE> is the command <CODE>define</CODE>. This +command takes two inputs. The first must be a word and the second a list. +The effect of <CODE>define</CODE> is to define a procedure whose name is the +first input and whose text is the second input. You can use +<CODE>define</CODE> to define a new procedure or to change the definition of +an old one. For example, I might redefine <CODE>opinion</CODE>: + +<PRE> +? <U>define "opinion [[yes no] [print sentence :yes [is yummy.]]</U> + <U>[print sentence :no [is yucky.]]]</U> +? <U>opinion [Ice cream] "Cheese</U> +Ice cream is yummy. +Cheese is yucky. +? <U>po "opinion</U> +to opinion :yes :no +print sentence :yes [is yummy.] +print sentence :no [is yucky.] +end +</PRE> + +<P> +Instead of replacing an old definition with an entirely new one, we +can use <CODE>define</CODE> and <CODE>text</CODE> together to change a procedure's +definition: + +<PRE> +? <U>define "opinion lput [print sentence :no "stinks!] ~</U> + <U>butlast text "opinion</U> +? <U>opinion "Logo "Basic</U> +Logo is yummy. +Basic stinks! +</PRE> + +<P> +(Of course, I didn't have to redefine the same procedure +name. I could have said + +<PRE> +? <U>define "strong.opinion ~</U> + <U>lput [print sentence :no "stinks!] butlast text "opinion</U> +</PRE> + +<P> +and then I would have had two procedures, the unchanged +<CODE>opinion</CODE> and the new version named <CODE>strong.opinion</CODE>.) + +<P> +It may be instructive to consider the analogy between <EM>variables,</EM> +which hold data, and <EM>procedures,</EM> which hold instructions. +Variables are given values with the <CODE>make</CODE> command and examined +with the operation <CODE>thing</CODE>. Procedures are given definitions with +the <CODE>define</CODE> command and examined with the operation +<CODE>text</CODE>. (There is no abbreviation for <CODE>text</CODE>-quote, +however, like the dots abbreviation for <CODE>thing</CODE>-quote.) + +<P> +To illustrate <CODE>define</CODE> and <CODE>text</CODE>, I've used them in +instructions typed in at top level. In practice, you wouldn't use +them that way; it's easier to examine a procedure with <CODE>po</CODE> and to +change its definition with <CODE>edit</CODE>. <CODE>Text</CODE> and <CODE>define</CODE> +are meant to be used not at top level but inside a program. + +<H2>Automated Definition</H2> + +<P> +Early in the first volume I defined the operation <CODE>second</CODE> this way: + +<PRE> +to second :thing +output first butfirst :thing +end +</PRE> + +<P> +Suppose I want more operations following this model, to be +called <CODE>third</CODE>, <CODE>fourth</CODE>, and so on. I could define them all +by hand or I could write a program to do it for me: + +<PRE> +to ordinals +ord1 [second third fourth fifth sixth seventh] [output first butfirst] +end + +to ord1 :names :instr +if emptyp :names [stop] +define first :names list [thing] (lput ":thing :instr) +ord1 (butfirst :names) (lput "butfirst :instr) +end + +? <U>ordinals</U> +? <U>po "fifth</U> +to fifth :thing +output first butfirst butfirst butfirst butfirst :thing +end +</PRE> + +<P> +(The name <CODE>ordinals</CODE> comes from the phrase <EM>ordinal +numbers,</EM> which is what things like "third" are called. Regular +numbers like "three" are called <EM>cardinal numbers.</EM>) This procedure +automatically defined new procedures named <CODE>second</CODE> through +<CODE>seventh</CODE>, each with one more <CODE>butfirst</CODE> in its +instruction line. + +<H2>A Single-Keystroke Program Generator</H2> + +<P> +A fairly common thing to do in Logo is to write a little program that +lets you type a single character on the keyboard to carry out some +instruction. For example, teachers of very young children sometimes +use a program that accepts <CODE>F</CODE> to move the turtle forward some +distance, <CODE>B</CODE> for back, and <CODE>L</CODE> and <CODE>R</CODE> for left and +right. What I want to write is a <EM>program-writing program</EM> that +will accept a name and a list of keystrokes and instructions as +inputs and define a procedure with that name that understands those +instructions. + +<PRE> +to onekey :name :list +local "text +make "text [[] [local "char] [print [Type ? for help]] + [make "char readchar]] +foreach :list [make "text lput (sentence [if equalp :char] + (word "" first ?) + butfirst ?) + :text] +make "text lput (lput (list "foreach :list ""print) + [if equalp :char "?]) ~ + :text +make "text lput (list :name) :text +define :name :text +end +</PRE> + +<P> +If we use this program with the instruction + +<PRE> +onekey "instant [[F [forward 20]] [B [back 20]] + [L [left 15]] [R [right 15]]] +</PRE> + +<P> +then it creates the following procedure: + +<PRE> +to instant +local "char +print [type ? for help] +make "char readchar +if equalp :char "F [forward 20] +if equalp :char "B [back 20] +if equalp :char "L [left 15] +if equalp :char "R [right 15] +if equalp :char "? [foreach [[F [forward 20]] [B [back 20]] + [L [left 15]] [R [right 15]]] + "print] +instant +end +</PRE> + +<P> +In addition to illustrating the use of <CODE>define</CODE>, this program +demonstrates how <CODE>sentence</CODE>, <CODE>list</CODE>, and <CODE>lput</CODE> can +all be useful in constructing lists, when you have to combine some +constant members with some variable members. + +<P> +Of course, if we only want to make one <CODE>instant</CODE> program, it's +easier just to type it in. An automatic procedure like <CODE>onekey</CODE> +is useful when you want to create several different procedures like +<CODE>instant</CODE>, each with a different "menu" of characters. For +example, consider these instructions: + +<PRE> +onekey "instant [[F [forward 20]] [B [back 20]] + [L [left 15]] [R [right 15]] [P [pens]]] +onekey "pens [[U [penup stop]] [D [pendown stop]] [E [penerase stop]]] +</PRE> + +<P> +With these definitions, typing <CODE>P</CODE> to <CODE>instant</CODE> +prepares to accept a pen command from the second list. In effect, +<CODE>instant</CODE> recognizes two-letter commands <CODE>PU</CODE> for <CODE>penup</CODE> +and so on, except that the sequence <CODE>P?</CODE> will display the help +information for just the pen commands. Here's another example: + +<PRE> +onekey "tinyturns [[F [forward 20]] [B [back 20]] + [L [left 5]] [R [right 5]] [H [hugeturns]]] +onekey "hugeturns [[F [forward 20]] [B [back 20]] + [L [left 45]] [R [right 45]] [T [tinyturns]]] +</PRE> + +<H2>Procedure Cross-Reference Listings</H2> + +<P> +When you're working on a very large project, it's easy to lose track +of which procedure invokes which other one. We can use the computer +to help solve this problem by +creating a <EM>cross-reference listing</EM> for all +the procedures in a project. For every procedure +in the project, a cross-reference listing tells which other procedures +invoke that one. If you write long procedures, it can also be helpful +to list which instruction line in procedure <CODE>A</CODE> invokes procedure +<CODE>B</CODE>. + +<P> +The general strategy will be to look through the <CODE>text</CODE> of every +procedure, looking for the name of the procedure we're interested in. +Suppose we're finding all the references to procedure <CODE>X</CODE> and +we're looking through procedures <CODE>A</CODE>, <CODE>B</CODE>, and +<CODE>C</CODE>. For each line of each procedure, we want to know whether +the word <CODE>X</CODE> appears in that line. (Of course you would not +really name a procedure <CODE>A</CODE> or <CODE>X</CODE>. You'd use +meaningful names. This is just an example.) We can't, however, just test + +<PRE> +memberp "x :instr +</PRE> + +<P> +(I'm imagining that the variable <CODE>instr</CODE> contains an +instruction line.) The reason is that a procedure invocation can be +part of a <EM>sublist</EM> of the instruction list if <CODE>X</CODE> is +invoked by way of something like <CODE>if</CODE>. For example, the word +<CODE>X</CODE> is not a member of the list + +<PRE> +[if emptyp :list [x :foo stop]] +</PRE> + +<P> +But it's a member of a member. (Earlier I made a big fuss about the fact +that if that instruction were part of procedure <CODE>A</CODE>, it's +actually <CODE>if</CODE> that invokes <CODE>X</CODE>, not <CODE>A</CODE>. +That's the true story, for the Logo interpreter. But for purposes of a +cross-reference listing, it does us no good to know that <CODE>if</CODE> +invokes <CODE>X</CODE>; what we want to know is which procedure definition to +look at if we want to find the instruction that uses <CODE>X</CODE>.) + +<P> +So the first thing we need is a procedure <CODE>submemberp</CODE> that takes +inputs like those of <CODE>memberp</CODE> but outputs <CODE>true</CODE> if the +first input is a member of the second, or a member of a member, and so +on. + +<PRE> +to submemberp :thing :list +if emptyp :list [output "false] +if equalp :thing first :list [output "true] +if listp first :list ~ + [if submemberp :thing first :list [output "true]] +output submemberp :thing butfirst :list +end +</PRE> + +<P> +Now we want a procedure that will take two words as input, both of +which are the names of procedures, and will print a list of all the +references to the first procedure in the text of the second. + +<PRE> +to reference :target :examinee +ref1 :target :examinee butfirst text :examinee 1 +end + +to ref1 :target :examinee :instrs :linenum +if emptyp :instrs [stop] +if submemberp :target first :instrs ~ + [print sentence "| | (word :examinee "\( :linenum "\) )] +ref1 :target :examinee butfirst :instrs :linenum+1 +end +</PRE> + +<P> +<CODE>Reference</CODE> uses <CODE>butfirst text :examinee</CODE> as the third +input to <CODE>ref1</CODE> to avoid the list of inputs to the procedure we're +examining. That's because one of those inputs might have the same name as +the <CODE>target</CODE> procedure, and we'd get a false indication of +success. (In the body of the definition of <CODE>:examinee</CODE>, any +reference to a variable named <CODE>X</CODE> will not use the word +<CODE>X</CODE> but rather the word <CODE>"X</CODE> or the word +<CODE>:X</CODE>. You may find that statement confusing. When you type an +<EM>instruction</EM> like + +<PRE> +print "foo +</PRE> + +<P> +the Logo evaluator interprets <CODE>"foo</CODE> as a request for the word +<CODE>foo</CODE>, quoted (as opposed to evaluated). So <CODE>print</CODE> +won't print a quotation mark. But if we look at the <EM>list</EM> + +<PRE> +[print "foo] +</PRE> + +<P> +then we are not, right now, evaluating it as a Logo +instruction. The second member of that list is the word <CODE>"foo</CODE>, +quote mark and all.) + +<P> +We can still get "false hits," finding the word <CODE>X</CODE> +(or whatever procedure name we're looking for) in an instruction list, +but not being used as a procedure name: + +<PRE> +print [w x y z] +</PRE> + +<P> +But cases like that will be relatively rare compared to the +cases of variables and procedures with the same name. + +<P> +The reason I'm printing spaces before the information is that I'm +working toward a listing that will look like this: + +<PRE> +target1 + proca(3) + procb(1) + procc(4) +target2 + procb(3) + procb(4) +</PRE> + +<P> +This means that the procedure named <CODE>target1</CODE> is invoked +in each of the procedures <CODE>proca</CODE>, <CODE>procb</CODE>, and <CODE>procc</CODE>; +procedure <CODE>target2</CODE> is invoked by <CODE>procb</CODE> on two different +instruction lines. + +<P> +Okay, now we can find references to one specific procedure within the +text of another specific procedure. Now we want to look for +references to one procedure within <EM>all</EM> the procedures making up +a project. + +<PRE> +to xref :target :list +print :target +foreach :list [reference :target ?] +end +</PRE> + +<P> +We're almost done. Now we want to apply <CODE>xref</CODE> to every +procedure in the project. This involves another run through the list +of projects: + +<PRE> +to xrefall :list +foreach :list [xref ? :list] +end +</PRE> + +<P> +To use this program to make a cross-reference listing of +itself, you'd say + +<PRE> +xrefall [xrefall xref reference ref1 submemberp] +</PRE> + +<P> +To cross-reference all of the procedures in your workspace, +you'd say + +<PRE> +xrefall procedures +</PRE> + +<P> +If you try this program on a project with a large number of procedures, +you should expect it to take a <EM>long</EM> time. If there +are five procedures, we have to examine each of them for +references to each of them, so we invoke <CODE>reference</CODE> 25 times. If +there are 10 procedures, we invoke <CODE>reference</CODE> 100 times! In +general, the number of invocations is the square of the number of +procedures. The fancy way to say this is that the program "takes +quadratic time" or that it "behaves quadratically." + +<P><A HREF="../v2-toc2.html">(back to Table of Contents)</A> +<P><A HREF="../v2ch4/v2ch4.html"><STRONG>BACK</STRONG></A> +chapter thread <A HREF="../v2ch6/v2ch6.html"><STRONG>NEXT</STRONG></A> + +<P> +<ADDRESS> +<A HREF="../index.html">Brian Harvey</A>, +<CODE>bh@cs.berkeley.edu</CODE> +</ADDRESS> +</BODY> +</HTML> |