[swift-evolution] [Pitch] New Version of Array Proposal

[Daryle Walker]

> On Jul 23, 2017, at 11:20 PM, Taylor Swift <kelvin13ma at gmail.com> wrote:
> 
> On Sun, Jul 23, 2017 at 11:05 PM, Daryle Walker <darylew at mac.com <mailto:darylew at mac.com>> wrote:
> 
>> On Jul 23, 2017, at 12:04 PM, Taylor Swift <kelvin13ma at gmail.com <mailto:kelvin13ma at gmail.com>> wrote:
> 
>> 
>> Incomplete indexing means 
>> 
>> let fsa:[5, 2; Int] = [5, 2; 2, 4, 3, 5, 4, 6, 5, 7, 6, 8]
>> fsa[3] // [2; 5, 7]
>> 
>> this would be the same as writing 
>> 
>> let fsa:[5; [2; Int]] = [5; [2; 2, 4], [2; 3, 5], [2; 4, 6], [2; 5, 7], [2; 6, 8]]
>> fsa[3] // [2; 5, 7]
>>  
>> in your current system. This would obviate the need to nest FSAs for the purpose of extracting entire rows of data.
> 
> Allowing partial indexing as you show it privileges one dimension over the others, although they’re supposed to be co-equal and the reason a particular dimension is privileged is due to an implementation detail. Or would you allow incomplete indexing on other dimensions besides the first? Where the true-multi-dimensional <-> nested FSA equivalence wouldn’t help you (because the elements are dispersed in the whole array). With complete generics, this could be a library function:
> 
> func removeRow<Dimension: Int, M…: Int, N…: Int, P: Int, T>(array: […M, P, …N; T], row: Int) -> […M, …N; T] where #lengthof(M) == Dimension
> 
> 
> I’m confused as to what the goals of FSAs are here. My understanding is that they are supposed to be a very low-level high-performance type that’s closely linked with the underlying memory representation. That’s why memory order initialization and flattened indexing is allowed, isn’t it? Partial indexing privileges one dimension over the others, precisely because one dimension should be privileged over the others, because it is much faster than a column slice. The partial indexing syntax is good because it emphasizes that this is an inherently fast operation. Whereas arbitrary row extraction should be a special function to emphasize that it is an inherently slow operation.

My vision of FSAs is as a low-ish mid-level type, not a low-level type and definitely not a very-low-level type. Yes, use as implementing parts of an abstract data type is a goal, otherwise why not stick with Array. And performance is a goal. But FSAs should be usable outside of that. That’s one reason my FSAs support multiple dimensions; it’s the opposite of K&R’s decision throwing out multiple dimensions in the original C when its contemporaries had them.

[Another reason for default support for multiple dimensions is that I don’t know if any processor vector-unit types model 2D arrays, or if all are 1D vectors. Limiting FSAs to one dimension means there’s no easy way to model 2D vector-type arrays. Using FSAs to bring processor vector-unit types to the user level is a core goal.]

Memory-order initialization for multi-dimensional arrays when not using explicit indexes is to save on needing to type out said indexes. And to help inform what elements are which when using static indexing. (Static indexing is flattened because my first attempt at making a multi-coordinate version of tuple’s anonymous member access looked dumb.)

By flattened indexing, do you mean the "withUnsafe*Flattening” functions? Those give the users a way to access the array as a collection. And it’s a way to handle functions that want an array of a particular element type, but for any length/shape, an adaptation of the “T[]” parameter type in C functions. The “T[]” parameter type let C programmers write a function for any array segment length, without specializations for “T[1],” “T[2],” “T[3],” and so on. (You have to pass the actual length separately.) This was before C++ templates and allowing function specializations per array length, but using the “T[]” saves on how many specializations are needed (just one instead of per array length used).

If you mean the “for-in” loop, the flattening is meant to be an abstraction. The C-style for loop was removed because we now abstract the iteration over collections so you don’t have to manually maintain an iteration counter. The flat for-loop removes having to manually write loop statements per dimension. If you don’t need the iterator-counter/iteration-coordinate, skipping the need to write the counter(s) anyway is a big savings. The new problem is what to do when you do want the iteration counter(s). For collections, use the “enumerated” method, which just returns a new sequence that is a pair of the original element and the would-have-been iteration counter. For FSAs, since iteration order is unspecified and copying to a bigger array is impractical, I use a new primary expression to get the counter.

To have partial indexing, and keep it only to the first (i.e. outermost) dimension, we can add a new set of global functions:

func withUnsafePartialIndexing<T, Result, M: Int, N…: Int>(of arg: inout [M, …N; T], _ body: (UnsafeBufferPointer<[…N; T]>) throws -> Result) rethrows -> Result

both mutable and immutable. Or maybe add a variant to target a specific row:

func withExtraction<T, Result, M: Int, N…: Int>(ofRow row: Int, from arg: inout [M, …N; T], body: ([…N; T]) throws -> Result) rethrows -> Result

(where the mutable version takes an “inout […N; T]” in the closure). If you want to strip more than one dimension, then do the subsequent dimensions within the closures. These functions would have to wait for complete generics, though.

In fact, the lack of a “constexpr” (to use a C++ term) story really limits FSA declarations (Right now, bounds must be integer literals.), let alone on how much complete generics would help.

— 
Daryle Walker
Mac, Internet, and Video Game Junkie
darylew AT mac DOT com 


-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-evolution/attachments/20170729/e8a8045b/attachment.html>