1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
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>
|