forked from scheme-requests-for-implementation/srfi-122
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathsrfi-122.html
1826 lines (1762 loc) · 127 KB
/
srfi-122.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 PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
<html>
<head>
<meta charset="utf-8">
<meta name="viewport" content="width=device-width, initial-scale=1">
<title>Nonempty Intervals and Generalized Arrays</title>
<link type="test/css" rel="stylesheet" href="http://srfi.schemers.org/srfi.css">
<script type="text/x-mathjax-config">
MathJax.Hub.Config({
tex2jax: {inlineMath: [['$','$'], ['\\(','\\)']]}
});</script>
<script integrity="sha384-Ra6zh6uYMmH5ydwCqqMoykyf1T/+ZcnOQfFPhDrp2kI4OIxadnhsvvA2vv9A7xYv" crossorigin="anonymous" type="text/javascript" src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.1/MathJax.js?config=TeX-AMS-MML_HTMLorMML"></script>
</head>
<body>
<h1>Title</h1>
<p>Nonempty Intervals and Generalized Arrays</p>
<h2>Author</h2>
<p>Bradley J. Lucier</p>
<h2>Status</h2>
<p>This SRFI is currently in <em>final</em> status. Here is <a href="http://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 122 at srfi dot schemers dot org">srfi-122@<span class="antispam">nospam</span>srfi.schemers.org</a></code>. To subscribe to the list, follow <a href="http://srfi.schemers.org/srfi-list-subscribe.html">these instructions</a>. You can access previous messages via the mailing list <a href="http://srfi-email.schemers.org/srfi-122">archive</a>. There is a <a href="https://github.com/scheme-requests-for-implementation/srfi-122">git repository</a> of this document, a reference implementation, a test file, and other materials.</p>
<ul>
<li>Received: 2015/7/23</li>
<li>Draft #1 published: 2015/7/27</li>
<li>Draft #2 published: 2015/7/31</li>
<li>Draft #3 published: 2015/7/31</li>
<li>Draft #4 published: 2015/9/03</li>
<li>Draft #5 published: 2015/9/18</li>
<li>Draft #6 published: 2015/10/19</li>
<li>Draft #7 published: 2016/8/15</li>
<li>Draft #8 published: 2016/8/19</li>
<li>Draft #9 published: 2016/8/25</li>
<li>Draft #10 published: 2016/8/30</li>
<li>Draft #11 published: 2016/9/7</li>
<li>Draft #12 published: 2016/9/17</li>
<li>Draft #13 published: 2016/11/18</li>
<li>Draft #14 published: 2016/11/28</li>
<li>Draft #15 published: 2016/12/15</li>
<li>Finalized: 2016/12/24</li></ul>
<h2>Post-finalization note</h2>
<p>This document, the associated implementation in generic-arrays.scm, and the test file test-arrays.scm differ from the finalized SRFI-122 in the following ways:</p>
<ul>
<li>The abstract has been rewritten to make it more precise. A "Motivation" section was added.</li>
<li>The procedures <code>interval-for-each</code>, <code>interval-cartesian-product</code>, <code>array-outer-product</code>, <code>array-tile</code>, <code>array-assign!</code>, and <code>array-swap!</code> have been added.</li>
<li>The discussion of Haar transforms as examples of separable transforms has been corrected.</li>
<li>The documentation has a few more examples of image processing algorithms.</li>
<li>Some matrix examples have been added to this document and test-arrays.scm.</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 nonempty 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 <i>intervals</i>, which 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 are specified to provide portable programs with efficient representations for common use cases.</p>
<h2>Motivation</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> by exploiting the algebraic structure of affine one-to-one mappings on multi-indices.</li>
<li>Separate <b>the routines that specify the work to be done</b> (<code>array-map</code>, <code>array-outer-product</code>, etc.) from <b>the routines that actually do the work</b> (<code>array->specialized-array</code>, <code>array-assign!</code>, <code>array-fold</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>
<h2>Overview</h2>
<h3>Bawden-style arrays</h3>
<p>In a <a href="https://groups.google.com/forum/?hl=en#!msg/comp.lang.scheme/7nkx58Kv6RI/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>. His arrays were defined on rectangular intervals in $\mathbb Z^d$ of the form $[0,u_0)\times\cdots\times [0,u_{d-1})$. I'll note that his function <code>array-set!</code> put 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 routine <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 function from the interval $[0,u_0)\times\cdots\times [0,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$ (in Bawden's case $[0,u_0)\times \cdots\times [0,u_{d-1})$) 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 $(0,\ldots,0,0)$, $(0,\ldots,0,1)$, $\ldots$, $(0,\ldots,1,0)$, etc., in lexicographical order, which means that if $\vec i$ and $\vec j$ are two multi-indices, then $\vec i<\vec j$ iff the first coordinate $k$ where $\vec i$ and $\vec j$ differ satisfies $\vec i_k<\vec j_k$. In fact, $I_A(\vec i)=\vec v\cdot\vec i$ for some specially-constructed vector $\vec v$ that depends only on $D_A$, the domain of $A$, where $\vec v\cdot\vec i$ is the dot product of $\vec v$ and $\vec i$.</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>Our extensions of Bawden-style arrays</h3>
<p>We incorporate Bawden-style arrays into this SRFI, but extend them in two relatively minor ways that we find quite useful.</p>
<p>First, we allow the intervals of multi-indices that form the domains of arrays to have nonzero lower bounds as well as upper bounds, so domains are rectangular, $d$-dimensional intervals $[l_0,u_0)\times\cdots\times[l_{d-1},u_{d-1})$.</p>
<p>Second, we introduce the notion of a <i>storage class</i>, an object that contains functions that manipulate, store, check, etc., different types of values. A <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>Common transformations on Bawden-style arrays</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 dimensions, which we call <i>tiling</i> the array. The routine <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. The only nonidentity permutation of a two-dimensional spreadsheet turns rows into columns and vice versa.</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 routines are simply "convenience" procedures. Second, because the composition of any number of affine mappings are 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>Generalized arrays</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})$ (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>Specifically, an array specifies a nonempty, 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" function, 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, one may read the values from a file, etc.</p>
<p>In this SRFI, Bawden-style arrays are called <i>specialized</i>. A specialized array is an example of a mutable array.</p>
<h3>Sharing generalized arrays</h3>
<p>Even if an array $A$ is not a specialized array, then 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))$ can 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 routine <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 not that expensive. If we denote <code>(array-getter A)</code> by <code>A-getter</code>, then if B is the result of <code>array-extract</code> applied to A, then <code>(array-getter B)</code> is simply <code>A-getter</code>. Similarly, if A is a two-dimensional array, and B is derived from A by applying the permutation $\pi((i,j))=(j,i)$, then <code>(array-getter B)</code> is <code>(lambda (i j) (A-getter j i))</code>. Translation and currying also lead to transformed arrays whose getters are relatively efficiently derived from <code>A-getter</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 functions <code>array-extract</code>, <code>array-translate</code>, <code>array-permute</code>, <code>array-curry</code>, <code>array-reverse</code>, and <code>array-sample</code>, and we provide relatively efficient implementations of these functions for arrays of dimension no greater than four.</p>
<h3>Array-map does not produce a specialized array</h3>
<p>Daniel Friedman and David Wise wrote a famous paper <a href="http://www.cs.indiana.edu/cgi-bin/techreports/TRNNN.cgi?trnum=TR44">CONS should not Evaluate its Arguments</a>. In the spirit of that paper, our procedure <code>array-map</code> does not immediately produce a specialized array, but a simple immutable array, whose elements are recomputed from the arguments of <code>array-map</code> each time they are accessed. This immutable array can be passed on to further applications of <code>array-map</code> for further processing, without generating the storage bodies for intermediate arrays.</p>
<p>We provide the procedure <code>array->specialized-array</code> to transform a generalized array (like that returned by <code>array-map</code>) to a specialized, Bawden-style array, for which accessing each element again takes $O(1)$ operations.</p>
<h3>Notational convention</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 functions 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>Issues and Notes</h2>
<ul>
<li><b>Relationship to <a href="http://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="http://research.microsoft.com/en-us/um/people/simonpj/papers/ndp/RArrays.pdf">array proposal for Haskell</a>. Our "specialized" arrays are related to Racket's "strict" arrays.</li>
<li><b>Indexers. </b>The argument new-domain->old-domain to <code>specialized-array-share</code> is, conceptually, a multi-valued array.</li>
<li><b>Source of function names. </b>The function <code>array-curry</code> gets its name from the
<a href="http://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 function of the interval, encapsulated here as <code>interval-contains-multi-index?</code>.</li>
<li><b>Choice of functions on intervals. </b>The choice of functions for both arrays and intervals was motivated almost solely by what I needed for arrays.</li>
<li><b>No empty intervals. </b>This SRFI considers arrays over only nonempty intervals of positive dimension. The author of this proposal acknowledges that other languages and array systems allow either zero-dimensional intervals or empty intervals of positive dimension, but prefers to leave such empty intervals as possibly compatible extensions to the current proposal.</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 a compatible extension of this SRFI.</li>
<li><b>No low-level specialized-array constructor. </b>While the author of the SRFI uses mainly <code>(make-array ...)</code>, <code>array-map</code>, and <code>array->specialized-array</code> to construct arrays, and while there are several other ways to construct arrays, there is no really low-level interface given for constructing specialized arrays (where one specifies a body, an indexer, etc.). It was felt that certain difficulties, some surmountable (such as checking that a given body is compatible with a given storage class) and some not (such as checking that an indexer is indeed affine), made a low-level interface less useful. At the same time, the simple <code>(make-array ...)</code> mechanism is so general, allowing one to specify getters and setters as general functions, as to cover nearly all needs.</li></ul>
<h2>Specification</h2>
<dl>
<dt>Miscellaneous Functions</dt>
<dd><a href="#translation?">translation?</a>,
<a href="#permutation?">permutation?</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-lower-bounds->list">interval-lower-bounds->list</a>,
<a href="#interval-upper-bounds->list">interval-upper-bounds->list</a>,
<a href="#interval-lower-bounds->vector">interval-lower-bounds->vector</a>,
<a href="#interval-upper-bounds->vector">interval-upper-bounds->vector</a>,
<a href="#interval=">interval=</a>,
<a href="#interval-volume">interval-volume</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-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-length">storage-class-length</a>,
<a href="#storage-class-default">storage-class-default</a>,
<a href="#generic-storage-class">generic-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="#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="#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="#specialized-array-default-safe?">specialized-array-default-safe?</a>,
<a href="#make-specialized-array">make-specialized-array</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="#specialized-array-share">specialized-array-share</a>,
<a href="#array->specialized-array">array->specialized-array</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-map">array-map</a>,
<a href="#array-for-each">array-for-each</a>,
<a href="#array-fold">array-fold</a>,
<a href="#array-fold-right">array-fold-right</a>,
<a href="#array-any">array-any</a>,
<a href="#array-every">array-every</a>,
<a href="#array->list">array->list</a>,
<a href="#list->specialized-array">list->specialized-array</a>,
<a href="#array-assign!">array-assign!</a>,
<a href="#array-swap!">array-swap!</a>.</dd></dl>
<h2>Miscellaneous Functions</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.</p>
<h3>Procedures</h3>
<p><b>Procedure: </b><code><a name="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 name="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>
<h2>Intervals</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 specified multi-indices of exact integers. The positive integer $d$ is the <i>dimension</i>
of the interval. It is required that
$l_0<u_0,\ldots,l_{d-1}<u_{d-1}$.</p>
<p>Intervals are a data type distinct from other Scheme data types.</p>
<h3>Procedures</h3>
<p><b>Procedure: </b><code><a name="make-interval">make-interval</a> <var>lower-bounds</var> <var>upper-bounds</var></code></p>
<p>Create a new interval; <code><var>lower-bounds</var></code> and <code><var>upper-bounds</var></code>
are nonempty vectors (of the same length) of exact integers that 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>Procedure: </b><code><a name="interval?">interval?</a> <var>obj</var></code></p>
<p>Returns <code>#t</code> if <code><var>obj</var></code> is an interval, and <code>#f</code> otherwise.</p>
<p><b>Procedure: </b><code><a name="interval-dimension">interval-dimension</a> <var>interval</var></code></p>
<p>If <code><var>interval</var></code> is an interval 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>. It is an error to call <code>interval-dimension</code>
if <code><var>interval</var></code> is not an interval.</p>
<p><b>Procedure: </b><code><a name="interval-lower-bound">interval-lower-bound</a> <var>interval</var> <var>i</var></code></p>
<p><b>Procedure: </b><code><a name="interval-upper-bound">interval-upper-bound</a> <var>interval</var> <var>i</var></code></p>
<p>If <code><var>interval</var></code> is an interval built with </p>
<blockquote><code>(make-interval <var>lower-bounds</var> <var>upper-bounds</var>)</code>
</blockquote>
<p>and <code><var>i</var></code> is an exact integer that satisfies</p>
<blockquote>$0 \leq i<$ <code>(vector-length <var>lower-bounds</var>)</code>,
</blockquote>
<p> then <code>interval-lower-bound</code> returns
<code>(vector-ref <var>lower-bounds</var> <var>i</var>)</code> and <code>interval-upper-bound</code> returns
<code>(vector-ref <var>upper-bounds</var> <var>i</var>)</code>. It is an error to call <code>interval-lower-bound</code> or <code>interval-upper-bound</code>
if <code><var>interval</var></code> and <code><var>i</var></code> do not satisfy these conditions.</p>
<p><b>Procedure: </b><code><a name="interval-lower-bounds->list">interval-lower-bounds->list</a> <var>interval</var></code></p>
<p><b>Procedure: </b><code><a name="interval-upper-bounds->list">interval-upper-bounds->list</a> <var>interval</var></code></p>
<p>If <code><var>interval</var></code> is an interval built with </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>. 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>Procedure: </b><code><a name="interval-lower-bounds->vector">interval-lower-bounds->vector</a> <var>interval</var></code></p>
<p><b>Procedure: </b><code><a name="interval-upper-bounds->vector">interval-upper-bounds->vector</a> <var>interval</var></code></p>
<p>If <code><var>interval</var></code> is an interval built 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>. 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>Procedure: </b><code><a name="interval-volume">interval-volume</a> <var>interval</var></code></p>
<p>If <code><var>interval</var></code> is an interval built 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>Procedure: </b><code><a name="interval=">interval=</a> <var>interval1</var> <var>interval2</var></code></p>
<p>If <code><var>interval1</var></code> and <code><var>interval2</var></code> are intervals built 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>Procedure: </b><code><a name="interval-subset?">interval-subset?</a> <var>interval1</var> <var>interval2</var></code></p>
<p>If <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>Procedure: </b><code><a name="interval-contains-multi-index?">interval-contains-multi-index?</a> <var>interval</var> <var>index-0</var> <var>index-1</var> <var>...</var></code></p>
<p>If <code><var>interval</var></code> is an interval with dimension $d$ and <code><var>index-0</var></code>, <code><var>index-1</var></code>, ..., is a multi-index of length $d$,
then <code>interval-contains-multi-index?</code> returns <code>#t</code> if </p>
<blockquote><code>(interval-lower-bound <var>interval</var> j)</code> $\leq$ <code><var>index-j</var></code> $<$ <code>(interval-upper-bound <var>interval</var> j)</code>
</blockquote>
<p>for $0\leq j < d$, and <code>#f</code> otherwise.</p>
<p>It is an error to call <code>interval-contains-multi-index?</code> if <code><var>interval</var></code> and <code><var>index-0</var></code>,..., do not satisfy this condition.</p>
<p><b>Procedure: </b><code><a name="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 function, 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, if <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> then <code>interval-projections</code> returns two intervals:</p>
<pre><code>
(values
(make-interval
(vector (interval-lower-bound <var>interval</var> 0)
...
(interval-lower-bound <var>interval</var>
(- <var>d</var> <var>right-dimension</var> 1)))
(vector (interval-upper-bound <var>interval</var> 0)
...
(interval-upper-bound <var>interval</var>
(- <var>d</var> <var>right-dimension</var> 1))))
(make-interval
(vector (interval-lower-bound <var>interval</var>
(- <var>d</var> <var>right-dimension</var>))
...
(interval-lower-bound <var>interval</var>
(- <var>d</var> 1)))
(vector (interval-upper-bound <var>interval</var>
(- <var>d</var> <var>right-dimension</var>))
...
(interval-upper-bound <var>interval</var>
(- <var>d</var> 1)))))</code></pre>
<p>It is an error to call <code>interval-projections</code> if its arguments do not satisfy these conditions.</p>
<p><b>Procedure: </b><code><a name="interval-for-each">interval-for-each</a> <var>f</var> <var>interval</var></code></p>
<p>This routine assumes that <code><var>interval</var></code> is an interval and <code><var>f</var></code> is a routine 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><b>Procedure: </b><code><a name="interval-dilate">interval-dilate</a> <var>interval</var> <var>lower-diffs</var> <var>upper-diffs</var></code></p>
<p>If <code><var>interval</var></code> is an interval with
lower bounds l<sub>0</sub>, ..., l<sub>d-1</sub> and
upper bounds u<sub>0</sub>, ..., u<sub>d-1</sub>, and <code><var>lower-diffs</var></code> is a vector of exact integers L<sub>0</sub>, ..., L<sub>d-1</sub> and <code><var>upper-diffs</var></code> is a vector of exact integers U<sub>0</sub>, ..., U<sub>d-1</sub>, then <code>interval-dilate</code> returns a new interval with
lower bounds l<sub>0</sub>+L<sub>0</sub>, ..., l<sub>d-1</sub>+L<sub>d-1</sub> and
upper bounds u<sub>0</sub>+U<sub>0</sub>, ..., u<sub>d-1</sub>+U<sub>d-1</sub>, as long as this is a
nonempty interval. It is an error if the arguments do not satisfy these conditions.</p>
<p>Examples:</p>
<pre><code>
(interval=
(interval-dilate (make-interval '#(0 0) '#(100 100))
'#(1 1) '#(1 1))
(make-interval '#(1 1) '#(101 101))) => #t
(interval=
(interval-dilate (make-interval '#(0 0) '#(100 100))
'#(-1 -1) '#(1 1))
(make-interval '#(-1 -1) '#(101 101))) => #t
(interval=
(interval-dilate (make-interval '#(0 0) '#(100 100))
'#(0 0) '#(-50 -50))
(make-interval '#(0 0) '#(50 50))) => #t
(interval-dilate
(make-interval '#(0 0) '#(100 100))
'#(0 0) '#(-500 -50)) => error
</code></pre>
<p><b>Procedure: </b><code><a name="interval-intersect">interval-intersect</a> <var>interval-1</var> <var>interval-2</var> <var>...</var></code></p>
<p>If all the arguments are intervals of the same dimension and they have a nonempty intersection,
the <code>interval-intersect</code> returns that intersection; otherwise it returns <code>#f</code>.</p>
<p>It is an error if the arguments are not all intervals with the same dimension.</p>
<p><b>Procedure: </b><code><a name="interval-translate">interval-translate</a> <var>interval</var> <var>translation</var></code></p>
<p>If <code><var>interval</var></code> is an interval with
lower bounds l<sub>0</sub>, ..., l<sub>d-1</sub> and
upper bounds u<sub>0</sub>, ..., u<sub>d-1</sub>, and <code><var>translation</var></code> is a translation with entries T<sub>0</sub>, ..., T<sub>d-1</sub>, then <code>interval-translate</code> returns a new interval with
lower bounds l<sub>0</sub>+T<sub>0</sub>, ..., l<sub>d-1</sub>+T<sub>d-1</sub> and
upper bounds u<sub>0</sub>+T<sub>0</sub>, ..., u<sub>d-1</sub>+T<sub>d-1</sub>.
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>Procedure: </b><code><a name="interval-permute">interval-permute</a> <var>interval</var> <var>permutation</var></code></p>
<p>The argument <code><var>interval</var></code> must be an interval, and the argument <code><var>permutation</var></code> must be a valid 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 function 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>Procedure: </b><code><a name="interval-scale">interval-scale</a> <var>interval</var> <var>scales</var></code></p>
<p>If <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 this condition.</p>
<p><b>Procedure: </b><code><a name="interval-cartesian-product">interval-cartesian-product</a> <var>interval</var> . <var>intervals</var></code></p>
<p>Implements the Cartesian product of the intervals in <code>(cons <var>interval</var> <var>intervals</var>)</code>. Returns</p>
<pre><code>
(make-interval (list->vector (apply append (map array-lower-bounds->list (cons interval intervals))))
(list->vector (apply append (map array-upper-bounds->list (cons interval intervals)))))</code></pre>
<p>It is an error if any argument is not an interval.</p>
<h2>Storage classes</h2>
<p>Conceptually, a storage-class is a set of functions to manage the backing store of a specialized-array.
The functions allow one to make a backing store, to get values from the store and to set new values, to return the length of the store, and to specify a default value for initial elements of the backing store. Typically, a backing store is a (heterogeneous or homogeneous) vector. A storage-class has a type distinct from other Scheme types.</p>
<h3>Procedures</h3>
<p><b>Procedure: </b><code><a name="make-storage-class">make-storage-class</a> <var>getter</var> <var>setter</var> <var>checker</var> <var>maker</var> <var>length</var> <var>default</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 an object containing <code><var>n</var></code> elements of value <code><var>value</var></code>.</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></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 name="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 name="storage-class-getter">storage-class-getter</a> <var>m</var></code></p>
<p><b>Procedure: </b><code><a name="storage-class-setter">storage-class-setter</a> <var>m</var></code></p>
<p><b>Procedure: </b><code><a name="storage-class-checker">storage-class-checker</a> <var>m</var></code></p>
<p><b>Procedure: </b><code><a name="storage-class-maker">storage-class-maker</a> <var>m</var></code></p>
<p><b>Procedure: </b><code><a name="storage-class-length">storage-class-length</a> <var>m</var></code></p>
<p><b>Procedure: </b><code><a name="storage-class-default">storage-class-default</a> <var>m</var></code></p>
<p>If <code><var>m</var></code> is an object created by</p>
<blockquote><code>(make-storage-class <var>getter setter checker maker length default</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>, and <code>storage-class-length</code> returns <code><var>length</var></code>, and <code>storage-class-default</code> returns <code><var>default</var></code>. Otherwise, it is an error to call any of these routines.</p>
<h3>Global Variables</h3>
<p><b>Variable: </b><code><a name="generic-storage-class">generic-storage-class</a></code></p>
<p><b>Variable: </b><code><a name="s8-storage-class">s8-storage-class</a></code></p>
<p><b>Variable: </b><code><a name="s16-storage-class">s16-storage-class</a></code></p>
<p><b>Variable: </b><code><a name="s32-storage-class">s32-storage-class</a></code></p>
<p><b>Variable: </b><code><a name="s64-storage-class">s64-storage-class</a></code></p>
<p><b>Variable: </b><code><a name="u1-storage-class">u1-storage-class</a></code></p>
<p><b>Variable: </b><code><a name="u8-storage-class">u8-storage-class</a></code></p>
<p><b>Variable: </b><code><a name="u16-storage-class">u16-storage-class</a></code></p>
<p><b>Variable: </b><code><a name="u32-storage-class">u32-storage-class</a></code></p>
<p><b>Variable: </b><code><a name="u64-storage-class">u64-storage-class</a></code></p>
<p><b>Variable: </b><code><a name="f32-storage-class">f32-storage-class</a></code></p>
<p><b>Variable: </b><code><a name="f64-storage-class">f64-storage-class</a></code></p>
<p><b>Variable: </b><code><a name="c64-storage-class">c64-storage-class</a></code></p>
<p><b>Variable: </b><code><a name="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-length
#f))</code></pre>Furthermore, <code>s<var>X</var>-storage-class</code> is defined 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> is defined 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> is defined for <code><var>X</var></code>= 32 and 64 (which have default value 0.0 and manipulate 32- and 64-bit floating-point numbers), and
<code>c<var>X</var>-storage-class</code> is defined 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). Each of these
could be defined simply as <code>generic-storage-class</code>, but it is assumed that implementations with homogeneous vectors will give definitions
that either save space, avoid boxing, etc., for the specialized arrays.
<h2>Arrays</h2>
<p>Arrays are a data type distinct from other Scheme data types.</p>
<h3>Procedures</h3>
<p><b>Procedure: </b><code><a name="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 function 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>Example: </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>Example: </p>
<pre><code>
(define a ;; a sparse array
(let ((domain
(make-interval '#(0 0)
'#(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>Procedure: </b><code><a name="array?">array?</a> <var>obj</var></code></p>
<p>Returns <code>#t</code> if <code><var>obj</var></code> is an array and <code>#f</code> otherwise.</p>
<p><b>Procedure: </b><code><a name="array-domain">array-domain</a> <var>array</var></code></p>
<p><b>Procedure: </b><code><a name="array-getter">array-getter</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>(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>Example: </p>
<pre><code>
(define a (make-array (make-interval '#(1 1) '#(11 11))
(lambda (i j)
(if (= i j)
1
0))))
(defina 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 name="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 function if <code><var>array</var></code> is not an array.</p>
<p><b>Procedure: </b><code><a name="mutable-array?">mutable-array?</a> <var>obj</var></code></p>
<p>Returns <code>#t</code> if <code><var>obj</var></code> is a mutable array and <code>#f</code> otherwise.</p>
<p><b>Procedure: </b><code><a name="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>. 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 name="specialized-array-default-safe?">specialized-array-default-safe?</a> [ <var>bool</var> ]</code></p>
<p>With no argument, returns <code>#t</code> if newly-constructed specialized arrays check the arguments of setters and getters by default, and <code>#f</code> otherwise.</p>
<p>If <code><var>bool</var></code> is <code>#t</code> then the next call to <code>specialized-array-default-safe?</code> will return <code>#t</code>;
if <code><var>bool</var></code> is <code>#f</code> then the next call to <code>specialized-array-default-safe?</code> will return <code>#f</code>;
otherwise it is an error.</p>
<p><b>Procedure: </b><code><a name="make-specialized-array">make-specialized-array</a> <var>interval</var> [ <var>storage-class</var> generic-storage-class ] [ <var>safe?</var> (specialized-array-default-safe?) ]</code></p>
<p>Constructs a specialized-array from its arguments.</p>
<p><code><var>interval</var></code> must be given as a nonempty interval. If given, <code><var>storage-class</var></code> must be a storage class; if it is not given it defaults to <code>generic-storage-class</code>. If given, <code><var>safe?</var></code> must be a boolean; if it is not given it defaults to the current value of <code>(specialized-array-default-safe?)</code>.</p>
<p>The body of the result is constructed as </p>
<pre><code>
((storage-class-maker <var>storage-class</var>)
(interval-volume <var>interval</var>)
(storage-class-default <var>storage-class</var>))
</code></pre>
<p>The indexer of the resulting array is constructed as the lexicographical mapping of <code><var>interval</var></code> onto the interval <code>[0,(interval-volume <var>interval</var>))</code>.</p>
<p>If <code><var>safe</var></code> is <code>#t</code>, then the arguments of the getter and setter (including the value to be stored) of the resulting array are always checked for correctness.</p>
<p>After correctness checking (if needed), <code>(array-getter <var>array</var>)</code> is defined simply as </p>
<pre><code>
(lambda multi-index
((storage-class-getter <var>storage-class</var>)
(array-body <var>array</var>)
(apply (array-indexer <var>array</var>) multi-index)))
</code></pre>
<p> and <code>(array-setter <var>array</var>)</code> is defined as </p>
<pre><code>
(lambda (val . multi-index)
((storage-class-setter <var>storage-class</var>)
(array-body <var>array</var>)
(apply (array-indexer <var>array</var>) multi-index)
val))
</code></pre>
<p>It is an error if the arguments of <code>make-specialized-array</code> do not satisfy these conditions.</p>
<p><b>Examples. </b>A simple array that can hold any type of element can be defined with <code>(make-specialized-array (make-interval '#(0 0) '#(3 3)))</code>. If you find that you're using a lot of unsafe arrays of unsigned 16-bit integers, one could define </p>
<pre><code>
(define (make-u16-array interval)
(make-specialized-array interval u16-storage-class #f))
</code></pre>
<p>and then simply call, e.g., <code>(make-u16-array (make-interval '#(0 0) '#(3 3)))</code>.</p>
<p><b>Procedure: </b><code><a name="specialized-array?">specialized-array?</a> <var>obj</var></code></p>
<p>Returns <code>#t</code> if <code><var>obj</var></code> is a specialized-array, and <code>#f</code> otherwise. A specialized-array is an array.</p>
<p><b>Procedure: </b><code><a name="array-storage-class">array-storage-class</a> <var>array</var></code></p>
<p><b>Procedure: </b><code><a name="array-indexer">array-indexer</a> <var>array</var></code></p>
<p><b>Procedure: </b><code><a name="array-body">array-body</a> <var>array</var></code></p>
<p><b>Procedure: </b><code><a name="array-safe?">array-safe?</a> <var>array</var></code></p>
<p><code>array-storage-class</code> returns the storage-class of <code><var>array</var></code>. <code>array-safe?</code> is true if and only if the arguments of <code>(array-getter <var>array</var>)</code> and <code>(array-setter <var>array</var>)</code> (including the value to be stored in the array) are checked for correctness.</p>
<p><code>(array-indexer <var>array</var>)</code> is assumed to be a one-to-one, but not necessarily onto, affine mapping from <code>(array-domain <var>array</var>)</code> into <code>(array-body <var>array</var>)</code>.</p>
<p>It is an error to call any of these routines if <code><var>array</var></code> is not a specialized-array.</p>
<p><b>Procedure: </b><code><a name="specialized-array-share">specialized-array-share</a> <var>array</var> <var>new-domain</var> <var>new-domain->old-domain</var></code></p>
<p>Constructs a new specialized-array that shares the body of the specialized-array <code><var>array</var></code>.
Returns an object that is behaviorally equivalent to a specialized array with the following fields:</p>
<pre><code>
domain: new-domain
storage-class: (array-storage-class <var>array</var>)
body: (array-body <var>array</var>)
indexer: (lambda multi-index
(call-with-values
(lambda ()
(apply <var>new-domain->old-domain</var>
multi-index))
(array-indexer <var>array</var>)))</code></pre>
<p><code><var>new-domain->old-domain</var></code> must be an affine one-to-one mapping from <code><var>new-domain</var></code> to
<code>(array-domain <var>array</var>)</code>.</p>
<p>Note: It is assumed that affine structure of the composition of <code><var>new-domain->old-domain</var></code> and <code>(array-indexer <var>array</var></code> will be used to simplify:</p>
<pre><code>
(lambda multi-index
(call-with-values
(lambda ()
(apply <var>new-domain->old-domain</var> multi-index))
(array-indexer <var>array</var>)))</code></pre>
<p>It is an error if <code><var>array</var></code> is not a specialized array, or if <code><var>new-domain</var></code> is not an interval, or if <code><var>new-domain->old-domain</var></code> is not a one-to-one affine mapping with the appropriate domain and range.</p>
<p><b>Example: </b>One can apply a "shearing" operation to an array as follows: </p>
<pre><code>
(define a
(array->specialized-array
(make-array (make-interval '#(0 0) '#(5 10))
list)))
(define b
(specialized-array-share
a
(make-interval '#(0 0) '#(5 5))
(lambda (i j)
(values i (+ i j)))))
;; Print the "rows" of b
(array-for-each (lambda (row)
(pretty-print (array->list row)))
(array-curry b 1))
;; which prints
;; ((0 0) (0 1) (0 2) (0 3) (0 4))
;; ((1 1) (1 2) (1 3) (1 4) (1 5))
;; ((2 2) (2 3) (2 4) (2 5) (2 6))
;; ((3 3) (3 4) (3 5) (3 6) (3 7))
;; ((4 4) (4 5) (4 6) (4 7) (4 8))
</code></pre>
<p>This "shearing" operation cannot be achieved by combining the procedures <code>array-extract</code>, <code>array-translate</code>, <code>array-permute</code>, <code>array-translate</code>, <code>array-curry</code>, <code>array-reverse</code>, and <code>array-sample</code>.</p>
<p><b>Procedure: </b><code><a name="array->specialized-array">array->specialized-array</a> <var>array</var> [ <var>result-storage-class</var> generic-storage-class ] [ <var>safe?</var> (specialized-array-default-safe?) ]</code></p>
<p>If <code><var>array</var></code> is an array whose elements can be manipulated by the storage-class
<code><var>result-storage-class</var></code>, then the specialized-array returned by <code>array->specialized-array</code> can be defined conceptually by:</p>
<pre><code>
(let* ((domain
(array-domain <var>array</var>))
(result
(make-specialized-array domain
<var>result-storage-class</var>
<var>safe?</var>)))
(array-assign! result <var>array</var>)
result)</code></pre>
<p>It is guaranteed that <code>(array-getter <var>array</var>)</code> is called precisely once for each multi-index in <code>(array-domain <var>array</var>)</code> in lexicographical order.</p>
<p>It is an error if <code><var>result-storage-class</var></code> does not satisfy these conditions, or if <code><var>safe?</var></code> is not a boolean.</p>
<p><b>Procedure: </b><code><a name="array-curry">array-curry</a> <var>array</var> <var>inner-dimension</var></code></p>
<p>If <code><var>array</var></code> is an array whose domain is an interval $[l_0,u_0)\times\cdots\times[l_{d-1},u_{d-1})$, and <code><var>inner-dimension</var></code> is an exact integer strictly between $0$ and $d$, then <code>array-curry</code> returns an immutable array with domain $[l_0,u_0)\times\cdots\times[l_{d-\text{inner-dimension}-1},u_{d-\text{inner-dimension}-1})$, each of whose entries is in itself an array with domain $[l_{d-\text{inner-dimension}},u_{d-\text{inner-dimension}})\times\cdots\times[l_{d-1},u_{d-1})$.</p>
<p>For example, if <code>A</code> and <code>B</code> are defined by </p>
<pre><code>
(define interval (make-interval '#(0 0 0 0)
'#(10 10 10 10)))
(define A (make-array interval list))
(define B (array-curry A 1))
(define A_ (array-getter A))
(define B_ (array-getter B))
</code></pre>
<p>so</p>
<pre><code>
(A_ i j k l) => (list i j k l)</code></pre>
<p>then <code>B</code> is an immutable array with domain <code>(make-interval '#(0 0 0) '#(10 10 10))</code>, each
of whose elements is itself an (immutable) array and </p>
<pre><code>
(equal?
(A_ i j k l)
((array-getter (B_ i j k)) l)) => #t
</code></pre>
<p>for all multi-indices <code>i j k l</code> in <code>interval</code>.</p>
<p>The subarrays are immutable, mutable, or specialized according to whether the array argument is immutable, mutable, or specialized.</p>
<p>More precisely, if </p>
<pre><code>0 < <var>inner-dimension</var> < (interval-dimension (array-domain <var>array</var>))</code></pre>
<p>then <code>array-curry</code> returns a result as follows.</p>
<p>If the input array is specialized, then array-curry returns</p>
<pre><code>
(call-with-values
(lambda () (interval-projections (array-domain <var>array</var>)
<var>inner-dimension</var>))
(lambda (outer-interval inner-interval)
(make-array
outer-interval
(lambda outer-multi-index
(specialized-array-share
<var>array</var>
inner-interval
(lambda inner-multi-index
(apply values
(append outer-multi-index
inner-multi-index))))))))</code></pre>
<p>Otherwise, if the input array is mutable, then array-curry returns</p>
<pre><code>
(call-with-values
(lambda () (interval-projections (array-domain <var>array</var>)
<var>inner-dimension</var>))
(lambda (outer-interval inner-interval)
(make-array
outer-interval
(lambda outer-multi-index
(make-array
inner-interval
(lambda inner-multi-index
(apply (array-getter <var>array</var>)
(append outer-multi-index
inner-multi-index)))
(lambda (v . inner-multi-index)
(apply (array-setter <var>array</var>)
v
(append outer-multi-index
inner-multi-index))))))))</code></pre>
<p>Otherwise, array-curry returns</p>
<pre><code>
(call-with-values
(lambda () (interval-projections (array-domain <var>array</var>)
<var>inner-dimension</var>))
(lambda (outer-interval inner-interval)
(make-array
outer-interval
(lambda outer-multi-index
(make-array
inner-interval
(lambda inner-multi-index
(apply (array-getter <var>array</var>)
(append outer-multi-index
inner-multi-index))))))))</code></pre>
<p>It is an error to call <code>array-curry</code> if its arguments do not satisfy these conditions.</p>
<p>Please see the note in the discussion of <a href="#array-tile">array-tile</a>.</p>
<p>Example:</p>
<pre><code>
(define a (make-array (make-interval '#(0 0)
'#(10 10))
list))
(define a_ (array-getter a))
(a_ 3 4) => (3 4)
(define curried-a (array-curry a 1))
(define curried-a_ (array-getter curried-a))
((array-getter (curried-a_ 3)) 4)
=> (3 4)</code></pre>
<p><b>Procedure: </b><code><a name="array-extract">array-extract</a> <var>array</var> <var>new-domain</var></code></p>
<p>Returns a new array with the same getter (and setter, if appropriate) of the first argument, defined on the second argument.</p>
<p>Assumes that <code><var>array</var></code> is an array and <code><var>new-domain</var></code> is an interval that is a sub-interval of <code>(array-domain <var>array</var>)</code>. If <code><var>array</var></code> is a specialized array, then returns </p>
<pre><code>
(specialized-array-share <var>array</var>
<var>new-domain</var>
values)
</code></pre>
<p>Otherwise, if <code><var>array</var></code> is a mutable array, then <code>array-extract</code> returns </p>
<pre><code>
(make-array <var>new-domain</var>
(array-getter <var>array</var>)
(array-setter <var>array</var>))
</code></pre>
<p>Finally, if <code><var>array</var></code> is an immutable array, then <code>array-extract</code> returns </p>
<pre><code>
(make-array <var>new-domain</var>
(array-getter <var>array</var>))
</code></pre>
<p>It is an error if the arguments of <code>array-extract</code> do not satisfy these conditions.</p>
<p><b>Procedure: </b><code><a name="array-tile">array-tile</a> <var>A</var> <var>S</var></code></p>
<p>Assume that <code><var>A</var></code> is an array and <code><var>S</var></code> is a vector of positive, exact integers. The routine <code>array-tile</code> returns a new immutable array $T$, each entry of which is a subarray of <code>A</code> whose domain has sidelengths given (mostly) by the entries of <code><var>S</var></code>. These subarrays completely "tile" <code><var>A</var></code>, in the sense that every entry in <code><var>A</var></code> is an entry of precisely one entry of the result $T$.</p>
<p>More formally, if <code><var>S</var></code> is the vector $(s_0,\ldots,s_{d-1})$, and the domain of <code><var>A</var></code> is the interval $[l_0,u_0)\times\cdots\times [l_{d-1},u_{d-1})$, then $T$ is an immutable array with all lower bounds zero and upper bounds given by
$$
\operatorname{ceiling}((u_0-l_0)/s_0),\ldots,\operatorname{ceiling}((u_{d-1}-l_{d-1})/s_{d-1}).
$$
The $i_0,\ldots,i_{d-1}$ entry of $T$ is <code>(array-extract <var>A</var> D_i)</code> with the interval <code>D_i</code> given by
$$
[l_0+i_0*s_0,\min(l_0+(i_0+1)s_0,u_0))\times\cdots\times[l_{d-1}+i_{d-1}*s_{d-1},\min(l_{d-1}+(i_{d-1}+1)s_{d-1},u_{d-1})).
$$
(The "minimum" operators are necessary if $u_j-l_j$ is not divisible by $s_j$.) Thus, each entry of $T$ will be a specialized, mutable, or immutable array, depending on the type of the input array <code><var>A</var></code>.</p>
<p>It is an error if the arguments of <code>array-tile</code> do not satisfy these conditions.</p>
<p><b>Note: </b>The routines <code>array-tile</code> and <code>array-curry</code> both decompose an array into subarrays, but in different ways. For example, if <code><var>A</var></code> is defined as <code>(make-array (make-interval '#(0 0) '#(10 10)) list)</code>, then <code>(array-tile <var>A</var> '#(1 10))</code> returns an array with domain <code>(make-interval '#(0 0) '#(10 1))</code>, each element of which is an array with domain <code>(make-interval '#(0 0) '#(1 10))</code> (i.e., a two-dimensional array whose elements are two-dimensional arrays), while <code>(array-curry <var>A</var> 1)</code> returns an array with domain <code>(make-interval '#(0) '#(10))</code>, each element of which has domain <code>(make-interval '#(0) '#(10))</code> (i.e., a one-dimensional array whose elements are one-dimensional arrays).</p>
<p><b>Procedure: </b><code><a name="array-translate">array-translate</a> <var>array</var> <var>translation</var></code></p>
<p>Assumes that <code><var>array</var></code> is a valid array, <code><var>translation</var></code> is a valid translation, and that the dimensions of the array and the translation are the same. The resulting array will have domain <code>(interval-translate (array-domain array) translation)</code>.</p>
<p>If <code><var>array</var></code> is a specialized array, returns a new specialized array</p>
<pre><code>
(specialized-array-share
<var>array</var>
(interval-translate (array-domain <var>array</var>)
<var>translation</var>)
(lambda multi-index
(apply values
(map -
multi-index
(vector->list <var>translation</var>)))))
</code></pre>
<p>that shares the body of <code><var>array</var></code>.</p>
<p>If <code><var>array</var></code> is not a specialized array but is a mutable array, returns a new mutable array</p>
<pre><code>
(make-array
(interval-translate (array-domain <var>array</var>)
<var>translation</var>)
(lambda multi-index
(apply (array-getter <var>array</var>)
(map -
multi-index
(vector->list <var>translation</var>))))
(lambda (val . multi-index)
(apply (array-setter <var>array</var>)
val
(map -
multi-index
(vector->list <var>translation</var>)))))
</code></pre>
<p>that employs the same getter and setter as the original array argument.</p>
<p>If <code><var>array</var></code> is not a mutable array, returns a new array</p>
<pre><code>
(make-array
(interval-translate (array-domain <var>array</var>)
<var>translation</var>)
(lambda multi-index
(apply (array-getter <var>array</var>)
(map - multi-index (vector->list <var>translation</var>)))))
</code></pre>
<p>that employs the same getter as the original array.</p>
<p>It is an error if the arguments do not satisfy these conditions.</p>
<p><b>Procedure: </b><code><a name="array-permute">array-permute</a> <var>array</var> <var>permutation</var></code></p>
<p>Assumes that <code><var>array</var></code> is a valid array, <code><var>permutation</var></code> is a valid permutation, and that the dimensions of the array and the permutation are the same. The resulting array will have domain <code>(interval-permute (array-domain array) permutation)</code>.</p>
<p>We begin with an example. Assume that the domain of <code><var>array</var></code> is represented by the interval $[0,4)\times[0,8)\times[0,21)\times [0,16)$, as in the example for <code>interval-permute</code>, and the permutation is <code>#(3 0 1 2)</code>. Then the domain of the new array is the interval $[0,16)\times [0,4)\times[0,8)\times[0,21)$.</p>
<p>So the multi-index argument of the <code>getter</code> of the result of <code>array-permute</code> must lie in the new domain of the array, the interval $[0,16)\times [0,4)\times[0,8)\times[0,21)$. So if we define <code><var>old-getter</var></code> as <code>(array-getter <var>array</var>)</code>, the definition of the new array must be in fact</p>
<pre><code>
(make-array (interval-permute (array-domain <var>array</var>)
'#(3 0 1 2))
(lambda (l i j k)
(old-getter i j k l)))
</code></pre>
<p>So you see that if the first argument if the new getter is in $[0,16)$, then indeed the fourth argument of <code><var>old-getter</var></code> is also in $[0,16)$, as it should be. This is a subtlety that I don't see how to overcome. It is the listing of the arguments of the new getter, the <code>lambda</code>, that must be permuted.</p>
<p>Mathematically, we can define $\pi^{-1}$, the inverse of a permutation $\pi$, such that $\pi^{-1}$ composed with $\pi$ gives the identity permutation. Then the getter of the new array is, in pseudo-code, <code>(lambda multi-index (apply <var>old-getter</var> (</code>$\pi^{-1}$<code> multi-index)))</code>. We have assumed that $\pi^{-1}$ takes a list as an argument and returns a list as a result.</p>
<p>Employing this same pseudo-code, if <code><var>array</var></code> is a specialized-array and we denote the permutation by $\pi$, then <code>array-permute</code> returns the new specialized array</p>
<pre><code>
(specialized-array-share <var>array</var>
(interval-permute (array-domain <var>array</var>) π)
(lambda multi-index
(apply values (π<sup>-1</sup> multi-index))))</code></pre>
<p>The result array shares <code>(array-body <var>array</var>)</code> with the argument.</p>
<p>Again employing this same pseudo-code, if <code><var>array</var></code> is not a specialized array, but is
a mutable-array, then <code>array-permute</code> returns the new mutable</p>
<pre><code>
(make-array (interval-permute (array-domain <var>array</var>) π)
(lambda multi-index
(apply (array-getter <var>array</var>)
(π<sup>-1</sup> multi-index)))
(lambda (val . multi-index)
(apply (array-setter <var>array</var>)
val
(π<sup>-1</sup> multi-index))))</code></pre>
<p>which employs the setter and the getter of the argument to <code>array-permute</code>.</p>
<p>Finally, if <code><var>array</var></code> is not a mutable array, then <code>array-permute</code> returns</p>
<pre><code>
(make-array (interval-permute (array-domain <var>array</var>) π)
(lambda multi-index
(apply (array-getter <var>array</var>)
(π<sup>-1</sup> multi-index))))</code></pre>
<p>It is an error to call <code>array-permute</code> if its arguments do not satisfy these conditions.</p>
<p><b>Procedure: </b><code><a name="array-reverse">array-reverse</a> <var>array</var> <var>flip?</var></code></p>
<p>We assume that <code><var>array</var></code> is an array and <code><var>flip?</var></code> is a vector of booleans whose length is the same as the dimension of <code><var>array</var></code>.</p>
<p><code>array-reverse</code> returns a new array that is specialized, mutable, or immutable according to whether <code><var>array</var></code> is specialized, mutable, or immutable, respectively. Informally, if <code>(vector-ref <var>flip?</var> k)</code> is true, then the ordering of multi-indices in the k'th coordinate direction is reversed, and is left undisturbed otherwise.</p>
<p>More formally, we introduce the function </p>
<pre><code>
(define flip-multi-index
(let* ((domain (array-domain <code><var>array</var></code>))
(lowers (interval-lower-bounds->list domain))
(uppers (interval-upper-bounds->list domain)))
(lambda (multi-index)
(map (lambda (i_k flip?_k l_k u_k)
(if flip?_k
(- (+ l_k u_k -1) i_k)
i_k))
multi-index
(vector->list <var>flip?</var>)
lowers
uppers))))</code></pre>
<p>Then if <code><var>array</var></code> is specialized, then <code>array-reverse</code> returns </p>
<pre><code>
(specialized-array-share
<code><var>array</var></code>
domain
(lambda multi-index
(apply values
(flip-multi-index multi-index))))</code></pre>
<p>Otherwise, if <code><var>array</var></code> is mutable, then <code>array-reverse</code> returns</p>
<pre><code>
(make-array
domain
(lambda multi-index
(apply (array-getter <code><var>array</var></code>)
(flip-multi-index multi-index)))
(lambda (v . multi-index)
(apply (array-setter <code><var>array</var></code>)
v
(flip-multi-index multi-index)))))</code></pre>
<p>Finally, if <code><var>array</var></code> is immutable, then <code>array-reverse</code> returns </p>
<pre><code>
(make-array
domain
(lambda multi-index
(apply (array-getter <code><var>array</var></code>)
(flip-multi-index multi-index))))) </code></pre>
<p>It is an error if <code><var>array</var></code> and <code><var>flip?</var></code> don't satisfy these requirements.</p>
<p><b>Procedure: </b><code><a name="array-sample">array-sample</a> <var>array</var> <var>scales</var></code></p>
<p>We assume that <code><var>array</var></code> is an array all of whose lower bounds are zero, and <code><var>scales</var></code> is a vector of positive exact integers whose length is the same as the dimension of <code><var>array</var></code>.</p>
<p><code>array-sample</code> returns a new array that is specialized, mutable, or immutable according to whether <code><var>array</var></code> is specialized, mutable, or immutable, respectively. Informally, if we construct a new matrix $S$ with the entries of <code><var>scales</var></code> on the main diagonal, then the $\vec i$th element of <code>(array-sample <var>array</var> <var>scales</var>)</code> is the $S\vec i$th element of <code><var>array</var></code>.</p>
<p>More formally, if <code><var>array</var></code> is specialized, then <code>array-sample</code> returns </p>
<pre><code>
(specialized-array-share
<code><var>array</var></code>
(interval-scale (array-domain <code><var>array</var></code>)
<code><var>scales</var></code>)
(lambda multi-index
(apply values
(map * multi-index (vector->list <code><var>scales</var></code>)))))</code></pre>
<p>Otherwise, if <code><var>array</var></code> is mutable, then <code>array-sample</code> returns</p>
<pre><code>
(make-array
(interval-scale (array-domain <code><var>array</var></code>)
<code><var>scales</var></code>)
(lambda multi-index
(apply (array-getter <code><var>array</var></code>)
(map * multi-index (vector->list <code><var>scales</var></code>))))
(lambda (v . multi-index)
(apply (array-setter <code><var>array</var></code>)
v
(map * multi-index (vector->list <code><var>scales</var></code>)))))</code></pre>
<p>Finally, if <code><var>array</var></code> is immutable, then <code>array-sample</code> returns </p>
<pre><code>
(make-array
(interval-scale (array-domain <code><var>array</var></code>)
<code><var>scales</var></code>)
(lambda multi-index
(apply (array-getter <code><var>array</var></code>)
(map * multi-index (vector->list <code><var>scales</var></code>)))))</code></pre>
<p>It is an error if <code><var>array</var></code> and <code><var>scales</var></code> don't satisfy these requirements.</p>
<p><b>Procedure: </b><code><a name="array-outer-product">array-outer-product</a> <var>op</var> <var>array1</var> <var>array2</var></code></p>
<p>Implements the outer product of <code><var>array1</var></code> and <code><var>array2</var></code> with the operator <code><var>op</var></code>, similar to the APL function with the same name.</p>
<p>Assume that <code><var>array1</var></code> and <code><var>array2</var></code> are arrays and that <code><var>op</var></code> is a function of two arguments. Assume that <code>(list-tail l n)</code> returns the list remaining after the first <code><var>n</var></code> items of the list <code><var>l</var></code> have been removed, and <code>(list-take l n)</code> returns a new list consisting of the first <code><var>n</var></code> items of the list <code><var>l</var></code>. Then <code><var>array-outer-product</var></code> returns the immutable array</p>
<pre><code>
(make-array (interval-cartesian-product (array-domain array1)
(array-domain array2))
(lambda args
(op (apply (array-getter array1) (list-take args (array-dimension array1)))
(apply (array-getter array2) (list-tail args (array-dimension array1))))))</code></pre>
<p>This operation can be considered a partial inverse to <code>array-curry</code>. It is an error if the arguments do not satisfy these assumptions.</p>
<p><b>Procedure: </b><code><a name="array-map">array-map</a> <var>f</var> <var>array</var> . <var>arrays</var></code></p>
<p>If <code><var>array</var></code>, <code>(car <var>arrays</var>)</code>, ... all have the same domain and <code><var>f</var></code> is a procedure, then <code>array-map</code>
returns a new array with the same domain and getter</p>
<pre><code>
(lambda multi-index
(apply <var>f</var>
(map (lambda (g)
(apply g multi-index))
(map array-getter
(cons <var>array</var> <var>arrays</var>)))))</code></pre>
<p>It is assumed that <code><var>f</var></code> is appropriately defined to be evaluated in this context.</p>
<p>It is expected that <code>array-map</code> and <code>array-for-each</code> will specialize the construction of</p>
<pre><code>
(lambda multi-index
(apply <var>f</var>
(map (lambda (g)
(apply g multi-index))
(map array-getter
(cons <var>array</var>
<var>arrays</var>)))))</code></pre>
<p>It is an error to call <code>array-map</code> if its arguments do not satisfy these conditions.</p>
<p><b>Note: </b>The ease of constructing temporary arrays without allocating storage makes it trivial to imitate, e.g., Javascript's map with index. For example, we can add the index to each element of an array <code><var>a</var></code> by </p>
<pre><code>
(array-map +
a
(make-array (array-domain a)
(lambda (i) i)))</code></pre>
<p>or even</p>
<pre><code>
(make-array (array-domain a)
(let ((a_ (array-getter a)))
(lambda (i)
(+ (a_ i) i))))</code></pre>
<p><b>Procedure: </b><code><a name="array-for-each">array-for-each</a> <var>f</var> <var>array</var> . <var>arrays</var></code></p>
<p>If <code><var>array</var></code>, <code>(car <var>arrays</var>)</code>, ... all have the same domain and <code><var>f</var></code> is an appropriate procedure, then <code>array-for-each</code>
calls</p>
<pre><code>
(interval-for-each
(lambda multi-index
(apply <var>f</var>
(map (lambda (g)
(apply g multi-index))
(map array-getter
(cons <var>array</var>
<var>arrays</var>)))))
(array-domain <var>array</var>))</code></pre>
<p>In particular, <code>array-for-each</code> always walks the indices of the arrays in lexicographical order.</p>
<p>It is expected that <code>array-map</code> and <code>array-for-each</code> will specialize the construction of</p>
<pre><code>
(lambda multi-index
(apply <var>f</var>
(map (lambda (g)
(apply g multi-index))
(map array-getter
(cons <var>array</var>
<var>arrays</var>)))))</code></pre>
<p>It is an error to call <code>array-for-each</code> if its arguments do not satisfy these conditions.</p>
<p><b>Procedure: </b><code><a name="array-fold">array-fold</a> <var>kons</var> <var>knil</var> <var>array</var></code></p>
<p>If we use the defining relations for fold over lists from SRFI-1:</p>