[4347fa]: s-doc.txt  Maximize  Restore  History

Download this file

1743 lines (1328 with data), 83.4 kB

   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
;This is the 09/02/92 version of the on-line documentation for
;Richard C. Waters' Series macro package.
;------------------------------------------------------------------------
;Copyright Massachusetts Institute of Technology, Cambridge, Massachusetts.
;Permission to use, copy, modify, and distribute this software and its
;documentation for any purpose and without fee is hereby granted,
;provided that this copyright and permission notice appear in all
;copies and supporting documentation, and that the name of M.I.T. not
;be used in advertising or publicity pertaining to distribution of the
;software without specific, written prior permission. M.I.T. makes no
;representations about the suitability of this software for any
;purpose. It is provided "as is" without express or implied warranty.
; M.I.T. DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING
; ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL
; M.I.T. BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR
; ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,
; WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION,
; ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS
; SOFTWARE.
;------------------------------------------------------------------------
Installing Series
The functions and forms discussed in this manual are defined in the
package "SERIES". To make these names easily accessible, you must use
the package "SERIES". The most convenient way to do this is to call
the function SERIES::INSTALL, which also sets up some additional
features of the series macro package. The examples in this documentation
assume that the form (SERIES::INSTALL) has been evaluated.
SERIES::INSTALL &key (:pkg *package*) (:macro T) (:shadow T) (:remove nil)
Calling this function sets up Series for use in the package :PKG. The
argument :PKG can either be a package, a package name, or a symbol
whose name is the name of a package. It defaults to the current
package.
The package "SERIES" is used in :PKG. If :MACRO is not NIL, the #
macro character syntax #Z and #M is set up. If :SHADOW is not NIL,
the symbols SERIES::LET, SERIES::LET*, SERIES::MULTIPLE-VALUE-BIND,
SERIES::FUNCALL, and SERIES::DEFUN are shadowing imported into :PKG.
These forms are identical to their standard counterparts, except that
they support various features of the Series macro package. When
shadowing is not done, you have to explicitly use SERIES::LET,
SERIES::LET*, and SERIES::MULTIPLE-VALUE-BIND when binding series in
an expression you want optimized; SERIES::FUNCALL when funcalling a
series function you want optimized; and SERIES::DEFUN when defining a
series function with the declaration OPTIMIZABLE-SERIES-FUNCTION.
If :REMOVE is not NIL, the effects of having previously
installed the Series macro package are undone. In particular, the package is
unused and any shadowing is undone. However, any changes to the readtable
are left in place.
The Series Macro Package
Series combine aspects of sequences, streams, and loops. Like sequences,
series represent totally ordered multi-sets. In addition, the series
functions have the same flavor as the sequence functions---namely, they
operate on whole series, rather than extracting elements to be processed by
other functions. For instance, the series expression below computes the
sum of the positive elements in a list.
(COLLECT-SUM (CHOOSE-IF #'PLUSP (SCAN '(1 -2 3 -4)))) => 4
Like streams, series can represent unbounded sets of elements and are
supported by lazy evaluation: Each element of a series is not computed
until it is needed. For instance, the series expression below returns a
list of the first five even natural numbers and their sum. The call on
SCAN-RANGE returns a series of all the even natural numbers. However,
since no elements beyond the first five are ever used, no elements beyond
the first five are ever computed.
(LET ((X (SUBSERIES (SCAN-RANGE :FROM 0 :BY 2) 0 5)))
(VALUES (COLLECT X) (COLLECT-SUM X))) => (0 2 4 6 8) and 20
Like sequences and unlike streams, the act of accessing the elements of a
series does not alter the series. For instance, both users of X above
receive the same elements.
A totally ordered multi-set of elements can be represented in a loop by the
successive values of a variable. This is extremely efficient, because it
avoids the need to store the elements as a group in any kind of data
structure. In most situations, series expressions achieve this same high
level of efficiency, because they are automatically transformed into loops
before being evaluated or compiled. For instance, the first expression
above is transformed into a loop like the following.
(LET ((SUM 0))
(DOLIST (I '(1 -2 3 -4) SUM)
(IF (PLUSP I) (SETQ SUM (+ SUM I))))) => 4
A wide variety of algorithms can be expressed clearly and succinctly using
series expressions. In particular, at least 90 percent of the loops
programmers typically write can be replaced by series expressions that are
much easier to understand and modify, and just as efficient. From this
perspective, the key feature of series is that they are supported by a rich
set of functions. These functions more or less correspond to the union of
the operations provided by the sequence functions, the LOOP clauses, and
the vector operations of APL.
Unfortunately, some series expressions cannot be transformed into loops.
This matters, because while transformable series expressions are much more
efficient than equivalent expressions involving sequences or streams,
non-transformable series expressions are much less efficient. Whenever a
problem comes up that blocks the transformation of a series expression, a
warning message is issued. Based on the information in the message, it is
usually easy to provide an efficient fix for the problem.
Fortunately, most series expressions can be transformed into loops. In
particular, pure expressions (ones that do not store series in variables)
can always be transformed. As a result, the best approach for programmers
to take is to simply write series expressions without worrying about
transformability. When problems come up, they can be ignored (since they
cannot lead to the computation of incorrect results) or dealt with on an
individual basis.
Series Functions
Throughout this chapter the notation S[j] is used to denote the jth element
of the series S. As in a list or vector, the first element of a series has
the subscript zero.
The # macro character syntax #Z(...) denotes a series that contains the
elements of LIST. This syntax is also used when printing series.
(CHOOSE-IF #'SYMBOLP #Z(A 2 B)) => #Z(A B)
Series are self-evaluating objects and the series data type is disjoint
from all other types.
SERIES [Type specifier]
The type specifier (SERIES ELEMENT-TYPE) denotes the set of series whose
elements are all members of the type ELEMENT-TYPE.
SERIES ARG &rest ARGS [Function]
The function SERIES returns an unbounded series that endlessly repeats the
values of the arguments. The second example below shows the preferred
method for constructing a bounded series.
(SERIES 'B 'C) => #Z(B C B C B C ...)
(SCAN (LIST 'A 'B 'C)) => #Z(A B C)
Scanners
Scanners create series outputs based on non-series inputs. They either
operate based on some formula (for example, scanning a range of integers)
or enumerate the elements in an aggregate data structure (for example,
scanning the elements in a list).
SCAN-RANGE &key (:START 0) (:BY 1) (:TYPE 'NUMBER) [Function]
:UPTO :BELOW :DOWNTO :ABOVE :LENGTH
The function SCAN-RANGE returns a series of numbers starting with the
:START argument (default integer 0) and counting up by the :BY argument
(default integer 1). The :TYPE argument (default NUMBER) is a type
specifier indicating the type of numbers in the series produced. The :TYPE
argument must be a (not necessarily proper) subtype of NUMBER. The :START
and :BY arguments must be of that type.
One of the last five arguments may be used to specify the kind of end test
to be used; these are called TERMINATION ARGUMENTS. If :UPTO is specified,
counting continues only so long as the numbers generated are less than or
equal to :UPTO. If :BELOW is specified, counting continues only so long
as the numbers generated are less than :BELOW. If :DOWNTO is specified,
counting continues only so long as the numbers generated are greater than
or equal to :DOWNTO. If :ABOVE is specified, counting continues only so
long as the numbers generated are greater than :ABOVE. If :LENGTH is
specified, it must be a non-negative integer and the output series has this
length.
If none of the termination arguments are specified, the output has
unbounded length. If more than one termination argument is specified, it
is an error.
(SCAN-RANGE :UPTO 4) => #Z(0 1 2 3 4)
(SCAN-RANGE :FROM 1 :BY -1 :ABOVE -4) => #Z(1 0 -1 -2 -3)
(SCAN-RANGE :FROM .5 :BY .1 :TYPE 'FLOAT) => #Z(.5 .6 .7 ...)
(SCAN-RANGE) => #Z(0 1 2 3 4 5 6 ...)
SCAN {TYPE} SEQUENCE [Function]
SCAN returns a series containing the elements of SEQUENCE in order. The
TYPE argument is a type specifier indicating the type of sequence to be
scanned; it must be a (not necessarily proper) subtype of SEQUENCE. If
TYPE is omitted, it defaults to LIST.
If the SEQUENCE is a list, it must be a proper list ending in NIL.
Scanning is significantly more efficient if it can be determined at compile
time whether TYPE is a subtype of LIST or VECTOR and for vectors what the
length of the vector is.
(SCAN '(A B C)) => #Z(A B C)
(SCAN 'STRING "BAR") => #Z(#\B #\A #\R)
SCAN-SUBLISTS LIST [Function]
SCAN-SUBLISTS returns a series containing the successive sublists of LIST.
The LIST must be a proper list ending in NIL.
(SCAN-SUBLISTS '(A B C)) => #Z((A B C) (B C) (C))
SCAN-MULTIPLE TYPE FIRST-SEQUENCE &rest MORE-SEQUENCES [Function]
Several sequences can be scanned at once by using several calls on SCAN.
Each call on SCAN will test to see when its sequence runs out of elements
and execution will stop as soon as any of the sequences are exhausted.
Although very robust, this approach to scanning can be a significant source
of inefficiency. In situations where it is known in advance which sequence
is the shortest, SCAN-MULTIPLE can be used to obtain the same results more
rapidly.
SCAN-MULTIPLE is similar to SCAN except that several sequences can be
scanned at once. If there are N sequence inputs, SCAN-MULTIPLE returns N
series containing the elements of these sequences. It must be the case
that none of the sequence inputs is shorter than the first sequence. All
of the output series are the same length as the first input sequence.
Extra elements in the other input sequences are ignored. Using
SCAN-MULTIPLE is more efficient than using multiple instances of SCAN,
because SCAN-MULTIPLE only has to check for the first input running out of
elements.
If TYPE is of the form (VALUES t1 ... tm), then there must be M sequence
inputs and the ith sequence must have type ti. Otherwise there can be any
number of sequence inputs, each of which must have type TYPE.
(MULTIPLE-VALUE-BIND (DATA WEIGHTS)
(SCAN-MULTIPLE 'LIST '(1 6 3 2 8) '(2 3 3 3 2))
(COLLECT (MAP-FN T #'* DATA WEIGHTS)))
=> (2 18 9 6 16)
SCAN-LISTS-OF-LISTS LISTS-OF-LISTS &optional LEAF-TEST [Function]
SCAN-LISTS-OF-LISTS-FRINGE LISTS-OF-LISTS &optional LEAF-TEST [Function]
The argument LISTS-OF-LISTS is viewed as an n-ary tree where each internal
node is a non-empty list and the elements of the list are the children of
the node. SCAN-LISTS-OF-LISTS and SCAN-LISTS-OF-LISTS-FRINGE each scan
LISTS-OF-LISTS in preorder and return a series of its nodes.
SCAN-LISTS-OF-LISTS returns every node in the tree.
SCAN-LISTS-OF-LISTS-FRINGE returns only the leaf nodes.
The scan proceeds as follows. The argument LISTS-OF-LISTS can be any Lisp
object. If LISTS-OF-LISTS is an atom or satisfies the predicate LEAF-TEST
(if present), it is a leaf node. (The predicate can count on only being
applied to conses.) Otherwise, LISTS-OF-LISTS is a (not necessarily proper)
list. The first element of LISTS-OF-LISTS is recursively scanned in full,
followed by the second and so on until a non-cons cdr is encountered.
Whether or not this final cdr is NIL, it is ignored.
(SCAN-LISTS-OF-LISTS '((2) (NIL))) => #Z(((2) (NIL)) (2) 2 (NIL) NIL)
(SCAN-LISTS-OF-LISTS-FRINGE '((2) (NIL))) => #Z(2 NIL)
(SCAN-LISTS-OF-LISTS-FRINGE '((2) (NIL))
#'(LAMBDA (E) (NUMBERP (CAR E))))
=> #Z((2) NIL)
SCAN-ALIST ALIST &optional (TEST #'EQL) [Function]
SCAN-PLIST PLIST [Function]
SCAN-HASH TABLE [Function]
When given an association list, a property list, or a hash table
(respectively), each of these functions produces two outputs: a series of
keys K and a series of the corresponding values V. Each key in the input
appears exactly once in the output, even if it appears more than once in
the input. (The TEST argument of SCAN-ALIST specifies the equality test
between keys; it defaults to EQL.) The two outputs have the same length.
Each V[j] is the value returned by the appropriate accessing function
(CDR-of-ASSOC, GETF, or GETHASH, respectively) when given K[j]. SCAN-ALIST
and SCAN-PLIST scan keys in the order they appear in the underlying
structure. SCAN-HASH scans keys in no particular order.
(SCAN-PLIST '(A 1 B 3)) => #Z(A B) AND #Z(1 3)
(SCAN-ALIST '((A . 1) NIL (A . 3) (B . 2)))
=> #Z(A B) AND #Z(1 2)
SCAN-SYMBOLS &optional (PACKAGE *PACKAGE*) [Function]
SCAN-SYMBOLS returns a series, in no particular order, and possibly
containing duplicates, of the symbols accessible in PACKAGE (which defaults
to the current package).
SCAN-FILE FILE-NAME &optional (READER #'READ) [Function]
SCAN-STREAM STREAM &optional (READER #'READ) [Function]
SCAN-FILE opens the file named by the string FILE-NAME and applies the
function READER to it repeatedly until the end of the file is reached.
READER must accept the standard input function arguments INPUT-STREAM,
EOF-ERROR-P, and EOF-VALUE as its arguments. (For instance, READER can be
READ, READ-PRESERVING-WHITE-SPACE, READ-LINE, or READ-CHAR.) If omitted,
READER defaults to READ. SCAN-FILE returns a series of the values returned
by READER, up to but not including the value returned when the end of the
file is reached. The file is correctly closed, even if an abort occurs.
SCAN-STREAM is like SCAN-FILE, except an open stream is given instead
of a file name. This works around a defect in SCAN-FILE where
additional options to OPEN cannot be specified.
SCAN-FN TYPE INIT STEP &optional TEST [Function]
The higher-order function SCAN-FN supports the general concept of scanning.
The TYPE argument is a type specifier, which specifies the type of values
returned by INIT and STEP. The VALUES type specifier can be used for this
argument to indicate multiple types; however, TYPE cannot indicate zero
values. If TYPE indicates M types t1, ..., tm, then SCAN-FN returns M
series T1, ..., TM where TI has the type (SERIES ti). The arguments INIT,
STEP, and TEST are functions.
The INIT must be of type (FUNCTION () (VALUES t1 ... tm)).
The STEP must be of type (FUNCTION (t1 ... tm) (VALUES t1 ... tm)).
The TEST (if present) must be of type (FUNCTION (t1 ... tm) T).
The elements of the TI are computed as follows:
(VALUES T1[0] ... TM[0]) = (FUNCALL INIT)
(VALUES T1[j] ... TM[j]) = (FUNCALL STEP T1[j-1] ... TM[j-1])
The outputs all have the same length. If there is no TEST, the outputs
have unbounded length. If there is a TEST, the outputs consist of the
elements up to, but not including, the first elements (with index J, say)
for which the following termination test is not NIL.
(FUNCALL TEST T1[j] ... TM[j])
It is guaranteed that STEP will not be applied to the elements that pass
this termination test.
If any of INIT, STEP, and TEST have side effects when invoked, they can
count on being called in the order indicated by the equations above, with
TEST called just before STEP on each cycle. However, due to the lazy
evaluation nature of series, these functions will not be called until their
outputs are actually used (if ever). In addition, no assumptions can be
made about the relative order of evaluation of these calls with regard to
execution in other parts of a given series expression. The first example
below scans down a list stepping two elements at a time. The second
example generates two unbounded series: the integers counting up from 1 and
the sequence of partial sums of the first I integers.
(SCAN-FN T #'(LAMBDA () '(A B C D)) #'CDDR #'NULL) => #Z((A B C D) (C D))
(SCAN-FN '(VALUES INTEGER INTEGER)
#'(LAMBDA () (VALUES 1 0))
#'(LAMBDA (I SUM) (VALUES (+ I 1) (+ SUM I))))
=> #Z(1 2 3 4 ...) AND #Z(0 1 3 6 ...)
SCAN-FN-INCLUSIVE TYPE INIT STEP TEST [Function]
The higher-order function SCAN-FN-INCLUSIVE is the same as SCAN-FN except
that the first set of elements for which TEST returns a non-null value is
included in the output. As with SCAN-FN, it is guaranteed that STEP will
not be applied to the elements for which TEST is non-null.
Mapping
By far the most common kind of series operation is mapping. In cognizance
of this fact, four different ways are provided for specifying mapping: one
fundamental form (MAP-FN) and three shorthand forms that are more
convenient in particular common situations.
MAP-FN TYPE FUNCTION &rest SERIES-INPUTS [Function]
The higher-order function MAP-FN supports the general concept of mapping.
The TYPE argument is a type specifier, which specifies the type of values
returned by FUNCTION. The VALUES construct can be used to indicate
multiple types; however, TYPE cannot indicate zero values. If TYPE
indicates M types t1, ..., tm, then MAP-FN returns M series T1, ..., TM
where TI has the type (SERIES ti). The argument FUNCTION is a function.
The remaining arguments (if any) are all series. Let these series be S1,
..., SN and suppose that SI has the type (SERIES si).
The FUNCTION must be of type (FUNCTION (s1 ... sn) (VALUES t1 ... tm))
The length of each output is the same as the length of the shortest input.
If there are no bounded series inputs, the outputs are unbounded. The
elements of the TI are the results of applying FUNCTION to the
corresponding elements of the series inputs.
(VALUES T1[j] ... TM[j]) = (FUNCALL FUNCTION S1[j] ... SN[j])
If FUNCTION has side effects, it can count on being called first on the
SI[0], then on the SI[1], and so on. However, due to the lazy evaluation
nature of series, FUNCTION will not be called on any group of input
elements until the result is actually used (if ever). In addition, no
assumptions can be made about the relative order of evaluation of the calls
on FUNCTION with regard to execution in other parts of a given series
expression.
(MAP-FN 'INTEGER #'+ #Z(1 2 3) #Z(4 5)) => #Z(5 7)
(MAP-FN T #'GENSYM) => #Z(#:G3 #:G4 #:G5 ...)
(MAP-FN '(VALUES INTEGER RATIONAL) #'FLOOR #Z(1/4 9/5 12/3))
=> #Z(0 1 4) AND #Z(1/4 4/5 0)
The # macro character syntax #M makes it easy to specify uses of MAP-FN
where TYPE is T and the FUNCTION is a named function. The notation
(#MFUNCTION ...) is an abbreviation for (MAP-FN T #'FUNCTION ...). The
form FUNCTION can be the printed representation of any Lisp object. The
notation #MFUNCTION can only appear in the function position of a list.
(COLLECT (#M1+ (SCAN '(1 2 3)))) => (2 3 4)
MAPPING ({({VAR | ({VAR}*)} VALUE)}*) {DECLARATION}* {FORM}* [Macro]
The macro mapping makes it easy to specify uses of map-fn where TYPE is T
and the function a literal LAMBDA. The syntax of mapping is analogous to
that of LET. The binding list specifies zero or more variables that are
bound in parallel to successive values of series. The VALUE part of each
pair is an expression that must produce a series. The DECLARATIONS and
FORMS are treated as the body of a LAMBDA expression that is mapped over
the series values. A series of the first values returned by this LAMBDA
expression is returned as the result of MAPPING.
(MAPPING ((X R) (Y S)) ...) == (MAP-FN T #'(LAMBDA (X Y) ...) R S)
(MAPPING ((X (SCAN '(2 -2 3))))
(EXPT (ABS X) 3)) => #Z(8 8 27)
The form MAPPING supports a special syntax that facilitates the use of
series functions returning multiple values. Instead of being a single
variable, the variable part of a var-value-pair can be a list of variables.
This list is treated the same way as the first argument to
MULTIPLE-VALUE-BIND and can be used to access the elements of multiple
series returned by a series function.
(MAPPING (((I V) (SCAN-PLIST '(A 1 B 2))))
(LIST I V))
=> #Z((A 1) (B 2))
ITERATE ({({VAR | ({VAR}*)} VALUE)}*) {DECLARATION}* {FORM}* [Macro]
The form ITERATE is the same as MAPPING, except that after mapping the
FORMS over the VALUES, the results are discarded and NIL is returned.
(LET ((ITEM (SCAN '((1) (-2) (3)))))
(ITERATE ((X (#MCAR ITEM)))
(IF (PLUSP X) (PRIN1 X))))
=> NIL (after printing ``13'')
To a first approximation, ITERATE and MAPPING differ in the same way as
MAPC and MAPCAR. In particular, like MAPC, ITERATE is intended to be used
in situations where the FORMS are being evaluated for side effect rather
than their results. However, due to the lazy evaluation semantics of
series, the difference between ITERATE and MAPPING is more than just a
question of efficiency.
If MAPCAR is used in a situation where the output is not used, time is
wasted unnecessarily creating the output list. However, if MAPPING is used
in a situation where the output is not used, no computation is performed,
because series elements are not computed until they are used. Thus ITERATE
can be thought of as a declaration that the indicated computation is to be
performed even though the output is not used for anything.
Truncation and Other Simple Transducers
Transducers compute series from series and form the heart of most series
expressions. Mapping is by far the most common transducer. This section
presents a number of additional simple transducers.
COTRUNCATE &rest SERIES-INPUTS [Function]
UNTIL BOOLS &rest SERIES-INPUTS [Function]
UNTIL-IF PRED &rest SERIES-INPUTS [Function]
Each of these functions accepts one or more series inputs S1, ..., SN as
its &REST argument and returns N series outputs T1, ..., TN that contain
the same elements in the same order---that is, TI[j]=SI[j]. Let K be the
length of the shortest input SI. COTRUNCATE truncates the series so that
each output has length K. Let K' be the position of the first element in
the boolean series BOOLS that is not NIL or, if every element is NIL, the
length of BOOLS. UNTIL truncates the series so that each output has length
(MIN K K'). Let K'' be the position of the first element in S1 such that
(PRED S1[K'']) is not NIL or, if there is no such element, the length of
S1. UNTIL-IF truncates the series so that each output has length (MIN K K'').
(COTRUNCATE #Z(1 2 -3 4) #Z(A B C)) => #Z(1 2 -3) and #Z(A B C)
(UNTIL #Z(NIL NIL T NIL) #Z(1 2 -3 4) #Z(A B C)) => #Z(1 2) and #Z(A B)
(UNTIL-IF #'MINUSP #Z(1 2 -3 4) #Z(A B C)) => #Z(1 2) and #Z(A B)
PREVIOUS ITEMS &optional (DEFAULT NIL) (AMOUNT 1) [Function]
The series returned by PREVIOUS is the same as the input series ITEMS
except that it is shifted to the right by the positive integer AMOUNT. The
shifting is done by inserting AMOUNT copies of DEFAULT before ITEMS and
discarding AMOUNT elements from the end of ITEMS.
(PREVIOUS #Z(10 11 12) 0) => #Z(0 10 11)
LATCH ITEMS &key :AFTER :BEFORE :PRE :POST [Function]
The series returned by LATCH is the same as the input series ITEMS except
that some of the elements are replaced by other values. LATCH acts like a
LATCH electronic circuit component. Each input element causes the creation
of a corresponding output element. After a specified number of non-null
input elements have been encountered, the latch is triggered and the output
mode is permanently changed.
The :AFTER and :BEFORE arguments specify the latch point. The latch point
is just after the :AFTER-th non-null element in ITEMS or just before the
:BEFORE-th non-null element. If neither :AFTER nor :BEFORE is specified,
an :AFTER of 1 is assumed. If both are specified, it is an error.
If a :PRE is specified, every element prior to the latch point is replaced
by this value. If a :POST is specified, every element after the latch
point is replaced by this value. If neither is specified, a :POST of NIL
is assumed.
(LATCH #Z(NIL C NIL D E)) => #Z(NIL C NIL NIL NIL)
(LATCH #Z(NIL C NIL D E) :BEFORE 2 :POST T) => #Z(NIL C NIL T T)
COLLECTING-FN TYPE INIT FUNCTION &rest SERIES-INPUTS [Function]
The higher-order function COLLECTING-FN supports the general concept of a
simple transducer with internal state. The TYPE argument is a type
specifier, which specifies the type of values returned by FUNCTION. The
VALUES construct can be used to indicate multiple types; however, TYPE
cannot indicate zero values. If TYPE indicates M types t1, ..., tm, then
COLLECTING-FN returns M series T1, ..., TM where TI has the type (SERIES
ti). The arguments INIT and FUNCTION are functions. The remaining
arguments (if any) are all series. Let these series be S1, ..., SN and
suppose that SI has the type (SERIES si).
The INIT must be of type (FUNCTION () (VALUES t1 ... tm)).
The FUNCTION must be of type (FUNCTION (t1 ... tm s1 ... sn) (VALUES t1 ... tm))
The length of each output is the same as the length of the shortest input.
If there are no bounded series inputs, the outputs are unbounded. The
elements of the TI are computed as follows:
(VALUES T1[0] ... TM[0]) =
(MULTIPLE-VALUE-CALL FUNCTION (FUNCALL INIT) S1[0] ... SN[0])
(VALUES T1[j] ... TM[j]) =
(FUNCALL FUNCTION T1[j-1] ... TM[j-1] S1[j] ... SN[j])
If INIT and/or FUNCTION have side effects, they can count on being called
in the order indicated by the equations above. However, due to the lazy
evaluation nature of series, these functions will not be called until their
outputs are actually used (if ever). In addition, no assumptions can be
made about the relative order of evaluation of these calls with regard to
execution in other parts of a given series expression. The first example
below computes a series of partial sums of the numbers in an input series.
The second example computes two output series: the partial sums of its
first input and the partial products of its second input.
(COLLECTING-FN 'INTEGER #'(LAMBDA () 0) #'+ #Z(1 2 3)) => #Z(1 3 6)
(COLLECTING-FN '(VALUES INTEGER INTEGER)
#'(LAMBDA () (VALUES 0 1))
#'(LAMBDA (SUM PROD X Y)
(VALUES (+ SUM X) (* PROD Y)))
#Z(4 6 8)
#Z(1 2 3))
=> #Z(4 10 18) AND #Z(1 2 6)
Conditional and Other Complex Transducers
This section presents a number of complex transducers, including ones that
support conditional computation.
CHOOSE BOOLS &optional (ITEMS BOOLS) [Function]
CHOOSE-IF PRED ITEMS [Function]
Each of these functions takes in a series of elements (ITEMS) and returns a
series containing the same elements in the same order, but with some
elements removed. CHOOSE removes ITEMS[j] if BOOLS[j] is NIL or J is
beyond the end of BOOLS. If ITEMS is omitted, CHOOSE returns the non-null
elements of BOOLS. CHOOSE-IF removes ITEMS[j] if (PRED ITEMS[j]) is NIL.
(CHOOSE #Z(T NIL T NIL) #Z(A B C D)) => #Z(A C)
(COLLECT-SUM (CHOOSE-IF #'PLUSP #Z(-1 2 -3 4))) => 6
EXPAND BOOLS ITEMS &optional (DEFAULT NIL) [Function]
EXPAND is a quasi-inverse of CHOOSE. The output contains the elements of
the input series ITEMS spread out into the positions specified by the
non-null elements in BOOLS---that is, ITEMS[j] is in the position occupied
by the jth non-null element in BOOLS. The other positions in the output
are occupied by DEFAULT. The output stops as soon as BOOLS runs out of
elements or a non-null element in BOOLS is encountered for which there is
no corresponding element in ITEMS.
(EXPAND #Z(NIL T NIL T T) #Z(A B C)) => #Z(NIL A NIL B C)
(EXPAND #Z(NIL T NIL T T) #Z(A)) => #Z(NIL A NIL)
SPREAD GAPS ITEMS &optional (DEFAULT NIL) [Function]
SPREAD is quite similar to EXPAND, except instead of giving booleans
on where to put the items, GAPS are specified which indicate how far
apart the items should be. A gap of 0 means the items will be
adjacent.
(SPREAD #Z(1 1 1) #Z(A B C)) -> #Z(NIL A NIL B NIL C)
(SPREAD #z(0 2 3) #z(A B C)) -> #Z(A NIL NIL B NIL NIL NIL C)
SPLIT ITEMS &rest TEST-SERIES-INPUTS [Function]
SPLIT-IF ITEMS &rest TEST-PREDICATES [Function]
These functions are like CHOOSE and CHOOSE-IF except that instead of
producing one restricted output, they partition the input series ITEMS
between several outputs. If there are N test inputs following ITEMS, then
there are N+1 outputs. Each input element is placed in exactly one output
series, depending on the outcome of a sequence of tests. If the element
ITEMS[j] fails the first K-1 tests and passes the kth test, it is put in
the kth output. If ITEMS[j] fails every test, it is placed in the last
output. In addition, all output stops as soon as any series input runs out
of elements. The test inputs to SPLIT are series of values; ITEMS[j]
passes the kth test if the jth element of the kth test-series is not NIL.
The test inputs to SPLIT-IF are predicates; ITEMS[j] passes the kth test if
the kth test predicate returns non-null when applied to ITEMS[j].
(SPLIT #Z(-1 2 3 -4) #Z(T NIL NIL T)) => #Z(-1 -4) and #Z(2 3)
(MULTIPLE-VALUE-BIND (+X -X) (SPLIT-IF #Z(-1 2 3 -4) #'PLUSP)
(VALUES (COLLECT-SUM +X) (COLLECT-SUM -X)))
=> 5 and -5
CATENATE &rest SERIES-INPUTS [Function]
CATENATE combines two or more series into one long series by appending them
end to end. The length of the output is the sum of the lengths of the
inputs.
(CATENATE #Z(B C) #Z() #Z(D)) => #Z(B C D)
SUBSERIES ITEMS START &optional BELOW [Function]
SUBSERIES returns a series containing the elements of the input series
ITEMS indexed by the non-negative integers from START up to, but not
including, BELOW. If BELOW is omitted or greater than the length of ITEMS,
the output goes all of the way to the end of ITEMS.
(SUBSERIES #Z(A B C D) 1) => #Z(B C D)
(SUBSERIES #Z(A B C D) 1 3) => #Z(B C)
POSITIONS BOOLS [Function]
POSITIONS returns a series of the indices of the non-null elements in the
series input BOOLS.
(POSITIONS #Z(T NIL T 44)) => #Z(0 2 3)
MASK MONOTONIC-INDICES [Function]
MASK is a quasi-inverse of POSITIONS. The series input MONOTONIC-INDICES
must be a strictly increasing series of non-negative integers. The output,
which is always unbounded, contains T in the positions specified by
MONOTONIC-INDICES and NIL everywhere else.
(MASK #Z()) => #Z(NIL NIL ...)
(MASK #Z(0 2 3)) => #Z(T NIL T T NIL NIL ...)
(MASK (POSITIONS #Z(NIL A NIL B NIL))) => #Z(NIL T NIL T NIL ...)
MINGLE ITEMS1 ITEMS2 COMPARATOR [Function]
The series returned by MINGLE contains all and only the elements of the two
input series. The length of the output is the sum of the lengths of the
inputs and is unbounded if either input is unbounded. The order of the
elements remains unchanged; however, the elements from the two inputs are
stably intermixed under the control of the COMPARATOR.
The COMPARATOR must accept two arguments and return non-null if and only if
its first argument is strictly less than its second argument (in some
appropriate sense). At each step, the COMPARATOR is used to compare the
current elements in the two series. If the current element from ITEMS2 is
strictly less than the current element from ITEMS1, the current element is
removed from ITEMS2 and transferred to the output. Otherwise, the next
output element comes from ITEMS1.
(MINGLE #Z(1 3 7 9) #Z(4 5 8) #'<) => #Z(1 3 4 5 7 8 9)
(MINGLE #Z(1 7 3 9) #Z(4 5 8) #'<) => #Z(1 4 5 7 3 8 9)
CHUNK M N ITEMS [Function]
This function has the effect of breaking up the input series ITEMS into
(possibly overlapping) chunks of length M. The starting positions of
successive chunks differ by N. The inputs M and N must both be positive
integers.
CHUNK produces M output series. The ith chunk consists of the ith elements
of the M outputs. Suppose that the length of ITEMS is L. The length of
each output is the floor of 1+(L-M)/N. The ith element of the kth output
is the (i*n+k)th element of ITEMS (i and k counting from zero).
The first example below shows CHUNK being used to compute a moving average.
The second example shows CHUNK being used to convert a property list into
an association list.
(MAPPING (((XI XI+1 XI+2) (CHUNK 3 1 #Z(1 5 3 4 5 6))))
(/ (+ XI XI+1 XI+2) 3)) => #Z(3 4 4 5)
(COLLECT
(MAPPING (((PROP VAL) (CHUNK 2 2 (SCAN '(A 2 B 5 C 8)))))
(CONS PROP VAL))) => ((A . 2) (B . 5) (C . 8))
Collectors
Collectors produce non-series outputs based on series inputs. They either
create a summary value based on some formula (the sum, for example) or
collect the elements of a series in an aggregate data structure (such as a
list).
COLLECT-FIRST ITEMS &optional (DEFAULT NIL) [Function]
COLLECT-LAST ITEMS &optional (DEFAULT NIL) [Function]
COLLECT-NTH N ITEMS &optional (DEFAULT NIL) [Function]
Given a series ITEMS, these functions return the first element, the last
element, and the Nth element, respectively. If ITEMS has no elements (or
no Nth element), DEFAULT is returned. If DEFAULT is not specified, then
NIL is used for DEFAULT.
(COLLECT-FIRST #Z() 'Z) => Z
(COLLECT-LAST #Z(A B C)) => C
(COLLECT-NTH 1 #Z(A B C)) => B
COLLECT-LENGTH ITEMS [Function]
COLLECT-LENGTH returns the number of elements in a series.
(COLLECT-LENGTH #Z(A B C)) => 3
COLLECT-SUM NUMBERS &optional (TYPE 'NUMBER) [Function]
COLLECT-SUM returns the sum of the elements in a series of numbers. The
TYPE is a type specifier that indicates the type of sum to be created. If
TYPE is not specified, then NUMBER is used for the TYPE. If there are no
elements in the input, a zero (of the appropriate type) is returned.
(COLLECT-SUM #Z(1.1 1.2 1.3)) => 3.6
(COLLECT-SUM #Z() 'COMPLEX) => #C(0 0)
COLLECT-PRODUCT NUMBERS &optional (TYPE 'NUMBER) [Function]
COLLECT-PRODUCT returns the product of the elements in a series of
numbers. The TYPE is a type specifier that indicates the type of sum
to be created. If TYPE is not specified, then NUMBER is used for the
TYPE. If there are no elements in the input, one (of the
appropriate type) is returned.
(COLLECT-PRODUCT #Z(1.1 1.2 1.3)) => 1.716
(COLLECT-PRODUCT #Z() 'FLOAT) => 1.0
COLLECT-MAX NUMBERS &optional (ITEMS NUMBERS) (DEFAULT NIL) [Function]
COLLECT-MIN NUMBERS &optional (ITEMS NUMBERS) (DEFAULT NIL) [Function]
Given a series of non-complex numbers, these functions returns the
element of ITEMS that corresponds to the maximum element and the
minimum element of NUMBERS, respectively. If ITEMS is omitted, the
the maximum or minimum of NUMBERS itself is returned. If there are no
elements in the input, DEFAULT is returned.
(COLLECT-MAX #Z(2 1 4 3)) => 4
(COLLECT-MIN #Z(1.2 1.1 1.4 1.3)) => 1.1
(COLLECT-MIN #Z()) => NIL
COLLECT-AND BOOLS [Function]
COLLECT-AND returns the AND of the elements in a series. As with the macro
AND, NIL is returned if any element of BOOLS is NIL. Otherwise, the last
element of BOOLS is returned. The value T is returned if there are no
elements in BOOLS.
(COLLECT-AND #Z(A B C)) => C
(COLLECT-AND #Z(A NIL C)) => NIL
COLLECT-OR BOOLS [Function]
COLLECT-OR returns the OR of the elements in a series. As with the macro
OR, NIL is returned if every element of BOOLS is NIL. Otherwise, the first
non-null element of BOOLS is returned. The value NIL is returned if there
are no elements in BOOLS.
(COLLECT-OR #Z(NIL B C)) => B
(COLLECT-OR #Z()) => NIL
COLLECT ITEMS [Function]
COLLECT TYPE ITEMS [Function]
COLLECT returns a sequence containing the elements of the series ITEMS.
The TYPE is a type specifier indicating the type of sequence to be created.
It must be either a proper subtype of SEQUENCE or the symbol BAG. If TYPE
is omitted, it defaults to LIST. (This function exhibits an argument
pattern that is unusual for Common Lisp: an ``optional'' argument
preceding a required argument. This pattern cannot be expressed in the
usual manner with &OPTIONAL. It is indicated above by two definition
lines, showing the two possible argument patterns.)
If the TYPE is BAG, a list is created with the elements in whatever order
can be most efficiently obtained. Otherwise, the order of the elements in
the sequence is the same as the order in ITEMS. If TYPE specifies a length
(that is, of a vector) this length must be greater than or equal to the
length of ITEMS.
The nth element of ITEMS is placed in the nth slot of the sequence
produced. Any unneeded slots are left in their initial state. Collecting
is significantly more efficient if it can be determined at compile time
whether TYPE is a subtype of LIST or VECTOR and for vectors what the length
of the vector is.
(COLLECT #Z(A B C)) => (A B C)
(COLLECT 'BAG #Z(A B C)) => (C A B) or (B A C) or ...
(COLLECT '(VECTOR INTEGER 3) #Z(1 2 3)) => #(1 2 3)
COLLECT-APPEND SEQUENCES [Function]
COLLECT-APPEND TYPE SEQUENCES [Function]
Given a series of sequences, COLLECT-APPEND returns a new sequence by
concatenating these sequences together in order. The TYPE is a type
specifier indicating the type of sequence created and must be a proper
subtype of SEQUENCE. If TYPE is omitted, it defaults to LIST. (This
function exhibits an argument pattern that is unusual for Common Lisp: an
``optional'' argument preceding a required argument. This pattern cannot
be expressed in the usual manner with &OPTIONAL. It is indicated above by
two definition lines, showing the two possible argument patterns.)
It must be possible for every element of every sequence in the input series
to be an element of a sequence of type TYPE. The result does not share any
structure with the sequences in the input.
(COLLECT-APPEND #Z((A B) NIL (C D))) => (A B C D)
(COLLECT-APPEND 'STRING #Z("A " "BIG " "CAT")) => "A BIG CAT"
COLLECT-IGNORE LISTS [Function]
Like COLLECT, but any results that would have been returned are
discarded. This also means the results are not consed.
COLLECT-NCONC LISTS [Function]
COLLECT-NCONC NCONCs the elements of the series LISTS together in order
and returns the result. This is the same as COLLECT-APPEND except that the
input must be a series of lists, the output is always a list, the
concatenation is done rapidly by destructively modifying the input
elements, and therefore the output shares all of its structure with the
input elements.
COLLECT-ALIST KEYS VALUES [Function]
COLLECT-PLIST KEYS VALUES [Function]
COLLECT-HASH KEYS VALUES &key :TEST :SIZE :REHASH-SIZE [Function]
:REHASH-THRESHOLD
Given a series of keys and a series of corresponding values, these
functions return an association list, a property list, and a hash table,
respectively. Following the order of the input, each KEYS[j]/VALUES[j]
pair is entered into the output so that it overrides all earlier
associations. If one of the input series is longer than the other, the
extra elements are ignored. The keyword arguments of COLLECT-HASH specify
attributes of the hash table produced and have the same meanings as the
arguments to MAKE-HASH-TABLE.
(COLLECT-ALIST #Z(A B C) #Z(1 2)) => ((B . 2) (A . 1))
(COLLECT-HASH #Z() #Z(1 2) :TEST #'EQ) => <an empty hash table>
COLLECT-FILE FILE-NAME ITEMS &optional (PRINTER #'PRINT) [Function]
COLLECT-STREAM STREAM ITEMS &optional (PRINTER #'PRINT) [Function]
This creates a file named FILE-NAME and writes the elements of the series
ITEMS into it using the function PRINTER. PRINTER must accept two inputs:
an object and an output stream. (For instance, PRINTER can be PRINT,
PRIN1, PRINC, PPRINT, WRITE-CHAR, WRITE-STRING, or WRITE-LINE.) If
omitted, PRINTER defaults to PRINT. The value T is returned. The file is
correctly closed, even if an abort occurs.
COLLECT-STREAM is idential to COLLECT-FILE, except an already open
stream is used instead of creating a new file.
COLLECT-FN TYPE INIT FUNCTION &rest SERIES-INPUTS [Function]
The higher-order function COLLECT-FN supports the general concept of
collecting. It is identical to COLLECTING-FN except that it only returns
the last element of each series computed. If there are no elements in
these series, the values returned by INIT are passed on directly as the
output of COLLECT-FN.
(COLLECT-FN 'INTEGER #'(LAMBDA () 0) #'+ #Z(1 2 3)) => 6
(COLLECT-FN 'INTEGER #'(LAMBDA () 0) #'+ #Z()) => 0
Alteration of Series
Series that come from scanning data structures such as lists and vectors
are closely linked to these structures. The function ALTER can be used to
modify the underlying data structure with reference to the series derived
from it. (Conversely, it is possible to modify a series by destructively
modifying the data structure it is derived from. However, given the lazy
evaluation nature of series, the effects of such modifications can be very
hard to predict. As a result, this kind of modification is inadvisable.)
ALTER DESTINATIONS ITEMS [Function]
ALTER changes the series DESTINATIONS so that it contains the elements in
the series ITEMS. More importantly, in the manner of SETF, the data
structure that underlies DESTINATIONS is changed so that if the series
DESTINATIONS were to be regenerated, the new values would be obtained. The
alteration process stops as soon as either input runs out of elements. The
value NIL is always returned. In the example below each negative element in
a list is replaced with its square.
(LET* ((DATA (LIST 1 -2 3 4 -5 6))
(X (CHOOSE-IF #'MINUSP (SCAN DATA))))
(ALTER X (#M* X X))
DATA)
=> (1 4 3 4 25 6)
ALTER can only be applied to series that are ALTERABLE. SCAN,
SCAN-ALIST, SCAN-MULTIPLE, SCAN-PLIST, and SCAN-LISTS-OF-LISTS-FRINGE
produce alterable series. However, the alterability of the output of
SCAN-LISTS-OF-LISTS-FRINGE is incomplete. If SCAN-LISTS-OF-LISTS-FRINGE is
applied to an object that is a leaf, altering the output series does not
change the object.
In general, the output of a transducer is alterable as long as the elements
of the output come directly from the elements of an input that is
alterable. In particular, the outputs of CHOOSE, CHOOSE-IF, SPLIT,
SPLIT-IF, COTRUNCATE, UNTIL, UNTIL-IF, and SUBSERIES are alterable as long
as the corresponding inputs are alterable.
TO-ALTER ITEMS ALTER-FN &rest ARGS [Function]
Given a series ITEMS, TO-ALTER returns an alterable series A containing
the same elements. The argument ALTER-FN is a function. The remaining
arguments are all series. Let these series be S1, ..., SN. If there are N
arguments after ALTER-FN, ALTER-FN must accept N+1 inputs. If (ALTER A B)
is later encountered, (MAP-FN T ALTER-FN B S1 ... SN) is implicitly
evaluated. For each element in B, ALTER-FN should make appropriate changes
in the data structure underlying A.
As an example, consider the following definition of a series function that
scans the elements of a list. Alteration is performed by changing cons
cells in the list being scanned.
(DEFUN SCAN-LIST (LIST)
(DECLARE (OPTIMIZABLE-SERIES-FUNCTION))
(LET ((SUBLISTS (SCAN-SUBLISTS LIST)))
(TO-ALTER (#MCAR SUBLISTS)
#'(LAMBDA (NEW PARENT) (SETF (CAR PARENT) NEW))
SUBLISTS)))
Optimization
Series expressions are transformed into loops by pipelining them---the
computation is converted from a form where entire series are computed one
after the other to a form where the series are incrementally computed in
parallel. In the resulting loop, each individual element is computed just
once, used, and then discarded before the next element is computed. For
this pipelining to be possible, a number of restrictions have to be
satisfied. Before looking at these restrictions, it is useful to consider
a related issue.
The composition of two series functions cannot be pipelined unless the
destination function consumes series elements in the same order that the
source function produces them. Taken together, the series functions
guarantee that this will always be true, because they all follow the same
fixed processing order. In particular, they are all `preorder'
functions---they process the elements of their series inputs and outputs in
ascending order starting with the first element. Further, while it is easy
for users to define new series functions, it is impossible to define one
that is not preorder.
It turns out that most series operations can easily be implemented in a
preorder fashion, the most notable exceptions being reversal and sorting.
As a result, little is lost by outlawing non-preorder series functions. If
some non-preorder operation has to be applied to a series, the series can
be collected into a list or vector and the operation applied to this new
data structure. (This is inefficient, but no less efficient than what
would be required if non-preorder series functions were supported.)
Basic Restrictions
The transformation of series expressions into loops is required to occur at
some time before compiled code is actually run. Optimization may or may
not be applied to interpreted code. If any of the restrictions described
below are violated, optimization is not possible. In this situation, a
warning message is issued at the time optimization is attempted and the
code is left unoptimized. This is not a fatal error and does not prevent
the correct results from being computed. However, given the large
improvements in efficiency to be gained, it is well worth fixing any
violations that occur. This is usually easy to do.
*SUPPRESS-SERIES-WARNINGS* [Variable]
If this variable is set (or bound) to anything other than its default value
of NIL, warnings about conditions that block the optimization of series
expressions are suppressed.
Before discussing the restrictions on series expressions, it is useful to
define precisely what is meant by the term SERIES EXPRESSION. This term is
semantic rather than syntactic in nature. Given a program, imagine it
converted from Lisp code into a data flow graph. In a data flow graph,
functions are represented as boxes, and both control flow and data flow are
represented as arrows between the boxes. Constructs such as LET and SETQ
are converted into patterns of data flow arcs. Control constructs such as
IF and LOOP are converted into patterns of control flow arcs. Suppose
further, that all loops have been converted into tail recursions so that
the graph is acyclic.
A series expression is a subgraph of the data flow graph for a program that
contains a group of interacting series functions. More specifically, given
a call F on a series function, the series expression E containing it is
defined as follows. E contains F. Every function using a series created
by a function in E is in E. Every function computing a series used by a
function in E is in E. Finally, suppose that two functions G and H are in
E and that there is a data flow path consisting of series and/or non-series
data flow arcs from G to H. Every function touched by this path (be it a
series function or not) is in E.
FOR OPTIMIZATION TO BE POSSIBLE, SERIES EXPRESSIONS HAVE TO BE STATICALLY
ANALYZABLE. As with most other optimization processes, a series expression
cannot be transformed into a loop at compile time, unless it can be
determined at compile time exactly what computation is being performed.
This places a number of relatively minor limits on what can be written.
For example, for optimization to be possible the type arguments to
higher-order functions such as MAP-FN and COLLECTING-FN have to be quoted
constants. Similarly, the numeric arguments to CHUNK have to be constants.
In addition, if FUNCALL is used to call a series function, the function
called has to be of the form (FUNCTION ...).
FOR OPTIMIZATION TO BE POSSIBLE, EVERY SERIES CREATED WITHIN A SERIES
EXPRESSION MUST BE USED SOLELY INSIDE THE EXPRESSION. (If a series is
transmitted outside of the expression that creates it, it has to be
physically represented as a whole. This is incompatible with the
transformations required to pipeline the creating expression.) To avoid
this problem, a series must not be returned as a result of a series
expressions as a whole, assigned to a free variable, assigned to a special
variable, or stored in a data structure. A corollary of the last point is
that when defining new optimizable series functions, series cannot be
passed into &REST arguments. Further, optimization is blocked if a series
is passed as an argument to an ordinary Lisp function. Series can only be
passed to the predefined series functions and to new series functions
defined using the declaration OPTIMIZABLE-SERIES-FUNCTION.
FOR OPTIMIZATION TO BE POSSIBLE, SERIES EXPRESSIONS MUST CORRESPOND TO
STRAIGHT LINE COMPUTATIONS. That is to say, the data flow graph
corresponding to a series expression cannot contain any conditional
branches. (Complex control flow is incompatible with pipelining.)
Optimization is possible in the presence of standard straight-line forms
such as PROGN, FUNCALL, SETQ, LAMBDA, LET, LET*, and MULTIPLE-VALUE-BIND as
long as none of the variables bound are special. There is also no problem
with macros as long as they expand into series functions and straight-line
forms. However, optimization is blocked by forms that specify complex
control flow (i.e., conditionals IF, COND, etc., looping constructs LOOP,
DO, etc., or branching constructs TAGBODY, GO, CATCH, etc.).
In the first example below, optimization is blocked, because the IF form is
inside of the series expression. However, in the second example,
optimization is possible, because although the IF feeds data to the series
expression, it is not inside the corresponding subgraph. Both of the
expressions below produce the same value, however, the second one is much
more efficient.
(COLLECT (IF FLAG (SCAN X) (SCAN Y))) ;warning message issued
(COLLECT (SCAN (IF FLAG X Y)))
Constraint Cycles
Even if a series expression satisfies all of the restrictions above, it
still may not be possible to transform the expression into a loop. The
sole remaining problem is that if a series is used in two places, the two
uses may place incompatible constraints on the times at which series
elements should be produced.
The series expression below shows a situation where this problem arises.
The expression creates a series X of the elements in a list. It then
creates a normalized series by dividing each element of X by the sum of the
elements in X. Finally, the expression returns the maximum of the
normalized elements.
(LET ((X (SCAN '(1 2 5 2)))) ; warning message issued
(COLLECT-MAX (#M/ X (SERIES (COLLECT-SUM X))))) => 1/2
The two uses of X in the expression place contradictory constraints on the
way pipelined evaluation must proceed. COLLECT-SUM requires that all of
the elements of X be produced before the sum can be returned and SERIES
requires that its input be available before it can start to produce its
output. However, #M/ requires that the first element of X be available at
the same time as the first element of the output of SERIES. For pipelining
to work, this implies that the first element of the output of SERIES (and
therefore the output of COLLECT-SUM) must be available before the second
element of X is produced. Unfortunately, this is impossible.
The essence of the inconsistency above is the cycle of constraints used in
the argument. This in turn stems from a cycle in the data flow graph
underlying the expression (see Figure 1). In Figure 1, function calls are
represented by boxes and data flow is represented by arrows. Simple arrows
indicate the flow of series values and cross hatched arrows indicate the
flow of non-series values.
|------| /------------------------------->|-------| |------|
-| scan |--- |------| |------| | #M/ |----->| max |-
|------| \--->| sum |+++++>|series|----->|-------| |------|
|------| |------|
Figure 1: A Constraint Cycle in a Series Expression
Given a data flow graph corresponding to a series expression, a CONSTRAINT
CYCLE is a closed loop of data flow arcs that can be traversed in such a
way that each arc is traversed exactly once and no non-series arc is
traversed backwards. (Series data flow arcs can be traversed in either
direction.) A constraint cycle is said to PASS THROUGH an input or output
port when exactly one of the arcs in the cycle touches the port. In Figure
1, the data flow arcs touching SCAN, SUM, SERIES, and #M/ form a constraint
cycle. Note that if the output of SCAN were not a series, this loop would
not be a constraint cycle, because there would be no valid way to traverse
it. Also note that while the constraint cycle passes through all the other
ports it touches, it does not pass through the output of SCAN.
Whenever a constraint cycle passes through a non-series output, an argument
analogous to the one above can be constructed and therefore pipelining is
impossible. When this situation arises, a warning message is issued
identifying the problematical port and the cycle passing through it. For
instance, the warning triggered by the example above states that the
constraint cycle associated with SCAN, COLLECT-SUM, SERIES, and #M/ passes
through the non-series output of COLLECT-SUM.
Given this kind of detailed information, it is easy to alleviate the
problem. To start with, every cycle must contain at least one function
that has two series data flows leaving it. At worst, the cycle can be
broken by duplicating this function (and any functions computing series
used by it). For instance, the example above can be rewritten as shown
below.
(LET ((X (SCAN '(1 2 5 2)))
(SUM (COLLECT-SUM (SCAN '(1 2 5 2)))))
(COLLECT-MAX (#M/ X (SERIES SUM))))
=> 1/2
It would be easy enough to automatically apply code copying to break
problematical constraint cycles. However, this is not done for two
reasons. First, there is considerable virtue in maintaining the property
that each function in a series expression turns into one piece of
computation in the loop produced. Users can be confident that series
expressions that look simple and efficient actually are simple and
efficient. Second, with a little creativity, constraint problems can often
be resolved in ways that are much more efficient than copying code. In the
example above, the conflict can be eliminated efficiently by interchanging
the operation of computing the maximum with the operation of normalizing an
element.
(LET ((X (SCAN '(1 2 5 2))))
(/ (COLLECT-MAX X) (COLLECT-SUM X))) => 1/2
The restriction that optimizable series expressions cannot contain
constraint cycles that pass through non-series outputs places limitations
on the qualitative character of optimizable series expressions. In
particular, they all must have the general form of creating some number of
series using scanners, computing various intermediate series using
transducers, and then computing one or more summary results using
collectors. The output of a collector cannot be used in the intermediate
computation unless it is the output of a separate subexpression.
It is worthy of note that the last expression above fixes the constraint
conflict by moving the non-series output out of the cycle, rather than by
breaking the cycle. This illustrates the fact that constraint cycles that
do not pass through non-series outputs do not necessarily cause problems.
They cause problems only if they pass through OFF-LINE ports.
A series input port or series output port of a series function is ON-LINE
if and only if it is processed in lock step with all the other on-line
ports as follows: The initial element of each on-line input is read, then
the initial element of each on-line output is written, then the second
element of each on-line input is read, then the second element of each
on-line output is written, and so on. Ports that are not on-line are
off-line. If all of the series ports of a function are on-line, the
function is said to be on-line; otherwise, it is off-line. (The above
extends the standard definition of the term `on-line' so that it applies to
individual ports as well as whole functions.)
If all of the ports a cycle passes through are on-line, the lock step
processing of these ports guarantees that there cannot be any conflicts
between the constraints associated with the cycle. However, passing
through an off-line port leads to the same kinds of problems as passing
through a non-series output.
Most of the series functions are on-line. In particular, scanners and
collectors are all on-line as are many transducers. However, the
transducers in Section on complex transducers are off-line. In particular,
the series inputs of CATENATE, CHOOSE-IF, CHUNK, EXPAND, MASK, MINGLE,
POSITIONS, and SUBSERIES along with the series outputs of CHOOSE, SPLIT,
and SPLIT-IF are off-line.
In summary, the fourth and final restriction is that FOR OPTIMIZATION TO BE
POSSIBLE, A SERIES EXPRESSION CANNOT CONTAIN A CONSTRAINT CYCLE THAT PASSES
THROUGH A NON-SERIES OUTPUT OR AN OFF-LINE PORT. Whenever this restriction
is violated a warning message is issued. Violations can be fixed either by
breaking the cycle or restructuring the computation so that the offending
port is removed from the cycle.
Defining New Series Functions
New functions operating on series can be defined just as easily as new
functions operating on any other data type. However, expressions
containing these new functions cannot be transformed into loops unless a
complete analysis of the functions is available. Among other things, this
implies that the definition of a new series function must appear before its
first use.
OPTIMIZABLE-SERIES-FUNCTION [Declaration specifier]
The declaration specifier (OPTIMIZABLE-SERIES-FUNCTION INTEGER) indicates
that the function being defined is a series function that needs to be
analyzed so that it can be optimized when it appears in series expressions.
(A warning is issued if the function being defined neither takes a series
as input nor produces a series as output.) INTEGER (default 1) specifies
the number of values returned by the function being defined. (This cannot
necessarily be determined by local analysis.) The only place
OPTIMIZABLE-SERIES-FUNCTION is allowed to appear is in a declaration
immediately inside a DEFUN. As an example, the following shows how a
simplified version of COLLECT-SUM could be defined.
(DEFUN SIMPLE-COLLECT-SUM (NUMBERS)
(DECLARE (OPTIMIZABLE-SERIES-FUNCTION 1))
(COLLECT-FN 'NUMBER #'(LAMBDA () 0) #'+ NUMBERS))
OFF-LINE-PORT [Declaration specifier]
The declaration specifier (OFF-LINE-PORT PORT-SPEC1 PORT-SPEC2 ...)
specifies that the indicated inputs and outputs are off-line. This
declaration specifier is only allowed in a DEFUN that contains the
declaration OPTIMIZABLE-SERIES-FUNCTION. Each PORT-SPEC must either be a
symbol that is one of the inputs of the function or an integer J indicating
the jth output (counting from zero). For example, (OFF-LINE-PORT X 1)
indicates that the input X and the second output are off-line. Every port
that is not mentioned in an OFF-LINE-PORT declaration is assumed to be
on-line. A warning is issued whenever a port's actual on-line/off-line
status does not agree with its declared status. This makes it easier to
keep track of which ports are off-line and which are not. Note that
off-line ports virtually never arise when defining scanners or reducers.
Declarations
A key feature of Lisp is that variable declarations are strictly optional.
Nevertheless, it is often the case that they are necessary in situations
where efficiency matters. Therefore, it is important that it be POSSIBLE
for programmers to provide declarations for every variable in a program.
The transformation of series expressions into loops presents certain
problems in this regard, because the loops created contain variables not
evident in the original code. However, if the information described below
is supplied by the user, appropriate declarations can be generated for all
of the loop variables created.
All the explicit variables that are bound in a series expression (for
example, by a LET that is part of the expression) should be given
informative declarations making use of the type specifier (SERIES
ELEMENT-TYPE) where appropriate.
Informative types should be supplied to series functions (such as SCAN and
MAP-FN) that have type arguments. When using SCAN it is important to
specify the type of element in the sequence as well as the sequence itself
(for example, by using (VECTOR * INTEGER) as opposed to merely VECTOR).
The form (LIST ELEMENT-TYPE) can be used to specify the type of elements in
a list.
If it is appropriate to have a type more specific than (SERIES T)
associated with the output of #M, #Z, SCAN-ALIST, SCAN-FILE, SCAN-HASH,
SCAN-LISTS-OF-LISTS-FRINGE, SCAN-LISTS-OF-LISTS, SCAN-PLIST, SERIES,
LATCH, or CATENATE, then the form THE, must be used to specify this type.
Finally, if the expression computing a non-series argument to a series
variable is neither a variable nor a constant, THE must be used to specify
the type of its result.
For example, the declarations in the series expressions below are
sufficient to ensure that every loop variable will have an accurate
declaration.
(COLLECT-LAST (CHOOSE-IF #'PLUSP (SCAN '(LIST INTEGER) DATA)))
(COLLECT '(VECTOR * FLOAT)
(MAP-FN 'FLOAT #'/
(SERIES (THE INTEGER (CAR DATA)))
(THE (SERIES INTEGER) (SCAN-FILE F))))
The amount of information the user has to provide is reduced by the fact
that this information can be propagated from place to place. For instance,
the variable holding the output of CHOOSE-IF holds a subset of the elements
held by the input variable. As a result, it is appropriate for it to have
the same type. When defining a new series function, the type specifier
SERIES-ELEMENT-TYPE can be used to indicate where type propagation should
occur.
SERIES-ELEMENT-TYPE [Type specifier]
The type specifier (SERIES-ELEMENT-TYPE VARIABLE) denotes the type of
elements in the series held in VARIABLE. VARIABLE must be a variable
carrying a series value (for example, a series argument of a series
function). SERIES-ELEMENT-TYPE can only be used in three places: in a
declaration in a LET, MAPPING, PRODUCING, or other binding form in a series
expression; in a declaration in a DEFUN being used to define a series
function; or in a type argument to a series function. As an example,
consider that COLLECT-LAST could have been defined as follows. The use of
SERIES-ELEMENT-TYPE ensures that the internal variable keeping track of the
most recent item has the correct type.
(DEFUN COLLECT-LAST (ITEMS &OPTIONAL (DEFAULT NIL))
(DECLARE (OPTIMIZABLE-SERIES-FUNCTION))
(COLLECT-FN '(SERIES-ELEMENT-TYPE ITEMS)
#'(LAMBDA () DEFAULT)
#'(LAMBDA (OLD NEW) NEW)
ITEMS))
Primitives
A large number of series functions are provided, because there are a large
number of useful operations that can be performed on series. However, this
functionality can be boiled down to a small number of primitive constructs.
COLLECTING-FN embodies the fundamental idea of series computations that
utilize internal state. It can be used as the basis for defining any
on-line transducer.
UNTIL embodies the fundamental idea of producing a series that is shorter
than the shortest input series. In particular, it embodies the idea of
computing a bounded series from non-series inputs. Together with
COLLECTING-FN, UNTIL can be used to define SCAN-FN, which can be used as
the basis for defining all the other scanners.
COLLECT-LAST embodies the fundamental idea of producing a non-series value
from a series. Together with COLLECTING-FN, it can be used to define
COLLECT-FN, which (with the occasional assistance of UNTIL) can be used as
the basis for defining all the other collectors.
PRODUCING embodies the fundamental idea of preorder computation. It can be
used as the basis for defining all the other series functions, including
the off-line transducers.
In addition to the above, four primitives are involved with supporting
various specialized aspects of series functions. Alterability is supported
by the function TO-ALTER and the declaration PROPAGATE-ALTERABILITY. The
propagation of type information is supported by the type specifier
SERIES-ELEMENT-TYPE. The best implementation of certain series functions
requires the form ENCAPSULATED.
PRODUCING OUTPUT-LIST INPUT-LIST {DECLARATION}* {FORM}* [Macro]
PRODUCING computes and returns a group of series and non-series outputs
given a group of series and non-series inputs. The key feature of
PRODUCING is that some or all of the series inputs and outputs can be
processed in an off-line way. To support this, the processing in the body
(consisting of the FORMS) is performed from the perspective of generators
and gatherers (see below). Each series input is converted to a generator
before being used in the body. Each series output is associated with a
gatherer in the body.
The OUTPUT-LIST has the same syntax as the binding list of a LET. The
names of the variables must be distinct from each other and from the names
of the variables in the INPUT-LIST. If there are N variables in the
OUTPUT-LIST, PRODUCING computes N outputs. There must be at least one
output variable. The variables act as the names for the outputs and can be
used in either of two ways. First, if an output variable has a value
associated with it in the OUTPUT-LIST, then the variable is treated as
holding a non-series value. The variable is initialized to the indicated
value and can be used in any way desired in the body. The eventual output
value is whatever value is in the variable when the execution of the body
terminates. Second, if an output variable does not have a value associated
with it in the OUTPUT-LIST, the variable is given as its value a gatherer
that collects elements. The only valid way to use the variable in the body
is in a call on NEXT-OUT. The output returned is a series containing these
elements. If the body never terminates, this series is unbounded.
The INPUT-LIST also has the same syntax as the binding list of a LET.
The names of the variables must be distinct from each other and the names
of the variables in the OUTPUT-LIST. The values can be series or
non-series. If the value is not explicitly specified, it defaults to NIL.
The variables act logically both as inputs and state variables and can be
used in one of two ways. First, if an input variable is associated with a
non-series value, then it is given this value before the evaluation of the
body begins and can be used in any way desired in the body. Second, if an
input variable is associated with a series, then the variable is given a
generator corresponding to this series as its initial value. The only
valid way to use the variable in the body is in a call on NEXT-IN.
There can be declarations at the start of the body. However, the only
declarations allowed are IGNORE declarations, type declarations, and
PROPAGATE-ALTERABILITY declarations (see below). In particular, it is an
error for any of the input or output variables to be special.
In conception, the body can contain arbitrary Lisp expressions. After the
appropriate generators and gatherers have been set up, the body is executed
until it terminates. If the body never terminates, the series outputs (if
any) are unbounded in length and the non-series outputs (if any) are never
produced.
Although easy to understand, this view of what can happen in the body
presents severe difficulties when optimizing (and even when evaluating)
series expressions that contain calls on PRODUCING. As a result, several
limitations are imposed on the form of the body to simplify the processing
required.
The first limitation is that, exclusive of any declarations, the body must
have the form (LOOP (TAGBODY ...)). The following example shows how
PRODUCING could be used to implement a scanner creating an unbounded series
of integers.
(PRODUCING (NUMS) ((NUM 0))
(DECLARE (INTEGER NUM) (TYPE (SERIES INTEGER) NUMS))
(LOOP
(TAGBODY
(SETQ NUM (1+ NUM))
(NEXT-OUT NUMS NUM))))
=> #Z(1 2 3 4 ...)
The second limitation is that the form TERMINATE-PRODUCING must be used to
terminate the execution of the body. Any other method of terminating the
body (with RETURN, for example) is an error. The following example shows
how PRODUCING could be used to implement the operation of summing a series.
The function TERMINATE-PRODUCING is used to stop the computation when
NUMBERS runs out of elements.
(PRODUCING ((SUM 0)) ((NUMBERS #Z(1 2 3)) NUM)
(LOOP
(TAGBODY
(SETQ NUM (NEXT-IN NUMBERS (TERMINATE-PRODUCING)))
(SETQ SUM (+ SUM NUM)))))
=> 6
The third limitation is that calls on NEXT-OUT associated with output
variables must appear at top level in the TAGBODY in the body. They cannot
be nested in other forms. In addition, an output variable can be the
destination of at most one call on NEXT-OUT and if it is the destination
of a NEXT-OUT, it cannot be used in any other way.
If the call on NEXT-OUT for a given output appears in the final part of the
TAGBODY in the body, after everything other than other calls on NEXT-OUT,
then the output is an on-line output---a new value is written on every
cycle of the body. Otherwise the output is off-line.
The following example shows how PRODUCING could be used to split a series
into two parts. Items are read in one at a time and tested. Depending on
the test, they are written to one of two outputs. Note the use of labels
and branches to keep the calls on NEXT-OUT at top level. Both outputs are
off-line. The first example above shows an on-line output.
(PRODUCING (ITEMS-1 ITEMS-2) ((ITEMS #Z(1 -2 3 -4)) ITEM)
(LOOP
(TAGBODY (SETQ ITEM (NEXT-IN ITEMS (TERMINATE-PRODUCING)))
(IF (NOT (PLUSP ITEM)) (GO D))
(NEXT-OUT ITEMS-1 ITEM)
(GO F)
D (NEXT-OUT ITEMS-2 ITEM)
F )))
=> #Z(1 3) and #Z(-2 -4)
The fourth limitation is that the calls on NEXT-IN associated with an input
variable V must appear at top level in the TAGBODY in the body, nested in
assignments of the form (SETQ VAR (NEXT-IN V ...)). They cannot be nested
in other forms. In addition, an input variable can be the source for at
most one call on NEXT-IN and if it is the source for a NEXT-IN, it cannot
be used in any other way.
If the call on NEXT-IN for a given input has as its sole termination action
(TERMINATE-PRODUCING) and appears in the initial part of the TAGBODY in the
body, before anything other than similar calls on NEXT-IN, then the input
is an on-line input---a new value is read on every cycle of the body.
Otherwise the input is off-line.
The example below shows how PRODUCING could be used to concatenate two
series. To start with, elements are read from the first input series.
When this runs out, a flag is set and reading begins from the second input.
Both inputs are off-line. The example above shows an on-line input.
(PRODUCING (ITEMS) ((ITEM-1 #Z(1 2))
(ITEM-2 #Z(3 4))
(IN-2 NIL)
ITEM)
(LOOP
(TAGBODY (IF IN-2 (GO D))
(SETQ ITEM (NEXT-IN ITEM-1 (SETQ IN-2 T) (GO D)))
(GO F)
D (SETQ ITEM (NEXT-IN ITEM-2 (TERMINATE-PRODUCING)))
F (NEXT-OUT ITEMS ITEM))))
=> #Z(1 2 3 4)
TERMINATE-PRODUCING [Macro]
This form (which takes no arguments) is used to terminate execution of (the
expansion of) the PRODUCING macro. As with the form GO,
TERMINATE-PRODUCING does not return any values; rather, control immediately
leaves the current context. The form TERMINATE-PRODUCING is allowed to
appear only in a PRODUCING body and causes the termination of the enclosing
call on PRODUCING.
PROPAGATE-ALTERABILITY [Declaration specifier]
The declaration specifier (PROPAGATE-ALTERABILITY INPUT OUTPUT) indicates
that attempts to alter an element of OUTPUT should be satisfied by altering
the corresponding element of INPUT. (The corresponding element of INPUT
is the one most recently read at the moment when the output element is
written.) This declaration can only appear in a call on PRODUCING. INPUT
and OUTPUT must be an input and an output of the PRODUCING. The example
below shows how the propagation of alterability could be supported in a
simplified version of UNTIL.
(DEFUN SIMPLE-UNTIL (BOOLS ITEMS)
(DECLARE (OPTIMIZABLE-SERIES-FUNCTION))
(PRODUCING (Z) ((X BOOLS) (Y ITEMS) BOOL ITEM)
(DECLARE (PROPAGATE-ALTERABILITY Y Z))
(LOOP
(TAGBODY
(SETQ BOOL (NEXT-IN X (TERMINATE-PRODUCING)))
(SETQ ITEM (NEXT-IN Y (TERMINATE-PRODUCING)))
(IF BOOL (TERMINATE-PRODUCING))
(NEXT-OUT Z ITEM)))))
ENCAPSULATED ENCAPSULATING-FN SCANNER-OR-COLLECTOR [Macro]
Some of the features provided by Common Lisp are supported solely by
encapsulating forms. For example, there is no way to specify a cleanup
expression that will always be run, even when an abort occurs, without
using UNWIND-PROTECT. ENCAPSULATED makes it possible to take advantage of
forms such as UNWIND-PROTECT when defining a series function.
ENCAPSULATED specifies a function that places an encapsulating form around
the computation performed by its second argument. The first argument must
be a quoted function that takes a Lisp expression and wraps the appropriate
encapsulating form around it, returning the resulting code. The second
input must be a literal call on SCAN-FN, SCAN-FN-INCLUSIVE, or COLLECT-FN.
The second argument can count on being evaluated in the scope of the
encapsulating form. The values returned by the second argument are
returned as the values of ENCAPSULATED. The following shows how
ENCAPSULATED could be used to define a simplified version of COLLECT-FILE.
(DEFUN COLLECT-FILE-WRAP (FILE NAME BODY)
`(WITH-OPEN-FILE (,FILE ,NAME :DIRECTION :OUTPUT) ,BODY))
(DEFMACRO SIMPLE-COLLECT-FILE (NAME ITEMS)
(LET ((FILE (GENSYM)))
`(ENCAPSULATED #'(LAMBDA (BODY)
(COLLECT-FILE-WRAP ',FILE ',NAME BODY))
(COLLECT-FN T #'(LAMBDA () T)
#'(LAMBDA (STATE ITEM)
(PRINT ITEM ,FILE)
STATE)
,ITEMS))))
Generators and Gatherers
Generators are generalized input streams in the sense of Smalltalk. A
generator can produce a potentially unbounded number of elements of any
type. Individual elements are not computed until requested by NEXT-IN.
When an element is taken from a generator, it is removed by side effect.
Subsequent uses of NEXT-IN obtain later elements.
There is a close relationship between a generator and a series of the
elements it produces. In particular, any series can be converted into a
generator. As a result, all the scanner functions used for creating series
can be used to create generators as well. There is no need to have a
separate set of functions for creating generators.
Gatherers are generalized output streams. Elements of any type can be
entered into a gatherer using NEXT-OUT. The gatherer combines the elements
together in time-sequence order into a net result. This result can be
retrieved using RESULT-OF.
There is a close relationship between a gatherer and a collector function
that combines elements in the same way. In particular, any one-input
one-output collector can be converted into a gatherer. As a result, all
the collectors used for computing summary results from series can be used
to create gatherers. There is no need to have a separate set of functions
for creating gatherers.
Generators
GENERATOR SERIES [Function]
Given a series, GENERATOR returns a generator containing the same elements.
NEXT-IN GENERATOR {ACTION}* [Macro]
NEXT-IN returns the next element in the generator GENERATOR. The ACTIONS
can be any Lisp expressions. They are evaluated if and only if no more
elements can be retrieved from GENERATOR. If there are no more elements
and no actions, it is an error. It is also an error to apply NEXT-IN to a
generator a second time after the generator has run out of elements. As an
example of generators, consider the following.
(LET ((X (GENERATOR (SCAN '(1 2 3 4)))))
(WITH-OUTPUT-TO-STRING (S)
(LOOP (PRIN1 (NEXT-IN X (RETURN)) S)
(PRIN1 (NEXT-IN X (RETURN)) S)
(PRINC "," S))))
=> "12,34,"
Gatherers
GATHERER COLLECTOR [Function]
The COLLECTOR must be a function of type (FUNCTION ((SERIES t1)) t2).
Given this function, GATHERER returns a gatherer that accepts elements of
type t1 and returns a final result of type t2. The method for combining
elements used by the gatherer is the same as the one used by the COLLECTOR.
NEXT-OUT GATHERER ITEM [Function]
Given a gatherer and a value, NEXT-OUT enters the value into the gatherer.
RESULT-OF GATHERER [Function]
RESULT-OF retrieves the net result from a gatherer. RESULT-OF can be
applied at any time. However, it is an error to apply RESULT-OF twice to
the same gatherer or to apply NEXT-OUT to a gatherer once RESULT-OF has
been applied.
(LET ((G (GATHERER #'COLLECT-SUM)))
(DOLIST (I '(1 2 3 4))
(NEXT-OUT G I)
(IF (EVENP I) (NEXT-OUT G (* 10 I))))
(RESULT-OF G))
=> 70
GATHERING ({(VAR FN)}*) {FORM}* [Macro]
The first subform must be a list of pairs. The first element of each pair,
VAR, must be a variable name. The second element of each pair, FN, must be
a form that when wrapped in (FUNCTION ...) is acceptable as an argument to
GATHERER. Each symbol is bound to a gatherer constructed from the
corresponding collector. The body (consisting of the FORMS) is evaluated
in the scope of these bindings. When this evaluation is complete,
GATHERING returns the RESULT-OF each gatherer. If there are N pairs in the
binding list, GATHERING returns N values. For example:
(DEFUN EXAMP (DATA)
(GATHERING ((X COLLECT) (Y COLLECT-SUM))
(ITERATE ((I (SCAN DATA)))
(CASE (FIRST I)
(:SLOT (NEXT-OUT X (SECOND I)))
(:PART (DOLIST (J (SECOND I)) (NEXT-OUT X J))))
(NEXT-OUT Y (THIRD I)))))
(EXAMP '((:SLOT A 10) (:PART (C D) 40))) => (A C D) and 50
As a further illustration of gatherers, consider the following definition
for a simplified version of GATHERING that handles only one binding pair.
(DEFMACRO SIMPLE-GATHERING (((VAR COLLECTOR)) &BODY BODY)
`(LET ((,VAR (GATHERER (FUNCTION ,COLLECTOR))))
,@BODY
(RESULT-OF ,VAR)))
The full capabilities of GATHERING can be supported in much the same way.
;------------------------------------------------------------------------
;Copyright Massachusetts Institute of Technology, Cambridge, Massachusetts.
;Permission to use, copy, modify, and distribute this software and its
;documentation for any purpose and without fee is hereby granted,
;provided that this copyright and permission notice appear in all
;copies and supporting documentation, and that the name of M.I.T. not
;be used in advertising or publicity pertaining to distribution of the
;software without specific, written prior permission. M.I.T. makes no
;representations about the suitability of this software for any
;purpose. It is provided "as is" without express or implied warranty.
; M.I.T. DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING
; ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL
; M.I.T. BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR
; ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,
; WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION,
; ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS
; SOFTWARE.
;------------------------------------------------------------------------