diff options
Diffstat (limited to 'js/games/nluqo.github.io/~bh/v2ch8/plist.html')
| -rw-r--r-- | js/games/nluqo.github.io/~bh/v2ch8/plist.html | 513 |
1 files changed, 513 insertions, 0 deletions
diff --git a/js/games/nluqo.github.io/~bh/v2ch8/plist.html b/js/games/nluqo.github.io/~bh/v2ch8/plist.html new file mode 100644 index 0000000..e5851d3 --- /dev/null +++ b/js/games/nluqo.github.io/~bh/v2ch8/plist.html @@ -0,0 +1,513 @@ + +<P><HTML> +<HEAD> +<TITLE>Computer Science Logo Style vol 2 ch 8: Property Lists</TITLE> +</HEAD> +<BODY> +<CITE>Computer Science Logo Style</CITE> volume 2: +<CITE>Advanced Techniques</CITE> 2/e Copyright (C) 1997 MIT +<H1>Property Lists</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/v2ch08.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="../v2ch7/v2ch7.html"><STRONG>BACK</STRONG></A> +chapter thread <A HREF="https://people.eecs.berkeley.edu/~bh/v2ch9/v2ch9.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 the first volume of this series, I wrote a procedure +named <CODE>french</CODE> that translates words from English to +French using a dictionary list like this: + +<P><PRE>[[book livre] [computer ordinateur] [window fenetre]] +</PRE> + +<P>This technique works fine with a short word list. +But suppose we wanted to undertake a serious +translation project, and suppose we wanted to be able to translate +English words into several foreign languages. (You can buy hand-held +machines these days with little keyboards and display panels that do +exactly that.) <CODE>Butfirst</CODE>ing through a list of tens of thousands +of words would be pretty slow, and setting up the lists in the first +place would be very difficult and error-prone. + +<P>If we were just dealing with English and French, one solution would be +to set up many variables, with each an English word as its <EM> +name</EM> and the corresponding French word as its <EM>value:</EM> + +<P><PRE>make "paper "papier +make "chair "chaise +make "computer "ordinateur +make "book "livre +make "window "fenetre +</PRE> + +<P>Once we've done this, the procedure to translate from +English to French is just <CODE>thing</CODE>: + +<P><PRE>? <U>print thing "book</U> +livre +</PRE> + +<P>The advantage of this technique is that it's easy to correct +a mistake in the translation; you just have to assign a new value to +the variable for the one word that is in error, instead of trying to +edit a huge list. + +<P>But we can't quite use this technique for more than one language. We +could create variables whose names contained both the English word and +the target language: + +<P><PRE>make "book.french "livre +make "book.spanish "libro + +to spanish :word +output thing word :word ".spanish +end +</PRE> + +<P>This is a perfectly workable technique but a little messy. +Many variables will be needed. A compromise might be to collect all +the translations for a single English word into one list: + +<P><PRE>make "book [livre libro buch libro liber] + +to spanish :word +output item 2 thing :word +end +</PRE> + +<P><H2>Naming Properties</H2> + +<P>The only thing wrong with this technique is that we have to +remember the correct order of the foreign languages. This can be +particularly tricky because some of the words are the same, or almost +the same, from one language to another. And if we happen not to know +the translation of a particular word in a particular language, we have +to take some pains to leave a gap in the list. Instead we could use +a list that tells us the languages as well as the translated words: + +<P><PRE>[French livre Spanish libro German buch Italian libro Latin liber] +</PRE> + +<P>A list in this form is called a <EM>property list.</EM> The +odd-numbered members of the list are property <EM>names,</EM> and the +even-numbered members are the corresponding property <EM>values.</EM> + +<P>You can see that this solution is a very flexible one. We can add a +new language to the list later, without confusing old procedures that +expect a particular length of list. If we don't know the translation +for a particular word in a particular language, we can just leave it +out. The order of the properties in the list doesn't matter, so we +don't have to remember it. The properties need not all be uniform in +their significance; we could, for example, give <CODE>book</CODE> a property +whose name is <CODE>part.of.speech</CODE> and whose value is <CODE>noun</CODE>. + +<P>To make this work, Berkeley Logo (along with several other dialects) +has procedures to create, remove, and examine +properties. The command <CODE>pprop</CODE> (Put PROPerty) takes three inputs; +the first two must be words, and the third can be any datum. The +first input is the name of a property list; the second is the name of +a property; the third is the value of that property. The effect of +<CODE>pprop</CODE> is to add the new property to the named list. (If there +was already a property with the given name, its old value is replaced +by the new value.) The command <CODE>remprop</CODE> (REMove PROPerty) +takes two inputs, which +must be words: the name of a property list and the name of a property +in the list. The effect of <CODE>remprop</CODE> is to remove the property +(name and value) from the list. The operation <CODE>gprop</CODE> (Get +PROPerty) also takes two words as inputs, the name of a property list +and the name of a property in the list. The output from <CODE>gprop</CODE> +is the value of the named property. (If there is no such property in +the list, <CODE>gprop</CODE> outputs the empty list.) + +<P><PRE>? <U>print gprop "book "German</U> +buch +</PRE> + +<P><H2>Writing Property List Procedures in Logo</H2> + +<P>It would be possible to write Logo procedures that would use ordinary +variables to hold property lists, which would work just like the ones +I've described. Since Berkeley Logo provides property lists as +a primitive capability, you won't need to load these into your +computer, but later parts of the discussion will make more sense if +you understand how they work. Here they are: + +<P><PRE>to pprop :list :name :value +if not namep :list [make :list []] +make :list pprop1 :name :value thing :list +end + +to pprop1 :name :value :oldlist +if emptyp :oldlist [output list :name :value] +if equalp :name first :oldlist ~ + [output fput :name (fput :value (butfirst butfirst :oldlist))] +output fput (first :oldlist) ~ + (fput (first butfirst :oldlist) + (pprop1 :name :value (butfirst butfirst :oldlist))) +end + +to remprop :list :name +if not namep :list [make :list []] +make :list remprop1 :name thing :list +end + +to remprop1 :name :oldlist +if emptyp :oldlist [output []] +if equalp :name first :oldlist [output butfirst butfirst :oldlist] +output fput (first :oldlist) ~ + (fput (first butfirst :oldlist) + (remprop1 :name (butfirst butfirst :oldlist))) +end + +to gprop :list :name +if not namep :list [output []] +output gprop1 :name thing :list +end + +to gprop1 :name :props +if emptyp :props [output []] +if equalp :name first :props [output first butfirst :props] +output gprop1 :name (butfirst butfirst :props) +end +</PRE> + +<P>Note that the input called <CODE>list</CODE> in each of these +procedures is not a property list itself but the <EM>name</EM> of a +property list. That's why each of the superprocedures evaluates + +<P><PRE>thing :list +</PRE> + +<P>to pass down as an input to its subprocedure. + +<P><H2>Property Lists Aren't Variables</H2> + +<P>The primitive procedures that support property lists in Berkeley +Logo, however, do <EM>not</EM> use <CODE>thing</CODE> to find the property +list. Just as the same word can independently name a procedure and a +variable, a property list is a <EM>third</EM> kind of named entity, +which is separate from the <CODE>thing</CODE> with the same name. For +example, if we gave <CODE>book</CODE> the property list shown with a +series of instructions like + +<P><PRE>pprop "book "French "livre +pprop "book "Spanish "libro +</PRE> + +<P>and so on, we would not be creating a <EM>variable</EM> named +<CODE>book</CODE>. + +<P><PRE>? <U>print :book</U> +book has no value +</PRE> + +<P>(Of course, we could give <CODE>book</CODE> a value with a <CODE> +make</CODE> instruction, but that value would have nothing to do with the +property list.) +Instead there is a fourth primitive procedure called <CODE>plist</CODE> that +can be used to examine a property list. <CODE>Plist</CODE> +takes one input, a word. It outputs the property list associated with +that word. If there is no such property list, <CODE>plist</CODE> outputs the +empty list. + +<P><H2>How Language Designers Earn Their Pay</H2> + +<P>If you're like me, you may have some questions about why this Logo +feature works the way it does. The form of a property list, for +example, may seem arbitrary to you. Why should it be a flat list, +with names as the odd-numbered members and values as the even-numbered +ones? Wouldn't it be more sensible to structure the list this way: + +<P><PRE>[[French livre] [Spanish libro] [German buch] + [Italian libro] [Latin liber]] +</PRE> + +<P>In this scheme each member of a property list is <EM>a property.</EM> A +property has two parts, a name and a value. A list structured in this +way would be easier to use with iterative tools like <CODE>map</CODE>. (Try +to figure out a way to redefine <CODE>map</CODE> so that it could map a +function over <EM>pairs</EM> of members of its input list. Your goal +is to find a way that isn't a kludge.) You wouldn't have to think +"What if the list has an odd number of members" when writing +procedures to manipulate property lists. + +<P>So why does Logo use the notation it does? I'm afraid the real answer +is "It's traditional." Logo property lists are the way they are +because that's what property lists look like in Lisp, the language +from which Logo is descended. Now, why was that decision made in the +design of Lisp? I'm not sure of the answer, but one possible reason +is that the flat property lists take up less room in the computer's +memory than the list-of-lists that I'd find more logical. (Logo +measures its available memory in <EM>nodes.</EM> It takes two overhead +nodes per property, not including the ones that actually contain the +name and the value, for the flat property list; it would take three +overhead nodes per property for the list-of-lists.) + +<P>Another minor advantage is that if you want to live dangerously, you +can use <CODE>memberp</CODE> to see if a particular property name exists in a +property list. It's living dangerously because the property name +might, by coincidence, be the <EM>value</EM> of some other property. +(In the dictionary example, this would be the situation if the German +word for "book" were "Greek"!) The advantage is that <CODE>memberp</CODE> +is a primitive procedure, so it's faster than one you could write +yourself that would check just the odd-numbered members of the +property list. + +<P><H2>Fast Replacement</H2> + +<P>Another question you might ask is this one: Why have property list +primitives at all? The list is a very general data structure, which +can be organized in many ways. Why single out this particular way of +using lists as the one to support with special primitive procedures? +After all, it's easy enough to implement property lists in Logo, as +I've done in this chapter. + +<P>One answer is that the primitives can be much faster than the versions +I've written in Logo because they can replace a value inside a +property list without recopying the rest of the list. My procedure +<CODE>pprop1</CODE>, for example, has to do two <CODE>fput</CODE>s for each property +in the list every time you want to change a single property. The +primitive version of <CODE>pprop</CODE> doesn't reconstruct the entire list; +it just rips out the old value from inside the list and sticks in a +new value. + +<P>Aside from the question of speed, the difference between changing +something inside a list and making a modified copy of the list may not +seem like a big deal. But it does raise a subtle question. If you say + +<P><PRE>make "myprops plist "myself +</PRE> + +<P>and then, later, use <CODE>pprop</CODE> or <CODE>remprop</CODE> to change some +of the properties of <CODE>myself</CODE>, does the value of the variable <CODE> +myprops</CODE> change? The answer is no; <CODE>plist</CODE> really outputs a <EM> +copy</EM> of the property list as it exists at the moment you invoke <CODE> +plist</CODE>. That copy becomes the value of <CODE>myprops</CODE>, and it doesn't change +if the property list itself is changed later. (Berkeley Logo, like Lisp, +does have primitives that allow you to change things inside lists in +general, and this possibility of a variable magically changing in value +because you change something else really does arise!) + +<P><H2>Defaults</H2> + +<P>Another language design question you might be wondering about is why +<CODE>gprop</CODE> outputs the empty list if you ask for a property that +doesn't exist. How do you say "book" in Urdu? + +<P><PRE>? <U>show gprop "book "urdu</U> +[] +</PRE> + +<P>If you ask for a <EM>variable</EM> that doesn't exist, you +get an error message. Why doesn't Logo print something like + +<P><PRE>book has no urdu property +</PRE> + +<P>in this situation? + +<P>The name for "what you get when you haven't provided an answer" is a +<EM>default.</EM> There aren't very many situations in which Logo +provides defaults. One obscure example in Berkeley Logo is the <EM> +origin</EM> of an array--the number used to select its first member. +By default the first member is number one, but it's possible to set up +an array that begins with some other number (most commonly zero). + +<P>The question of what should be considered an error is always a hot one +among language designers. The issue is one of programming convenience +versus ease of debugging. Suppose <CODE>thing</CODE> output the empty list +if asked for a nonexistent variable. It would have been easier for +me to write the property list procedures in this chapter; I could have +left out the <CODE>if not namep</CODE> instructions. This is a situation in +which I might ask for a variable that hasn't been given a value "on +purpose," with a perfectly clear idea of what result I want. On the +other hand, if <CODE>thing</CODE> were permissive in this way, what would +happen if I gave it an input that wasn't a variable name because I +made a spelling error? Instead of getting an error message right +away, my program would muddle on with an empty list instead of +whatever value was really needed. Eventually I'd get a different +error message or an incorrect result, and it would be much harder to +find the point in the program that caused the problem. + +<P>The same issue arises, by the way, about operations like <CODE>first</CODE>. +What should <CODE>first</CODE> do if you give it an empty list as input? +Logo considers this an error, as do most versions of Lisp. Some +versions of Lisp, though, output an empty list in this situation. + +<P>It's most common to need "permissive" primitives when working on +extensions to Logo itself, such as property lists, as opposed to specific +application programs. An application programmer has complete control over +the inputs that procedures will be given; an implementor of a programming +language (or an extension to it) has to handle anything that comes up. I +think that's why, traditionally, it's always been the <EM>teachers</EM> of +Logo who vote in favor of error messages and the <EM>implementors</EM> who +prefer permissive primitives. + +<P>So why is <CODE>gprop</CODE> permissive when all other Logo primitives are +not? Well, the others were designed early in the history of the +language when teachers were in charge at the design meetings. +Property lists were added to Logo more recently; the implementors showed up +one day and said, "Guess what? We've put in property lists." So +they did it their way! + +<P><H2>An Example: Family Trees</H2> + +<P>Here is an example program using property lists. My goal is to +represent this family tree: + +<P><CENTER><IMG SRC="family.gif" ALT="figure: family"></CENTER> + +<P>Each person will be represented as a property list, +containing the properties <CODE>mother</CODE>, <CODE>father</CODE>, <CODE>kids</CODE>, and +<CODE>sex</CODE>. The first two will have words (names) as their values, +<CODE>kids</CODE> will be a list of names, and <CODE>sex</CODE> will be <CODE>male</CODE> or +<CODE>female</CODE>. Note that this is only a partial family tree; we don't know +the name of Betty's husband or Boris's wife. Here's how I'll enter +all this information: + +<P><PRE>to family :mom :dad :girls :boys +catch "error [pprop :mom "sex "female] +catch "error [pprop :dad "sex "male] +foreach :girls [pprop ? "sex "female] +foreach :boys [pprop ? "sex "male] +localmake "kids sentence :girls :boys +catch "error [pprop :mom "kids :kids] +catch "error [pprop :dad "kids :kids] +foreach :kids [pprop ? "mother :mom pprop ? "father :dad] +end + +family "Ann "Abraham [Betty] [Bill Bob] +family "Amelia "Albert [Barbara] [Brian Boris] +family "Betty [] [Cathy] [Colin] +family "Barbara "Bob [Carol] [Charlie] +family [] "Boris [] [Chris Cecil] +</PRE> + +<P>The instructions that catch errors do so in case a family has an +unknown mother or father, which is the case for two of the ones in our +family tree. + +<P>Now the idea is to be able to get information out of the tree. The +easy part is to get out the information that is there explicitly: + +<P><PRE>to mother :person +output gprop :person "mother +end + +to kids :person +output gprop :person "kids +end + +to sons :person +output filter [equalp (gprop ? "sex) "male] kids :person +end +</PRE> + +<P>Of course several more such procedures can be written along +similar lines. + +<P>The more interesting challenge is to deduce information that is not +explicitly in the property lists. The following procedures make use +of the ones just defined and other obvious ones like <CODE>father</CODE>. + +<P><PRE>to grandfathers :person +output sentence (father father :person) (father mother :person) +end + +to grandchildren :person +output map.se [gprop ? "kids] (kids :person) +end + +to granddaughters :person +output justgirls grandchildren :person +end + +to justgirls :people +output filter [equalp (gprop ? "sex) "female] :people +end + +to aunts :person +output justgirls sentence (siblings mother :person) ~ + (siblings father :person) +end + +to cousins :person +output map.se [gprop ? "kids] sentence (siblings mother :person) ~ + (siblings father :person) +end + +to siblings :person +local "parent +if emptyp :person [output []] +make "parent mother :person +if emptyp :parent [make "parent father :person] +output remove :person kids :parent +end +</PRE> + +<P>In writing <CODE>siblings</CODE>, I've been careful to have it +output an empty list if its input is empty. That's because <CODE> +aunts</CODE> and <CODE>cousins</CODE> may invoke <CODE>siblings</CODE> with an empty +input if we're looking for the cousins of someone whose father or +mother is unknown. + +<P>You'll find, if you try out these procedures, that similar care needs +to be exercised in some of the "easy" procedures previously written. +For example, <CODE>grandfathers</CODE> will give an error message if applied +to a person whose mother <EM>or</EM> father is unknown, even if the +other parent is known. One solution would be a more careful version +of <CODE>father</CODE>: + +<P><PRE>to father :person +if emptyp :person [output []] +output gprop :person "father +end +</PRE> + +<P>The reason for choosing an empty list as output for a +nonexistent person rather than an empty word is that the former just +disappears when combined with other things using <CODE>sentence</CODE>, but +an empty word stays in the resulting list. So <CODE>grandfathers</CODE>, for +example, will output a list of length 1 if only one grandfather is +known rather than a list with an empty word in addition to the known +grandfather. Procedures like <CODE>cousins</CODE> also rely heavily on the +flattening effect of <CODE>sentence</CODE>. + +<P>This is rather an artificial family tree because I've paid no +attention to family names, and all the given names are unique. In +practice, you wouldn't be able to assume that. Instead, each property +list representing a person would have a name like <CODE>person26</CODE> and +would include properties <CODE>familyname</CODE> and <CODE>givenname</CODE> or +perhaps just a <CODE>name</CODE> property whose value would be a list. All +the procedures like <CODE>father</CODE> and <CODE>cousins</CODE> would output lists +of these funny <CODE>person26</CODE>-type names, and you'd need another +procedure <CODE>realnames</CODE> that would extract the real names from the +property lists of people in a list. But I thought it would be clearer +to avoid that extra level of naming confusion here. + +<P> + +<P><A HREF="../v2-toc2.html">(back to Table of Contents)</A> +<P><A HREF="../v2ch7/v2ch7.html"><STRONG>BACK</STRONG></A> +chapter thread <A HREF="https://people.eecs.berkeley.edu/~bh/v2ch9/v2ch9.html"><STRONG>NEXT</STRONG></A> + +<P> +<ADDRESS> +<A HREF="../index.html">Brian Harvey</A>, +<CODE>bh@cs.berkeley.edu</CODE> +</ADDRESS> +</BODY> +</HTML> |