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
1438
1439
1440
1441
1442
1443
1444
1445
1446
1447
1448
1449
1450
1451
1452
1453
1454
1455
1456
1457
1458
1459
1460
1461
1462
1463
1464
1465
1466
1467
1468
1469
1470
1471
1472
1473
1474
1475
1476
1477
1478
1479
1480
1481
1482
1483
1484
1485
1486
1487
1488
1489
1490
1491
1492
1493
1494
1495
1496
1497
1498
1499
1500
1501
1502
1503
1504
1505
1506
1507
1508
1509
1510
1511
1512
1513
1514
1515
1516
1517
1518
1519
1520
1521
1522
1523
1524
1525
1526
1527
1528
1529
1530
1531
1532
1533
1534
1535
1536
1537
1538
1539
1540
1541
1542
1543
1544
1545
1546
1547
1548
1549
1550
1551
1552
1553
1554
1555
1556
1557
1558
1559
1560
1561
1562
1563
1564
1565
1566
1567
1568
1569
1570
1571
1572
1573
1574
1575
1576
1577
1578
1579
1580
1581
1582
1583
1584
1585
1586
1587
1588
1589
1590
1591
1592
1593
1594
1595
1596
1597
1598
1599
1600
1601
1602
1603
1604
1605
1606
1607
1608
1609
1610
1611
1612
1613
1614
1615
1616
1617
1618
1619
1620
1621
1622
1623
1624
1625
1626
1627
1628
1629
1630
1631
1632
1633
1634
1635
1636
1637
1638
1639
1640
1641
1642
1643
1644
1645
1646
1647
1648
1649
1650
1651
1652
1653
1654
1655
1656
1657
1658
1659
1660
1661
1662
1663
1664
1665
1666
1667
1668
1669
1670
1671
1672
1673
1674
1675
1676
1677
1678
1679
1680
1681
1682
1683
1684
1685
1686
1687
1688
1689
1690
1691
1692
1693
1694
1695
1696
1697
1698
1699
1700
1701
1702
1703
1704
1705
1706
1707
1708
1709
1710
1711
1712
1713
1714
1715
1716
1717
1718
1719
1720
1721
1722
1723
1724
1725
1726
1727
1728
1729
1730
1731
1732
1733
1734
1735
1736
1737
1738
1739
1740
1741
1742
1743
1744
1745
1746
1747
1748
1749
1750
1751
1752
1753
1754
1755
1756
1757
1758
1759
1760
1761
1762
1763
1764
1765
1766
1767
1768
1769
1770
1771
1772
1773
1774
1775
1776
1777
1778
1779
1780
1781
1782
1783
1784
1785
1786
1787
1788
1789
1790
1791
1792
1793
1794
1795
1796
1797
1798
1799
1800
1801
1802
1803
1804
1805
1806
1807
1808
1809
1810
1811
1812
1813
1814
1815
1816
1817
1818
1819
1820
1821
1822
1823
1824
1825
1826
1827
1828
1829
1830
1831
1832
1833
1834
1835
1836
1837
1838
1839
1840
1841
1842
1843
1844
1845
1846
1847
1848
1849
1850
1851
1852
1853
1854
1855
1856
1857
1858
1859
1860
1861
1862
1863
1864
1865
1866
1867
1868
1869
1870
1871
1872
1873
1874
1875
1876
1877
1878
1879
1880
1881
1882
1883
1884
1885
1886
1887
1888
1889
1890
1891
1892
1893
1894
1895
1896
1897
1898
1899
1900
1901
1902
1903
1904
1905
1906
1907
1908
1909
1910
1911
1912
1913
1914
1915
1916
1917
1918
1919
1920
1921
1922
1923
1924
1925
1926
1927
1928
1929
1930
1931
1932
1933
1934
1935
1936
1937
1938
1939
1940
1941
1942
1943
1944
1945
1946
1947
1948
1949
1950
1951
1952
1953
1954
1955
1956
1957
1958
1959
1960
1961
1962
1963
1964
1965
1966
1967
1968
1969
1970
1971
1972
1973
1974
1975
1976
1977
1978
1979
1980
1981
1982
1983
1984
1985
1986
1987
1988
1989
1990
1991
1992
1993
1994
1995
1996
1997
1998
1999
2000
2001
2002
2003
2004
2005
2006
2007
2008
2009
2010
2011
2012
2013
2014
2015
2016
2017
2018
2019
2020
2021
2022
2023
2024
2025
2026
2027
2028
2029
2030
2031
2032
2033
2034
2035
2036
2037
2038
2039
2040
2041
2042
2043
2044
2045
2046
2047
2048
2049
2050
2051
2052
2053
2054
2055
2056
2057
2058
2059
2060
2061
2062
2063
2064
2065
2066
2067
2068
2069
2070
2071
2072
2073
2074
2075
2076
2077
2078
2079
2080
2081
2082
2083
2084
2085
2086
2087
2088
2089
2090
2091
2092
2093
2094
2095
2096
2097
2098
2099
2100
2101
2102
2103
2104
2105
2106
2107
2108
2109
2110
2111
2112
2113
2114
2115
2116
2117
2118
2119
2120
2121
2122
2123
2124
2125
2126
2127
2128
2129
2130
2131
2132
2133
2134
2135
2136
2137
2138
2139
2140
2141
2142
2143
2144
2145
2146
2147
2148
2149
2150
2151
2152
2153
2154
2155
2156
2157
2158
2159
2160
2161
2162
2163
2164
2165
2166
2167
2168
2169
2170
2171
2172
2173
2174
2175
2176
2177
2178
2179
2180
2181
2182
2183
2184
2185
2186
2187
2188
2189
2190
2191
2192
2193
2194
2195
2196
2197
2198
2199
2200
2201
2202
2203
2204
2205
2206
2207
2208
2209
2210
2211
2212
2213
2214
2215
2216
2217
2218
2219
2220
2221
2222
2223
2224
2225
2226
2227
2228
2229
2230
2231
2232
2233
2234
2235
2236
2237
2238
2239
2240
2241
2242
2243
2244
2245
2246
2247
2248
2249
2250
2251
2252
2253
2254
2255
2256
2257
2258
2259
2260
2261
2262
2263
2264
2265
2266
2267
2268
2269
2270
2271
2272
2273
2274
2275
2276
2277
2278
2279
2280
2281
2282
2283
2284
2285
2286
2287
2288
2289
2290
2291
2292
2293
2294
2295
2296
2297
2298
2299
2300
2301
2302
2303
2304
2305
2306
2307
2308
2309
2310
2311
2312
2313
2314
2315
2316
2317
2318
2319
2320
2321
2322
2323
2324
2325
2326
2327
2328
2329
2330
2331
2332
2333
2334
2335
2336
2337
2338
2339
2340
2341
2342
2343
2344
2345
2346
2347
2348
2349
2350
2351
2352
2353
2354
2355
2356
2357
2358
2359
2360
2361
2362
2363
2364
2365
2366
2367
2368
2369
2370
2371
2372
2373
2374
2375
2376
2377
2378
2379
2380
2381
2382
2383
2384
2385
2386
2387
2388
2389
2390
2391
2392
2393
2394
2395
2396
2397
2398
2399
2400
2401
2402
2403
2404
2405
2406
2407
2408
2409
2410
2411
2412
2413
2414
2415
2416
2417
2418
2419
2420
2421
2422
2423
2424
2425
2426
2427
2428
2429
2430
2431
2432
2433
2434
2435
2436
2437
2438
2439
2440
2441
2442
2443
2444
2445
2446
2447
2448
2449
2450
2451
2452
2453
2454
2455
2456
2457
2458
2459
2460
2461
2462
2463
2464
2465
2466
2467
2468
2469
2470
2471
2472
2473
2474
2475
2476
2477
2478
2479
2480
2481
2482
2483
2484
2485
2486
2487
2488
2489
2490
2491
2492
2493
2494
2495
2496
2497
2498
2499
2500
2501
2502
2503
2504
2505
2506
2507
2508
2509
2510
2511
2512
2513
2514
2515
2516
2517
2518
2519
2520
2521
2522
2523
2524
2525
2526
2527
2528
2529
2530
2531
2532
2533
2534
2535
2536
2537
2538
2539
2540
2541
2542
2543
2544
2545
2546
2547
2548
2549
2550
2551
2552
2553
2554
2555
2556
2557
2558
2559
2560
2561
2562
2563
2564
2565
2566
2567
2568
2569
2570
2571
2572
2573
2574
2575
2576
2577
2578
2579
2580
2581
2582
2583
2584
2585
2586
2587
2588
2589
2590
2591
2592
2593
2594
2595
2596
2597
2598
2599
2600
2601
2602
2603
2604
2605
2606
2607
2608
2609
2610
2611
2612
2613
2614
2615
2616
2617
2618
2619
2620
2621
2622
2623
2624
2625
2626
2627
2628
2629
2630
2631
2632
2633
2634
2635
2636
2637
2638
2639
2640
2641
2642
2643
2644
2645
2646
2647
2648
2649
2650
2651
2652
2653
2654
2655
2656
2657
2658
2659
2660
2661
2662
2663
2664
2665
2666
2667
2668
2669
2670
2671
2672
2673
2674
2675
2676
2677
2678
2679
2680
2681
2682
2683
2684
2685
2686
2687
2688
2689
2690
2691
2692
2693
2694
2695
2696
2697
2698
2699
2700
2701
2702
2703
2704
2705
2706
2707
2708
2709
2710
2711
2712
2713
2714
2715
2716
2717
2718
2719
2720
2721
2722
2723
2724
2725
2726
2727
2728
2729
2730
2731
2732
2733
2734
2735
2736
2737
2738
2739
2740
2741
2742
2743
2744
2745
2746
2747
2748
2749
2750
2751
2752
2753
2754
2755
2756
2757
2758
2759
2760
2761
2762
2763
2764
2765
2766
2767
2768
2769
2770
2771
2772
2773
2774
2775
2776
2777
2778
2779
2780
2781
2782
2783
2784
2785
2786
2787
2788
2789
2790
2791
2792
2793
2794
2795
2796
2797
2798
2799
2800
2801
2802
2803
2804
2805
2806
2807
2808
2809
2810
2811
2812
2813
2814
2815
2816
2817
2818
2819
2820
2821
2822
2823
2824
2825
2826
2827
2828
2829
2830
2831
2832
2833
2834
2835
2836
2837
2838
2839
2840
2841
2842
2843
2844
2845
2846
2847
2848
2849
2850
2851
2852
2853
2854
2855
2856
2857
2858
2859
2860
2861
2862
2863
2864
2865
2866
2867
2868
2869
2870
2871
2872
2873
2874
2875
2876
2877
2878
2879
2880
2881
2882
2883
2884
2885
2886
2887
2888
2889
2890
2891
2892
2893
2894
2895
2896
2897
2898
2899
2900
2901
2902
2903
2904
2905
2906
2907
2908
2909
2910
2911
2912
2913
2914
2915
2916
2917
2918
2919
2920
2921
2922
2923
2924
2925
2926
2927
2928
2929
2930
2931
2932
2933
2934
2935
2936
2937
2938
2939
2940
2941
2942
2943
2944
2945
2946
2947
2948
2949
2950
2951
2952
2953
2954
2955
2956
2957
2958
2959
2960
2961
2962
2963
2964
2965
2966
2967
2968
2969
2970
2971
2972
2973
2974
2975
2976
2977
2978
2979
2980
2981
2982
2983
2984
2985
2986
2987
2988
2989
2990
2991
2992
2993
2994
2995
2996
2997
2998
2999
3000
3001
3002
3003
3004
3005
3006
3007
3008
3009
3010
3011
3012
3013
3014
3015
3016
3017
3018
3019
3020
3021
3022
3023
3024
3025
3026
3027
3028
3029
3030
3031
3032
3033
3034
3035
3036
3037
3038
3039
3040
3041
3042
3043
3044
3045
3046
3047
3048
3049
3050
3051
3052
3053
3054
3055
3056
3057
3058
3059
3060
3061
3062
3063
3064
3065
3066
3067
3068
3069
3070
|
<HTML>
<HEAD>
<TITLE>Computer Science Logo Style vol 3 ch 6: Artificial Intelligence</TITLE>
</HEAD>
<BODY>
<CITE>Computer Science Logo Style</CITE> volume 3:
<CITE>Beyond Programming</CITE> 2/e Copyright (C) 1997 MIT
<H1>Artificial Intelligence</H1>
<TABLE width="100%"><TR><TD>
<IMG SRC="../csls3.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/v3ch06.pdf">Download PDF version</A>
<TR><TD align="right"><A HREF="../v3-toc2.html">Back to Table of Contents</A>
<TR><TD align="right"><A HREF="../v3ch5/v3ch5.html"><STRONG>BACK</STRONG></A>
chapter thread <A HREF="https://people.eecs.berkeley.edu/~bh/v3ch7/v3ch7.html"><STRONG>NEXT</STRONG></A>
<TR><TD align="right"><A HREF="https://mitpress.mit.edu/books/computer-science-logo-style-second-edition-volume-3">MIT
Press web page for <CITE>Computer Science Logo Style</CITE></A>
</TABLE></TABLE>
<HR><P>Program file for this chapter: <A HREF="student.lg"><CODE>student</CODE></A>
<P>
<P>Can a computer be intelligent? What would it mean for a computer to be
intelligent? John McCarthy, one of the founders of
artificial intelligence
research, once defined the field as "getting a computer to do things which,
when done by people, are said to involve intelligence." The point of the
definition was that he felt perfectly comfortable about carrying on his
research without first having to defend any particular philosophical view of
what the word "intelligence" means.
<P>There have always been two points of view among AI researchers about what
their purpose is. One point of view is that AI programs contribute to our
understanding of <EM>human</EM> psychology; when researchers take this view
they try to make their programs reflect the actual mechanisms of intelligent
human behavior. For example, Allen Newell and
Herbert A. Simon begin their
classic AI book <EM>Human Problem Solving</EM> with the sentence, "The aim
of this book is to advance our understanding of how humans think." In one
of their research projects they studied cryptarithmetic problems, in which
digits are replaced with letters in a multi-digit addition or multiplication.
First they did a careful observation and analysis of how a human subject
attacked such a problem, then they pointed out specific problem-solving
techniques that the person used, and used those techniques as the basis for
designing a computer simulation. The other point of view
is that AI programs provide a more abstract model for intelligence in
general; just as one can learn about the properties of computers by studying
finite-state machines, even though no real computer operates precisely as a
formal finite-state machine does, we can learn about the properties of any
possible intelligent being by simulating intelligence in a computer program,
whether or not the mechanisms of that program are similar to those used by
people.
<P>In the early days of AI research these two points of view were not sharply
divided. Sometimes the same person would switch from one to the other,
sometimes trying to model human thought processes and sometimes trying to
solve a given problem by whatever methods could be made to work. More
recently, researchers who hold one or the other point of view consistently
have begun to define two separate fields. One is <EM>
cognitive science,</EM> in which computer scientists join with
psychologists, linguists, biologists, and others to study human cognitive
psychology, using computer programs as a concrete embodiment of theories
about the human mind. The other is called <EM>expert systems</EM>
or <EM>knowledge engineering,</EM> in which programming techniques
developed by AI researchers are put to practical use in programs that solve
real-world business problems such as the diagnosis and repair of
malfunctioning equipment.
<P><H2>Microworlds: Student</H2>
<P>In this chapter I'm going to concentrate on one particular area of AI
research: teaching a computer to understand English. Besides its inherent
interest, this area has the advantage that it doesn't require special
equipment, as do some other parts of AI such as machine vision and the
control of robot manipulators.
<P>In the 1950s many people were very optimistic about the use of computers to
translate from one language to another. IBM undertook a government-sponsored
project to translate scientific journals from Russian to English. At first
they thought that this translation could be done very straightforwardly,
with a Russian-English dictionary and a few little kludges to rearrange the
order of words in a sentence to account for differences in the grammatical
structure of the two languages. This simple approach was not successful.
One problem is that the same word can have different meanings, and even
different parts of speech, in different contexts. (According to one famous
anecdote, the program translated the Russian equivalent of "The spirit is
willing but the flesh is weak" into "The vodka is strong but the meat is
rotten.")
<P>A decade later, several AI researchers had the idea that ambiguities in the
meanings of words could be resolved by trying to understand English only in
some limited context. If you know in advance that the sentence you're
trying to understand is about baseball statistics, or about relationships in
a family tree, or about telling a robot arm to move blocks on a table (these
are actual examples of work done in that period) then only certain narrowly
defined types of sentences are meaningful at all. You needn't think about
metaphors or about the many assumptions about commonsense knowledge that
people make in talking with one another. Such a limited context for a
language understanding program is called a <EM>microworld.</EM>
<P>This chapter includes a Logo version of Student, a program written by
Daniel G. Bobrow for his 1964 Ph.D. thesis, <EM>Natural
Language Input for a Computer Problem Solving System,</EM> at MIT. Student
is a program that solves algebra word problems:
<P><PRE>? <U>student [The price of a radio is 69.70. If this price is 15 percent</U>
<U>less than the marked price, find the marked price.]</U>
The marked price is 82 dollars
</PRE>
<P>(In this illustration I've left out some of Student's display of
intermediate results.) The program has two parts: one that translates the
word problem into the form of equations and another that solves the
equations. The latter part is complex (about 40 Logo procedures) but
straightforward; it doesn't seem surprising to most people that a computer
can manipulate mathematical equations. It is Student's understanding of
English sentences that furthered the cause of artificial intelligence.
<BLOCKQUOTE>
<P><A NAME="bobrow1">The aim</A> of the
research reported here was to discover how one could build a
computer program which could communicate with people in a natural language
within some restricted problem domain. In the course of this investigation,
I wrote a set of computer programs, the Student system, which accepts as
input a comfortable but restricted subset of English which can be used to
express a wide variety of algebra story problems...
<P>In the following discussion, I shall use phrases such as "the computer
understands English." In all such cases, the "English" is just the
restricted subset of English which is allowable as input for the computer
program under discussion. In addition, for purposes of this report I have
adopted the following operational definition of understanding. A computer
<EM>understands</EM> a subset of English if it accepts input sentences which
are members of this subset, and answers questions based on information
contained in the input. The Student system understands English in this
sense. [Bobrow, 1964.]
</BLOCKQUOTE>
<P>How does the algebra microworld simplify the understanding problem? For one
thing, Student need not know anything about the meanings of noun phrases.
In the sample problem above, the phrase <CODE>The price of a radio</CODE> is used
as a variable name. The problem could just as well have been
<P><PRE>The weight of a giant size detergent box is 69.70 ounces. If this weight
is 15 percent less than the weight of an enormous size box, find the
weight of an enormous size box.
</PRE>
<P>For Student, either problem boils down to
<P><PRE><EM>variable1</EM> = 69.70 <EM>units</EM>
<EM>variable1</EM> = 0.85 * <EM>variable2</EM>
Find <EM>variable2</EM>.
</PRE>
<P>Student understands particular words only to the extent that they
have a <EM>mathematical</EM> meaning. For example, the program knows that
<CODE>15 percent less than</CODE> means the same as <CODE>0.85 times</CODE>.
<P><H2>How Student Translates English to Algebra</H2>
<P>Student translates a word problem into equations in several steps. In the
following paragraphs, I'll mention in parentheses the names of the Logo
procedures that carry out each step I describe, but don't read the
procedures yet. First read through the description of the process without
worrying about the programming details of each step. Later you can reread
this section while examining the complete listing at the end of the chapter.
<P>In translating Student to Logo, I've tried not to change the capabilities of
the program in any way. The overall structure of my version is similar to
that of Bobrow's original implementation, but I've changed some details.
I've used iteration and mapping tools to make the program easier to read;
I've changed some aspects of the fine structure of the program to fit more
closely with the usual Logo programming style; in a few cases I've tried to
make exceptionally slow parts of the program run faster by finding a more
efficient algorithm to achieve the same goal.
<P>The top-level procedure <CODE>student</CODE> takes one input, a list containing the
word problem. (The disk file that accompanies this project includes several
variables containing sample problems. For example,
<P><PRE>? <U>student :radio</U>
</PRE>
<P>will carry out the steps I'm about to describe.) Student begins
by printing the original problem:
<P><PRE>? <U>student :radio</U>
The problem to be solved is
The price of a radio is 69.70. If this price is 15 percent less than the
marked price, find the marked price.
</PRE>
<P>The first step is to separate punctuation characters from the
attached words. For example, the word "<CODE>price,</CODE>" in the original problem
becomes the two words "<CODE>price ,</CODE>" with the comma on its own. Then
(<CODE>student1</CODE>) certain <EM>mandatory substitutions</EM> are applied
(<CODE>idioms</CODE>). For example, the phrase <CODE>percent less than</CODE> is translated
into the single word <CODE>perless</CODE>. The result is printed:
<P><PRE>With mandatory substitutions the problem is
The price numof a radio is 69.70 dollars . If this price is 15 perless
the marked price , find the marked price .
</PRE>
<P>(The word <CODE>of</CODE> in an algebra word problem can have two
different meanings. Sometimes it means "times," as in the phrase
"one half of the population." Other times, as in this problem, "of" is
just part of a noun phrase like "the price of a radio." The special word
<CODE>numof</CODE> is a flag to a later part of the program and will then be
further translated either into <CODE>times</CODE> or back into <CODE>of</CODE>. The
original implementation of Student used, instead of a special word like <CODE>
numof</CODE>, a "tagged" word represented as a list like <CODE>[of / op]</CODE>. Other
examples of tagging are <CODE>[Bill / person]</CODE> and <CODE>[has / verb]</CODE>.)
<P>
<P>The next step is to separate the problem into simple sentences (<CODE>bracket</CODE>):
<P><PRE>The simple sentences are
The price numof a radio is 69.70 dollars .
This price is 15 perless the marked price .
Find the marked price .
</PRE>
<P>Usually this transformation of the problem is straightforward, but
the special case of "age problems" is recognized at this time, and special
transformations are applied so that a sentence like
<P><PRE>Mary is 24 years old.
</PRE>
<P>is translated into
<P><PRE>Mary s age is 24 .
</PRE>
<P>An age problem is one that contains any of the phrases <CODE>as old
as</CODE>, <CODE>age</CODE>, or <CODE>years old</CODE>.
<P>The next step is to translate each simple sentence into an equation or a
variable whose value is desired as part of the solution (<CODE>senform</CODE>).
<P><PRE>The equations to be solved are
Equal [price of radio] [product 69.7 [dollars]]
Equal [price of radio] [product 0.85 [marked price]]
</PRE>
<P>The third simple sentence is translated, not into an equation, but
into a request to solve these equations for the variable <CODE>marked price</CODE>.
<P>The translation of simple sentences into equations is the most
"intelligent" part of the program; that is, it's where the program's
knowledge of English grammar and vocabulary come into play and many special
cases must be considered. In this example, the second simple sentence
starts with the phrase <CODE>this price</CODE>. The program recognizes the word
<CODE>this</CODE> (procedure <CODE>nmtest</CODE>) and replaces the entire phrase with the
left hand side of the previous equation (procedure <CODE>this</CODE>).
<P>
<P><H2>Pattern Matching</H2>
<P>Student analyzes a sentence by comparing it to several <EM>patterns</EM>
(<CODE>senform1</CODE>). For example, one sentence form that Student understands
is exemplified by these sentences:
<P><PRE>Joe weighs 163 pounds .
The United States Army has 8742 officers .
</PRE>
<P>The general pattern is
<P><PRE><EM>something</EM> <EM>verb</EM> <EM>number</EM> <EM>unit</EM> .
</PRE>
<P>Student treats such sentences as if they were rearranged to match
<P><PRE>The number of <EM>unit</EM> <EM>something</EM> <EM>verb</EM> is <EM>number</EM> .
</PRE>
<P>and so it generates the equations
<P><PRE>Equal [number of pounds Joe weighs] 163
Equal [number of officers United States Army has] 8742
</PRE>
<P>The original version of Student was written in a pattern matching
language called Meteor, which Bobrow wrote in Lisp. In Meteor, the
instruction that handles this sentence type looks like this:
<P><PRE>(* ( (1 / verb) (fn nmtest) 1 (1 / dlm)) 0
(/ (*s shelf (*k equal (fn opform (*k the number of 4 1 2))
(fn opform (*k 3 5 6))))) return)
</PRE>
<P>The top line contains the pattern to be matched. In the pattern,
a dollar sign represents zero or more words; the notation <CODE>1</CODE>
represents a single word. The zero at the end of the line means that the
text that matches the pattern should be deleted and nothing should replace
it. The rest of the instruction pushes a new equation onto a stack named
<CODE>shelf</CODE>; that equation is formed out of the pieces of the matched
pattern according to the numbers in the instruction. That is, the number
<CODE>4</CODE> represents the fourth component of the pattern, which is <CODE>1</CODE>.
Here is the corresponding instruction in the Logo version:
<P><PRE>if match [^one !verb1:verb !factor:numberp #stuff1 !:dlm] :sent
[output (list (list "equal
opform (sentence [the number of]
:stuff1 :one :verb1)
opform (list :factor) ))]
</PRE>
<P>The pattern matcher I used for Student is the same as the one in
<EM>Advanced Techniques,</EM> the second volume of this series.<SUP>*</SUP> Student often relies on the fact that
Meteor's pattern matcher finds the <EM>first substring</EM> of the text that
matches the pattern, rather than requiring the entire text to match. Many
patterns in the Logo version therefore take the form
<P><PRE>[^beg <EM>interesting part</EM> #end]
</PRE>
<P>where the "interesting part" is all that appeared in the Meteor
pattern.
<P><SMALL><BLOCKQUOTE><SMALL><SUP>*</SUP>The
version in this project is modified slightly; the <CODE>match</CODE> procedure
first does a fast test to try to reject an irrelevant pattern in O(<EM>n</EM>)
time before calling the actual pattern matcher, which could take as much
as O(2<SUP><SMALL><EM>n</EM></SMALL></SUP>) time to reject a pattern, and which has been renamed <CODE>rmatch</CODE>
(for "real match") in this project.</SMALL></BLOCKQUOTE></SMALL>
<P>Here is a very brief summary of the Logo pattern matcher included in this
program. For a fuller description with examples, please refer to Volume 2.
<CODE>Match</CODE> is a predicate with two inputs, both lists. The first input is
the <EM>pattern</EM> and the second input is the <EM>sentence.</EM> <CODE>Match</CODE>
outputs <CODE>true</CODE> if the sentence <EM>matches</EM> the pattern. A word in
the pattern that does not begin with one of the special <EM>quantifier</EM>
characters listed below matches the identical word in the sentence. A word
in the pattern that does begin with a quantifier matches zero or more words
in the sentence, as follows:
<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
<TR><TD><CODE>@</CODE><TD> zero or more (test as group)
<TR><TD><CODE>^</CODE><TD> zero or more (as few as possible)
</TABLE>
<P>
All quantifiers match as many consecutive words as possible while
still allowing the remaining portion of the pattern to be matched, except
for <CODE>^</CODE>. A quantifier may be used alone, or it can be followed by a
variable name, a predicate name, or both:
<P><PRE>#
#var
#:pred
#var:pred
</PRE>
If a variable name is used, the word or words that match the
quantifier will be stored in that variable if the match is successful. (The
value of the variable if the match is not successful is not guaranteed.) If
a predicate is used, it must take one word as input; in order for a word in
the sentence to be accepted as (part of) a match for the quantifier, the
predicate must output <CODE>true</CODE> when given that word as input. For
example, the word
<P><PRE>!factor:numberp
</PRE>
<P>in the pattern above requires exactly one matching word in the
sentence; that word must be a number, and it is remembered in the variable
<CODE>factor</CODE>. If the quantifier is <CODE>@</CODE> then the predicate must take a
<EM>list</EM> as input, and it must output <CODE>true</CODE> for all the candidate
matching words taken together as a list. For example, if you define a
procedure
<P><PRE>to threep :list
output equalp count :list 3
end
</PRE>
<P>then the pattern word
<P><PRE>@:threep
</PRE>
<P>will match exactly three words in the sentence. (Student does not
use this last feature of the pattern matcher. In fact, predicates are
applied only to the single-word quantifiers <CODE>?</CODE> and <CODE>!</CODE>.)
<P>Pattern matching is also heavily used in converting words and phrases with
mathematical meaning into the corresponding arithmetic operations
(<CODE>opform</CODE>). An equation is a list of three members; the first member is the
word <CODE>equal</CODE> and the other two are expressions formed by applying
operations to variables and numbers. Each operation that is required is
represented as a list whose first member is the name of the Logo procedure
that carries out the operation and whose remaining members are expressions
representing the operands. For example, the equation
<P><CENTER><EM>y</EM> = 3<EM>x</EM><SUP><SMALL>2</SMALL></SUP>
+ 6<EM>x</EM> − 1</CENTER><P>
would be represented by the list
<P><PRE>[equal [y] [sum [product 3 [square [x]]] [product 6 [x]] [minus 1]]]
</PRE>
<P>The variables are represented by lists like <CODE>[x]</CODE> rather than
just the words because in Student a variable can be a multi-word phrase like
<CODE>price of radio</CODE>. The difference between two expressions is represented
by a <CODE>sum</CODE> of one expression and <CODE>minus</CODE> the other, rather than as
the <CODE>difference</CODE> of the expressions, because this representation turns
out to make the process of simplifying and solving the equations easier.
<P>In word problems, as in arithmetic expressions, there is a precedence of
operations. Operations like <CODE>squared</CODE> apply to the variables right next
to them; ones like <CODE>times</CODE> are intermediate, and ones like <CODE>plus</CODE>
apply to the largest possible subexpressions. Student looks first for the
lowest-priority ones like <CODE>plus</CODE>; if one is found, the entire rest of
the clause before and after the operation word provide the operands. Those
operands are recursively processed by <CODE>opform</CODE>; when all the
low-priority operations have been found, the next level of priority will be
found by matching the pattern
<P><PRE>[^left !op:op1 #right]
</PRE>
<P><H2>Solving the Equations</H2>
<P>Student uses the substitution technique to solve the equations. That is,
one equation is rearranged so that the left hand side contains only a single
variable and the right hand side does not contain that variable. Then, in
some other equation, every instance of that variable is replaced by the
right hand side of the first equation. The result is a new equation from
which one variable has been eliminated. Repeating this process enough times
should eventually yield an equation with only a single variable, which can
be solved to find the value of that variable.
<P>When a problem gives rise to several linear equations in several variables,
the traditional technique for computer solution is to use matrix inversion;
this technique is messy for human beings because there is a lot of
arithmetic involved, but straightforward for computers because the algorithm
can be specified in a simple way that doesn't depend on the particular
equations in each problem. Bobrow chose to use the substitution method
because some problems give rise to equations that are linear in the variable
for which a solution is desired but nonlinear in other variables. Consider
this problem:
<P><PRE>? <U>student :tom</U>
The problem to be solved is
If the number of customers Tom gets is twice the square of 20 per cent of
the number of advertisements he runs, and the number of advertisements he
runs is 45, what is the number of customers Tom gets?
With mandatory substitutions the problem is
If the number numof customers Tom gets is 2 times the square 20 percent
numof the number numof advertisements he runs , and the number numof
advertisements he runs is 45 , what is the number numof customers
Tom gets ?
The simple sentences are
The number numof customers Tom gets is 2 times the square 20 percent
numof the number numof advertisements he runs .
The number numof advertisements he runs is 45 .
What is the number numof customers Tom gets ?
The equations to be solved are
Equal [number of customers Tom gets]
[product 2 [square [product 0.2 [number of advertisements
he runs]]]]
Equal [number of advertisements he runs] 45
The number of customers Tom gets is 162
The problem is solved.
</PRE>
<P>The first equation that Student generates for this problem is
linear in the number of customers Tom gets, but nonlinear in the number of
advertisements he runs. (That is, the equation refers to the <EM>square</EM>
of the latter variable. An equation is <EM>linear</EM> in a given variable
if that variable isn't multiplied by anything other than a constant number.)
Using the substitution method, Student can solve the problem by substituting
the value 45, found in the second equation, for the number of advertisements
variable in the first equation.
<P>(Notice, in passing, that one of the special <CODE>numof</CODE> words in this
problem was translated into a multiplication rather than back into the
original word <CODE>of</CODE>.)
<P>The actual sequence of steps required to solve a set of equations is quite
intricate. I recommend taking that part of Student on faith the first time
you read the program, concentrating instead on the pattern matching
techniques used to translate the English sentences into equations. But here
is a rough guide to the solution process. Both <CODE>student1</CODE> and <CODE>
student2</CODE> call <CODE>trysolve</CODE> with four inputs: a list of the equations to
solve, a list of the variables for which values are wanted, and two lists of
<EM>units.</EM> A unit is a word or phrase like <CODE>dollars</CODE> or <CODE>feet</CODE>
that may be part of a solution. Student treats units like variables while
constructing the equations, so the combination of a number and a unit is
represented as a product, like
<P><PRE>[product 69.7 [dollars]]
</PRE>
<P>for 69.70 in the first sample problem. While constructing the
equations, Student generates two lists of units. The first, stored in the
variable <CODE>units</CODE>, contains any word or phrase that appears along with a
number in the problem statement, like the word <CODE>feet</CODE> in the phrase <CODE>
3 feet</CODE> (<CODE>nmtest</CODE>). The second, in the variable <CODE>aunits</CODE>, contains
units mentioned explicitly in the <CODE>find</CODE> or <CODE>how many</CODE> sentences
that tell Student what variables should be part of the solution
(<CODE>senform1</CODE>). If the problem includes a sentence like
<P><PRE>How many inches is a yard?
</PRE>
<P>then the variable <CODE>[inches]</CODE>, and <EM>only</EM> that variable,
is allowed to be part of the answer. If there are no <CODE>aunits</CODE>-type
variables in the problem, then any of the <CODE>units</CODE> variables may appear
in the solution (<CODE>trysolve</CODE>).
<P><CODE>Trysolve</CODE> first calls <CODE>solve</CODE> to solve the equations and then uses
<CODE>pranswers</CODE> to print the results. <CODE>Solve</CODE> calls <CODE>solver</CODE> to do
most of the work and then passes its output through <CODE>solve.reduce</CODE> for
some final cleaning up. <CODE>Solver</CODE> works by picking one of the
variables from the list <CODE>:wanted</CODE> and asking <CODE>solve1</CODE> to find a
solution for that variable in terms of <EM>all</EM> the other variables--the
other wanted variables as well as the units allowed in the ultimate answer.
If <CODE>solve1</CODE> succeeds, then <CODE>solver</CODE> invokes itself,
adding the newly-found expression for one variable to an <EM>
association list</EM> (in the variable <CODE>alis</CODE>) so that, from then
on, any occurrence of that variable will be replaced with the equivalent
expression. In effect, the problem is simplified by eliminating one
variable and eliminating one equation, the one that was solved to find the
equivalent expression.
<P><CODE>Solve1</CODE> first looks for an equation containing the variable for which
it is trying to find a solution. When it finds such an equation, the next
task is to eliminate from that equation any variables that aren't part of
the wanted-plus-units list that <CODE>solver</CODE> gave <CODE>solve1</CODE> as an input.
To eliminate these extra variables, <CODE>solve1</CODE> invokes <CODE>solver</CODE> with
the extras as the list of wanted variables. This mutual recursion between
<CODE>solver</CODE> and <CODE>solve1</CODE> makes the structure of the solution process
difficult to follow. If <CODE>solver</CODE> manages to eliminate the extra
variables by expressing them in terms of the originally wanted ones, then
<CODE>solve1</CODE> can go on to substitute those expressions into its originally
chosen equation and then use <CODE>solveq</CODE> to solve that one equation for the
one selected variable in terms of all the other allowed variables. <CODE>
Solveq</CODE> manipulates the equation more or less the way students in algebra
classes do, adding the same term to both sides, multiplying both sides by
the denominator of a polynomial fraction, and so on.
<P>Here is how <CODE>solve</CODE> solves the radio problem. The equations, again, are
<P><PRE>Equal [price of radio] [product 69.7 [dollars]]
Equal [price of radio] [product 0.85 [marked price]]
</PRE>
<P><CODE>Trysolve</CODE> evaluates the expression
<P><PRE>(1) solve [[marked price]]
[[equal [price of radio] [product 69.7 [dollars]]]
[equal [price of radio] [product 0.85 [marked price]]] ]
[[dollars]]
</PRE>
<P>(I'm numbering these expressions so that I can refer to them later
in the text.) The first input to <CODE>solve</CODE> is the list of variables
wanted in the solution; in this case there is only one such variable. The
second input is the list of two equations. The third is the list of unit
variables that are allowed to appear in the solution; in this case only <CODE>
[dollars]</CODE> is allowed. <CODE>Solve</CODE> evaluates
<P><PRE>(2) solver [[marked price]] [[dollars]] [] []
</PRE>
<P>(There is a fifth input, the word <CODE>insufficient</CODE>, but this is
used only as an error flag if the problem can't be solved. To simplify this
discussion I'm going to ignore that input for both <CODE>solver</CODE> and <CODE>
solve1</CODE>.) <CODE>Solver</CODE> picks the first (in this case, the only) wanted
variable as the major input to <CODE>solve1</CODE>:
<P><PRE>(3) solve1 [marked price]
[[dollars]]
[]
[[equal [price of radio] [product 69.7 [dollars]]]
[equal [price of radio] [product 0.85 [marked price]]] ]
[]
</PRE>
<P>Notice that the first input to <CODE>solve1</CODE> is a single variable,
not a list of variables. <CODE>Solve1</CODE> examines the first equation in the
list of equations making up its fourth input. The desired variable does not
appear in this equation, so <CODE>solve1</CODE> rejects that equation and invokes
itself recursively:
<P><PRE>(4) solve1 [marked price]
[[dollars]]
[]
[[equal [price of radio] [product 0.85 [marked price]]]]
[[equal [price of radio] [product 69.7 [dollars]]]]
</PRE>
<P>This time, the first (and now only) equation on the list of
candidates does contain the desired variable. <CODE>Solve1</CODE> removes that
equation, not from its own list of equations (<CODE>:eqns</CODE>), but from <CODE>
solve</CODE>'s overall list (<CODE>:eqt</CODE>). The equation, unfortunately, can't be
solved directly to express <CODE>[marked price]</CODE> in terms of <CODE>[dollars]</CODE>,
because it contains the extra, unwanted variable <CODE>[price of radio]</CODE>.
We must eliminate this variable by solving the remaining equations for it:
<P><PRE>(5) solver [[price of radio]] [[marked price] [dollars]] [] []
</PRE>
<P>As before, <CODE>solver</CODE> picks the first (again, in this case, the
only) wanted variable and asks <CODE>solve1</CODE> to solve it:
<P><PRE>(6) solve1 [price of radio]
[[marked price] [dollars]]
[]
[[equal [price of radio] [product 69.7 [dollars]]]]
[]
</PRE>
<P><CODE>Solve1</CODE> does find the desired variable in the first (and
only) equation, and this time there are no extra variables. <CODE>Solve1</CODE>
can therefore ask <CODE>solveq</CODE> to solve the equation:
<P><PRE>(7) solveq [price of radio]
[equal [price of radio] [product 69.7 [dollars]]]
</PRE>
<P>It isn't part of <CODE>solveq</CODE>'s job to worry about which variables
may or may not be part of the solution; <CODE>solve1</CODE> doesn't call <CODE>
solveq</CODE> until it's satisfied that the equation is okay.
<P>In this case, <CODE>solveq</CODE> has little work to do because the equation is
already in the desired form, with the chosen variable alone on the left side
and an expression not containing that variable on the right.
<P><PRE>solveq (7) <EM>outputs</EM> [[price of radio] [product 69.7 [dollars]]
<EM>to</EM> solve1 (6)
</PRE>
<P><CODE>Solve1</CODE> appends this result to the previously empty
association list.
<P><PRE>solve1 (6) <EM>outputs</EM> [[[price of radio] [product 69.7 [dollars]]]
<EM>to</EM> solver (5)
</PRE>
<P><CODE>Solver</CODE> only had one variable in its <CODE>:wanted</CODE> list, so
its job is also finished.
<P><PRE>solver (5) <EM>outputs</EM> [[[price of radio] [product 69.7 [dollars]]]
<EM>to</EM> solve1 (4,3)
</PRE>
<P>This outer invocation of <CODE>solve1</CODE> was trying to solve for
<CODE>[marked price]</CODE> an equation that also involved <CODE>[price of radio]</CODE>.
It is now able to use the new association list to substitute for this
unwanted variable an expression in terms of wanted variables only; this
modified equation is then passed on to <CODE>solveq</CODE>:
<P><PRE>(8) solveq [marked price]
[equal [product 69.7 [dollars]] [product 0.85 [marked price]]]
</PRE>
<P>This time <CODE>solveq</CODE> has to work a little harder, exchanging the
two sides of the equation and dividing by 0.85.
<P><PRE>solveq (8) <EM>outputs</EM> [[marked price] [product 82 [dollars]]]
<EM>to</EM> solve1 (4,3)
</PRE>
<P><CODE>Solve1</CODE> appends this result to the association list:
<P><PRE>solve1 (4,3) <EM>outputs</EM> [[[price of radio] [product 69.7 [dollars]]]
[[marked price] [product 82 [dollars]]] ]
<EM>to</EM> solver (2)
</PRE>
<P>Since <CODE>solver</CODE> has no other wanted variables, it outputs the
same list to <CODE>solve</CODE>, and <CODE>solve</CODE> outputs the same list to <CODE>
trysolve</CODE>. (In this example, <CODE>solve.reduce</CODE> has no effect because all
of the expressions in the association list are in terms of allowed units
only. If the equations had been different, the expression for <CODE>[price
of radio]</CODE> might have included <CODE>[marked price]</CODE> and then <CODE>
solve.reduce</CODE> would have had to substitute and simplify (<CODE>subord</CODE>).)
<P>It'll probably take tracing a few more examples and beating your head
against the wall a bit before you really understand the structure of <CODE>
solve</CODE> and its subprocedures. Again, don't get distracted by this part of
the program until you've come to understand the language processing part,
which is our main interest in this chapter.
<P><H2>Age Problems</H2>
<P>The main reason why Student treats age problems specially is that the
English form of such problems is often expressed as if the variables were
people, like "Bill," whereas the real variable is "Bill's age." The
pattern matching transformations look for proper names (<CODE>personp</CODE>) and
insert the words <CODE>s age</CODE> after them (<CODE>ageify</CODE>). The first such age
variable in the problem is remembered specially so that it can be
substituted for pronouns (<CODE>agepron</CODE>). A special case is the phrase <CODE>
their ages</CODE>, which is replaced (<CODE>ageprob</CODE>) with a list of all the age
variables in the problem.
<P><PRE>? <U>student :uncle</U>
The problem to be solved is
Bill's father's uncle is twice as old as Bill's father. 2 years from now
Bill's father will be 3 times as old as Bill. The sum of their ages is
92 . Find Bill's age.
With mandatory substitutions the problem is
Bill s father s uncle is 2 times as old as Bill s father . 2 years
from now Bill s father will be 3 times as old as Bill . sum their
ages is 92 . Find Bill s age .
The simple sentences are
Bill s father s uncle s age is 2 times Bill s father s age .
Bill s father s age pluss 2 is 3 times Bill s age pluss 2 .
Sum Bill s age and Bill s father s age and Bill s father s uncle s age
is 92 .
Find Bill s age .
The equations to be solved are
Equal [Bill s father s uncle s age] [product 2 [Bill s father s age]]
Equal [sum [Bill s father s age] 2] [product 3 [sum [Bill s age] 2]]
Equal [sum [Bill s age]
[sum [Bill s father s age] [Bill s father s uncle s age]]] 92
Bill s age is 8
The problem is solved.
</PRE>
<P>(Note that in the original problem statement there is a space
between the number <CODE>92</CODE> and the following period. I had to enter the
problem in that form because of an inflexibility in Logo's input parser,
which assumes that a period right after a number is part of the number, so
that "<CODE>92.</CODE>" is reformatted into <CODE>92</CODE> without the dot.)
<P>Student represents the possessive word <CODE>Bill's</CODE> as the two words
<CODE>Bill s</CODE> because this representation allows the pattern matcher to
manipulate the possessive marker as a separate element to be matched.
A phrase like <CODE>as old as</CODE> is just deleted (<CODE>ageprob</CODE>) because the
transformation from people to ages makes it redundant.
<P>The phrase <CODE>2 years from now</CODE> in the original problem is first
translated to <CODE>in 2 years</CODE>. This phrase is further processed according
to where it appears in a sentence. When it is attached to a particular
variable, in a phrase like <CODE>Bill s age in 2 years</CODE>, the entire phrase is
translated into the arithmetic operation <CODE>Bill s age pluss 2 years</CODE>
(<CODE>agewhen</CODE>). (The special word <CODE>pluss</CODE> is an addition operator,
just like <CODE>plus</CODE>, except for its precedence; <CODE>opform</CODE> treats it as a
tightly binding operation like <CODE>squared</CODE> instead of a loosely binding
one like the ordinary <CODE>plus</CODE>.) When a phrase like <CODE>in 2 years</CODE>
appears at the beginning of a sentence, it is remembered (<CODE>agesen</CODE>) as
an implicit modifier for <EM>every</EM> age variable in that sentence that
isn't explicitly modified. In this example, <CODE>in 2 years</CODE> modifies both
<CODE>Bill s father s age</CODE> and <CODE>Bill s age</CODE>. The special precedence of
<CODE>pluss</CODE> is needed in this example so that the equation will be based on
the grouping
<P><PRE>3 times [ Bill s age pluss 2 ]
</PRE>
<P>rather than
<P><PRE>[ 3 times Bill s age ] plus 2
</PRE>
<P>as it would be with the ordinary <CODE>plus</CODE> operator. You can
also see how the substitution for <CODE>their ages</CODE> works in this example.
<P>Here is a second sample age problem that illustrates a different kind of
special handling:
<P><PRE>? <U>student :ann</U>
The problem to be solved is
Mary is twice as old as Ann was when Mary was as old as Ann is now. If
Mary is 24 years old, how old is Ann?
With mandatory substitutions the problem is
Mary is 2 times as old as Ann was when Mary was as old as Ann is now . If
Mary is 24 years old , what is Ann ?
The simple sentences are
Mary s age is 2 times Ann s age minuss g1 .
Mary s age minuss g1 is Ann s age .
Mary s age is 24 .
What is Ann s age ?
The equations to be solved are
Equal [Mary s age] [product 2 [sum [Ann s age] [minus [g1]]]]
Equal [sum [Mary s age] [minus [g1]]] [Ann s age]
Equal [Mary s age] 24
Ann s age is 18
The problem is solved.
</PRE>
<P>What is new in this example is Student's handling of the phrase <CODE>was
when</CODE> in the sentence
<P><PRE>Mary is 2 times as old as Ann was when Mary was as old as Ann is now .
</PRE>
<P>Sentences like this one often cause trouble for human algebra students
because they make <EM>implicit</EM> reference to a quantity that is not
explicitly present as a variable. The sentence says that Mary's age <EM>
now</EM> is twice Ann's age <EM>some number</EM> of years ago, but that number
is not explicit in the problem. Student makes this variable explicit by
using a <EM>generated symbol</EM> like the word <CODE>g1</CODE> in this illustration.
Student replaces the phrase <CODE>was when</CODE> with the words
<P><PRE>was g1 years ago . g1 years ago
</PRE>
<P>This substitution (in <CODE>ageprob</CODE>) happens <EM>before</EM> the
division of the problem statement into simple sentences (<CODE>bracket</CODE>). As
a result, this one sentence in the original problem becomes the two sentences
<P><PRE>Mary s age is 2 times Ann s age g1 years ago .
G1 years ago Mary s age was Ann s age now .
</PRE>
<P>The phrase <CODE>g1 years ago</CODE> in each of these sentences is
further processed by <CODE>agesen</CODE> and <CODE>agewhen</CODE> as discussed earlier;
the final result is
<P><PRE>Mary s age is 2 times Ann s age minuss g1 .
Mary s age minuss g1 is Ann s age .
</PRE>
<P>A new generated symbol is created each time this situation arises,
so there is no conflict from trying to use the same variable name for two
different purposes. The phrase <CODE>will be when</CODE> is handled similarly,
except that the translated version is
<P><PRE>in g2 years . in g2 years
</PRE>
<P><H2>AI and Education</H2>
<BLOCKQUOTE>
<P><A NAME="bobrow2">These decoupling heuristics</A> are useful
not only for the Student program but
for people trying to solve age problems. The classic age problem about Mary
and Ann, given above, took an MIT graduate student over 5 minutes to solve
because he did not know this heuristic. With the heuristic he was able to
set up the appropriate equations much more rapidly. As a crude measure of
Student's relative speed, note that Student took less than one minute to
solve this problem.
</BLOCKQUOTE>
<P>This excerpt from Bobrow's thesis illustrates the idea that
insights from artificial intelligence research can make a valuable
contribution to the education of human beings. An intellectual problem is
solved, at least in many cases, by dividing it into pieces and developing a
technique for each subproblem. The subproblems are the same whether it is a
computer or a person trying to solve the problem. If a certain technique
proves valuable for the computer, it may be helpful for a human problem
solver to be aware of the computer's methods. Bobrow's suggestion to teach
people one specific heuristic for algebra word problems is a relatively
modest example of this general theme. (A <EM>heuristic</EM> is a rule that
gives the right answer most of the time, as opposed to an <EM>
algorithm,</EM> a
rule that always works.) Some researchers in cognitive science and
education have proposed the idea of <EM>intelligent CAI</EM>
(computer assisted instruction), in which a computer would be programmed as a
"tutor" that would observe the efforts of a student in solving a problem.
The tutor would know about some of the mistaken ideas people can have about
a particular class of problem and would notice a student falling into one
of those traps. It could then offer advice tailored to the needs of that
individual student.
<P>The development of the Logo programming language (and so also, indirectly,
this series of books) is another example of the relationship between AI and
education. Part of the idea behind Logo is that the process of programming
a computer resembles, in some ways, the process of teaching a person to do
something. (This can include teaching oneself.) For example, when a
computer program doesn't work, the experienced programmer doesn't give up in
despair, but instead <EM>debugs</EM> the program. Yet many students are
willing to give up and say "I just don't get it" if their understanding of
some problem isn't perfect on the first try.
<BLOCKQUOTE>
<P><A NAME="papert">The critic</A> is afraid
that children will adopt the computer as model and
eventually come to "think mechanically" themselves. Following the
opposite tack, I have invented ways to take educational advantage of the
opportunities to master the art of <EM>deliberately</EM> thinking like a
computer, according, for example, to the stereotype of a computer program
that proceeds in a step-by-step, literal, mechanical fashion. There are
situations where this style of thinking is appropriate and useful. Some
children's difficulties in learning formal subjects such as grammar or
mathematics derive from their inability to see the point of such a style.
<P>
A second educational advantage is indirect but ultimately more important.
By deliberately learning to imitate mechanical thinking, the learner becomes
able to articulate what mechanical thinking is and what it is not. The
exercise can lead to greater confidence about the ability to choose a
cognitive style that suits the problem. Analysis of "mechanical thinking"
and how it is different from other kinds and practice with problem analysis
can result in a new degree of intellectual sophistication. By providing a
very concrete, down-to-earth model of a particular style of thinking, work
with the computer can make it easier to understand that there is such a
thing as a "style of thinking." And giving children the opportunity to
choose one style or another provides an opportunity to develop the skill
necessary to choose between styles. Thus instead of inducing mechanical
thinking, contact with computers could turn out to be the best conceivable
antidote to it. And for me what is most important in this is that through
these experiences these children would be serving their apprenticeships as
epistemologists, that is to say learning to think articulately about
thinking. [Seymour Papert, <EM>Mindstorms</EM>, Basic Books, 1980, p. 27.]
</BLOCKQUOTE>
<P><H2>Combining Sentences Into One Equation</H2>
<P>In age problems, as we've just seen, a single sentence may give rise to two
equations. Here is an example of the opposite, several sentences that
together contribute a single equation.
<P><PRE>? <U>student :nums</U>
The problem to be solved is
A number is multiplied by 6 . This product is increased by 44 . This
result is 68 . Find the number.
With mandatory substitutions the problem is
A number ismulby 6 . This product is increased by 44 . This result is
68 . Find the number .
The simple sentences are
A number ismulby 6 .
This product is increased by 44 .
This result is 68 .
Find the number .
The equations to be solved are
Equal [sum [product [number] 6] 44] 68
The number is 4
The problem is solved.
</PRE>
<P>Student recognizes problems like this by recognizing the phrases "is
multiplied by," "is divided by," and "is increased by" (<CODE>senform1</CODE>).
A sentence containing one of these phrases is not translated into an
equation; instead, a <EM>partial</EM> equation is saved until the next
sentence is read. That next sentence is expected to start with a phrase
like "this result" or "this product." The same procedure (<CODE>this</CODE>)
that in other situations uses the left hand side of the last equation as the
expression for the <CODE>this</CODE>-phrase notices that there is a remembered
partial equation and uses that instead. In this example, the sentence
<P><PRE>A number ismulby 6 .
</PRE>
<P>remembers the algebraic expression
<P><PRE>[product [number] 6]
</PRE>
<P>The second sentence uses that remembered expression as part of a
new, larger expression to be remembered:
<P><PRE>[sum [product [number] 6] 44]
</PRE>
<P>The third sentence does not contain one of the special "is
increased by" phrases, but is instead a standard "A is B" sentence.
That sentence, therefore, does give rise to an equation, as shown above.
<P>Perhaps the most interesting thing to notice about this category of word
problem is how narrowly defined Student's criterion for recognizing the
category is. Student gets away with it because algebra word problems are
highly <EM>stereotyped;</EM> there are just a few categories, with
traditional, standard wordings. In principle there could be a word problem
starting
<P><PRE>Robert has a certain number of jelly beans. This number is twice the
number of jelly beans Linda has.
</PRE>
<P>These two sentences are together equivalent to
<P><PRE>The number of jelly beans Robert has is twice the number of jelly beans
Linda has.
</PRE>
<P>But Student would not recognize the situation because the first
sentence doesn't talk about "is increased by." We could teach Student to
understand a word problem in this form by adding the instruction
<P><PRE>if match [^one !verb1:verb a certain number of #stuff1 !:dlm] :sent
[push "ref opform (se [the number of] :stuff1 :one :verb1)
op []]
</PRE>
<P>along with the other known sentence forms in <CODE>senform1</CODE>.
(Compare this to the pattern matching instruction shown earlier for a
similar sentence but with an explicitly specified number.)
<P>Taking advantage of the stereotyped nature of word problems is an example of
how the microworld strategy helped make the early AI programs possible. If
word problems were expressed with all the flexibility of language in general,
Student would need many more sentence patterns than it actually has. (How
many different ways can you think of to express the same idea about Robert
and Linda? How many of those ways can Student handle?)
<P><H2>Allowing Flexible Phrasing</H2>
<P>In the examples we've seen so far, Student has relied on the repetition of
identical or near-identical phrases such as "the marked price" or "the
number of advertisements he runs." (The requirement is not quite strictly
identical phrases because articles are removed from the noun phrases to make
variable names.) In real writing, though, such phrases are often
abbreviated when they appear for a second time. Student will translate such
a problem into a system of equations that can't be solved, because what
should be one variable is instead a different variable in each equation.
But Student can recognize this situation and apply heuristic rules to guess
that two similar variable names are meant, in fact, to represent the same
variable. (Some early writers on AI considered the use of heuristic methods
one of the defining characteristics of the field. Computer scientists
outside of AI were more likely to insist on fully reliable algorithms. This
distinction still has some truth to it, but it isn't emphasized so much as a
critical issue these days.) Student doesn't try to equate different
variables until it has first tried to solve the equations as they are
originally generated. If the first attempt at solution fails, Student has
recourse to less certain techniques (<CODE>student2</CODE> calls <CODE>vartest</CODE>).
<P><PRE>? <U>student :sally</U>
The problem to be solved is
The sum of Sally's share of some money and Frank's share is 4.50.
Sally's share is twice Frank's. Find Frank's and Sally's share.
With mandatory substitutions the problem is
sum Sally s share numof some money and Frank s share is 4.50 dollars .
Sally s share is 2 times Frank s . Find Frank s and Sally s share .
The simple sentences are
Sum Sally s share numof some money and Frank s share is 4.50 dollars .
Sally s share is 2 times Frank s .
Find Frank s and Sally s share .
The equations to be solved are
Equal [sum [Sally s share of some money] [Frank s share]]
[product 4.50 [dollars]]
Equal [Sally s share] [product 2 [Frank s]]
The equations were insufficient to find a solution.
Assuming that
[Frank s] is equal to [Frank s share]
Assuming that
[Sally s share] is equal to [Sally s share of some money]
Frank s is 1.5 dollars
Sally s share is 3 dollars
The problem is solved.
</PRE>
<P>In this problem Student has found two pairs of similar variable names.
When it finds such a pair, Student adds an equation of the form
<P><PRE>[equal <EM>variable1</EM> <EM>variable2</EM>]
</PRE>
<P>to the previous set of equations. In both of the pairs in this
example, the variable that appears later in the problem statement is
entirely contained within the one that appears earlier.
<P>Another point of interest in this example is that the variable <CODE>[dollars]</CODE>
is included in the list of units that may be part of the answer. The word
problem does not explicitly ask "How many dollars is Sally's share," but
because one of the sentences sets an expression equal to "4.50 dollars"
Student takes that as implicit permission to express the answer in dollars.
<P>The only other condition under which Student will consider two variables
equal is if their names are identical except that some phrase in the one
that appears earlier is replaced with a pronoun in the one that appears
later. That is, a variable like <CODE>[the number of ice cream cones the
children eat]</CODE> will be considered equal to a later variable <CODE>[the number
of ice cream cones they eat]</CODE>. Here is a problem in which this rule is
applied:
<P><PRE>? <U>student :guns</U>
The problem to be solved is
The number of soldiers the Russians have is one half of the number of
guns they have. They have 7000 guns. How many soldiers do they have?
With mandatory substitutions the problem is
The number numof soldiers the Russians have is 0.5 numof the number numof
guns they have . They have 7000 guns . howm soldiers do they have ?
The simple sentences are
The number numof soldiers the Russians have is 0.5 numof the number numof
guns they have .
They have 7000 guns .
Howm soldiers do they have ?
The equations to be solved are
Equal [number of soldiers Russians have]
[product 0.5 [number of guns they have]]
Equal [number of guns they have] 7000
The equations were insufficient to find a solution.
Assuming that
[number of soldiers they have] is equal to
[number of soldiers Russians have]
The number of soldiers they have is 3500
The problem is solved.
</PRE>
<P><H2>Using Background Knowledge</H2>
<P>In some word problems, not all of the necessary information is contained
within the problem statement itself. The problem requires the student to
supply some piece of general knowledge about the world in order to determine
the appropriate equations. This knowledge may be about unit conversions
(one foot is 12 inches) or about relationships among physical quantities
(distance equals speed times time). Student "knows" some of this <EM>
background</EM> information and can apply it (<CODE>geteqns</CODE>) if the equations
determined by the problem statement are insufficient.
<P><PRE>? <U>student :jet</U>
The problem to be solved is
The distance from New York to Los Angeles is 3000 miles. If the average
speed of a jet plane is 600 miles per hour, find the time it takes to
travel from New York to Los Angeles by jet.
With mandatory substitutions the problem is
The distance from New York to Los Angeles is 3000 miles . If the average
speed numof a jet plane is 600 miles per hour , find the time it takes to
travel from New York to Los Angeles by jet .
The simple sentences are
The distance from New York to Los Angeles is 3000 miles .
The average speed numof a jet plane is 600 miles per hour .
Find the time it takes to travel from New York to Los Angeles by jet .
The equations to be solved are
Equal [distance from New York to Los Angeles] [product 3000 [miles]]
Equal [average speed of jet plane]
[quotient [product 600 [miles]] [product 1 [hours]]]
The equations were insufficient to find a solution.
Using the following known relationships
Equal [distance] [product [speed] [time]]
Equal [distance] [product [gas consumption]
[number of gallons of gas used]]
Assuming that
[speed] is equal to [average speed of jet plane]
Assuming that
[time] is equal to [time it takes to travel
from New York to Los Angeles by jet]
Assuming that
[distance] is equal to [distance from New York to Los Angeles]
The time it takes to travel from New York
to Los Angeles by jet is 5 hours
The problem is solved.
</PRE>
<P>Student's library of known relationships is indexed according to the first
word of the name of each variable involved in the relationship. (If a
variable starts with the words <CODE>number of</CODE> it is indexed under the
following word.) The relationships, in the form of equations, are stored in
the property lists of these index words.
<P>Property lists are also used to keep track of irregular plurals and the
corresponding singulars. Student tries to keep all units in plural form
internally, so that if a problem refers to both <CODE>1 foot</CODE> and <CODE>
2 feet</CODE> the same variable name will be used for both. (That is, the first
of these will be translated into
<P><PRE>[product 1 [feet]]
</PRE>
<P>in Student's internal representation. Then the opposite
translation is needed if the product of <CODE>1</CODE> and some unit appears in an
answer to be printed.
<P>The original Student also used property lists to remember the parts of
speech of words and the precedence of operators, but because of differences
in the syntax of the Meteor pattern matcher and my Logo pattern matcher I've
found it easier to use predicate operations for that purpose.
<P>The original Student system included a separately invoked <CODE>remember</CODE>
procedure that allowed all these kinds of global information to be entered
in the form of English sentences. You'd say
<P><PRE>Feet is the plural of foot
</PRE>
<P>or
<P><PRE>Distance equals speed times time
</PRE>
<P>and <CODE>remember</CODE> would use patterns much like those used in
understanding word problems to translate these sentences into <CODE>pprop</CODE>
instructions. Since Lisp programs, like Logo programs, can themselves be
manipulated as lists, <CODE>remember</CODE> could even accept information of a
kind that's stored in
the Student program itself, such as the wording transformations in <CODE>
idioms</CODE>, and modify the program to reflect this information. I haven't
bothered to implement that part of the Student system because it takes up
extra memory and doesn't exhibit any new techniques.
<P>As the above example shows, it's important that Student's search for
relevant known relationships comes before the attempt to equate variables
with similar names. The general relationship that uses a variable named
simply <CODE>[distance]</CODE> doesn't help unless Student can identify it as
relevant to the variable named <CODE>[distance from New York to Los Angeles]</CODE>
in the specific problem under consideration.
<P>Here is another example in which known relationships are used:
<P><PRE>? <U>student :span</U>
The problem to be solved is
If 1 span is 9 inches, and 1 fathom is 6 feet,
how many spans is 1 fathom?
With mandatory substitutions the problem is
If 1 span is 9 inches , and 1 fathom is 6 feet , howm spans is 1 fathom ?
The simple sentences are
1 span is 9 inches .
1 fathom is 6 feet .
Howm spans is 1 fathom ?
The equations to be solved are
Equal [product 1 [spans]] [product 9 [inches]]
Equal [product 1 [fathoms]] [product 6 [feet]]
Equal g2 [product 1 [fathoms]]
The equations were insufficient to find a solution.
Using the following known relationships
Equal [product 1 [yards]] [product 3 [feet]]
Equal [product 1 [feet]] [product 12 [inches]]
1 fathom is 8 spans
The problem is solved.
</PRE>
<P>Besides the use of known relationships, this example illustrates two other
features of Student. One is the use of an explicitly requested unit in the
answer. Since the problem asks
<P><PRE>How many spans is 1 fathom?
</PRE>
<P>Student knows that the answer must be expressed in <CODE>spans</CODE>.
Had there been no explicit request for a particular unit, all the units that
appear in phrases along with a number would be eligible to appear in the
answer: <CODE>inches</CODE>, <CODE>feet</CODE>, and <CODE>fathoms</CODE>. Student might then
blithely inform us that
<P><PRE>1 fathom is 1 fathom
The problem is solved.
</PRE>
<P>The other new feature demonstrated by this example is the use of a generated
symbol to represent the desired answer. In the statement of this problem,
there is no explicit variable representing the unknown. <CODE>[Fathoms]</CODE> is
a <EM>unit,</EM> not a variable for which a value could be found. The problem
asks for the value of the expression
<P><PRE>[product 1 [fathoms]]
</PRE>
<P>in terms of spans. Student generates a variable name (<CODE>g2</CODE>)
to represent the unknown and produces an equation
<P><PRE>[equal g2 [product 1 [fathoms]]
</PRE>
<P>to add to the list of equations. A generated symbol will be
needed whenever the "Find" or "What is" sentence asks for an expression
rather than a simple variable name. For example, an age problem that asks
"What is the sum of their ages" would require the use of a generated
symbol. (The original Student <EM>always</EM> used a generated symbol for
the unknowns, even if there was already a single variable in the problem
representing an unknown. It therefore had equations like
<P><PRE>[equal g3 [marked price]]
</PRE>
<P>in its list, declaring one variable equal to another. I chose to
check for this case and avoid the use of a generated symbol because the time
spent in the actual solution of the equations increases quadratically with
the number of equations.)
<P><H2>Optional Substitutions</H2>
<P>We have seen many cases in which Student replaces a phrase in the statement
of a problem with a different word or phrase that fits better with the later
stages of processing, like the substitution of <CODE>2 times</CODE> for <CODE>twice</CODE>
or a special keyword like <CODE>perless</CODE> for <CODE>percent less than</CODE>.
Student also has a few cases of <EM>optional</EM> substitutions that may or
may not be made (<CODE>tryidiom</CODE>).
<P>There are two ways in which optional substitutions can happen. One is
exemplified by the phrase <CODE>the perimeter of the rectangle</CODE>. Student
first attempts the problem without any special processing of this phrase.
If a solution is not found, Student then replaces the phrase with <CODE>twice
the sum of the length and width of the rectangle</CODE> and processes the
resulting new problem from the beginning. Unlike the use of known
relationships or similarity of variable names, which Student handles by
adding to the already-determined equations, this optional substitution
requires the entire translation process to begin again. For example, the
word <CODE>twice</CODE> that begins the replacement phrase will be further
translated to <CODE>2 times</CODE>.
<P>The second category of optional substitution is triggered by the phrase <CODE>
two numbers</CODE>. This phrase must always be translated to something, because
it indicates that two different variables are needed. But the precise
translation depends on the wording of the rest of the problem. Student
tries two alternative translations: <CODE>one of the numbers and the other
number</CODE> and <CODE>one number and the other number</CODE>. Here is an example in
which the necessary translation is the one Student tries second:
<P><PRE>? <U>student :sumtwo</U>
The problem to be solved is
The sum of two numbers is 96, and one number is 16 larger than the other
number. Find the two numbers.
The problem with an idiomatic substitution is
The sum of one of the numbers and the other number is 96 , and one
number is16 larger than the other number . Find the one of the numbers
and the other number .
With mandatory substitutions the problem is
sum one numof the numbers and the other number is 96 , and one number
is 16 plus the other number . Find the one numof the numbers and the
other number .
The simple sentences are
Sum one numof the numbers and the other number is 96 .
One number is 16 plus the other number .
Find the one numof the numbers and the other number .
The equations to be solved are
Equal [sum [one of numbers] [other number]] 96
Equal [one number] [sum 16 [other number]]
The equations were insufficient to find a solution.
The problem with an idiomatic substitution is
The sum of one number and the other number is 96 , and one number is 16
larger than the other number . Find the one number and the other number .
With mandatory substitutions the problem is
sum one number and the other number is 96 , and one number is 16 plus the
other number . Find the one number and the other number .
The simple sentences are
Sum one number and the other number is 96 .
One number is 16 plus the other number .
Find the one number and the other number .
The equations to be solved are
Equal [sum [one number] [other number]] 96
Equal [one number] [sum 16 [other number]]
The one number is 56
The other number is 40
The problem is solved.
</PRE>
<P>There is no essential reason why Student uses one mechanism rather than
another to deal with a particular problematic situation. The difficulties
about perimeters and about the phrase "two numbers" might have been solved
using mechanisms other than this optional substitution one. For example,
the equation
<P><PRE>[equal [perimeter] [product 2 [sum [length] [width]]]]
</PRE>
<P>might have been added to the library of known relationships. The
difficulty about alternate phrasings for "two numbers" could be solved by
adding
<P><PRE>[[one of the !word:pluralp] ["one singular :word]]
</PRE>
<P>to the list of idiomatic substitutions in <CODE>idiom</CODE>.
<P>Not all the mechanisms are equivalent, however. The "two numbers" problem
couldn't be solved by adding equations to the library of known relationships,
because that phrase appears as part of a larger phrase like "the sum of two
numbers," and Student's understanding of the word <CODE>sum</CODE> doesn't allow
it to be part of a variable name. The word <CODE>sum</CODE> only makes sense to
Student in the context of a phrase like <CODE>the sum of <CODE><EM>
something</EM></CODE> and <CODE><EM>something else</EM></CODE></CODE>. (See procedure <CODE>tst.sum</CODE>.)
<P><H2>If All Else Fails</H2>
<P>Sometimes Student fails to solve a problem because the problem is beyond
either its linguistic capability or its algebraic capability. For example,
Student doesn't know how to solve quadratic equations. But sometimes a
problem that Student could solve in principle stumps it because it happens
to lack a particular piece of common knowledge. When a situation like that
arises, Student is capable of asking the user for help (<CODE>student2</CODE>).
<P><PRE>? <U>student :ship</U>
The problem to be solved is
The gross weight of a ship is 20000 tons. If its net weight is 15000
tons, what is the weight of the ships cargo?
With mandatory substitutions the problem is
The gross weight numof a ship is 20000 tons . If its net weight is 15000
tons , what is the weight numof the ships cargo ?
The simple sentences are
The gross weight numof a ship is 20000 tons .
Its net weight is 15000 tons .
What is the weight numof the ships cargo ?
The equations to be solved are
Equal [gross weight of ship] [product 20000 [tons]]
Equal [its net weight] [product 15000 [tons]]
The equations were insufficient to find a solution.
Do you know any more relationships among these variables?
Weight of ships cargo
Its net weight
Tons
Gross weight of ship
<U>The weight of a ships cargo is the gross weight minus the net weight</U>
Assuming that
[net weight] is equal to [its net weight]
Assuming that
[gross weight] is equal to [gross weight of ship]
The weight of the ships cargo is 5000 tons
The problem is solved.
</PRE>
<P><H2>Limitations of Pattern Matching</H2>
<P>Student relies on certain stereotyped forms of sentences in the problems it
solves. It's easy to make up problems that will completely bewilder it:
<P><PRE>Suppose you have 14 jelly beans. You give 2 each to Tom, Dick, and
Harry. How many do you have left?
</PRE>
<P>The first mistake Student makes is that it thinks the word <CODE>
and</CODE> following a comma separates two clauses; it generates simple sentences
<P><PRE>You give 2 each to Tom , Dick .
Harry .
</PRE>
<P>This is quite a fundamental problem; Student's understanding of
the difference between a phrase and a clause is extremely primitive and
prone to error. Adding another pattern won't solve this one; the trouble
is that Student pays no attention to the words in between the key words like
<CODE>and</CODE>.
<P>There are several other difficulties with this problem, some worse than
others. Student doesn't recognize the word <CODE>suppose</CODE> as having a
special function in the sentence, so it makes up a noun phrase <CODE>suppose
you</CODE> just like <CODE>the russians</CODE>. This could be fixed with an idiomatic
substitution that just ignored <CODE>suppose</CODE>. Another relatively small
problem is that the sentence starting <CODE>how many</CODE> doesn't say how many of
what; Student needs a way to understand that the relevant noun phrase is
<CODE>jelly beans</CODE> and not, for example, <CODE>Tom</CODE>. The words <CODE>give</CODE>
(representing subtraction) and <CODE>each</CODE> (representing counting a set and
then multiplying) have special mathematical meanings comparable to <CODE>
percent less</CODE>. A much more subtle problem
in knowledge representation is
that in this problem there are two different quantities that could be called
<CODE>the number of jelly beans you have</CODE>: the number you have at the
beginning of the problem and the number you have at the end. Student has a
limited understanding of this passage-of-time difficulty when it's doing an
age problem, but not in general.
<P>How many more difficulties can you find in this problem? For how many of
them can you invent improvements to Student to get around them?
<P>Some difficulties seem to require a "more of the same" strategy: adding
some new patterns to Student that are similar to the ones already there.
Other difficulties seem to require a more fundamental redesign. Can that
redesign be done using a pattern matcher as the central tool, or are more
powerful tools needed? How powerful <EM>is</EM> pattern matching, anyway?
<P>Answering questions like these is the job of automata theory. From that
point of view, the answer is that it depends exactly what you mean by
"pattern matching." The pattern matcher used in Student is equivalent
to a finite-state machine. The important thing to note about the patterns
used in Student is that they only apply predicates to one word at a time,
not to groups of words. In other words, they don't use the <CODE>@</CODE>
quantifier. Here is a typical <CODE>student</CODE> pattern:
<P><PRE>[^ what !:in [is are] #one !:dlm]
</PRE>
<P>For the purposes of this discussion, you can ignore the fact that
the pattern matcher can set variables to remember which words matched each
part of the pattern. In comparing a pattern matcher to a finite-state
machine, the question we're asking is what categories of strings can the
pattern matcher accept. This particular pattern is equivalent to the
following machine:
<P><CENTER><IMG SRC="pattern.gif" ALT="figure: pattern"></CENTER>
<P>The arrow that I've labeled <EM>dlm</EM> is actually several arrows
connecting the same states, one for each symbol that the predicate <CODE>dlm</CODE>
accepts, i.e., period, question mark, and semicolon. Similarly, the arrows
labeled <EM>any</EM> are followed for any symbol at all. This machine is
nondeterministic, but you'll recall that that doesn't matter; we can turn it
into a deterministic one if necessary.
<P>To be sure you understand the equivalence of patterns and finite-state
machines, see if you can draw a machine equivalent to this pattern:
<P><PRE>[I see !:in [the a an] ?:numberp &:adjective !:noun #:adverb]
</PRE>
<P>This pattern uses all the quantifiers that test words one at a
time.
<P>If these patterns are equivalent to finite-state machines, you'd expect them
to have trouble recognizing sentences that involve <EM>embedding</EM> of
clauses within clauses, since these pose the same problem as keeping track
of balancing of parentheses. For example, a sentence like "The book that
the boy whom I saw yesterday was reading is interesting" would strain the
capabilities of a finite-state machine. (As in the case of parentheses, we
could design a FSM that could handle such sentences up to some fixed depth
of embedding, but not one that could handle arbitrarily deep embedding.)
<P><H2>Context-Free Languages</H2>
<P>If we allow the use of the <CODE>@</CODE> quantifier in patterns, and if the
predicates used to test substrings of the sentences are true functions
without side effects, then the pattern matcher is equivalent to an RTN or a
production rule grammar. What makes an RTN different from a finite-state
machine is that the former can include arrows that match several symbols
against another (or the same) RTN. Equivalently, the <CODE>@</CODE> quantifier
matches several symbols against another (or the same) pattern.
<P>A language that can be represented by an RTN is called a <EM>
context-free</EM> language. The reason for the name is that in such a
language a given string consistently matches or doesn't match a given
predicate regardless of the rest of the sentence. That's the point of what
I said just above about side effects; the output from a test predicate
can't depend on anything other than its input. Pascal is a context-free
language because
<P><PRE>this := that
</PRE>
<P>is always an assignment statement regardless of what other statements
might be in the program with it.
<P>What <EM>isn't</EM> a context-free language? The classic example in automata
theory is the language consisting of the strings
<P><PRE>abc
aabbcc
aaabbbccc
aaaabbbbcccc
</PRE>
<P>and so on, with the requirement that the number of <CODE>a</CODE>s be
equal to the number of <CODE>b</CODE>s and also equal to the number of <CODE>c</CODE>s.
That language can't be represented as RTNs or production rules. (Try it.
Don't confuse it with the language that accepts any number of <CODE>a</CODE>s
followed by any number of <CODE>b</CODE>s and so on; even a finite-state machine
can represent that one. The equal number requirement is important.)
<P>The classic formal system that can represent <EM>any</EM> language for which
there are precise rules is the Turing machine. Its advantage over
the RTN is precisely that it can "jump around" in its memory, looking at
one part while making decisions about another part.
<P>There is a sharp theoretical boundary between context-free and
context-sensitive languages, but in practice the boundary is sometimes fuzzy.
Consider again the case of Pascal and that assignment statement. I said
that it's recognizably an assignment statement because it matches a
production rule like
<P><PRE>assignment : identifier := expression
</PRE>
<P>(along with a bunch of other rules that determine what qualifies
as an expression). But that production rule doesn't really express <EM>
all</EM> the requirements for a legal Pascal assignment statement. For
example, the identifier and the expression must be of the same type. The
actual Pascal compiler (any Pascal compiler, not just mine) includes
instructions that represent the formal grammar plus extra instructions that
represent the additional requirements.
<P>The type agreement rule is an example of context sensitivity. The types of
the relevant identifiers were determined in <CODE>var</CODE> declarations earlier
in the program; those declarations are part of what determines whether the
given string of symbols is a legal assignment.
<P><H2>Augmented Transition Networks</H2>
<P>One could create a clean formal description of Pascal, type agreement rules
and all, by designing a Turing machine to accept Pascal programs. However,
Turing machines aren't easy to work with for any practical problem. It's
much easier to set up a context-free grammar for Pascal and then throw in a
few side effects to handle the context-sensitive aspects of the language.
<P>Much the same is true of English. It's possible to set up an RTN (or a
production rule grammar) for noun phrases, for example, and another one for
verb phrases. It's tempting then to set up an RTN for a sentence like this:
<P><CENTER><IMG SRC="sentence.gif" ALT="figure: sentence"></CENTER>
<P>This machine captures some, but not all, of the rules of English.
It's true that a sentence requires a noun phrase (the subject) and a verb
phrase (the predicate). But there are <EM>agreement</EM> rules for person
and number (I <EM>run</EM> but he <EM>runs</EM>) analogous to the type
agreement rules of Pascal.
<P>Some artificial intelligence researchers, understanding all this, parse
English sentences using a formal description called an <EM>
augmented transition network</EM> (ATN). An ATN is just
like an RTN except
that each transition arrow can have associated with it not only the name of
a symbol or another RTN but also some <EM>conditions</EM> that must be met in
order to follow the arrow and some <EM>actions</EM> that the program should
take if the arrow is followed. For example, we could turn the RTN just
above into an ATN by adding an action to the first arrow saying "store the
number (singular or plural) of the noun phrase in the variable <CODE>
number</CODE>" and adding a condition to the second arrow saying "the number of
the verb phrase must be equal to the variable <CODE>number</CODE>."
<P>Subject-predicate agreement is not the only rule in English grammar best
expressed as a side effect in a transition network. Below is an ATN
for noun phrases taken from <EM>Language as a Cognitive Process, Volume 1:
Syntax</EM> by Terry Winograd (page 598). I'm not going to attempt to explain
the notation or the detailed rules here, but just to give one example, the
condition labeled "h16p" says that the transition for apostrophe-s can be
followed if the head of the phrase is an ordinary noun ("the book's") but
not if it's a pronoun ("you's").
<P>
<CENTER><A NAME="winograd"><IMG SRC="atn.gif" ALT="figure: atn"></A></CENTER>
<P>The ATN is equivalent in power to a Turing machine; there is no known
mechanism that is more flexible in carrying out algorithms. The flexibility
has a cost, though. The time required to parse a string with an ATN is not
bounded by a polynomial function. (Remember, the time for an RTN is
O(<EM>n</EM><SUP><SMALL>3</SMALL></SUP>).) It can easily be exponential, O(2<SUP><SMALL><EM>n</EM></SMALL></SUP>). One reason is that a
context-sensitive procedure can't be subject to memoization. If two
invocations of the same procedure with the same inputs can give different
results because of side effects, it does no good to remember what result we
got the last time. Turning an ATN into a practical program is often
possible, but not a trivial task.
<P>In thinking about ATNs we've brought together most of the topics in this
book: formal systems, algorithms, language parsing, and artificial
intelligence. Perhaps that's a good place to stop.
<P>
<TABLE width="100%"><TR><TD><A HREF="../v3-toc2.html">(back to Table of Contents)</A>
<TD align="right"><A HREF="../v3ch5/v3ch5.html"><STRONG>BACK</STRONG></A>
chapter thread <A HREF="https://people.eecs.berkeley.edu/~bh/v3ch7/v3ch7.html"><STRONG>NEXT</STRONG></A>
</TABLE>
<H2>Program Listing</H2>
<P><PRE>
to student :prob
say [The problem to be solved is] :prob
make "prob map.se [depunct ?] :prob
localmake "orgprob :prob
student1 :prob ~
[[[the perimeter of ! rectangle]
[twice the sum of the length and width of the rectangle]]
[[two numbers] [one of the numbers and the other number]]
[[two numbers] [one number and the other number]]]
end
to student1 :prob :idioms
local [simsen shelf aunits units wanted ans var lasteqn
ref eqt1 beg end idiom reply]
make "prob idioms :prob
if match [^ two numbers #] :prob ~
[make "idiom find [match (sentence "^beg first ? "#end) :orgprob] :idioms ~
tryidiom stop]
while [match [^beg the the #end] :prob] [make "prob (sentence :beg "the :end)]
say [With mandatory substitutions the problem is] :prob
ifelse match [# @:in [[as old as] [age] [years old]] #] :prob ~
[ageprob] [make "simsen bracket :prob]
lsay [The simple sentences are] :simsen
foreach [aunits wanted ans var lasteqn ref units] [make ? []]
make "shelf filter [not emptyp ?] map.se [senform ?] :simsen
lsay [The equations to be solved are] :shelf
make "units remdup :units
if trysolve :shelf :wanted :units :aunits [print [The problem is solved.] stop]
make "eqt1 remdup geteqns :var
if not emptyp :eqt1 [lsay [Using the following known relationships] :eqt1]
student2 :eqt1
end
to student2 :eqt1
make "var remdup sentence (map.se [varterms ?] :eqt1) :var
make "eqt1 sentence :eqt1 vartest :var
if not emptyp :eqt1 ~
[if trysolve (sentence :shelf :eqt1) :wanted :units :aunits
[print [The problem is solved.] stop]]
make "idiom find [match (sentence "^beg first ? "#end) :orgprob] :idioms
if not emptyp :idiom [tryidiom stop]
lsay [Do you know any more relationships among these variables?] :var
make "reply readlist
if equalp :reply [yes] [print [Tell me.] make "reply readlist]
if equalp :reply [no] [print [] print [I can't solve this problem.] stop]
make "reply map.se [depunct ?] :reply
if dlm last :reply [make "reply butlast :reply]
if not match [^beg is #end] :reply [print [I don't understand that.] stop]
make "shelf sentence :shelf :eqt1
student2 (list (list "equal opform :beg opform :end))
end
;; Mandatory substitutions
to depunct :word
if emptyp :word [output []]
if equalp first :word "$ [output sentence "$ depunct butfirst :word]
if equalp last :word "% [output sentence depunct butlast :word "percent]
if memberp last :word [. ? |;| ,] [output sentence depunct butlast :word last :word]
if emptyp butfirst :word [output :word]
if equalp last2 :word "'s [output sentence depunct butlast butlast :word "s]
output :word
end
to last2 :word
output word (last butlast :word) (last :word)
end
to idioms :sent
local "number
output changes :sent ~
[[[the sum of] ["sum]] [[square of] ["square]] [[of] ["numof]]
[[how old] ["what]] [[is equal to] ["is]]
[[years younger than] [[less than]]] [[years older than] ["plus]]
[[percent less than] ["perless]] [[less than] ["lessthan]]
[[these] ["the]] [[more than] ["plus]]
[[first two numbers] [[the first number and the second number]]]
[[three numbers]
[[the first number and the second number and the third number]]]
[[one half] [0.5]] [[twice] [[2 times]]]
[[$ !number] [sentence :number "dollars]] [[consecutive to] [[1 plus]]]
[[larger than] ["plus]] [[per cent] ["percent]] [[how many] ["howm]]
[[is multiplied by] ["ismulby]] [[is divided by] ["isdivby]]
[[multiplied by] ["times]] [[divided by] ["divby]]]
end
to changes :sent :list
localmake "keywords map.se [findkey first ?] :list
output changes1 :sent :list :keywords
end
to findkey :pattern
if equalp first :pattern "!:in [output first butfirst :pattern]
if equalp first :pattern "?:in [output sentence (item 2 :pattern) (item 3 :pattern)]
output first :pattern
end
to changes1 :sent :list :keywords
if emptyp :sent [output []]
if memberp first :sent :keywords [output changes2 :sent :list :keywords]
output fput first :sent changes1 butfirst :sent :list :keywords
end
to changes2 :sent :list :keywords
changes3 :list :list
output fput first :sent changes1 butfirst :sent :list :keywords
end
to changes3 :biglist :nowlist
if emptyp :nowlist [stop]
if changeone first :nowlist [changes3 :biglist :biglist stop]
changes3 :biglist butfirst :nowlist
end
to changeone :change
local "end
if not match (sentence first :change [#end]) :sent [output "false]
make "sent run (sentence "sentence last :change ":end)
output "true
end
;; Division into simple sentences
to bracket :prob
output bkt1 finddelim :prob
end
to finddelim :sent
output finddelim1 :sent [] []
end
to finddelim1 :in :out :simples
if emptyp :in ~
[ifelse emptyp :out [output :simples] [output lput (sentence :out ".) :simples]]
if dlm first :in ~
[output finddelim1 (nocap butfirst :in) []
(lput (sentence :out first :in) :simples)]
output finddelim1 (butfirst :in) (sentence :out first :in) :simples
end
to nocap :words
if emptyp :words [output []]
if personp first :words [output :words]
output sentence (lowercase first :words) butfirst :words
end
to bkt1 :problist
local [first word rest]
if emptyp :problist [output []]
if not memberp ", first :problist ~
[output fput first :problist bkt1 butfirst :problist]
if match [if ^first , !word:qword #rest] first :problist ~
[output bkt1 fput (sentence :first ".)
fput (sentence :word :rest) butfirst :problist]
if match [^first , and #rest] first :problist ~
[output fput (sentence :first ".) (bkt1 fput :rest butfirst :problist)]
output fput first :problist bkt1 butfirst :problist
end
;; Age problems
to ageprob
local [beg end sym who num subj ages]
while [match [^beg as old as #end] :prob] [make "prob sentence :beg :end]
while [match [^beg years old #end] :prob] [make "prob sentence :beg :end]
while [match [^beg will be when #end] :prob] ~
[make "sym gensym
make "prob (sentence :beg "in :sym [years . in] :sym "years :end)]
while [match [^beg was when #end] :prob] ~
[make "sym gensym
make "prob (sentence :beg :sym [years ago .] :sym [years ago] :end)]
while [match [^beg !who:personp will be in !num years #end] :prob] ~
[make "prob (sentence :beg :who [s age in] :num "years #end)]
while [match [^beg was #end] :prob] [make "prob (sentence :beg "is :end)]
while [match [^beg will be #end] :prob] [make "prob (sentence :beg "is :end)]
while [match [^beg !who:personp is now #end] :prob] ~
[make "prob (sentence :beg :who [s age now] :end)]
while [match [^beg !num years from now #end] :prob] ~
[make "prob (sentence :beg "in :num "years :end)]
make "prob ageify :prob
ifelse match [^ !who:personp ^end s age #] :prob ~
[make "subj sentence :who :end] [make "subj "someone]
make "prob agepron :prob
make "end :prob
make "ages []
while [match [^ !who:personp ^beg age #end] :end] ~
[push "ages (sentence "and :who :beg "age)]
make "ages butfirst reduce "sentence remdup :ages
while [match [^beg their ages #end] :prob] [make "prob (sentence :beg :ages :end)]
make "simsen map [agesen ?] bracket :prob
end
to ageify :sent
if emptyp :sent [output []]
if not personp first :sent [output fput first :sent ageify butfirst :sent]
catch "error [if equalp first butfirst :sent "s
[output fput first :sent ageify butfirst :sent]]
output (sentence first :sent [s age] ageify butfirst :sent)
end
to agepron :sent
if emptyp :sent [output []]
if not pronoun first :sent [output fput first :sent agepron butfirst :sent]
if posspro first :sent [output (sentence :subj "s agepron butfirst :sent)]
output (sentence :subj [s age] agepron butfirst :sent)
end
to agesen :sent
local [when rest num]
make "when []
if match [in !num years #rest] :sent ~
[make "when sentence "pluss :num make "sent :rest]
if match [!num years ago #rest] :sent ~
[make "when sentence "minuss :num make "sent :rest]
output agewhen :sent
end
to agewhen :sent
if emptyp :sent [output []]
if not equalp first :sent "age [output fput first :sent agewhen butfirst :sent]
if match [in !num years #rest] butfirst :sent ~
[output (sentence [age pluss] :num agewhen :rest)]
if match [!num years ago #rest] butfirst :sent ~
[output (sentence [age minuss] :num agewhen :rest)]
if equalp "now first butfirst :sent ~
[output sentence "age agewhen butfirst butfirst :sent]
output (sentence "age :when agewhen butfirst :sent)
end
;; Translation from sentences into equations
to senform :sent
make "lasteqn senform1 :sent
output :lasteqn
end
to senform1 :sent
local [one two verb1 verb2 stuff1 stuff2 factor]
if emptyp :sent [output []]
if match [^ what are ^one and ^two !:dlm] :sent ~
[output fput (qset :one) (senform (sentence [what are] :two "?))]
if match [^ what !:in [is are] #one !:dlm] :sent ~
[output (list qset :one)]
if match [^ howm !one is #two !:dlm] :sent ~
[push "aunits (list :one) output (list qset :two)]
if match [^ howm ^one do ^two have !:dlm] :sent ~
[output (list qset (sentence [the number of] :one :two "have))]
if match [^ howm ^one does ^two have !:dlm] :sent ~
[output (list qset (sentence [the number of] :one :two "has))]
if match [^ find ^one and #two] :sent ~
[output fput (qset :one) (senform sentence "find :two)]
if match [^ find #one !:dlm] :sent [output (list qset :one)]
make "sent filter [not article ?] :sent
if match [^one ismulby #two] :sent ~
[push "ref (list "product opform :one opform :two) output []]
if match [^one isdivby #two] :sent ~
[push "ref (list "quotient opform :one opform :two) output []]
if match [^one is increased by #two] :sent ~
[push "ref (list "sum opform :one opform :two) output []]
if match [^one is #two] :sent ~
[output (list (list "equal opform :one opform :two))]
if match [^one !verb1:verb ^factor as many ^stuff1 as
^two !verb2:verb ^stuff2 !:dlm] ~
:sent ~
[if emptyp :stuff2 [make "stuff2 :stuff1]
output (list (list "equal ~
opform (sentence [the number of] :stuff1 :one :verb1) ~
opform (sentence :factor [the number of] :stuff2 :two :verb2)))]
if match [^one !verb1:verb !factor:numberp #stuff1 !:dlm] :sent ~
[output (list (list "equal ~
opform (sentence [the number of] :stuff1 :one :verb1) ~
opform (list :factor)))]
say [This sentence form is not recognized:] :sent
throw "error
end
to qset :sent
localmake "opform opform filter [not article ?] :sent
if not operatorp first :opform ~
[queue "wanted :opform queue "ans list :opform oprem :sent output []]
localmake "gensym gensym
queue "wanted :gensym
queue "ans list :gensym oprem :sent
output (list "equal :gensym opform (filter [not article ?] :sent))
end
to oprem :sent
output map [ifelse equalp ? "numof ["of] [?]] :sent
end
to opform :expr
local [left right op]
if match [^left !op:op2 #right] :expr [output optest :op :left :right]
if match [^left !op:op1 #right] :expr [output optest :op :left :right]
if match [^left !op:op0 #right] :expr [output optest :op :left :right]
if match [#left !:dlm] :expr [make "expr :left]
output nmtest filter [not article ?] :expr
end
to optest :op :left :right
output run (list (word "tst. :op) :left :right)
end
to tst.numof :left :right
if numberp last :left [output (list "product opform :left opform :right)]
output opform (sentence :left "of :right)
end
to tst.divby :left :right
output (list "quotient opform :left opform :right)
end
to tst.tothepower :left :right
output (list "expt opform :left opform :right)
end
to expt :num :pow
if :pow < 1 [output 1]
output :num * expt :num :pow - 1
end
to tst.per :left :right
output (list "quotient ~
opform :left ~
opform (ifelse numberp first :right [:right] [fput 1 :right]))
end
to tst.lessthan :left :right
output opdiff opform :right opform :left
end
to opdiff :left :right
output (list "sum :left (list "minus :right))
end
to tst.minus :left :right
if emptyp :left [output list "minus opform :right]
output opdiff opform :left opform :right
end
to tst.minuss :left :right
output tst.minus :left :right
end
to tst.sum :left :right
local [one two three]
if match [^one and ^two and #three] :right ~
[output (list "sum opform :one opform (sentence "sum :two "and :three))]
if match [^one and #two] :right ~
[output (list "sum opform :one opform :two)]
say [sum used wrong:] :right
throw "error
end
to tst.squared :left :right
output list "square opform :left
end
to tst.difference :left :right
local [one two]
if match [between ^one and #two] :right [output opdiff opform :one opform :two]
say [Incorrect use of difference:] :right
throw "error
end
to tst.plus :left :right
output (list "sum opform :left opform :right)
end
to tst.pluss :left :right
output tst.plus :left :right
end
to square :x
output :x * :x
end
to tst.square :left :right
output list "square opform :right
end
to tst.percent :left :right
if not numberp last :left ~
[say [Incorrect use of percent:] :left throw "error]
output opform (sentence butlast :left ((last :left) / 100) :right)
end
to tst.perless :left :right
if not numberp last :left ~
[say [Incorrect use of percent:] :left throw "error]
output (list "product ~
(opform sentence butlast :left ((100 - (last :left)) / 100)) ~
opform :right)
end
to tst.times :left :right
if emptyp :left [say [Incorrect use of times:] :right throw "error]
output (list "product opform :left opform :right)
end
to nmtest :expr
if match [& !:numberp #] :expr [say [argument error:] :expr throw "error]
if and (equalp first :expr 1) (1 < count :expr) ~
[make "expr (sentence 1 plural (first butfirst :expr) (butfirst butfirst :expr))]
if and (numberp first :expr) (1 < count :expr) ~
[push "units (list first butfirst :expr) ~
output (list "product (first :expr) (opform butfirst :expr))]
if numberp first :expr [output first :expr]
if memberp "this :expr [output this :expr]
if not memberp :expr :var [push "var :expr]
output :expr
end
to this :expr
if not emptyp :ref [output pop "ref]
if not emptyp :lasteqn [output first butfirst last :lasteqn]
if equalp first :expr "this [make "expr butfirst :expr]
push "var :expr
output :expr
end
;; Solving the equations
to trysolve :shelf :wanted :units :aunits
local "solution
make "solution solve :wanted :shelf (ifelse emptyp :aunits [:units] [:aunits])
output pranswers :ans :solution
end
to solve :wanted :eqt :terms
output solve.reduce solver :wanted :terms [] [] "insufficient
end
to solve.reduce :soln
if emptyp :soln [output []]
if wordp :soln [output :soln]
if emptyp butfirst :soln [output :soln]
local "part
make "part solve.reduce butfirst :soln
output fput (list (first first :soln) (subord last first :soln :part)) :part
end
to solver :wanted :terms :alis :failed :err
local [one result restwant]
if emptyp :wanted [output :err]
make "one solve1 (first :wanted) ~
(sentence butfirst :wanted :failed :terms) ~
:alis :eqt [] "insufficient
if wordp :one ~
[output solver (butfirst :wanted) :terms :alis (fput first :wanted :failed) :one]
make "restwant (sentence :failed butfirst :wanted)
if emptyp :restwant [output :one]
make "result solver :restwant :terms :one [] "insufficient
if listp :result [output :result]
output solver (butfirst :wanted) :terms :alis (fput first :wanted :failed) :one
end
to solve1 :x :terms :alis :eqns :failed :err
local [thiseq vars extras xterms others result]
if emptyp :eqns [output :err]
make "thiseq subord (first :eqns) :alis
make "vars varterms :thiseq
if not memberp :x :vars ~
[output solve1 :x :terms :alis (butfirst :eqns) (fput first :eqns :failed) :err]
make "xterms fput :x :terms
make "extras setminus :vars :xterms
make "eqt remove (first :eqns) :eqt
if not emptyp :extras ~
[make "others solver :extras :xterms :alis [] "insufficient
ifelse wordp :others
[make "eqt sentence :failed :eqns
output solve1 :x :terms :alis (butfirst :eqns)
(fput first :eqns :failed) :others]
[make "alis :others
make "thiseq subord (first :eqns) :alis]]
make "result solveq :x :thiseq
if listp :result [output lput :result :alis]
make "eqt sentence :failed :eqns
output solve1 :x :terms :alis (butfirst :eqns) (fput first :eqns :failed) :result
end
to solveq :var :eqn
local [left right]
make "left first butfirst :eqn
ifelse occvar :var :left ~
[make "right last :eqn] [make "right :left make "left last :eqn]
output solveq1 :left :right "true
end
to solveq1 :left :right :bothtest
if :bothtest [if occvar :var :right [output solveqboth :left :right]]
if equalp :left :var [output list :var :right]
if wordp :left [output "unsolvable]
local "oper
make "oper first :left
if memberp :oper [sum product minus quotient] [output run (list word "solveq. :oper)]
output "unsolvable
end
to solveqboth :left :right
if not equalp first :right "sum [output solveq1 (subterm :left :right) 0 "false]
output solveq.rplus :left butfirst :right []
end
to solveq.rplus :left :right :newright
if emptyp :right [output solveq1 :left (simone "sum :newright) "false]
if occvar :var first :right ~
[output solveq.rplus (subterm :left first :right) butfirst :right :newright]
output solveq.rplus :left butfirst :right (fput first :right :newright)
end
to solveq.sum
if emptyp butfirst butfirst :left [output solveq1 first butfirst :left :right "true]
output solveq.sum1 butfirst :left :right []
end
to solveq.sum1 :left :right :newleft
if emptyp :left [output solveq.sum2]
if occvar :var first :left ~
[output solveq.sum1 butfirst :left :right fput first :left :newleft]
output solveq.sum1 butfirst :left (subterm :right first :left) :newleft
end
to solveq.sum2
if emptyp butfirst :newleft [output solveq1 first :newleft :right "true]
localmake "factor factor :newleft :var
if equalp first :factor "unknown [output "unsolvable]
if equalp last :factor 0 [output "unsolvable]
output solveq1 first :factor (divterm :right last :factor) "true
end
to solveq.minus
output solveq1 (first butfirst :left) (minusin :right) "false
end
to solveq.product
output solveq.product1 :left :right
end
to solveq.product1 :left :right
if emptyp butfirst butfirst :left [output solveq1 (first butfirst :left) :right "true]
if not occvar :var first butfirst :left ~
[output solveq.product1 (fput "product butfirst butfirst :left)
(divterm :right first butfirst :left)]
localmake "rest simone "product butfirst butfirst :left
if occvar :var :rest [output "unsolvable]
output solveq1 (first butfirst :left) (divterm :right :rest) "false
end
to solveq.quotient
if occvar :var first butfirst :left ~
[output solveq1 (first butfirst :left) (simtimes list :right last :left) "true]
output solveq1 (simtimes list :right last :left) (first butfirst :left) "true
end
to denom :fract :addends
make "addends simplus :addends
localmake "den last :fract
if not equalp first :addends "quotient ~
[output simdiv list (simone "sum
(remop "sum list (distribtimes (list :addends) :den)
first butfirst :fract))
:den]
if equalp :den last :addends ~
[output simdiv (simplus list (first butfirst :fract) (first butfirst :addends))
:den]
localmake "lowterms simdiv list :den last :addends
output simdiv list (simplus (simtimes list first butfirst :fract last :lowterms)
(simtimes list first butfirst :addends
first butfirst :lowterms)) ~
(simtimes list first butfirst :lowterms last :addends)
end
to distribtimes :trms :multiplier
output simplus map [simtimes (list ? :multiplier)] :trms
end
to distribx :expr
local [oper args]
if emptyp :expr [output :expr]
make "oper first :expr
if not operatorp :oper [output :expr]
make "args map [distribx ?] butfirst :expr
if reduce "and map [numberp ?] :args [output run (sentence [(] :oper :args [)])]
if equalp :oper "sum [output simplus :args]
if equalp :oper "minus [output minusin first :args]
if equalp :oper "product [output simtimes :args]
if equalp :oper "quotient [output simdiv :args]
output fput :oper :args
end
to divterm :dividend :divisor
if equalp :dividend 0 [output 0]
output simdiv list :dividend :divisor
end
to factor :exprs :var
local "trms
make "trms map [factor1 :var ?] :exprs
if memberp "unknown :trms [output fput "unknown :exprs]
output list :var simplus :trms
end
to factor1 :var :expr
localmake "negvar minusin :var
if equalp :var :expr [output 1]
if equalp :negvar :expr [output -1]
if emptyp :expr [output "unknown]
if equalp first :expr "product [output factor2 butfirst :expr]
if not equalp first :expr "quotient [output "unknown]
localmake "dividend first butfirst :expr
if equalp :var :dividend [output (list "quotient 1 last :expr)]
if not equalp first :dividend "product [output "unknown]
localmake "result factor2 butfirst :dividend
if equalp :result "unknown [output "unknown]
output (list "quotient :result last :expr)
end
to factor2 :trms
if memberp :var :trms [output simone "product (remove :var :trms)]
if memberp :negvar :trms [output minusin simone "product (remove :negvar :trms)]
output "unknown
end
to maybeadd :num :rest
if equalp :num 0 [output :rest]
output fput :num :rest
end
to maybemul :num :rest
if equalp :num 1 [output :rest]
output fput :num :rest
end
to minusin :expr
if emptyp :expr [output -1]
if equalp first :expr "sum [output fput "sum map [minusin ?] butfirst :expr]
if equalp first :expr "minus [output last :expr]
if memberp first :expr [product quotient] ~
[output fput first :expr
(fput (minusin first butfirst :expr) butfirst butfirst :expr)]
if numberp :expr [output minus :expr]
output list "minus :expr
end
to occvar :var :expr
if emptyp :expr [output "false]
if wordp :expr [output equalp :var :expr]
if operatorp first :expr [output not emptyp find [occvar :var ?] butfirst :expr]
output equalp :var :expr
end
to remfactor :num :den
foreach butfirst :num [remfactor1 ?]
output (list "quotient (simone "product butfirst :num) (simone "product butfirst :den))
end
to remfactor1 :expr
local "neg
if memberp :expr :den ~
[make "num remove :expr :num make "den remove :expr :den stop]
make "neg minusin :expr
if not memberp :neg :den [stop]
make "num remove :expr :num
make "den minusin remove :neg :den
end
to remop :oper :exprs
output map.se [ifelse equalp first ? :oper [butfirst ?] [(list ?)]] :exprs
end
to simdiv :list
local [num den numop denop]
make "num first :list
make "den last :list
if equalp :num :den [output 1]
if numberp :den [output simtimes (list (quotient 1 :den) :num)]
make "numop first :num
make "denop first :den
if equalp :numop "quotient ~
[output simdiv list (first butfirst :num) (simtimes list last :num :den)]
if equalp :denop "quotient ~
[output simdiv list (simtimes list :num last :den) (first butfirst :den)]
if and equalp :numop "product equalp :denop "product [output remfactor :num :den]
if and equalp :numop "product memberp :den :num [output remove :den :num]
output fput "quotient :list
end
to simone :oper :trms
if emptyp :trms [output ifelse equalp :oper "product [1] [0]]
if emptyp butfirst :trms [output first :trms]
output fput :oper :trms
end
to simplus :exprs
make "exprs remop "sum :exprs
localmake "factor [unknown]
catch "simplus ~
[foreach :terms ~
[make "factor (factor :exprs ?) ~
if not equalp first :factor "unknown [throw "simplus]]]
if not equalp first :factor "unknown [output fput "product remop "product :factor]
localmake "nums 0
localmake "nonnums []
localmake "quick []
catch "simplus [simplus1 :exprs]
if not emptyp :quick [output :quick]
if not equalp :nums 0 [push "nonnums :nums]
output simone "sum :nonnums
end
to simplus1 :exprs
if emptyp :exprs [stop]
simplus2 first :exprs
simplus1 butfirst :exprs
end
to simplus2 :pos
local "neg
make "neg minusin :pos
if numberp :pos [make "nums sum :pos :nums stop]
if memberp :neg butfirst :exprs [make "exprs remove :neg :exprs stop]
if equalp first :pos "quotient ~
[make "quick (denom :pos (maybeadd :nums sentence :nonnums butfirst :exprs)) ~
throw "simplus]
push "nonnums :pos
end
to simtimes :exprs
local [nums nonnums quick]
make "nums 1
make "nonnums []
make "quick []
catch "simtimes [foreach remop "product :exprs [simtimes1 ?]]
if not emptyp :quick [output :quick]
if equalp :nums 0 [output 0]
if not equalp :nums 1 [push "nonnums :nums]
output simone "product :nonnums
end
to simtimes1 :expr
if equalp :expr 0 [make "nums 0 throw "simtimes]
if numberp :expr [make "nums product :expr :nums stop]
if equalp first :expr "sum ~
[make "quick distribtimes (butfirst :expr)
(simone "product maybemul :nums sentence :nonnums ?rest)
throw "simtimes]
if equalp first :expr "quotient ~
[make "quick
simdiv (list (simtimes (list (first butfirst :expr)
(simone "product
maybemul :nums
sentence :nonnums ?rest)))
(last :expr))
throw "simtimes]
push "nonnums :expr
end
to subord :expr :alist
output distribx subord1 :expr :alist
end
to subord1 :expr :alist
if emptyp :alist [output :expr]
output subord (substop (last first :alist) (first first :alist) :expr) ~
(butfirst :alist)
end
to substop :val :var :expr
if emptyp :expr [output []]
if equalp :expr :var [output :val]
if not operatorp first :expr [output :expr]
output fput first :expr map [substop :val :var ?] butfirst :expr
end
to subterm :minuend :subtrahend
if equalp :minuend 0 [output minusin :subtrahend]
if equalp :minuend :subtrahend [output 0]
output simplus (list :minuend minusin :subtrahend)
end
to varterms :expr
if emptyp :expr [output []]
if numberp :expr [output []]
if wordp :expr [output (list :expr)]
if operatorp first :expr [output map.se [varterms ?] butfirst :expr]
output (list :expr)
end
;; Printing the solutions
to pranswers :ans :solution
print []
if equalp :solution "unsolvable ~
[print [Unable to solve this set of equations.] output "false]
if equalp :solution "insufficient ~
[print [The equations were insufficient to find a solution.] output "false]
localmake "gotall "true
foreach :ans [if prans ? :solution [make "gotall "false]]
if not :gotall [print [] print [Unable to solve this set of equations.]]
output :gotall
end
to prans :ans :solution
localmake "result find [equalp first ? first :ans] :solution
if emptyp :result [output "true]
print (sentence cap last :ans "is unitstring last :result)
print []
output "false
end
to unitstring :expr
if numberp :expr [output roundoff :expr]
if equalp first :expr "product ~
[output sentence (unitstring first butfirst :expr)
(reduce "sentence butfirst butfirst :expr)]
if (and (listp :expr)
(not numberp first :expr)
(not operatorp first :expr)) ~
[output (sentence 1 (singular first :expr) (butfirst :expr))]
output :expr
end
to roundoff :num
if (abs (:num - round :num)) < 0.0001 [output round :num]
output :num
end
to abs :num
output ifelse (:num < 0) [-:num] [:num]
end
;; Using known relationships
to geteqns :vars
output map.se [gprop varkey ? "eqns] :vars
end
to varkey :var
local "word
if match [number of !word #] :var [output :word]
output first :var
end
;; Assuming equality of similar variables
to vartest :vars
if emptyp :vars [output []]
local [var beg end]
make "var first :vars
output (sentence (ifelse match [^beg !:pronoun #end] :var
[vartest1 :var (sentence :beg "& :end) butfirst :vars]
[[]])
(vartest1 :var (sentence "# :var "#) butfirst :vars)
(vartest butfirst :vars))
end
to vartest1 :target :pat :vars
output map [varequal :target ?] filter [match :pat ?] :vars
end
to varequal :target :var
print []
print [Assuming that]
print (sentence (list :target) [is equal to] (list :var))
output (list "equal :target :var)
end
;; Optional substitutions
to tryidiom
make "prob (sentence :beg last :idiom :end)
while [match (sentence "^beg first :idiom "#end) :prob] ~
[make "prob (sentence :beg last :idiom :end)]
say [The problem with an idiomatic substitution is] :prob
student1 :prob (remove :idiom :idioms)
end
;; Utility procedures
to qword :word
output memberp :word [find what howm how]
end
to dlm :word
output memberp :word [. ? |;|]
end
to article :word
output memberp :word [a an the]
end
to verb :word
output memberp :word [have has get gets weigh weighs]
end
to personp :word
output memberp :word [Mary Ann Bill Tom Sally Frank father uncle]
end
to pronoun :word
output memberp :word [he she it him her they them his her its]
end
to posspro :word
output memberp :word [his her its]
end
to op0 :word
output memberp :word [pluss minuss squared tothepower per sum difference numof]
end
to op1 :word
output memberp :word [times divby square]
end
to op2 :word
output memberp :word [plus minus lessthan percent perless]
end
to operatorp :word
output memberp :word [sum minus product quotient expt square equal]
end
to plural :word
localmake "plural gprop :word "plural
if not emptyp :plural [output :plural]
if not emptyp gprop :word "sing [output :word]
if equalp last :word "s [output :word]
output word :word "s
end
to singular :word
localmake "sing gprop :word "sing
if not emptyp :sing [output :sing]
if not emptyp gprop :word "plural [output :word]
if equalp last :word "s [output butlast :word]
output :word
end
to setminus :big :little
output filter [not memberp ? :little] :big
end
to say :herald :text
print []
print :herald
print []
print :text
print []
end
to lsay :herald :text
print []
print :herald
print []
foreach :text [print cap ? print []]
end
to cap :sent
if emptyp :sent [output []]
output sentence (word uppercase first first :sent butfirst first :sent) ~
butfirst :sent
end
;; The pattern matcher
to match :pat :sen
if prematch :pat :sen [output rmatch :pat :sen]
output "false
end
to prematch :pat :sen
if emptyp :pat [output "true]
if listp first :pat [output prematch butfirst :pat :sen]
if memberp first first :pat [! @ # ^ & ?] [output prematch butfirst :pat :sen]
if emptyp :sen [output "false]
localmake "rest member first :pat :sen
if not emptyp :rest [output prematch butfirst :pat :rest]
output "false
end
to rmatch :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 rmatch butfirst :pat butfirst :sen]
output "false
end
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
to match!
if emptyp :sen [output "false]
if not try.pred [output "false]
make :special.var first :sen
output rmatch butfirst :pat butfirst :sen
end
to match?
make :special.var []
if emptyp :sen [output rmatch butfirst :pat :sen]
if not try.pred [output rmatch butfirst :pat :sen]
make :special.var first :sen
if rmatch butfirst :pat butfirst :sen [output "true]
make :special.var []
output rmatch butfirst :pat :sen
end
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 rmatch 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
to match&
output &test match#
end
to &test :tf
if emptyp thing :special.var [output "false]
output :tf
end
to match^
make :special.var []
output ^test :sen
end
to ^test :sen
if rmatch 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
to match@
make :special.var :sen
output @test []
end
to @test :sen
if @try.pred [if rmatch 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
to try.pred
if listp :special.pred [output rmatch :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 rmatch :special.pred thing :special.var]
output run list :special.pred thing :special.var
end
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 rmatch first :pats :sen [output "true]
output anyof1 :sen butfirst :pats
end
;; Sample word problems
make "ann [Mary is twice as old as Ann was when Mary was as old as Ann is now.
If Mary is 24 years old, how old is Ann?]
make "guns [The number of soldiers the Russians have is
one half of the number of guns they have. They have 7000 guns.
How many soldiers do they have?]
make "jet [The distance from New York to Los Angeles is 3000 miles.
If the average speed of a jet plane is 600 miles per hour,
find the time it takes to travel from New York to Los Angeles by jet.]
make "nums [A number is multiplied by 6 . This product is increased by 44 .
This result is 68 . Find the number.]
make "radio [The price of a radio is $69.70.
If this price is 15 percent less than the marked price, find the marked price.]
make "sally [The sum of Sally's share of some money and Frank's share is $4.50.
Sally's share is twice Frank's. Find Frank's and Sally's share.]
make "ship [The gross weight of a ship is 20000 tons.
If its net weight is 15000 tons, what is the weight of the ships cargo?]
make "span [If 1 span is 9 inches, and 1 fathom is 6 feet,
how many spans is 1 fathom?]
make "sumtwo [The sum of two numbers is 96,
and one number is 16 larger than the other number. Find the two numbers.]
make "tom [If the number of customers Tom gets is
twice the square of 20 per cent of the number of advertisements he runs,
and the number of advertisements he runs is 45,
what is the number of customers Tom gets?]
make "uncle [Bill's father's uncle is twice as old as Bill's father.
2 years from now Bill's father will be 3 times as old as Bill.
The sum of their ages is 92 . Find Bill's age.]
;; Initial data base
pprop "distance "eqns ~
[[equal [distance] [product [speed] [time]]]
[equal [distance] [product [gas consumtion] [number of gallons of gas used]]]]
pprop "feet "eqns ~
[[equal [product 1 [feet]] [product 12 [inches]]]
[equal [product 1 [yards]] [product 3 [feet]]]]
pprop "feet "sing "foot
pprop "foot "plural "feet
pprop "gallons "eqns ~
[[equal [distance] [product [gas consumtion] [number of gallons of gas used]]]]
pprop "gas "eqns ~
[[equal [distance] [product [gas consumtion] [number of gallons of gas used]]]]
pprop "inch "plural "inches
pprop "inches "eqns [[equal [product 1 [feet]] [product 12 [inches]]]]
pprop "people "sing "person
pprop "person "plural "people
pprop "speed "eqns [[equal [distance] [product [speed] [time]]]]
pprop "time "eqns [[equal [distance] [product [speed] [time]]]]
pprop "yards "eqns [[equal [product 1 [yards]] [product 3 [feet]]]]
</PRE>
<P><A HREF="../v3-toc2.html">(back to Table of Contents)</A>
<P><A HREF="../v3ch5/v3ch5.html"><STRONG>BACK</STRONG></A>
chapter thread <A HREF="https://people.eecs.berkeley.edu/~bh/v3ch7/v3ch7.html"><STRONG>NEXT</STRONG></A>
<P>
<ADDRESS>
<A HREF="../index.html">Brian Harvey</A>,
<CODE>bh@cs.berkeley.edu</CODE>
</ADDRESS>
</BODY>
</HTML>
|