-
Notifications
You must be signed in to change notification settings - Fork 1
/
Copy pathsrfi-231.html
3698 lines (3573 loc) · 252 KB
/
srfi-231.html
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
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="utf-8">
<title>SRFI 231: Intervals and Generalized Arrays</title>
<link type="image/png" sizes="192x192" rel="icon" href="/favicon.png">
<link type="text/css" rel="stylesheet" href="https://srfi.schemers.org/srfi.css">
<meta name="viewport" content="width=device-width, initial-scale=1">
<script type="text/x-mathjax-config">
MathJax.Hub.Config({
tex2jax: {inlineMath: [['$','$'], ['\\(','\\)']]}
});</script>
<script integrity="sha384-Ra6zh6uYMmH5ydwCqqMoykyf1T/+ZcnOQfFPhDrp2kI4OIxadnhsvvA2vv9A7xYv" crossorigin="anonymous" src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.1/MathJax.js?config=TeX-AMS-MML_HTMLorMML"></script>
</head>
<body>
<h1><a href="https://srfi.schemers.org/"><img class="srfi-logo" src="https://srfi.schemers.org/srfi-logo.svg" alt="SRFI logo"></a>231: Intervals and Generalized Arrays</h1>
<p> by Bradley J. Lucier</p>
<h2 id="status">Status</h2>
<p>This SRFI is currently in <em>final</em> status. Here is <a href="https://srfi.schemers.org/srfi-process.html">an explanation</a> of each status that a SRFI can hold. To provide input on this SRFI, please send email to <code><a href="mailto:srfi+minus+231+at+srfi+dotschemers+dot+org">srfi-231@<span class="antispam">nospam</span>srfi.schemers.org</a></code>. To subscribe to the list, follow <a href="https://srfi.schemers.org/srfi-list-subscribe.html">these instructions</a>. You can access previous messages via the mailing list <a href="https://srfi-email.schemers.org/srfi-231/">archive</a>.</p>
<ul>
<li>Received: 2022-01-05</li>
<li>Draft #1 published: 2022-01-07</li>
<li>Draft #2 published: 2022-01-20</li>
<li>Draft #3 published: 2022-01-26</li>
<li>Draft #4 published: 2022-02-24</li>
<li>Draft #5 published: 2022-03-16</li>
<li>Draft #6 published: 2022-03-17</li>
<li>Draft #7 published: 2022-04-25</li>
<li>Draft #8 published: 2022-05-23</li>
<li>Draft #9 published: 2022-05-26</li>
<li>Draft #10 published: 2022-06-01</li>
<li>Draft #11 published: 2022-06-09</li>
<li>Draft #12 published: 2022-06-20</li>
<li>Draft #13 published: 2022-06-24</li>
<li>Draft #14 published: 2022-07-19</li>
<li>Draft #15 published: 2022-08-12</li>
<li>Draft #16 published: 2022-08-16</li>
<li>Draft #17 published: 2022-09-17</li>
<li>Draft #18 published: 2022-09-22</li>
<li>Draft #19 published: 2022-09-23</li>
<li>Finalized: 2022-09-25</li>
<li>Revised to fix errata:
<ul>
<li>2023-01-16 (Add <a href="#array-assign-erratum">note</a> about invoking the continuations of getters and setters in <code>array-assign!</code> more than once.)</li>
</ul></li>
<li><a href="commentary.html">Commentary</a> added by author on 2023-09-19.</li>
</ul>
<h2>Abstract</h2>
<p>This SRFI specifies an array mechanism for Scheme. Arrays as defined here are quite general; at their most basic, an array is simply a mapping, or function, from multi-indices of exact integers $i_0,\ldots,i_{d-1}$ to Scheme values. The set of multi-indices $i_0,\ldots,i_{d-1}$ that are valid for a given array form the <i>domain</i> of the array. In this SRFI, each array's domain consists of the cross product of intervals of exact integers $[l_0,u_0)\times[l_1,u_1)\times\cdots\times[l_{d-1},u_{d-1})$ of $\mathbb Z^d$, $d$-tuples of integers. Thus, we introduce a data type called $d$-<i>intervals</i>, or more briefly <a href="https://en.wikipedia.org/w/index.php?title=Interval_(mathematics)&oldid=1091935326"><i>intervals</i></a>, that encapsulates this notion. (We borrow this terminology from, e.g., Elias Zakon's <a href="http://www.trillia.com/zakon1.html">Basic Concepts of Mathematics</a>.) Specialized variants of arrays provide portable programs with efficient representations for common use cases.</p>
<p>This is a revised and improved version of <a href="https://srfi.schemers.org/srfi-179/">SRFI 179</a>.</p>
<h2>Contents</h2>
<ul>
<li><a href="#Rationale">Rationale</a></li>
<li><a href="#Overview">Overview</a>
<ul>
<li><a href="#Introductory">Introductory remarks</a></li>
<li><a href="#Bawden">Bawden-style arrays</a></li>
<li><a href="#extension">Our extensions of Bawden-style arrays</a></li>
<li><a href="#transformations">Common transformations on Bawden-style arrays</a></li>
<li><a href="#generalized">Generalized arrays</a></li>
<li><a href="#sharing">Sharing generalized arrays</a></li>
<li><a href="#convention">Notational convention</a></li>
</ul></li>
<li><a href="#Notes">Notes</a></li>
<li><a href="#Specification">Specification</a></li>
<li><a href="#Preliminary">Preliminary notes</a></li>
<li><a href="#Miscellaneous">Miscellaneous procedures</a>
<ul>
<li><a href="#miscprocedures">Procedures</a></li>
</ul></li>
<li><a href="#Intervals">Intervals</a>
<ul>
<li><a href="#intervalprocedures">Procedures</a></li>
</ul></li>
<li><a href="#Storage">Storage classes</a>
<ul>
<li><a href="#storageprocedures">Procedures</a></li>
<li><a href="#storageglobals">Global variables</a></li>
</ul></li>
<li><a href="#Arrays">Arrays</a>
<ul>
<li><a href="#parameters">Parameters</a></li>
<li><a href="#arrayprocedures">Procedures</a></li>
</ul></li>
<li><a href="#Implementation">Implementation</a></li>
<li><a href="#relationship">Relationship to other array libraries</a>
<ul>
<li><a href="#NumPy">NumPy arrays</a></li>
<li><a href="#othersrfis">Other SRFIs</a></li>
<li><a href="#Racket">Racket's array library</a></li>
</ul></li>
<li><a href="#otherexamples">Other examples</a></li>
<li><a href="#Acknowledgments">Acknowledgments</a></li>
<li><a href="#References">References</a></li>
<li><a href="#Copyright">Copyright</a></li>
</ul>
<h2><a id="Rationale">Rationale</a></h2>
<p>This SRFI was motivated by a number of somewhat independent notions, which we outline here and which are explained below.</p>
<ul>
<li>Provide a <b>general API</b> (Application Program Interface) that specifies the minimal required properties of any given array, without requiring any specific implementation strategy from the programmer for that array.</li>
<li>Provide a <b>single, efficient implementation for dense arrays</b> (which we call <i>specialized arrays</i>).</li>
<li>Provide <b>useful array transformations</b>.</li>
<li>Separate <b>the procedures that specify the work to be done</b> (<code>array-map</code>, <code>array-outer-product</code>, etc.) from <b>the procedures that actually do the work</b> (<code>array-copy</code>, <code>array-assign!</code>, <code>array-fold-left</code>, etc.). This approach <b>avoids temporary intermediate arrays</b> in computations.</li>
<li>Encourage <b>bulk processing of arrays</b> rather than word-by-word operations.</li>
</ul>
<p>This SRFI differs from the finalized <a href="https://srfi.schemers.org/srfi-179/">SRFI 179</a> in the following ways:</p>
<ul>
<li>Empty and zero-dimensional arrays are incorporated into this SRFI. It is an error to call the setter or getter of an empty array. Zero-dimensional arrays specify their sole element with an empty multi-index.</li>
<li><code>specialized-array-default-safe?</code> and <code>specialized-array-default-mutable?</code> are now <a href="https://srfi.schemers.org/srfi-39/">SRFI 39</a> parameters.</li>
<li><code>list->array</code> is now called as <code>(list->array interval list ...)</code>; i.e., the order of the first two arguments has been reversed.</li>
<li><code>array-copy</code> no longer allows changing the domain of the result. Use <code>(specialized-array-reshape (array-copy ...) <var>new-domain</var>)</code> instead.</li>
<li><code>make-specialized-array</code> now accepts an optional initial value with which to fill the new array.</li>
<li>The SRFI 179 procedure <code>array-fold</code> has been replaced by <a href="#array-fold-left"><code>array-fold-left</code></a>. Now <code>array-fold-left</code> and <code>array-fold-right</code> follow the definition of the left and right folds in <a href="http://www.r6rs.org/final/html/r6rs-lib/r6rs-lib-Z-H-4.html">R6RS</a> (as well as <a href="https://ocaml.org/api/List.html">Ocaml</a> and <a href="https://wiki.haskell.org/Fold">Haskell</a>). <code>array-fold-left</code> from this SRFI has different semantics to <code>array-fold</code> from SRFI 179.</li>
<li><code>array-assign!</code> now requires that the source and destination have the same domain. Use <code>specialized-array-reshape</code> on the destination array to mimic the SRFI 179 version.</li>
<li>If the first argument to <code>array-copy</code> is a specialized array, then omitted arguments are taken from the argument array and do not default to <code>generic-storage-class</code>, <code>(specialized-array-default-mutable?)</code>, and <code>(specialized-array-default-safe?)</code>. Thus, by default, <code>array-copy</code> makes a true copy of a specialized array.</li>
<li>Procedures that generate useful permutations have been added: <a href="#index-rotate"><code>index-rotate</code></a>, <a href="#index-first"><code>index-first</code></a>, <a href="#index-last"><code>index-last</code></a>, and <a href="#index-swap"><code>index-swap</code></a>.</li>
<li><code>interval-rotate</code> and <code>array-rotate</code> have been removed; use <code>(array-permute A (index-rotate (array-dimension A) k))</code> instead of <code>(array-rotate A k)</code>.</li>
<li><code>array-tile</code> is now more flexible in how you can decompose an array.</li>
<li><code>array-elements-in-order?</code> has been renamed <code>array-packed?</code>.</li>
<li><code>interval-cartesian-product</code> can now take zero arguments, in which case it returns <code>(make-interval '#())</code>.</li>
<li><code>char-storage-class</code> is provided.</li>
<li>Introduced new procedures <a href="#interval-width"><code>interval-width</code></a>, <a href="#interval-widths"><code>interval-widths</code></a>, <a href="#interval-empty?"><code>interval-empty?</code></a>, <a href="#interval-fold-left"><code>interval-fold-left</code></a>, <a href="#interval-fold-right"><code>interval-fold-right</code></a>, <a href="#storage-class-data?"><code>storage-class-data?</code></a>, <a href="#storage-class-data-rarrow-body"><code>storage-class-data->body</code></a>, <a href="#array-empty?"><code>array-empty?</code></a>, <a href="#make-specialized-array-from-data"><code>make-specialized-array-from-data</code></a>, <a href="#vector-rarrow-array"><code>vector->array</code></a>, <a href="#array-rarrow-vector"><code>array->vector</code></a>, <a href="#list*-rarrow-array"><code>list*->array</code></a>, <a href="#array-rarrow-list*"><code>array->list*</code></a>, <a href="#vector*-rarrow-array"><code>vector*->array</code></a>, <a href="#array-rarrow-vector*"><code>array->vector*</code></a>, <a href="#array-inner-product"><code>array-inner-product</code></a>, <a href="#array-stack"><code>array-stack</code></a>, <a href="#array-append"><code>array-append</code></a>, <a href="#array-block"><code>array-block</code></a>, <a href="#array-freeze!"><code>array-freeze!</code></a>, and <a href="#array-decurry"><code>array-decurry</code></a>.</li>
<li>The sample implementation now provides call/cc-safe implementations of all procedures whose names do not end with <code>!</code>. We define new procedures <a href="#array-copy!"><code>array-copy!</code></a>, <a href="#array-stack!"><code>array-stack!</code></a>, <a href="#array-decurry!"><code>array-decurry!</code></a>, <a href="#array-append!"><code>array-append!</code></a>, and <a href="#array-block!"><code>array-block!</code></a>, which are not guaranteed to be call/cc-safe but which may be faster or use less memory than the corresponding call/cc-safe versions. See further discussion, with our definition of "call/cc-safe", in the notes below.</li>
<li>A new set of "Introductory remarks" surveys some of the more important procedures in this SRFI.</li>
</ul>
<h2><a id="Overview">Overview</a></h2>
<h3><a id="Introductory">Introductory remarks</a></h3>
<p>The next few sections talk perhaps too much about the mathematical ideas that underpin many of the procedures in this SRFI, so I discuss here some of the procedures and compare them to operations on spreadsheets, matrices, and imaging.</p>
<p>There are two procedures that simply create new arrays:</p>
<ul>
<li><a href="#make-array"><code>make-array</code></a>: Takes as arguments a specification of the valid indices $i\ j\ k$ etc. of the array, together with a Scheme procedure, which, when presented with indices in the valid range, computes the array element. The elements of the array are not precomputed and stored somewhere; the specified procedure is recalculated each time that element is needed. A procedure that modifies which element is returned at a given set of indices is allowed as a third argument. See the sparse matrix example below to see how this is useful. We call the result a <i>generalized array</i>.</li>
<li><a href="#make-specialized-array"><code>make-specialized-array</code></a>: Takes as an argument a specification of a valid range of indices and reserves a block of memory in which to store elements of the matrix; optionally, one can restrict which objects can be stored as elements in the array or generate code to precheck that all the indices are in range on each access, and to precheck that values stored as array elements actually comply with any given restrictions. Elements are stored in row-major order, as in C. We call the result a <i>specialized array</i>.</li>
</ul>
<p>In the next group of procedures, the new and old arrays share elements, so modifications to one affect the others. Also, none of these procedures move any data: for specialized arrays they just change how the data are indexed, while for generalized arrays they manipulate the arguments of the getter and setter. For specialized arrays, these procedures can be combined in any way without increasing unreasonably the number of operations required to access an array element.</p>
<ul>
<li><a href="#array-extract"><code>array-extract</code></a>: Constructs a rectangular "window" or "view" into an existing array, like a rectangular region of a spreadsheet, or a submatrix of a matrix.</li>
<li><a href="#array-translate"><code>array-translate</code></a>: Slides an array around, like changing the zero-based indexing of C arrays to the 1-based indexing of Fortran arrays. If you wanted to compare two subimages of the same number of rows and columns of pixels, for example, you could use array-extract to select each of the subimages, and then use array-translate to overlay one on the other, i.e., to use the same indexing for both.</li>
<li><a href="#array-permute"><code>array-permute</code></a>: Swaps rows, columns, sheets, etc., of the original array, like swapping rows and columns in a spreadsheet or transposing a matrix. The auxiliary procedures <code>index-rotate</code>, <code>index-first</code>, <code>index-last</code>, and <code>index-swap</code> create commonly used permutations.</li>
<li><a href="#array-reverse"><code>array-reverse</code></a>: Reverses the order of rows or columns (or both) of a spreadsheet. Like flipping an image vertically or horizontally.</li>
<li><a href="#array-sample"><code>array-sample</code></a>: Accesses every second (or third, etc.) row or column, or both, of an array.</li>
</ul>
<p>The following two procedures decompose arrays in different ways. They return <i>generalized arrays</i> whose elements are themselves arrays. Like the procedures described immediately above, the resulting subarrays share elements with their argument.</p>
<ul>
<li><a href="#array-curry"><code>array-curry</code></a>: Represents a $d$-dimensional array as a $d'$-dimensional array whose entries are themselves arrays of dimension $d-d'$. Like thinking of a three-dimensional CT scan as a one-dimensional array of two-dimensional slices, or thinking of a matrix as a one-dimensional array of one-dimensional rows. You could combine this operation with <code>array-permute</code> to think of a matrix as an array of columns, or look at slices in different orientations of a three-dimensional CT scan. Considering a video as a one-dimensional sequence (in time) of two-dimensional stills (in space) is another example of currying. The subarrays share elements with the original array. The procedures <code>array-decurry</code> and <code>array-stack</code>, described below, reverse this process.</li>
<li><a href="#array-tile"><code>array-tile</code></a>: Decomposes a $d$-dimensional array into $d$-dimensional sub-blocks with cuts parallel to the coordinate axes, and returns the subarrays in an array. Like breaking a large matrix into smaller matrices for block matrix operations. The subarrays share elements with the original array. The procedures <code>array-block</code> and <code>array-append</code>, described below, reverse this process.</li>
</ul>
<p>The next few procedures set up operations to be executed in the future. They build <i>generalized</i> arrays.</p>
<ul>
<li><a href="#array-map"><code>array-map</code></a>: Specifies an operation to be applied componentwise on arrays, so if <code><var>A</var></code> and <code><var>B</var></code> are matrices, <code>(array-map + <var>A</var> <var>B</var>)</code> sets up a new generalized array that adds elements of the arrays componentwise. You can chain these operations, so have <code>(array-map + (array-map (lambda (<var>x</var>) (* <var>alpha x</var>)) <var>A</var>) <var>B</var>)</code> without immediately computing and storing all the values of those arrays.</li>
<li><a href="#array-outer-product"><code>array-outer-product</code></a>: Applies an operation to all possible pairs of elements of two original arrays. Like considering an $m$-vector as a column vector and an $n$-vector as a row vector, and multiplying them together to compute an $m\times n$ matrix.</li>
<li><a href="#array-inner-product"><code>array-inner-product</code></a>: Like APL's inner product; multiplying two matrices is an example of an operation implemented using <code>array-inner-product</code>.</li>
</ul>
<p>Then, there are procedures that <i>do</i> generate all elements of an array and either store them somewhere, or combine them in some way:</p>
<ul>
<li><a href="#array-copy"><code>array-copy</code></a>: Evaluates the argument array at all valid indices and stores those values into a new specialized array.</li>
<li><a href="#array-assign!"><code>array-assign!</code></a>: Evaluates the argument array at all valid indices and assigns their values to the elements of an existing array. In the Gaussian Elimination example below, we combine <code>array-map</code>, <code>array-outer-product</code>, <code>array-extract</code>, and <code>array-assign!</code> to do one step of the elimination.</li>
<li><a href="#array-stack"><code>array-stack</code></a>: Like taking the individually rendered frames of an animated movie and combining them in time to make a complete video. Can be considered a partial inverse to <code>array-curry</code>. Returns a specialized array.</li>
<li><a href="#array-decurry"><code>array-decurry</code></a>: Takes a "curried" array of arrays, and returns a single array with the same elements. An inverse to <code>array-curry</code>; a multi-dimensional version of <code>array-stack</code>.</li>
<li><a href="#array-append"><code>array-append</code></a>: Like concatenating a number of images left to right, or top to bottom. Returns a specialized array. A partial inverse to <code>array-tile</code>.</li>
<li><a href="#array-block"><code>array-block</code></a>: Assumes that an array has been decomposed into blocks by cuts perpendicular to each coordinate axis; takes an array of those blocks as an argument, and returns a reconstructed array. An inverse to <a href="#array-tile"><code>array-tile</code></a>; a multi-dimensional version of array-append.</li>
<li><a href="#array-fold-left"><code>array-fold-left</code></a>, <a href="#array-fold-right"><code>array-fold-right</code></a>, <a href="#array-reduce"><code>array-reduce</code></a>, <a href="#array-for-each"><code>array-for-each</code></a>, <a href="#array-any"><code>array-any</code></a>, and <a href="#array-every"><code>array-every</code></a>: Evaluates all elements of an array (for <code>array-every</code> and <code>array-any</code>, as many as needed to know the result), and combines them in certain ways.</li>
</ul>
<p>Finally, we have procedures that convert between other data and arrays:</p>
<ul>
<li><a href="#make-specialized-array-from-data"><code>make-specialized-array-from-data</code></a>: Construct a specialized array whose body shares elements with an existing data structure.</li>
<li><a href="#array-rarrow-list"><code>array->list</code></a>, <a href="#list-rarrow-array"><code>list->array</code></a>, <a href="#array-rarrow-vector"><code>array->vector</code></a>, and <a href="#vector-rarrow-array"><code>vector->array</code></a>: Either transfer the elements of an array to a list or vector, or construct a specialized array from the elements of a list or vector.</li>
<li><a href="#array-rarrow-list*"><code>array->list*</code></a>, <a href="#list*-rarrow-array"><code>list*->array</code></a>, <a href="#array-rarrow-vector*"><code>array->vector*</code></a>, and <a href="#vector*-rarrow-array"><code>vector*->array</code></a>: Either transfer the elements of an array to a nested list or vector, or construct a specialized array from the elements of a nested list or vector.</li>
</ul>
<p>I hope this brief discussion gives a flavor for the design of this SRFI.</p>
<h3><a id="Bawden">Bawden-style arrays</a></h3>
<p>In a <a href="https://groups.google.com/g/comp.lang.scheme/c/7nkx58Kv6RI/m/a5hdsduFL2wJ">1993 post</a> to the news group comp.lang.scheme, Alan Bawden gave a simple implementation of multi-dimensional arrays in R4RS scheme. The only constructor of new arrays required specifying an initial value, and he provided the three low-level primitives <code>array-ref</code>, <code>array-set!</code>, and <code>array?</code>, as well as <code>make-array</code> and <code>make-shared-array</code>. His arrays were defined on rectangular intervals in $\mathbb Z^d$ of the form $[l_0,u_0)\times\cdots\times [l_{d-1},u_{d-1})$. I'll note that his procedure <code>array-set!</code> puts the value to be entered into the array at the front of the variable-length list of indices that indicate where to place the new value. He offered an intriguing way to "share" arrays in the form of a procedure <code>make-shared-array</code> that took a mapping from a new interval of indices into the domain of the array to be shared. His implementation incorporated what he called an <i>indexer</i>, which was a procedure from the interval $[l_0,u_0)\times\cdots\times [l_{d-1},u_{d-1})$ to an interval $[0,N)$, where the <i>body</i> of the array consisted of a single Scheme vector of length $N$. Bawden called the mapping specified in <code>make-shared-array</code> <i>linear</i>, but I prefer the term <i>affine</i>, as I explain later.</p>
<p>Mathematically, Bawden's arrays can be described as follows. We'll use the vector notation $\vec i$ for a multi-index $i_0,\ldots,i_{d-1}$. (Multi-indices correspond to Scheme <code>values</code>.) Arrays will be denoted by capital letters $A,B,\ldots$, the domain of the array $A$ will be denoted by $D_A$, and the indexer of $A$, mapping $D_A$ to the interval $[0,N)$, will be denoted by $I_A$. Initially, Bawden constructs $I_A$ such that $I_A(\vec i)$ steps consecutively through the values $0,1,\ldots,N-1$ as $\vec i$ steps through the multi-indices $(l_0,\ldots,l_{d-2},l_{d-1})$, $(l_0,\ldots,l_{d-2},l_{d-1}+1)$, $\ldots$, $(l_0,\ldots,l_{d-2}+1,l_{d-1})$, etc., in lexicographical order, which means that if $\vec i$ and $\vec j$ are two multi-indices, then $\vec i<\vec j$ if and only if the least coordinate $k$ where $\vec i$ and $\vec j$ differ satisfies $\vec i_k<\vec j_k$. This ordering of multi-indices is also known as <a href="https://en.wikipedia.org/w/index.php?title=Row-_and_column-major_order&oldid=995330290">row-major order</a>, which is used in the programming language C to order the elements of multi-dimensional arrays. In contrast, the programming language Fortran uses column-major order to order the elements of multi-dimensional arrays.</p>
<p>In <code>make-shared-array</code>, Bawden allows you to specify a new $r$-dimensional interval $D_B$ as the domain of a new array $B$, and a mapping $T_{BA}:D_B\to D_A$ of the form $T_{BA}(\vec i)=M\vec i+\vec b$; here $M$ is a $d\times r$ matrix of integer values and $\vec b$ is a $d$-vector. So this mapping $T_{BA}$ is <i>affine</i>, in that $T_{BA}(\vec i)-T_{BA}(\vec j)=M(\vec i-\vec j)$ is <i>linear</i> (in a linear algebra sense) in $\vec i-\vec j$. The new indexer of $B$ satisfies $I_B(\vec i)=I_A(T_{BA}(\vec i))$.</p>
<p>A fact Bawden exploits in the code, but doesn't point out in the short post, is that $I_B$ is again an affine map, and indeed, the composition of <i>any</i> two affine maps is again affine.</p>
<h3><a id="extension">Our extensions of Bawden-style arrays</a></h3>
<p>We incorporate Bawden-style arrays into this SRFI, but extend them in one minor way that we find useful.</p>
<p>We introduce the notion of a <i>storage class</i>, an object that contains procedures that manipulate, store, check, etc., different types of values. The <code>generic-storage-class</code> can manipulate any Scheme value, whereas, e.g., a <code>u1-storage-class</code> can store only the values 0 and 1 in each element of a body.</p>
<p>We also require that our affine maps be one-to-one, so that if $\vec i\neq\vec j$ then $T(\vec i)\neq T(\vec j)$. Without this property, modifying the $\vec i$th component of $A$ would cause the $\vec j$th component to change.</p>
<h3><a id="transformations">Common transformations on Bawden-style arrays</a></h3>
<p>Requiring the transformations $T_{BA}:D_B\to D_A$ to be affine may seem esoteric and restricting, but in fact many common and useful array transformations can be expressed in this way. We give several examples below: </p>
<ul>
<li><b>Restricting the domain of an array: </b> If the domain of $B$, $D_B$, is a subset of the domain of $A$, then $T_{BA}(\vec i)=\vec i$ is a one-to-one affine mapping. We define <code>array-extract</code> to define this common operation; it's like looking at a rectangular sub-part of a spreadsheet. We use it to extract the common part of overlapping domains of three arrays in an image processing example below. </li>
<li><b>Tiling an array: </b>For various reasons (parallel processing, optimizing cache localization, GPU programming, etc.), one may wish to process a large array as a number of subarrays of the same dimension. We call this <i>tiling</i> the array. The procedure <code>array-tile</code> returns a new array, each entry of which is a subarray extracted (in the sense of <code>array-extract</code>) from the input array.</li>
<li><b>Translating the domain of an array: </b>If $\vec d$ is a vector of integers, then $T_{BA}(\vec i)=\vec i-\vec d$ is a one-to-one affine map of $D_B=\{\vec i+\vec d\mid \vec i\in D_A\}$ onto $D_A$. We call $D_B$ the <i>translate</i> of $D_A$, and we define <code>array-translate</code> to provide this operation.</li>
<li><b>Permuting the coordinates of an array: </b>If $\pi$ <a href="https://en.wikipedia.org/wiki/Permutation">permutes</a> the coordinates of a multi-index $\vec i$, and $\pi^{-1}$ is the inverse of $\pi$, then $T_{BA}(\vec i)=\pi (\vec i)$ is a one-to-one affine map from $D_B=\{\pi^{-1}(\vec i)\mid \vec i\in D_A\}$ onto $D_A$. We provide <code>array-permute</code> for this operation. Several procedures build commonly used permutations: <code>(index-rotate <var>n</var> <var>k</var>)</code> rotates <code><var>n</var></code> indices <code><var>k</var></code> places to the left; <code>(index-first <var>n</var> <var>k</var>)</code> moves the $k$th of $n$ indices to be the first index, leaving the others in order; <code>(index-last <var>n</var> <var>k</var>)</code> moves the $k$th of $n$ indices to be the last index, again leaving the others in order; <code>(index-swap <var>n i j</var>)</code> swaps the $i$th and $j$th of $n$ indices, again leaving the others in order.</li>
<li><b>Currying an array: </b>Let's denote the cross product of two intervals $\text{Int}_1$ and $\text{Int}_2$ by $\text{Int}_1\times\text{Int}_2$; if $\vec j=(j_0,\ldots,j_{r-1})\in \text{Int}_1$ and $\vec i=(i_0,\ldots,i_{s-1})\in \text{Int}_2$, then $\vec j\times\vec i$, which we define to be $(j_0,\ldots,j_{r-1},i_0,\ldots,i_{s-1})$, is in $\text{Int}_1\times\text{Int}_2$. If $D_A=\text{Int}_1\times\text{Int}_2$ and $\vec j\in\text{Int}_1$, then $T_{BA}(\vec i)=\vec j\times\vec i$ is a one-to-one affine mapping from $D_B=\text{Int}_2$ into $D_A$. For each vector $\vec j$ we can compute a new array in this way; we provide <code>array-curry</code> for this operation, which returns an array whose domain is $\text{Int}_1$ and whose elements are themselves arrays, each of which is defined on $\text{Int}_2$. Currying a two-dimensional array would be like organizing a spreadsheet into a one-dimensional array of rows of the spreadsheet.</li>
<li><b>Traversing some indices in a multi-index in reverse order: </b>Consider an array $A$ with domain $D_A=[l_0,u_0)\times\cdots\times[l_{d-1},u_{d-1})$. Fix $D_B=D_A$ and assume we're given a vector of booleans $F$ ($F$ for "flip?"). Then define $T_{BA}:D_B\to D_A$ by $i_j\to i_j$ if $F_j$ is <code>#f</code> and $i_j\to u_j+l_j-1-i_j$ if $F_j$ is <code>#t</code>. In other words, we reverse the ordering of the $j$th coordinate of $\vec i$ if and only if $F_j$ is true. $T_{BA}$ is an affine mapping from $D_B\to D_A$, which defines a new array $B$, and we can provide <code>array-reverse</code> for this operation. Applying <code>array-reverse</code> to a two-dimensional spreadsheet might reverse the order of the rows or columns (or both).</li>
<li><b>Uniformly sampling an array: </b>Assume that $A$ is an array with domain $[0,u_1)\times\cdots\times[0,u_{d-1})$ (i.e., an interval all of whose lower bounds are zero). We'll also assume the existence of vector $S$ of scale factors, which are positive exact integers. Let $D_B$ be a new interval with $j$th lower bound equal to zero and $j$th upper bound equal to $\operatorname{ceiling}(u_j/S_j)$ and let $T_{BA}(\vec i)_j=i_j\times S_j$, i.e., the $j$th coordinate is scaled by $S_j$. ($D_B$ contains precisely those multi-indices that $T_{BA}$ maps into $D_A$.) Then $T_{BA}$ is an affine one-to-one mapping, and we provide <code>interval-scale</code> and <code>array-sample</code> for these operations.</li>
</ul>
<p>We make several remarks. First, all these operations could have been computed by specifying the particular mapping $T_{BA}$ explicitly, so that these procedures are in some sense "convenience" procedures. Second, because the composition of any number of affine mappings is again affine, accessing or changing the elements of a restricted, translated, curried, permuted array is no slower than accessing or changing the elements of the original array itself. Finally, we note that by combining array currying and permuting, say, one can come up with simple expressions of powerful algorithms, such as extending one-dimensional transforms to multi-dimensional separable transforms, or quickly generating two-dimensional slices of three-dimensional image data. Examples are given below.</p>
<h3><a id="generalized">Generalized arrays</a></h3>
<p>Bawden-style arrays are clearly useful as a programming construct, but they do not fulfill all our needs in this area. An array, as commonly understood, provides a mapping from multi-indices $(i_0,\ldots,i_{d-1})$ of exact integers
in a nonempty, rectangular, $d$-dimensional interval $[l_0,u_0)\times[l_1,u_1)\times\cdots\times[l_{d-1},u_{d-1})$, $l_k<u_k$ — the <i>domain</i> of the array — to Scheme objects.
Thus, two things are necessary to specify an array: an interval and a mapping that has that interval as its domain.</p>
<p>Since these two things are often sufficient for certain algorithms, we introduce in this SRFI a minimal set of interfaces for dealing with such arrays.</p>
<p>We also consider as Scheme objects the case when $d>0$ and some $l_k=u_k$; in this case the mathematical cross product is empty, and arrays with such a domain have no elements but still "dimension" $d$. Applying the function associated with this array is an error.</p>
<p>Finally, we allow $d=0$; such an array would have one element, and the function that accesses it is a function with no arguments (i.e., a "thunk").</p>
<p>So an array specifies a multi-dimensional interval, called its <i>domain</i>, and a mapping from this domain to Scheme objects. This mapping is called the <i>getter</i> of the array, accessed with the procedure <code>array-getter</code>; the domain of the array (more precisely, the domain of the array's getter) is accessed with the procedure <code>array-domain</code>.</p>
<p>If this mapping can be changed, the array is said to be <i>mutable</i>, and the mutation is effected
by the array's <i>setter</i>, accessed by the procedure <code>array-setter</code>. We call an object of this type a mutable array. Note: If an array does not have a setter, then we call it immutable even though the array's getter might not be a "pure" procedure, i.e., the value it returns may not depend solely on the arguments passed to the getter.</p>
<p>In general, we leave the implementation of generalized arrays completely open. They may be defined simply by closures, or
they may have hash tables or databases behind an implementation, or may read the values from a file, etc.</p>
<p>In this SRFI, Bawden-style arrays are called <i>specialized</i>. A specialized array may be either mutable or immutable.</p>
<h3><a id="sharing">Sharing generalized arrays</a></h3>
<p>Even if an array $A$ is not a specialized array, it could be "shared" by specifying a new interval $D_B$ as the domain of a new array $B$ and an affine map $T_{BA}:D_B\to D_A$. Each call to $B$ would then be computed as $B(\vec i)=A(T_{BA}(\vec i))$.</p>
<p>One could again "share" $B$, given a new interval $D_C$ as the domain of a new array $C$ and an affine transform $T_{CB}:D_C\to D_B$, and then each access $C(\vec i)=A(T_{BA}(T_{CB}(\vec i)))$. The composition $T_{BA}\circ T_{CB}:D_C\to D_A$, being itself affine, could be precomputed and stored as $T_{CA}:D_C\to D_A$, and $C(\vec i)=A(T_{CA}(\vec i))$ could be computed with the overhead of computing a single affine transformation.</p>
<p>So, if we wanted, we could share generalized arrays with constant overhead by adding a single layer of (multi-valued) affine transformations on top of evaluating generalized arrays. Even though this could be done transparently to the user, we do not do that here; it would be a compatible extension of this SRFI to do so. We provide only the procedure <code>specialized-array-share</code>, not a more general <code>array-share</code>.</p>
<p>Certain ways of sharing generalized arrays, however, are relatively easy to code and are not expensive. If we denote <code>(array-getter <var>A</var>)</code> by <code><var>A_</var></code>, then if <code><var>B</var></code> is the result of <code>array-extract</code> applied to <code><var>A</var></code>, then <code>(array-getter <var>B</var>)</code> is simply <code><var>A_</var></code>. Similarly, if <code><var>A</var></code> is a two-dimensional array, and <code><var>B</var></code> is derived from <code><var>A</var></code> by applying the permutation $\pi((i,j))=(j,i)$, then <code>(array-getter <var>B</var>)</code> is <code>(lambda (i j) (<var>A_</var> j i))</code>. Translation and currying also lead to transformed arrays whose getters are relatively efficiently derived from <code><var>A_</var></code>, at least for arrays of small dimension.</p>
<p>Thus, while we do not provide for sharing of generalized arrays for general one-to-one affine maps $T$, we do allow it for the specific procedures <code>array-extract</code>, <code>array-translate</code>, <code>array-permute</code>, <code>array-curry</code>, <code>array-reverse</code>, <code>array-tile</code>, and <code>array-sample</code>, and we provide relatively efficient implementations of these procedures for arrays of dimension no greater than four.</p>
<h3><a id="convention">Notational convention</a></h3>
<p>If <code><var>A</var></code> is an array, then we generally define <code><var>A_</var></code> to be <code>(array-getter <var>A</var>)</code> and <code><var>A!</var></code> to be <code>(array-setter <var>A</var>)</code>. The latter notation is motivated by the general Scheme convention that the names of procedures that modify the contents of data structures end in <code><var>!</var></code>, while the notation for the getter of an array is motivated by the TeX notation for subscripts. See particularly the <a href="#Haar">Haar transform</a> example.</p>
<h2><a id="Notes">Notes</a></h2>
<ul>
<li><b>Empty and zero-dimensional arrays: </b>The vectors of upper and lower bounds of an interval can have zero elements, in which case the zero-dimensional interval itself has no elements, but zero-dimensional arrays with this domain have getters and setters that take zero indices as arguments, and which return or set a single element, much like a Scheme <code>box</code>. If an interval has at least one upper and lower bound, and at least one of these upper bounds equals the associated lower bound, then that interval is empty, and arrays with empty intervals as domains have getters and setters that should raise an exception when called.</li>
<li><b>This SRFI and <code>call-with-current-continuation</code>: </b>The Scheme procedure <code>call-with-current-continuation</code> captures and encapsulates as a procedure the continuation of the current computation, which, perforce, includes a certain amount of state that consists of the values of captured variables at the point the continuation is captured. This captured procedure can be invoked multiple times, as any procedure can.
<br>No procedure in the sample implementation itself calls <code>call-with-current-continuation</code>, but the procedural arguments to, e.g., <code>make-array</code>, <code>specialized-array-share</code>, <code>array-map</code>, etc., may themselves call <code>call-with-current-continuation</code>.
<br>All procedures in the sample implementation whose names do not end with an exclamation point (!) are written in a way that does not modify the state of any data captured by a continuation. We call such procedures <i>call/cc safe</i>.
<br>It is intended that all procedures in this library whose names do not end with an exclamation point (!) be implemented in a call/cc-safe way.
<br>Besides the procedures <code>array-set!</code> and <code>array-assign!</code>, which explicitly mutate state and which, therefore, are <i>not</i> call/cc safe, we provide the procedures <code>array-copy!</code>, <code>array-stack!</code>, <code>array-decurry!</code>, <code>array-append!</code>, and <code>array-block!</code>, which are not necessarily call/cc safe, but which may be faster or use less memory than the corresponding call/cc-safe versions.
<br id="array-assign-erratum">For the procedures <code>array-copy!</code>, <code>array-stack!</code>, <code>array-decurry!</code>, <code>array-append!</code>, and <code>array-block!</code>, it is an error if the continuation of each call to an array's getter is invoked more than once. For the procedure <code>array-assign!</code>, it is an error if the continuation of each call to the destination's setter or the source's getter is invoked more than once.</li>
<li><b>Relationship to <a href="https://docs.racket-lang.org/math/array_nonstrict.html#%28tech._nonstrict%29">nonstrict arrays</a> in Racket. </b>It appears that what we call simply arrays in this SRFI are called nonstrict arrays in the math/array library of Racket, which in turn was influenced by an <a href="https://www.microsoft.com/en-us/research/wp-content/uploads/2016/07/RArrays.pdf">array proposal for Haskell</a>. Our "specialized" arrays are related to Racket's "strict" arrays.</li>
<li><b>Indexers. </b>The argument <code><var>new-domain->old-domain</var></code> to <code>specialized-array-share</code> is, conceptually, the getter of a multi-valued array.</li>
<li><b>Source of procedure names. </b>The procedure <code>array-curry</code> gets its name from the
<a href="https://en.wikipedia.org/wiki/Currying">curry operator</a> in programming—we are currying the getter of the array and keeping careful track of the domains.
<code>interval-projections</code> can be thought of as currying the
characteristic procedure of the interval, encapsulated here as <code>interval-contains-multi-index?</code>.</li>
<li><b>Choice of procedures on intervals. </b>The choice of procedures for both arrays and intervals was motivated almost solely by what I needed for arrays.</li>
<li><b>Multi-valued arrays. </b>While this SRFI restricts attention to single-valued arrays, wherein the getter of each array returns a single value, allowing multi-valued immutable arrays would be a compatible extension of this SRFI.</li>
</ul>
<h2><a id="Specification">Specification</a></h2>
<dl>
<dt>Miscellaneous Procedures</dt>
<dd><a href="#translation?">translation?</a>,
<a href="#permutation?">permutation?</a>,
<a href="#index-rotate">index-rotate</a>,
<a href="#index-first">index-first</a>,
<a href="#index-last">index-last</a>,
<a href="#index-swap">index-swap</a>.</dd>
<dt>Intervals</dt>
<dd><a href="#make-interval">make-interval</a>,
<a href="#interval?">interval?</a>,
<a href="#interval-dimension">interval-dimension</a>,
<a href="#interval-lower-bound">interval-lower-bound</a>,
<a href="#interval-upper-bound">interval-upper-bound</a>,
<a href="#interval-width">interval-width</a>,
<a href="#interval-lower-bounds-rarrow-list">interval-lower-bounds->list</a>,
<a href="#interval-upper-bounds-rarrow-list">interval-upper-bounds->list</a>,
<a href="#interval-lower-bounds-rarrow-vector">interval-lower-bounds->vector</a>,
<a href="#interval-upper-bounds-rarrow-vector">interval-upper-bounds->vector</a>,
<a href="#interval=">interval=</a>,
<a href="#interval-widths">interval-widths</a>,
<a href="#interval-volume">interval-volume</a>,
<a href="#interval-empty?">interval-empty?</a>,
<a href="#interval-subset?">interval-subset?</a>,
<a href="#interval-contains-multi-index?">interval-contains-multi-index?</a>,
<a href="#interval-projections">interval-projections</a>,
<a href="#interval-for-each">interval-for-each</a>,
<a href="#interval-fold-left">interval-fold-left</a>,
<a href="#interval-fold-right">interval-fold-right</a>,
<a href="#interval-dilate">interval-dilate</a>,
<a href="#interval-intersect">interval-intersect</a>,
<a href="#interval-translate">interval-translate</a>,
<a href="#interval-permute">interval-permute</a>,
<a href="#interval-scale">interval-scale</a>,
<a href="#interval-cartesian-product">interval-cartesian-product</a>.</dd>
<dt>Storage Classes</dt>
<dd><a href="#make-storage-class">make-storage-class</a>,
<a href="#storage-class?">storage-class?</a>,
<a href="#storage-class-getter">storage-class-getter</a>,
<a href="#storage-class-setter">storage-class-setter</a>,
<a href="#storage-class-checker">storage-class-checker</a>,
<a href="#storage-class-maker">storage-class-maker</a>,
<a href="#storage-class-copier">storage-class-copier</a>,
<a href="#storage-class-length">storage-class-length</a>,
<a href="#storage-class-default">storage-class-default</a>,
<a href="#storage-class-data?">storage-class-data?</a>,
<a href="#storage-class-data-rarrow-body">storage-class-data->body</a>,
<a href="#generic-storage-class">generic-storage-class</a>,
<a href="#char-storage-class">char-storage-class</a>,
<a href="#s8-storage-class">s8-storage-class</a>,
<a href="#s16-storage-class">s16-storage-class</a>,
<a href="#s32-storage-class">s32-storage-class</a>,
<a href="#s64-storage-class">s64-storage-class</a>,
<a href="#u1-storage-class">u1-storage-class</a>,
<a href="#u8-storage-class">u8-storage-class</a>,
<a href="#u16-storage-class">u16-storage-class</a>,
<a href="#u32-storage-class">u32-storage-class</a>,
<a href="#u64-storage-class">u64-storage-class</a>,
<a href="#f8-storage-class">f8-storage-class</a>,
<a href="#f16-storage-class">f16-storage-class</a>,
<a href="#f32-storage-class">f32-storage-class</a>,
<a href="#f64-storage-class">f64-storage-class</a>,
<a href="#c64-storage-class">c64-storage-class</a>,
<a href="#c128-storage-class">c128-storage-class</a>.</dd>
<dt>Arrays</dt>
<dd><a href="#specialized-array-default-safe?">specialized-array-default-safe?</a>,
<a href="#specialized-array-default-mutable?">specialized-array-default-mutable?</a>,
<a href="#make-array">make-array</a>,
<a href="#array?">array?</a>,
<a href="#array-domain">array-domain</a>,
<a href="#array-getter">array-getter</a>,
<a href="#array-dimension">array-dimension</a>,
<a href="#mutable-array?">mutable-array?</a>,
<a href="#array-setter">array-setter</a>,
<a href="#array-freeze!">array-freeze!</a>,
<a href="#array-empty?">array-empty?</a>,
<a href="#make-specialized-array">make-specialized-array</a>,
<a href="#make-specialized-array-from-data">make-specialized-array-from-data</a>,
<a href="#specialized-array?">specialized-array?</a>,
<a href="#array-storage-class">array-storage-class</a>,
<a href="#array-indexer">array-indexer</a>,
<a href="#array-body">array-body</a>,
<a href="#array-safe?">array-safe?</a>,
<a href="#array-packed?">array-packed?</a>,
<a href="#specialized-array-share">specialized-array-share</a>,
<a href="#array-copy">array-copy</a>,
<a href="#array-copy!">array-copy!</a>,
<a href="#array-curry">array-curry</a>,
<a href="#array-extract">array-extract</a>,
<a href="#array-tile">array-tile</a>,
<a href="#array-translate">array-translate</a>,
<a href="#array-permute">array-permute</a>,
<a href="#array-reverse">array-reverse</a>,
<a href="#array-sample">array-sample</a>,
<a href="#array-outer-product">array-outer-product</a>,
<a href="#array-inner-product">array-inner-product</a>,
<a href="#array-map">array-map</a>,
<a href="#array-for-each">array-for-each</a>,
<a href="#array-fold-left">array-fold-left</a>,
<a href="#array-fold-right">array-fold-right</a>,
<a href="#array-reduce">array-reduce</a>,
<a href="#array-any">array-any</a>,
<a href="#array-every">array-every</a>,
<a href="#array-rarrow-list">array->list</a>,
<a href="#list-rarrow-array">list->array</a>,
<a href="#array-rarrow-list*">array->list*</a>,
<a href="#list*-rarrow-array">list*->array</a>,
<a href="#array-rarrow-vector">array->vector</a>,
<a href="#vector-rarrow-array">vector->array</a>,
<a href="#vector*-rarrow-array">vector*->array</a>,
<a href="#array-rarrow-vector*">array->vector*</a>,
<a href="#array-assign!">array-assign!</a>,
<a href="#array-stack">array-stack</a>,
<a href="#array-stack!">array-stack!</a>,
<a href="#array-decurry">array-decurry</a>,
<a href="#array-decurry!">array-decurry!</a>,
<a href="#array-append">array-append</a>,
<a href="#array-append!">array-append!</a>,
<a href="#array-block">array-block</a>,
<a href="#array-block!">array-block!</a>,
<a href="#array-ref">array-ref</a>,
<a href="#array-set!">array-set!</a>,
<a href="#specialized-array-reshape">specialized-array-reshape</a>.</dd></dl>
<h2><a id="Preliminary">Preliminary notes</a></h2>
<p>We use <code>take</code> and <code>drop</code> from <a href="https://srfi.schemers.org/srfi-1/srfi-1.html">SRFI 1</a> to define various procedures.</p>
<h2><a id="Miscellaneous">Miscellaneous procedures</a></h2>
<p>This document refers to <i>translations</i> and <i>permutations</i>.
A translation is a vector of exact integers. A permutation of dimension $n$
is a vector whose entries are the exact integers $0,1,\ldots,n-1$, each occurring once, in any order.
We provide four procedures that return useful permutations.</p>
<h3><a id="miscprocedures">Procedures</a></h3>
<p><b>Procedure: </b><code><a id="translation?">translation?</a> <var>object</var></code></p>
<p>Returns <code>#t</code> if <code><var>object</var></code> is a translation, and <code>#f</code> otherwise.</p>
<p><b>Procedure: </b><code><a id="permutation?">permutation?</a> <var>object</var></code></p>
<p>Returns <code>#t</code> if <code><var>object</var></code> is a permutation, and <code>#f</code> otherwise.</p>
<p><b>Procedure: </b><code><a id="index-rotate">index-rotate</a> <var>n</var> <var>k</var></code></p>
<p>Assumes that <var>n</var> is a nonnegative exact integer and that <var>k</var> is an exact integer between 0 and <var>n</var> (inclusive). Returns a permutation that rotates <var>n</var> indices <var>k</var> places to the left:</p>
<pre><code>(define (index-rotate n k)
(let ((identity-permutation (iota n)))
(list->vector (append (drop identity-permutation k)
(take identity-permutation k)))))</code></pre>
<p>For example, <code>(index-rotate 5 3)</code> returns <code>'#(3 4 0 1 2)</code>. It is an error of the arguments do not satisfy these conditions.</p>
<p><b>Procedure: </b><code><a id="index-first">index-first</a> <var>n</var> <var>k</var></code></p>
<p>Assumes that <var>n</var> is a positive exact integer and that <var>k</var> is an exact integer between 0 (inclusive) and <var>n</var> (exclusive). Returns a permutation of length <var>n</var> that moves index <var>k</var> (with count beginning at 0) to be first and leaves the other indices in order:</p>
<pre><code>(define (index-first n k)
(let ((identity-permutation (iota n)))
(list->vector (cons k
(append (take identity-permutation k)
(drop identity-permutation (fx+ k 1)))))))</code></pre>
<p>For example, <code>(index-first 5 3)</code> returns <code>'#(3 0 1 2 4)</code>. It is an error if the arguments do not satisfy these conditions.</p>
<p><b>Procedure: </b><code><a id="index-last">index-last</a> <var>n</var> <var>k</var></code></p>
<p>Assumes that <var>n</var> is a positive exact integer and that <var>k</var> is an exact integer between 0 (inclusive) and <var>n</var> (exclusive). Returns a permutation of length <var>n</var> that moves index <var>k</var> (with count beginning at 0) to be last and leaves the other indices in order:</p>
<pre><code>(define (index-last n k)
(let ((identity-permutation (iota n)))
(list->vector (append (take identity-permutation k)
(drop identity-permutation (fx+ k 1))
(list k)))))</code></pre>
<p>For example, <code>(index-last 5 3)</code> returns <code>'#(0 1 2 4 3)</code>. It is an error if the arguments do not satisfy these conditions.</p>
<p><b>Procedure: </b><code><a id="index-swap">index-swap</a> <var>n</var> <var>i</var> <var>j</var></code></p>
<p>Assumes that <code><var>n</var></code> is a positive exact integer and that <code><var>i</var></code> and <code><var>j</var></code> are exact integers between 0 (inclusive) and <code><var>n</var></code> (exclusive). Returns a permutation of length <code><var>n</var></code> that swaps index <code><var>i</var></code> and index <code><var>j</var></code> and leaves the other indices in order.</p>
<p>For example, <code>(index-swap 5 3 0)</code> returns <code>#(3 1 2 0 4)</code>. It is an error if the arguments do not satisfy these assumptions.</p>
<h2><a id="Intervals">Intervals</a></h2>
<p>An interval represents the set of all multi-indices of exact integers
$i_0,\ldots,i_{d-1}$
satisfying
$l_0\leq i_0<u_0,\ldots,l_{d-1}\leq i_{d-1}<u_{d-1}$,
where the <i>lower bounds</i>
$l_0,\ldots,l_{d-1}$
and the <i>upper bounds</i>
$u_0,\ldots,u_{d-1}$
are exact integers. The nonnegative integer $d$ is the <i>dimension</i>
of the interval.</p>
<p>If $l_k=u_k$ for some $k$ then the interval is <i>empty</i>; if $d=0$ then the interval is <i>zero-dimensional</i>. So rather than mathematical objects, it is perhaps better to think of intervals as pairs of vectors $L$ and $U$ for which $L_k\leq U_k$; $L$ or $U$ could be empty (hence $d=0$).</p>
<p>Intervals are a data type distinct from other Scheme data types.</p>
<h3><a id="intervalprocedures">Procedures</a></h3>
<p><b>Procedure: </b><code><a id="make-interval">make-interval</a> <var>arg1</var> #!optional <var>arg2</var></code></p>
<p>Create a new interval. Assumes that <code><var>arg1</var></code> and <code><var>arg2</var></code> (if given) are vectors (of the same length) of exact integers.</p>
<p>If <code><var>arg2</var></code> is not given, then the entries of <code><var>arg1</var></code>, if any, must be nonnegative, and they are taken as the <code><var>upper-bounds</var></code> of the interval, and <code><var>lower-bounds</var></code> is set to a vector of the same length with exact zero entries.</p>
<p>If <code><var>arg2</var></code> is given, then <code><var>arg1</var></code> is taken to be <code><var>lower-bounds</var></code> and <code><var>arg2</var></code> is taken to be <code><var>upper-bounds</var></code>, which must satisfy</p>
<pre><code>(<= (vector-ref <var>lower-bounds</var> i) (vector-ref <var>upper-bounds</var> i))</code></pre>
<p> for
$0\leq i<{}$<code>(vector-length <var>lower-bounds</var>)</code>. It is an error if
<code><var>lower-bounds</var></code> and <code><var>upper-bounds</var></code> do not satisfy these conditions.</p>
<p><b>Example: </b></p>
<pre><code>(let ((A (make-interval '#(3 4)))
(B (make-interval '#(0 0) '#(3 4))))
(interval= A B)) ;; => #t</code></pre>
<p><b>Procedure: </b><code><a id="interval?">interval?</a> <var>object</var></code></p>
<p>Returns <code>#t</code> if <code><var>object</var></code> is an interval, and <code>#f</code> otherwise.</p>
<p><b>Example: </b></p>
<pre><code>(let ((A (make-interval '#(3 4)))
(B 1))
(interval? A) ;; => #t
(interval? B)) ;; => #f</code></pre>
<p><b>Procedure: </b><code><a id="interval-dimension">interval-dimension</a> <var>interval</var></code></p>
<p>Assumes <code><var>interval</var></code> is an interval; if <code><var>interval</var></code> is built with </p>
<pre><code>(make-interval <var>lower-bounds</var> <var>upper-bounds</var>)</code></pre>
<p>then <code>interval-dimension</code> returns <code>(vector-length <var>lower-bounds</var>)</code>.</p>
<p>It is an error to call <code>interval-dimension</code>
if <code><var>interval</var></code> is not an interval.</p>
<p><b>Example: </b></p>
<pre><code>(let ((A (make-interval '#(3 4)))
(B (make-interval '#())))
(interval-dimension A) ;; => 2
(interval-dimension B)) ;; => 0</code></pre>
<p><b>Procedure: </b><code><a id="interval-lower-bound">interval-lower-bound</a> <var>interval</var> <var>i</var></code></p>
<p><b>Procedure: </b><code><a id="interval-upper-bound">interval-upper-bound</a> <var>interval</var> <var>i</var></code></p>
<p><b>Procedure: </b><code><a id="interval-width">interval-width</a> <var>interval</var> <var>i</var></code></p>
<p>Assumes that <code><var>interval</var></code> is an interval made, e.g., with <code>(make-interval <var>lower-bounds upper-bounds</var>)</code>, and that <code><var>i</var></code> is an exact integer that satisfies</p>
<blockquote>$0 \leq i<$ <code>(interval-dimension <var>interval</var>)</code>.
</blockquote>
<p> Then <code>interval-lower-bound</code> returns
<code>(vector-ref <var>lower-bounds</var> <var>i</var>)</code>, <code>interval-upper-bound</code> returns
<code>(vector-ref <var>upper-bounds</var> <var>i</var>)</code>, and <code>interval-width</code> returns
<code>(- (vector-ref <var>upper-bounds</var> <var>i</var>) (vector-ref <var>lower-bounds</var> <var>i</var>))</code>.</p>
<p>It is an error to call <code>interval-lower-bound</code>, <code>interval-upper-bound</code>, or <code>interval-width</code> if <code><var>interval</var></code> and <code><var>i</var></code> do not satisfy these conditions.</p>
<p><b>Example: </b></p>
<pre><code>(let ((A (make-interval '#(1 0) '#(3 4))))
(interval-lower-bound A 0) ;; => 1
(interval-upper-bound A 0) ;; => 3
(interval-width A 0)) ;; => 2</code></pre>
<p><b>Procedure: </b><code><a id="interval-lower-bounds-rarrow-list">interval-lower-bounds->list</a> <var>interval</var></code></p>
<p><b>Procedure: </b><code><a id="interval-upper-bounds-rarrow-list">interval-upper-bounds->list</a> <var>interval</var></code></p>
<p>Assumes <code><var>interval</var></code> is an interval built, e.g., by </p>
<pre><code>(make-interval <var>lower-bounds</var> <var>upper-bounds</var>)</code></pre>
<p>Then <code>interval-lower-bounds->list</code> returns <code>(vector->list <var>lower-bounds</var>)</code> and <code>interval-upper-bounds->list</code> returns <code>(vector->list <var>upper-bounds</var>)</code>.</p>
<p>It is an error to call
<code>interval-lower-bounds->list</code> or <code>interval-upper-bounds->list</code> if <code><var>interval</var></code> does not satisfy these conditions.</p>
<p><b>Example: </b></p>
<pre><code>(let ((A (make-interval '#(1 0) '#(3 4))))
(interval-lower-bounds->list A) ;; => (1 0)
(interval-upper-bounds->list A)) ;; => (3 4)</code></pre>
<p><b>Procedure: </b><code><a id="interval-lower-bounds-rarrow-vector">interval-lower-bounds->vector</a> <var>interval</var></code></p>
<p><b>Procedure: </b><code><a id="interval-upper-bounds-rarrow-vector">interval-upper-bounds->vector</a> <var>interval</var></code></p>
<p>Assumes <code><var>interval</var></code> is an interval built, e.g., with </p>
<pre><code>(make-interval <var>lower-bounds</var> <var>upper-bounds</var>)</code></pre>
<p>Then <code>interval-lower-bounds->vector</code> returns a copy of <code><var>lower-bounds</var></code> and <code>interval-upper-bounds->vector</code> returns a copy of <code><var>upper-bounds</var></code>.</p>
<p>It is an error to call
<code>interval-lower-bounds->vector</code> or <code>interval-upper-bounds->vector</code> if <code><var>interval</var></code> does not satisfy these conditions.</p>
<p><b>Example: </b></p>
<pre><code>(let ((A (make-interval '#(1 0) '#(3 4))))
(interval-lower-bounds->vector A) ;; => '#(1 0)
(interval-upper-bounds->vector A)) ;; => '#(3 4)</code></pre>
<p><b>Procedure: </b><code><a id="interval-widths">interval-widths</a> <var>interval</var></code></p>
<p>Assumes <code><var>interval</var></code> is an interval built, e.g., with </p>
<pre><code>(make-interval <var>lower-bounds</var> <var>upper-bounds</var>)</code></pre>
<p>Then, assuming the existence of <code>vector-map</code>, <code>interval-widths</code> returns </p>
<pre><code>(vector-map - <var>upper-bounds</var> <var>lower-bounds</var>)</code></pre>
<p>It is an error to call <code>interval-widths</code> if <code><var>interval</var></code> does not satisfy this condition.</p>
<p><b>Example: </b></p>
<pre><code>(let ((A (make-interval '#(1 0) '#(3 4))))
(interval-widths A)) ;; => '#(2 4)</code></pre>
<p><b>Procedure: </b><code><a id="interval-volume">interval-volume</a> <var>interval</var></code></p>
<p>Assumes <code><var>interval</var></code> is an interval built, e.g., with </p>
<pre><code>(make-interval <var>lower-bounds</var> <var>upper-bounds</var>)</code></pre>
<p>Then, assuming the existence of <code>vector-map</code>, <code>interval-volume</code> returns </p>
<pre><code>(apply * (vector->list (vector-map - <var>upper-bounds</var> <var>lower-bounds</var>)))</code></pre>
<p>It is an error to call <code>interval-volume</code> if <code><var>interval</var></code> does not satisfy this condition.</p>
<p><b>Example: </b></p>
<pre><code>(let ((A (make-interval '#(1 0) '#(3 4)))
(B (make-interval '#())))
(interval-volume A) ;; => 8
(interval-volume B)) ;; => 1</code></pre>
<p><b>Procedure: </b><code><a id="interval-empty?">interval-empty?</a> <var>interval</var></code></p>
<p>Assumes <code><var>interval</var></code> is an interval; returns <code>(eqv? 0 (interval-volume <var>interval</var>))</code>.</p>
<p>It is an error to call <code>interval-empty?</code> if <code><var>interval</var></code> does not satisfy this condition.</p>
<p><b>Example: </b></p>
<pre><code>(let ((A (make-interval '#(1 0) '#(3 4)))
(B (make-interval '#()))
(C (make-interval '#(1 0) '#(1 4))))
(interval-empty? A) ;; => #f
(interval-empty? B) ;; => #f
(interval-empty? C)) ;; => #t</code></pre>
<p><b>Procedure: </b><code><a id="interval=">interval=</a> <var>interval1</var> <var>interval2</var></code></p>
<p>Assumes that <code><var>interval1</var></code> and <code><var>interval2</var></code> are intervals built, e.g., with </p>
<pre><code>(make-interval <var>lower-bounds1</var> <var>upper-bounds1</var>)</code></pre>
<p>and</p>
<pre><code>(make-interval <var>lower-bounds2</var> <var>upper-bounds2</var>)</code></pre>
<p>respectively. Then <code>interval=</code> returns</p>
<pre><code>(and (equal? <var>lower-bounds1</var> <var>lower-bounds2</var>) (equal? <var>upper-bounds1</var> <var>upper-bounds2</var>))</code></pre>
<p>It is an error to call <code>interval=</code> if <code><var>interval1</var></code> or <code><var>interval2</var></code> do not satisfy this condition.</p>
<p><b>Example: </b></p>
<pre><code>(let ((A (make-interval '#(1)))
(B (make-interval '#(1 1)))
(C (make-interval '#(0) '#(1)))
(D (make-interval '#(0 0)))
(E (make-interval '#(0))))
(interval= A B) ;; => #f
(interval= A C) ;; => #t
(interval= D E)) ;; => #f</code></pre>
<p><b>Procedure: </b><code><a id="interval-subset?">interval-subset?</a> <var>interval1</var> <var>interval2</var></code></p>
<p>Assumes that <code><var>interval1</var></code> and <code><var>interval2</var></code> are intervals of the same dimension $d$. Then <code>interval-subset?</code> returns <code>#t</code> if </p>
<pre><code>(>= (interval-lower-bound <var>interval1</var> j) (interval-lower-bound <var>interval2</var> j))</code></pre>
<p>and</p>
<pre><code>(<= (interval-upper-bound <var>interval1</var> j) (interval-upper-bound <var>interval2</var> j))</code></pre>
<p>for all $0\leq j<d$. Otherwise, it returns <code>#f</code>. It is an error if the arguments do not satisfy these conditions.</p>
<p><b>Example: </b></p>
<pre><code>(let ((A (make-interval '#(2 3)))
(B (make-interval '#(1 1)))
(C (make-interval '#(3 1) '#(3 3))))
(interval-subset? A B) ;; => #f
(interval-subset? B A) ;; => #t
(interval-subset? C A)) ;; => #f</code></pre>
<p><b>Procedure: </b><code><a id="interval-contains-multi-index?">interval-contains-multi-index?</a> <var>interval</var> . <var>multi-index</var></code></p>
<p>Assumes that <code><var>interval</var></code> is an interval with dimension $d$ and <code><var>multi-index</var></code> is a multi-index (a sequence of exact integers) of length $d$. Then <code>interval-contains-multi-index?</code> returns <code>(every <= (interval-lower-bounds->list <var>interval</var>) <var>multi-index</var> (interval-upper-bounds->list <var>interval</var>))</code>.</p>
<p>It is an error to call <code>interval-contains-multi-index?</code> if <code><var>interval</var></code> and <code><var>multi-index</var></code> do not satisfy this condition.</p>
<p><b>Example: </b></p>
<pre><code>(let ((A (make-interval '#(1 0) '#(4 5))))
(interval-contains-multi-index? A 2 1) ;; => #t
(interval-contains-multi-index? A 0 3)) ;; => #f</code></pre>
<p><b>Procedure: </b><code><a id="interval-projections">interval-projections</a> <var>interval</var> <var>right-dimension</var></code></p>
<p>Conceptually, <code>interval-projections</code> takes a $d$-dimensional interval
$[l_0,u_0)\times [l_1,u_1)\times\cdots\times[l_{d-1},u_{d-1})$
and splits it into two parts</p>
<blockquote>$[l_0,u_0)\times\cdots\times[l_{d-\text{right-dimension}-1},u_{d-\text{right-dimension}-1})$
</blockquote>
<p>and</p>
<blockquote>$[l_{d-\text{right-dimension}},u_{d-\text{right-dimension}})\times\cdots\times[l_{d-1},u_{d-1})$
</blockquote>
<p>This procedure, the inverse of Cartesian products or cross products of intervals, is used to keep track of the domains of curried arrays.</p>
<p>More precisely, this procedure assumes that <code><var>interval</var></code> is an interval and <code><var>right-dimension</var></code> is an exact integer that satisfies <code>0 <= <var>right-dimension</var> <= <var>d</var></code>, in which case <code>interval-projections</code> returns two intervals:</p>
<pre><code>(let ((left-dimension
(- (interval-dimension interval right-dimension)))
(lowers
(interval-lower-bounds->list interval))
(uppers
(interval-upper-bounds->list interval)))
(values
(make-interval
(list->vector (take lowers left-dimension))
(list->vector (take uppers left-dimension)))
(make-interval
(list->vector (drop lowers left-dimension))
(list->vector (drop uppers left-dimension)))))</code></pre>
<p>It is an error to call <code>interval-projections</code> if its arguments do not satisfy these conditions.</p>
<p><b>Example: </b></p>
<pre><code>(let ((A (make-interval '#(2 3 1 5 4))))
(call-with-values
(lambda ()
(interval-projections A 2))
(lambda (left right)
(interval= (make-interval '#(2 3 1)) left) ;; => #t
(interval= (make-interval '#(5 4)) right)))) ;; => #t</code></pre>
<p><b>Procedure: </b><code><a id="interval-for-each">interval-for-each</a> <var>f</var> <var>interval</var></code></p>
<p>This procedure assumes that <code><var>interval</var></code> is an interval and <code><var>f</var></code> is a procedure whose domain includes elements of <code><var>interval</var></code>. It is an error to call <code>interval-for-each</code> if <code><var>interval</var></code> and <code><var>f</var></code> do not satisfy these conditions.</p>
<p><code>interval-for-each</code> calls <code><var>f</var></code> with each multi-index of <code><var>interval</var></code> as arguments, all in lexicographical order.</p>
<p>In particular, if <code><var>interval</var></code> is zero-dimensional, <code><var>f</var></code> is called as a thunk; if the interval is empty, then <code><var>f</var></code> is never called.</p>
<p><b>Example: </b></p>
<pre><code>(let ((A (make-interval '#(3 2))))
(interval-for-each (lambda (i j)
(display i) (display #\space)
(display j) (display #\space)
(display "=> ")
(display (and (even? i)
(even? j)))
(newline))
A))</code></pre>
<p>Displays:</p>
<pre><code>0 0 => #t
0 1 => #f
1 0 => #f
1 1 => #f
2 0 => #t
2 1 => #f</code></pre>
<p><b>Procedure: </b><code><a id="interval-fold-left">interval-fold-left</a> <var>f</var> <var>operator</var> <var>identity</var> <var>interval</var></code></p>
<p><b>Procedure: </b><code><a id="interval-fold-right">interval-fold-right</a> <var>f</var> <var>operator</var> <var>identity</var> <var>interval</var></code></p>
<p>These procedures assume that <code><var>f</var></code> is a procedure whose domain includes elements of <code><var>interval</var></code>, that <code><var>operator</var></code> is a procedure of two arguments, and that <code><var>interval</var></code> is an interval.</p>
<p>If <code><var>interval</var></code> is empty, these procedures return <code><var>identity</var></code>. If <code><var>interval</var></code> is zero-dimensional, then <code>interval-fold-left</code> returns <code>(<var>operator</var> <var>identity</var> (<var>f</var>))</code> and <code>interval-fold-right</code> returns <code>(<var>operator</var> (<var>f</var>) <var>identity</var>)</code>.</p>
<p>Otherwise, assume that there is a procedure <code>(next-multi-index multi-index interval)</code> which, given an interval and a list representing a multi-index in that interval, returns either a list representing the next valid multi-index in the interval or <code>#f</code> if no such multi-index exists.</p>
<p>Then these procedures can be defined as</p>
<pre><code>(define (interval-fold-left f operator identity interval)
(cond ((interval-empty? interval)
identity)
((zero? (interval-dimension interval))
(operator identity (f)))
(else
(let loop ((result identity)
(multi-index (interval-lower-bounds->list interval)))
(let* ((item (apply f multi-index))
(new-result (operator result item))
(next (next-multi-index multi-index interval)))
(if next
(loop new-result next)
new-result))))))
(define (interval-fold-right f operator identity interval)
(cond ((interval-empty? interval)
identity)
((zero? (interval-dimension interval))
(operator (f) identity))
(else
(let loop ((multi-index (interval-lower-bounds->list interval)))
(if multi-index
(let* ((item (apply f multi-index))
(tail-result (loop (next-multi-index multi-index interval))))
(operator item tail-result))
identity)))))</code></pre>
<p>Note that <code>interval-fold-left</code> alternates evaluations of <code><var>f</var></code> and <code><var>operator</var></code>, while <code>interval-fold-right</code> evaluates <code><var>f</var></code> at all multi-indices before applying <code><var>operator</var></code> to any arguments.</p>
<p>It is an error if the arguments do not satisfy these assumptions.</p>
<p><b>Example: </b>One can compute the <a href="https://en.wikipedia.org/w/index.php?title=Sieve_of_Eratosthenes&oldid=1101704798">Sieve of Eratosthenes</a> with </p>
<pre><code>(define (eratosthenes n)
;; Compute all primes <= n
(let* ((sqrt-n (exact (floor (sqrt n))))
(A (make-specialized-array (make-interval '#(2)
(vector (+ n 1)))
u1-storage-class
1))
(A_ (array-getter A))
(A! (array-setter A)))
(do ((i 2 (+ i 1)))
((> i sqrt-n)
(interval-fold-right identity
(lambda (i result)
(if (eqv? (A_ i) 1)
(cons i result)
result))
'()
(array-domain A)))
(if (eqv? (A_ i) 1)
(do ((j (square i) (+ j i)))
((> j n))
(A! 0 j))))))
(length (eratosthenes 1000000)) => 78498</code></pre>
<p><b>Procedure: </b><code><a id="interval-dilate">interval-dilate</a> <var>interval</var> <var>lower-diffs</var> <var>upper-diffs</var></code></p>
<p>Assumes that <code><var>interval</var></code> is an interval with
lower bounds $\ell_0,\dots,\ell_{d-1}$ and
upper bounds $u_0,\dots,u_{d-1}$, and <code><var>lower-diffs</var></code> is a vector of exact integers $L_0,\dots,L_{d-1}$ and <code><var>upper-diffs</var></code> is a vector of exact integers $U_0,\dots,U_{d-1}$. Then <code>interval-dilate</code> returns a new interval with
lower bounds $\ell_0+L_0,\dots,\ell_{d-1}+L_{d-1}$ and
upper bounds $u_0+U_0,\dots,u_{d-1}+U_{d-1}$, as long as this is a
valid interval. It is an error if the arguments do not satisfy these conditions.</p>
<p><b>Examples:</b></p>
<pre><code>(interval=
(interval-dilate (make-interval '#(100 100))
'#(1 1) '#(1 1))
(make-interval '#(1 1) '#(101 101))) => #t
(interval=
(interval-dilate (make-interval '#(100 100))
'#(-1 -1) '#(1 1))
(make-interval '#(-1 -1) '#(101 101))) => #t
(interval=
(interval-dilate (make-interval '#(100 100))
'#(0 0) '#(-50 -50))
(make-interval '#(50 50))) => #t
(interval-dilate
(make-interval '#(100 100))
'#(0 0) '#(-500 -50)) => error</code></pre>
<p><b>Procedure: </b><code><a id="interval-intersect">interval-intersect</a> <var>interval</var> . <var>intervals</var></code></p>
<p>Assumes that all the arguments are intervals of the same dimension. If they have a valid intersection,
then <code>interval-intersect</code> returns that intersection; otherwise it returns <code>#f</code>.</p>
<p>More precisely, <code>interval-intersect</code> calculates</p>
<pre><code>(let* ((intervals (cons interval intervals))
(lower-bounds (apply vector-map max (map interval-lower-bounds intervals)))
(upper-bounds (apply vector-map min (map interval-upper-bounds intervals))))
(and (vector-every (lambda (x y) (<= x y)) lower-bounds upper-bounds)
(make-interval lower-bounds upper-bounds)))</code></pre>
<p>It is an error if the arguments are not all intervals with the same dimension.</p>
<p><b>Example: </b></p>
<pre><code>(let ((A (make-interval '#(2 5) '#(10 7)))
(B (make-interval '#(0 6) '#(8 11)))
(C (make-interval '#(2 6) '#(8 7)))
(D (make-interval '#(1 1))))
(interval= (interval-intersect A B) C) ;; => #t
(interval-intersect A D)) ;; => #f</code></pre>
<p><b>Procedure: </b><code><a id="interval-translate">interval-translate</a> <var>interval</var> <var>translation</var></code></p>
<p>Assumes that <code><var>interval</var></code> is an interval, with, e.g.,
lower bounds $\ell_0,\dots,\ell_{d-1}$ and
upper bounds $u_0,\dots,u_{d-1}$, and <code><var>translation</var></code> is a translation with entries $T_0,\dots,T_{d-1}$.
Then <code>interval-translate</code> returns a new interval with
lower bounds $\ell_0+T_0,\dots,\ell_{d-1}+T_{d-1}$ and
upper bounds $u_0+T_0,\dots,u_{d-1}+T_{d-1}$.
It is an error if the arguments do not satisfy these conditions.</p>
<p>One could define <code>(interval-translate interval translation)</code> by <code>(interval-dilate interval translation translation)</code>.</p>
<p><b>Example: </b></p>
<pre><code>(let ((A (make-interval '#(2 5) '#(10 7)))
(B (make-interval '#(1 6) '#(9 8))))
(interval= (interval-translate A '#(-1 1)) B)) ;; => #t</code></pre>
<p><b>Procedure: </b><code><a id="interval-permute">interval-permute</a> <var>interval</var> <var>permutation</var></code></p>
<p>Assumes that <code><var>interval</var></code> is an interval and <code><var>permutation</var></code> is a permutation with the same dimension as <code><var>interval</var></code>. It is an error if the arguments do not satisfy these conditions.</p>
<p>Heuristically, this procedure returns a new interval whose axes have been permuted in a way consistent with <code><var>permutation</var></code>.
But we have to say how the entries of <code><var>permutation</var></code> are associated with the new interval.</p>
<p>We have chosen the following convention: If the permutation is $(\pi_0,\ldots,\pi_{d-1})$, and the argument interval
represents the cross product
$[l_0,u_0)\times[l_1,u_1)\times\cdots\times[l_{d-1},u_{d-1})$,
then the result represents the cross product
$[l_{\pi_0},u_{\pi_0})\times[l_{\pi_1},u_{\pi_1})\times\cdots\times[l_{\pi_{d-1}},u_{\pi_{d-1}})$.</p>
<p>For example, if the argument interval represents $[0,4)\times[0,8)\times[0,21)\times [0,16)$ and the
permutation is <code>#(3 0 1 2)</code>, then the result of <code>(interval-permute <var>interval</var> <var>permutation</var>)</code> will be
the representation of $[0,16)\times [0,4)\times[0,8)\times[0,21)$.</p>
<p><b>Example: </b></p>
<pre><code>(let ((A (make-interval '#(4 8 21 16)))
(B (make-interval '#(16 4 8 21))))
(interval= (interval-permute A '#(3 0 1 2)) B)) ;; => #t</code></pre>
<p><b>Procedure: </b><code><a id="interval-scale">interval-scale</a> <var>interval</var> <var>scales</var></code></p>
<p>Assumes that <code><var>interval</var></code> is a $d$-dimensional interval $[0,u_1)\times\cdots\times[0,u_{d-1})$ with all lower bounds zero, and <code><var>scales</var></code> is a length-$d$ vector of positive exact integers, which we'll denote by $\vec s$. Then <code>interval-scale</code> returns the interval $[0,\operatorname{ceiling}(u_1/s_1))\times\cdots\times[0,\operatorname{ceiling}(u_{d-1}/s_{d-1}))$.</p>
<p>It is an error if <code><var>interval</var></code> and <code><var>scales</var></code> do not satisfy these conditions.</p>
<p><b>Example: </b></p>
<pre><code>(let ((A (make-interval '#(4 7)))
(B (make-interval '#(2 4))))
(interval= (interval-scale A '#(3 2)) B)) ;; => #t</code></pre>
<p><b>Procedure: </b><code><a id="interval-cartesian-product">interval-cartesian-product</a> . <var>intervals</var></code></p>
<p>Assumes that all the arguments are intervals. Implements the Cartesian product of the intervals in <code><var>intervals</var></code>. Returns:</p>
<pre><code>(make-interval
(list->vector
(apply append (map interval-lower-bounds->list intervals)))
(list->vector
(apply append (map interval-upper-bounds->list intervals))))</code></pre>
<p>It is an error if any argument is not an interval.</p>
<p><b>Example: </b></p>
<pre><code>(let ((A (make-interval '#(3 4)))
(B (make-interval '#(1 2 3) '#(7 8 9)))
(C (make-interval '#(0 0 1 2 3) '#(3 4 7 8 9))))
(interval= (interval-cartesian-product A B) C)) ;; => #t</code></pre>
<h2><a id="Storage">Storage classes</a></h2>
<p>Conceptually, a storage-class is a set of procedures to manage the backing store of a specialized array.
The procedures allow one to make a backing store, to get values from the store, to set new values, to return the length of the store, to specify a default value for initial elements of the backing store, to recognize which data can be converted to a backing store of this storage class, and to convert data to a backing store of this storage class. Typically, a backing store is a (heterogeneous or homogeneous) vector. A storage-class has a type distinct from other Scheme types.</p>
<h3><a id="storageprocedures">Procedures</a></h3>
<p><b>Procedure: </b><code><a id="make-storage-class">make-storage-class</a> <var>getter</var> <var>setter</var> <var>checker</var> <var>maker</var> <var>copier</var> <var>length</var> <var>default</var> <var>data?</var> <var>data->body</var></code></p>
<p>Here we assume the following relationships between the arguments of <code>make-storage-class</code>. Assume that the "elements" of
the backing store are of some "type", either heterogeneous (all Scheme types) or homogeneous (of some restricted type).</p>
<ul>
<li><code>(<var>maker n</var> <var>value</var>)</code> returns a linearly addressed object containing <code><var>n</var></code> elements of value <code><var>value</var></code>.</li>
<li><var>copier</var> may be #f or a procedure; if a procedure then if <code><var>to</var></code> and <code><var>from</var></code> were created by <code><var>maker</var></code>, then <code>(<var>copier to at from start end</var>)</code> copies elements from <code><var>from</var></code> beginning at <code><var>start</var></code> (inclusive) and ending at <code><var>end</var></code> (exclusive) to <code><var>to</var></code> beginning at <code><var>at</var></code>. It is assumed that all the indices involved are within the domain of <code><var>from</var></code> and <code><var>to</var></code>, as needed. The order in which the elements are copied is unspecified.</li>
<li>If <code><var>v</var></code> is an object created by <code>(<var>maker n value</var>)</code> and 0 <= <code><var>i</var></code> < <code><var>n</var></code>, then <code>(<var>getter v i</var>)</code> returns the current value of the <code><var>i</var></code>'th element of <code><var>v</var></code>, and <code>(<var>checker</var> (<var>getter v i</var>)) => #t</code>.</li>
<li>If <code><var>v</var></code> is an object created by <code>(<var>maker n value</var>)</code>, 0 <= <code><var>i</var></code> < <code><var>n</var></code>, and <code>(<var>checker</var> <var>val</var>) => #t</code>, then <code>(<var>setter v i val</var>)</code> sets the value of the <code><var>i</var></code>'th element of <code><var>v</var></code> to <code><var>val</var></code>.</li>
<li>If <code><var>v</var></code> is an object created by <code>(<var>maker n value</var>)</code> then <code>(<var>length v</var>)</code> returns <code><var>n</var></code>.</li>
<li>The <code><var>data?</var></code> and <code><var>data->body</var></code> entries are low-level procedures. <code>((storage-class-data? <var>storage-class</var>) <var>data</var>)</code> returns <code>#t</code> if and only if <code>((storage-class-data->body <var>storage-class</var>) <var>data</var>)</code> returns a body sharing data with <code><var>data</var></code>, without copying. See the discussion of <code>make-specialized-array-from-data</code>.</li>
</ul>
<p>If the arguments do not satisfy these conditions, then it is an error to call <code>make-storage-class</code>.</p>
<p>Note that we assume that <code><var>getter</var></code> and <code><var>setter</var></code> generally take <i>O</i>(1) time to execute.</p>
<p><b>Procedure: </b><code><a id="storage-class?">storage-class?</a> <var>m</var></code></p>
<p>Returns <code>#t</code> if <code><var>m</var></code> is a storage class, and <code>#f</code> otherwise.</p>
<p><b>Procedure: </b><code><a id="storage-class-getter">storage-class-getter</a> <var>m</var></code></p>
<p><b>Procedure: </b><code><a id="storage-class-setter">storage-class-setter</a> <var>m</var></code></p>
<p><b>Procedure: </b><code><a id="storage-class-checker">storage-class-checker</a> <var>m</var></code></p>
<p><b>Procedure: </b><code><a id="storage-class-maker">storage-class-maker</a> <var>m</var></code></p>
<p><b>Procedure: </b><code><a id="storage-class-copier">storage-class-copier</a> <var>m</var></code></p>
<p><b>Procedure: </b><code><a id="storage-class-length">storage-class-length</a> <var>m</var></code></p>
<p><b>Procedure: </b><code><a id="storage-class-default">storage-class-default</a> <var>m</var></code></p>
<p><b>Procedure: </b><code><a id="storage-class-data?">storage-class-data?</a> <var>m</var></code></p>
<p><b>Procedure: </b><code><a id="storage-class-data-rarrow-body">storage-class-data->body</a> <var>m</var></code></p>
<p>Assumes that <code><var>m</var></code> is a storage class, created, e.g., by</p>
<blockquote><code>(make-storage-class <var>getter setter checker maker copier length default data? data->body</var>)</code>
</blockquote>
<p>Then <code>storage-class-getter</code> returns <code><var>getter</var></code>, <code>storage-class-setter</code> returns <code><var>setter</var></code>, <code>storage-class-checker</code> returns <code><var>checker</var></code>, <code>storage-class-maker</code> returns <code><var>maker</var></code>, <code>storage-class-copier</code> returns <code><var>copier</var></code>, <code>storage-class-length</code> returns <code><var>length</var></code>, <code>storage-class-default</code> returns <code><var>default</var></code>, <code>storage-class-data?</code> returns <code><var>data?</var></code>, and <code>storage-class-data->body</code> returns <code><var>data->body</var></code>. Otherwise, it is an error to call any of these procedures.</p>
<h3><a id="storageglobals">Global variables</a></h3>
<p><b>Variable: </b><code><a id="generic-storage-class">generic-storage-class</a></code></p>
<p><b>Variable: </b><code><a id="char-storage-class">char-storage-class</a></code></p>
<p><b>Variable: </b><code><a id="s8-storage-class">s8-storage-class</a></code></p>
<p><b>Variable: </b><code><a id="s16-storage-class">s16-storage-class</a></code></p>
<p><b>Variable: </b><code><a id="s32-storage-class">s32-storage-class</a></code></p>
<p><b>Variable: </b><code><a id="s64-storage-class">s64-storage-class</a></code></p>
<p><b>Variable: </b><code><a id="u1-storage-class">u1-storage-class</a></code></p>
<p><b>Variable: </b><code><a id="u8-storage-class">u8-storage-class</a></code></p>
<p><b>Variable: </b><code><a id="u16-storage-class">u16-storage-class</a></code></p>
<p><b>Variable: </b><code><a id="u32-storage-class">u32-storage-class</a></code></p>
<p><b>Variable: </b><code><a id="u64-storage-class">u64-storage-class</a></code></p>
<p><b>Variable: </b><code><a id="f8-storage-class">f8-storage-class</a></code></p>
<p><b>Variable: </b><code><a id="f16-storage-class">f16-storage-class</a></code></p>
<p><b>Variable: </b><code><a id="f32-storage-class">f32-storage-class</a></code></p>
<p><b>Variable: </b><code><a id="f64-storage-class">f64-storage-class</a></code></p>
<p><b>Variable: </b><code><a id="c64-storage-class">c64-storage-class</a></code></p>
<p><b>Variable: </b><code><a id="c128-storage-class">c128-storage-class</a></code></p>
<p><code>generic-storage-class</code> is defined as if by</p>
<pre><code>(define generic-storage-class
(make-storage-class vector-ref
vector-set!
(lambda (arg) #t)
make-vector
vector-copy!
vector-length
#f
vector?
values))</code></pre>
<p>In the sample implementation <code>char-storage-class</code> is defined as</p>
<pre><code>(define char-storage-class
(make-storage-class string-ref
string-set!
char?
make-string
string-copy!
string-length
#\0
string?
values))</code></pre>
<p>Implementations shall define <code>s<var>X</var>-storage-class</code> for <code><var>X</var></code>=8, 16, 32, and 64 (which have default values 0 and
manipulate exact integer values between -2<sup><var>X</var>-1</sup> and
2<sup><var>X</var>-1</sup>-1 inclusive),
<code>u<var>X</var>-storage-class</code> for <code><var>X</var></code>=1, 8, 16, 32, and 64 (which have default values 0 and manipulate exact integer values between 0 and
2<sup><var>X</var></sup>-1 inclusive),
<code>f<var>X</var>-storage-class</code> for <code><var>X</var></code>= 8, 16, 32, and 64 (which have default value 0.0 and manipulate 8-, 16-, 32-, and 64-bit floating-point numbers), and
<code>c<var>X</var>-storage-class</code> for <code><var>X</var></code>= 64 and 128 (which have default value 0.0+0.0i and manipulate complex numbers with, respectively, 32- and 64-bit floating-point numbers as real and imaginary parts).</p>
<p>Implementations with an appropriate homogeneous vector type should define the associated global variable using <code>make-storage-class</code>. Otherwise, they shall define the associated global variable to <code>#f</code>.</p>
<h2><a id="Arrays">Arrays</a></h2>
<p>Arrays are a data type distinct from other Scheme data types.</p>
<p>In the examples we use a procedure <code>array-unveil</code> that lists the multi-indices and elements of an array in lexicographical order: </p>
<pre><code>(define (array-unveil A)
(let ((D_A (array-domain A))
(A_ (array-getter A)))
(interval-for-each (lambda args
(for-each (lambda (arg)
(display #\space) (display arg))
args)
(for-each display
(list " => " (apply A_ args) #\newline)))
D_A)))</code></pre>
<p>For example:</p>
<pre><code>(let ((A (make-array (make-interval '#(2 3 2)) list)))
(array-unveil A))</code></pre>
<p>displays:</p>
<pre><code> 0 0 0 => (0 0 0)
0 0 1 => (0 0 1)
0 1 0 => (0 1 0)
0 1 1 => (0 1 1)
0 2 0 => (0 2 0)
0 2 1 => (0 2 1)
1 0 0 => (1 0 0)
1 0 1 => (1 0 1)
1 1 0 => (1 1 0)
1 1 1 => (1 1 1)
1 2 0 => (1 2 0)
1 2 1 => (1 2 1)</code></pre>
<h3><a id="parameters">Parameters</a></h3>
<p><b>Parameter: </b><code><a id="specialized-array-default-safe?">specialized-array-default-safe?</a></code></p>
<p>A parameter as specified in <a href="https://srfi.schemers.org/srfi-39/">SRFI 39</a>. Initially, <code>(specialized-array-default-safe?)</code> returns <code>#f</code>. It is an error to call <code>(specialized-array-default-safe? <var>arg</var>)</code> if <code><var>arg</var></code> is not a boolean.</p>
<p><b>Parameter: </b><code><a id="specialized-array-default-mutable?">specialized-array-default-mutable?</a></code></p>
<p>A parameter as specified in <a href="https://srfi.schemers.org/srfi-39/">SRFI 39</a>. Initially, <code>(specialized-array-default-mutable?)</code> returns <code>#t</code>. It is an error to call <code>(specialized-array-default-mutable? <var>arg</var>)</code> if <code><var>arg</var></code> is not a boolean.</p>
<h3><a id="arrayprocedures">Procedures</a></h3>
<p><b>Procedure: </b><code><a id="make-array">make-array</a> <var>interval</var> <var>getter</var> [ <var>setter</var> ]</code></p>
<p>Assume first that the optional argument <code>setter</code> is not given.</p>
<p>If <code><var>interval</var></code> is an interval and <code><var>getter</var></code> is a procedure from
<code><var>interval</var></code> to Scheme objects, then <code>make-array</code> returns an array with domain <code><var>interval</var></code>
and getter <code><var>getter</var></code>.</p>
<p>It is an error to call <code>make-array</code> if <code><var>interval</var></code> and <code><var>getter</var></code>
do not satisfy these conditions.</p>
<p>If now <code><var>setter</var></code> is specified, assume that it is a procedure such that getter and setter satisfy: If</p>
<blockquote><code>(<var>i</var><sub>1</sub>,...,<var>i</var><sub>n</sub>)</code> $\neq$ <code>(<var>j</var><sub>1</sub>,...,<var>j</var><sub>n</sub>)</code>
</blockquote>
<p>are elements of <code><var>interval</var></code> and </p>
<blockquote><code>(getter <var>j</var><sub>1</sub> ... <var>j</var><sub>n</sub>) => x</code>
</blockquote>
<p>then "after"</p>
<blockquote><code>(setter v <var>i</var><sub>1</sub> ... <var>i</var><sub>n</sub>)</code>
</blockquote>
<p>we have</p>
<blockquote><code>(getter <var>j</var><sub>1</sub> ... <var>j</var><sub>n</sub>) => x</code>
</blockquote>
<p>and</p>
<blockquote><code>(getter <var>i</var><sub>1</sub>,...,<var>i</var><sub>n</sub>) => v</code>
</blockquote>
<p>Then <code>make-array</code> builds a mutable array with domain <code><var>interval</var></code>, getter <code><var>getter</var></code>, and
setter <code><var>setter</var></code>. It is an error to call <code>make-array</code> if its arguments do not satisfy these conditions.</p>
<p><b>Example: </b></p>
<pre><code> (define a (make-array (make-interval '#(1 1) '#(11 11))
(lambda (i j)
(if (= i j)
1
0))))</code></pre>
<p>defines an array for which <code>(array-getter a)</code> returns 1 when i=j and 0 otherwise.</p>
<p><b>Example: </b></p>
<pre><code>(define a ;; a sparse array
(let ((domain
(make-interval '#(1000000 1000000)))
(sparse-rows
(make-vector 1000000 '())))
(make-array
domain
(lambda (i j)
(cond ((assv j (vector-ref sparse-rows i))
=> cdr)
(else
0.0)))
(lambda (v i j)
(cond ((assv j (vector-ref sparse-rows i))
=> (lambda (pair)
(set-cdr! pair v)))
(else
(vector-set!
sparse-rows
i
(cons (cons j v)
(vector-ref sparse-rows i)))))))))
(define a_ (array-getter a))
(define a! (array-setter a))
(a_ 12345 6789) => 0.
(a_ 0 0) => 0.
(a! 1.0 0 0) => undefined
(a_ 12345 6789) => 0.
(a_ 0 0) => 1.</code></pre>
<p><b>Example: </b> If an array <code>A</code> is empty, e.g., <code>(make-array (make-interval '#(0 0)) getter setter)</code>, then it is an error to call <code>getter</code> or <code>setter</code>. Still, such arrays can usefully exist to simplify limit cases of some algorithms.</p>
<p><b>Example: </b><code>(define a (make-array (make-interval '#()) (lambda () 42)))</code> makes an array with a zero-dimensional domain whose getter takes no arguments and always returns 42.</p>
<p><b>Example: </b>We can have the following interactive session, which builds a zero-dimensional mutable array: </p>
<pre><code>> (define a
(let ((contents (box 42)))
(make-array
(make-interval '#())
(lambda ()
(unbox contents))
(lambda (val)
(set-box! contents val)))))
> (define a_ (array-getter a))
> (define a! (array-setter a))
> (a_)
42
> (a! 23)
> (a_)
23</code></pre>
<p><b>Procedure: </b><code><a id="array?">array?</a> <var>object</var></code></p>
<p>Returns <code>#t</code> if <code><var>object</var></code> is an array and <code>#f</code> otherwise.</p>
<p><b>Procedure: </b><code><a id="array-domain">array-domain</a> <var>array</var></code></p>
<p><b>Procedure: </b><code><a id="array-getter">array-getter</a> <var>array</var></code></p>
<p>Assumes that <code><var>array</var></code> is an array built, e.g., by</p>
<pre><code>(make-array <var>interval</var> <var>getter</var> [<var>setter</var>])</code></pre>
<p>(with or without the optional <code><var>setter</var></code> argument). Then <code>array-domain</code> returns <code><var>interval</var></code> and <code>array-getter</code> returns <code><var>getter</var></code>.
It is an error to call <code>array-domain</code> or <code>array-getter</code> if <code><var>array</var></code> is not an array.</p>
<p><b>Example: </b></p>
<pre><code>(define a (make-array (make-interval '#(1 1) '#(11 11))
(lambda (i j)
(if (= i j)
1
0))))
(define a_ (array-getter a))
(a_ 3 3) => 1
(a_ 2 3) => 0
(a_ 11 0) => is an error</code></pre>
<p><b>Procedure: </b><code><a id="array-dimension">array-dimension</a> <var>array</var></code></p>
<p>Shorthand for <code>(interval-dimension (array-domain <var>array</var>))</code>. It is an error to call this procedure if <code><var>array</var></code> is not an array.</p>
<p><b>Example: </b></p>
<pre><code>(let ((A (make-array (make-interval '#(3 3)) list))
(B (make-array (make-interval '#()) (lambda () 42))))
(array-dimension A) ;; => 2
(array-dimension B)) ;; => 0</code></pre>
<p><b>Procedure: </b><code><a id="mutable-array?">mutable-array?</a> <var>object</var></code></p>
<p>Returns <code>#t</code> if <code><var>object</var></code> is a mutable array and <code>#f</code> otherwise.</p>
<p><b>Example: </b></p>
<pre><code>(let ((A (array-copy (make-array (make-interval '#(2 2)) list)
generic-storage-class
#t))
(B (array-copy (make-array (make-interval '#(2 2)) list)
generic-storage-class
#f)))
(mutable-array? A) ;; => #t
(mutable-array? B)) ;; => #f</code></pre>
<p><b>Procedure: </b><code><a id="array-setter">array-setter</a> <var>array</var></code></p>
<p>If <code><var>array</var></code> is an array built by</p>
<pre><code>(make-array <var>interval</var> <var>getter</var> <var>setter</var>)</code></pre>
<p>then <code>array-setter</code> returns <code><var>setter</var></code>. Other procedures can build mutable arrays, e.g., <code>array-copy</code>. It is an error to call <code>array-setter</code>
if <code><var>array</var></code> is not a mutable array.</p>
<p><b>Procedure: </b><code><a id="array-freeze!">array-freeze!</a> <var>array</var></code></p>
<p>Modifies the array <code><var>array</var></code> so it is not mutable. Returns the modified argument.</p>
<p>It is an error if <code><var>array</var></code> is not an array.</p>
<p><b>Example: </b></p>
<pre><code>(let ((array (array-copy (make-array (make-interval '#(2 2)) list)
generic-storage-class
#t)))
(mutable-array? array) ;; => #t
(array-freeze! array)
(mutable-array? array)) ;; => #f</code></pre>
<p><b>Procedure: </b><code><a id="array-empty?">array-empty?</a> <var>array</var></code></p>
<p>Assumes <code><var>array</var></code> is an array, and returns <code>(interval-empty? (array-domain <var>array</var>))</code>. It is an error if the argument is not an array.</p>
<p><b>Example: </b></p>
<pre><code>(let ((A (make-array (make-interval '#(2 2)) list))
(B (make-array (make-interval '#(4 0 4)) list)))
(array-empty? A) ;; => #f
(array-empty? B)) ;; => #t</code></pre>
<p><b>Procedure: </b><code><a id="make-specialized-array">make-specialized-array</a> <var>interval</var> [ <var>storage-class</var> [ <var>initial-value</var> [ <var>safe?</var> ] ] ]</code></p>
<p>Constructs a mutable specialized array from its arguments.</p>