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
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
1001
1002
1003
1004
1005
1006
1007
1008
1009
1010
1011
1012
1013
1014
1015
1016
1017
1018
1019
1020
1021
1022
1023
1024
1025
1026
1027
1028
1029
1030
1031
1032
1033
1034
1035
1036
1037
1038
1039
1040
1041
1042
1043
1044
1045
1046
1047
1048
1049
1050
1051
1052
1053
1054
1055
1056
1057
1058
1059
1060
1061
1062
1063
1064
1065
1066
1067
1068
1069
1070
1071
1072
1073
1074
1075
1076
1077
1078
1079
1080
1081
1082
1083
1084
1085
1086
1087
1088
1089
1090
1091
1092
1093
1094
1095
1096
1097
1098
1099
1100
1101
1102
1103
1104
1105
1106
1107
1108
1109
1110
1111
1112
1113
1114
1115
1116
1117
1118
1119
1120
1121
1122
1123
1124
1125
1126
1127
1128
1129
1130
1131
1132
1133
1134
1135
1136
1137
1138
1139
1140
1141
1142
1143
1144
1145
1146
1147
1148
1149
1150
1151
1152
1153
1154
1155
1156
1157
1158
1159
1160
1161
1162
1163
1164
1165
1166
1167
1168
1169
1170
1171
1172
1173
1174
1175
1176
1177
1178
1179
1180
1181
1182
1183
1184
1185
1186
1187
1188
1189
1190
1191
1192
1193
1194
1195
1196
1197
1198
1199
1200
1201
1202
1203
1204
1205
1206
1207
1208
1209
1210
1211
1212
1213
1214
1215
1216
1217
1218
1219
1220
1221
1222
1223
1224
1225
1226
1227
1228
1229
1230
1231
1232
1233
1234
1235
1236
1237
1238
1239
1240
1241
1242
1243
1244
1245
1246
1247
1248
1249
1250
1251
1252
1253
1254
1255
1256
1257
1258
1259
1260
1261
1262
1263
1264
1265
1266
1267
1268
1269
1270
1271
1272
1273
1274
1275
1276
1277
1278
1279
1280
1281
1282
1283
1284
1285
1286
1287
1288
1289
1290
1291
1292
1293
1294
1295
1296
1297
1298
1299
1300
1301
1302
1303
1304
1305
1306
1307
1308
1309
1310
1311
1312
1313
1314
1315
1316
1317
1318
1319
1320
1321
1322
1323
1324
1325
1326
1327
1328
1329
1330
1331
1332
1333
1334
1335
1336
1337
1338
1339
1340
1341
1342
1343
1344
1345
1346
1347
1348
1349
1350
1351
1352
1353
1354
1355
1356
1357
1358
1359
1360
1361
1362
1363
1364
1365
1366
1367
1368
1369
1370
1371
1372
1373
1374
1375
1376
1377
1378
1379
1380
1381
1382
1383
1384
1385
1386
1387
1388
1389
1390
1391
1392
1393
1394
1395
1396
1397
1398
1399
1400
1401
1402
1403
1404
1405
1406
1407
1408
1409
1410
1411
1412
1413
1414
1415
1416
1417
1418
1419
1420
1421
1422
1423
1424
1425
1426
1427
1428
1429
1430
1431
1432
1433
1434
1435
1436
1437
|
<HTML>
<HEAD>
<TITLE>Computer Science Logo Style vol 2 ch 7: Pattern Matcher</TITLE>
</HEAD>
<BODY>
<CITE>Computer Science Logo Style</CITE> volume 2:
<CITE>Advanced Techniques</CITE> 2/e Copyright (C) 1997 MIT
<H1>Pattern Matcher</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/v2ch07.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="../v2ch6/v2ch6.html"><STRONG>BACK</STRONG></A>
chapter thread <A HREF="../v2ch8/v2ch8.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>Program file for this chapter: <A HREF="match.lg"><CODE>match</CODE></A>
<P>
In a <EM>conversational</EM> program, one that carries on a conversation with
the user, you may often have occasion to compare what the user types with
some expected response. For example, a quiz program will compare the user's
response with the correct answer; if you've just asked "how are you," you
might look for words like "fine" or "lousy" in the reply. The main
tools that Logo provides for such comparisons are <CODE>equalp</CODE>, which
compares two values for exact equality, and <CODE>memberp</CODE>, which compares
one datum with a list of alternatives. This project provides a more
advanced comparison tool.
<P>Most of the projects in this book are fairly complicated in their inner
workings, but relatively simple in the external appearance of what they do.
This project is the reverse; the actual program is not so complex, but it
does quite a lot, and it will take a while to explain all of it. Pattern
matching is a powerful programming tool, and I hope you won't be put off by
the effort required to learn how to use it.
<P>A <EM>pattern</EM> is a list in which some members are not made explicit.
This definition is best understood by considering an example. Consider the
pattern
<P><PRE>[Every # is a #]
</PRE>
<P>The words <CODE>every</CODE>, <CODE>is</CODE>, and <CODE>a</CODE> represent themselves
explicitly. The two number signs, however, are symbols representing "zero
or more arbitrary data." Here are some lists that would match the
pattern:
<P><PRE>[Every man is a mortal]
[Every computer programmer is a genius]
[Every is a word]
[Every datum is a word or a list]
</PRE>
<P>Here are some lists that would <EM>not</EM> match the pattern:
<P><PRE>[Socrates is a man]
[Every man is an animal]
[Everyone I know is a friend]
[I think every list is a match]
</PRE>
<P>The first of these examples doesn't match the pattern because the
word <CODE>every</CODE> is missing. The second has <CODE>an</CODE> instead of <CODE>a</CODE>,
while the third has <CODE>everyone</CODE> instead of <CODE>every</CODE>. The fourth has
the extra words <CODE>I think</CODE> before the word <CODE>every</CODE>. This last
example <EM>would</EM> match the pattern
<P><PRE>[# every # is a #]
</PRE>
<P>because this new pattern allows for extra words at the beginning.
<P><CODE>Match</CODE> is a predicate that takes two inputs. The first input is a
pattern and the second input is a sentence. The output is <CODE>true</CODE> if the
sentence matches the pattern, otherwise <CODE>false</CODE>.
<P><PRE>? <U>print match [Every # is a #] [Every book is a joy to read]</U>
true
? <U>print match [Every # is a #] [Every adolescent is obnoxious]</U>
false
</PRE>
<P>Patterns can be more complicated than the ones I've shown so far. In the
following paragraphs I'll introduce the many ways that you can modify
patterns to control which sentences they'll match. As you read, you should
make up sample patterns of your own and try them out with <CODE>match</CODE>.
<P>Often, in a conversational program, it's not good enough just to know
whether or not a sentence matches a pattern. You also want to know the
pieces of the sentence that match the variable parts of the pattern. <CODE>
Match</CODE> meets this requirement by allowing you to tell it the names of
variables that you want to receive the matching words from the sentence.
Here is an example:
<P><PRE>? <U>print match [#food is for #animal] [Hay is for horses]</U>
true
? <U>show :food</U>
[Hay]
? <U>show :animal</U>
[horses]
? <U>print match [#food is for #animal] [C++ is for the birds]</U>
true
? <U>show :food</U>
[C++]
? <U>show :animal</U>
[the birds]
</PRE>
<P>Here is a short <A NAME="converse"> conversational program using the parts of the
pattern matcher we've discussed so far.
<P><PRE>to converse
local [response name like]
print [Hi, my name is Toby and I like ice cream]
print [Tell me about yourself]
make "response readlist
if match [# my name is #name] :response [do.name strip.and :name]
if match [# i like #like] :response [do.like strip.and :like]
print [Nice meeting you!]
end
to do.name :name
print sentence "Hello, :name
end
to do.like :like
print sentence [I'm glad you like] :like
end
to strip.and :text
local "short
if match [#short and #] :text [output :short]
output :text
end
? <U>converse</U>
Hi, my name is Toby and I like ice cream
Tell me about yourself
<U>My name is Brian and I like Chinese food</U>
Hello, Brian
I'm glad you like Chinese food
Nice meeting you!
? <U>converse</U>
Hi, my name is Toby and I like ice cream
Tell me about yourself
<U>I like spaghetti and meat balls</U>
I'm glad you like spaghetti
Nice meeting you!
</PRE>
<P>If <CODE>match</CODE> outputs <CODE>false</CODE>, there is no guarantee of what
values will end up in the variables mentioned in the pattern. <CODE>
Converse</CODE> uses the result of the match only if <CODE>match</CODE> outputs <CODE>
true</CODE>.
<P><CODE>Converse</CODE> looks for each part of the sentence (the name and the thing
the person likes) in two steps: first it finds the keywords <CODE>my name is</CODE>
or <CODE>I like</CODE> and extracts everything following those phrases, then it
looks within what it extracted for the word <CODE>and</CODE> and removes anything
following it. For example, when I typed
<P><PRE>My name is Brian and I like Chinese food
</PRE>
<P>the result of matching the name pattern was to give the variable
<CODE>name</CODE> the value
<P><PRE>Brian and I like Chinese food
</PRE>
<P>Then <CODE>strip.and</CODE> used a second pattern to eliminate everything
after the <CODE>and</CODE>. You might be tempted to extract the name in one step
by using a pattern like
<P><PRE>[# my name is #name and #]
</PRE>
<P>but I wanted to avoid that pattern because it won't match a
sentence that only contains
<P><PRE>my name is Mary
</PRE>
<P>without expressing any likes or dislikes. The program as I've
written it does accept these shorter sentences also. Later we'll see a more
complicated pattern that accepts sentences with or without <CODE>and</CODE>
using a single pattern.
<P>The special symbol <CODE>#</CODE> in a pattern represents zero or more words. <CODE>
Match</CODE> recognizes other symbols with different meanings:
<P><TABLE>
<TR><TD><CODE>#</CODE><TD> zero or more
<TR><TD><CODE>&</CODE><TD> one or more
<TR><TD><CODE>?</CODE><TD> zero or one
<TR><TD><CODE>!</CODE><TD> exactly one
</TABLE>
<P>For example, if you'd like the <CODE>converse</CODE> program to recognize
only the first name of the person using it, you could change the relevant
pattern to
<P><PRE>[# my name is !name #]
</PRE>
<P>Then a conversation with the program might look like this:
<P><PRE>? <U>converse</U>
Hi, my name is Toby and I like ice cream
Tell me about yourself
<U>My name is Brian Harvey</U>
Hello, Brian
Nice meeting you!
?
</PRE>
<P>The word <CODE>!name</CODE> in the pattern matched just the single word
<CODE>Brian</CODE>, not the multiple words <CODE>Brian Harvey</CODE> that the original
pattern would have selected. (If you modify <CODE>converse</CODE> in this way, it
should be possible to remove the invocation of <CODE>strip.and</CODE> in computing
the input to <CODE>do.name</CODE>. The single word stored in the variable <CODE>name</CODE> won't
contain any other clauses.)
<P>So far, the patterns we've seen allow two extremes: the pattern can include
a single word that must be matched exactly, or it can allow <EM>any</EM> word
at all to be matched. It is also possible to write a pattern that calls for
words in some specified category--that is, words that satisfy some
predicate. Here is an example:
<P><PRE>to ask.age
local "age
print [How old are you?]
if match [# !age:numberp #] readlist ~
[print (sentence [You are] :age [years old.]]
end
? <U>ask.age</U>
How old are you?
<U>I will be 36 next month</U>
You are 36 years old.
</PRE>
<P>This is a slightly silly example, but it does illustrate the use
of a predicate to restrict which words can match a variable part of a
pattern. The pattern used in <CODE>ask.age</CODE> looks for a single word for
which <CODE>numberp</CODE> is <CODE>true</CODE>, that is, for a number. Any number of
words surrounding the number are allowed.
<P>Of course, a predicate used in a pattern need not be a primitive one like
<CODE>numberp</CODE>. You may find it useful to write your own predicates that
select categories of words. Such a predicate might have a list built in:
<P><PRE>to colorp :word
output memberp :word [red orange yellow blue green violet white black]
end
</PRE>
<P>Or you could check some inherent property of a word:
<P><PRE>to ends.y :word
output equalp last :word "y
end
</PRE>
<P>In either case, what is essential is that your predicate must take
a word as its single input, and must output <CODE>true</CODE> if you want <CODE>
match</CODE> to accept the word to fill a slot in the pattern.
<P>It is most common to want a predicate like <CODE>colorp</CODE>
above--one that tests its input word for membership in a certain list. A
special notation makes it possible to include such a list in the pattern
itself, instead of writing a predicate procedure. For example, suppose you
are writing a quiz program, and you want to ask the question, "What is the
quickest route from Boston to Framingham?" You'd like to accept answers
like these:
<P><PRE>Mass Pike
the Massachusetts Turnpike
the Pike
</PRE>
<P>but not <CODE>the Ohio Turnpike</CODE>! Here is a pattern you could use.
<P><PRE>[?:in [the] ?:in [Mass Massachusetts] !:in [Pike Turnpike]]
</PRE>
<P>The special predicate <CODE>in</CODE> is a version of <CODE>memberp</CODE> that
knows to look in the pattern, right after the element that invokes <CODE>in</CODE>,
for the list of acceptable words. This pattern accepts zero or one <CODE>
the</CODE>, zero or one of <CODE>Mass</CODE> or <CODE>Massachusetts</CODE>, and one of <CODE>
Pike</CODE> or <CODE>Turnpike</CODE>. That is, the first two words are optional and the
third is required.
<P>Earlier I rejected the use of a pattern
<P><PRE>[# my name is #name and #]
</PRE>
<P>because I wanted also to be able to accept sentences without <CODE>
and</CODE> following the name. I promised to exhibit a pattern that would accept
both sentence forms. Here it is:
<P><PRE>[# my name is #name:notand #]
</PRE>
<P>This pattern uses a predicate <CODE>notand</CODE> that allows any word
except <CODE>and</CODE>. It's easy to write this predicate:
<P><PRE>to notand :word
output not equalp :word "and
end
</PRE>
<P>(By the way, the symbols indicating the number of words to match are meant
to be mnemonic. The question mark indicates that it's questionable whether
or not the word will be in the sentence. The exclamation point looks a
little like a digit 1, and also shouts emphatically that the word is
present. The number sign means that any number of words (including zero) is
okay, and the ampersand indicates that more words are required, namely at
least one instead of at least zero.)
<P>We've seen various combinations of quantifiers (that's what I'll call
the characters like <CODE>#</CODE> that control how many words are matched),
variable names, and predicates:
<P><TABLE>
<TR><TD><CODE>#</CODE><TD> no variable, no predicate (accept any word)
<TR><TD><CODE>#name</CODE><TD> set variable, no predicate
<TR><TD><CODE>?:in</CODE><TD> no variable, test predicate
<TR><TD><CODE>!age:numberp</CODE><TD> set variable, test predicate
</TABLE>
<P>We are now about to discuss some of the more esoteric features of
the <CODE>match</CODE> program. So far, we have always compared a pattern against
a <EM>sentence,</EM> a list of words. It is also possible to match a pattern
against a structured list, with smaller lists among its members. <CODE>Match</CODE>
treats a sublist just like a word, if you don't want to examine the inner
structure of the sublist. Here are some examples.
<P><PRE>? <U>print match [hello #middle goodbye] [hello is [very much] like goodbye]</U>
true
? <U>show :middle</U>
[is [very much] like]
? <U>print match [hi #middle:wordp bye] [hi and then bye]</U>
true
? <U>show :middle</U>
[and then]
? <U>print match [hi #middle:wordp bye] [hi and [then] bye]</U>
false
? <U>print match [hi #mid:wordp #dle:listp bye] [hi and [then] bye]</U>
true
? <U>show :mid show :dle</U>
[and]
[[then]]
</PRE>
<P>A more interesting possibility is to ask <CODE>match</CODE> to apply a
sub-pattern to a sublist. This is done by using the pattern (that is, a
list) in place of the name of a predicate. Here is an example:
<P><PRE>? <U>print match [a #:[x # y] b] [a [x 111 y] [x 222 y] b]</U>
true
? <U>print match [a #:[x # y] b] [a [x 333 zzz] b]</U>
false
</PRE>
<P>It is possible to include variable names in the subpattern, but
this makes sense only if the quantifier outside the pattern is <CODE>!</CODE> or
<CODE>?</CODE> because otherwise you may be trying to assign more than one value to
the same variable. Here's what I mean:
<P><PRE>? <U>print match [a #all:[x #some y] b] [a [x 111 y] [x 222 y] b]</U>
true
? <U>show :all show :some</U>
[[x 111 y] [x 222 y]]
[222]
</PRE>
<P>The variable <CODE>all</CODE> is properly set to contain both of the
lists that matched the subpattern, but the variable <CODE>some</CODE> only contains
the result of the second match.
<P>If a list appears in a pattern without a quantifier before it, <CODE>match</CODE>
treats it as if it were preceded by "<CODE>!:</CODE>"; in other words, it tries
to match the subpattern exactly once.
<P>A pattern element like <CODE>#:predicate</CODE> can match several members of the
target sentence; the predicate is applied to each candidate member
separately. For example:
<P><PRE>? <U>print match [#nums:numberp #rest] [3 2 1 blastoff!]</U>
true
? <U>show :nums show :rest</U>
[3 2 1]
[blastoff!]
</PRE>
<P>Sometimes you may want to match several members of a sentence, but
apply the predicate to all of the candidates <EM>together</EM> in one list.
To do this, use the quantifier <CODE>@</CODE>:
<P><PRE>to threep :list
output equalp count :list 3
end
? <U>print match [@begin:threep #rest] [a b c d e]</U>
true
? <U>show :begin show :rest</U>
[a b c]
[d e]
</PRE>
<P>In this example, I haven't used the predicate to examine the <EM>
nature</EM> of the matching words, but rather to control the <EM>number</EM> of
words that are matched. Here is another example that looks "inside" the
matching words.
<P><PRE>to headtailp :list
if (count :list) < 2 [output "false]
output equalp first :list last :list
end
? <U>print match [#front @good:headtailp #back] [a b c x d e f g x h i]</U>
true
? <U>show :front show :good show :back</U>
[a b c]
[x d e f g x]
[h i]
</PRE>
<P>Think about all the different tests that <CODE>match</CODE> has to make
to find this match! Also, do you see why the first instruction of <CODE>
headtailp</CODE> is needed?
<P>Some patterns are <EM>ambiguous;</EM> that is, there might be more than one
way to associate words from the matched sentence with quantifiers in the
pattern. For example, what should the following do?
<P><PRE>match [#front xx #back] [a b c d xx e f g xx h i]
</PRE>
<P>The word <CODE>xx</CODE> appears twice in the matched sentence. The
program could choose to use everything up to the first <CODE>xx</CODE> as <CODE>
front</CODE>, leaving six words for <CODE>back</CODE>, or it could choose to use
everything up to the second <CODE>xx</CODE> as <CODE>front</CODE>, leaving only two words
for <CODE>back</CODE>. In fact, each quantifier, starting from the left, matches
as many words as it can:
<P><PRE>? <U>print match [#front xx #back] [a b c d xx e f g xx h i]</U>
true
? <U>show :front show :back</U>
[a b c d xx e f g]
[h i]
</PRE>
<P>If that's not what you want, the quantifier <CODE>^</CODE> behaves
like <CODE>#</CODE> except that it matches as <EM>few</EM> words as possible.
<P><PRE>? <U>print match [^front xx #back] [a b c d xx e f g xx h i]</U>
true
? <U>show :front show :back</U>
[a b c d]
[e f g xx h i]
</PRE>
<P>We can use the <CODE>^</CODE> quantifier to fix a bug
in <A HREF="v2ch7.html#converse">the <CODE>converse</CODE>
program</A>:
<P><PRE>? <U>converse</U>
Hi, my name is Toby and I like ice cream
Tell me about yourself
<U>My name is Brian and I like bacon and eggs</U>
Hello, Brian and I like bacon
I'm glad you like bacon
Nice meeting you!
</PRE>
<P>The problem here is that the pattern used by <CODE>strip.and</CODE>
divided the sentence at the second <CODE>and</CODE>, just as the earlier example
chose the second <CODE>xx</CODE> when I used <CODE>#</CODE> as the quantifier. We
can fix it this way:
<P><PRE>to strip.and :text
local "short
if match [^short and #] :text [output :short]
output :text
end
? <U>converse</U>
Hi, my name is Toby and I like ice cream
Tell me about yourself
<U>My name is Brian and I like bacon and eggs</U>
Hello, Brian
I'm glad you like bacon
Nice meeting you!
</PRE>
<P>There is just one more special feature of <CODE>match</CODE> left to describe. It
is another special predicate, like <CODE>in</CODE>, but this one is called <CODE>
anyof</CODE>. When you use <CODE>anyof</CODE>, the next member of the pattern should be
a <EM>list of patterns</EM> to test. <CODE>Match</CODE> tries each pattern in turn,
applied to list members as determined by the quantifier used. In practice,
though, <CODE>anyof</CODE> only makes sense when applied to several members as a
group, so the quantifier <CODE>@</CODE> should always be used. An example may make
this clear. I'm going to rewrite the <CODE>converse</CODE> program to check for
names and likes all at once.
<P><PRE>to converse
local [response name like rest]
print [Hi, my name is Toby and I like ice cream]
print [Tell me about yourself]
make "response readlist
while match [@:anyof [[My name is #name:notand]
[I like #like:notand]
[&:notand]]
?:in [and] #rest] ~
:line ~
[make "response :rest]
if not emptyp :name [print sentence "Hello, :name]
if not emptyp :like [print sentence [I'm glad you like] :like]
print [Nice meeting you!]
end
</PRE>
<P>This program uses the <CODE>notand</CODE> predicate I wrote earlier. It
checks for clauses separated by the word <CODE>and</CODE>. Each clause can match
any of three patterns, one for the name, one for the liking, and a general
pattern that matches any other clause. The clauses can appear in any order.
<P><PRE>? <U>converse</U>
Hi, my name is Toby and I like ice cream
Tell me about yourself
<U>My name is Brian and I hate cheese</U>
Hello, Brian
Nice meeting you!
? <U>converse</U>
Hi, my name is Toby and I like ice cream
Tell me about yourself
<U>I like wings and my name is Jonathan</U>
Hello, Jonathan
I'm glad you like wings
Nice meeting you!
</PRE>
<P><H2>Reinventing <CODE>Equalp</CODE> for Lists</H2>
<P>
<P><CODE>Match</CODE> is a kind of fancy <CODE>equalp</CODE> with a complicated understanding
of what equality means. One way to approach an understanding of <CODE>match</CODE>
is to begin with this question: Suppose Logo's primitive <CODE>equalp</CODE> only
worked for comparing two <EM>words</EM> for equality. (For the remainder of
this section, I won't use the word <CODE>equalp</CODE> at all; I'll call this
imaginary primitive <CODE>wordequalp</CODE> instead.) How would you write a
<CODE>listequalp</CODE> to compare two lists? This is basically a <CODE>
butfirst</CODE>-style recursive operation, but you have to be a little careful
about the fact that either input might be smaller than the other.
<P><PRE>to listequalp :a :b
if emptyp :a [output emptyp :b]
if emptyp :b [output "false]
if wordequalp first :a first :b ~
[output listequalp butfirst :a butfirst :b]
output "false
end
</PRE>
<P>(This procedure contains the instruction <CODE>output "false</CODE>
twice, but it never says <CODE>output "true</CODE>. How can it ever say that two
lists are equal?)
<P>There is one deficiency in the procedure as I've defined
it. The problem is that it only works for <EM>sentences</EM>--lists whose
members are words. If either list contains a sublist, <CODE>listequalp</CODE> will
try to apply <CODE>wordequalp</CODE> to that sublist. If you enjoy the exercise of
reinventing Logo primitives, you may want to fix that. But for my purposes,
the version here is good enough as a basis for further development of the
pattern matcher.
<P><H2>A Simple Pattern Matcher</H2>
<P>We can extend the idea of <CODE>listequalp</CODE> slightly to make a pattern
matcher that only recognizes the special word <CODE>#</CODE> to mean "match zero
or more words." We won't do any of the fancy things like storing the
matching words in a variable.
<P><PRE>to match :pat :sen
if emptyp :pat [output emptyp :sen]
if emptyp :sen [if equalp first :pat "#
[output match butfirst :pat :sen]
[output "false]]
if equalp first :pat "# [output or match butfirst :pat :sen
match :pat butfirst :sen]
if equalp first :pat first :sen ~
[output match butfirst :pat butfirst :sen]
output "false
end
</PRE>
<P>The end test is more complicated in this program than in <CODE>listequalp</CODE>
because the combination of an empty sentence and a nonempty pattern can
still be a match, if the pattern is something like <CODE>[#]</CODE> that matches
zero or more words.
<P>
<P>The really interesting part of this procedure is what happens if a <CODE>#</CODE>
is found in the pattern. The match succeeds (outputs <CODE>true</CODE>) if one of
two smaller matches succeeds. The two smaller matches correspond to two
possible conditions: the <CODE>#</CODE> can match zero words, or more than zero.
The first case is detected by the expression
<P><PRE>match butfirst :pat :sen
</PRE>
<P>For example, suppose you want to evaluate
<P><PRE>match [# cream] [cream]
</PRE>
<P>This expression should yield the value <CODE>true</CODE>, with the <CODE>
#</CODE> matching no words in the sentence. In this example the expression
<P><PRE>match butfirst :pat :sen
</PRE>
<P>is equivalent to
<P><PRE>match [cream] [cream]
</PRE>
<P>which straightforwardly outputs <CODE>true</CODE>.
<P>On the other hand, the expression
<P><PRE>match :pat butfirst :sen
</PRE>
<P>comes into play when the <CODE>#</CODE> has to match at least one word.
For example, consider the expression
<P><PRE>match [# cream] [ice cream]
</PRE>
<P>Here the <CODE>#</CODE> should match the word <CODE>ice</CODE>. The expression
<P><PRE>match :pat butfirst :sen
</PRE>
<P>is here equivalent to
<P><PRE>match [# cream] [cream]
</PRE>
<P>But this is the example that was <CODE>true</CODE> just above.
<P>If the <CODE>#</CODE> has to match more than one word, several recursive
invocations of <CODE>match</CODE> are required, each one taking the <CODE>butfirst</CODE>
of the sentence once. For example, suppose we start with
<P><PRE>match [# cream] [vanilla ice cream]
</PRE>
<P>Here is the sequence of recursive invocations leading to a <CODE>
true</CODE> match:
<P><PRE>match :pat butfirst :sen match [# cream] [ice cream]
match :pat butfirst :sen match [# cream] [cream]
match butfirst :pat :sen match [cream] [cream]
</PRE>
<P>I have been talking as if Logo only evaluated whichever of the two
expressions
<P><PRE>match butfirst :pat :sen
</PRE>
<P>and
<P><PRE>match :pat butfirst :sen
</PRE>
<P>is appropriate for the particular inputs used. Actually, <EM>
both</EM> expressions are evaluated each time, so there are many recursive
invocations of <CODE>match</CODE> that come out <CODE>false</CODE>. However, the purpose
of the primitive operation <CODE>or</CODE> is to output <CODE>true</CODE> if <EM>
either</EM> of its inputs is <CODE>true</CODE>. To understand fully how <CODE>match</CODE>
works, you'll almost certainly have to trace a few examples carefully by
hand.
<P><H2>Efficiency and Elegance</H2>
<P>Pattern matching is a complicated task, and even the best-written programs
are not blindingly fast. But what is the "best-written" program? In the
simple pattern matcher of the last section, the instruction
<P><PRE>if equalp first :pat "# [output or match butfirst :pat :sen
match :pat butfirst :sen]
</PRE>
<P>is extremely compact and elegant. It packs a lot of power into a
single instruction, by combining the results of two recursive invocations
with <CODE>or</CODE>. The similarity of the inputs to the two invocations is also
appealing.
<P>The trouble with this instruction is that it is much slower than necessary,
because it always tries both recursive invocations even if the first one
succeeds. A more efficient way to program the same general idea would be
this:
<P><PRE>if equalp first :pat "# ~
[if match butfirst :pat :sen
[output "true]
[output match :pat butfirst :sen]]
</PRE>
<P>This new version is much less pleasing to the eye, but it's much
faster. The reason is that if the expression
<P><PRE>match butfirst :pat :sen
</PRE>
<P>outputs <CODE>true</CODE>, then the other recursive invocation is avoided.
<P>It's a mistake to make efficiency your only criterion for program style.
Sometimes it's worth a small slowdown of your program to achieve a large
gain in clarity. But this is a case in which the saving is quite
substantial. Here is a partial trace of the evaluation of
<P><PRE>match [cat # bat] [cat rat bat]
</PRE>
<P>using the original version of the procedure:
<P><PRE>match [cat # bat] [cat rat bat] [cat # bat] [cat rat bat]
match butfirst :pat butfirst :sen [# bat] [rat bat]
match butfirst :pat :sen [bat] [rat bat]
match :pat butfirst :sen [# bat] [bat]
match butfirst :pat :sen [bat] [bat]
match butfirst :pat butfirst :sen [] []
* match :pat butfirst :sen [# bat] []
* match butfirst :pat :sen [bat] []
</PRE>
<P>The two invocations marked with asterisks are avoided by using the
revised version. These represent 25% of the invocations of <CODE>match</CODE>, a
significant saving. (Don't think that the program necessarily runs 25%
faster. Not all invocations take the same amount of time. This is just a
rough measure.) If there were more words after the <CODE>#</CODE> in the pattern,
the saving would be even greater.
<P>In this situation we achieve a large saving of time by reorganizing the flow
of control in the program. This is quite different from a more common sort
of concern for efficiency, the kind that leads people to use shorter
variable names so that the program will be a little smaller, or to worry
about whether to use <CODE>fput</CODE> or <CODE>sentence</CODE> in a case where either
would do. These small "bumming" kinds of optimization are rarely worth
the trouble they cause. Figuring out how many times <CODE>match</CODE> is invoked
using each version is a simple example of the branch of computer science
called <EM>analysis of algorithms;</EM> a more profound analysis might use
mathematical techniques to compare the two versions in general, rather than
for a single example.
<P>In the full version of the pattern matcher, listed at the end of this
project description, I've taken some care to avoid unnecessary matching.
On the other hand, the full version has less flexibility than the simple
version because of its ability to assign matching words to variables.
Consider a case like
<P><PRE>match [# #] [any old list of words]
</PRE>
<P>Which <CODE>#</CODE> matches how many words? It doesn't matter if you
don't store the result of the match in variables. But if the pattern is
<CODE>[#a #b]</CODE> instead, there has to be a uniform rule about which part of
the pattern matches what. (In my pattern matcher, all of the words would be
assigned to <CODE>a</CODE>, and <CODE>:b</CODE> would be empty. In general, pattern
elements toward the left match as many words as possible when there is any
ambiguity.) The simple pattern matcher doesn't have this problem, and can
be written to match the ambiguous pattern whichever way gives a <CODE>true</CODE>
result most quickly.
<P>By the way, what if the two expressions that invoke <CODE>match</CODE> recursively
were reversed in the revised instruction? That is, what if the instruction
were changed again, to read
<P><PRE>if equalp first :pat "# ~
[if match :pat butfirst :sen
[output "true]
[output match butfirst :pat :sen]]
</PRE>
<P>Would this be more or less efficient than the previous version?
<P><H2>Logo's Evaluation of Inputs</H2>
<P>The discussion about efficiency started because Logo <EM>evaluates</EM> the
inputs to the primitive operation <CODE>or</CODE> before invoking the procedure.
That is, in the example in question, Logo invokes <CODE>match</CODE> twice before
using <CODE>or</CODE> to check whether either invocation output <CODE>true</CODE>.
This is consistent with the way Logo does things in general: To evaluate an
expression that uses some procedure, Logo first evaluates all the inputs for
that procedure, and then invokes the procedure with the evaluated inputs.
Logo's rule is extremely consistent (except for the <CODE>to</CODE> command), but
it isn't the only possible way. In Lisp, a language that's like Logo in
many ways, each procedure can choose whether or not its inputs should be
evaluated in advance.
<P>
<P>An example may make it clearer what I mean by this. Lisp has a
procedure called <CODE>set</CODE> that's
equivalent to the Logo <CODE>make</CODE>. You say
<P><PRE>(set 'var 27)
</PRE>
<P>as the equivalent of
<P><PRE>make "var 27
</PRE>
<P>But Lisp also has a version called <CODE>setq</CODE> whose first input is
<EM>not</EM> evaluated before <CODE>setq</CODE> is invoked. It's as if there were
an automatic quote mark before the first input, so you just say
<P><PRE>(setq var 27)
</PRE>
<P>with the same effect as the other examples.
<P>Except for the special format of the <CODE>to</CODE> command that forms the title
line of a procedure, Berkeley Logo and many other Logo dialects
do not have any form of automatically-quoted inputs. The design principle
was that consistency of evaluation would make the rules easier to
understand. Some other versions of Logo do use auto-quoting for certain
procedures. For example, in Berkeley Logo, to edit the definition of a
procedure named <CODE>doit</CODE> you type the instruction
<P><PRE>edit "doit
</PRE>
<P>But in some other versions of Logo you instead say
<P><PRE>edit doit
</PRE>
<P>because in those versions, the <CODE>edit</CODE> command auto-quotes its
input. One possible reason for this design decision is that teachers of
young children like to present Logo without an explicit discussion of the
evaluation rules. They teach the <CODE>edit</CODE> command as a special case,
rather than as just the invocation of a procedure like everything else.
Using this approach, auto-quoting the input avoids having to explain what
that quotation mark means.
<P>The advantage of the non-auto-quoting version of <CODE>edit</CODE> isn't just in
some abstract idea of consistency. It allows us to take advantage of
composition of functions. Suppose you are working on a very large project,
a video game, with hundreds of procedures. You want to edit all the procedures
having to do with the speed of the spaceships, or whatever moves around the
screen in this game. Luckily, all the procedures you want have the word
<CODE>speed</CODE> as part of their names; they are called <CODE>shipspeed</CODE> or
<CODE>asteroidspeed</CODE> or <CODE>speedcontrol</CODE>. You can say
<P><PRE>edit filter [substringp "speed ?] procedures
</PRE>
<P>(<CODE>Procedures</CODE> is a Berkeley Logo primitive operation that
outputs a list of all procedures defined in the workspace; <CODE>substringp</CODE>
is a predicate that checks whether one word appears as part of a longer
word.) An auto-quoting <CODE>edit</CODE> command wouldn't have this flexibility.
<P>The reason all this discussion is relevant to the pattern matcher is that
the Lisp versions of <CODE>or</CODE> and <CODE>and</CODE> have auto-quoted inputs, which
get evaluated one by one. As soon as one of the inputs to <CODE>or</CODE> turns
out to be <CODE>true</CODE> (or one of the inputs to <CODE>and</CODE> is <CODE>false</CODE>), the
evaluation stops. This is very useful not only for efficiency reasons, as
in the discussion earlier, but to prevent certain kinds of errors. For
example, consider this Logo instruction:
<P><PRE>if not emptyp :list [if equalp first :list 1 [print "one]]
</PRE>
<P>It would be pleasant to be able to rewrite that instruction this
way:
<P><PRE>if and (not emptyp :list) (equalp first :list 1) [print "one]
</PRE>
<P>The use of <CODE>and</CODE>, I think, makes the program structure clearer
than the nested <CODE>if</CODE>s. That is, it's apparent in the second version
that something (the <CODE>print</CODE>) is to be done if two conditions are met, and
that that's all that happens in the instruction. In the first version,
there might have been another instruction inside the range of the first
(outer) <CODE>if</CODE>; you have to read carefully to see that that isn't so.
<P>Unfortunately, the second version won't work in Logo. If <CODE>:list</CODE> is in
fact empty, the expression
<P><PRE>(equalp first :list 1)
</PRE>
<P>is evaluated before <CODE>and</CODE> is invoked; this expression causes
an error message because <CODE>first</CODE> doesn't accept an empty input. In
Lisp, the corresponding instruction <EM>would</EM> work, because the two
predicate expressions would be evaluated serially and the second wouldn't
be evaluated if the first turned out to be false.
<P>The serial evaluation of inputs to <CODE>and</CODE> and <CODE>or</CODE> is so
often useful that some people have proposed it for Logo, even at the cost of
destroying the uniform evaluate-first rule. But if you want a serial <CODE>
and</CODE> or <CODE>or</CODE>, it's easy enough to write them, if you explicitly quote
the predicate expressions that are its inputs:
<P><PRE>to serial.and :pred1 :pred2
if not run :pred1 [output "false]
output run :pred2
end
to serial.or :pred1 :pred2
if run :pred1 [output "true]
output run :pred2
end
</PRE>
<P>Here's how you would use <CODE>serial.and</CODE> to solve the problem
with the nested <CODE>if</CODE>s:
<P><PRE>if (serial.and [not emptyp :list] [equalp first :list 1]) [print "one]
</PRE>
<P>Similarly, you could use <CODE>serial.or</CODE> instead of <CODE>or</CODE> to
solve the efficiency problem in the first version of the pattern matcher:
<P><PRE>output serial.or [match butfirst :pat :sen] [match :pat butfirst :sen]
</PRE>
<P>These procedures depend on the fact that the predicate expressions
that are used as their inputs are presented inside square brackets; that's
why they are not evaluated before <CODE>serial.and</CODE> or <CODE>serial.or</CODE> is
invoked.
<P><H2>Indirect Assignment</H2>
<P>From now on, I'll be talking about the big pattern matcher, not the simple
one I introduced to illustrate the structure of the problem. Here is the
top-level procedure <CODE>match</CODE>:
<P><PRE>to match :pat :sen
local [special.var special.pred special.buffer in.list]
if or wordp :pat wordp :sen [output "false]
if emptyp :pat [output emptyp :sen]
if listp first :pat [output special fput "!: :pat :sen]
if memberp first first :pat [? # ! & @ ^] [output special :pat :sen]
if emptyp :sen [output "false]
if equalp first :pat first :sen ~
[output match butfirst :pat butfirst :sen]
output "false
end
</PRE>
<P>As you'd expect, there are more cases to consider in this more
featureful version, but the basic structure is similar to the simple
matcher. The instructions starting <CODE>if emptyp</CODE>, <CODE>if memberp</CODE>,
<CODE>if emptyp</CODE>, and <CODE>if equalp</CODE> play the same roles as similar
instructions in the other version. (The <CODE>memberp</CODE> test replaces the
comparison against the word <CODE>#</CODE> with a wider range of choices.)
<P>The first <CODE>if</CODE> instruction tests for errors in the format of the pattern
or the sentence to be matched, in which a word is found where a list was
expected. It's not important if you use well-formed inputs to <CODE>match</CODE>.
The <CODE>listp</CODE> test essentially converts a pattern like
<P><PRE>[foo [some # pattern] baz]
</PRE>
<P>to the equivalent form
<P><PRE>[foo !:[some # pattern] baz]
</PRE>
<P>The interesting new case comes when <CODE>match</CODE> sees a word in the
pattern that starts with one of the six special quantifier characters. In
this case, <CODE>match</CODE> invokes <CODE>special</CODE> to check for a match.
<P>One of the interesting properties of <CODE>special</CODE> is that it has to be able
to assign a value to a variable whose name is not built into the program,
but instead is part of the <EM>data</EM> used as input to the program.
That is, if the word
<P><PRE>?howmany:numberp
</PRE>
<P>appears in the pattern, <CODE>special</CODE> (or one of its
subprocedures) must assign a value to the variable named <CODE>howmany</CODE>, but
there is no instruction of the form
<P><PRE>make "howmany ...
</PRE>
<P>anywhere in the program. Instead, <CODE>match</CODE> has <EM>another</EM>
variable, whose name is <CODE>special.var</CODE>, whose <EM>value</EM> is the <EM>
name</EM> <CODE>howmany</CODE>. The assignment of the matching words to the
pattern-specified variable is done with an instruction like
<P><PRE>make :special.var ...
</PRE>
<P>Here the first input to <CODE>make</CODE> is not a quoted word, as usual,
but an expression that must be evaluated to figure out which variable to use.
<P><CODE>Special</CODE>, then, has two tasks. First it must divide a word like
<P><PRE>?howmany:numberp
</PRE>
<P>into its component parts; then it must carry out the matching
tasks that are the <EM>meaning</EM> of those parts. These two tasks are like
a smaller version of what a programming language interpreter like Logo
does. Finding the meaningful parts of an instruction is called the <EM>
syntax</EM> of a language, and understanding what the parts mean is called the
<EM>semantics</EM> of the language. <CODE>Special</CODE> has two instructions, one
for the syntax and one for the semantics:
<P><PRE>to special :pat :sen
set.special parse.special butfirst first :pat "
output run word "match first first :pat
end
</PRE>
<P>To <EM>parse</EM> something is to divide it into its pieces. <CODE>
Parse.special</CODE> outputs a list of the form
<P><PRE>[howmany numberp]
</PRE>
<P>for the example we're considering. Then <CODE>set.special</CODE> assigns
the two members of this list as the values of two variables. The variable
named <CODE>special.var</CODE> is given the value <CODE>howmany</CODE>, and the variable
named <CODE>special.pred</CODE> is given the value <CODE>numberp</CODE>. This preliminary
work is what makes possible the indirect assignment described earlier.
<P><H2>Defaults</H2>
<P>What happens if the pattern has a word like
<P><PRE>?:numberp
</PRE>
<P>without a variable name? What happens when the program tries to
assign a value to the variable named in the pattern? <CODE>Set.special</CODE>
contains the instruction
<P><PRE>if emptyp :special.var [make "special.var "special.buffer]
</PRE>
<P>The effect of this instruction is that if you do not mention a
variable in the pattern, the variable named <CODE>special.buffer</CODE> will be
used to hold the results of the match. This variable is the <EM>
default</EM> variable, the one used if no other is specified.
<P>It's important, by the way, that the variable <CODE>special.buffer</CODE> is
declared to be local in procedure <CODE>match</CODE>. What makes it important is
that <CODE>match</CODE> is recursive; if you use a pattern like
<P><PRE>[a # b # c]
</PRE>
<P>then the matching of the second <CODE>#</CODE> is a subproblem of the
matching of the first one. <CODE>Match</CODE> invokes <CODE>special</CODE>, which invokes
<CODE>match#</CODE>, which invokes <CODE>#test</CODE>, which invokes <CODE>
match</CODE> on the <CODE>butfirst</CODE> of the pattern. That <CODE>butfirst</CODE> contains
another <CODE>#</CODE>. Each of these uses the variable <CODE>special.buffer</CODE> to
remember the words it is trying as a match; since the variable is declared
local, the two don't get confused. (This means, by the way, that you can
really confuse <CODE>match</CODE> by using the same variable name twice in a
pattern. It requires a fairly complicated pattern to confuse <CODE>match</CODE>,
but here is an example. The first result is correct, the second incorrect.
<P><PRE>? <U>print match [a #x b &y ! c] [a i b j c b k c]</U>
true
? <U>show :x show :y</U>
[i]
[j c b]
? <U>print match [a #x b &x ! c] [a i b j c b k c]</U>
false
</PRE>
<P>The only change is that the variable name <CODE>x</CODE> is used twice in
the second pattern, and as a result, <CODE>match</CODE> doesn't find the correct
match. You'll know that you really understand how <CODE>match</CODE> works if you
can explain why it <EM>won't</EM> fail if the <CODE>!</CODE> is removed from the
pattern.)
<P>When writing a tool to be used in other projects, especially if the tool
will be used by other people, it's important to think about defaults. What
should the program do if some piece of information is missing? If you don't
provide for a default explicitly, the most likely result is a Logo error
message; your program will end up trying to take <CODE>first</CODE> of an empty
list, or something like that.
<P>Another default in the pattern matcher is for the predicate used to test
matches. For example, what happens when the word
<P><PRE>?howmany
</PRE>
<P>appears in the pattern, without a predicate? This case is
recognized by <CODE>parse.special</CODE>, in the instruction
<P><PRE>if emptyp :word [output list :var "always]
</PRE>
<P>The special predicate <CODE>always</CODE> is used if no other is given in
the pattern. <CODE>Always</CODE> has a very simple definition:
<P><PRE>to always :x
output "true
end
</PRE>
<P>
<P><H2>Program as Data</H2>
<P>The instruction in <CODE>special</CODE> that carries out the semantics of a special
pattern-matching instruction word is
<P><PRE>output run word "match first first :pat
</PRE>
<P>If the pattern contains the word
<P><PRE>?howmany:numberp
</PRE>
<P>then this instruction extracts the quantifier character
<CODE>?</CODE> (the first character of the first word of the pattern) and makes
from it a procedure name <CODE>match?</CODE>. That name is then <CODE>run</CODE> as a Logo
expression; that is, <CODE>special</CODE> invokes a procedure whose name is <CODE>
match?</CODE>.
<P>Most programming languages do not allow the invocation of a procedure based
on finding the name of the procedure in the program's data. Generally there
is a very strict separation between program and data. Being able to
manipulate data to create a Logo instruction, and then run it, is a very
powerful part of Logo. It is also used to deal with the names of predicates
included in the pattern; to see if a word in the sentence input to <CODE>
match</CODE> is a match for a piece of the pattern, the predicate <CODE>try.pred</CODE>
contains the instruction
<P><PRE>output run list :special.pred quoted first :sen
</PRE>
<P>This instruction generates a list whose first member is the name
of the predicate found in the pattern and whose second and last member is a
word from the sentence. Then this list is run as a Logo expression, which
should yield either <CODE>true</CODE> or <CODE>false</CODE> as output, indicating whether
or not the word is acceptable.
<P><H2>Parsing Rules</H2>
<P>When you are reading the program, remember that the kind of pattern that
I've written as
<P><PRE>[begin !:[smaller # pattern] end]
</PRE>
<P>is read by Logo as if I'd written
<P><PRE>[begin !: [smaller # pattern] end]
</PRE>
<P>That is to say, this pattern is a list of four members. I think
of the middle two as a unit, representing a single thing to match. The
sublist takes the place of a predicate name after the <CODE>!</CODE> quantifier.
But for Logo, there is no predicate name in the word starting with the
exclamation point; the pattern is a separate member of the large list.
That's why <CODE>set.special</CODE> uses the expression
<P><PRE>emptyp :special.pred
</PRE>
<P>to test for this situation, rather than <CODE>listp</CODE>. After <CODE>
parse.special</CODE> does its work, all it has found is a colon with nothing
following it. <CODE>Set.special</CODE> has to look at the next member of the
pattern list in order to find the subpattern.
<P><H2>Further Explorations</H2>
<P>Chapter 9 is a large program that uses <CODE>match</CODE>. It
may give you ideas for the ways in which this tool can be used in your own
programs. Here, instead of talking about applications of <CODE>match</CODE>, I'll
discuss some possible extensions or revisions of the pattern matcher itself.
<P>There are many obvious small extensions. For example, to complement the
special <CODE>in</CODE> primitive, you could write <CODE>notin</CODE>, which would accept
all <EM>but</EM> the members of the following list. You could allow the use
of a number as the predicate, meaning that exactly that many matching words
are required. That is, in the example for which I invented the predicate
<CODE>threep</CODE>, I would instead be able to use
<P><PRE>[@begin:3 #rest]
</PRE>
<P>as the pattern.
<P>There is no convenient way to say in a pattern that some subpattern can be
repeated several times, if the subpattern is more than a single word. That
is, in the second version of <CODE>converse</CODE>, instead of having to use <CODE>
while</CODE> to chop off pieces of the matched
sentence into a variable <CODE>rest</CODE>, I'd like to be able to say in the
pattern something like
<P><PRE>[@@: [@:anyof [[my name is #name:notand]
[i like #like:notand]
[&:notand]]
?:in [and]]]
</PRE>
<P>Here the doubled atsign (<CODE>@@</CODE>) means that the entire pattern
that follows should be matched repeatedly instead of only once.
<P>For other approaches to pattern matching, you might want to read about the
programming languages Snobol and Icon, each of which includes pattern
matching as one of its main features.
<P>
<TABLE width="100%"><TR><TD><A HREF="../v2-toc2.html">(back to Table of Contents)</A>
<TD align="right"><A HREF="../v2ch6/v2ch6.html"><STRONG>BACK</STRONG></A>
chapter thread <A HREF="../v2ch8/v2ch8.html"><STRONG>NEXT</STRONG></A>
</TABLE>
<P><H2>Program Listing</H2>
<P><P>
<P><PRE>
to match :pat :sen
local [special.var special.pred special.buffer in.list]
if or wordp :pat wordp :sen [output "false]
if emptyp :pat [output emptyp :sen]
if listp first :pat [output special fput "!: :pat :sen]
if memberp first first :pat [? # ! & @ ^] [output special :pat :sen]
if emptyp :sen [output "false]
if equalp first :pat first :sen ~
[output match butfirst :pat butfirst :sen]
output "false
end
;; Parsing quantifiers
to special :pat :sen
set.special parse.special butfirst first :pat "
output run word "match first first :pat
end
to parse.special :word :var
if emptyp :word [output list :var "always]
if equalp first :word ": [output list :var butfirst :word]
output parse.special butfirst :word word :var first :word
end
to set.special :list
make "special.var first :list
make "special.pred last :list
if emptyp :special.var [make "special.var "special.buffer]
if memberp :special.pred [in anyof] [set.in]
if not emptyp :special.pred [stop]
make "special.pred first butfirst :pat
make "pat fput first :pat butfirst butfirst :pat
end
to set.in
make "in.list first butfirst :pat
make "pat fput first :pat butfirst butfirst :pat
end
;; Exactly one match
to match!
if emptyp :sen [output "false]
if not try.pred [output "false]
make :special.var first :sen
output match butfirst :pat butfirst :sen
end
;; Zero or one match
to match?
make :special.var []
if emptyp :sen [output match butfirst :pat :sen]
if not try.pred [output match butfirst :pat :sen]
make :special.var first :sen
if match butfirst :pat butfirst :sen [output "true]
make :special.var []
output match butfirst :pat :sen
end
;; Zero or more matches
to match#
make :special.var []
output #test #gather :sen
end
to #gather :sen
if emptyp :sen [output :sen]
if not try.pred [output :sen]
make :special.var lput first :sen thing :special.var
output #gather butfirst :sen
end
to #test :sen
if match butfirst :pat :sen [output "true]
if emptyp thing :special.var [output "false]
output #test2 fput last thing :special.var :sen
end
to #test2 :sen
make :special.var butlast thing :special.var
output #test :sen
end
;; One or more matches
to match&
output &test match#
end
to &test :tf
if emptyp thing :special.var [output "false]
output :tf
end
;; Zero or more matches (as few as possible)
to match^
make :special.var []
output ^test :sen
end
to ^test :sen
if match butfirst :pat :sen [output "true]
if emptyp :sen [output "false]
if not try.pred [output "false]
make :special.var lput first :sen thing :special.var
output ^test butfirst :sen
end
;; Match words in a group
to match@
make :special.var :sen
output @test []
end
to @test :sen
if @try.pred [if match butfirst :pat :sen [output "true]]
if emptyp thing :special.var [output "false]
output @test2 fput last thing :special.var :sen
end
to @test2 :sen
make :special.var butlast thing :special.var
output @test :sen
end
;; Applying the predicates
to try.pred
if listp :special.pred [output match :special.pred first :sen]
output run list :special.pred quoted first :sen
end
to quoted :thing
if listp :thing [output :thing]
output word "" :thing
end
to @try.pred
if listp :special.pred [output match :special.pred thing :special.var]
output run list :special.pred thing :special.var
end
;; Special predicates
to always :x
output "true
end
to in :word
output memberp :word :in.list
end
to anyof :sen
output anyof1 :sen :in.list
end
to anyof1 :sen :pats
if emptyp :pats [output "false]
if match first :pats :sen [output "true]
output anyof1 :sen butfirst :pats
end
</PRE><P>
<P><A HREF="../v2-toc2.html">(back to Table of Contents)</A>
<P><A HREF="../v2ch6/v2ch6.html"><STRONG>BACK</STRONG></A>
chapter thread <A HREF="../v2ch8/v2ch8.html"><STRONG>NEXT</STRONG></A>
<P>
<ADDRESS>
<A HREF="../index.html">Brian Harvey</A>,
<CODE>bh@cs.berkeley.edu</CODE>
</ADDRESS>
</BODY>
</HTML>
|